実数の集合が非可算であることの証明

質問

対角線論法を用いて、実数の集合と自然数の集合が対等でないことを示せば、”実数の集合が非可算であること”は示せているのでしょうか？別の証明方法があるなら教えていただきたいです。
よろしくお願いします。

回答No.5

boiseweb

何をもって「対角線論法」と称するかという問題がありますね．

自然数の集合のベキ集合 P(N) にしろ，実数の集合 R にしろ，それが可算でないことを証明しようとしたら，何らかの形で対角線論法に訴える必要があります．「対角線論法によらない証明」というのはたぶん見かけの問題だけで，本質的に対角線論法を回避した証明はないと思います．

多くの数学書では，実数の10進無限小数表示を使った対角線論法で R が可算でないことを証明して，「ここで使った論法は対角線論法と呼ばれる」などと説明していると思います．
しかし，10進無限小数表示を使うのは，あくまで「対角線論法を使った証明の，ひとつの例」でしかありません．「対角線論法といえば無限小数表示を使うもの」と考えているとしたら，それは，ひどく狭い解釈です．
理論計算機科学における停止問題(halting problem)の決定不可能性の証明や，数学基礎論におけるゲーデルの不完全性定理の証明で使われる手法も「対角線論法」と呼ばれますが，それらの証明には実数の無限小数表示は出てきません．

#4 さんの回答では P(N) が可算でないことを経由して証明していますが，P(A) が A より濃度大であること（カントールの定理）の証明は，対角線論法そのものです．
また，#3 さんの回答にある区間縮小法を使った証明も，広い意味で対角線論法と呼ぶべきものです．

====
なお，重箱の隅をつつくようで恐縮ですが，#3，#4 の証明について，#3 は2分割でなく3分割（最小番号の実数が第1区間に属せば第3区間を選択，さもなくば第1区間を選択），#4 の P(N) の R への埋め込みは2進小数でなく3進小数を使うほうが，テクニカルな問題を回避できて，初学者向けの説明としては無難かと思います．

藤田博司「魅了する無限」（技術評論社）

では，「3分割」の区間縮小法を使った証明（これも本質的には対角線論法）がていねいに書かれています．

嘉田勝「論理と集合から始める数学の基礎」（日本評論社）

では，「P(N) は可算でない」「P(N) から R への単射が存在する」の2段で証明していますが，前者の証明の方法について「対角線論法と呼ばれます」と明言しています（ちなみに，後者の証明では3進小数を使ってカントール集合に埋め込んでいます）．

回答No.4

grothendieck

”実数の集合が非可算であること”は次のような証明も知られています。カントールは任意の集合Aとそのベキ集合P(A)の間には1対1対応は存在しないことを示しました。証明は例えば
　メアリー・タイルズ著三浦雅弘訳「集合論の哲学」産業図書、p.71
区間[0,1]に含まれる実数の2進少数展開を考えれば自然数Nの
ベキ集合P(N)と[0,1]に含まれる実数の間に1対1対応があることはすぐに分かるので、実数の集合は非可算であることになります。

回答No.3

funoe

（命題）
閉区間の列［a1,b1］⊃[a2,b2]⊃・・・⊃[an,bn]⊃・・・
があって、bn-an→０のとき、各区間に共通に含まれる実数が唯一つ存在する。

を前提にします。

区間[0,1]の実数にすべて付番できたとします。
この区間を半分に分けた[0、1/2]、[1/2,1]のうち、最小の番号が付番された
実数を含まない方を選択します。
（このとき選択された区間には1番が含まれないので最小のものは２番以上です）
選ばれた区間を半分に分け、両方の区間の中で最小の番号が付番された実数を含まない方を選択します。
（このとき選択された区間の最小のものは３番以上です）
選ばれた区間を半分に分け、両方の区間の中で最小の番号が付番された実数を含まない方を選択します。
（このとき選択された区間の最小のものは４番以上です）
この操作を繰り返したとき得られる区間縮小列は、冒頭の条件を満たすので
各区間に含まれる実数が1個決まります。
その実数に付番された番号がＮとすると、
上記の操作（区間を半分にして新たな区間を選択する操作）のＮ＋１回目
で選択された区間に含まれる最小のものがＮ＋１であることに反します。

回答No.2

grothendieck

カントールは最初1874年にこれを区間縮小法で証明し、後に対角線論法で証明したとされています。

参考URL：

http://www.teachersparadise.com/ency/ja/wikipedia/a/a_/a_a_a_a_a_a_a_e_c_e_.html

回答No.1

rinkun

可算でなければ非可算です。自然数(可算無限)と対等でなければ有限か非可算ですが、有限でないのは対角線論法以前に明らかでしょう。
別証明は知りません。おそらく一般に知られていないと思います。