{悖论} 对角线法的合理解释

[hyifeng]

在证明实数不可数时，康托尔发明了反对角线法。
对这个方法，我一直心存疑惑。

------------------实数不可数的反对角线证明-----------------

我简要描述一下对角线法证明实数不可数的过程。

假设实数是可数的，那么0~1之间的实数也是可数的，
设 0~1 所有实数的枚举为

0.a1 a2 a3 a4 a5...
0.b1 b2 b3 b4 b5...
0.c1 c2 c3 c4 c5...
...

其中 a1 a2 ... an ... b1 b2 ....代表的是每一位小数

那么断言这个实数
0.m1 m2 m3 ...
不在上面的集合中，只要m1!=a1，m2!=b2, m3!=c3 .....

因为 m1!=a1 所以这个数不可能和枚举中的第1个数相等，
因为 m2!=b2 所以这个数不可能和枚举中的第2个数相等，
....

所以，0~1的实数不可以被枚举，实数集不可数。

---------------------------证毕-------------------------------

我不清楚的一点是，为什么这个方法是可以的。
为什么这个无穷的过程生成实数，是可以被取得并拿来进行反证的？

为了表达我的意思，我用自然数为例，

假设所有自然数的枚举是
35, 124, 7, 99, .....
此集合用符号 N 表示。

max(C) 表示从数集C中取最大值，
max(35) = 35
max(35, 124) = 124
max(35, 124, 7) = 124
...

设 U = max(N)，
因为 U属于N，所以 U是一个自然数，并且 U+1是被定义的。
那么断言这个自然数
U+1
不在N中，因为U+1大于N中任何一个元素。

那么结论是：自然数是不可枚举的。
但很明显这是一个矛盾，由此可以证明一个无穷为完成的过程不可以当作一个结果来使用。

请看出其中逻辑错误的同学指点。

[alai]

什么叫"枚举"？你对于自然数的证明只是证明了自然数不是有限的。

对角线法则是证明实数是不可数的，即不存在实数与自然数的一一对应。

2008/8/26 hyifeng <hyi...@gmail.com>

[hyifeng]

我对于自然数的证明 是想说

如果一个无穷未完成的过程得到的结果可以当作一个实体来使用的话，
那么，能证明不存在自然数与自然数的一一对应。

On 8月26日, 下午8时20分, alai <ala...@gmail.com> wrote:
> 什么叫"枚举"？你对于自然数的证明只是证明了自然数不是有限的。
> 对角线法则是证明实数是不可数的，即不存在实数与自然数的一一对应。
>

> 2008/8/26 hyifeng <hyif...@gmail.com>

[hyifeng]

其实我没弄明白，一个由无穷的过程得到的结果，拿来反证实数的不可数，是不是合理的。

On 8月26日, 下午8时20分, alai <ala...@gmail.com> wrote:

> 什么叫"枚举"？你对于自然数的证明只是证明了自然数不是有限的。
> 对角线法则是证明实数是不可数的，即不存在实数与自然数的一一对应。
>

> 2008/8/26 hyifeng <hyif...@gmail.com>

[鋆邓]

你的错误在于:

证明实数不可数的对角线法是：

假设有存在一种正确的对应方式，在这种对应方式下用对角线法得到一个实数，这个实数无法在列表中找到对应的整数，因此证明该对应方式不正确，从而证明正确的对应方式是不存在的。

而你似乎在列举一种错误的对应方式，但不能证明正确的对应方式是不存在的。

2008/8/26 hyifeng <hyi...@gmail.com>

[鋆邓]

注意对应的两个数必须是可明确说明的，

比如：

我说无穷循环小数132.389389389....对应着1995532是可以的，但不可以说它对应着一个"无穷循环整数"399399399399.....，因为无穷大并不算一个明确的整数。

对于你的整数对应规则也一样，如果你能对任何一个整数到整数的对应规则，证明存在一个可明确说明的整数，它一定不能对应另一个可明确说明的数，那么恭喜你证明了整数不可数。

2008/8/26 鋆邓 <tdzl...@gmail.com>

[hyifeng]

> 而你似乎在列举一种错误的对应方式，但不能证明正确的对应方式是不存在的。

嗯。

我没有感觉到我那个方法是你说的那样，
它一样是假设存在一种对应方式，则总能找到一个自然数，不在其中。只不过不是“对角线数”而是“max+1”罢了。


区别是，明明我们知道有一种方式，能正确映射max+1，
而不是，明明我们知道有一种方式，能正确映射0.m1 m2 m3 ...
所以，我们感觉康托尔是对的，我是错的。

On 8月26日, 下午8时34分, "鋆邓" <tdzl2...@gmail.com> wrote:
> 你的错误在于:
> 证明实数不可数的对角线法是：
> 假设有存在一种正确的对应方式，在这种对应方式下用对角线法得到一个实数，这个实数无法在列表中找到对应的整数，因此证明该对应方式不正确，从而证明正确的对应方式是不存在的。
> 而你似乎在列举一种错误的对应方式，但不能证明正确的对应方式是不存在的。
>

> 2008/8/26 hyifeng <hyif...@gmail.com>

[hyifeng]

这个我明白，
可是我没有违反可数的概念啊。

On 8月26日, 下午8时38分, "鋆邓" <tdzl2...@gmail.com> wrote:
> 注意对应的两个数必须是可明确说明的，
> 比如：
> 我说无穷循环小数132.389389389....对应着1995532是可以的，但不可以说它对应着一个"无穷循环整数"399399399399.....，因为无穷大并不算一个明确的整数。
> 对于你的整数对应规则也一样，如果你能对任何一个整数到整数的对应规则，证明存在一个可明确说明的整数，它一定不能对应另一个可明确说明的数，那么恭喜你证明了整数不可数。
>

> 2008/8/26 鋆邓 <tdzl2...@gmail.com>

>
> > 你的错误在于:
> > 证明实数不可数的对角线法是：
>
> > 假设有存在一种正确的对应方式，在这种对应方式下用对角线法得到一个实数，这个实数无法在列表中找到对应的整数，因此证明该对应方式不正确，从而证明正确的对应方式是不存在的。
> > 而你似乎在列举一种错误的对应方式，但不能证明正确的对应方式是不存在的。
>

> > 2008/8/26 hyifeng <hyif...@gmail.com>

[鋆邓]

恩，那你的问题就是，证明过程应该说明正确的对应方法不存在，而不是存在一种错误的方法。

2008/8/26 hyifeng <hyi...@gmail.com>

[hyifeng]

不是已经是你说的那样了吗？

我在重申一下我的目的：

1，假设存在一种方法枚举所有的自然数
2，通过一个无穷的过程得到一个自然数，不在这个枚举之中
3，矛盾，得出不存在枚举所有的自然数的方法，自然数不可数
4，再次矛盾，从已知条件知自然数必然可数，
一个无穷未完成的结果不可以作为实体使用，从而推翻对角线法。

我最终的目的是，对角线法不成立。

On 8月26日, 下午8时52分, "鋆邓" <tdzl2...@gmail.com> wrote:
> 恩，那你的问题就是，证明过程应该说明正确的对应方法不存在，而不是存在一种错误的方法。
>

> 2008/8/26 hyifeng <hyif...@gmail.com>

[鋆邓]

恩，那你的问题就是，按照你的方法得到的那个整数U是不存在的，因为max(N)是不存在的。

至少是不明确的。

2008/8/26 hyifeng <hyi...@gmail.com>

[Eric]

max(.) 函数只能对有限个数定义。对无限个数的定义，如自然数，由自然数的性质，max(N) 不存在

你的悖论的根源，是你的max 函数自己臆想了它可以等于一个固定的数U

好好想想对角线函数定义的时候函数值是不是能明显确定的，而你是不是well-define “对角线数”

[obtuseSword]

首先，你的错误是因为你的过程无法终止，而你想确定的数（最大数）依赖于你的过程，所以自然数集无法通过你的过程确定一个最大数。

其次，引起你对Cantor证明的疑惑的症结不在于它确定每一位小数的过程，而在于，一个实数，是否可以通过一个数列（就是各小数位）来表达。 这
产生了一个问题，实数到底是什么？

其实，现代数学中的实数，是一个很抽象的概念，实数系无非是一个代数系统。我们都知道，现代数学的基础是集合论，数学中的所有对象，如果非要追根究
底的话，都可以找出它们的集合定义，也就是说，所有数学对象都是“集合”，集合如同构成数学世界的基本粒子。现在再来说实数，它也是通过已经定义的数学
对象定义出来的，流行的有两种定义方式，一种是Cantor的定义，利用了Cauchy序列，另一种是Dedekind的定义，利用了“有理分划”，他
们都是通过已经定义的有理数来定义实数的。而小数表示法并不是一种定义，它只是表示实数的一种方法，这种表示法为何是正确有效的，需要证明。现在我们姑
且承认这一事实：任何0到1之间的实数都和一个0-1序列一一对应。那么再来看Cantor对实数不可数的证明：

假定实数集是可数的，那么所有实数可以构成一个数列 { R(n) }，将每个实数按二进制展开 R(n) = dn1 dn2 dn3 ...
dn1 , dn2 , dn3 ... 要不是0，要不是1. 再考虑一个二进制序列，d1 = ~d11, d2 = ~d22, ... （~
表示取反）显然这个序列对应一个实数，但不等于{ R(n) } 中的任何一个，矛盾。 这里对二进制序列的描述与你对最大数的定义的区别是，你那里
最大数这个对象是否存在都是不知道的，只有你不断更新最大值的过程终止后，才能确定是否存在这样一个对象。 而这里我们要的是一个数列，数列无非是一个
有序对的集合{ (~d11,d1),(~d22,d2),... } ，而有序对又可以通过集合来定义，集合论的公理保证了我们描述的对象是存在的，
我们的描述只是要“把握”它，就是在茫茫的数学对象中“抓住”我们想要的对象，让它出来说话。我们描述这个实数的时候，当然是一个过程，因为我们只能一
位一位地说出它的数码，但是这个实数已经先于我们的描述而存在。

[Bruce Khereid]

很高兴看到这里开始讨论这么“稳重”的问题了。以下是我的解释，请基础数学学得
好的同学指正错误：

你举的正反两个例子本质的不同点在于，你将 0.m1 m2 m3 ... 这个实体和
max(N) 这个实体相比较，这两个实体的存在性是有差异的。

我们先说 max(U)，你没有给 max(x) 下严格的定义，只是说，是在参数集合中取
最大的元素，可并没有证明其存在性，例如，对于任何有限的自然数集，max(X)
自然是存在的（你举的三个例子均属于这一情况），但对全体自然数构成的集合
max(N) 当然不存在，而你直接从三个例子就得出了其存在的结论，这就是整个“悖
论”的原因所在。

再说 0.m1 m2 m3 ... 这个数，我这里简写为 c0 吧。在我们得出 c0 之前，假设
中的由 (0,1] 的全体元素构成的数列已经构造完毕（或者说已经客观存在），由
可列集的定义，它就是已经存在的，而不需要一个“无穷步骤的过程”来创造它（要
知道数学证明不是跑在图灵机上的）。那么对于一个确定的实数列，c0 也是确定
的，因为如果用 q[n] 表示数列中第 n 个元素的话 c0 “就”等于
Sigma{ i = 1, 正无穷}(( q[i] * E ^ i) % E) / E ^ i。
（你可能会说，你看，这个 Sigma 中不也引入了无穷吗，这里 Sigma 只是一种简
写形式，像 lim{ n -> 无穷} 一个道理，它表示：
如果用 p[i][j] 表示 q[i] 小数形式中第 j 位，c0[j] 表示 c0 小数形式中第 j
位，则对于任意 k 属于正整数集，均满足 p[i][k] = c0[k]。）

对于 c0 在数列中的存在性也是如此，由 c0 的定义即可证明其不存在。因为对于
任意 k 属于正整数集，p[k][k] 不等于 c0[k]，即 q[k] 不等于 c0（这里要提到
你漏写了康托尔给的一个假设，对于有限小数的两种表示法，只取确定规则下的一
种，只有这个假设 q[k] 不等于 c0 才成立）。对于任意正整数 k，q[k] 的集合
等于上述数列元素构成的集合，那么显然 c0 也不存在于数列中。

所以我认为这个证明没问题。不过历史上是不是确实有很多人质疑他这一证明过
程？谁了解这些质疑的理由？可以给大家介绍一下吗？康托尔后来给过一个基于闭
区间套定理的证明，和这些人的质疑有关吗？

[hyifeng]

> max(.) 函数只能对有限个数定义。对无限个数的定义，如自然数，由自然数的性质，max(N) 不存在
>
> 你的悖论的根源，是你的max 函数自己臆想了它可以等于一个固定的数U

"由自然数的性质，max(N)不存在" 这个说法反而使我有点模糊。
max是一个行为很明确的函数，如果你承认能从两个数值中选择较大者，
则max可以良好运作，而且取出的数值必在原集合中。

问题是，这是一个不会完成的过程，U是我赋予这个结果的一个代号。
我们都无法想象如果过程能够完结，U具体会是什么。

> 好好想想对角线函数定义的时候函数值是不是能明显确定的，而你是不是well-define “对角线数”

同样反对角线数，我们很清楚如何去构造它，
但是所有的 “半吊子成品” 都是等于没有，直到最后一刻，走完所有实数才得到结果。
所以，*如果反对角线数能完全构造出来，那么我也找出了最大的自然数*
可惜我们知道它们具有什么性质，但不知道具体是什么。

我那个证明还是有很多问题，
“U+1” 是很可能出问题的，因为它可能未定义（因为比∞大1的数不存在）。

[hyifeng]

谢谢各位踊跃发言。

其中有一位同学提到了"区间套定理的证明"，我从网上找了一个转贴过来。

这个证明咋一看，
竟然觉得可以用于证明"有理数"是不可数的。

-------------------------------------------------------------
　　定理4 区间[0,1]中的点是不可数的。
　　证　用反证法。

假定区间[0,1]中的点是可数的，把[0,1]中的点编号为 X1,X2,X3,...,Xn,...
把闭区间[0,1]三等分，则显见 [0,1/3] 与 [2/3,1] 中总有一个区间不含有X1，用I1表示这个闭区间。
把I1三等分，在它们的左与右两个闭区间总有一个不含有X2, 用I2表示这个闭区间。
同样，把I2三等分，可得不含有X3的一个闭区间I3，等等。
据归纳法，便得到一列闭区间{In}。
由作法知，I1 包含 I2 包含 I3 包含 .... 包含 In 包含....
且Xn不属于In, n=1,2,3,...

由于In的长度为1/3^n趋于0，故据数学分析中区间套定理，存在点 E 属于 In (n=1,2,3,...)
由于Xn不属于In，故E不会是任一Xn，但E又是[0,1]中的点，出现了矛盾。
这表明区间[0,1]中的点是不可数的。

-------------------------------------------------------------------------------

[avalon]

自然数枚举和与之对比的实数例子，还是有区别的。

证明实数不可数，用的是反证法，构造了一个实数，
不存在于任何可能的实数的子集中；

自然数的例子中，你证明了对于任意有限个自然数的子集，
可以找到未被枚举出的自然数

显然，这里的有限个是不能推广到任意概念上的。



hyifeng 写道:

[hayate]

说说怎么证明是有理数的
ps:区间套定理是实数基本定理

2008/8/27 hyifeng <hyi...@gmail.com>

[hyifeng]

> 由于In的长度为1/3^n趋于0，故据数学分析中区间套定理，存在点 E 属于 In (n=1,2,3,...)

"故据数学分析中区间套定理" 换成平均值，
设In为[a,b] ，必然有点E=(a+b)/2 属于 In

> 由于Xn不属于In，故E不会是任一Xn，但E又是[0,1]中的点，出现了矛盾。

On 8月27日, 上午10时14分, hayate <hayate...@gmail.com> wrote:
> 说说怎么证明是有理数的
> ps:区间套定理是实数基本定理
>

> 2008/8/27 hyifeng <hyif...@gmail.com>

[Bruce Khereid]

1、这个 E 是全局性质，对于所有 In 都是这一个确定的 E，而不是对每个 In 有
一个特定的 E。（从而显然 E 不能和 a 或 b 有关，因为 a 或 b 和 n 有关）

2、这个唯一公共点不是你说了算的，它是由区间序列的收敛方式客观决定的，不
是想取“平均值”就可以取的。

你可以进一步考虑这个 E 到底是什么。事实上，它就是你的区间套左界数列和有
界数列的极限，这两个极限是相等的，就是 E，而且由于极限唯一性，E 也是唯一的。

这样一来，你的问题就清晰了：这个 E 是有理数还是无理数？如果 E 必然是有理
数的话，你的质疑是正确的，即有理数就是不可列的。可惜，E 不一定是有理数。
事实上，这也是无理数的一种定义方式，有理数对极限运算是不封闭的。

[hyifeng]

兄弟你解析得很好。

[pongba]

2008/8/27 Bruce Khereid <bruce....@gmail.com>

1、这个 E 是全局性质，对于所有 In 都是这一个确定的 E，而不是对每个 In 有
一个特定的 E。（从而显然 E 不能和 a 或 b 有关，因为 a 或 b 和 n 有关）

2、这个唯一公共点不是你说了算的，它是由区间序列的收敛方式客观决定的，不
是想取"平均值"就可以取的。

你可以进一步考虑这个 E 到底是什么。事实上，它就是你的区间套左界数列和有
界数列的极限，这两个极限是相等的，就是 E，而且由于极限唯一性，E 也是唯一的。

这样一来，你的问题就清晰了：这个 E 是有理数还是无理数？如果 E 必然是有理
数的话，你的质疑是正确的，即有理数就是不可列的。可惜，E 不一定是有理数。
事实上，这也是无理数的一种定义方式，有理数对极限运算是不封闭的。

兄台解释得很好:-)
我补充一个出处：哈代的《纯数学教程》第一章（或者第二章，记不清了）对此有很好的解释。

--
刘未鹏(pongba)|C++的罗浮宫
http://blog.csdn.net/pongba
TopLanguage
http://groups.google.com/group/pongba

[up duan]

我觉得只要把"可数"这个概念分析清楚就可以解释问题。

可数：可以跟自然数序列一一对应。

那么可以直接推论出自然数可数。简单的推理也可以推导出整数集可数。

实数集不可数采用的是对角线法证明的。属于反证法，不是构造性证明，但是人们觉得置信度非常高，几乎等于确定。

2008/8/27 pongba <pon...@gmail.com>

[pongba]

根据我的理解，你的核心疑惑应该是：

根据对角线构造出来的一个实数，它后面的小数怎么写都写不完，换言之，似乎不管我们往后怎么走都不能"确切"地锁定它的值。那这个"动态"的东东能叫一个数吗？（我们平常称"一个数"是说一个明确的，固定的数）。

说实话这很不直观，我自己也有疑惑。但又找不到方法反驳。举个例子，圆周率的小数点往后拓展永远也拓展不完，但并不影响圆周率是一个确定的数，因为每个圆的周长直径比却毫无疑问是可以证明是相等的。

我想这里的问题应该在于"实数到底能不能通过这里的对角线方法来描述"，Bruce 提到实数是可以用有理数或实数无穷数列的极限来描述的（《纯数学教程》），如果我们接受这个定义，便可以将对角线方法的描述转化为区间套描述了，如下：

0.a1 a2 a3 a4 a5...
0.b1 b2 b3 b4 b5...
0.c1 c2 c3 c4 c5...
..

首先，根据第一行，我们的实数位于

0~1 之间 => 此为区间套的第一个区间

根据第二行，我们的实数位于：

0.r1 ~ 0.(r1+1) 之间 => 此为区间套的第二个区间

r1 代表选取的第一个不等于a1的数。

根据第三行，实数位于：

0.r1r2 ~ 0.r1(r2+1)之间

...

显然，这是一个无穷区间套，根据区间套定理必然有一个实数属于所有区间。

2008/8/26 hyifeng <hyi...@gmail.com>

在证明实数不可数时，康托尔发明了反对角线法。
对这个方法，我一直心存疑惑。

------------------实数不可数的反对角线证明-----------------

我简要描述一下对角线法证明实数不可数的过程。

假设实数是可数的，那么0~1之间的实数也是可数的，
设 0~1 所有实数的枚举为

0.a1 a2 a3 a4 a5...
0.b1 b2 b3 b4 b5...
0.c1 c2 c3 c4 c5...
...

其中 a1 a2 ... an ... b1 b2 ....代表的是每一位小数

那么断言这个实数
0.m1 m2 m3 ...
不在上面的集合中，只要m1!=a1，m2!=b2, m3!=c3 .....

因为 m1!=a1 所以这个数不可能和枚举中的第1个数相等，
因为 m2!=b2 所以这个数不可能和枚举中的第2个数相等，
....

所以，0~1的实数不可以被枚举，实数集不可数。

[denny.wang]

第一次发言，呵呵

我觉得你第二个证明中"U属于N"是错误的推论。。

 

在08-8-27，up duan <fix...@gmail.com> 写道：

[denny.wang]

关于第二个自然数的证明，问三个问题：

1.你用的是反证法么？那么你的假设是什么，枚举的意思？

2.N指的是什么？是所有的自然数集？

3.如果N指的是自然数集，那么max(N)存在是否存在，若存在就一定在N里面，无穷大似乎不是自然数

 

在08-8-27，denny. wang <wxia...@gmail.com> 写道：

--
Best Regards!

From: Denny Wang

[Bruce Khereid]

看到 pongba 的话，我想再用另一种说法说两句（怎么感觉咱们把楼主放手术台上
解剖了呢？哈哈，玩笑），

依我看来，楼主认为“无穷”这个词不总是可靠。的确，很多同学不小心的时候容易
犯一种错误就是将一个性质从有限情况无条件推广到无限情况，楼主举的例子
（max(X)）就是这一类情况，这一推广在无条件时总是不可取的。

但这和另一种情况是完全不同的：定义中、公理中指定了无限的情况的。例如实数
的小数表示法、可列集与自然数集的一一对应关系等。

虽然楼主没有给出明确的定义，但大家的“常识”中，max(X) 是定义在有限集上
的，直接取得其在 N 上的值是错误的。但定义 c0（见我第一封邮件），用的是实
数的小数表示法的定义，自然没有问题。在我第一封邮件中括号里对 Sigma 中的
无穷的解释也是同理。

[hyifeng]

我发贴就是为了让大伙解剖的，不用手软，呵呵。


前面我说过的一段话表达了我的看法：
-----------------------------------------

max是一个行为很明确的函数，如果你承认能从两个数值中选择较大者，
则max可以良好运作，而且取出的数值必在原集合中。

问题是，这是一个不会完成的过程，U是我赋予这个结果的一个代号。
我们都无法想象如果过程能够完结，U具体会是什么。

同样反对角线数，我们很清楚如何去构造它，
但是所有的 “半吊子成品” 都是等于没有，直到最后一刻，走完所有实数才得到结果。
所以，*如果反对角线数能完全构造出来，那么我也找出了最大的自然数*

可惜我们知道它们具有什么性质，却不知道具体是什么。
------------------------------------------

*如果反对角线数能完全构造出来，那么我也找出了最大的自然数*

我觉得两者的情况类似，你无法想象U会是多少，我也无法想象这个反对角线数是多少。
所以只能描述出其意义、性质，而不是给出一个具体的数值。U 只是一个符号，如pongba说的PI。

> > 2008/8/26 hyifeng <hyif...@gmail.com>

[hyifeng]

> 说实话这很不直观，我自己也有疑惑。但又找不到方法反驳。举个例子，圆周率的小数点往后拓展永远也拓展不完，但并不影响圆周率是一个确定的数，因为每个圆的周长直径比却毫无疑问是可以证明是相等的。

呵呵，
你这种理解我也想过。

你提到的这本《纯数学教程》，我有时间一定会找来看看。

On 8月27日, 下午1时14分, pongba <pon...@gmail.com> wrote:
> 根据我的理解，你的核心疑惑应该是：
>
> 根据对角线构造出来的一个实数，它后面的小数怎么写都写不完，换言之，似乎不管我们往后怎么走都不能"确切"地锁定它的值。那这个"动态"的东东能叫一个数吗？（我们平常称"一个数"是说一个明确的，固定的数）。
>
> 说实话这很不直观，我自己也有疑惑。但又找不到方法反驳。举个例子，圆周率的小数点往后拓展永远也拓展不完，但并不影响圆周率是一个确定的数，因为每个圆的周长直径比却毫无疑问是可以证明是相等的。
>
> 我想这里的问题应该在于"实数到底能不能通过这里的对角线方法来描述"，Bruce
> 提到实数是可以用有理数或实数无穷数列的极限来描述的（《纯数学教程》），如果我们接受这个定义，便可以将对角线方法的描述转化为区间套描述了，如下：
>
> 0.a1 a2 a3 a4 a5...
> 0.b1 b2 b3 b4 b5...
> 0.c1 c2 c3 c4 c5...
> ..
>
> 首先，根据第一行，我们的实数位于
>
> 0~1 之间 => 此为区间套的第一个区间
>
> 根据第二行，我们的实数位于：
>
> 0.r1 ~ 0.(r1+1) 之间 => 此为区间套的第二个区间
>
> r1 代表选取的第一个不等于a1的数。
>
> 根据第三行，实数位于：
>
> 0.r1r2 ~ 0.r1(r2+1)之间
>
> ...
>
> 显然，这是一个无穷区间套，根据区间套定理必然有一个实数属于所有区间。
>

> 2008/8/26 hyifeng <hyif...@gmail.com>

[nolavosky]

首先申明我并不是数学系的学生，很多地方还是凭着感觉走的，因而很有可能犯了很恶心的错误：）

对角线法分别针对实数和自然数，整理如下：
实数P[i] 自然数
可｜ 0.a1a2a3... 可｜0
数｜ 0.b1b2b3... 数｜1
长｜ 0.c1c2c3... 长｜2
度｜ ... ... 度｜...
操作：
作m，使m[i]!=P[i][i] 起始n=0，如果n<=i n=i+1 (扩展的max())

由于假设实数集合是可数的，已知自然数集合是可数的，那么如果m可以得到，n也可以。
实数的定义有好几种，这里将其定义为无尽小数，比较直观。那么作为无尽小数，m属于实数，进而推出谬误。
那么n是自然数么？存在比所有自然数大的自然数么？对于这个问题，我们似乎遇到了罗素悖论（理发师悖论，只要将罗素悖论标准描述中通常为不等号的二元关
系改为大于号即可）。

以上的推导应该都是朴素集合论中的东西，但是罗素悖论用朴素集合论无法解决，得借助公理化集合论。

请问大家怎么看呢？

On Aug 26, 12:13 pm, hyifeng <hyif...@gmail.com> wrote:
> 在证明实数不可数时，康托尔发明了反对角线法。
> 对这个方法，我一直心存疑惑。
>
> ------------------实数不可数的反对角线证明-----------------
>
> 我简要描述一下对角线法证明实数不可数的过程。
>
> 假设实数是可数的，那么0~1之间的实数也是可数的，
> 设 0~1 所有实数的枚举为
>
> 0.a1 a2 a3 a4 a5...
> 0.b1 b2 b3 b4 b5...
> 0.c1 c2 c3 c4 c5...
> ...
>
> 其中 a1 a2 ... an ... b1 b2 ....代表的是每一位小数
>
> 那么断言这个实数
> 0.m1 m2 m3 ...
> 不在上面的集合中，只要m1!=a1，m2!=b2, m3!=c3 .....
>
> 因为 m1!=a1 所以这个数不可能和枚举中的第1个数相等，
> 因为 m2!=b2 所以这个数不可能和枚举中的第2个数相等，
> ....
>
> 所以，0~1的实数不可以被枚举，实数集不可数。
>

[Eric]

我说两个

1. 什么叫well-defined的函数. 是说这个函数对于定义域里面每个值都对应到一个确定的值。 对角线法则的变换函数就是well-
defined, 在二进制的情况下就是1对应到0， 0对应到1。而对角线法则只是在每个不同的位上面用这样的映射无穷多次而已。 而你说的
max()可以求，是因为可以应用有限集合的max法则无穷多次得到一个max. 请注意对角线法则的无穷多次， 是一个定义良好的函数应用了无穷多
次。 你的无穷多次， 是为了求一个函数值递归了无穷多次。 这个无穷多次一来， 这个最大函数max 就不是well-define 的。楼主的证明
实际上就是证明了这个函数不是well-define的。

其实假设max(N)=U, 然后U是自然数的话， 本身就是有悖论的，因为这就蕴含了N当中所有的数都小于等于U了。 因此，这个悖论完全是max造
成了，和对角线法则无关。

2. 什么叫做可以无穷下去？ 比如为什么写对角线的过程可以连续的写下去而没有数学家怀疑呢？ 因为可以无穷下去就是说这个序列是能对应到自然数的，
是可数的，因此可以一个一个的写下去。 而反观 max (.) 的含义， 是定义在自然数的幂集上的。自然数的幂集是不可数的，所以对于很多自然数的
子集合来说 max(.) 是无法从简单的有限集合的定义推广的，比如max(偶数)就是没法定义的。 要证明 max 对于所有的子集都有定义， 才
能证明max是well-define的，而这个是没法证明的。

再说服不了你，我也没办法了 :)

[hyifeng]

这里well-define的意义是，对结果中*任意确定的*位n，是可以通过有限步确定的。
而max做不到，是这个意思？

[hyifeng]

那我继续说，
假如就是上面的那个意思。

那，只要能找到一个方法能起到max相似的结果，但是过程是对结果中任意的位都能通过有限步来确定的，就如你说的well-define了。

把一个自然数左右倒置，例如 521 就是：
个 十 百 千 万 .....
1 2 5 0 0 .....

把所有自然数的枚举都写成上面的形式

1 2 5 0 0 ...
4 0 0 0 0 ...
0 0 7 1 0 ...
....

用编号来表示：（ nxx 表示一位数字）

n11 n12 n13 n14 .....
n21 n22 n23 n24 .....
n31 n32 n33 n34 ...
n41 n42 n43 n44 ...
...

现在考虑对角线（右上<->左下）的数列，

数列1: n11
数列2: n12 n21
数列3: n13 n22 n31
数列4: n14 n23 n32 n41
.....

每一条对角线确定一位数，数列1 确定个位，数列2 确定十位，数列3 确定百位 .....
这每一位数，都是取这条对角线上出现最大的数字 （是从0 ~ 9的）

例如，从个位开始 数过来第6位数（即十万位），只用考虑前6个数就可以确定。
任何一位数，都可以通过有限步确定。

生成的这个数，必然 “大于等于” 集合中所有的数。

不知道这种方法算不算well-define？

[hyifeng]

呵呵，

发完后就觉得不对了...