哥德尔定理依赖的数学背景——读哥德尔后之十一
好像正好是去年4月份的时候，我正在一段一段地品味法国作家加缪的《鼠疫》（见我的新浪博文784-795）。重新翻看《鼠疫》一书，加缪在《鼠疫》结尾中的一段话，大概表明人类在那个时代所面临的困境：
“鼠疫杆菌决不会完全消亡，它们能够在家具或衣物里休眠数十年。它们在浴室，地下室，行李箱，手帕和旧纸张里耐心地潜伏着，等候着冥冥中的指令或人类的不幸，到那时，鼠疫将再次唤醒它的属群，送它们去某座幸福的城市撒播死亡。”
（加缪《鼠疫》中文版最后一页）
一、哥德尔的形式系统P，本质上是先前数学家创造的叠加
如同第二章开首所言：
*我们现在将着手以上所描述框架更为严格的发展，开首先给出形式系统P的一个精确刻画。对这个形式系统P，我们寻求去证明不可判定命题的存在。这个P本质上是这样获得的，它给PM逻辑叠加上皮亚诺的公理。也就是说，这个PM加上了作为个体的数字，加上了作为基本概念的后继关系。*（哥德尔原著英译本第40页）
二、系统P的四大类基本符号，也是许多数学家积淀下来的。
第一大类：常元符号
第二大类：各种变元类型符号
第三大类：组合符号表示
3.数符号：number-sign
若a为0的情形，称这样一个符号为数符号。
第四大类：P中公式表示
基本公式：elementary formulae
对于n > 1，我们把第n种类型符号和第n种类型变元看作是等同的。形式如a(b)的符号组合，其中b是第n个类型符号，a是第n+1个类型符号，称a(b)这类符号为基本公式。
公式类：class of formulae
公式类被定义为最小的类，这个类含有所有基本公式，并包含以下带有任意a和b的表达式：～（a）， （a）∨（b），x（a）（其中x是任意给定变元）。
这个定义来自卢卡西维兹和塔尔斯基的工作，其中的塔尔斯基，在后面的定理证明中还会提到，两位来自波兰华沙学派的学者，塔尔斯基后去美国。
复合公式：
公式a∨b称a与b的析取disjunction；
～a是a的否定negation；
所有x（a）称作a的普遍化generalzation；
一个没有自由变元的公式称作命题公式propositional formulae（自由变元用通常的方式定义）。
一个带有n个自由个体变元的命题公式（否则就是没有自由变元）我们称之为n元关系符号n-place relation-sign，对于n=1，则称做类符号class-sign。
类型提升：type-lift
一个公式a是有关另一个公式b的一个类型提升，如果a从b导出，当用出现在b中的所有变元类型的同量增加的时候。
以上用粗体字标出的文字，都是按照哥德尔原著版面的标记，下同。
三、系统P的五组公理：总共11个公理，实质上是PM的公理+PA的公理+集论公理
下述五组中的11个公式称作P公理，这些公理借助习惯性的定义省略式：“.”（合取），”→“（蕴涵），”≡“（等价），E“x”（存在），“=”(等号）而形成，有关括号的省略也遵照通常习惯。
皮亚诺最初为自然数给定九条公理，后缩为5条。哥德尔保留其公理1，3，5，略掉其中的两条，一条是任何数的后继是自然数，另一条是1是自然数。皮亚诺是把1作为自然数起点，不是把0作为自然数起点。
分别用类型n或者n+1的变元替换v或者u，并且为公式a替换不含有自由变元u的公式。这个公理表达了还原公理（或者称集合论的概括公理）
四、系统P的基本概念，也是传承
1.直接后承immediate consequence
一个公式c称为公式a与b的直接后承，如果a是公式(～(b))v©；并且，一个公式c称为公式a的直接后承，如果c是公式v(a)，其中，v指称任意给定的变元。
2.可证公式provable formulae
可证公式类被定义为最小的公式类，该公式类含有公理并且相关于“直接后承”关系封闭。
这里用同样的斜体字语词来表达那些类和自然数关系，这些类和关系已经用这种形式被指派给这些以前就定义过的元数学概念，如“变元”，“公式”，“命题公式”，“公理”，“可证公式”等等。在系统P中存在不可判定问题的那些命题因此将读作如下，例如这样来读：存在命题公式a使得既不是a，也不是a的否定是可证公式。
现在开始引入递归观念了。
4.递归定义recursive
到目前为止，得引进一个插述式的思考了，它和形式系统P没有直接的联系，并且，事先给出以下的定义：
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/226377.html原文链接：https://javaforall.net
