至多可数紧性 (Countable Compactness)

至多可数紧性定理 (CCT)

定理：至多可数紧性定理 (Countable Compactness Theorem, CCT)

对于任意至多可数语言 \(L\) ，任意 \(L\)-公式集 \(\Gamma\) 以及任意的 \(L\)-公式 \(\psi\) ，\(\Gamma \models \psi\) 当且仅当存在有限子集 \(\Gamma_0 \subseteq \Gamma, \Gamma_0 \models \psi\) .

如果我们将 “存在有限子集 \(\Gamma_0 \subseteq \Gamma\) 使得 \(\Gamma_0\models \psi\)” 写为 \(\Gamma\models^* \psi\) ，那么 CCT 其实就说明了一件事就是

\[ \Gamma\models^* \psi \iff \Gamma \models \psi \]

对于所有满足 \(\Gamma\models^* \psi\) 的语句 \(\psi\) ，它们组成的集合记为 \(\mathrm{Th}^*(\Gamma)\) ，实际上也就是 \(\mathrm{Th}(\Gamma)= \mathrm{Th}^*(\Gamma)\) .

接下来，先补充 \(L\) 公式集的有限相容的概念，\(\Gamma\) 有限相容，如果对于所有的有限子集 \(\Gamma_0 \subseteq \Gamma\) ，\(\Gamma_0\) 都是相容的.

引理

对于任意公式集 \(\Gamma\) 和任意公式 \(\psi\) ，\(\Gamma\models^* \psi \iff \Gamma\cup \left\lbrace \neg \psi \right\rbrace\) 不是有限相容的.

证明：

\(\Gamma\models^* \psi\) ，则存在 \(\Gamma_0 \subseteq \Gamma\) 使得 \(\Gamma_0 \models \psi\) ，此时 \(\Gamma_0\cup \left\lbrace \neg \psi \right\rbrace\) 是不相容的. 对于所有满足 \(\Gamma_0\models \psi\) 的 \(\Gamma_0\) 都有这个不相容的结论，因此 \(\Gamma\cup \left\lbrace \neg \psi \right\rbrace\) 是不有限相容的. \(\square\)

ACCT

ACCT 介绍

定理：ACCT (Alternative Countable Compactness Theorem)

对于任意可数语言 \(L\) 以及任意 \(L\)-公式集 \(\Gamma\) ，如果 \(\Gamma\) 是有限相容的，那么 \(\Gamma\) 是相容的.

（从 ACCT 证明 CCT）：

考虑 \(\Gamma\models \psi\) ，此时 \(\Gamma\cup \left\lbrace \neg \psi \right\rbrace\) 是不相容的，根据 ACCT 它不是有限相容的，那么根据刚才的引理，\(\Gamma\models^* \psi\) 成立. \(\square\)

ACCT 应用

下面给出 ACCT 应用的例.

模型问题

例：ACCT 应用

设 \(\Gamma\) 是一个语句集，如果 \(\Gamma\) 有任意大的有限模型，即对任意正整数 \(n\) ，存在 \(\Gamma\) 的模型 \(\mathfrak{A}\) 满足 \(|A|\geqslant n\) ，则 \(\Gamma\) 有无限模型.

例如，\(\Gamma = \Gamma_{\mathrm{Gp}}\cup \left\lbrace \varphi \right\rbrace\) ，其中 \(\Gamma_{\mathrm{Gp}}\) 是群公理集，\(\varphi = \forall x(x*x = e)\) . 对于任意的 \(n\) ，考虑

\[ \bigoplus_{i=1}^n \mathbb{Z}_2 \tag{1} \]

注意：
- \(\oplus\) 为群的直和，如果只学过抽象代数 Ⅰ 这个部分没有学到，在两个群 \(G\) 和 \(H\) 都是交换群的时候，\(G\times H\) 就称为直和. 群的直和依旧是群，且计算为每位依次计算.
- 这里的运算为加法运算，可以理解为 \(n\) 位的二进制数加法，此时不存在进位，因此根据 \(\overline{1}+\overline{1} = \overline{0}\) 和 \(\overline{0}+\overline{0}=\overline{0}\) ，\(x+x=e\) 是正确的.

此时的 (1) 就是符合题意的模型. 由 \(n\) 的任意性可知有无限模型. \(\square\)

推论

设 \(\varphi\) 是一个语句，若 \(\varphi\) 的谱 \(\mathrm{Sp}(\varphi)\) 为无限集，则 \(\varphi\) 有无限模型.

可公理化问题

例：ACCT 可公理化问题

性质 "\(\mathfrak{A}\) 的全域是有限集" 不是可公理化的.