Corollary.
良类型项求值到唯一的同类型值
Corollary. 良类型项求值到唯一的同类型值
采用 词项的集合 的有限项、 值与数值 的值、 多步规约 的多步规约, 以及 类型与类型判断 的类型规则. 若 ,则存在唯一的值 ,使得
Proof.
存在性.从 出发,只要有后继就继续规约. 由 规约使大小严格下降 ,每步大小严格下降, 规约链至多有 步,因而必能到达没有后继的项 . 由 保型 对链长归纳,得 . 再用 进展 : 是值或还能规约; 后一种情况已经排除,所以 是具有类型 的值.
唯一性.设 且 ,其中 、 都是值. 对第一条链的长度归纳;归纳性质允许第二条链任意长. 若第一条链有零步,则 .由 值不可规约 , 没有后继, 因此第二条链也只能有零步,. 若第一条链至少有一步,它形如 . 能规约,由 值不可规约 知它不属于值; 第二条链不能有零步,必形如 . 由 确定性 得 . 两条剩余链从同一项出发,第一条的长度更小,由 归纳假设 得 .
∎
类型安全 只排除受阻,不独自保证终止. 这条推论还用到了另行证明的终止性与确定性; 它针对上述未扩展语言,不能直接推广到含一般递归或其他求值规则的语言.