実数全体の集合 R
ここでは実数全体の集合 R が可算集合ではないことの証明をしましょう。
実数を無限小数に表示します。有限小数は 1=0.9999... にならって表示します。
例えば、
10 = 9.9999999....
√2 = 1.41421356....
1/3 = 0.333333....
1/2 = 0.499999....
π = 3.14159265....
（証明）
背理法で証明します。
R が可算集合であると仮定して、矛盾を導きます。
可算集合の定義「自然数全体の集合 N からの全単射が存在する集合。」
f:N → R 全単射が存在したとしましょう。
この時、実数全体は自然数にあわせて順番に並べることができます。
f(1),f(2),f(3),...,f(k),...
と並べることができます。
今、無限小数 b を次によって定めます。
b の整数部分は 0 で任意の自然数 k に対して
f(k) の 小数第 k 位が 1 ならば b の小数第 k 位は 2,
f(k) の 小数第 k 位が 1 以外ならば b の小数第 k 位は 1.
（1,2 である必要はありません。
重要なのは b と f(k) の 小数第 k 位が違うと言うことです。）
さて、こうして得られた無限小数 b は 実数です。
f は全射なので、∃ m ∈ N such that f(m) = b です。
しかし、b は
「f(m) の 小数第 m 位 と b の小数第 m 位 とが違う」
ように選んだわけですから。f(m) ≠ b です。
これは矛盾です。（証明終わり）
上の証明法を「対角線論法」と言います。
下の図のように実数を並べていき、対角線の部分
と異なるように実数 b を選べば、どの f(k) とも異なる実数を得ることができます
| f(1) = |
A. | a1 |
a2 | a3 |
a4 | a5 |
... |
| f(2) = |
B. | b1 |
b2 | b3 |
b4 | b5 |
... |
| f(3) = |
C. | c1 |
c2 | c3 |
c4 | c5 |
... |
| f(4) = |
D. | d1 |
d2 | d3 |
d4 | d5 |
... |
| f(5) = |
E. | e1 |
e2 | e3 |
e4 | e5 |
... |
| ... |