[附注] 最小集合确实存在

[定义] 项的集合 有一个存在性前提:满足那三条封闭条件的集合中真的有一个最小的。先固定一个背景集合 𝑈,包含节点标签取自 true、false、0、succ、pred、iszero、if 的所有有限有序树(暂不限制每个标签的孩子数量)。𝑈 本身满足三条封闭条件,所以满足条件的 𝑈 的子集至少有一个,取交集不是在对空的一族集合操作。

把所有满足封闭条件的 𝑈 的子集取交集,记为 𝐼:

  • 每个集合都含 true、false、0,所以 𝐼 也含这三个常量;
  • 若 𝑡 1∈𝐼,则 𝑡 1 在每个集合里。每个集合都对三个一元构造封闭,所以 succ 𝑡 1、pred 𝑡 1、iszero 𝑡 1 也在每个集合里,因而在 𝐼 里;
  • 若 𝑡 1,𝑡 2,𝑡 3∈𝐼,它们在每个集合里。每个集合都对 if 构造封闭,所以 if 𝑡 1 then 𝑡 2 else 𝑡 3 也在交集里。

因此 𝐼 满足全部封闭条件,而且按交集的定义,它包含在每个满足条件的集合里。这就是所需的最小集合 ,不是从一堆集合里凭直觉挑一个。

References

[定义] 项的集合 [set-of-terms]

Based on Typsite