明日はGREを取って、質問があります。解答鍵に基づいて、この実践テストは、Nから{0,1}までのすべての関数の集合が数えられないことを述べている。カウントアウェイ質問（理論）
次のように、自然数をこれらの関数にマップすることはできませんか？ 、F4（1）= 0、F4（2）= 0、F4（3）= 1、およびF4（何か）=である
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 ...
0。最終的には、これらの機能のすべての可能な種類をカバーしませんか？そして、私たちは間違いなく自然数をこの集合に写像することができます。
リストのすべてのエントリには1の有限数が含まれます。あなたのリストでは、すべてのevensに対して0を返しますが、すべてのオッズに対して1を返す関数、または常に1を返す関数はどこにありますか？対角化の議論は、他の番号付けスキームが動作しないことを示すことができる。これを行うには、位置iに1-（fi（i））を返す関数を考えます。この機能は少なくとも1つの場所でリストの各エントリと異なるため、リストにはありません。
これはカンターの定理の一部です。 this paper（最終付近）を参照してください。
これが数えられれば、不合理なものも数えなければなりません。バイナリ小数点としてリストアップしたこれらの関数のそれぞれについて考えてみて、それらを1：1にすることができます。
このアルゴリズムによって構築される関数f_kは、f_k（n）= 1となるような有限数の値nを持ちますが、関数f（odd）= 1、f（even）= 0を持ちます。有効な関数であり、このアルゴリズムで生成できる関数のリストには含まれていません。
一般的にDanによって示されているように、カンターの対角引数を適用できます。そのような集合が数えられれば、集合全体をカバーする数列の関数g_1、g_2、...が得られます。しかし、h（n）！= g_n（n）という新しい関数hを構築することができます。これは、hはg_kのどれとも等しくないことがあります。
実際、自然数のi、jのタプル（i、j）のセットは、確かに数えることができます。だから私はGREがこれを間違っていると思う。 – Claudiu
@Claudiu：もちろんNxNは数えられますが、それは問題ではありません。それは関数N - > {0,1}の集合であり、これは数えられない（練習問題：この集合が実数集合と同じ基数を持つことを証明する）。 – ShreevatsaR