命题1.8 可数个可数集的并集是可数集.证明：设可数个可数集分别为012,,,A A A , 其中012{,,,}(0,1,2,)i A a a a i ==. 我们令0i i A A ∞==. 把A 的元素按照如下次序排成阵列00010203101112132021222330313233,,,,,,,,,,,,,,,,a a a a a a a a a a a a a a a a (0.1)并依据箭头指示的方向顺序对集合A 的元素进行枚举. 不难看出该枚举算法可以保证A 的每个元素在有限步里被枚举到, 由此说明A 是可数的. ■命题1.2.2. 实数集R 是不可数集.证明: 根据上述分析知, 只要证明所有形如(1.2.2)的#2小数的全体是不可数的.运用反证法: 如果全体形如(1.1.2)的#2小数是可数的, 则这些数的全体可枚举如下： 000102031011121320212223303132330.0.0.0.x x x x x x x x x x x x x x x x (0.2)其中每个ij x 是0或1. 我们利用枚举(2.3)构造一#2小数010.n y y y y =满足: 1i y =如果0ii x =; 0i y =如果1ii x =, 则y 不同于(2.3)所枚举出的全体#2小数中的任意一个, 由此产生矛盾. 此矛盾说明全体#2小数是不能枚举的, 因此它们是不可数的, 所以R 也是不可数的. ■例3-1. 证明自然数加法(,)f x y x y =+是原始递归函数.证明: 首先我们注意到自然数集上的恒等函数I()x x =是原始递归函数，因为11I()P ()x x=. 于是(,)f x y x y =+可以通过递归模式(,0)I()f x x =，(,1)S((,))f x y f x y +=定义. 所以(,)f x y x y =+是原始递归函数. ■例3-2. 证明自然数乘法(,)g x y x y =⋅是原始递归函数.证明: 我们已经证明了x y +是原始递归的，在此基础上(,)g x y x y =⋅可以通过递归模式(,0)O()g x x =，(,1)(,)g x y g x y x +=+定义. 所以(,)g x y x y =⋅是原始递归函数. ■命题6.1（可靠性定理）. 每个L 的定理都是L 的重言式.证明：设A 是L 的定理，则存在L 的证明，即公式序列12,,,n A A A 满足：每个iA或是L 的公理，或是由某两个前面的公式j A 和k A 经MP 得到. 现在我们施归纳于公式序列12,,,n A A A 的长度n 来证明.奠基步：当1=n 时，上述序列中只有一个公式A ，那么A 必为L 的公理L 1，L 2或L 3，由例6-2知A 一定是重言式.归纳推证步：假设命题对小于n 的证明序列成立. 在证明序列12,,,n A A A 中公式n A 是A ，可分两种情况考虑：情况1. n A 是公理，那么由奠基步的证明即得A 是重言式.情况2. n A 是由公式,()j k j k n <<A A 经MP 得到，此时不妨设k A 为n j A A →的形式. 由于j A 和k A 是出现在n A 之前L 的定理，故根据归纳假定知j A 和k A 均为重言式，即对任意赋值v ，均有()j v T =A 和()()k j n v v T =→=A A A . 如果()n v F =A ，那么根据赋值的定义就有()j v F =A ，此和()j v T =A 矛盾. 此矛盾说明对任意的赋值v 必有T v n =)(A ，故n A 是L 的重言式. 根据归纳法原理命题得证.命题6.2. 形式系统L 是协调的.证明：如果L 不是协调的，则存在L 的公式A 使得|L --A 并且|L --A . 由可靠性定理知A 和A 都是重言式，即对任意L 的赋值v ，()v A 和(~)v A 均为T ，由此而产生矛盾. ■命题6.3. L 的扩充*L 是协调的充要条件为存在一个合式公式不是*L 的定理.证明：如果*L 协调，则对任意公式A ，A 和A 不能同时为*L 的定理，故至少有一公式不是*L 的定理. 反之，假定*L 不协调，那么就有公式B 使得*L --|B 并且*|L --B . 由于*L 是L 的扩充，那么L 的定理也是*L 的定理，由例2-2（b ）知()→→B B A 是L 的定理, 于是运用推理规则MP 就可得到*L --|A , 其中A 为任意公式，这样任意公式A 都成为了*L 的定理. 换句话说，如果有公式不是*L 的定理，那么*L 必是协调的. ■在我们通过对L 的公理集添加公式得到扩充*L 时，必须保证*L 是协调的. 下面命题为我们提供了一个途径.命题 6.4. 设*L 是L 的协调扩充，A 是L 的公式并且A 不是*L 的定理. 则我们把A 加到*L 的公理中得到*L 的扩充**L 是协调的.证明：设A 是L 的公式且不是*L 的定理. 现将A 加入*L 的公理集得到*L 的扩充**L .如果**L 不协调，则有某公式B 使得**|L --B 并且**|L --B ，由此可得**|L --A . 由于**L与*L 的区别在于**L 只比*L 多一条公理A ，所以在*L 中，若假设A 则可推出A ，即*|L --A A ，运用演绎定理就得到*|L --→A A . 注意到()→→A A A 是L 的定理因而也是*L 的定理，于是运用MP 可得*|L --A ，这和A 不是*L 的定理矛盾.命题6.5. 设*L 是L 的协调扩充，则存在*L 的协调完备扩充.证明：首先注意到L 的全部公式是可数的，因而我们可用某种方法将之排列出来. 设,,,210A A A是L 的全部公式的一个枚举. 我们构造*L 的扩充序列01,,,,n J J J 如下：首先令*0J L =，构造1J ：如果00|J --A ，则令10J J =；如果没有00|J --A ，即0A 不是0J 的定理，则把0A 加入0J 的公理集得到1J . 根据命题6.4知1J 是协调的.假定已有1n J -且1n J -是协调的，我们构造n J : 如果11|J n n----A ，则令1n n J J -=，如果没有11|J n n----A ，则把1n-A 加入1n J -的公理集得到n J . 同样n J 是协调的.按照这样的方法依次构造下去，我们得到了一个扩充序列01n J J J ⊆⊆⊆⊆，其中*0J L =而每个(0,1,)n J n =都是协调的.构造形式系统J ，它的公理集是由所有01,,,,n J J J 的公理集的并集组成. 我们证明J 是*L 的协调完全扩充. 首先J 是协调的：如果J 不协调，那么有公式A 使得|J --A 并且|J--A ，即在J 中能证明A 和A 都是J 的定理. 但由于证明的序列是有穷的，因而最多只用到J 的有穷条公理，因此必有某个n J ，n J 的公理包含这些公理，于是在n J 中就可证明A 和A 都是n J 的定理，这和n J 协调矛盾.其次J 是完全的：设A 是任一L 的公式，不妨设A 为k A . 如果k A 是k J 的定理，那么k A 也是J 的定理; 否则k A 将成为1k J +的定理，当然也是J 的定理.命题5 在解释I 中，赋值v 满足公式A )(i x ∃的充要条件是在I 中至少存在一个与v -i 等价的赋值'v ，'v 满足A 。

证明：设v 满足A )(i x ∃，则v 满足~A )(i x ∀，故v 不满足))(~(A i x ∀，于是有一个与v -i 等价的赋值'v 不满足A ~，故此'v 满足A 。

反之，若与v -i 等价的v 满足A ，那么'v 不满足A ~，故v 不满足A )(i x ∀，可得..v 满足~A )(i x ∀，即v 满足A )(i x ∃。

命题7 设I 是L 的解释，A 是L 的公式，v 和w 是I 中的赋值，且对A 中的每个自由变元i x 均有)()(i i x w x v =，则v 满足A 当且仅当w 满足A 。

证明：施归纳于A 中联结词的数目奠基步：A 是原子公式，如),,,(21n n i t t t A ，对任意出现在i t 中的自由变元和常元，均有v 和w 的值相同，因而)()(i i t w t v =),2,1(n i =，故v 满足A 的充要条件为w 满足A 。

归纳推导：情形1，A 是B ~；情形2，A 是C B →；这两种情形可以直接证明，只要用到有关的定义以及归纳假定即可，因而留作习题。

情形3 ，A 是B )(i x ∀，假定v 满足A ，设'w 是任意与w -i 等价的赋值，由于i x 在B )(i x ∀中不自由出现，则对A 中出现的任意自由变元y ，)()()('y v y w y w ==。

我们定义'v 如下：)(')('i i x w x v =))(()('i j x v x v j j ≠=则'v 是与v -i 等价的赋值，由v 满足B )(i x ∀知，'v 满足B 知'v 满足B ，注意到对B 中的任意自由变元)(i x y y ≠，均有)(')()('y w y v y v ==，又有)(')('i i x w x v =，根据归纳假定知'w 满足B ，而'w 是任意与w -i 等价的赋值，故有w 满足B )(i x ∀，即w 满足公式A 。

反之，类似可证明若w 满足B )(i x ∀，则v 满足B )(i x ∀。

根据归纳法原理，命题得证。

□命题3.2. L 的任意公式A 都与一个L 的前束范式B 等价.该命题可施归纳于A 的长度来进行证明,证明的思路可归结为求某公式前束范式的一般方法：步骤1. 对给定的公式A ，改变A 中的约束变元，使它们都不同于A 中的自由变元,而且不同的约束变元取不同的名，这样得到1A . 根据变元替换定理知1--↔|A A ； 步骤2. 如果A 是原子公式，那么它已是前束范式;步骤3. （1）如果A 是~C 的情形：设C 的前束范式为1122i i k ik x x x θθθD ，那么A 的前束范式为1122(~)i i k ik x x x θθθD ,其中,.j j j θθθ∃∀⎧⎪=⎨∀∃⎪⎩如果是如果是 （2）如果A 是→C B 的形式：设C 的前束范式为*1122c i c i ck ik x x x θθθC ，B 的前束范式为*1122b i b i bl il x x x θθθB ，则A 的前束范式为1112()()()()()**c i ck ik b j bl jl x x x x θθθθ→C B .（3）如果A 是()→→C B D ，则先求→B D 的前束范式F ，再求→C F 的前束范式.（4）如果A 是()→→C B D ，则先求→C B 的前束范式F ，再求→F D 的前束范式. ■数理逻辑和计算机科学有着十分密切的关系，无论是数字电子计算机雏形的图灵机，还是数字电路的布尔代数，以及作为程序设计工具的语言、程序设计方法学、关系数据库、知识库、编译方法、人工智能等领域均离不开数理逻辑。