非可算無限とは、自然数の番号を使ってすべての要素を列挙することができない無限です。代表例は実数の集合で、0と1の間だけに限っても、自然数全体より大きな濃度を持ちます。
無限が二種類以上ある
自然数も実数も無限にありますが、単に「終わりがない」という性質だけでは大きさを比較できません。集合論では、一対一対応が作れるかどうかで比較します。
自然数と偶数は対応できます。一方、自然数と0から1までの実数の間には、すべてを尽くす対応を作れません。非可算とは、いまの並べ方が下手だったという指摘ではなく、どんな列挙でも成功しないという主張です。
対角線論法の考え方
0と1の間の実数を全部リストにした、と仮定します。1行目の小数第1位、2行目の第2位、3行目の第3位、…に注目し、それぞれと違う桁を持つ新しい小数を作ります。
例えば、注目した桁が1なら2に、それ以外なら1に置き換えます。できた小数は、n行目の数と少なくとも小数第n位で異なります。したがって、どの行にもありません。すべて並べたという仮定に反するため、完全な列挙はできないと分かります。
小数の二通りの表し方を避ける
0.4999…と0.5000…のように、同じ数に複数の小数表現がある場合があります。上の作り方で新しい桁を1か2に限るのは、このような末尾が9または0で続く曖昧さを避けるためです。証明では「文字列が違う」だけでなく「数として違う」ことを確かめます。
これは、無限に長い計算を実際に完了させる手順ではありません。どんなリストを渡されても、そのリストにない数を定義できるという論証です。
「密集している」とは違う
有理数も数直線上に密にありますが、可算です。非可算かどうかは、見た目の密度や小数の桁数だけでは決まりません。有理数にも0.333…のような無限小数があります。
有限のコンピューターに保存できる文字列は、長さ順に並べられます。そのため「画面に表示できる小数をどんどん作る」ことでは実数全体を尽くせません。日常の数字の扱いを超えるところに、この用語の面白さがあります。