自然数の集合と[0, 1]区間の濃度の違い
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/08/01 07:08 UTC 版)
「カントールの対角線論法」の記事における「自然数の集合と[0, 1]区間の濃度の違い」の解説
自然数全体の集合 N {\displaystyle \mathbb {N} } から[0, 1]区間(=0以上1以下の実数全体の集合)への全単射が存在しない事を以下のように証明できる。後で見るように、この証明は暗に対角線論法を使っている。 なお、[0, 1]区間と実数全体の集合 R {\displaystyle \mathbb {R} } は濃度が等しいので、この事実は N {\displaystyle \mathbb {N} } から R {\displaystyle \mathbb {R} } への全単射が存在しない事を含意する。 さて、仮に N {\displaystyle \mathbb {N} } から[0, 1]区間への全単射φが存在したとし、φ(i)をaiと書く事にする。すると[0, 1]区間の各元を a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } と番号づけする事ができた事になる。 aiを二進数展開したときの j {\displaystyle j} 桁目をai,jとし、biを¬ai,iとする。 そしてbを小数点展開が0.b1b2…となる実数とする。このとき、bは a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } のいずれとも異なる。実際iを任意に取るとき、aiのi桁目はai,iであるのに対し、bのi桁目は¬ai,iであるので、aiとbは異なる。 仮定より[0, 1]区間の全ての元は a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } と番号づけされているはずなのに、[0, 1]区間の元であるはずのbは a 1 , a 2 , ⋯ {\displaystyle a_{1},a_{2},\cdots } のいずれとも異なるので、矛盾。従って N {\displaystyle \mathbb {N} } から[0, 1]区間への全単射は存在しない。 なお、n桁に対応する元は 2 n {\displaystyle 2^{n}} 個存在するが、対角線論法においてはn桁に対して元の数をn個として議論していることには注意が必要である。 以上の論法は、行列A={ai,j}i,jに対して対角線論法の「行列による表現」を使ってベクトル{bi}={¬ai,i}がAのいずれの行とも異なる事を証明したものであると解釈できる。従って以上の論法は暗に対角線論法を使っている。
※この「自然数の集合と[0, 1]区間の濃度の違い」の解説は、「カントールの対角線論法」の解説の一部です。
「自然数の集合と[0, 1]区間の濃度の違い」を含む「カントールの対角線論法」の記事については、「カントールの対角線論法」の概要を参照ください。
- 自然数の集合と[0, 1]区間の濃度の違いのページへのリンク