Corollary. 良类型项求值到唯一的同类型值

采用 词项的集合 的有限项、 值与数值 的值、 多步规约 的多步规约, 以及 类型与类型判断 的类型规则. 若 𝑡:𝑇,则存在唯一的值 𝑣,使得

𝑡⟶ ∗𝑣 且 𝑣:𝑇.

Proof.

存在性.从 𝑡 出发,只要有后继就继续规约. 由 规约使大小严格下降 ,每步大小严格下降, 规约链至多有 size( 𝑡 )−1 步,因而必能到达没有后继的项 𝑢. 由 保型 对链长归纳,得 𝑢:𝑇. 再用 进展 :𝑢 是值或还能规约; 后一种情况已经排除,所以 𝑢 是具有类型 𝑇 的值.

唯一性.设 𝑡⟶ ∗𝑣 且 𝑡⟶ ∗𝑤,其中 𝑣、𝑤 都是值. 对第一条链的长度归纳;归纳性质允许第二条链任意长. 若第一条链有零步,则 𝑡=𝑣.由 值不可规约 ,𝑡 没有后继, 因此第二条链也只能有零步,𝑤=𝑡=𝑣. 若第一条链至少有一步,它形如 𝑡⟶𝑡 1⟶ ∗𝑣. 𝑡 能规约,由 值不可规约 知它不属于值; 第二条链不能有零步,必形如 𝑡⟶𝑡 2⟶ ∗𝑤. 由 确定性 得 𝑡 1=𝑡 2. 两条剩余链从同一项出发,第一条的长度更小,由 归纳假设 得 𝑣=𝑤.

∎

类型安全 只排除受阻,不独自保证终止. 这条推论还用到了另行证明的终止性与确定性; 它针对上述未扩展语言,不能直接推广到含一般递归或其他求值规则的语言.