哥德尔定理依赖的逻辑数学背景——读哥德尔后之十一

开读哥德尔原著英译本第二章，恰好碰上广州来势汹汹的疫情。这个该死的新冠病毒，在地球上肆虐快两年了，该消停了吧？可5月的广州，让这个期盼又成幻影。又得一番折腾，才能让我们回复到正常的生活轨道了。本来想到广州“南海神庙”再瞅瞅的愿望，因为这突如其来的疫情，暂时是落空了。

广州疫情的几张图片

从荔湾开始

广州疫情

广州全员检测

广州南海神庙

好像正好是去年4月份的时候，我正在一段一段地品味法国作家加缪的《鼠疫》（见我的新浪博文784-795）。重新翻看《鼠疫》一书，加缪在《鼠疫》结尾中的一段话，大概表明人类在那个时代所面临的困境：

“鼠疫杆菌决不会完全消亡，它们能够在家具或衣物里休眠数十年。它们在浴室，地下室，行李箱，手帕和旧纸张里耐心地潜伏着，等候着冥冥中的指令或人类的不幸，到那时，鼠疫将再次唤醒它的属群，送它们去某座幸福的城市撒播死亡。”

（加缪《鼠疫》中文版最后一页）

而现时代呢，似乎不仅仅是疫情，还有战争，观念冲突，种族隔阂，环境恶化等等。21世纪的人类，俨然面临着远比加缪所描述的时代更多的问题。

不过，还有人类的智慧在，还有在世代的磨难中发展起来的文明与科学在。

而读书，就是在传承这些智慧和文明。有意思的是，这种对于智慧与文明的传承，在哥德尔原著英译本的第二章，我们看到的，几乎就是传承既有智慧的范本。

一、哥德尔的形式系统P，本质上是先前数学家创造的叠加

如同第二章开首所言：

我们现在将着手以上所描述框架更为严格的发展，开首先给出形式系统P的一个精确刻画。对这个形式系统P，我们寻求去证明不可判定命题的存在。这个P本质上是这样获得的，它给PM逻辑叠加上皮亚诺的公理。也就是说，这个PM加上了作为个体的数字，加上了作为基本概念的后继关系。（哥德尔原著英译本第40页）

这个引文告诉我们，哥德尔建构的系统P，主要是两个构件。一个构件是罗素与怀特海在其《数学原理》刻画的PM，熟悉逻辑史的人一般都知道。罗素等的PM，在更早的时候，德国人弗雷格的《概念语言》也有过较完整的描述。另一个构件是意大利人皮亚诺创建的公理化算术。而比皮亚诺更早的德国人戴德金，在其《自然数的意义与本质》的论文中，同样有很精彩的论述。

这两个构件的基本内容，立刻就以基本符号，系统P公理，基本概念的方式在哥德尔随后的文字中展现出来，一种清晰而且概略的描述风格。

二、系统P的四大类基本符号，也是许多数学家积淀下来的。

第一大类：常元符号

共7个常元符号：“～”（并非），“∨”（或者），”"“（对所有而言），”0“（零，空），“f”（后继），“（”（左园括弧），“）”（右园括弧）。

这些常元符号的进一步理解，参阅王宪钧先生的《数理逻辑引论》，也许是快速理解的一个捷径。这本书出版近40年了，北京大学出版社1982年版。重新翻看，依然感觉亲切而耐读。当然对于“0”和“f”的理解，在王本中未提及，需要对皮亚诺算术有所知的读者，同样是1982年出版的罗素《数理哲学导论》一书，值得推荐。

第二大类：各种变元类型符号

1.一级变元（表示个体，换言之，也就是表示包括0的任意自然数）：

“x₁”,”y₁”,”z₁”,......

这个一级变元，表示的是个体。凡以下标为1的小写x，y，z...符号出现的字符，表达的就是自然数个体。例如数字0，1，2等等。

2.二级变元（表示个体的类）：

“x₂”,”y₂”,”z₂”,......

这类符号表示的是类，自然数个体的积聚，或者由某个性质串起来的一堆东西，在自然语言中常常可以用普遍概念来表示这样的类，在自然数中，偶数就构成了一个类，由那些可被2除的数来构成。

哥德尔把他面对的个体，全都归之于自然数。而用自然数个体形成的类，一个数字个体抽象之后的再抽象，并且，这样一种抽象过程可以无穷延续。如此看待个体的这样一种数字本体哲学，让我颇为惊异。上个世纪30年代，计算机科学恐怕还是一无所有，但哥德尔这个诉诸数字的个体依赖，不就在预示着随后出现的数字化时代么？

3.三级到....变元（表示个体类的类）：

“x₃”,”y₃”,”z₃”,......

这个三级变元，还有变元符号之后的省略号，正如上所述，这类符号表示个体类再来构成的类，其后的省略号.....,则意味着哥德尔设想的级别是可以无穷延续的，

延至无穷的类型变元（表示个体类的类的类......）：

对每一作为级别成员的自然数，这个级别层次可以一直延续到无穷类型。

第三大类：组合符号表示

1.关系类符号：

表示二词项和多词项函数（也称关系）的变元作为基本符号是多余的，因为关系可以定义为序偶的类，进一步又可以定义为类的类的序偶。

例如：用（（a），（a,b))表示的序偶a，b，其中的（x，y）意味着这样的一个类，其仅具有成员x和y，并且（x）表示的这个类，其仅有成员是x。

2.后继符号与一级变元符号组合形成的符号：

即：a，fa, ffa, fffa,...等等。

其中，a为0，或者为一级变元。

这就产生数符号概念，

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公理，这些公理借助习惯性的定义省略式：“.”（合取），”→“（蕴涵），”≡“（等价），“$x”（存在），“=”(等号）而形成，有关括号的省略也遵照通常习惯。

第一组.皮亚诺公理，也称PA，取3个

皮亚诺最初为自然数给定九条公理，后缩为5条。哥德尔保留其公理1，3，5，略掉其中的两条，一条是任何数的后继是自然数，另一条是1是自然数。皮亚诺是把1作为自然数起点，不是把0作为自然数起点。

第二组.四个命题逻辑PM公理模式，每一个公式都是从以下模式，通过对于p，q，r的任意公式替换而导出。

1.p∨p→p 重言公理

2.p→p∨q 析取引入公理

3.p∨q→q∨p 析取交换公理

4.(p→q)→(r∨p→r∨q) 这常被称为三段论律或者蕴涵传递律

第三组.量词公理模式，一阶逻辑中的带量词公式，可以说，都是从这两个公理模式中获得。

这个公理中的自由变元v，如果出现在复合公式(b∨a)中，则蕴涵着这样的结论。

这个v是任意变元；b则是这样的公式，即v不作为自由变元在b出现。如此，则原来辖域为b∨a的全称公式，就可以是全称辖域仅在a中的一个全称公式和b的析取。这个公理,应该是一阶逻辑公理系统K6的一个变形。

K6 （所有"x(A→B)）→（A→所有"x(B)）(见汉密尔顿《数理逻辑》修订版）

第四组.集合论公理模式中的子集公理，或称分离公理。

    分别用类型n或者n+1的变元替换v或者u，并且为公式a替换不含有自由变元u的公式。这个公理表达了还原公理（或者称集合论的概括公理）

第五组.从以下类型提升导出的每一个公式，包括公式本身。

1.（∀x₁（(x₂(x₁) ≡ y₂(x₁)) →（x₂ = y₂)

这个公理陈述了：一个类完全由其成员来决定。这就是集合论中的外延公理，一个集合完全由其所包含的成员来决定，而与这些成员的来历，物理意义，它所表示的对象无关。

以上两组符号还不是哥德尔承继的全部基础性数学观念，还有以下的一些有关系统P的语义与语形方面的基本观念。

四、系统P的基本概念，也是传承

1.直接后承immediate consequence

一个公式c称为公式a与b的直接后承，如果a是公式(～(b))v(c)；并且，一个公式c称为公式a的直接后承，如果c是公式"v(a)，其中，v指称任意给定的变元。

2.可证公式provable formulae

可证公式类被定义为最小的公式类，该公式类含有公理并且相关于“直接后承”关系封闭。

3.基本符号与自然数的一一对应

可以用一个表格，先来图示7个基本符号和自然数的对应

有了这个基本对应，进一步的符号规定，

类型n的变元被给定形式为pⁿ的自然数(其中p是大于13的自然数）。因此，

对于每一个基本符号的有限序列（也可以说是每一个公式），都有一个一一对应的，一个自然数的有限序列。这些自然数的有限序列，我们现在把它们映射到（也就是一一对应到）自然数，通过设这些数：2ⁿ¹，3ⁿ²，4ⁿ³，...p_k^nk对应于序列n₁，n₂，...n_k，其中p_k指称数量级中的第k个素数。

一个自然数由此一一对应地指定，不仅是指定给每一个基本符号，而且还指定给这些符号的每一个有限序列。

也就是，用函数或者说关系Φ(a)，指称对应于基本符号或者基本符号a序列的那个数。假定现在给定了一个基本符号或者这种基本符号序列的类（或者关系）R（a₁，a₂，....a_n)。我们给这个序列指派自然数的类或者关系R’(x₁，x₂，....x_n),这个R’(x₁，x₂，....x_n)对于x₁，x₂，....x_n成立，当且仅当存在a₁，a₂，....a_n使得：

公式x_i=Φ(a_i)(i=1,2,...-n)和公式R（a₁，a₂，....a_n)成立。

这里用同样的斜体字语词来表达那些类和自然数关系，这些类和关系已经用这种形式被指派给这些以前就定义过的元数学概念，如“变元”，“公式”，“命题公式”，“公理”，“可证公式”等等。在系统P中存在不可判定问题的那些命题因此将读作如下，例如这样来读：存在命题公式a使得既不是a，也不是a的否定是可证公式。

现在开始引入递归观念了。

4.递归定义recursive

到目前为止，得引进一个插述式的思考了，它和形式系统P没有直接的联系，并且，事先给出以下的定义：

一个数论函数Φ(x₁，x₂...x_n)被数论函数Ψ(x₁，x₂...x_n-1)和μ(x₁，x₂...x_n+1)说成是递归定义的，如果对于所有的x₂，x₃...x_n，k而言，以下公式成立：

Φ(0，x₂，x₃...x_n) = Ψ(x₂，x₃...x_n)

Φ(k+1，x₂，x₃...x_n) = μ(k，Φ（k，x₂，x₃...x_n) （2）

这就是数论函数的递归定义，关于数论还有递归，以及以下有关数论与递归的几个观念，好像还没有觉得有把握的地方可说，好在这学习还得继续，且留待本篇之后的学习笔记再来加深理解吧。

但这个递归定义有个注释应该提及，该注释说，这个数论函数的定义域是非否定的整数，或者这类n元组，而其值域也是非否定的整数。

4.递归函数

一个数论函数Φ称作递归的，如果存在一个有限数论函数序列Φ₁，Φ₂，...Φ_n，该序列在Φ中终结，且有如下性质：

或者是，该序列的每一个函数Φ_k是被在前的数论函数递归定义的；

或者是，通过替换从在前的任意数论函数推导而来的；

最后，或者是，它是一个常元或者是那个后继函数x+1。

5.递归函数的度degree和递归关系

函数Φ_i的最短序列长度，它属于一个递归函数Φ，被起名为是该函数Φ的度degree。

一个在自然数之中的关系R(x₁，x₂...x_n)称作递归的，如果存在一个递归函数Φ(x₁，x₂...x_n)使得对于所有的x₁，x₂...x_n都有：

R(x₁，x₂...x_n)～[Φ(x₁，x₂...x_n)=0]

哥德尔为其定理证明给出基本背景性的数学观念，到此暂告一段落。在此数学背景之下，立马就是若干需要证明其成立的命题1-4。在证明了这个1-4命题之后，哥德尔笔锋一转，给出了1-45个有关函数（或者关系）的定义，一个元数学的可证公式定义则留给了定义46。

哥文读至此，翻庄子《内篇》以调适，《人间世》尾文跃入眼帘：

已乎已乎！临人以德。殆乎殆乎！画地而趋。

迷阳迷阳，无伤吾行。吾行郤曲，无伤吾足。

山木，自寇也；膏火，自煎也。桂可食，故伐之；漆可用，故割之。人皆知有用之用，而莫知无用之用也。（《庄子通释》第63页）

追读哥德尔的这元数学文字，无伤吾行，无伤吾足，人皆知有用之用，哥德尔的东西，大概就是那无用之用的极致吧。

且待读后续篇。

转载本文请联系原作者获取授权，同时请注明本文来自周祯祥科学网博客。

链接地址：https://wap.sciencenet.cn/blog-3478957-1290455.html?mobile=1

收藏

分享