カリー＝ハワード同型対応
第二の公理図式から ( α → ( β → α ) → α ) → ( α → β → α ) → α → α {\displaystyle (\alpha \to (\beta \to \alpha )\to \alpha )\to (\alpha \to \beta \to \alpha )\to \alpha \to \alpha } を得る、
第一の公理図式から α → ( β → α ) → α {\displaystyle \alpha \to (\beta \to \alpha )\to \alpha } を得る、
第一の公理図式から α → β → α {\displaystyle \alpha \to \beta \to \alpha } を得る、
モーダス・ポネンスを2回適用して α → α {\displaystyle \alpha \to \alpha } を得る。
ハスケル・カリーがヒルベルト流の体系とコンビネータ論理の構文的対応を強調した後、ウィリアム・アルヴィン・ハワードは1969年に単純型付きラムダ計算と自然演繹との構文的な同型性を明確にした。以下、左辺で直観主義的自然演繹の含意断片を形式化し、右辺でラムダ計算の型付け規則を示す。左辺では Γ , Γ 1 , Γ 2 {\displaystyle \Gamma ,\Gamma _{1},\Gamma _{2}} で順序付けられた論理式の列を表す。右辺ではラムダ項で名前付けられた論理式の列を表す。
この対応を言い換えれば、 Γ ⊢ α {\displaystyle \Gamma \vdash \alpha } を証明するということは、型宣言列 Γ {\displaystyle \Gamma } のもとで型 α {\displaystyle \alpha } を持つオブジェクトを構成することに対応する。公理は新しい変数の導入(とその型宣言)に、→ I 規則は関数抽象に、→ E 規則は関数適用に対応する。もし左辺の文脈 Γ {\displaystyle \Gamma } を単なる論理式の集合と見做す(暗黙の縮約と弱化を認める)ならば、この対応は正確ではないことが分かる。というのも、例えば Γ {\displaystyle \Gamma } の中にラムダ項 λ x . λ y .