カリー＝ハワード同型対応
「証明=プログラム」対応はゲンツェンのシークエント計算においても確立されるが、ヒルベルト流の体系や自然演繹のように、既に知られていたような計算模型との対応関係は存在しない。
シークエント計算は左導入規則、右導入規則、ならびに除去可能なカット規則により特徴づけられる。シークエント計算の構造はある種の抽象機械の構造に似ている。非形式的な対応は次のようである:
t : α ⟶ β u : α ⟶ γ ⟨ t , u ⟩ : α ⟶ β × γ {\displaystyle {\frac {t:\alpha \longrightarrow \beta \qquad u:\alpha \longrightarrow \gamma }{\langle t,u\rangle :\alpha \longrightarrow \beta \times \gamma }}}
射影:
π 1 : α × β ⟶ α π 2 : α × β ⟶ β {\displaystyle {\frac {}{\pi _{1}:\alpha \times \beta \longrightarrow \alpha }}\qquad {\frac {}{\pi _{2}:\alpha \times \beta \longrightarrow \beta }}}
カリー化:
t : α × β ⟶ γ λ t : α ⟶ β → γ {\displaystyle {\frac {t:\alpha \times \beta \longrightarrow \gamma }{\lambda t:\alpha \longrightarrow \beta \rightarrow \gamma }}}
評価:
e v a l : ( α → β ) × α ⟶ β {\displaystyle {\frac {}{eval:(\alpha \rightarrow \beta )\times \alpha \longrightarrow \beta }}}
最後に、圏の等式を次により定める:
i d ∘ t = t , t ∘ i d = t , ( v ∘ u ) ∘ t = v ∘ ( u ∘ t ) , {\displaystyle id\circ t=t,t\circ id=t,(v\circ u)\circ t=v\circ (u\circ t),}
S : ( δ → ( α → β → γ ) → ( α → β ) → α → γ ) → ( δ → α → β → γ ) → δ → ( α → β ) → α → γ {\displaystyle S:(\delta \to (\alpha \to \beta \to \gamma )\to (\alpha \to \beta )\to \alpha \to \gamma )\to (\delta \to \alpha \to \beta \to \gamma )\to \delta \to (\alpha \to \beta )\to \alpha \to \gamma }
を得る。これと先の論理式にモーダス・ポネンスを適用すれば、
S ( K S ) : ( δ → α → β → γ ) → δ → ( α → β ) → α → γ {\displaystyle S(KS):(\delta \to \alpha \to \beta \to \gamma )\to \delta \to (\alpha \to \beta )\to \alpha \to \gamma }