C02 一般自然数的刻画

领读人：

时间：2025年2月16日 21:01:35 - 22:44:33

会议链接：https://meeting.tencent.com/crm/KwqZe13nd5  

密码：UD0S

Chap02 一般自然数的刻画

1. 自然数

1.1.1. 全体自然数集合的定义

❌ 自然数是1，2，3，……

什么是 ……

❌ 一个自然数要么是1，要么是另一个自然数的后继

随意添加一个a-2, a-1, a， a+1，a+2.。。也都成为自然数

✔ 任何一个集合，只要它包含1并包含它每个成员后继，它就包含所有自然数

1.1.2. 如何刻画一个任意的自然数集合? 算术如何还原成逻辑?

1.1.3. 刻画集合的方法：

莱布尼茨、二一律、乘法和加法定义的例子，使用归纳法来定义

类似的方法可以得到：

皮亚诺公理：

❓对任意引入的w，怎么把它排除

❌ 反复利用多次2能达到的数才属于一个集合，涉及循环论证

✔ 应用5，因为1不在w的集合中

根据皮亚诺公理我们得到了自然数性质，如何证明它充分地定义了自然数（没有本质不同的模型）？

1a Sa Na 表示其中一个模型中的1、后继函数和集合

1b Sb Nb 表示另一个模型中的，只要他们存在一一映射，就认为是本质相同的。

公理系统转化为形式系统：

形式系统包含的元素：字母表（自然数），项（自然数中的一部分），公式（？），公理（），演绎规则（？）

公理系统： A

一阶谓词(and, or, xor, >, <)：x

A 与 x 的交集 --> B， 可枚举， 范畴性的

B+ (+, *) --> 非范畴的

为什么要形式化系统：

涉及后面递归、图灵机的定义，如果一个式子是可计算的，那他在形式化系统里面就会有相应的公式、定理表述

2. 连续统:

2.1.1. 芝诺悖论：

拒绝集合的每个元素要比另一个多的假设（无穷大于无穷）

2.1.2. 连续统假设

引入无穷小量: 定义导数，点的长度

定义实数领域：

1） 自然的实数vs生造的实数：能直接写出来的是自然的，满足某些定义的是生造的

2） 连续性公理

戴德金的证明：把集合切割等效成直线的切割，每个切割决定一个点；

每个有界的有理数集有最小上界，作为公理如何表述；

2.1.3. 实数不可数

太长不看版： 在各种系统中，我们都可以证明实数的对应物，任何特殊系统都不能准确形式化真正的数学结果；直观上实数是存在的，但是它在不同系统里有不同的定义。

给定任意实数序列，我们都能找到一个实数不在其中，那只要给出一个构造，我定义一个实数，不满足这个构造即可；

这种声明是非直谓的，那再定义一个阶，第N+1阶的实数 不在 第N阶实数的集合中；

然后我们会遇到一个困难，无法指称所有实数。

方案：引入一个新的变元，取值范围是集合+实数

非直谓的困难引发了构造性和直谓 递归分析 f(n+1) = g(n)

3. 机械程序

形式化的价值：帮助证明一些原来只能暗示的东西；历史上很多问题都是在关键概念被形式化后才得到解答。

3.1 哥德尔机械论

如果我们从模糊的直观开始，如何找到明晰的概念忠实对应于它。

哥德尔认为应该引入直观。

精确理论的哲学应该对形而上学做的，就如同牛顿对物理学做的。

概念适用情形下：直观速度观念对应的精确概念ds/dt, 面积对应度量

一个直观可能有多个概念，从而导致矛盾：连续性是连续运动还是平滑??

关于点的直观：点组成线 只在点的直观下才是矛盾的

3.2 一般递归函数

一般递归性给出了机械程序的恰当定义。

原始递归：f1(m, n) = m+n; f2(m, n) = m*n; f3(m, 1) = m, f3(m, n+1) =f1(f2(m,n), ...)

并不是所有可计算函数都是原始递归的，比如，我定义一个f1(m), 再定义f2(m) = f1(m-1) + f1(m+1), 那它就不是原始递归的，但是它是可计算的。

仅仅通过形式定义有无法中止的危险，所以在某些确定的步骤，函数一定是可计算的。

3.3 图灵可计算性

图灵机的构造：

图灵机成立的原则：

a. 确定性原则

b. 有穷性原则

如果考虑人类执行这些代码，因为人类无法处理无限的符号，所以图灵机需要有有穷性原则。

3.4 可行性分析