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

一、离散数学DiscreteMathematics

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

1.无理数:第一次数学危机
数还具有了几何解释——数轴,数和直线上的点一一对应
整数:间隔为单位长度的点
分数p/q:将单位长度q等分,取p个等分
一切都是完美的,以至于整数和分数被称为有理数(rational number)
毕达哥拉斯自己痛苦地证明了√2既不是整数,也不是分数——不是有理数

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

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

2.无穷:第二次数学危机
危机的潜伏:芝诺Zeno of Elea四个悖论 (~BC450)
〉 反对空间时间无限可分的两个悖论:运动不存在和阿基里斯追不上乌龟;
〉 反对空间时间有限可分的两个悖论:飞矢不 动和游行队伍。
〉 古希腊人已经认识到无穷小和“很小很小” 的矛盾
http://baike.baidu.com/view/9383.htm

### 危机的爆发:微积分的基础(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

发表评论

电子邮件地址不会被公开。 必填项已用*标注