可算無限集合のベキ乗が可算無限でないことを対角線論法で証明する。

質問

http://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%B3%E3%83%88%E3%83%BC%E3%83%AB%E3%81%AE%E5%AF%BE%E8%A7%92%E7%B7%9A%E8%AB%96%E6%B3%95

をみているのですが、
わかりません。

証明
背理法による。全単射 ψ: X → 2^X が存在したとしよう。X の部分集合 A を

だいたい可算無限の意味がよくわかりません。
お願いします。

回答No.3

grothendieck · ベストアンサー

かりに0と1の間のすべての数が、
　１：0.123455343……
　２：0.2434293335……
　３：0.746943489……
　４：0.34235255……
　：
　：

のように番号付けて並べられたとします。しかしこのリストの中にない数を必ず構成することができます。上のリストの中のn番目の数の小数第n桁の数字を取り出すと、
　１：1
　２：4
　３：6
　４：3
　：
　：
となります。そこで第n桁の数字がこれとは異なるように、例えば１多い数字で置き換えて
　0.2574……
という数を考えると、これは上のリストの中の数のどれとも異なることになります。これが「今最後に作った実数は、それぞれ小数点以下第ｎ位の数字が番号ｎの実数とは異なっている。ということは、∞番まで自然数を振ったとしても、最低こうやって作った実数はもれていることになる。」ということです。

お礼

ありがとうございます。とてもわかりやすかったです。

回答No.2

cirrhata

野矢茂樹さんが『無限論の教室』という本を出していらっしゃいます。加算無限の意味から対角線論法まで、言葉で分かりやすく解説されています。数式による厳密な証明とは別のアプローチで取り敢えず全体的な意味を把握するというのも悪くないかもしれません。(ただ、数学ではなく数学の哲学になってしまうかもしれませんが)

お礼

ありがとうございます。

回答No.1

grothendieck

可算無限集合というのは、自然数の集合との間に全単射が存在するような集合です。
全単射 ψ: X → 2^X が存在したとします。X の部分集合 A をa∈Xに対して、
　a∈A　if a ∈/ ψ(a)　
　a∈/ A　if a ∈ψ(a)

で定義します。ここで∈/は∈の否定を表わすものとします。すると、A ∈ 2^X であって、ψ は全射だから、ある x に対して A = ψ(x) とならなければならないことになります。そこでx ∈ ψ(x) とすると
x ∈ A。ところがAはx∈ψ(x)のときx∈/ Aとなるように構成されていたのだからこれは矛盾。同様にx ∈/ ψ(x)としても矛盾が生じるから全単射は存在しないことになります。

補足

ありがとうございます。
ちょっと対角線論法をよく理解してなくて、

http://www.geocities.co.jp/WallStreet/1356/kuru/EVILMATH.html
を読んでいるのですが、
そこの、
「今最後に作った実数は、それぞれ小数点以下第ｎ位の数字が番号ｎの実数とは異なっている。ということはだ、∞番まで自然数を振ったとしても、最低こうやって作った実数はもれていることになる。というわけで、どうやっても「もれなく番号がふれない」、実数の方があまる、ということは、自然数より実数の方が多い（濃い）訳だよ。
」というところがわかりません。
特に、「今最後に作った実数は、それぞれ小数点以下第ｎ位の数字が番号ｎの実数とは異なっている。ということはだ、∞番まで自然数を振ったとしても、最低こうやって作った実数はもれていることになる。」のところです。
お願いします。