カントールの対角線論法について質問です。

カントールの対角線論法について質問です。野矢茂樹著の「無限論の教室」によると、
x0 = 0.1111...
x1 = 0.1011...
x2 = 0.0111...
x3 = 0.1010...
...
のように 0 から 1 までの小数を２進数で列挙して、その対角線を取った 0.1010... の小数点以下の 0 と 1 を逆転させた x = 0.0101... が、列挙したはずの 0 から 1 までの小数のどれにも当てはまらないことから、それは矛盾である。したがって実数を自然数と 1 : 1 に対応させることはできない、としています。

以上は、もし実数が自然数と同じ濃度ならば、という仮定の下でのことなので、実数を x1, x2, x3, ... と連番で、つまり自然数の濃度で表したらどうなるのかということを考えています。しかしここでその仮定がないとき、何の仮定もないときに、0 から 1 までの実数を列挙せよと言われたら、やはり上に挙げた x1, x2, x3, ... が生まれると思います。するとやはり対角線論法により矛盾しますが、ここでは仮定がないので仮定を背理法の前提として棄却する訳にはいかず、その矛盾は何の前提もないパラドックスになってしまうように思われます。

私はどこかで間違っているのでしょうか？ ネット上ではこれについての言及は見つけられませんでした。どなたかご存知の方、教えていただければ幸いです。

質問者からの補足コメント

• yahoo! 知恵袋でも同じ質問をしたのですが、回答に適切に対応することができず、聞きたいことを聞きそびれてしまったので、こちらで質問させていただきました。

    補足日時：2023/11/07 04:45

• お礼ではなくこちらに書くべきでしたかね？ まだ慣れないもので…。
  
  回答ありがとうございます。
  私が知りたいのは、「実数が自然数と同じ濃度ならば」という仮定の下で対角線論法を使って、矛盾するよね、だから実数が自然数と同じ濃度ではない、とするところを、仮定なく実数を列挙したらどうなるのか、その場合も対角線論法を使って矛盾になってしまうのではないか、とうことなのですが。それは不可能だということでしょうか？

  No.1の回答に寄せられた補足コメントです。 補足日時：2023/11/07 07:07

• すみません、お礼欄の訂正です。
  × mtrajcp さんは、決して無限にはたどりつかないと思っているのか、無限への過程における有限のみがある思っているのか、どっちなのでしょう？
  
  ○ mtrajcp さんは、無限への過程によって無限にたどりつくと思っているのか、決して無限にはたどりつかず、無限への過程における有限のみがある思っているのか、どっちなのでしょう？

  No.37の回答に寄せられた補足コメントです。 補足日時：2023/11/09 14:04

• 

  すいません。No.43 へのお礼コメントの
  >次に No.35 の回答中の (0.2111… )₃ が列挙した列の中に現れないときについてですが、…
  の段落は、間違いです。No.35 へのお礼コメントで自分で超限順序数の必要性を導いたのでした。
  
  それを受けて、No.35 での 3進数による実数の列挙では、循環節 1... の後に循環節 2... が来るとき、 (0.111...1110222...)₃ のようにすれば、それは (0.111...1111)₃となって循環節 1... を列挙の中に出現させることができると思いました。

  No.43の回答に寄せられた補足コメントです。 補足日時：2023/11/10 07:24

• そろそろ質問を閉じさせていただきたいと思います。
  返信が追いつかなかった回答者の方を含め、付き合っていただきありがとうございます。最初は相手にされないんじゃないかと心配していたのですが、こんなに反響があるとは。ほとんど反対意見でしたけどね。色々やり取りしましたが、パラドックスになるのではという疑念はついに否定されず、疑念を深める結果になりましたが、私としてはそれもまた良しです。
  ではさようなら。

    補足日時：2023/11/13 12:09

No.43 回答者： stomachman 回答日時： 2023/11/10 01:16

No.35 へのコメントについて。

> 循環節が 2... にたどりつくまでの桁に 1 が無限にある

[1] "1"が無限に続いた「あと」に"2"が無限に続いている列、というものは構成できます。

例えば、自然数の普通の意味での大小の関係を"p＜q"と表す時、以下を満たす順序関係「p小q」を導入する：
(1) 偶数p, qについて、p小q とは、p＜q であることを表す。
(2) 奇数p, qについて、p小q とは、p＜q であることを表す。
(3) どの自然数nについても、0小n
(4) どの奇数pとどの偶数qについても、 p小q

そうすると「小」は全順序関係になり、だから自然数を「小」である順に並べた列
1, 3, 5, 7, ...... 2, 4, 6, 8, 10, ......
ができる。で、この列の各要素を、それが偶数なら"2"、奇数なら"1"に置き換えた列を作れば、「"1"が無限に続いたあとに"2"が無限に続いている列」ができる。
　この列の一つの要素を「●番目の要素」と指定するには、列の要素に超限順序数が対応していると考えればいいですね。すると、有限番目の要素は"1"であり、超限番目（ω番目以降）の要素は"2"である。ここまでは何も問題ありません。

[2] 有理数の小数表現は「ある有限の桁以降は、ある有限の長さを持つ循環節になっている小数」になることは、容易に証明できる。ですから、有理数をいくら並べたって、「循環節が 2... にたどりつくまでの桁に 1 が無限にある」なんてシロモノは現れません。つまり、有理数の小数表現に「超限番目の桁」なんてものは、そもそも存在しえない。

　ですから、「循環節が 2... にたどりつくまでの桁に 1 が無限にある」なんてことは、ご質問にある「規則的に並べて」作った小数（どれも有理数）の中には決して現れません。

　ついでに：

[3] 「超限番目の桁」を持つ列が「実数の小数表現」としてなら成立するか。言い換えれば、「相異なる実数x, yであって、小数表現の有限番目の桁が全て一致していて、超限番目（ω番目以降）の桁に違いがあるようなx, y」というものが考えられるのかどうか。

　デデキントの切断を使って実数を定義する話を思い出せば、実数xとは 「q ≦ xを満たす有理数全部の集合M(x)」に他ならないんでした。xの値は、M(x)と、有理数全体の集合からM(x)を除いた集合(補集合)G(x) によって「挟まれた」値として定義される。すなわち
　　m ≦ x ＜ g
となる m∈M(x)とg∈G(x) を選んで g - m を幾らでも小さくできる。それが実数ってことです。
　で、このmとgはどっちも有理数だから、それらの小数表現は「ある有限の桁以降は、ある有限の長さを持つ循環節になっている小数」になっている。有理数の小数表現に「超限番目の桁」なんてものはそもそもありません。
　なので、「有限番目の桁が全て一致している」のなら、それは同じ実数である。だから「有限番目の桁が全て一致しているような二つの相異なる実数」というものは存在できない。すなわち、「"1"が無限に続いたあとに"2"が無限に続いている」というのは、実数の小数表現になっていない。つまり、実数の小数表現に「超限番目の桁」なんてものは、そもそも存在しえない。

　かくて、いろんな実数を並べてみたって、「循環節が 2... にたどりつくまでの桁に 1 が無限にある」ってことは生じない。

この回答へのお礼

再び丁寧な回答、ありがとうございます。
超限順序数のことは知らなかったので、Wikipedia を頼りに回答を読んでいます。
私の直感として、2進数では実数の列挙の中に対角線の数が現れるが、3進数にすると現れなくなるというのが、どうも腑に落ちなくて、実質同じもののはずなのに、という思いで回答を読ませていただきました。

それで、まず
>ですから、「循環節が 2... にたどりつくまでの桁に 1 が無限にある」
>なんてことは、ご質問にある「規則的に並べて」作った小数（どれも
>有理数）の中には決して現れません。
についてですが、これは私の意見と違うようですね。
2進数での実数の列挙の場合、n 番目の実数の小数点以下の桁数が stomachman さんの言うように log₂n 以下であるなら、n が無限大のとき、log₂n も無限大に発散するので、その無限大番目の実数は小数点以下無限桁の小数となり、そのすべての桁それぞれが 0 か 1 かである組み合わせが列挙されるので、これをもって有理数でなく実数が列挙されていると考えているのですが。おかしいでしょうか？

次に No.35 の回答中の (0.2111… )₃ が列挙した列の中に現れないときについてですが、これを No.35 のお礼コメントで循環節 1... のあとに循環節 2... が来る数と考えていましたが、よく考えると対角線を取って循環節 2... となった、その 2 を 1 に置き換えているだけなので、循環節 1... の後に循環節 2... は来ない数だと気付きました。これは間違っていないですよね？ そのせいで超限順序数を使った説明をさせてしまい、すみません。

以上を総合すると、私の考えでは、3進数においても2進数と同様に 0 から 1 までの実数を列挙でき、その対角線上の数を 2 → 1, 1 → 0, 0 → 2 と置き換えた数は、0 から 1 までの数のリストのどれとも一致しない。実数を列挙したはずなのにそのどれとも違う数ができるとなって、質問文で述べたパラドックスに陥るとなる・・・これでいいと思われますか？

お礼日時：2023/11/10 04:37

No.42 回答者： Tacosan 回答日時： 2023/11/09 22:22

対角線論法を一般的に書くと

任意の集合 A に対して, A と 2^A との間に全単射は存在しない
で, 証明としては
全単射 f: A → 2^A が存在すると仮定したときに
X = { a ∈ A | a ∉ f(a) }
という A の部分集合を考えると
f(x) = X となる x ∈ A は存在しない
で終わり.

ねんのためほそくすると自然数の集合 N と実数の集合 R とのあいだには
2^N と R とは濃度が等しい (つまり全単射が存在する)
という関係がある.

No.41 回答者： mtrajcp 回答日時： 2023/11/09 17:07

「

対角線論法は無限にたどりつくと考えなければ成り立ちません。
」
は間違いです
「
対角線論法は無限にある実数のリストが
「すべて」列挙されているとした上でのこと
」ではありません

「
無限にある実数のリストが
「すべて」列挙されているとした
」
というのは
対角線論法の
前提ではなく
対角線論法の
仮定なのです

対角線論法では
「
無限にある実数のリストが
「すべて」列挙されている
」
と仮定すると
矛盾が起きるので
「
無限にある実数のリストが
「すべて」は列挙されてはいない
」
という結論が出るのです
有限桁の小数有限小数は無限にあるのだから
「
どこまで行っても実数のリストを有限個しか列挙できない
」
は間違いです

No.40 回答者： mtrajcp 回答日時： 2023/11/09 16:54

全然わかってない

無限桁の自然数は存在しないのだから
無限への過程などない
無限にたどりつかない

しいていえば

無限(桁)にはたどりつかず、
無限(∞)への過程における有限(桁)のみが(無限に)ある

----------------------
決して無限桁にはたどりつかないのです、
有限桁の
自然数はどこまでも無限に大きくなるけれども
有限桁の自然数なのです
無限桁にはならないのです

1は有限桁の自然数である

ある自然数
n
が有限桁ならば
n+1
も有限桁だから

すべての自然数nは有限桁である

と数学的帰納法によって
すべての自然数nは有限桁である
ことは証明されているのです

だから
それを小数点.を中心に反転しても
小数の桁数は自然数の桁数と同じなのだから
決して無限桁にはたどりつかないのです、
有限桁の
小数の最小位はどこまでも無限に小さくなるけれども
有限桁の小数なのです
無限桁の無限小数にはならないのです

すべての自然数nは有限桁である
から
それを小数点.を中心に反転した
小数は有限桁なのです

No.39 回答者： mtrajcp 回答日時： 2023/11/09 16:01

無限桁の自然数は存在しないのだから

決して無限桁にはたどりつかないのです、
有限桁の
自然数はどこまでも無限に大きくなるけれども
有限桁の自然数なのです
無限桁にはならないのです

1は有限桁の自然数である

ある自然数
n
が有限桁ならば
n+1
も有限桁だから

すべての自然数nは有限桁である

と数学的帰納法によって
すべての自然数nは有限桁である
ことは証明されているのです

だから
それを小数点.を中心に反転しても
小数の桁数は自然数の桁数と同じなのだから
決して無限桁にはたどりつかないのです、
有限桁の
小数の最小位はどこまでも無限に小さくなるけれども
有限桁の小数なのです
無限桁の無限小数にはならないのです

すべての自然数nは有限桁である
から
それを小数点.を中心に反転した
小数は有限桁なのです

この回答へのお礼

その言い分は分かります。
私は mtrajcp さんが、無限への過程によって無限にたどりつくと思っているのか、それとも決して無限にはたどりつかず、無限への過程における有限のみがある思っているのか、どちらなのかを聞きたかったのですが。これについてはいかがですか？

お礼日時：2023/11/09 16:33

No.38 回答者： syotao 回答日時： 2023/11/09 16:01

<無限への過程によって無限にたどりつくと思っているのか、決して無限にはたどりつかず、無限への過程における有限のみがあると思っているのか、>

数学的に言うと、後者が今の数学の考えでしょう。たとえば
ｎを1以上の整数としたとき、集合S=｛1/ｎ｜ｎ≧1｝において
ｎ→∞　のとき1/ｎ→0　だけれども0がSに含まれるとは
数学ではいいません。

この回答へのお礼

回答ありがとうございます。
そうなんですよね。しかし一方で対角線論法は無限にたどりつくと考えなければ成り立ちません。対角線論法は無限にある実数のリストが「すべて」列挙されているとした上でのことですので、どこまで行っても実数のリストを有限個しか列挙できないのならば、対角線論法は成り立たないことになってしまいます。これは数学の一貫性の欠如だと思います。

お礼日時：2023/11/09 16:19

No.37 回答者： mtrajcp 回答日時： 2023/11/09 09:39

無限桁の自然数は存在しないけれども

有限桁の自然数は無限にあるのです
「桁」を省略しないで下さい

無限ではなく
無限桁の自然数は存在しないのだから
無限桁の小数
にたどり着かないといっているのです
実数のリストを有限個しか列挙できないとはいっていません

無限個の有限小数のリストは列挙できるのです

0→0.0
1→0.1
10→0.01
11→0.11
100→0.001
101→0.101
110→0.011
111→0.111
…
は
すべて無限個のすべての有限小数のリストです
その中には無限小数は含まれないけれども

この回答へのお礼

？？
mtrajcp さんは、決して無限にはたどりつかないと思っているのか、無限への過程における有限のみがある思っているのか、どっちなのでしょう？

お礼日時：2023/11/09 12:37

No.36 回答者： 一票の格差に反対 回答日時： 2023/11/09 07:50

さすが、無限の話はコメントが伸びるな。

No.35 回答者： stomachman 回答日時： 2023/11/09 06:59

No.4ですが、横入り失礼。

　ハナから並べ方を決めちゃっうんじゃ意味がないんですよ。カントールの対角線論法のミソは、「どんな並べ方をしたってムリだよ」と証明する、という所にあるんですから。

> 0.0
> 0.1
> 0.01
> 0.11
> 0.001
> 0.011
> 0.101
> 0.111
> ...
> のように規則的に並べていく

実際にこの列について考えてみますと：

[1] この列のn番目にある実数は、小数点以下の桁数が(log₂n)以下です。すなわち、この列に現れる実数はどれも小数点以下が有限桁である。小数点以下が有限桁ってことは有理数だということであり、だからこれは有理数ばかりでできた列です。もちろん、実数全部の列挙には程遠い。

[2] 試しに、この列の対角線をなぞって"0"と"1"を入れ替えてみれば、できるのは
(0.00111111111…)₂ = (0.01)₂ = (1/4)₁₀
であり、これは列に現れている。あれあれ。

[3] いやいや、対角線論法の処方に従えば、小数点以下が有限桁の場合には最後の"1"を"01111…"で置き換えて無限小数にしておかなくては。それをやると
0.0111111111…
0.00111111111…
0.10111111111…
0.000111111111…
0.010111111111…
0.100111111111…
0.110111111111…
...
ということになる。で、対角線をなぞって"0"と"1"を入れ替えてできるのは、
(0.110000000…)₂ = (0.10111111111…)₂ = (3/4)₁₀
であり、これは列に現れている。あれあれあれ。

[4] しかし、例えば3進法にすれば、もうちょっと「対角線論法っぽい」話になります。
0.1
0.2
0.01
0.11
0.21
0.02
0.12
0.22
0,001
0.101
0.201
…
と並べ、これを無限小数による表現で
0.0222222222…
0.1222222222…
0.00222222222…
0.10222222222…
0.20222222222…
0.01222222222…
0.11222222222…
0.21222222222…
0,000222222222…
0.100222222222…
0.200222222222…
…
にする。そして、対角線にそって、"2"は"1"に、"1"は"0"に、"0"は"2"に置き換えれば
(0.2111… )₃ = (12/20)₃ = (5/6)₁₀
が得られて、確かにこれは列に現れない。なぜなら循環節が"1…"になるものは列に含まれていないから。つまり、「この並べ方じゃ、0と1の間の有理数全部を列挙することもできない」と証明できたわけです。

[5] いや、わざわざ対角線なんか考えなくたって、[3]でも[4]でも、循環節の長さが2以上の循環小数（例えば0.01010101…）が列に出てこないのは明らかですから、「この並べ方じゃ、0と1の間の（実数全部どころか）有理数全部を列挙することもできない」と分かりますけどね。

ま、「どんな並べ方をしたってムリだよ」と言いたいのに、「ある特定の並べ方では、実数を列挙できない」と分かったからって、そんなもんしょうがないわけです。

この回答へのお礼

丁寧な回答ありがとうございます。
[4] について、循環節が 1... になる3進数は確かに列に現れませんが、循環節が 2... にたどりつくまでの桁に 1 が無限にある3進数は考えられると思います。

どうしてこんなことを言うのかというと、小数点以下の各桁が 0, 1, 2 である組み合わせの数を列挙したものが 0 から 1 までの3進数の列挙となるので、その組み合わせに収まる数だけを考えれば良いと思ったからです。そこに循環節が 1 である3進数が「ある」と考えることができるのではないか、と思ったのです。3進数の列挙は小数点以下無限桁まで対象にするので。

ではその循環節 1... の後に来る最後の循環節 2... はどこへ行ったのか？となると思いますが、そこは無限の不思議なところで、１つの数が２つの循環節を持つという異様なこととなっているので、どう捉えたら良いのか私にも分かりません。

しかしそう考えた結果、0 と 1 の間の有理数を含めた実数全体を列挙できる可能性は、まだ残るのではないかと思います。

お礼日時：2023/11/09 11:54

No.34 回答者： Tacosan 回答日時： 2023/11/08 21:18

「列挙する」というのが「自然数と 1対1 に対応させる」という意味であるなら, それこそ対角線論法によって「できない」と否定されている.

「列挙する」がそういう意味でない, というなら＊定義＊してくれ. ちなみに
x0 = 0.1111...
x1 = 0.1011...
x2 = 0.0111...
...
のようにただ書くことを「定義」とはいわない.

この回答へのお礼

回答ありがとうございます。実数の列挙の定義ですが、0 から 1 までの実数について言えば、
0.0
0.1
0.01
0.11
0.001
0.011
0.101
0.111
...
のように規則的に並べていくことを無限に続けることをもって、定義としたいと思います。これはコンピュータでプログラムすることもできます（というかそのプログラムを実際作りました）。これをもって定義とすることで納得いただけますか？

お礼日時：2023/11/08 21:33