“离散数学”数学

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

连续以及世界的本质

• 连续，通俗来说就是无限可分
• “一尺之锤，日取其半，万世不竭”
  《庄子*天下篇》
• 物质世界的本质是连续？还是离散？这是个哲学家们争论不休的问题…
• 但在理性王国中，从自然数到有理数，再到实数，涉及到无线的连续已经被创造了

“数”学

• 数学源于人们对于计量的需要：
  • 计数问题：从结绳法的1、2、3…开始
  • 测量问题：长度、面积、体积
  • 出现了整数——最原始的数，源于人们对“相继出现”和“次序”的感知
• 毕达哥拉斯信奉“万物皆数”
  Number Rules the Universe
  数是宇宙的本原，是现实秩序的根据
• 数学脱离观察、直觉和经验，成为纯粹思维的产物——现代科学以致现代文明的起源

三次数学危机

无理数：第一次数学危机

• 数还具有了集合解释——数轴，数和直线上的点一一对应
• 整数：间隔为单位长度的点
• 分数p/q：将单位长度q等分，取p个等分
  
• 计数和测量统一在一起
• 一切都是完美的，以致整数和分数被成为有理数（rational number）
  rational：理性的、合理的
  
• 直到毕达哥拉斯自己痛苦地证明了$\sqrt{2}$2​既不是整数，也不是分数——不是有理数
• 与人的常识矛盾：存在不能用单位长度来测量的线段？
• 摧毁了毕达哥拉斯学派的基础，学派花了很长时间来保密
• 据说，毕达哥拉斯的一个学生西帕苏斯，由于泄露了这个秘密而被扔进了大海。
• 人们不情愿地把这种“不合理性”的数成为无理数（iirational number）

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

• 最后在BC370由欧克多斯通过给比例（即分数）下新定义的方法所解决。
• 和1872年狄德金所给出的无理数的现代解释基本一致
• 第一次数学危机给我们的启示：
  直觉和经验不一定靠得住，推理和证明才是可靠的。

古文明的际遇

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

无穷：第二次数学危机

• 危机的潜伏：芝诺Zeno of Elea四个悖论（~BC450）
• 反对空间时间无限可分的两个悖论：运动不存在和阿基里斯追不上乌龟
  
• 反对空间时间有限可分的两个悖论：飞矢不动和游行队伍。
• 古希腊人已经认识到无穷小和“很小很小”的矛盾。

危机的爆发：微积分的基础（18世纪早期）

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

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

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

无穷级数的求和

• 格兰迪级数（Grandi’s series，1703）
• 1 - 1 + 1 - 1 + 1 - 1 + 1 … =?
  • = 1/2?
  • = 1 ?
  • = 0?

危机的解决：1820s ~ 1870s

• 从波尔查诺Bolzano、阿尔贝Abel、柯西Cauchy、狄里赫利Dirichlet等人对连续的定义和极限论开始。
• 到维尔斯特拉斯、狄德金、康托等人独立地建立了实数理论，在实数理论上建立极限论的基础。

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

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

理发师？第三次数学危机

• 1901年5月，罗素Russell发现的悖论沉重打击了集合论和逻辑基础。
  • … …理发师困境
  • … …说谎的克里特人
• 悖论动摇了整个数学的根本
• 罗素提出类型论，策梅罗Zermelo提出公理化集合论来对朴素集合论进行限制，解决悖论问题。

对形式系统的验证

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

形式化的极限

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

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

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

埃舍尔M.C.Escher的版画

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

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

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

以有限把握无穷

• 人们所能理解的概念和调动的资源是有限的。
• 以少数的规则包含无限多的事实。
• 从有限的推导抓住无限丰富的未知。
• 自我相关，是一种在有限中包含无限的概念，一种以有限体现无限的过程。
• “递归”就是自我相关。
• 人类思维过程和认知概念中包含着大量的自我相关和层次缠绕
  • 自省、自指
  • 对逻辑的研究，对智能的模拟
    （以逻辑研究逻辑，以智能模拟智能）
• 自我相关是产生思维和智能很重要的基础？
  • 但，哥德尔不完全性定理之处自我相关恰恰就是限制形式系统的幽灵
• 人类一思考，上帝就发笑？

《离散数学》

• 人类知识大厦的基础
  • 数理逻辑
  • 集合论
  • 图论
  • 抽象代数
  • 形式语言与自动机