Theorem. 保型

采用 类型与类型判断 的类型关系 和 一步规约 的规约关系. 若 𝑡:𝑇 且 𝑡⟶𝑡 ′,则 𝑡 ′:𝑇.

Proof.

对 𝑡⟶𝑡 ′ 作规则归纳( 规则归纳法 ),对 𝑇 一般化. 每个情形先对 𝑡:𝑇 使用 反演 .

对 E-IfTrue,𝑡= if  true  then 𝑡 2 else 𝑡 3,𝑡 ′=𝑡 2,反演直接得 𝑡 2:𝑇;E-IfFalse 对称,反演得 𝑡 3:𝑇. 对 E-If,𝑡 ′= if 𝑡 1 ′ then 𝑡 2 else 𝑡 3,前提为 𝑡 1⟶𝑡 1 ′;反演得 𝑡 1: Bool、𝑡 2:𝑇、𝑡 3:𝑇,对前提用 归纳假设 (取类型为 Bool)得 𝑡 1 ′: Bool,再用 T-If 即得结论. 对 E-PredZero,𝑡 ′=0,反演得 𝑇= Nat,用 T-Zero. 对 E-PredSucc, t = pred (succ nv), t' = nv,反演两次先得 𝑇= Nat 且 succ nv : Nat,再得 nv : Nat. 对 E-IsZeroZero 与 E-IsZeroSucc,𝑡 ′ 是 true 或 false,反演得 𝑇= Bool,用 T-True 或 T-False. 对同余规则 E-Succ,反演得 𝑇= Nat 且 𝑡 1: Nat, 归纳假设 给出 𝑡 1 ′: Nat,再用 T-Succ;E-Pred 同理,最后用 T-Pred;E-IsZero 反演得 𝑇= Bool 且 𝑡 1: Nat, 归纳假设 给出 𝑡 1 ′: Nat,最后用 T-IsZero.

∎