1

我明天要考GRE，有一个问题。根据答案键，这个练习测试表明从 N 到 {0, 1} 的所有函数的集合是不可数的。

您不能将自然数映射到这些函数，如下所示？

 i   1 2 3 4 5 6 7 8 ...
f0 = 0 0 0 0 0 0 0 0 ...
f1 = 1 0 0 0 0 0 0 0 ...
f2 = 0 1 0 0 0 0 0 0 ...
f3 = 1 1 0 0 0 0 0 0 ...
f4 = 0 0 1 0 0 0 0 0 ...

也就是说，f4(1)=0，f4(2)=0，f4(3)=1，f4(其他)=0。这最终不会涵盖所有可能的这些功能吗？我们绝对可以将自然数映射到这个集合。

4

4 回答 4

5

您列表中的所有条目将包含有限数量的条目。在您的列表中，所有偶数返回 0 但所有赔率返回 1 的函数会出现在列表的哪个位置，或者总是返回 1 的函数？对角化参数可以表明没有其他编号方案也可以工作。为此，考虑一个在位置 i 处返回 1-(fi(i)) 的函数。那么这个函数至少在一个地方与列表中的每个条目不同，所以它不在列表中。

于 2009-04-04T04:53:39.207 回答
1

这是康托尔定理的一部分。见这篇论文（接近尾声。）

于 2009-04-04T04:42:57.097 回答
1

如果这是可数的，那么非理性也必须是可数的。想想你列出的每个二进制十进制函数，你可以将它们与实数 [0, 1) 1:1

于 2009-04-04T04:44:31.070 回答
1

由该算法构造的任何函数 f_k 都有有限数量的值 n，使得 f_k(n)=1，但您有函数 f(odd)=1, f(even)=0，这是一个有效的函数并且不在此算法可以生成的函数列表中。

一般来说，您可以应用康托尔的对角线论证，如 Dan 所述。如果这样的集合是可数的，那么你有一个可数的函数族 g_1，g_2，...，它们涵盖了整个集合。但是你可以构造一个新函数 h 使得 h(n) != g_n(n)，通过构造 h 不能等于任何 g_k，荒谬！

于 2009-04-04T05:01:56.987 回答