命题1.8可数个可数集的并集是可数集
证明：设可数个可数集分别为 Ao,A,A,川,其中A ={ao,a!, a2,i)}( i =0,1,2,111).我们 令A =|Jil A ?把A的元素按照如下次序排成阵列
(0.1)
并依据箭头指示的方向顺序对集合
A的元素进行枚举.不难看出该枚举算法可以保证
每个元素在有限步里被枚举到
，由此说明A是可数的? ■
命题1.2.2.实数集R是不可数集.
证明：根据上述分析知，只要证明所有形如(1.2.2)的2#小数的全体是不可数的
#
运用反证法：如果全体形如(1.1.2)的2小数是可数的，则这些数的全体可枚举如下:
0. X00 X01 X02 X03 0. No * Xu X12
| I |
(0.2)
0. X20 X21 X22 X23 I H 0. X30 X31 X32、X33 \\ | \\ III
其中每个Xij是0或1.我们利用枚举(2.3)构造一 2#小数y =0$0丫川匕川满足：y =1如果 人=0; yi =0如果Xii =1,则y不同于(2.3)所枚举出的全体 2#小数中的任意一个,由此产 生矛盾.此矛盾说明全体 2#小数是不能枚举的，因此它们是不可数的，所以R也是不可数
例3-1.证明自然数加法f(x,y)二x y是原始递归函数.
证明：首先我们注意到自然数集上的恒等函数l(x ) = x是原始递归函数，因为 l(x)二 pX .)于是 f
(x,y)二x y 可以通过递归模式 f(x,0) =l(x)， f (x, y 1^S(f (x,y)) 定义.所以f (x,y) =x y是原始递归函
数.■
例3-2.证明自然数乘法g(x, y)二x y是原始递归函数 证明：我们已经证明了 x y是原始递归的，在此基础上
g(x, y^x y可以通过递归模
式 g(x,0) =O(x)， g(x,y ■ 1) = g(x,y) ■ x定义.所以 g(x, y)=x，y 是原始递归函数.■
命题6.1 (可靠性定理).每个L的定理都是L的重言式?
证明：设A 是L的定理，则存在 L的证明，即公式序列 A1,A2^i，An满足：每个Ai 或是L的公理，或是由某两个前面的公式 A j和A k经MP得到?现在我们施归纳于公式序列
A i ,A 2J H，A n的长度n来证明?
奠基步：当n =1时，上述序列中只有一个公式 L3,由例6-2知A - -定是 重言式?
归纳推证步： 假设命题对小于 n的证明序列成立?在证明序列 Ai,A2,|\n中公式
A ，那么A 必为L的公理L1，L2或
A n是A，可分两种情况考虑：
情况1. An是公理，那么由奠基步的证明即得
A是重言式?
情况2. An是由公式A j,Ak (j ::: k ::: n)经MP得到，此时不妨设 Ak为A j > An的形式? 由于Aj和Ak是出现在An之前L的定理，故根据归纳假定知
A j和Ak均为重言式，即对
任意赋值v ,均有v(A j) =T和v(AQ二v(A j :H An)二T .如果v(An)=F，那么根据赋值 的定义就有v(A
j
) =F，此和v(A j) =T矛盾?此矛盾说明对任意的赋值 v必有v(A n) =T，
故An是L的重言式?根据归纳法原理命题得证?
命题6.2.形式系统L是协调的?
证明：如果L不是协调的，则存在 L的公式A 使得|--LA并且卜-LLA ?由可靠性 定理知A和LI
A 都是重言式，即对任意 L的赋值v，v(A )和v(~A )均为T，由此而产 生矛盾? ■
命题6.3. L的扩充L*是协调的充要条件为存在一个合式公式不是 L*的定理?
证明：如果L*协调，则对任意公式 A ，A 和LI A 不能同时为L*的定理，故至少有 一公式不是L*的定理?
反之，假定L*不协调，那么就有公式B使得|—「B并且|--「LB ?由于L*是L的扩 充，那么L的定理也是L*的定理，由例2-2 (b)知L B > (B > A )是L的定理，于是运 用推理规则MP就可得到| —L*A ,其中A为任意公式，这样任意公式 A 都成为了 L*的 定理?换句话说，如果有公式不是 L*的定理，那么L*必是协调的? ■
在我们通过对L的公理集添加公式得到扩充 们提供了一个途径?
L*时，必须保证L*是协调的?下面命题为我
命题6.4.设L*是L的协调扩充，
A 是L的公式并且 A 不是L*的定理?则我们把
UA 加到L的公理中得到L的扩充L是协调的?
证明：设A是L的公式且不是L*的定理.现将［J A力口入L*的公理集得到L*的扩充L**
如果L**不协调，则有某公式B使得|—L**B并且|—L**|_B ，由此可得|—L**A .由于L** 与L*的区别在于L**只比L*多一条公理|_1 A ，所以在L*中，若假设LI A
LA |__L*A
.
则可推出A，即
，运用演绎定理就得到|__L*LA 、A .注意到(LA )A))A 是L的
定理因而也是L*的定理，于是运用 MP可得|—L* A ，这和A 不是L*的定理矛盾.
■A Lt * *
命题6.5.设L是L的协调扩充，则存在 L的协调完备扩充
证明：首先注意到L的全部公式是可数的，因而我们可用某种方法将之排列出来
?
设
A O
,A
1,A 2 ,
是L的全部公式的一个枚举.我们构造L*的扩充序列J°,Ji,|||,Jn,山如下：
首先令Jo = L，构造J1 :如果| —JO A 0，则令J1 = o ；如果没有|一 JOAO，即A 0不 是JO的定理，则
J
把L AO加入JO的公理集得到根据命题6.4知Ji是协调的?
假定已有Jn」且Jnl是协调的，我们构造Jn：如果卜「J n」A n-1，则令Jn二Jn」，如果没 有卜-Jn
丄A n-i，则把L A n-1加入Jn二的公理集得到J. ?同样Jn是协调的?
按照这样的方法依次构造下去， 我们得到了一个扩充序列
J/MJF Jn川，其中
J。=L*而每个Jn (n=0,1,|H)都是协调的.
构造形式系统J，它的公理集是由所有
Jo，Ji，||),Jn，山的公理集的并集组成?我们证明
J是L*的协调完全扩充.
首先J是协调的：如果J不协调，那么有公式A 使得| —J A并且卜-JLA ，即在J 中能证明A和LI A 都是J的定理?但由于证明的序列是有穷的，因而最多只用到
J的有
穷条公理，因此必有某个Jn , Jn的公理包含这些公理， 于是在Jn中就可证明A和LI A 都 是Jn的定理，这和Jn协调矛盾?
其次J是完全的：设A 是任一 L的公式，不妨设A 为Ak ?如果Ak是Jk的定理，那 么Ak也是J的定理；否则L Ak将成为J\的定理，当然也是 j的定理?
命题5在解释|中，赋值v满足公式(Xi )A 的充要条件是在I中至少存在一个与 vi-等 价的赋值v'， v'满足A 。
证明：设v满足(xJA ，则v满足~( — Xi)A ，故v不满足(?Xi)(~A )，于是有一个与v
i -等价的赋值v'不满足~ A ，故此v'满足A 。
反之，若与v i -等价的v满足A ，那么v'不满足~A ，故v不满足(-xJA ，可得..v
江苏科技大学数理逻辑2010试题数理逻辑2011试题
