关于希尔伯特无穷旅馆问题

希尔伯特无穷旅馆问题或许可以揭示出有限和无穷的本质区别:对于一个无穷的集合S,一定可以找到它的一个子集
S`和S的每个元素一一对应。

如果一个集合的每个元素都可以跟自然数集合一一对应,即每个S中的元素都有一个唯一的编号,那么我们说S是“可
数无穷的”。比如对于自然数集合Z,我们可以找到一个映射f:n->2n将Z和它的子集--偶数集合E一一映射。更一般
地,我们其实可以把Z划分成任意有限个不相交子集,每个子集都和Z一一对应。另一方面,一个可数无穷集中的元素
跟任意有限N个可数无穷集的所有元素是可以一一对应的。
	那么,能否建立Z和无穷多个可数无穷集的一一对应呢?为了方便,我们称可数无穷个可数无穷集合是二阶可
数无穷集合,相应地可以定义更高阶的无穷集合。易知下面的方法是可行的:
1---2	3---4     ...	k	...
  /   /   /
1   2	3	4 ...	k	...
| /   /
1   2	3	4 ...	k	...
   /
1	2	3	4 ...	k	...
	这样之所以能成功,是因为选择对角线使在两个维度上同时趋于无穷。也可以想象Z和三阶可数无穷集的对应
关系。但是四阶的我想象不出来了。
	但是这样本身会有一个问题:我们所说的一阶可数无穷和二阶可数无穷的差别是什么呢?既然它们含有同样多
的元素,那么有什么理由把它们分别叫做一阶和二阶呢?
	我将尝试做一下简单的说明(也许在有的人看来相当于什么也没说明)。设集合ZZ是二阶无穷的,不妨设ZZ=
{Z,Z1,Z2,Z3,...Zk...},那么可以看到,ZZ包含了集合Z,Z中的元素,在ZZ中最好称之为“元子”或者其他,因为ZZ
的直接元素不是1,2,3 ...这样的数字,而是这些数字或者其他元素组成的集合。而一旦集合的元素不再是同一级别的,
继续进行推理就会引发很多矛盾。例如著名的罗素悖论:
	设W是全体不包含自身的集合组成的集合。那么,集合W里有没有它自己呢?
在这个命题中,W可以包含集合,也可以包含集合的集合,它的元素不是一个级别的。

	上面构造的方法利用了对角线,它是不是康托的所谓“对角线方法”呢?其实,它只是很多方法的一种,跟“对
角线方法”没有什么联系,也可以这样构造:
1   2	3   4 ...	k	...
    |   |   |
1---2	3   4 ...	k	...
        |   |
1---2---3   4 ...	k	...
            |
1---2---3---4 ...	k	...
	康托的对角线方法是用来证明一个集合不可数的一种方法。即,这样的集合不能用自然数与之一一对应。例如
实数区间[1,2],我们是不可能找到与上面类似的方法使其中的每个元素都有唯一的一个编号的(编号不一定按大小顺
序,实际上,就算是可数的有理数集合Q,也不可能按大小顺序把其中的每个元素编号),康托的对角线方法是这样
解决这个问题的:
	假设我们已经给区间[1,2]中的每个实数编了号,它们是
a1=1.234234...
a2=1.624665...
a3=1.432234...
.
.
ak=1.843543...
.
.
我们将根据这个可数无穷个实数组成的序列构造出一个实数x:
	x的整数部分是1,x的第i位小数x[i]是这样确定的:如果ai的第i位小数是1,那么x[i]=2,否则x[i]=1;
这样的目的是为了保证x不等于ai。这样下去我们发现x在[1,2]中间,但是它跟所有的ai都不相等。所以我们的假设是
错误的,即区间[1,2]内的实数是不可数的。

关于哥德尔、集合论、心灵可计算、图灵机,我有时间将慢慢学习总结。
Advertisements
上一篇文章
下一篇文章
留下评论

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s

%d 博主赞过: