江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc

《江苏科技大学 数理逻辑2010试题、数理逻辑2011试题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、命题1.8可数个可数集的并集是可数集.证明：设可数个可数集分别为,其中.我们令.把的元素按照如下次序排成阵列(0.1)并依据箭头指示的方向顺序对集合的元素进行枚举.不难看出该枚举算法可以保证的每个元素在有限步里被枚举到,由此说明是可数的.■命题1.2.2.实数集是不可数集.证明:根据上述分析知,只要证明所有形如(1.2.2)的小数的全体是不可数的.运用反证法:如果全体形如(1.1.2)的小数是可数的,则这些数的全体可枚举如下：(0.2)其中每个是或.我们利用枚举(2.3)构造一小数满足:如果;如果,则不同于(2.3)所枚举出的全体小数中的任

2、意一个,由此产生矛盾.此矛盾说明全体小数是不能枚举的,因此它们是不可数的,所以也是不可数的.■例3-1.证明自然数加法是原始递归函数.证明:首先我们注意到自然数集上的恒等函数是原始递归函数，因为.于是可以通过递归模式，定义.所以是原始递归函数.■例3-2.证明自然数乘法是原始递归函数.证明:我们已经证明了是原始递归的，在此基础上可以通过递归模式，定义.所以是原始递归函数.■命题6.1（可靠性定理）.每个的定理都是的重言式.证明：设是的定理，则存在的证明，即公式序列满足：每个或是的公理，或是由某两个前面的公式和经得到.现在我们施归纳于公式序列

3、的长度来证明.奠基步：当时，上述序列中只有一个公式，那么必为的公理L1，L2或L3，由例6-2知一定是重言式.归纳推证步：假设命题对小于的证明序列成立.在证明序列中公式是，可分两种情况考虑：情况1.是公理，那么由奠基步的证明即得是重言式.情况2.是由公式经得到，此时不妨设为的形式.由于和是出现在之前的定理，故根据归纳假定知和均为重言式，即对任意赋值，均有和.如果，那么根据赋值的定义就有，此和矛盾.此矛盾说明对任意的赋值必有，故是的重言式.根据归纳法原理命题得证.命题6.2.形式系统是协调的.证明：如果不是协调的，则存在的公式使得并且.由可靠

4、性定理知和都是重言式，即对任意的赋值，和均为，由此而产生矛盾.■命题6.3.的扩充是协调的充要条件为存在一个合式公式不是的定理.证明：如果协调，则对任意公式，和不能同时为的定理，故至少有一公式不是的定理.反之，假定不协调，那么就有公式使得并且.由于是的扩充，那么的定理也是的定理，由例2-2（b）知是的定理,于是运用推理规则就可得到,其中为任意公式，这样任意公式都成为了的定理.换句话说，如果有公式不是的定理，那么必是协调的.■在我们通过对的公理集添加公式得到扩充时，必须保证是协调的.下面命题为我们提供了一个途径.命题6.4.设是的协调扩充，是

5、的公式并且不是的定理.则我们把加到的公理中得到的扩充是协调的.证明：设是的公式且不是的定理.现将加入的公理集得到的扩充.如果不协调，则有某公式使得并且，由此可得.由于与的区别在于只比多一条公理，所以在中，若假设则可推出，即，运用演绎定理就得到.注意到是的定理因而也是的定理，于是运用可得，这和不是的定理矛盾.命题6.5.设是的协调扩充，则存在的协调完备扩充.证明：首先注意到的全部公式是可数的，因而我们可用某种方法将之排列出来.设是的全部公式的一个枚举.我们构造的扩充序列如下：首先令，构造：如果，则令；如果没有，即不是的定理，则把加入的公理集得

6、到.根据命题6.4知是协调的.假定已有且是协调的，我们构造:如果，则令，如果没有，则把加入的公理集得到.同样是协调的.按照这样的方法依次构造下去，我们得到了一个扩充序列，其中而每个都是协调的.构造形式系统，它的公理集是由所有的公理集的并集组成.我们证明是的协调完全扩充.首先是协调的：如果不协调，那么有公式使得并且，即在中能证明和都是的定理.但由于证明的序列是有穷的，因而最多只用到的有穷条公理，因此必有某个，的公理包含这些公理，于是在中就可证明和都是的定理，这和协调矛盾.其次是完全的：设是任一的公式，不妨设为.如果是的定理，那么也是的定理;否

7、则将成为的定理，当然也是的定理.命题5在解释中，赋值满足公式的充要条件是在中至少存在一个与等价的赋值，满足。证明：设满足，则满足~，故不满足，于是有一个与等价的赋值不满足，故此满足。反之，若与等价的满足，那么不满足，故不满足，可得..满足~，即满足。命题7设是的解释，是的公式，和是中的赋值，且对中的每个自由变元均有，则满足当且仅当满足。证明：施归纳于中联结词的数目奠基步：是原子公式，如，对任意出现在中的自由变元和常元，均有和的值相同，因而，故满足的充要条件为满足。归纳推导：情形1，是；情形2，是；这两种情形可以直接证明，只要用到有关的定义以

8、及归纳假定即可，因而留作习题。情形3，是，假定满足，设是任意与等价的赋值，由于在中不自由出现，则对中出现的任意自由变元，。。我们定义如下：则是与等价的赋值，由满足知，满足知满足，