« アキレス腱痛&ロンドン・マラソン&一口つぶやき♪ | トップページ | やはりマラソンに給水は「不要」だったか! »

カントールの対角線論法と集合~無限、濃度、可付番(可算)

雨で走れないから、手頃な数学ネタでも見つけて記事を書くことに決定。

ハイレベルだけど、差し当たりの記事なら簡単に書けるものとして思い

ついたのが、有名な天才数学者・カントール(Georg Cantor)の「対角線

論法」(diagonal argument)だ。

          

名前だけは先にどこかで聞いてたけど、内容を知ったのは、高校数学

の定番参考書「モノグラフ」シリーズ(科学振興社)の24巻『公式集』だっ

た。お馴染みの矢野健太郎が監修を務めたこの本の終盤(p.307-309)

に、集合の「濃度」の話が簡単に書いてあって、話の最後に対角線論法

も出てたのだ。

             

まず、集合の濃度と「可付番集合」(or 可算集合)について、簡単にまと

めとこう。2つの集合の要素の間に、1対1の対応(or 全単射)が存在す

る時、それらの集合は「対等」であり、濃度が等しいという。さらに、自然

数全体の集合N={1,2,3,・・・}と対等な集合を、可付番集合とか

集合という(countable set)。つまり、1番、2番、3番と、自然数の番号

を付けられるということだ。

                         

100427a

 たとえば偶数全体の集合

 は、自然数全体の集合よ

 り小さいはずだけど、左図

 のように1対1の対応づけ

 が出来る。したがって、2

 つの集合は対等で濃度は

 等しく、偶数全体の集合は

 可付番ということにもある。

    

 他に簡単なものだと、整数

全体の集合Z={・・・,-2,-1,0,1,2,・・・}も可付番集合と言える。

要素を、0,1,-1,2,-2,・・・と並べ変えて、先頭から順に1番、2番

としていけばよい。

          

         ☆          ☆          ☆

こうした話に続いて、可付番でない集合(=非可算集合)の代表例として

出て来るのが、実数全体の集合Rだ。その証明には、まずRの一部分

(=部分集合)である、0~1の実数全体の集合でさえ、可付番でない

とを示す。ましてや、実数全体は可付番でないという流れだ。0~1とは、

両端の0と1を含まない集合だから、区間(0,1)に含まれる実数全体

の集合とも言える(両端は丸カッコ)。

       

さて、0~1の実数の集合が可付番でないことを証明するには、可付番

だと仮定して、矛盾を導けばよい(背理法 or 帰謬法)。今、仮にその集

合が可付番だとすると、要素を上から1番、2番と並べることが出来るは

ずだ。その際、0~1の要素はすべて、「0.・・・」という形の無限小数

表しておく。例えば1/4、つまり0.25なら、0.24999・・・とする。

     

100427b

 ここで、「0.・・・」と

 いう形の無限小数

 で表される、とい

 う数を考えてみる。

 ただし a は、小数

 第一位が1番目の

 小数の数字(図の

 2)と異なり、小数

 第二位が2番目の

小数の数字(図の9)と異なり、小数第三位が3番目の小数の数字(図の

1)と異なり・・・・、という条件をみたすものとする。一般に a は、小数第

n 位の数字が、n番目の小数と異なる

      

この時は、1番、2番の順に並べておいた各小数と比べると、左上か

ら右下へと対角線上に続く数字の箇所だけ異なってることになる。これ

が「対角線論法」という名前の由来だ。

                 

この時、a は0~1の間の実数であるにも関わらず、何番目の小数とも

一致しないことになる。つまり、a には自然数(の番号)が対応してない。

これは矛盾である。したがって、0~1の実数全体が可付番であるという

仮定は誤りであり、実は可付番ではない。   Q.E.D.証明終了。。

         

     

2点補足しておこう。まず、なぜ0.25=0.24999・・・なのかについて。

0.24999・・・=x とおくと、2.49999・・・= 10 x 。

よって、10 x - x = 2.25。つまり 9 x = 2.25だから、x = 0.25。

       

また、a に自然数が対応してないという点は、新たな背理法を導入して

示すことも出来る。つまり、 a に自然数 n を対応づけることが出来たと

仮定すると、a は上から n 番目の小数と等しいことになる。しかし、a と

n 番目の小数とは、小数第 n 位が異なってるはず。これは矛盾だから、

仮定は誤り。したがって、a に自然数 n を対応づけることは出来ない。

      

       ☆          ☆          ☆

こうして、自然数全体の集合Nの濃度(ℵ ₀: アレフゼロ)と、0~1の実数

全体の濃度とは、異なることになる。当然、実数全体の集合Rも可付番

ではなく、Nよりも濃度が大きい(=無限の度合いが高い)。より正確に

は、Rの一部分(真部分集合)である有理数全体の集合が可付番である

ことを示して、そこにさらに無理数全体が加わったのがRだから、Rの方

がNよりも濃度が大きい(or 高い)という話になるが、省略しておく。更に

厳密な証明のやり方もあるはずだけど、まだ分からない。

       

なお、「0~1の実数全体」と実数全体とは、等しい濃度をもつ。なぜなら、

関数 y = e^x / (1+e^x) によって、1対1の対応づけが可能だから

である(e^x とは e の x 乗を表す書き方)。その実数全体の集合の濃

度は ℵ (アレフ)と呼ばれる。。

        

        

さて、ここまでなら、あちこちに似たような話が書いてあることだろう。で

も、私は面白いことを思いついた。どうも対角線論法というのは、騙され

たような気がするから、その違和感を具体的な形にする、奇妙な証明

考えたのだ。そこで対角線論法を用いて示されるのは、「自然数全体の

集合N自体は、可付番ではない」という、明らかにおかしい命題だ♪

     

100427c

 今、Nが可付番だと

 仮定して、上から1

 番、2番、・・・と並べ

 てみる。ただし、

 自然数の左には無

 限に0を並べておく。

 そして、n 番目の自

 然数とは n ケタ目

                                 が異なってる自然

数 b を考えてみるのだ。すると、0~1の実数全体の時と同様に、bを

自然数と対応づけることは出来ない(何番目とも言えない)。これは矛

盾である。したがって、自然数全体は可付番ではない。。

       

ちなみに、並べ方は、上から小さい順に、・・・001、・・・002、・・・003

となっていても構わない。左上から右下という本来の向きとは反対に、

右上から左下に向かう数字の列に注目した対角線論法によって、自然

数と自然数が1対1対応でないという妙な結論が証明できてしまうのだ。

        

           

私は念のため、数学が専門の友人に電話で話してみた。すると、左側

に0を並べるというのが気になるけど、なぜいけないのかは差し当たり

分からない、という応答だった。もちろん、私も同じなのだ。何かマズイ

事が起きそうな気がするし、自然数の定義や表記の問題もある。ただ、

差し当たり、ここがこうゆう理由でおかしい、と指摘することが出来ない。

     

やはり、無限の問題は厄介で奇妙ということか♪ 対角線論法は、他の

色んな話とも関わるテクニックだから、いずれまた扱うと思う。

とりあえず、今日の所はこの辺で。。☆彡  

    

 

     ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・・

P.S.上で提示した奇妙な話は、少なくとも現代数学の一つの体系にお

    いては鮮やかに解決できることが分かった。

    下のリンクの後続記事(特にP.S.2)を参照。

          

cf.デデキントの「切断」による実数の構成~対角線論法2

|

« アキレス腱痛&ロンドン・マラソン&一口つぶやき♪ | トップページ | やはりマラソンに給水は「不要」だったか! »

数学」カテゴリの記事

コメント

そうやって作られたbは自然数ではありません。

投稿: wd0 | 2010年5月27日 (木) 18時32分

> wd0 さん
   
はじめまして。
もちろん、そうでしょうね。
    
その根拠となるテキストとか、論理的理由を
求めて、じっくり歩むつもりです。
実数の場合との違い、あるいは小学校以来の
自然数の扱いとの整合性も問題となります。
   
ペアノ、デデキント、フレーゲはもちろん、
ユークリッドにも遡って、記事を書きながら
少しずつ考えをまとめてる最中です。
小学校の教科書も読み返して楽しんでます ☆彡
    
   
P.S.現代数学の一つの体系においては、
    bが自然数ではないことが分かりました。
    上のリンクの続編記事に書いてます。
    ただし、これで全て解決した訳ではありません。

投稿: テンメイ | 2010年5月29日 (土) 03時02分

始めまして、失礼いたします。

カントールの対角線論法の意味は、点を集めて線になるのか、という事だと考えました。
1と0の間に点を無数に増やして行った場合、点が有限個であれば線にはなりません。
しかし極限に於いては線になる、というのが、無限小数や実数の稠密性の意味ではないでしょうか。
この考えは、極限でなければ線にならないという点が対角線論法の主張と一致します。
このような前提に立って、実数と自然数を一対一対応させる方法を考えました。
まず小数点以下が一桁の小数を順番に並べます。
次に二桁、次に三桁。…
この数の列は有限の範囲では有限小数しか含みませんが、極限に於いては無限小数も全て含むはずです。
この場合、対角線論法で作った新しい小数は、有限の範囲では新しい数ですが、極限に於いては、列にある数の一つと無限に近い(無限桁目が異なる)数になります。
つまり有限の範囲では一対一対応は実現しませんが、極限に於いては実現しています。
極限を考えなければ、点を集めても線にはならないという結果は同じですが、カントールの論法の理屈は否定してみました。
数学好きのド素人の発想ですが、いかがでしょうか。

ついでに言うと加算濃度(デジタル)と連続体濃度(アナログ)以外の濃度って実在するのかなって疑問に感じております。

投稿: しまないちゃー | 2014年4月24日 (木) 15時41分

> しまないちゃー さん
  
はじめまして。コメントどうもです。
   
「島ないちゃー」、つまり沖縄に移住した
本土の方ですかね。初耳の言葉でした。
    
   
さて、まず稠密と無限について。
厳密さにこだわらず、簡単に言うと、
稠密なら無限ですが、無限なら稠密とは言えません。
つまり、稠密の方が強い情報ということですね。
  
無限小数や実数の稠密性は、イメージ的に、
極限において線になることに近いのは確かです。
ただ、線にならない稠密もあるので注意が必要です。
  
    
それはさておき、「カントールの論法の理屈は否定」
という本題のお話。
面白い発想だとは思いますが、否定にはなっていません。
   
まず、無限小数をすべて含むのなら、
その部分を考えるだけで対角線論法が成立します。
新たに作る無限小数は、元々の無限小数すべてと異なるし、
有限小数すべてとも異なってるので。
つまり、新たに作った無限小数が元の順列からハミ出すわけです。
   
これで背理法が成立。
可算と仮定すると矛盾するから、可算ではない。
     
また、「列にある数の一つと無限に近い」というのは
単純な誤解です。
新たに作った数と、元々あった「個々の数」との比較では、
ある有限の数以上の差になってます。
数を具体的に書けば、すぐ分かること。
何ケタ目が違ってるのかは決まってるので、
単に違ってるケタ数が大きくなるとか、
差が小さくなるというだけです。
     
そうした事なら、元々の対角線論法でも同じことで、
論法の効力には関係ありません。
「無限に近い」とはどうゆうことなのか、
解析学の基本であるε-δ論法とか考えてみてください。
   
さらに、おそらくトリビアル(些細)なことでしょうが、
その並べ方だと、数が重複してます。
例えば、0.1と0.0999999・・・が
ダブって並べられてることになります。
元々の対角線論法では、重複はありません。
      
  
一方、別の話として、「加算」と言うより「可算」濃度と
連続体濃度以外の濃度は、いくらでもあります。
一般的な話題には、ほとんどなりませんけどね。
      
有限集合の濃度とか、無限直積集合の濃度を考えるのです。
いくらでもあるからこそ、濃度と濃度の演算があります。
   
適当な本かサイトで調べてみてください。。

投稿: テンメイ | 2014年4月26日 (土) 00時18分

テンメイ さん

ご丁寧な お返事に大変感謝しております。

しまないちゃーは お察しの通り、島に住み着いた内地人の意味です。

リスト状に一個一個一列に並べれば自然数と一対一対応すると思い込んでいた所に落とし穴がありました。

有限小数を全て並べた時点で既に可算無限なので、そこに並んでいない無限小数を後から並べたら一対一対応していませんね。

また、無限の列が無限に出来てしまうので、最初の列に割り込ませる事も出来ません。

これを厳密に言ったのが対角線論法なのでしょうね。

教えて頂いた情報を参考にしてもっときちんと勉強してみようと思います。

どうもありがとうございました。

投稿: しまないちゃー | 2014年4月26日 (土) 14時38分

> しまないちゃー さん
  
こんばんは。ご丁寧に、どうもです。  
やはり沖縄に移住した方ですか。
私も4回、旅行してます。いい所ですよね。
  
対角線論法は、まだ奥が深い話なので、
私ももっと勉強して、第3弾の記事を書くつもりです。
カントールの原論文も調べてみたいと思ってます。
    
数学は難しいけど、楽しいですね。
お互い、頑張りましょう。。

投稿: テンメイ | 2014年4月27日 (日) 20時28分

コメントを書く



(ウェブ上には掲載しません)


コメントは記事投稿者が公開するまで表示されません。



« アキレス腱痛&ロンドン・マラソン&一口つぶやき♪ | トップページ | やはりマラソンに給水は「不要」だったか! »