自然数から{0, 1}への関数全体の集合が非可算であることの証明
$ Natから$ Nat \rightarrow \{0, 1\}への全単射が存在すると仮定して矛盾を導く。
そのような全単射を$ fとする。$ a_{m n} = f(m)(n)とおくと、各$ mに対する$ f(m)の定義は以下のような表に書き起こせる。
$ \begin{array}{l} & 0 & 1 & 2 & ... \\ f(0) & a_{00} & a_{01} & a_{02} & ... \\ f(1) & a_{10} & a_{11} & a_{12} & ... \\ f(2) & a_{20} & a_{21} & a_{22} & ... \\ ... \end{array}
ここで、以下のように関数$ g: Nat \rightarrow \{0, 1\}を定義する。
$ g(n) = \begin{cases} 0 & (a_{nn} = 1) \\ 1 & (a_{nn} = 0) \end{cases}
$ gは表の対角線成分の値を反転させた関数に他ならない。
$ gは$ Nat \rightarrow \{0, 1\}であるから、ある自然数$ mが存在して$ g = f(m)となる。
よって$ gは表のどこかに位置するはずである。
しかし、$ gの対角線成分はどの$ f(n)とも異なるので矛盾。