[引理] 反演

以下结论只针对 [定义] 类型与类型判断 的七条类型规则;𝑡:𝑇 表示能由这些规则搭出有限推导,Bool、Nat 分别是布尔类型与自然数类型。

  1. 若 true :𝑇 或 false :𝑇,则 𝑇= Bool。若 0:𝑇,则 𝑇= Nat。
  2. 若 if 𝑡 1 then 𝑡 2 else 𝑡 3:𝑇,则 𝑡 1: Bool,𝑡 2:𝑇,𝑡 3:𝑇。
  3. 若 succ 𝑡 1:𝑇 或 pred 𝑡 1:𝑇,则 𝑇= Nat 且 𝑡 1: Nat。
  4. 若 iszero 𝑡 1:𝑇,则 𝑇= Bool 且 𝑡 1: Nat。
证明
每一条都看推导的最后一步。以第 3 条中的 succ 为例:七条规则里,结论左边形如 succ 𝑡 1 的只有 T-Succ。所以推导的最后一步就是 T-Succ,它的结论类型是 Nat,前提是 𝑡 1: Nat。其余各条同理,每次都只有一条规则可能适用。
∎

References

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

Backlinks

Based on Typsite