Theorem. 进展

采用 类型与类型判断 的类型关系、 值与数值 的值定义, 以及 一步规约 的规约关系. 若 𝑡:𝑇,则 𝑡 是值,或存在 𝑡 ′ 使 𝑡⟶𝑡 ′.

Proof.

对 𝑡:𝑇 作规则归纳 (类型推导版本的 规则归纳法 ), 按最后一步的规则分情形.

若最后一步是 T-True、T-False 或 T-Zero,则 𝑡 本身就是值. 若最后一步是 T-If,则 𝑡= if 𝑡 1 then 𝑡 2 else 𝑡 3,前提里有 𝑡 1: Bool;对 𝑡 1 用 归纳假设 ,若 𝑡 1 能规约,由 E-If 知 𝑡 也能规约;若 𝑡 1 是值,由 典范形式 第 1 条知它是 true 或 false,可分别用 E-IfTrue、E-IfFalse. 若最后一步是 T-Succ,前提为 𝑡 1: Nat;若 𝑡 1 能规约,用 E-Succ;若 𝑡 1 是值,由 典范形式 第 2 条知它是数值 nv,于是 t = succ nv 本身也是数值,自然也是值. 若最后一步是 T-Pred,前提为 𝑡 1: Nat;若 𝑡 1 能规约,用 E-Pred;若 𝑡 1 是值,则它是数值,等于 0 时用 E-PredZero,形如 succ nv' 时用 E-PredSucc. T-IsZero 的情形与 T-Pred 相同,分别用 E-IsZero、E-IsZeroZero、E-IsZeroSucc.

∎