《从数学到哲学》读书笔记（二）

摘要：《从数学到哲学》是王浩的代表作，是其正面集中阐释自己哲学思想的作品。循着从柏拉图到哥德尔的“数学-哲学家”传统，王浩在书中首次对实质事实主义一般立场进行了长篇阐发；广泛、深入地讨论了数学哲学的诸议题；探索了心灵与机器、数学与计算机、知识与生活等话题；还重点考察了逻辑和数学领域的一些基本概念。

王浩

二、一般数学概念的刻画

1.自然数

· 计数所用的最后一个序数给出了这个聚合基数。我们可以可以用相同的符号既表示序数，也表示基数。对于自然数，我们就是这么做的。但当我们遇到无穷大的基数和序数时，这种做法就行不通了。因此如果我们把基数看成是由计数得来，序数的概念似乎就更为基本。

· 多于或等于的概念先于基数和序数的概念。要将不同的石堆按数量多少排序，配对就足够了。但为了得到自然数的表征，我们需要“一”和“加一”的概念。似乎可以合理地说，序数和基数都预设了“一个单位”和“增加一个单位”的概念，但它们谁都不比另一个更基本。

· 任意一个集合，只要它包含1并包含它的每个成员的后继，它就包含所有的自然数。如果把所有这类集合的共有部分分离出来，它便恰好包含我们想要的所有自然数而毫无多余之物，因为否则就会有一个比此共有部分更小的集合，它包含1并包含它的每个成员的后继。这立即会把我们引向如下两个问题：刻画“一个任意的自然数集”这个概念；把算术还原为逻辑。

· 布劳威尔站在直觉主义的立场说：通过抛弃康德的空间先天性并更坚决地坚持时间的先天性而得到复活。根据这种新直觉主义，生命时刻分裂成质上不同的部分，仅在保持分离的条件下由时间重新统一，它在抽象掉情感内容后成为数学思维的基本现象，即对纯粹二一性的直觉。此二一性直觉是基本的数学直觉，它创造的不只有1和2，还包括全部有穷序数，因为二一性二元素中的一个可以被看作一个新的二一性，这个过程可以无限重复。

· 格拉斯曼演算系统的疏忽被戴德金纠正，于是我们有了通常所说的皮亚诺公理：(Pl)1是一个数。(P2)任何数的后继是一个数。(P3)不同的数有不同的后继。(P4)1不是任何数的后继。(P5)对于任意的集合K，如果1属于K并且K的任何成员的后继也属于K，那么所有数都属于K。

· 根据戴德金，人们接着会被迫接受如下这些事实。（1）N是一个集合，其元素被称为数。（2）N的元素具有一种特定的顺序，后者由如下事实决定：对于每个确定的数n，都有一个确定的数φ(n),它是n的后继。映射φ把N映射到自身之中，φ（N）是N的一部分。（3）不同的数有不同的后继，即φ是一一映射。（4）并非每个数都是一个后继，即φ（N）是N的一个真部分。1是唯一不在φ（N）中的数。（5）有人可能认为，这些事实已经足以确定N。但它们也适用于每个这样的集合S,它在N的基础上还包含一个由任意一些元素t构成的集合T，人们总是可以扩充一一映射φ，使得φ（T）=T。

· S的一个满足P1到P4的元素n属于序列N，当且仅当，n属于S的每个具有如下性质的子集K：(i)元素1属于K；(ii)映射的像φ(K)是K的一部分。

· 戴德金只是验证了自然数序列可由他的公理完全决定，然后就得出结论，那些公理对于推演定理也是充分的。因为假如某个定理独立于那些公理，那些公理就有两个可能的解释或模型，根据其中一个解释，该定理是真的，根据另一个解释，该定理是假的。但如果那些公理为理论确定了一个唯一的模型，这种情况就不可能出现。因此关于自然数的所有定理必定都是可推演的。这个论证是可信的，但不完全明晰，其中一个原因是解释的概念还不够明确。

· 戴德金的结论经常被这样表述：那些公理是范畴性的，或者它们没有本质上不同的模型。那些公理实际上有一些不同的模型。但是在同构的技术意义上，它们本质上都是一样的。

· N是一个可能的集合，这在直观上似乎是显然的。但哥德尔的不完全性结果表明，没有一个完全形式化的系统能强迫我们拥有一个足够丰富的集合论域，使得所要的集合N必定在其中。

· 在P5中，我们可能恰巧只表达了某些简单的定义性质，使得如此规定的每个K或者是有穷的或者是余有穷的（除了有穷多个数之外，它包含所有的数）。那么不难找到P1到P5的一个模型，它包含某些“外来入侵者”。T={(2b+1)/2}就是一个例子，这里b是任意整数。

· 已知具有范畴性（在同构意义下只有一个模型）和完全性（系统能够决定所有命题的真假）的系统是准形式化的二阶（允许量词作用于集合或函数和自然数）算术系统，它使用了一个非形式的集合概念，如在P5中出现的，而一阶算术（量词仅作用于自然数）系统是不可完全的。

· 纯逻辑（一阶逻辑）是否真的是我们想要的逻辑的全部？仅以没有相应的完备形式系统为理由，不足以让我们拒绝考虑扩充逻辑。通过增加量词“对不可数多的x”得到的扩充，就有完备的形式系统。

· 形式系统有助于系统地研究存在性定理和可计算函数之间的关系。要说明可计算函数和数学中的存在性定理之间的联系，最好的办法是考虑一个如下形式的存在性断言：“对每个自然数m，存在一个自然数n，m和n有R关系。”

· 依赖于所涉及的那个函数，对于每个m，它产生对应的n。如果R是可计算的或可判定的，它就是可计算的。这个函数的确切性质可通过考察一个给定的、导向那个存在性断言的证明而得到确定。一个存在性陈述的意义依赖于它的证明方法。或者一个存在性陈述的意义取决于它所有可能的证明。

· 由于可计算函数只构成任意函数的一个真子类，在一个可计算函数存在和一个任意函数不存在之间缺少一种对称性。这种不对称性可以用来帮助一个外行人理解布劳威尔对排中律的拒斥。

2.连续统

· 有两类不同的问题与连续统（实数集的基数）相关。第一种类型包括芝诺悖论，在很大程度上包括无穷小量的概念。这些问题更关注作为一个一般概念的无穷，即便我们处理的不是连续统而是有理数，它们也会出现。第二类问题，如点集连续性的定义和不可数集的概念，只关心连续统本身。

· 鲍尔查诺认为，两个无穷集之间存在一一对应，并不意味着可以推断说它们成员数量上是相等的。而康托则将两个集合在成员数量上的相等定义为它们的成员之间存在一一对应，所以集合与其真子集可以拥有相同数量的成员。

· 罗素似乎指出，我们知道有一个前提（整体在成员数量上总是多于其部分）足以引发芝诺悖论，如果我们能拒斥此前提，我们就能摆脱悖论。

· 无穷小的线段、面积或体积的形象，在微分和积分中仍有分中仍有启发价值。而且近年来在数理逻辑中还有一个有趣的发现，与非标准模型有关。根据这个发现，可以给出一个融贯的“非标准分析”系统，在这个系统中，无穷小量可以被无歧义地使用。

· √2属于这样一类数，它们对应着可用尺规作图法从单位元构造出来的线段。这些数实际上是代数数亦即整系数方程的实根的特例。e和π不是任何代数方程的根的证明告诉我们，实数域比代数数域还要宽广。

· 魏尔斯特拉斯、戴德金和康托对的理论基本上归结为这样一种观点：每个有界的有理数集都有最小上界，这应该被当作一条公设或公理。因此每个有界的实数集也有最小上界。一个有理数集，如果小于该集合任何元素的有理数都属于它，我们称之为“穷举的”。实数和有理数的穷举有界集之间存在一一对应。

· 如果我们想确保这些有理数的集合存在，就必须使用这样一个集合理论，在其中那些有理数的集合被假定存在。假定这些集合存在和假定它们对应的实数存在一样是一条假设。因此将它们等同并不能使实数的存在更为确定。

· 戴德金认为，一个切割是这样一个划分，它将全部有理数（或实数）分成两个集合A和B，使得A中的每个元素都小于B中的每个元素。被当作连续性的公理或定义的是这个原则：直线上的每个切割决定一个唯一的点。通过把实数与直线上的点相联系，实数上的每个切割决定一个实数。如果剔除切割中的所有无理数，我们就能得到所有有理数切割，每个这样的切割也决定一个唯一的实数（有理数在实数中是稠密的）。形式化中从有理数上的切割开始，其优点是我们可以从有理数及其集合构造实数。

· 实数构成一个连续有序域。由于有序域的公理不成问题，我们只考虑连续性公理，它基本上就是切割原则，但也可以用上界语言来方便地陈述。每个（上方）有界的实数集K（F的一个子集），都有一个最小上界。

· 这是一个二阶系统，因为上述公理不仅谈及实数，还谈及实数的任意集合K。这一特征使该公理系统足够强，以至于是范畴性的。如果我们改用一阶系统，那么所得的初等理论是完全的和可判定的（一个理论T称为可判定的，如果存在一个算法（图灵机），对任意语句φ，能在有限步内判定T⊢φ或T⊢¬φ），但不再是范畴性的。

· 康托的对角线论证证明了，给定实数的任意枚举，我们总能找到一个实数，它在该枚举中不出现。这个证明的更广泛的含义是，没有完全显式的刻画能穷尽所有实数。没有形式系统能包含所有实数。

· 如果我们想从对角线论证中提取更多信息，从而得到一个单一的定理，我们必须使用一个间接的论证和一些非直谓的定义。假设有一个对全体实数的枚举，那么我们可以利用这个总体定义一个实数，它不可能出现在该枚举中。在此论证中，因为我们假定所有实数都在该序列中，我们必须使用一个非直谓的定义来得到一个不在该序列中的实数。对这个实数的定义是非直谓的（包含对其所定义对象从属的一个总体的指称），因为在定义它时我们指称了所有实数，它本身也是其中之一。

· 引入一种新的变元，其取值范围为所有有穷阶的集合和实数。由于每个一般实数集必定具有某个有穷的阶n，其最小上界的阶为n+1，它也是有穷的，因此该最小上界是一个落在一般实数变元取值范围之内的实数。这样我们就可以在不使用非直谓定义的前提下，陈述并证明这个一般定理：每个有界实数集都有一个最小上界。

· 当我们已经定义了一个集合论域，用非直谓定义引入一个新集合，会扰乱原初论域的大小和秩序，而直谓定义则不然。

· 一个自然数集可以包含或不包含1，包含或不包含2，等等，因此必定有2^ℵ0个可能的自然数集，其中包括所有在任意形式集合论中可定义的自然数集。这为连续统提供了一种不可达的模型，但它没有说明该如何显式地规定实数或自然数集。

· 每个直观证明都对应一类证明，或者一类部分解释，我们可以根据直观定理在其中可以被自然地表征的系统的类，来对直观定理进行分类。这一进路可以避免关于哪种观点为是的争论。它还能更充分地揭示普通非形式数学证明的直观内容。

3.机械程序

· 数理逻辑中用一般递归（涵盖所有可计算函数的最广泛的递归定义方式）或图灵可计算性（丘奇-图灵论题说明图灵可计算性等价于一般递归函数）对机械程序的定义十分重要。

· 凭借可计算性的概念，人们第一次成功地给出了一个有趣的认识论概念的绝对定义，即不依赖于所选的形式系统（由一组符号、规则和公理严格定义的逻辑框架）的定义。

· 在每个适当丰富的形式系统中，都存在一些句子，它们和它们的否定都不可证。这个结果澄清了（绝对）可证性的概念，至少在如下意义上：任何给定的形式系统中的可证性都无法完全抓住可证性的直观概念。

· 在通常被指为递归性或图灵可计算性的明晰概念的定义中，人们使用了如下条件：“对每个自然数m，存在一个自然数n，使得某个确定的关系R在m和n之间成立。”这里只要求该条件为真，用来求解与给定之数m相对应的数n的方法是悬而未决的。

（1）哥德尔论机械程序和对概念的感知

· 哥德尔指出，机械程序的精确概念是由产生部分而非一般递归函数的图灵机清晰地展示出来的。我们的直观概念并不要求机械程序总是会终止或成功。一个有时不成功的程序，如果是被明晰地定义的，仍然是一个程序，即一种完全确定的行进方式。用“可由图灵机执行”这个明晰的概念对机械概念的定义，既是正确的，也是唯一的。与“恒有终止的机械程序”这个更复杂的概念不同，现在看得很清楚的、不加限制的机械程序概念，对直觉主义者和古典主义者有着相同的意义。

· 形式系统只不过是产生定理的机械程序。一个形式系统不过是一个多值图灵机，它允许在特定的步骤进行预定范围内的选择。操纵图灵机的人可以根据自己的选择在某些步骤设置控制杆。这正是人们在一个形式系统中证明定理时所做的。

· 在感官知觉和对概念的感知之间，相似性多于差异性。对不同但逻辑上等价的概念的感知，可类比于从不同的角度感知感官对象。如果一开始就没有明晰的东西，那么就很难理解，何以在许多情况下一个模糊的概念能唯一地决定一个明晰的概念，而不容许最微小的选择自由。

· 有些情况下，我们把两个或更多个精确概念杂糅在一个直观概念中，并因此得出了似乎矛盾的结果。当我们认识到，我们的直观概念中杂糅了两个不同的明晰概念，悖论就消失了。

· 当我们使用关于点的集合论概念，并试图将长度赋予线上的任意点集，我们就与直观概念失去了联系。这也解决了这样一个悖论：从集合论的角度讲，人们可以把一个球体分解成有穷多个部分，并把它们重新组装成一个较小的球体。

（2）一般递归函数

· 虽然对机械程序的最令人信服的定义是通过图灵的抽象机器的概念得到的，与之等价的递归函数概念却是在历史上出现得最早的，它差不多可以说是将加法和乘法的简单递归定义推广到极点的产物。

· 不是所有可计算函数都是原始递归的（可通过复合f(0,x,…,y)=g(x,…,y), f(n+1,x,…,y)= h(n,x,…，y,f(n,x,…,y))模式定义的函数，其中g和f是给定的），而且任何比较简单的类很可能都是不充分的，因为有可能借助对角化找到一个新的可计算函数。

· 假设φ指称一个未知函数，ψ1，…，ψk是已知函数，并且假设诸ψ和φ以最一般的方式相互代入后所得的一些表达式的对可以构成等式，那么如果所得的函数等式组对φ有唯一的解，φ就是一个递归函数。这里是在直觉主义的意义上说存在φ的一个解。如果是在经典意义上理解它，那么该定义决定了一个比一般递归函数更广泛的类。

· 导出等式是通过用数字代换函数表达式的变元和函数值得到的，一组等式定义一个一般递归函数，当且仅当对于每组固定的主目值m1,…,mn，存在唯一的数字k，使得以啊φ(m1,…,mn) =k是一个导出等式（从已知条件、定理或方程出发，通过逻辑推理或数学运算得到的等式）。这一要求等价于这个条件：可以如此安排φ的所有可能的参数组(m1,…,mn)，使得对于任意给定的主目组(m1,…,mn)，通过给定的等式对φ的值的计算只需要关于(m1,…,mn)之前的主目组所对应的φ的值的知识，并且无论以何种方式来做这件事，所得到的φ的值是不变的。

· 从经典的观点看，图灵可计算性为机械过程提供了一个准确的分析。但从构造性的观点看，这个概念并不是完全确定的，作为显明构造性方法是什么的一种方式，它是循环的，因为该定义同样涉及一个需用一个函数来解释的存在量词。

（3）图灵机

· 图灵机的定义如下。每台图灵机可以处于一个固定、有穷的状态表中的任何一个状态。它配有一张双向（潜在地）无穷的长纸带。纸带划分为一个个方格，每个方格可记写一个符号，不失一般性，可以规定方格只有空白和有标记（一次性固定下来）两种内容样态。纸带会在图灵机前经过，每个时刻，图灵机只能扫描一个方格，并处于一个给定的状态。每个时刻图灵机所扫描方格的内容（空白或有标记）和机器所处的状态，决定了该图灵机的当前配置。当前配置则决定机器要做出（或执行）什么动作（或原子行为）：改变被扫描方格的内容，或变换被扫描方格为其左侧或右侧的相邻方格（通过移动纸带或机器实现），或转变机器的当前状态为另一状态，或停机。机器从任意初始的状态和被扫描的方格开始；初始的纸带（输入）可以包含任意有标记方格和空白方格的组合，尽管通常我们假定初始纸带只包含有穷多的有标记方格。一旦启动，机器应根据其在每个阶段的当前配置进行动作。如果它一直没有机会做出“停机”的动作，它就得一直运行下去。如果机器停机了，那时纸带的内容一般称为输出。

· 一个算法就是一个有穷的规则集，它精确地告诉我们，对于给定的一类问题，这一刻到下一刻该做什么。给定一个用来求解K类问题的算法和属于K的一个问题，任何人都能够求解这个问题，只要他能执行该算法所要求的操作，准确地遵守那些给定的规则。

· 在执行一个算法时，人类计算者使用一些数据，包括该算法的指令，这些数据部分地储存在他的记忆中，但更多地是写在纸上或印在参考图表上。有（a）某种存储装置来储存初始数据和居间结果。他还要执行（b）某些基本运算。他（c）通过查阅指令来决定下一步做什么，从而控制步骤序列。

· 在这三个要素中，（b）是最易于机械化的。台式计算器的引入已经将这方面工作的很大一部分交给了机器。自动（排序）计算机所做的是，增加（1）一个存储单元以存储信息，以及（3）一个控制单元以根据作为算法之实现的一个程序来执行指令。台式计算器被（2）一个运算单元取代，它与（1）和（3）集成在一起。起初程序是由外部通过插接板提供的，因此无法指示机器对程序进行修改以增加灵活性。但很快机器就开始拥有“存储式程序”，使得程序成为初始数据的一部分，并且可以巧妙地编写一个程序来指示机器自动完成多个程序的工作。

· 如果我们考虑一个人在一张纸（假设它被划分成一些方格）上做计算，该过程涉及如下几件事：（1）一种存储媒介，即那张纸；（2）一种语言，它具有表示数字和方向的符号，假定它们被写在了那张纸上；（3）被察看区域，即每个时刻被观察的一些方格；（4）“心灵状态”，即那名计算者在每个阶段都记录计算到达的阶段，并决定下一步做什么；（5）进行下一步计算的行为，它可能涉及（a）通过写下或擦除一些符号而进行的符号上的改变，（b）被察看区域的改变，（c）“心灵状态”的改变。

· 要使得该过程是机械的，即能被一台机器执行，或以机械的（非创造性的）方式被一个人执行，其原因可以概括为如下两个原则：A确定性原则；B有穷性原则。

· 根据确定性原则，在决定下一步做什么时，唯一相关的信息是当前在被察看区域观察到的符号和当前的“心灵状态”。我们可以把当前“心灵状态”设想为一种严格的、有条件的态度，即准备好做出某些特定的行为，这些行为完全取决于当前在纸上所观察到的符号。

· 根据有穷性原则，心灵在每个时刻只能储存和感知有穷多不同的项，这些项的数量有固定的有穷上界。每个时刻可感知项数的上界非常小，而可存储项数的上界则十分大，但相信存在这种上界仍然是合理的。由这一原则立即可得，计算者在每个时刻只能察看有穷多的方格。需要考虑的心灵状态的数量也是有穷的。可打印符号的数目也是有穷的。

· 计算在每一步所执行的操作涉及三类变化：心灵状态，写在计算表上的符号，以及观察区域。我们暂时假定，每次操作只进行这三种改变中的一种。

· 我们可以绘制在一个给定的算法下的计算的一个机械模型。每个心灵状态对应着机器的一种“配置”或状态。机器在每个时刻扫描B个方格。在每次操作中，机器可以改变其配置，或在另一个方格里改变符号，或改变所扫描区域到L个方格以内的另一个区域。把B和L限制为1并让机器在一条线状纸带上工作，无损于一般性。因此仅有的可变要素是可用符号数（字母表的大小）和状态数。我们可以通过扩充字母表来减少状态数，通过增加状态数来缩小字母表。

（4）构造性和实际可行性

· 自然数上的一个函数φ是图灵可计算的，当且仅当它可由一台图灵机计算。而函数φ可由一台图灵机计算，当且仅当从任何给定的主目值(m1,…,mn)在初始纸带上的表征出发，这台机器最终会停止运行并输出对数字k的表征，其中k是φ(m1,…,mn)的值。

· 在此定义中，有两个存在性断言：存在一台图灵机（或一组等式）；对于每组给定的主目值，存在纸带的一个最终状态（或一个导出等式），它表征一个数字（输出）。简便起见，我们可以只考虑这两个概念中的一个。

· 我们考虑给定等式E，对于任何主目值(m1,…,mn),存在E的一个（唯一的）导出等式，它形如φ(m1,…,mn)=k。写成算术形式，我们可以将该条件简要概括为∀m∃n(gE(m,n)=0),其中n是从E到一个主目值为m且具有所要求的形式的等式的最短推导（的哥德尔数），gE是一个合适的原始递归函数。

· ∀m∃n(gE(m,n)=0)是真的，当且仅当对每个数字m，存在一个数字m使得融gE(m,n)=0是可验证的（仅用数值计算即可证明）。但如果我们接受一种构造主义的立场，如果一般递归性被视为对构造性的分析，我们就陷入一种循环，因为该条件的意义要求存在一个构造性的函数f使得对所有的m都有gE(m,f(m))=0。

· 丘奇论题的官方表述提议将一般递归函数等同于能行可计算函数（存在明确的、机械的步骤（算法）能在有限步内计算出函数值的函数）。

· 我们面临着两个彼此不相排斥的选项：（a）忽视能行程序（或能行可计算函数）和机械程序（或算法）之间的表面的语义差别；（b）主张丘奇所关心的是分析一个与机械程序概念根本有别的直观概念。

· 并非所有一般递归定义的存在性条件∀x∃y(gE(x,y)=0)都可以在一个单一的形式系统中得到证明。在任意给定的形式系统中可证明为一般递归的函数可以以一种一般递归的方式被枚举，然后应用对角线论证就可以得到一个新的一般递归函数。对于每个形式系统S，算术命题Con(S)等价于某个一般递归函数的存在条件。根据哥德尔定理，该存在条件在S中是不可证的。

· 我们可以重新安排自然数的顺序，并考虑那些遵循向较小的（在新的顺序中）参数值还原这一原则的定义。我们现在可以得到自然数的、序型不同的（对应于康托第二数类中的不同序数）良序，以及对应相同序数但又十分不同的良序。对于每个良序<，我们都可以引入序数递归的模式足限制条件f(m,n)=g(m,f(h(m),n),n)，这里g和h是给定的函数，且h(m)<m。

· 通过对良序进行分类，我们或许能得到全体一般递归函数的一个有序结构。如果<是一般递归的，则如此定义的所有函数也都是一般递归的。如果我们从一个给定的序数出发，向着越来越小的序数前进，我们必定会在有穷步内停止。任何一般递归函数都可以这样来定义，即使我们将<限制为原始递归的或具有序型ω。现在的问题是，如何按适当的标准对良序进行分类。

· 从数学上讲，将机械程序等同于图灵可计算性或一般递归性的经典论题是卓有成效的，因为它使一系列不同的机械不可解性结果得以可能。但是在带来重要的数学结果这方面，为能行程序寻找一种有序结构的努力，其回报远没有这么丰厚。

参考文献

王浩，《从数学到哲学》