明日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です。これは最終的にこれらの機能のすべての可能な種類をカバーしませんか？そして、自然数をこのセットに確実にマッピングすることができます。
リスト内のすべてのエントリには、有限数のエントリが含まれます。リストのどこに、すべての偶数に対して0を返すが、すべてのオッズに対して1を返す関数が表示されますか、それとも常に1を返す関数が表示されますか？対角化の議論は、他の番号付けスキームも機能しないことを示すことができます。これを行うには、位置iで1-（fi（i））を返す関数を考えます。この場合、この関数はリスト内の各エントリと少なくとも1つの場所で異なるため、リストには含まれていません。
これはカントールの定理の一部です。この論文を参照してください（終わり近く）。
これが可算であるならば、不合理なものも可算でなければならないでしょう。リストした各関数を2進数の小数として考えれば、実数[0、1）と1：1で表すことができます。
このアルゴリズムによって構築される関数f_kは、f_k（n）= 1のように有限数の値nを持ちますが、有効な関数である関数f（odd）= 1、f（even）=0があります。このアルゴリズムで生成できる関数のリストにはありません。
一般に、ダンが述べたように、カントールの対角論を適用できます。そのような集合が可算である場合、集合全体をカバーする可算関数g_1、g_2、...のファミリーがあります。しかし、その後、h（n）！= g_n（n）となるような新しい関数hを作成できます。作成により、hはg_kのいずれにも等しくなりません。