简明数理逻辑

丛书序 前言 章绪论1 1.1数理逻辑发展简介1 1.2数学定义、证明与定理5 1.3证明方法7 第2章集合论10 2.1集合10 2.1.1对象及其名称10 2.1.2集合的定义11 2.1.3集合的表示11 2.1.4罗素悖论12 2.1.5公理化方法13 2.1.6外延公理和空集公理13 2.1.7子集14 2.1.8分离公理14 2.1.9无序对和单点集15 2.1.10交集16 2.1.11并集16 2.1.12集合的差18 2.1.13幂集19 2.1.14广义并20 2.1.15广义交20 2.2关系21 2.2.1有序对21 2.2.2笛卡儿积22 2.2.3二元关系23 2.2.4关系的运算24 2.2.5像与原像25 2.2.6等价关系26 2.2.7偏序关系27 2.2.8良序关系29 2.2.9多元关系30 2.3映射31 2.3.1映射的定义31 2.3.2单射、满射和双射34 2.3.3序同态与序同构36 2.3.4集族37 2.3.5广义笛卡儿积37 2.3.6选择公理38 2.3.7多元映射38 2.4归纳证明与归纳定义39 2.4.1自然数的定义39 2.4.2数学归纳法40 2.4.3归纳定义43 2.5有穷集合和无穷集合47 2.5.1等势集合47 2.5.2康托尔-伯恩斯坦定理49 2.5.3有穷集合51 2.5.4可数集合52 2.5.5无穷集合53 2.5.6不可数集合54 2.6序数与基数56 2.6.1序数56 2.6.2超穷归纳法59 2.6.3可数序数61 2.6.4基数62 2.6.5基数算术64 第3章命题演算66 3.1命题演算的形式语言66 3.1.1命题演算的形式符号66 3.1.2形成规则67 3.2命题演算的语义68 3.2.1赋值、真值表、重言式69 3.2.2代入72 3.2.3语义后承73 3.2.4紧致性定理73 3.2.5等价与替换75 3.2.6联结词的个数76 3.3命题演算的公理及推理规则77 3.4形式证明及形式定理78 3.5形式推演78 3.6推演定理82 3.7导出规则及辅助推演规则84 3.8斜式推演85 3.9可靠性定理90 3.10范式与完全性定理91 3.11联结词完全性96 第4章谓词演算97 4.1一阶谓词逻辑的形式语言97 4.1.1符号系统97 4.1.2形成规则98 4.1.3自由变元与约束变元99 4.2谓词演算的语义100 4.2.1一阶语言的结构100 4.2.2指派与项的取值101 4.2.3满足关系103 4.2.4语义后承107 4.3谓词演算的公理系统及推理规则108 4.3.1谓词演算的形式证明109 4.3.2形式推演109 4.4谓词演算的可靠性定理110 4.5推演定理112 4.5.1依赖性与变化性113 4.5.2谓词演算的推演定理115 4.6谓词演算的推演规则118 4.7斜式推演121 4.8具有特殊句法结构的公式123 4.8.1前束范式123 4.8.2公式分层125 4.8.3斯科伦范式126 4.9完全性定理与紧致性定理127 第5章可计算性理论129 5.1部分递归129 5.1.1原始递归函数130 5.1.2部分递归函数132 5.1.3递归函数133 5.1.4递归关系135 5.2图灵可计算函数137 5.2.1单带确定图灵机137 5.2.2多带图灵机141 5.3图灵计算的算术化145 5.3.1图灵机的编码145 5.3.2计算的算术化147 5.4丘奇-图灵论题150 5.5通用图灵机151 5.5.1通用函数152 5.5.2s-m-n定理153 5.5.3通用函数的应用155 5.6不可判定性158 5.7部分可判定性162 5.7.1部分可判定谓词162 5.7.2递归可枚举集166 5.7.3集合间的多一归约169 5.8图灵计算的逻辑刻画172 5.9递归定理175 5.10神谕图灵机181 5.10.1神谕图灵机的配置181 5.10.2神谕图灵机的编码183 5.10.3相对于A的递归集与r.e.集184 5.10.4图灵归约与图灵度185 第6章哥德尔不完全性定理188 6.1皮亚诺算术系统PA188 6.1.1皮亚诺算术系统188 6.1.2PA的语义190 6.2序关系191 6.3可表示性193 6.4哥德尔编码196 6.5元数学的算术化197 6.6哥德尔不完全性定理的证明200 第7章模型论207 7.1结构之间的关系208 7.1.1子结构208 7.1.2初等子结构210 7.1.3同态与同构210 7.1.4嵌入与初等嵌入211 7.1.5初等等价212 7.1.6膨胀与收缩212 7.1.7图像与初等图像213 7.2完全性定理与紧致性定理的详细证明213 7.2.1完全性定理213 7.2.2斯科伦化218 7.2.3紧致性定理220 7.2.4全称型理论的模型论刻画223 7.3完全理论与模型完全理论223 7.4部分同构230 7.4.1部分同构与有穷同构230 7.4.2Fra*ssé定理232 7.5量词消去235 7.6内插定理238 7.6.1命题逻辑的内插定理238 7.6.2谓词逻辑的内插定理238 7.6.3Beth可定义性定理241 7.7Ⅱ2-理论的模型论性质242 7.8型省略定理245 7.8.1相对于结构的型245 7.8.2相对于理论的型248 参考文献250 索引251