第三课：离散数学引言

Page 2 — 什么是"离散"数学

• 离散数学（Discrete Mathematics）
• Discrete：separate，discontinuous，分离的、不连续的
• 研究"离散结构"的数学
• 研究分立的对象之间所形成的关系
• 什么是连续？无限可分
• 庄子：一尺之棰，日取其半，万世不竭
• 亚里士多德：物质是连续的，可以无限分割

💡 人话：离散数学研究的是像整数、图论中点和线这种"一个一个分开"的东西，而不是像实数那样"连续不断"的东西。

Page 3 — 世界的本质是离散的？

• 德谟克利特：物质世界的本质是离散的
• 海水表面连续但由一粒粒沙子组成
• 水分割到最后是没法再分的"水粒"→原子（希腊语"不可分割"）
• 数学王国：从自然数到有理数，再到实数

Page 4 — 数学的起源

• 数学源于计数（结绳法的1,2,3...）和测量（长度、面积、体积）
• 毕达哥拉斯：万物皆数，Number Rules the Universe
• 数学脱离观察、直觉和经验，成为纯粹思维的产物

Page 5-7 — 第一次数学危机

• 数有了几何解释（数轴），整数和分数统称有理数
• √2被发现既不是整数也不是分数
• 摧毁了毕达哥拉斯学派的基础
• 学生希帕苏斯因泄密被扔进大海
• 欧多克斯重新定义比例解决（BC370）
• 启示：直觉和经验不一定可靠，推理和证明才是可靠的

💡 人话：古希腊人发现√2没法用分数表示，这颠覆了"万物皆有理数"的信念。这说明数学不能靠"感觉"，要靠严格的证明。

Page 8 — 古文明的际遇

• 古希腊通过演绎推理建立欧几里德《几何原本》和亚里士多德逻辑体系
• 其他古文明（埃及、巴比伦、中国、印度）停留在"算学"阶段

Page 9-10 — 第二次数学危机

• 芝诺四个悖论（~BC450）：
• 反对无限可分：运动不存在、阿基里斯追不上乌龟
• 反对有限可分：飞矢不动、游行队伍
• 危机爆发（18世纪）：微积分的基础——无穷小的问题
• 牛顿和莱布尼兹创立微积分
• 关键问题：无穷小究竟是什么？
• 最终由极限论严格解决

💡 人话：微积分刚发明的时候，"无穷小"这个概念不严格——到底多小算无穷小？后来用极限严格定义才解决。

Page 14-15 — 第三次数学危机

• 罗素悖论：把所有集合分为"以自身为元素的集合"和"不以自身为元素的集合"
• 理发师悖论：理发师给所有不自己刮胡子的人刮胡子——他给自己刮吗？
• 动摇了整个数学的基础
• 解法：罗素类型论、策梅罗公理化集合论

💡 人话：朴素集合论里"所有集合的集合"会自相矛盾，就像"这句话是错的"一样。罗素的类型论和策梅罗的公理化集合论限制了这种"自我指涉"。

Page 15 — 希尔伯特的形式化思想

• 数学建立在公理化集合论和数理逻辑两块基石之上
• 如果能证明形式系统的一致性和完全性，数学基础就牢靠了

Page 16-17 — 哥德尔不完备性定理（1930）

• 希尔伯特（1928）提出四个问题，希望形式化整个数学
• 哥德尔：任何包含自然数定义的形式系统，要么不完备（不能证明所有真理），要么不一致（包含自相矛盾）
• 霍金（2003）：以"哥德尔和物理学的终结"放弃对"万有理论"的追求
• "自我相关"是限制形式系统的幽灵
• 彭罗斯（无限循环）楼梯、《盗梦空间》

💡 人话：哥德尔证明了数学不可能既完备又不矛盾——总有一些真的命题你没法从公理推导出来。这和"这句话是错的"这种自指悖论有关。

Page 18 — 有限与无穷

• 人类能理解的概念和调动的资源都是有限的
• "自我相关"是一种在有限中包含无限的概念（如递归）
• 自省、自指（本文、笔者）、对逻辑的研究、对智能的模拟
• 自我相关是产生思维和智能的重要基础
• 但哥德尔指出自我相关正是限制形式系统的幽灵

Page 19-21 — 数理逻辑

• 逻辑学：探索、阐述和确立有效推理原则的科学（亚里士多德创立）
• 三段论：大前提+小前提→结论
• 凡人皆有一死（Valar Morghulis）
• 苏格拉底是人
• ∴苏格拉底会死
• 莱布尼茨：想创造"通用科学语言"，用计算代替推理（先驱）
• 布尔（1847）：《逻辑的数学分析》，创立布尔代数
• 弗雷格（1884）：引入量词的符号
• 数理逻辑四大分支：
• 公理化集合论（研究无矛盾问题）
• 证明论（研究逻辑结构和证明规律）
• 递归论（研究可计算性，和计算机发展密切相关）
• 模型论（研究形式系统的数学模型）
• 本课程讲的基础部分：命题演算与谓词演算