《数理逻辑》章节试读

《逻辑与形而上学教科书系列》的笔记-笔记 - 笔记

**预备知识**
1.外延原理：两个集合相等当且仅当它们的元素相同。
2.幂集：A的所有子集组成的集合是A的幂集。
3.空集是任何集合的子集：运用反证法——找不到一个属于空集但不属于其他集合的元素。
4.关系：有序对的集合
5.函数：一类特殊的关系，对应的结果要唯一。n元函数是n+1元关系。
6.单射：对所有定义域中的元素，若x≠y，则f(x)≠f(y)
7.满射：对一个对应到Y上的函数f有ran(f)＝Y
8.双射：既单射又满射
9.等价关系：R是等价关系当且仅当R是自反的，对称的，传递的。
10.等价类：对属于集合X的某个元素x和某个等价关系，集合X中和元素x有该等价关系的元素组成的集合称为x关于该等价关系的等价类。
**
命题逻辑**
语法部分
1.规定符号：把符号看作是无意义的
2.定义合式公式：自上而下与自下而上两种定义都运用到归纳原理（归纳原理本身合理性需要证明）
3.证明唯一可读性：论证公式没有歧义
4.证明被选取联词的功能完全性：论证可以找到仅涉及被选取联词的合式公式来表达任意的多元布尔函数（从多个命题符号的真假值映射得到的某一真假值)
5.引进推演系统：推演系统由公理和规则组成。最常见的推演系统有"希尔伯特式"系统(三条公理和分离规则)，"甘岑式"系统(一条公理和很多规则)。
6.定义“证明”或“推演”：给定一个推演系统，由该系统的公理集和假设的公式集出发，通过该系统的推理规则得到一个有穷的公式序列，这个过程被称为从假设的公式集到得到的有穷公式序列中最后一个公式的一个推演
语义部分
1.定义真值指派：包括定义原子命题的真值指派和制定与日常推理相符合的复合命题的真值指派的扩张，对真值指派的扩张的规定用到了递归定义（递归定义本身合理性需要证明）。
2.定义满足和重言蕴涵：重言蕴涵规定了一个公式或一个公式集与某一公式的真值之间的关系。
语法与语义的统一
1.证明可靠性定理：在给定的推演系统内，如果从一个公式集推演出某一个公式，则每一个满足该公式集中所有公式的真值指派都满足被推出的这个公式。
2.证明完全性定理：在给定的真值指派扩张下，如果每一个满足某公式集中所有公式的真值指派都满足某个公式，则存在一个从该公式集到这个公式的推演。
可证的都是真的，真的都是可证的

完全性定理证明步骤
1. 证明：如果∑重言蕴涵r，则∑能推出r
2. 即证：如果∑推不出r，则∑不重言蕴涵r（逆否）
3. 因为：如果∑推不出r，则∑与{¬r}一致（此引理需要证明）
4. 因为：如果∑与{¬r}一致，则∑与{¬r}可满足（此定理需要证明）
5. 因为：如果∑与{¬r}可满足，则∑不重言蕴涵r（由定义可得，不需证明）
6. 完成：由第3条第4条第5条可知第2条成立

完全性定理与其等价命题
如果 ∑重言蕴涵r：对任意真值指派，如果它满足∑中所有公式，那么它满足公式r
则 ∑能推出r：存在一个通过∑中公式和系统公理和分离规则得到r的推演
如果 ∑一致：不存在一个公式其本身和其否定能一起被∑推出；∑不能推出一切公式
则 ∑可满足：存在一个真值指派满足∑中所有公式
注意
（1）可满足与重言蕴涵之间没有固定联系：
1.一公式集重言蕴涵一公式不代表该公式集与该公式组成的集合可满足
原因：如果该公式集本身是不可满足的（没有任何一个真值指派满足它），它也可以重言蕴涵该公式（假前提推任何东西都为真）。
2.一公式集与一公式组成的集合可满足不代表该公式集重言蕴涵该公式
原因：该集合可满足（存在一个真值指派同时满足该公式集与该公式）不代表其他任意满足该公式集的真值指派都能满足该公式。
（2）称一个公式集一致或不一致只是对该公式集某个性质的描述，与一个公式集对公式的推演的可能性没有对错评价上的关系。如：一个一致的公式集和一个不一致的公式集可能可以推出一个相同的公式，但我们不能说一致的公式集的推演才是对的而不一致的公式集的推演是错的。一个公式集到一个公式的推演只有存在与不存在的情况，没有从外部对其进行的对或错的评价。
（3）在"∑与¬ß不一致当且仅当∑能推出ß"这条引理中，无论是作为"∑与¬ß不一致"的前提还是结论，"∑能推出ß"中的∑本身可能一致也可能不一致。
（4）在林登鲍姆引理中，全体公式中可能包含矛盾的公式如：ß和¬ß。因此在把公式加进原有的相容公式集中之前要固定一个全体公式的枚举。因为对某个公式ß来说，可能它之前的公式集既推不出ß也推不出¬ß，所以例如对公式集{r}来说，如果ß出现在¬ß前面则{r,ß}构成新的一致集，如果¬ß出现在ß之前则{r,¬ß}构成新的一致集。
**
模态(命题)逻辑
**

语法部分
1.规定符号：在命题逻辑符号基础上增加新一元联词——模态算子
2.定义合式公式：在命题逻辑公式基础上增加——若ß为公式，则ß的模态式也为公式
3.证明唯一可读性
4.引进推演系统：在命题逻辑"希尔伯特式"系统基础上增加一条K公理和必然化规则
语义部分
1.定义模型M＝(W,R,V): W是一个非空集合，习惯性把W中的元素成为可能世界；R是一个描述W中的元素的二元关系；V是一个从命题符号的集合到 W 的幂集的映射，V也被称为赋值，对每个命题符号A来说，赋值V指派给A的集合V(A)就是那些A在其中成立的可能世界的集合。
2.定义模态公式在模型M中的某个世界w中为真：归纳法
3.定义模态公式在模型M＝(W,R,V)中为真：该公式在模型M的所有世界中都为真
4.定义模态公式具有普遍有效性：该公式在所有模型(的所有世界)中都为真
5.定义模态的重言式
语法与语义的统一
1.证明可靠性定理的弱形式：在给定的K系统内，如果一个模态公式是K系统中的内定理，则该公式是普遍有效的。
2.证明完全性定理的弱形式：如果一个模态公式是普遍有效的，则该公式是K系统中的内定理。

完全性定理弱形式证明步骤
1. 证明：如果r是普遍有效的，则r是K系统中的内定理
2. 即证：如果K系统推不出r，则r不是普遍有效的（逆否）
3. 因为：如果K系统推不出r，则K系统与{¬r}一致
4. 因为：如果K系统与{¬r}一致，则{¬r}在典范模型M中为真（此定理需要证明）
5. 因为：如果{¬r}在典范模型M中为真，则r不是普遍有效的（由定义可得，不需证明）
6. 完成：由第3条第4条第5条可知第2条成立
注意
（1）对必然化规则的理解：在K系统内如果ß成立，则相当于说在K系统的任意模型的任意世界中存在ß。所以对任意模型的任意世界w来说，w的可通达世界都存在ß，因此在w中必然ß成立。又因为w是任意选取的，因此必然ß在K系统内成立。
（2）如果某个世界w不能通达任何一个世界，则根据定义对任意公式ß有必然ß在世界w中为真。
**一阶逻辑**
语法部分
1.规定符号：把符号看作是无意义的
2.定义项：项在公式中扮演名词在句子中扮演的角色
3.定义合式公式：其中由谓词符号和项构成的是原子公式
4.定义变元的自由出现与约束出现，替换规则，可替换规则
5.元定理：演绎定理，逆否命题，反证法，常数概括定理，循环替换引理，约束变元替换定理
6.开公式：含有自由变元的公式，反之为闭公式

注意
（1）如果某一公式如φ（x不在该公式中自由出现）能根据概括定理推出∀xβ，那么能推出公式φ的公式集也可以推出∀xβ，而不用考虑x在该公式集中是否自由出现
（2）可以对原子公式Pxy中的y用x进行替换，替换后变成Pxx，虽然二者形式不同但由于开语句无真假，因此这样的替换并没有语义上的意义。但是这里说的"可以替换"只是对该公式而言，在整个推演过程是否可以对该公式进行替换则是由该公式之前的推导过程来决定的。
（3）概括定理相当于是第四组公理从对单个公式的应用到对一个公式集的应用的扩展。对第四组公理的理解：1.当某变元在某公式中自由出现时该公式作为开语句是没有真假值的，因此对该公式进行概括可能会导新公式产生真假值（如果该新公式还有其他自由变元的话则依然是开语句） 2.当某变元在某公式中没有出现时我们没有用关于该变元的任何假设就证明了该公式，相当于说对任意该变元此公式成立 3.当某变元在某公式中约束出现时对该公式再进行概括相当于对该变元的约束进行重申
（4）内定理是由公理和推演规则推出来的，元定理是关于系统推演过程中步骤之间的规则。
（5）对于公理系统中的公理四：ß蕴含任意xß（x不在ß中自由出现），如果ß本身为假，则不管x是否在ß中自由出现ß蕴涵任意xß都成立。
（6）证明某条公理的独立性（既从其他公理出发推不出这条公理）只需要证明这条公理能推出某个公式而其他公理推不出这个公式。
语义部分
1.定义结构：定义域为语言中的符号的函数（通过挑选结构来解释语法部分中的谓词符号，常数符号，函数符号；并给量词指定论域）。
2.定义赋值：一个赋值s就是一个从V（所有自由变元的集合）到结构A的函数。
3.定义（结构A，赋值s）满足公式ß：用结构A解释ß中的符号，用赋值s解释自由变元，用赋值s的扩张解释项和原子公式，从而把公式ß翻译成元语言中的陈述，通过元语言世界中的知识判断陈述成立。如果所有（结构A，赋值s）都满足公式ß，则称ß为普遍有效的。
4.定义公式集∑语义蕴涵公式ß：每一个满足公式集∑中所有公式的（结构A，赋值s）都满足公式ß。
5.定义闭语句ß在结构A中为真（ß在A中成立，A满足ß，A是ß的一个模型）：在结构A中对所有函数s，都有（结构A，赋值s）满足闭语句ß。
6.定义定义：给定一个语言L和一个结构A，如果某个公式ß中的所有自由变元（假设总共有k个）用A的论域里的k个元素赋值后成立，则称公式ß在结构A中定义了一个k－元关系。
7.结构内的可定义性：如果一个结构中的k个元素存在一个可以被某个公式在该结构内定义的k－元关系，则称这个k－元关系是可定义的。
8.定义初等类和广义初等类：如果在同一个一阶语言中对一个闭语句r有Mod{r}（Mod{r}表示由闭语句r的模型所组成的类），则称Mod{r}为一个EC（初等类）；如果在同一个一阶语言中对一个闭语句集∑有Mod∑（Mod∑表示由闭语句集∑的模型所组成的类），则称Mod∑为一个EC∆（广义初等类）
9.定义同态：在某个固定语言的两个结构论域之间的一种函数关系（不可以一对多，可以多对一，可以未对完值域中所有元素）
10.定义同构：在某个固定语言的两个结构论域之间的一种函数关系（不可以一对多，不可以多对一，不可以未对完值域中所有元素）
11.定义初等等价：固定一个语言L和它的两个结构A和B，L中任何闭语句在A中成立当且仅当在B中成立。
12.定义结构的理论：所有在结构A中成立的闭语句组成的集合为A的理论，记作ThA。
注意
（1）对于一个（结构A，赋值s）来说，（结构A，赋值s）|≠ß当且仅当（结构A，赋值s）|=¬ß；而对一个公式集∑来说，不管Σ|=ß还是Σ|≠ß都和Σ|=¬ß之间无蕴涵关系；不管∑⊢ß还是∑⊢ ß都和∑⊢¬ß之间无蕴涵关系
语法与语义的统一
1.证明可靠性定理：在给定的推演系统和语言内，如果一个公式集∑可以推演出某一个公式ß，则每一个满足公式集∑中所有公式的（结构A，赋值s）都满足公式ß。
2.证明完全性定理：如果每一个满足公式集∑中所有公式的（结构A，赋值s）都满足公式ß，则在给定的推演系统和语言内公式集∑可以推演出公式ß。
可靠性定理证明步骤
1.证明分离规则的保真性
2.证明普遍有效的公式的概括也是普遍有效的
3.证明公理集是普遍有效的
完全性定理证明步骤
1. 证明：如果∑语义蕴涵r，则∑能推出r
2. 即证：如果∑推不出r，则∑不语义蕴涵r
3. 因为：如果∑推不出r，则∑与{¬r}一致
4. 因为：如果∑与{¬r}一致，则∑与{¬r}可满足（完全性定理等价命题）
5. 因为：如果∑与{¬r}可满足，则∑不语义蕴涵r
6. 完成：由第3条第4条第5条可知第2条成立

完全性定理等价命题证明步骤
1. 添加新的常数到原语言中（为添加Henkin公理做准备）
2. 添加一族新的Henkin公理到一个一致集中（用于处理量词）
3. 把这个新的一致集扩充成一个极大一致集∆
4. 通过定义一个特殊的结构A和赋值函数s使其能够满足极大一致集∆（暂时用谓词E替换掉等词）
5. 证明谓词E是论域中的合同关系（即E能够划分出等价类，且等价类中元素对外关系一致）
6. 定义商结构A/E和赋值函数S并证明（A/E，S）能够满足极大一致集∆
注意
（1）可靠性定理中用到的替换引理：如果项t可以在公式ß中替换变元x，则"先把赋值s中对变元x赋的值定为s对项t的扩张再用赋值s对公式ß进行赋值扩张"与"先把公式ß中的变元x替换成项t再用赋值s对新的公式ß进行赋值扩张"的结果是一样的。
（2）蕴涵符号不是一一对应关系，如在Henkin公理中"存在x使得ß(x)成立蕴涵ß(c)成立（c为我们新给出的一个定义其在ß中成立的直接证据）"应被理解为"若存在x使得ß对x成立，则如果把x替换成直接证据c，那么ß对c成立"，而不能理解为"若存在x使得ß对x成立，则一定是把x替换成直接证据c使得ß对c成立"。因此在添加Henkin公理的时候不需要考虑对其前件来说是否存在原语言中的某个元素使得ß对其成立。
（3）对Henkin公理的逆否形式理解时要注意，其形式虽看似为"如果把x替换成常数c后ß成立，则对任意x都有ß成立"，但这里隐含的一个前提是：c是我们在原语言基础上作为直接证据而新添加的一个定义其在¬ß中成立的常数。因此Henkin公理的逆否形式的前件"把x替换成常数c后ß成立"本身是假的，所以Henkin公理的逆否形式本身是成立的。
（4）证明"任何一致的公式集都是可满足的"的思路是根据一致集读出一个结构。为了使每一个一致集都要能读出一个满足它自身的结构，因此在我们构造的结构中符号的定义必须要指涉到这个一致集本身，即和这个一致集建立起某种关系。
（5）解决等词问题的商结构A/E的方法是：把在元语言中不相同而在对象语言结构A中相等（由此产生出矛盾）的元素构成等价类，并把这些等价类作为新结构A/E的论域的元素。
这里展现的一种消除矛盾的思维方式是：我们把"被我们看作相同的（由某些原因造成的，如：Henkin公理造成）但互相之间其实并不同的"一些东西仍然看作相同的，但把这种相同归结于这些东西拥有一种相同的性质，即"被我们看作相同但互相之间其实并不同"这种性质。
（6）我们希望在一阶语言中对不同的结构进行分类（通过有穷句话刻画出不同结构类的性质，我们把一个闭语句或闭语句集的意义看成是它们把那些在其中为真的结构给挑选了出来），而紧致性定理的应用说明了当一个闭语句集（其中可以只有一个闭语句也可以有无穷多个闭语句）能够描述所有有穷模型的时候它同时也能描述一个无穷模型，我们找不到一个能把所有有穷结构从所有结构中挑选出来的一阶逻辑的闭语句集。因此一阶语言无法刻画出"有穷"概念，而无穷结构组成的类虽然可以公理化但不可有穷公理化，即我们也不可以通过有穷句话把"无穷"概念刻画出来。
（7）Peano公理集在二阶语言中才唯一地（指Peano公理集刻画出来的结构是同构的，因此无法通过结构内部的语言把它们分辨开来，实质上是同一的结构）刻画出算术结构（算术结构：直观上一个其论域为自然数集，有加法和乘法两种函数运算，0是第一个元素，其他元素由0通过"加1"运算生成的结构）。结构外部的无法分辨可能在结构内部（实质的，唯一的）的语言上可分辨（如非标准模型在标准模型的基础上往论域里添加的“非自然数”无穷大），但是在外部的结构的理论上不可分辨（如非标准模型和标准模型的初等等价）
（8）证明非标准算术模型B与标准算术模型A不同构：
如果B和A同构，且令h(cB)=m=cA ，则根据Σ知（m,cB）∈＜在结构B中成立。因为B和A同构所以：
（m,cB）∈＜当且仅当（h(m), h(cB)）∈＜
（m-1,cB）∈＜当且仅当（h(m-1),m）∈＜
……
（1,cB）∈＜当且仅当（h(1),m）∈＜
（0,cB）∈＜当且仅当（h(0), m）∈＜
结构A中从h(0)到h(m)共m+1个元素都要满足小于m且结构A中从h(0)到h(m)共m+1个元素要和结构B中从0到m共m+1个元素一一对应.不可能
（9）∑有任意大小的有穷模型：对任意正数i，∑都有有i个元素的模型，既∑的模型的基数必须有|A|=1、|A|=2、|A|=3、|A|=4、……；∑有任意大的有穷模型：对任意自然数n，∑都有比n大的有穷模型，既∑的模型的基数可以没有|A|=1、|A|=2、|A|=3、|A|=4等，但一定要有“……”
（10）若∑有任意大的有穷模型，则∑U{∃2,∃3,∃4……}和∑U{∃3,∃4……}和∑U{∃2,∃4……}的无穷模型都是相同的，既只要∑U{ }的{ }中有“……”，形成的无穷模型都是相同的。
**递归论**
1.原始递归函数、递归函数和部分递归函数的概念是对可计算性（可判定性）的精确定义。即以数学的方式表达我们直观上所理解的"可以计算"。
2.证明了一些和素数相关的函数都是原始递归的，而在后面部分哥德尔将用素数分解定理来编码时将涉及到这些函数。
3.把递归的概念扩大到集合和谓词上。如果一个谓词它的特征函数是原始递归的，那么这个谓词是个原始递归谓词。如果一个集合它的特征函数是递归的，那么这个集合是一个递归集，即可判定集合。
4.如果一个部分函数可以被图灵机计算（即输入x如果f(x)有值则图灵机能算出这个值，如果f(x)在此处无定义，则图灵机就一直算下去不会停），则称这个部分函数是图灵可计算函数。
5.一个函数是图灵可计算的当且仅当它是部分递归的。
**模型论**
1.一个理论是完备的，如果对每一个闭语句sigma，或者sigma或者其否定属于该理论。对完备的理论，其任意模型都初等等价。
2.一个理论可公理化指存在一个可判定的闭语句集使该理论为此闭语句集的语义后承。
3.一个理论可判定指存在一个算法使得对任意闭语句，该算法能算出该闭语句是否属于该理论。任何完备、可公理化的理论都是可判定的。
**可表示性**
粗略地说，研究可表示性即研究怎么样的标准自然数上的关系可以用怎么样的形式语言中的公式表示出来。本节先确定可表示的定义，目标是证明所有递归关系都是在选定的算术系统内可表示的。其中在证明原始递归是可表示时需要用到中国剩余定理来进行编码和解码。最后本节得到：所有的递归函数在Q中都是可表示的。因而所有的递归关系在Q中也都是可表示的。而由可表示的关系的定义可知，所有可表示关系也都是递归关系。
**语法的算术化**
为了在某形式语言中讨论逻辑的语法甚至语义，哥德尔使用了在1930年代时被视为非常神奇的编码技巧，即哥德尔编码（这一技巧可以与许多哲学家区分出人的独特性的符号化能力进行联系，并且不完全性定理之所以能被某些人认为是区分机器和人的一个论据的根本之处无疑就在于此处的编码）。通过用自然数来编码“公式”、“证明”等逻辑语法中的对象，并且使编码后的对象是自然数的递归子集，我们可以在我们的形式语言中研究这些对象的性质。这个过程就是语法的算术化。