命题理论(Propositional Theories)

语句集 $\Gamma$ 的模型、$\Gamma$ 的语义后承概念

语句集 $\Gamma$ 的模型

定义：语句集 $\Gamma$ 的模型

对于任意语句集合 $\Gamma$，

一个真值指派 $V$ 是 $\Gamma$ 的模型当且仅当对于所有的 $\varphi\in \Gamma$ 都有 $V(\varphi) = \mathrm{T}$ ； $\mathrm{Mod}(\Gamma)$ 是 $\Gamma$ 的所有模型组成的集合.
对于任意的语句 $\psi$ ，$\Gamma \mid\!\equiv \psi$ 当且仅当对于 $\Gamma$ 的所有模型 $V$ ，都有 $V(\psi)= \mathrm{T}$ .

如果 $\psi\in \Gamma$ ，那么 $\Gamma \mid\!\equiv \psi$ .

例题

请求出 $\Gamma = \left\lbrace p_{n+1}\to p_n : n\in \omega \right\rbrace$ 所有的模型，也就是 $\mathrm{Mod}(\Gamma)$ .

首先，对于 $\forall n \in \omega$ 都能有 $V(p_n) = \mathrm{T}$ 的所有真值指派 $V$ 自然都是 $\Gamma$ 的模型.

对于剩下的情形，都要满足 $V(p_{n+1}\to p_n) = \mathrm{T}$ ，此时真值指派需要满足对于某个 $n$ 有

\[ V(p_i) = \begin{cases} \mathrm{T} , i \leqslant n \\ \mathrm{F} , i > n . \end{cases} \]

因此我们列举了所有的可能模型. $\square$

语义模型的一些性质

对于任意的 $\psi$ ，$\mid\!\equiv\psi \iff \varnothing \mid\!\equiv \psi$ .
对于任意的 $\varphi_0,\cdots,\varphi_n,\psi$ ，以下等价：
1. $\left\lbrace \varphi_0,\cdots,\varphi_n \right\rbrace \mid\!\equiv \psi$ ；
2. $\varphi_0 \land \cdots \land \varphi_n \mid\!\equiv \psi$ ；
3. 对于任意 $i<n$ ，$\left\lbrace \varphi_0,\cdots,\varphi_{i-1} \right\rbrace \mid\!\equiv \varphi_i \land \cdots \land \varphi_n \to \psi$

上述性质由定义可以直接导出. $\square$

集合与模型的关系

对于任意的集合 $\Gamma$ 和 $\Delta$ ，以及任意的语句 $\varphi$ 和 $\psi$ ，

$\Gamma \subseteq \Delta \Rightarrow \mathrm{Mod}(\Delta) \subseteq \mathrm{Mod}(\Gamma)$ .
$\Gamma \mid\!\equiv \psi$ 当且仅当 $\mathrm{Mod}(\Gamma) \subseteq \mathrm{Mod}(\psi)$ .
若 $\Gamma \subseteq \Delta$ 且 $\Gamma \mid\!\equiv \psi$ ，那么 $\Delta \mid\!\equiv \psi$ ;
$\Gamma \cup \left\lbrace \varphi \right\rbrace \mid\!\equiv \psi\iff \Gamma \mid\!\equiv \varphi \to \psi$.

命题理论的概念

命题理论的定义与定理

我们再看 $\Gamma \mid\!\equiv \psi$ ，它可以看作一个说法的符号表示：“在 $\Gamma$ 的假定（公理）下可以推导出 $\psi$”. 因此，有命题理论的定义：

定义：命题理论

若一个语句集合 $T$ 在语义后承的意义下封闭，那么则称 $T$ 为一个命题理论 (Propositional Theory)，也就是说，对于命题理论 $T$ 中任意的 $\varphi$ ,恒有
$$ T \mid!\equiv \varphi \Rightarrow \varphi\in T. $$
$T$ 中的元素也被称为定理 (Theorem).

定义：生成的理论，公理

对于任意语句集 $\Gamma$ ，由 $\Gamma$ 生成的命题理论为集合：
$$ \mathrm{Th}(\Gamma) = \left\lbrace \psi: \Gamma \mid!\equiv \psi \right\rbrace .$$
我们称 $\Gamma$ 是 $\mathrm{Th}(\Gamma)$ 的公理集合.

结合前面的性质，可以导出如下简单结论：

$\Gamma \subseteq \mathrm{Th(\Gamma)}$;
$\mathrm{Mod}(\Gamma) = \mathrm{Mod}(\mathrm{Th}(\Gamma))$ ;
$\mathrm{Th}(\Gamma)$ 是一个命题理论；
$\Gamma \subseteq \Delta \Rightarrow \mathrm{Th}(\Gamma)\subseteq \mathrm{Th}(\Delta)$ ;
$\Gamma$ 是一个命题理论当且仅当 $\Gamma= \mathrm{Th}(\Gamma)$ ;
$\mathrm{Th}(\Gamma)$ 是具有性质 $\Gamma \subseteq T$ 的集合 $T$ ;
$\mathrm{Th}(\varnothing) = \left\lbrace \varphi: \varphi \text{ is a tautology} \right\rbrace$ 被包含在所有的命题理论当中.

命题理论的相容

语句集的相容

定义：语句集的相容和完全

对于任意语句集 $\Gamma$ ，

(i) 若 $\Gamma$ 至少有一个模型，则 $\Gamma$ 是相容 (consistent) 的，否则则称不相容 (inconsistent).

(ii) 若对于任何语句 $\varphi$ ， $\varphi\in\Gamma$ 和 $\neg\varphi\in \Gamma$ 总有且仅有一个属于 $\Gamma$ ，则称 $\Gamma$ 为完全 (Complete) 的. 否则则为不完全 (Incomplete) 的.

真值指派的理论

定义：真值指派的理论

对于任意的真值指派 $V$ ，$V$ 的理论定义为集合：
$$ \mathrm{Th}(V) = \left\lbrace \psi: V(\psi)=\mathrm{T} \right\rbrace $$

定理

对于任何的真值指派 $V$ ，

(i) $\mathrm{Th}(V)$ 是一个完全且相容的命题理论，并且 $V$ 是其唯一的模型.

(ii) 对于任意的真值指派 $W$ ，$V=W\iff \mathrm{Th}(V) = \mathrm{Th}(W)$ .

$\mathrm{Th}(V)$ 有 $V$ 这一个模型，从而相容，并且对于 $\varphi\in \mathrm{Th}(V)$ ，$V(\varphi) = \mathrm{T} \iff V(\neg\varphi) = \mathrm{F}$ ，因此它也是完全的.
最后，如果存在另一个模型 $W$ ，那么 $V(\varphi)=\mathrm{T}$ 成立时，自然有 $W(\varphi) = \mathrm{T}$ 成立，反过来：

\[ V(\varphi)=\mathrm{F} \Rightarrow V(\neg \varphi)=\mathrm{T}\Rightarrow W(\neg \varphi) = \mathrm{T} \Rightarrow W(\varphi) =\mathrm{F} \]

从而 $V=W$ 成立. $\square$

命题理论集合的势

定理：命题理论不可数

对于集合 $E =\left\lbrace T: T \text{ is a propositional theory} \right\rbrace$ ，也就是所有命题理论构成的集合，它的势是多少？

一方面，由推论可知集合 $E$ 至少为连续统势，另一方面，$T \subseteq \mathrm{Sent}_L$ ，因此 $E \subseteq \mathcal{P}(\mathrm{Sent}_L)$ ，其中 $\mathcal{P}(A)$ 表示 $A$ 的幂集. 那么由于 $\mathrm{Sent}_L$ 是可数集，则 $E$ 的势不超过连续统势，合起来可知 $E$ 的势是连续统势. $\square$

完全延拓

定理

对于语句集合 $\Gamma$ 和任意的命题理论 $T$ ，下面的结论等价：

$T$ 是一个完全的命题理论且 $\Gamma\subseteq T$ .（此时称 $T$ 为 $\Gamma$ 的完全延拓）
对于 $\Gamma$ 的一些模型 $V$ ，$T=\mathrm{Th}(V)$ .

留个坑日后再证明. $\square$

可公理化类

定义：真值指派类的理论

对于任意非空真值指派类 $K$ ，$K$ 的理论定义为：
$$ \mathrm{Th}(K) = \left\lbrace \psi: V(\psi)=\mathrm{T} \text{ for all } V\in K\right\rbrace $$

说白了就是将一堆真值指派归类，整体的理论就是每一个真值指派的理论的交.

命题

对于任意非空真值指派类 $K$ ,

$\mathrm{Th}(K)$ 是一个相容的命题理论，并且每个 $V\in K$ 都是 $\mathrm{Th}(K)$ 的模型.
如果 $K$ 至少有两个不同的元素，那么 $\mathrm{Th}(K)$ 是不完全的.

紧性 (Compactness)

PCT

定理：命题紧性定理 (Propositional Compactness Theorem, PCT)

对于任意的语句集 $T$ 和任意的语句 $\psi$ ：$\Gamma\mid\!\equiv \psi$ 当且仅当存在有限集 $\Gamma_0 \subseteq \Gamma$ ，$\Gamma_0 \mid\!\equiv \psi$ .

我们为了符号上的表达方便，直接引入 $\Gamma\mid\!\equiv^* \psi$ ，将其定义为 $\Gamma$ 存在有限子集 $\Gamma_0$ 使得 $\Gamma_0\mid\!\equiv \psi$ . 因此 PCT 可以简单表示为：

\[ \Gamma\mid\!\equiv \psi \iff \Gamma\mid\!\equiv^* \psi \]

有限相容

定义：有限相容

一个语句集 $\Gamma$ 是有限相容的当且仅当其每一个有限子集 $\Gamma_0$ 都是相容的.

APCT

定理：APCT (Alternative Propositional Compactness Theorem)

对于任意语句集 $\Gamma$，如果 $\Gamma$ 是有限相容的，那么 $\Gamma$ 是相容的.

引理

对于任意语句集 $\Gamma$ 和任意 $\psi$ ：

$\Gamma\mid\!\equiv^* \psi$ 当且仅当 $\Gamma\cup \left\lbrace \neg \psi \right\rbrace$ 不是有限相容的.

APCT 和 PCT 的等价性

下面考虑证明 APCT 和 PCT 的等价性.

从 APCT 到 PCT ：$\Gamma\mid\!\equiv \psi$ 时，$\Gamma\cup \left\lbrace \neg \psi \right\rbrace$ 不相容，因此根据 APCT 可知它不有限相容，根据前面的引理可以知道 $\Gamma\mid\!\equiv^* \psi$ 成立.

从 PCT 到 APCT ：$\Gamma$ 有限相容时，其任意有限子集都是相容的，因此对于任意 $\psi$ ，如果 $\Gamma_0\mid\!\equiv \psi$ 不成立，那么由 PCT 可知 $\Gamma\mid\!\equiv \psi$ 也不成立，因此 $\Gamma$ 是相容的. $\square$

相容、完全、有限相容的推导关系

命题：有限相容+完全=相容

任意有限相容且完全的语句集都是相容的.