离散数学[1]-引子(形式化及其极限)

一、离散数学DiscreteMathematics

〉 关于“离散结构”的数学
〉 离散Discrete含义:分离的，不连续的 seperate, discontinuous
〉 研究分立的对象之间所形成的关系
〉 离散结构源于人们对时间相继性的感知  原子性世界的经验

1.无理数:第一次数学危机

数还具有了几何解释——数轴，数和直线上的点一一对应

整数:间隔为单位长度的点

分数p/q:将单位长度q等分，取p个等分

一切都是完美的，以至于整数和分数被称为有理数(rational number)

毕达哥拉斯自己痛苦地证明了√2既不是整数，也不是分数——不是有理数

第一次数学危机的解决及启示

最后在BC370由欧多克斯通过给比例 (即分数)下新定义的方法所解决。

〉 和1872年狄德金所给出的无理数的 现代解释基本一致
〉 第一次数学危机给我们的启示:
〉 直觉和经验不一定靠得住，推理和证明才是可靠的。

古文明的际遇

• 古希腊人通过演绎推理建立形成了欧 几里得《几何原本》的公理体系与亚 里士多德的逻辑体
• 埃及、巴比伦、中国、印度等古文明 的数学，并没有经历过这样的危机与 革命，所以也就一直停留在计量所需的“算 学”阶段。

2.无穷:第二次数学危机

危机的潜伏:芝诺Zeno of Elea四个悖论 (~BC450)

〉 反对空间时间无限可分的两个悖论:运动不存在和阿基里斯追不上乌龟;
〉 反对空间时间有限可分的两个悖论:飞矢不 动和游行队伍。
〉 古希腊人已经认识到无穷小和“很小很小” 的矛盾

危机的爆发:微积分的基础(18世纪早期)

• 求曲线长度、包围面积、速度、切线、 极大值、极小值采用的“穷竭法”导 致了微积分的创立。
• 牛顿和莱布尼兹被公认为微积分的奠 基者
• 他们把上述各种问题的解法统一成一 种方法，微分法和积分法，并有明确 的计算微分法的步骤，微分法和积分 法互为逆运算

微积分里的“无穷小”是什么?

〉 无穷小量究竟是不是零?两种答案都会导致 矛盾。
〉 牛顿对它曾作过三种不同解释，但始终无法 解决上述矛盾:
1669年说它是一种常量; 1671年又说它是一个趋于零的变量; 1676年又说它是“两个正在消逝的量的最终比” 。
〉 大主教贝克莱讽刺它是“消失了的量的鬼魂

无穷级数的求和

格兰迪级数(Grandi’sseries,1703) 〉 1-1+1-1+1-1+1……=?

〉 =1/2?
〉 =1?
〉 =0?

危机的解决:1820s~1870s

从波尔查诺Bolzano、阿贝尔Abel、 柯西Cauchy、狄里赫利Dirichlet等 人对连续的定义和极限论开始。

到魏尔斯特拉斯、狄德金、康托等人 独立地建立了实数理论，在实数理论 上建立极限论的基础。

第二次数学危机的结果和启示

数学分析建立在实数理论的严格基础之上

〉 导致数理逻辑和集合论的诞生，由此把数学 分析的无矛盾性问题归结为实数论的无矛盾 性问题
〉 整个数学看来都具备了严格的形式化基础
〉 再次提醒人们直觉和经验是不可靠的
〉 无限、无穷都已经超出了人类的经验范围

3.理发师?第三次数学危机

1901年5月，罗素Russell发现的悖论沉重 打击了集合论和逻辑基础。

〉 ......理发师困境
〉 ......说谎的克利特人
〉 悖论动摇了整个数学的根本
〉 罗素提出类型论，策梅罗Zermelo提出公 理化集合论来对朴素集合论进行限制，解决 悖论问题。

对形式系统的验证

第三次数学危机解决以后，整个数学界非常 乐观

〉 希尔伯特Hilbert的形式化思想占统治地位
〉 数学建立在公理化集合论和数理逻辑两块基
石之上
〉 整个数学的基本理论是自然数的算术和实数 理论，它们都已经公理化
〉 如果能够证明这些形式系统的一致性和完全 性，整个数学基础就比较牢靠了

形式化的极限?

• 1928年，希尔伯特提出四个问题，希望能 够把整个数学理论系统形式化，并证明无矛 盾。
• 1930年，哥德尔Godel宣布了不完全性定 理，这是一个具有哲学意义的普适定理。
• 2003年，霍金以“哥德尔和物理学的终结” 的演讲公开放弃对“万有理论”的追求。
• 人们认识到对整个数学形式化的努力是注定 要失败的。
• 无矛盾的系统不完备，完备的系统却是存在自相矛盾的。

4.完美”的数学终结于“自我相关”

〉 “自我相关”的逻辑悖论 下面这句话是错的 上面这句话是对的
〉 哥德尔不完全性定理也运用“自我相关”
〉 证明了一切包含了自然数定义的形式系统，
〉 要么不完备(不能证明所有真理)，要么不 一致(包含自相矛盾)。
〉 “自我相关，层次缠绕”的怪圈无处不在

埃舍尔M. C. Escher的版画

--Drawing Hands
--Print Gallery
--Ascending and Descending
--Waterfall

巴赫J. S. Bach《音乐的奉献Musical Offering》

〉 卡农canon:一种重复演奏同一主题的音乐 形式，通常用不同的音部来重复，每个音部 都比前一个延迟一段时间。
〉 主题中的每个音符都必须巧妙和延迟的音部 中同一主题的其它音符保持和谐。
〉 《音乐的奉献》里运用了一种特殊的卡农技 巧构成自我相关的怪圈，
〉 用不同音部首尾相接的变调使听众有一种不 断增调的感觉。

以有限把握无穷

〉 人所能理解的概念和调动的资源都是有限的
〉 以少数的规则包含无限多的事实
〉 从有限的推导抓住无限丰富的未知
〉 自我相关，是一种在有限中包含无限的概念， 一种以有限体现无限的过程
〉 如果把自我相关称作“递归”，大家就很熟 悉了

〉人类思维过程和认知概念中包含着大量的自 我相关和层次缠绕
〉 自省、自指
〉 对逻辑的研究，对智能的模拟
(以逻辑研究逻辑，以智能模拟智能)
〉 自我相关是产生思维和智能很重要的基础?
〉 但，哥德尔不完全性定理指出自我相关恰恰 就是限制形式系统的幽灵。
〉 人类一思考，上帝就发笑?

二、离散数学包含

• 数理逻辑
• 集合论
• 图论
• 抽象代数
• 形式语言与自动机

参考资料

陈斌 北京大学地球与空间科学学院 gischen@pku.edu.cn

https://www.coursera.org/learn/dmathgen/home/info