対角線論法で自然数の濃度が実数の濃度と等しいことを示せるか?

証明

任意の自然数aに対し、ある自然数bが存在してa < 2^b となることを示す。
このようなbが存在しないと仮定すると、任意のbに対して a ≧ 2^b
したがって、集合A = {2^b | b ∈ N} を考えると、この集合は上に有界であるので、上限u = sup Aが存在する。
 
いま、u' = u / 2 とおく。
uは明らかに正である(0 < 2 ∈ A)ので、u' < u
したがって、u' = u / 2 < 2^b' をみたすb' ∈ Aが存在する。
これより 2^(b + 1) > u
2^(b + 1) はAの要素なので、sup Aより大きいAの要素が存在することになるが、これは矛盾。
ゆえに任意の自然数aに対し、ある自然数bが存在してa < 2^b. (ア)
 
(ア)を用いて、次に定義されるXが自然数でないことを示す。
数列表現 {1, 1, 1, ...} ({a_n}, a_n = 1) で表される自然数Xを仮定する。
仮定よりX + 1 は自然数。
これと(ア)より、ある自然数Bが存在して 2^B > X+1.
明らかにB≠0なので、2^B - 1 > 0.
ゆえに 2^B + (2^B - 1) > 2^B > X+1.
 
変形して
2 * 2^B - 1 > X + 1
2^(B + 1) - 1 > X + 1
Σ(k = 0..B) 2^k > X + 1 > X (イ)
 
Σ(k = 0..B) 2^k は {a'_n} (n > B ならばa'_n = 0, それ以外ならばa'_n = 1) という数列で表されるが、
X は {a_n}, a_n = 1 で表されるので、明らかにX > Σ(k = 0..B) 2^k (ウ)
 
(イ)と(ウ)は矛盾。
これはXが自然数であると仮定したからである。
よって、数列表現{1, 1, 1, ... }で表される自然数は存在しない。
 
 
いま、ある自然数Yを表す数列{A_n}に対し、ある自然数mが存在してn > m ⇒ A_m = 1をみたすとする。
Yの後者を有限回取ることで、Xとなる。
つまり、2 ^ m > Mをみたす自然数Mが存在して、 Y + M = X (エ)
右辺は自然数であるが、左辺は自然数でなく矛盾。
これはYが自然数であると仮定したためである。
よって、{A_n}に対し、ある自然数mが存在してn > m ⇒ A_m = 1をみたすような数列で表される自然数は存在しない。

発端

• https://twitter.com/dempacat/status/497749330401300481
• https://twitter.com/dempacat/status/497749888411521024