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