可数性问题(理论)

我明天要参加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.这最终会涵盖所有可能的这些功能吗？我们绝对可以将自然数映射到此集.

列表中的所有条目都包含有限数量的条目.你的列表中的所有evens返回0但是所有赔率都返回1的函数或总是返回1的函数？对角化参数可以表明没有其他编号方案可以工作.为此,请考虑在位置i返回1-(fi(i))的函数.然后,此函数与列表中的每个条目在至少一个位置上不同,因此它不在列表中.