[定理] 类型唯一

对 [定义] 类型与类型判断 的七条类型规则,若 𝑡:𝑇 且 𝑡:𝑇 ′,则 𝑇=𝑇 ′。

证明

对 𝑡 结构归纳( [约定] 归纳证明的写法 ),对 𝑇、𝑇 ′ 一般化。

  • 常量、succ 𝑡 1、pred 𝑡 1、iszero 𝑡 1:由 [引理] 反演 ,类型被项的形状直接定死(Bool 或 Nat),所以 𝑇=𝑇 ′。
  • if 𝑡 1 then 𝑡 2 else 𝑡 3:由 [引理] 反演 第 2 条,𝑡 2:𝑇 且 𝑡 2:𝑇 ′。𝑡 2 是直接子项,由 归纳假设 𝑇=𝑇 ′。
∎

References

[定义] 类型与类型判断 [types-and-typing-judgments]

[约定] 归纳证明的写法 [writing-inductive-proofs]

[引理] 反演 [typing-inversion]

[定义] 归纳假设 [induction-hypothesis]

Backlinks

Based on Typsite