Theorem.
进展
Theorem. 进展
采用 类型与类型判断 的类型关系、 值与数值 的值定义, 以及 一步规约 的规约关系. 若 ,则 是值,或存在 使 .
Proof.
对 作规则归纳 (类型推导版本的 规则归纳法 ), 按最后一步的规则分情形.
若最后一步是 T-True、T-False 或 T-Zero,则 本身就是值. 若最后一步是 T-If,则 ,前提里有 ;对 用 归纳假设 ,若 能规约,由 E-If 知 也能规约;若 是值,由 典范形式 第 1 条知它是 或 ,可分别用 E-IfTrue、E-IfFalse. 若最后一步是 T-Succ,前提为 ;若 能规约,用 E-Succ;若 是值,由 典范形式 第 2 条知它是数值 nv,于是 t = succ nv 本身也是数值,自然也是值. 若最后一步是 T-Pred,前提为 ;若 能规约,用 E-Pred;若 是值,则它是数值,等于 时用 E-PredZero,形如 succ nv' 时用 E-PredSucc. T-IsZero 的情形与 T-Pred 相同,分别用 E-IsZero、E-IsZeroZero、E-IsZeroSucc.
∎