谓词逻辑

$\forall x\, P(x)$ 意味着“无论把 $x$ 换成什么,$P$ 都成立”——所以代入任意具体的项 $t$,$P(t)$ 也必须成立。这条规则把一般规律变成具体实例:从“$\forall x\, (\text{Human}(x) \to \text{Mortal}(x))$”在 $t = \text{Socrates}$ 处实例化,得到“$\text{Human}(\text{Socrates}) \to \text{Mortal}(\text{Socrates})$”,即经典三段论的第一个前提。

我们直接从塔斯基满足语义出发论证,该语义按公式结构递归定义了在一个结构中的真。

由 $\forall$ 的语义子句:$\mathcal{M} \models_s \forall x\, P(x) \iff \text{for every } d \in M,\ \mathcal{M} \models_{s[x \mapsto d]} P(x)$。假设前提 $\mathcal{M} \models_s \forall x\, P(x)$;由此子句,$\mathcal{M} \models_{s[x \mapsto d]} P(x)$ 对每个 $d \in M$ 都成立,毫无例外。

既然该断言对每个 $d \in M$ 都成立,它特别地对 $d = t^{\mathcal{M},s}$(项 $t$ 在赋值 $s$ 下于 $\mathcal{M}$ 中所表示的元素)也成立。代入这个特定的 $d$,得到 $\mathcal{M} \models_{s[x \mapsto t^{\mathcal{M},s}]} P(x)$。

由代入引理(一个把变量赋值与项代入联系起来的标准结果,可对 $P$ 的结构作归纳证明):$\mathcal{M} \models_{s[x \mapsto t^{\mathcal{M},s}]} P(x) \iff \mathcal{M} \models_s P(t)$,该引理恰好在 $t$ 对 $P(x)$ 中的 $x$ 可代入时成立(即 $t$ 的自由变量不会被意外约束)。应用此引理,把 $\mathcal{M} \models_{s[x \mapsto t^{\mathcal{M},s}]} P(x)$ 转化为 $\mathcal{M} \models_s P(t)$。

由于 $\mathcal{M}$、$s$、$t$ 都是任意的,从 $\forall x\, P(x)$ 到 $P(t)$ 的推理在每个结构、每种赋值下都保真:该规则是可靠的。

$\exists y\, \forall x\, R(x,y)$ 要求存在单一的见证元素 $y$ 对每个 $x$ 都适用(“固定”见证),而 $\forall x\, \exists y\, R(x,y)$ 只要求每个 $x$ 都有某个见证元素,不同的 $x$ 可以对应不同的见证元素(“可变”见证)。固定见证自动也是可变见证(重复使用即可),但反过来不然——这正是“有人爱着所有人”(一个普遍的爱人)与“人人都被某人所爱”(可能各不相同)之间的区别,是谓词逻辑澄清的自然语言中经典的歧义来源。

正向。 设 $\mathcal{M} \models_s \exists y\, \forall x\, R(x,y)$。由 $\exists$ 的语义子句,$\mathcal{M} \models_s \exists y\, \varphi \iff \text{there is } d \in M \text{ with } \mathcal{M} \models_{s[y \mapsto d]} \varphi$;应用于此处得到某个 $d_0 \in M$ 使得 $\mathcal{M} \models_{s[y \mapsto d_0]} \forall x\, R(x,y)$。

对此应用 $\forall$ 的子句,得 $\mathcal{M} \models_{s[y \mapsto d_0][x \mapsto a]} R(x,y)$ 对每个 $a \in M$ 都成立,因为 $\forall x$ 遍历整个 $M$,与之后选取哪个 $a$ 无关。

现在固定任意 $a \in M$ 来验证 $\forall x\, \exists y\, R(x,y)$。由上一段,取 $x \mapsto a$ 得 $\mathcal{M} \models_{s[y \mapsto d_0][x \mapsto a]} R(x,y)$,这表明在 $x \mapsto a$ 下 $d_0$ 本身就是 $\exists y\, R(x,y)$ 的见证元素;因此 $\mathcal{M} \models_{s[x \mapsto a]} \exists y\, R(x,y)$。

由于 $a \in M$ 是任意的,$\mathcal{M} \models_{s[x \mapsto a]} \exists y\, R(x,y)$ 对每个 $a$ 都成立,这正是 $\mathcal{M} \models_s \forall x\, \exists y\, R(x,y)$ 的语义子句。这就证明了 $\exists y\, \forall x\, R(x,y) \Rightarrow \forall x\, \exists y\, R(x,y)$。

逆命题不成立:反例。 设 $\mathcal{M}$ 的论域为 $M = \mathbb{Z}$(整数),把 $R(x,y)$ 解释为“$x < y$”。此时 $\forall x\, \exists y\, R(x,y)$ 为真:对每个整数 $x$,取 $y = x+1$ 即有 $x < y$。但 $\exists y\, \forall x\, R(x,y)$ 为假:它需要一个单一整数 $y$ 大于每个整数 $x$,而不存在这样的最大整数(对任何候选 $y$,整数 $y+1$ 都违反 $y+1 < y$)。所以 $\forall x\, \exists y\, R(x,y)$ 成立而 $\exists y\, \forall x\, R(x,y)$ 不成立,说明逆蕴含一般不成立。