Lemma. 反演

这里的四条结论只针对 类型与类型判断 的七条类型规则; 𝑡:𝑇 表示能由这些规则搭出有限推导,Bool、Nat 分别是布尔类型与自然数类型. 第 1 条,若 true :𝑇 或 false :𝑇,则 𝑇= Bool;若 0:𝑇,则 𝑇= Nat. 第 2 条,若 if 𝑡 1 then 𝑡 2 else 𝑡 3:𝑇,则 𝑡 1: Bool,𝑡 2:𝑇,𝑡 3:𝑇. 第 3 条,若 succ 𝑡 1:𝑇 或 pred 𝑡 1:𝑇,则 𝑇= Nat 且 𝑡 1: Nat. 第 4 条,若 iszero 𝑡 1:𝑇,则 𝑇= Bool 且 𝑡 1: Nat.

Proof.
每一条都看推导的最后一步. 以第 3 条中的 succ 为例:七条规则里,结论左边形如 succ 𝑡 1 的只有 T-Succ. 所以推导的最后一步就是 T-Succ,它的结论类型是 Nat,前提是 𝑡 1: Nat. 其余各条同理,每次都只有一条规则可能适用.
∎