力迫

王浩老师的《数理逻辑通俗讲话》上有一个关于力迫的有趣引理（这本书跟“通俗”一点不沾边，可能它面向的是数学系吧）。我们向集合论语言 Ը 中加入一个新常元 G 得到语言 Ը' ，令 p 是一个特征函数，其中 dom(p) ⊂ ω ∧ |p|＜ω，且对于任意 i∈dom(p) ，都有 p(i)＝1∨p(i)＝0。规定力迫关系：对于任意不含 G 的公式 ф ，M╞ ф ⇔ p ⊩ ф； p(x)＝1 ⇔ p ⊩ G(x)＝1；p ⊩ ψ ∧ ф ⇔ p ⊩ ψ ∧ p ⊩ ф；p ⊩ ¬ψ ⇔ ∀q ⊇ p，q ⊮ ψ； p ⊩ ∃xψ ⇔ ∃x，p ⊩ ψ(x) 。注意我们的初始逻辑符号没有析取、蕴含和全称量词。根据力迫关系的定义，不难证明如下引理成立：

引理1：q ⊇ p → (p ⊩ ψ → q ⊩ ψ)。

引理2：p ⊮ ψ ∧ ¬ψ。

引理3：如果 p ⊮ ψ ，那么存在 q ⊇ p 满足 q ⊩ ¬ψ¬ψ。

证明：对公式递归即可。

我们称引入的常元G 对应的集合是generic，当且仅当对于任意 Ը' 公式 ф ， G ⊩ ф 或者 G ⊩ ¬ψ，其中 G ⊩ ф ⇔ ∃p ⊂ G，p ⊩ ф 。

定理：对于任意p ∈ P，存在generic的 G ⊃ p 。

证明：令ф₁，ф₂，· · · 是 Ը' 的一个枚举，根据引理 3 可得如果 p ⊮ ф₁ ，那么存在 q ⊃ p 满足 q ⊩ ¬ф₁，令 q＝p₁ ，那么递归可得 p₁，p₂，· · · 最后令 G＝∪pᵢ 即可

ᵢ∈ω

，不难验证 G ⊩ ф 或者 G ⊩ ¬ф 。

此时的G 是一个 ω 的函数，那么这是一个什么样的函数呢？

引理4：G ⊩ G is infinity 。

证明：用反证法。假设存在p ⊂ G ，p ⊩ ∃n ∈ ω∀x(G(x)＝1 → x ≤ n)，那么 p ⊩ ∀x(G(x)＝1 → x ≤ n) ，根据力迫关系可得不存在 q ⊃ p 满足 q ⊩ ∃x(G(x)＝1∧x ≥ n)。由于 p 的定义域有上界，不妨设 dom(p)∪n ⊂ i，那么 q＝p∪{〈i，1〉} ⊩ G(i)＝1∧n∈i，矛盾，反证引理 4 成立。

引理5： G 力迫“G 的任意算术子集都是有穷的”。

证明：令ψ(x) 定义了 G 的算术子集 A ，那么存在 p ⊂ G 满足 p ⊩ ∀x(ψ(x) → x∈G)，由于 p 的定义域有限，因此只有有限个 x∈ω 满足 p ⊩ x∈G，这蕴含只有有限个 x 满足 p ⊩ ψ(x) ，因此 p 力迫“ A 是有穷集合”， G 也力迫“ A 是有穷集合”，引理 5 得证。

推论1： G 不是算术子集。

证明：由引理4，5 可得。