Theorem.
保型
Theorem. 保型
采用 类型与类型判断 的类型关系 和 一步规约 的规约关系. 若 且 ,则 .
Proof.
对 作规则归纳( 规则归纳法 ),对 一般化. 每个情形先对 使用 反演 .
对 E-IfTrue,,,反演直接得 ;E-IfFalse 对称,反演得 . 对 E-If,,前提为 ;反演得 、、,对前提用 归纳假设 (取类型为 )得 ,再用 T-If 即得结论. 对 E-PredZero,,反演得 ,用 T-Zero. 对 E-PredSucc, t = pred (succ nv), t' = nv,反演两次先得 且 succ nv : Nat,再得 nv : Nat. 对 E-IsZeroZero 与 E-IsZeroSucc, 是 或 ,反演得 ,用 T-True 或 T-False. 对同余规则 E-Succ,反演得 且 , 归纳假设 给出 ,再用 T-Succ;E-Pred 同理,最后用 T-Pred;E-IsZero 反演得 且 , 归纳假设 给出 ,最后用 T-IsZero.
∎