【数理逻辑如何入门】：从「离散数学」开始

在《能否通过离散数学学习数理逻辑？》中，我们深入探讨了从离散数学开始入门学习数理逻辑的可能性。不过，大部分人学习离散数学并非是为了学习数理逻辑，因此以学习数理逻辑为目的学习离散数学，其观念、视角、学习方法、内容选取就与一般性的学习有了很大不同，最大的不同是：对每项内容的学习，程度要更深入，而学习的目的则是：从理论、实践两个方面理解掌握做数学证明的方法。贯穿整个学习过程的中心概念有两个：【语言】、【结构】。
今天就来谈谈这个问题。
一、离散数学是一门什么样的学科？
与数学的主流分支不同，离散数学看上去没有一个确定的中心话题，内容很庞杂。我曾做过一个粗略的统计，离散数学的内容涉及大约四十几个大大小小不同的话题，从集合、函数、关系、命题逻辑、谓词逻辑，到算法、计数、数据结构、递归、图论、概率、数论、形式语言与自动机，布尔代数、向量与矩阵，线性规划、抽象代数，编码理论、信息论，博弈论、运筹学、理论计算机科学等，真是那句俗话，XXX是个筐，什么都可以往里装。由于离散数学的内容包括面很广，一本通常意义上的教科书不可能全部涵盖，因此我们看到的教科书基本是上述内容集合的不同子集。
那么到底应当如何定义「离散数学」这门学科呢？如果我们使用集合的语言表达就是：
（1）离散数学 = {x∈数学 | 离散结构(x)}
其中，「离散数学」是「数学」的一个子集，「离散结构」是一个谓词，x代表任意数学对象。
现在来详细考察一下这个「离散数学」的定义式。我们的考察，从为什么会出现这样一个学科开始。首先，和其它数学分支不同，「离散数学」并没有开辟数学的新领域，而是在既有的数学领域划出一个范围，以「离散结构」这个性质为标准，若某个数学对象属于离散结构就划入，然后把划入的数学对象的集合命名为「离散数学」。
那为什么会出现「离散数学」这门学科呢？回答是：
         因为计算机的出现！！！因为计算机只能处理离散对象。
生活中离散对象和连续对象的例子是大米和水，前者是离散的，后者是连续的，因为米粒是可列举的、可数的，英语属于可数名词，中文可以用单位量词「粒」等表示，水是无法列举的、也是不可数的，因而在英语中属于不可数名词，中文则不可直接用单位量词表示。形象地说，计算机可以处理像米粒这样的离散对象而无法直接处理像水这样的连续对象。
例如，我们在计算机屏幕上看到一条光滑的曲线。按照微积分定义，一条光滑曲线在某个区间连续，则一定可以找到区间内任意一点的极限。换句话说，在这个区间内点之间的距离是无穷小，这个区间是由无穷多个点构成的。但是在计算机的屏幕上就不是那么回事了，一条曲线无论多么精细、平滑，一定是由一组固定的、确定的、有限数量的「点」（像素）构成的，否则要是按照极限定义，那条曲线是永远画不出来的。也就是说，如果我们要在计算机上处理、表达连续性数据，必须先要把它「离散化」—— 把无穷数量的无穷小量变成有固定的、可确定的有限数量的数值——把连续变成离散。拿「水」这个例子说，我们需要把「水」这个连续对象变成像「水滴」这样的离散对象。
如果你是个程序员，那我们把上述的思想变成一个编程任务：在一个实数直角坐标系的闭区间[2, 3]上定义一条处处连续的曲线，你的任务是写一段代码，列举该区间内所有点的坐标值，亦即，列举下列集合的所有元素
（2）{ (x, y) ∈ R² | 2 ≤ x ≤ 3 ∧ y ∈ R }
你将如何做呢？当然是先确定一个循环，从实数2.0到实数3.0。然后找到递增的台阶。这时你遇到了麻烦，下一个点是什么？为什么？当你脑子里冒出「下一个」的念头时，你已经输了，因为根据极限定义连续曲线根本就没有「下一个」这个概念，因为我永远可以在你设定的「下一个」之前找到离当前数更近的「下一个」使得你定义的那个「下一个」不再是「下一个」。为什么你会有「下一个」这样的概念，是因为计算机给你「洗脑」了。
你编写这段代码的另一个困难是不知道这个循环什么时候结束，因为在[2,3]区间内，有无穷多个实数，换句话说，你的这个循环体永远不会结束。你的幸运在于你所给定的实数区间是闭区间，如果是开区间，你连从哪里开始到哪里结束都无法确定，理由一样，我永远可以找到一个比你设定的开始的那个实数更靠近2.0、比你设定的结束的那个实数更靠近3.0的实数。这个任务是无法完成的，因为这不是一个「可计算的」任务。问题的根源，就在于「离散」与「连续」的矛盾 — — 你试图用离散的手段解决连续的问题，用有穷的方法解决无穷的问题；其中「无穷」（无穷小量与无穷大的个数）这个概念是阻碍你解决这个问题的「元凶」。
我们知道，历史上许多数学悖论都是因「无穷」这样的概念而引发的，因此，希尔伯特曾试图在自己公理系统中排除「无穷」的概念，而代之以所谓 “finitary”【注1】的概念，亦即用一个有穷输入的概念代替「无穷」这个概念，以便在公理系统中彻底排除悖论的干扰，并将基于这个理念建立的数学公理体系称作 “finitary mathematics”。这是将数学中连续对象离散化的首次理论尝试，也是「离散数学」这个概念产生的最基本动机。
上世纪1930年代，布尔巴基学派将整个数学理论进行了重构和形式化，并试图以「结构」这个概念统一所有的数学分支。自此，「什么是数学」的定义发生了变化，数学的本质就是对「结构」的研究，而「数」与「形」不过是「结构」概念下的两个实例而已。
到了现代由于计算机的出现，「离散」的概念从学术走向现实，从科学走向技术，数学对象的离散化成为刻不容缓的任务。数学家对这一新挑战的回答是：将现有数学对象根据「结构」的概念以「离散结构」为标准一分为二，将具有「离散结构」的对象合称为「离散数学」；将不属于「离散结构」的数学对象离散化，由此而产生了一个新的数学分支—— 计算数学（又称「数值计算方法」）—— 一门专门研究如何将非离散结构的数学对象离散化的学科。
通过上面的讨论，我们就可以大致了解（1）的真正含义：在「结构」这个概念下，我们对所有数学对象进行分类，属于离散结构的数学对象就划为「离散数学」。因此，「离散数学」并不是一个独立的数学分支，而是对数学对象「横切」、提取公因式所得的一个数学对象集合。这些数学对象本来分属于它们各自的数学分支，只是由于都具有「离散结构」这个属性才走到了一起。由此可知，「离散数学」是个开放集，任何具有「离散结构」属性的数学对象都可以归为「离散数学」。
有了上面讨论的铺垫，我们现在心里对「离散数学到底是什么」这个问题应当有了明确的答案—— 研究「离散结构」数学对象的学科。
那到底什么是「结构」？为什么所有数学学科都可以统一在「结构」这个概念下？这就是代数特别是抽象代数要讨论的问题。如果你浏览过一些数学著作、特别是国外出版的数学著作就会发现，许多严肃的作者都会把「代数结构」放在其正文内容的前面，根本原因，是使读者建立「结构」的概念。因为只有理解了「结构」的概念，才能理解所有数学对象的共性。
因此从理论上说，学习离散数学应当从什么是数学结构开始，因为这个概念不仅是统御离散数学而且是理解所有数学内容的总纲。但是要理解什么是数学结构，就要先理解描述数学结构的语言——一阶语言、集合、函数、关系。从数理逻辑的角度看，整个数学是由两个部分组成：数学知识的形式化表示——数学结构，表达数学命题、数学证明的标准语言——一阶语言。而表达数学结构、一阶语言的基本构件就是集合、函数、关系、一阶语言。用这些构件描述「结构」的基本框架是这样的：
① 给出一个数学对象的【集合】，并描述这个【集合】的基本性质；
② 定义在这个集合之上元素之间的【关系】，对这些【关系】的表达既可以使用集合意义上的「有序元组」(ordered tuple) 也可以使用一阶语言的「谓词」(predicate)；
③ 定义在这个集合上的可以施行的【运算】以及参加【运算】的元素个数（又称作「元」：ary），这就是【函数】；
④ 定义陈述这个结构的公理、定义、定理的【语言】，这就是【一阶语言】。
因此我们从「离散数学」入门数理逻辑的中心概念就是：【结构】、【语言】，而学习的最基础内容是【一阶语言】、【集合】、【关系】、【函数】。
数学的标准语言是一阶语言，而一阶语言本身，也可以当做具有离散结构的数学对象，这就是我们在任何一本离散数学教科书中看到的「命题逻辑」和「谓词逻辑」的真实面貌。换句话说，离散数学中的逻辑，不是研究推理论证，而是这个逻辑形式化后（弗雷格、罗素）的数学形式。这样的逻辑，我们关注的不是什么「思维能力的提高」，而是作为一种离散的数学结构、它与其它具有离散结构的数学对象的异同，我们都可以用代数结构的概念对这种数学对象进行研究。作为初学者，我们所学到的，不是什么推理论证，而是逻辑式的代数属性、性质和特征。因此，我们获得的知识，是纯形式化的知识，没有语义、只有句法、只有代数。学到这样的逻辑当然不完整，充其量就是和我们在中学所学的关于自然数、整数和有理数运算规律基本相同的另一种代数，只不过运算对象不再是数而是命题真值而已。
离散数学的内容，大致可以分为三类：语言类、理论类、实例类。集合、函数、关系、一阶语言属于语言类，因为这些内容相当数学元语言的基本构件——它们提供了描述数学对象的基本词汇和语法。群环域相当于理论归纳，我们通过这部分内容认识、熟悉、掌握关于「结构」——「数学结构」——「代数结构」的概念。由此理解为什么所有的数学对象，自己已知的、未知的，都可以用「结构」的概念归纳，形式化。在这个过程中，所有数学对象都可以用集合、函数、关系、一阶语言这四个工具在「结构」的概念下得到统一，所有的数学对象、数学分支都不过是「结构」的概念下的具体实例。因此离散数学教科书中的其它内容，都是在讲「离散结构」这个概念下各种数学对象的实例，对这部分你完全有取舍的自由，可根据你的需要进行选择。把上面这些归纳一下，离散数学的主要内容包括：
* 语言类：一阶语言、集合、关系、函数
* 理论类：代数结构，群、环、域，同构、同态
* 实例类：剩余的其它内容
不过，对「语言类」和「理论类」的学习绝不是一次性的，而是要经过多次的反复，因为这些内容贯穿于所有数学对象，不管你今后是学习分析、代数、还是几何拓扑、其它应用数学，你都要经历对集合、关系、函数、一阶语言和代数结构的反复学习，因此不要指望一次学习就掌握了这些内容的所有。如果我们把对这些内容的每一次学习看做「趟」(phase)的话，离散数学阶段是第一趟 (first phase)，那么今后在学习其它数学内容的时就会经历第二趟、第三趟...，而每一趟的学习绝不是对前一趟的简单重复，而是逐渐扩大范围。
例如离散数学阶段的集合，基本上是最简单最直观的有限、可数集合，而在学习分析时就会遇到不可数集合、无穷集合；这就会产生一系列问题，而这些问题在有限可数的情况下根本不可能遇到。正是这些内容大大扩充了集合论的内容；
一阶语言也如此：虽然它可以解决大部分数学公理系统的表示问题，但是如果所研究对象本身也是形式系统，比如用一阶语言去研究一阶语言本身，或者比一阶语言更强大的形式系统，那么就要扩充语言的表达能力，这时就要用到比一阶语言表达力更强的语言，例如内涵逻辑等。或者，需要用不同的表达式系统，例如组合子逻辑、lambda演算等。
关系概念则是理论计算机科学与关系型数据库的基础内容，在这里关系的概念进一步扩大，成为一门独立的学科——关系代数。
而函数的概念，则是数学分析中最重要的数学对象，特别是在泛函分析中。
总之，作为语言类的集合、关系、函数、一阶语言这四个主题在数学其它分支都有相应的扩展，所以对这些概念的每一趟学习都是在前趟学习的基础上进一步的深化。不过记住这一点很重要：将集合、关系、函数、一阶语言和代数结构当作描述其它数学对象的工具与将它们本身当作研究对象是完全不同的两回事，前者是数理逻辑，后者是其它数学分支。
二、如何从离散数学入门数理逻辑？
从离散数学开始入门数理逻辑，学习的的重点就是本文一开始提到的：一个中心，两个重点。
（3）一个中心：学习如何规范化地做数学证明，在这个过程中培养提高自己的逻辑思维能力；
（4）两个重点：
      i. 语言：一阶语言、集合、函数、关系，这是描述所有数学对象的语言，是数学的「元语言」
     ii. 结构：代数结构——数学结构——结构；群、环、域和同构、同态。
关于「结构」概念的讨论，可参考本栏目的下列笔记：
数理逻辑的三个核心概念
数理逻辑的三个核心概念：结构——算术结构（1）
数理逻辑的三个核心概念：结构——算术结构（2）
数理逻辑的三个核心概念：结构——自然语言结构
数理逻辑的三个核心概念：结构——代数结构
在此基础上，熟悉和理解教科书中所列举的其它数学结构的实例。
在上面列举的学习重点中，语言的学习主要就是集合语言（包括集合、关系、函数）、一阶语言（命题逻辑、谓词逻辑）的学习，这个学习过程当然包括了理解定义、做习题等内容，但更重要的是运用——通过学习数学证明进一步理解一阶语言在数学中的作用，使自己成为这种语言的熟练使用者。
从数理逻辑的角度，数理逻辑的本质就是从理论的高度研究证明，它的句法、语义、演算规则。而在离散数学的阶段，主要是在初步掌握了一阶语言后大量的实践。
学会做证明题的一大标志是，可以自如地将证明题分别用自然语言（中英语）和一阶语言写出，并可以自如地在二者之间相互翻译。只有当你充分理解、完全掌握、自如运用一阶语言写出数学证明，你才真正达到了数学的成熟。
「证明」、「语言」、「结构」是学习离散数学的中心内容。
明确了学习的大方向，现在谈谈学习方法。不过我这里所说的学习方法并不是常规意义上的如何学习，而是一个原则，那就是：你的学习需要两种指南：
第一种指南：用非「元语言」式的语言告诉你，你现在学的到底是什么东西。意思是，不是用数学的语言解释你所要学的数学对象是什么。假定你现在要学的是线性代数，那么什么是线性代数？这个解释不应当只是告诉你线性代数就是解线性方程组的学科、是研究线性转换的学科、是研究向量空间的学科，而是从更高的认知维度、套用一个现在流行术语就是「降维」解释这个数学对象是什么。只有通过这样的指南，你才能获得你所要学习内容的真正理解。因为只有在这个维度理解了学习对象，你才能知道所学内容对你认识这个世界有什么帮助。这种理解是哲学式的、认知式的理解。真正好的指南，是让我对这个世界、而不仅仅是对数学知识有更深刻的认识和理解，尤其是学习数学，更应当如此。
第二种指南我称作工作手册（workbook）或技术手册——我们的大多数教科书都属于这个类型——提供技术细节的讲解以及相应的练习，学习者通过这样的指南获得实际技能的掌握和理解，认识新的技术领域。
不过在现实中，很难找到第一种那样的指南，尤其是中文资源。这就需要读者去在各种著作中主动发现，或者在阅读中自己感悟——要在阅读中多思考，从过去自己的经验、从自己知道的别人的经验中思考。这种思考，不应当仅仅是本学科的，应当是跨学科的，要善于从别的不相关的学科知识、生活经验感悟目前学习对象的真实「认知」意义。当学完一个学习对象要问自己的就是，通过对这部分知识的学习，我对这个「世界」的哪个部分又有了新的了解，而不应当仅仅是我学会了矩阵运算，我弄懂了哥德尔定理。在「豆瓣」本人的阅读书单上，列举了一些类似第一指南的英语书籍，也是我近年来关注数学著作的主要基准。
在前面的笔记我曾经说过，数理逻辑实际上是数学哲学的形式化表达——用一阶语言的符号表达数学对数学自身的理解。有人说，数学就是一种工具，用来解决现实世界的其它问题。其实，用数学解决问题包括了两个方面：将问题从自然语言描述翻译成数学语言，这个过程我们称之「建模」，利用数学提供的工具、方法解决问题——这个过程我们称之「算法」。
而数理逻辑是用来解决数学自身的问题，描述数学问题的语言是一阶语言，为此建立的模型是【代数结构】，解决问题的框架与方法则是相应的形式系统。而离散数学则向我们提供了解决离散结构数学问题的工具和方法。我们学习离散数学作为数理逻辑的入门，应当要有这样的觉悟，而不仅仅停留在知识表面技术细节的理解和掌握。
那么，具体的学习策略是什么？
应当说，我们现在所处的时代是信息过剩的时代。我们的问题不是无书可选，而是可选的资源太多而无法决定。因此，我们的学习策略就要适应这样的时代。我个人的学习方式是：不再以某单一教科书为单位从头到尾纵向学习，而是以内容、话题为单位横向学习。假定我目前正在学习集合论的某一话题，我就从所有我可以得到的各种资源中学习。例如教科书，注意选取来自多种不同学科的教科书，不同时代的新旧教科书，地域不同的教科书，中外多个老师的视频教程，众多的个人博客、笔记、多个社交媒体等等。在这个过程中，我得到的不是一家之言，而是所有人——古今中外所有我所及之作者的众家之言，每个人可能都说了一部分，但是众家的合集就可以使我得到一个比一家之言更全面的知识和认识，其中我更有可能得到上面所说的第一种指南。
另外需要注意的是，离散数学不是单独的数学分科，而是各个数学学科的合集，我们选择学习材料时，切忌只选择带「离散数学」标题的，只要你理解了离散数学的本质，你就会发现所有的数学教科书中都有可能包含离散数学的内容，例如大部分分析，代数，拓扑的教科书的前面都包含一些集合、函数、关系、一阶语言和代数结构的内容。因此以主题、话题为中心，你就可以打破界限利用更多的资源进行学习。
学习的重点是有两个：理解概念，多做证明。概念的理解，重点应当是上面提到的第一指南意义上的理解，但是如果无法找到这样的指南，自己也无法体悟，那就要作为未解决的问题，在继续进行下一步学习的同时时时关注前一问题的概念性理解。只有在这个层面上理解学习才算真正完成。
三、目标
学到什么程度才算是入门？第一，可以用一阶语言读写定义、定理、证明并可以在自然语言与一阶语言之间互译；第二，对结构的概念、群环域等结构类有深入的理解，熟悉一些典型的离散结构，如、自然数、整数，向量等，对于未知的数学对象能够用结构的观点迅速得到其要旨。
达到这个程度，现在市面上的所有的任何程度的数学教科书、数理逻辑教科书对你来说已不再是「天书」，因为这些书本质上都是用直译成自然语言的一阶语言写成的关于某个数学结构实例的技术手册。
学习数理逻辑的终极目的，是使你成为一个「数学思想者」，数学对你不再是一堆拉丁希腊字母和特殊符号，也不再是一个公式连着另一个公式的推导证明，它是就你的世界观，数学是你表达哲学理念的最恰当方式。
(完)
【注】
“finitary”是希尔伯特公理化理论的专用术语，是指一个运算/操作/函数，其输入值/运算子/参数的数量可以用一个自然数表达。
从构词法上分析，finit- 表示有限，而 -ary，则是像 binary、unary、ternary等，表示谓词/函数所需的「项」、「参数」，数学、计算机的术语是「元」，元组(tuple)的「元」，finitary 直译应当是「有限元」，但是和中文的「有限元分析」相冲突，故索性不译，直接放在这里。-ary 的名词形是 arity.
这种细微而重要的差别，一般词典无法帮到你，你在读中文文献时很难体会得到，或者是译者不具备这样的素养，或者是没有用准确的中文表达出来。本人因才疏学浅亦无法用准确的中文表达finitary的原意，故有此注解。