测试逻辑(Experimental logic literature)[2] 语义与推理(Semantics and Deduction)(WIP)

集合论想学自己学去吧, 该回归一般意义上的数理逻辑了. 另外本系列持续使用中文写作.

默认的latex编译器又哈哈了, 喜欢我美刀吗￥￥￥

上期我们浪费了一期在最为基础的集合论上, 然而集合论并不是一个很好的例子, 毕竟其中很多东西若深入讨论需要大量基础, 关于其的开放问题也是数不胜数. 若未来还会举例子的话, 估计会是某些带明显反例的语言, 如Smullyan的SELF或Robinson算数. 本期我们先介绍一个公式是如何被解释的, 再介绍一阶语言中的证明系统.

1 模型(model)与解释(interpretation)

对一个一阶语言L, 我们对它的模型与解释是一个二元组(M,\phi), 其中M是一个集合, 而\phi是一个以L的字母表(除去变量)为定义域的映射, 满足:
对任意常量c, \phi(c)\in M;
对任意度数为r的算子f, \phi(f)是一个M^r到M的映射;
对任意度数为r的关系p, \phi(p)是M^r的一个子集.

例子1.1 (\mathbb N,\phi)使得\phi(+), \phi(\cdot)是通常的加法与乘法, \phi(\bar 0)=0, \phi(\bar 1)=1, \phi(=)=\lbrace (x,x):x\in\mathbb N\rbrace是一个\text{L}_1\text{Ar}的模型.

在规定了解释后, 我们就可以理解公式的真值(truth value). 然而变量顾名思义是会变的量, 所以我们先规定在一个特定的变量赋值下某公式的真值.
令\bar M为所有从变量字母表到M的映射构成的集合, 对\xi\in\bar M, 首先归纳定义项t在\xi下被映射到的值t^\xi:
若t=c为常量, 则t^\xi=\phi(c);
若t=x为变量, 则t^\xi=\xi(x);
若t=f(t_1,...,t_r), t^\xi=\phi(f)(t_1^\xi,...,t_r^\xi).
由归纳原理对t中算子个数归纳可得这样的t^\xi对每个t都是唯一定义的. 注意对算子个数, 或联词加上量词个数归纳, 是基础数理逻辑中的重要方法!
紧接着我们归纳定义公式P的真值|P|(\xi):
若P=p(t_1,...,t_r), |P|(\xi)=1当且仅当(t_1^\xi,...,t_r^\xi)\in\phi(p);
若P=\neg Q, |P|(\xi)=1-|Q|(\xi);
若P=Q\vee R, |P|(\xi)=|Q|(\xi)+|R|(\xi)-|Q|(\xi)|R|(\xi);
以此类推由逻辑联词自然的意义计算真值...
若P=\forall xQ, |P|(\xi)=\min\limits_{\zeta\in X}|Q|(\zeta), 其中X=\lbrace\zeta:\forall y(y\ne x\Rightarrow\zeta(y)=\xi(y))\rbrace;
相似地, 若P=\exists xQ, |P|(\xi)=\max\limits_{\zeta\in X}|Q|(\zeta).
注意这些真值不仅与\xi有关, 更基础的影响因素是模型的选取. 严格来说记号应为|P|_\phi(\xi), 不过接下来在不产生歧义的情况下均将下标简略.

然而大多数时候我们期望中的公式应该有一个不依赖于\xi的真值, 如\forall x(x=\bar0)在\text L_1\text{Ar}的标准模型下应该对任何\xi都有真值0. 为了严格定义这种公式, 我们首先引入自由(free)出现(occurence)与约束出现. 一个变量x在一个公式P中的出现为x在P中作为一个字符出现且这个出现的位置的前一个字符(若存在)不是\forall或\exists. 一个变量x的出现为约束的当且仅当这个x的前面有\forall x(或\exists x(, 且这个左括号对应的右括号在这个x的后面; 不是约束的出现称为自由出现.
注意约束或自由出现是相对出现而言而不是相对变量, 如(\forall x(x=\bar0))\Rightarrow(x=\bar 0)中, x在第5位的出现是约束的, 而在倒数第4位的出现是自由的. 一个公式为闭公式(closed formula)当且仅当所有其中变量的所有出现都是约束的. 下面是一系列重要结论:

引理1.1 若\xi_1,\xi_2\in\bar M满足任意P中出现的x有x^{\xi_1}=x^{\xi_2}, |P|(\xi_1)=|P|(\xi_2).

证明 首先我们归纳证明一个对项的小结论 - 若项t是P的子串, t^{\xi_1}=t^{\xi_2}:
若t=c显然, 若t=x, 由假设x在P中出现, 所以由条件结论成立.
若t=f(t_1,...,t_r), 显然每个t_i都是P的字串, 于是由归纳假设t_i^{\xi_1}=t_i^{\xi_2}, 所以t^{\xi_1}=f(t_1^{\xi_1},...,t_r^{\xi_1})=f(t_1^{\xi_2},...,t_r^{\xi_2})=t^{\xi_2}, 因为函数会将相同的元素映射到相同的元素.
接着归纳证明此引理:
若P=p(t_1,...,t_r), 由上面引理t_i^{\xi_1}=t_i^{\xi_2}, 于是|P|(\xi_1)=|P|(\xi_2).
若P=\neg Q, 由归纳假设|P|(\xi_1)=1-|Q|(\xi_1)=1-|Q|(\xi_2)=|P|(\xi_2). 其他逻辑联词联成的P可以作相似证明.
若P=\forall xQ 若|P|(\xi_1)=0, 这意味着有一个\zeta_1满足\forall y\ne x(y^{\zeta_1}=y^{\xi_1})且|Q|(\zeta_1)=0. 令x^{\zeta_2}=x^{\zeta_1}, y^{\zeta_2}=y^{\xi_2}若y\ne x. 对|Q|(\zeta_1)与|Q|(\zeta_2)应用归纳假设 - 这是合理的, 因为对每一个P中出现的y, 若y\ne x, y^{\zeta_2}=y^{\xi_2}=y^{\xi_1}=y^{\zeta_1}, 若y=x, x^{\zeta_1}是x^{\zeta_2}的直接定义值. 那么|P|(\xi_2)\le |Q|(\zeta_2)=0. 由对称性若|P|(\xi_2)=0可以推出|P|(\xi_1)=0, 即|P|(\xi_1)=|P|(\xi_2).
P=\exists xQ的证明使用相同手法. 当然也可以通过|\exists xQ|(\xi)=1-|\forall x(\neg Q)|(\xi)来论证: 虽然\neg Q联词与量词数量之和与P相等, 但是我们只需要知道对任意满足条件的\zeta_1,\zeta_2, \neg Q(\zeta_1)=\neg Q(\zeta_2); 这点已在归纳第二行论证过了.

引理1.2 若P中x的每个出现都是约束的, 那么对\xi_1,\xi_2\in\bar M满足任意P中出现的y\ne x有y^{\xi_1}=y^{\xi_2}, |P|(\xi_1)=|P|(\xi_2).

证明 还是归纳证明, 原子公式与联词联成的公式是平凡的. 若P=\forall yQ:
首先如果y\ne x, 所有Q中x的出现都是约束的. 若|P|(\xi_1)=0, 这意味着有一个\zeta_1满足\forall z\ne y(z^{\zeta_1}=z^{\xi_1})且|Q|(\zeta_1)=0. 令y^{\zeta_2}=y^{\zeta_1}, z^{\zeta_2}=z^{\xi_2}若z\ne y. 对|Q|(\zeta_1)与|Q|(\zeta_2)应用归纳假设, 那么|P|(\xi_2)\le |Q|(\zeta_2)=0. 由对称性结论成立.
最后如果y=x, 即P=\forall xQ, 若|P|(\xi_1)=0, 有\zeta_1满足任意y\ne x都有y^{\zeta_1}=y^{\xi_1}且|Q|(\zeta_1)=0. 令x^{\zeta_2}=x^{\zeta_1}, y^{\zeta_2}=y^{\xi_2}若y\ne x. 注意到对任意出现在Q中的y, y^{\zeta_2}=y^{\zeta_1}, 由引理1.1可得|Q|(\zeta_2)=|Q|(\zeta_1)=0. 由对称性结论成立.
P=\exists yQ相似地成立.

定理1.3 若P是闭公式, 对任意\xi_1, \xi_2, |P|(\xi_1)=|P|(\xi_2).

证明 由于P的长度有限, P中出现的变量个数有限, 于是我们可以将它们列为\lbrace x_1,...,x_r\rbrace. 现在对n归纳证明: 若x_i^{\xi_1}=x_i^{\xi_2}对任意i\ge n成立, |P|(\xi_1)=|P|(\xi_2).
当n=1时这就是引理1.1. 若已对n=k证明, 当n=k+1时, 对\xi_1, \xi_2, 令x_{k}^{\xi_2'}=x^{\xi_2}, x_j^{\xi_2'}=x_j^{\xi_1}若j\ne k, P中不出现的变量随意赋值, 那么对任意i\ge k都有x_i^{\xi_2'}=x_i^{\xi_2}, 于是由归纳假设|P|(\xi_2')=|P|(\xi_2). 同时由引理1.2|P|(\xi_1)=|P|(\xi_2'), 所以|P|(\xi_1)=|P|(\xi_2). 当n=r+1时即是要证的定理.

下面我们来作一些总结: 首先由定理1.3, 对闭公式而言无需强调它在某个特定\xi下的真值, 于是对闭公式P我们可以简记它的真值的记号为|P|.
其次, 真值不受赋值影响的公式不一定是闭的. 回到(\forall x(x=\bar0))\Rightarrow(x=\bar 0), 由于\Rightarrow前的公式真值永远是0, 整个公式的真值永远是1, 但它不是闭的.
接着, 对语言L中的一个公式集\mathcal E(通常无穷), 我们称L的一个模型(M,\phi)为\mathcal E的一个模型当且仅当对任意P\in \mathcal E与\xi\in\bar M都有|P|_\phi(\xi)=1.
最后是归纳法的可行性. 我们真的能在没有\text {PA}的情况下使用归纳法吗? 十分可惜的是, 归纳法属于元语言的一条"公理", 毕竟诸多使用自然数的场合, 如计数公式的长度, 是在没有\text{PA}的情况下进行的, 而关于这些情况应用的东西纯粹属于符合直觉的论断. 在之后的证明中我们还会在没有集合论的情况下用到集合基数乃至选择公理. 数学并非完全逻辑完全严格的学科, 还请读者做好心理准备.

2 推理(deduction)规则

给定一个公式集\mathcal E与一个公式P, 我们称有限序列(P_1,...,P_{n-1},P_n=P)为一个\mathcal E到P的推理或证明(proof)当且仅当对于序列中任意的P_i:
要么P_i\in\mathcal E;
要么存在j,k<i使得P_k=P_j\Rightarrow P_i(\text{MP});
要么存在j<i使得P_i=\forall x P_j(\text{Gen}).
这个序列中的每个P_i就相当于证明中的一个步骤, 从已知条件\mathcal E出发应用两条符合直觉的推理规则 - \text{MP}与\text{Gen}, 一步步推得想要的结论. \text{MP}, 即拉丁语Modus Ponens, 来源于古希腊形式逻辑中的三段论, 即如果已知A和"A能推出B", 就可知B. \text{Gen}, 来源于Generalization, 即已知A恒真那么自然可以将其推广到对某个变量的一切取值A都是真的. 若存在\mathcal E到P的推理, 我们将其记作\mathcal E\vdash P. 不过为了避免受非必要的苦, 我们先不在没了解恒真式与其他逻辑公理的情况下贸然进行证明. 事实上, 在\mathcal E不包含所有公理的情况下判断某个P能否由\mathcal E推出是一件非常困难的事, 就算对任何\mathcal E的模型(M,\phi)与任意\xi\in\bar M都有|P|_\phi(\xi)=1. (当然在\mathcal E包含所有公理的情况下这是肯定的 - 这正是大名鼎鼎的Gödel完备性定理) 一个备受研究的例子即\mathcal E为直觉主义逻辑的所有公理, 但P是某个Q\vee(\neg Q).

3 恒真式, Gödelian公式集与公理

下面我们考虑如下集合

T_\phi L=\lbrace P:\forall\xi\in\bar M(|P|_\phi(\xi)=1)\rbrace

这个集合的元素被称为\phi-真公式(\phi-true formula), 我们即将会看到, 这种集合与一阶语言的完备性(completeness)有着密不可分的关系. 下面是它自然的性质:
1 T_\phi L是完备(complete)的, 即对任意闭公式P, 要么P\in T_\phi L, 要么\neg P\in T_\phi L. 这是显然的, 因为若P \notin T_ \phi L , |P|_ \phi=0, 于是|\neg P|_ \phi=1-|P|_ \phi=1.

2 T_ \phi L不包含矛盾, 即对任意公式P不可能有P\in T_ \phi L且\neg P\in T_ \phi L. 这依然是十分显然的.
3 T_ \phi L在