無限集合の濃度とは? 写像の全単射、可算無限、カントールの対角線論法

どうも、木村(@kimu3_slime)です。

自然数の集合\(\mathbb{N}\)と実数の集合\(\mathbb{R}\)は、どちらも要素を無限に持つ集合(無限集合)です。

参考:ガリレオのパラドックスとヒルベルトの無限ホテルから感じる、無限集合の性質

これらの無限集合は、どのくらい「多い」のでしょうか。無限は無限だ……と考えたら、話が終わってしまいます。

その「無限の多さ」を比べるための考え方が、今回紹介する「濃度」です。

じつは、実数の集合の濃度の方が、自然数の集合の濃度より大きいです。つまり、実数の方が自然数より「多い」のです。これを証明するときに使う、カントールの対角線論法も紹介します。

 



濃度とは何か、有限集合の場合

集合の要素の個数を一般化するのが、濃度の考え方です。

ものを数えずに、大小を考えるためにはどうすればいいか? そう、比較すればいいのです。

まずは有限集合の場合を考えましょう。(いきなり無限を考えるのは難しい)

 

\(A=\{1,2,3,4,5\},B=\{1,5,7\},C=\{a,b,c,d,e\}\)とします。

\(A,C\)の要素の個数は同じく5つ、\(B\)はそれより少ない3つですね。

数えずに要素の多さを比較するためには……対応関係を作ってみればいいのです。

図に示したように、要素の個数が同じ\(A,C\)は、要素に一対一の対応関係を作れます。

一方で、\(A,B\)にはどうやっても一対一の対応関係が作れません。必ず、\(A\)の要素の中には関係性を作れないものが2つ存在しますね。

この「どのような対応関係を作れるか」が、濃度の考え方を固めるヒントとなります。

 

写像とは、全単射とは

数学では、さきほど図示したような集合の要素同士の対応関係を写像(mapping)といいます。

図の左側は、次によって定まる写像\(f:C\to A\)です。\(f(a)=1,f(b)=2,f(c)=3,f(d)=4,f(e)=5\)。

これはすべての\(C\)の要素をただ一つの\(A\)の要素に写しています。写像は、すべてのインプットに対して結果を返さなければならず、また行き先がない・ふたつ以上ではあってはならないものです。

図の右側は、写像\(g:B\to A\)です。\(g(1)=1,g(5)=2,g(7)=3\)ですね。

(写像の行き先となる集合\(A\)が数の集合のとき、写像は関数とも呼ばれます。写像は関数のようなもの(関数の一般化)と思ってもらえば大丈夫です。集合論では、数だけでない集合を考えるので、写像という呼び方をするこが多いです。)

 

\(f\)は、\(C\)の要素を\(A\)の要素に一対一に対応させています。このような写像を、一対一写像(one-to-one mapping)、あるいは全単射写像(bijection mapping)といいます。

「一対一である・全単射である」とは、どういうことでしょうか。これは条件を2つに分解してしまえばわかります。

全射とは

写像\(g\)は、\(A\)の要素すべてに対応しているわけではありません。例えば、\(4\in A\)は\(g(b),b\in B\)という形で表せません。これを\(g\)が全射ではないといいます。

逆に、行き先の集合のあらゆる要素を、元の集合の要素を写像で写したものとして表せるとき、その写像は全射(surjection)であるといいます。

言い換えれば、\(F:X\to Y\)が全射であるとは、任意の\(y\in Y\)に対してある\(x\in X\)で\(y=F(x)\)となるものが存在することです。

例えば、\(f:C\to A\)は全射です。\(1\in A\)は、\(a\in C\)によって\(1=f(a)\)と表せます。ほかのすべての要素も同様です。

\(f\)によって「もれなく」\(A\)をカバーできているわけですね。\(g\)にはもれがあるわけです。全射な写像は、上への(onto)写像とも呼ばれます。

単射とは

写像\(f,g\)は、いずれも異なる要素を異なる要素へ対応させています。\(f(a)=1\neq 2 =f(b)\)であり、\(g(5)=2 \neq 3 =g(7)\)であり……といったように。これを単射な写像(injection mapping)といいます。

言い換えれば、\(F:X\to Y\)が単射であるとは、任意の\(x,y\in Y\)に対して\(x\neq y\)ならば\(F(x)\neq F(y)\)となることです。対偶を考えれば、任意の\(x,y\in Y\)に対して\(F(x)= F(y)\)ならば\(x= y\)となると言っても同じです。

単射とは、さきほどの図で言えば「矢印の行き先をすべて異なるものにする」ということ。2個を1個に対応させる関係が混ざっていたら、個数を数えるときに不適切ですよね(笑)。

\(h:A\to B\)を、\(h(1)=1,h(2)=5,h(3)=7,h(4)=7,h(5)=7\)によって定めると、\(h\)は写像です。\(h\)は全射ではあるが単射ではありません(各自考えてみてください)。

全単射とは

写像が一対一である、全単射であるとは、全射かつ単射であることです。

\(f\)は全単射であり、\(g\)は全単射ではありません(単射ではあるが全射ではない)。

 

集合の要素の個数、(有限集合の)濃度の話に戻りましょう。

要素の個数が同じとき、必ず全単射な写像が存在します。今回\(A,C\)の要素は5つでしたが、それがいくつになっても全単射な写像は存在しますよね。

要素の個数が異なるとき、全単射な写像は存在しません

今回の例で全単射な写像\(j:A\to B\)が存在したとしましょう。\(j\)は単射ですから、\(j(1),j(2),j(3),j(4)\)は\(B\)の異なる4つの要素です。しかし、\(B\)の要素は3つでした。これは矛盾です、つまり全単射な写像は存在しません。この議論は、要素の個数がいくつになっても通用しますね。

しかしながら、要素の個数が異なるとき、単射な写像は存在します。

今回の例でいう\(g\)ですね。少ない要素の集合から多い要素の集合へは必ず単射な写像を作ることができます。

このように考えれば集合の要素の多さの話が、どういう性質(全単射・単射)の写像が存在するかに置き換えられそうですね。写像を使って議論すれば、個数を数える必要がなくなるのです。

 

濃度とは何か、無限集合の場合

ここからは、有限集合だけでなく無限集合も考えます。(さきほどまでの具体的な集合\(A\)の話はリセットします))

濃度は英語でcardinarityというので、\(\mathrm{card}(A)\)でその濃度を表すことにしましょう。

定義:濃度

集合\(A\)と集合\(B\)の濃度が等しいとは、\(A\)から\(B\)への全単射が存在すること。このとき、\(\mathrm{card}(A)=\mathrm{card}(B)\)と書く。

集合\(A\)の濃度が集合\(B\)の濃度より大きくないとは、\(A\)から\(B\)への単射が存在すること。このとき、\(\mathrm{card}(A)\leq\mathrm{card}(B)\)と書く。

集合\(A\)の濃度が集合\(B\)の濃度より小さいとは、濃度が等しくなく、かつ大きくないこと。このとき、\(\mathrm{card}(A)<\mathrm{card}(B)\)と書く。

\(\mathrm{card}(\{1,2,\dots,n\}):=n \  (n\in \mathbb{N})\)

\(\aleph _0:=\mathrm{card}(\mathbb{N})\)

\(\aleph := \mathrm{card}(\mathbb{R})\)

濃度は、集合の間に全単射・単射が存在するかどうかによって決めてしまうのです。これで数えなくてよくなりました。

さきほどのケースのような集合を考えると、\( \mathrm{card} (\{a,b,c,d,e\})=5\)です。なぜなら、\(\{a,b,c,d,e\}\)と\(\{1,2,3,4,5\}\)の間には全単射が存在するから。有限集合の濃度は、要素の個数と一致しています。

 

さて、無限集合の濃度はどうなるのでしょうか。

\(\aleph _0\)(アレフ・ゼロ、アレフ・ヌルとも)という記号で、自然数の集合の濃度を表しています。\(\aleph _0\)自体は単なる記号であり、数ではありません。

\( \mathrm{card}(\{1\})=1<\mathrm{card}(\{1,2\})=2<\cdots \\ < \mathrm{card}(\{1,2,\dots,n\})=n < \aleph _0 =\mathrm{card}(\mathbb{N}) \ \)

という関係が成立しているのはわかるでしょうか。有限集合から\(N\)への単射は作れますが、全射は作れません。

つまり、\(n < \aleph _0\)といったように、有限集合と無限集合の要素の多さの違いを表現できています。\(\aleph _0\)は無限大として見ることができますが、濃度の定義に従った記号にすぎないことに注意しましょう。

 

濃度が等しい無限集合の例、可算集合と非可算集合

無限集合の濃度をいくつか考えてみましょう。

 

\(O\)を正の偶数全体の集合、\(S\)を平方数全体の集合とすると、\(\mathrm{card}(O)=\mathrm{card}(S)=\aleph _0\)です。\(f:\mathbb{N}\to O\)を\(f(n)=2n \)、\(g:\mathbb{N}\to S\)を\(g(n)=n^2 \)と定めれば、どちらも全単射な写像となっています(確かめてみてください)。

つまり、偶数全体や平方数全体は、自然数と「同じだけ多い」のです。ガリレオが言っていたことを正確に表しています。

参考:ガリレオのパラドックスとヒルベルトの無限ホテルから感じる、無限集合の性質

 

また、整数全体の集合\(\mathbb{Z}\)と有理数全体の集合\(\mathbb{Q}\)とも等しいです\(\mathrm{card}(\mathbb{Z})=\mathrm{card}(\mathbb{Q})=\aleph _0\)。

整数について。自然数を正負の符号をつけて交互に並べていってしまえばいいのです。\(f:\mathbb{N} \to \mathbb{Z}\)を\(f(1)=1,f(2)=-1,f(3)=2,f(4)=-2,\dots\)とすれば、\(\mathbb{Z}\)すべてをカバーできますよね。(ゼロが抜けるのでちょっと修正すると)

\[f (n) = \begin{cases} m & ( n=2m-1,m\in\mathbb{N} )  \\ -m+1 & ( n=2m,m\in\mathbb{N} ) \end{cases}\]

は全単射となります(確かめてみてください)。

有理数について。有理数は、\(\frac{a}{b}, a\in \mathbb{Z},b\in \mathbb{N}\)と整数と自然数の組で表せます。

整数と自然数の組の集合を\(\mathbb{Z}\times \mathbb{N} :=\{ (a,b) \mid a \in \mathbb{Z},b \in \mathbb{N} \}\)と書きましょう(組を集めた集合を直積集合という)。\(g:\mathbb{Z}\times \mathbb{N}\to \mathbb{Q}\)を\(g(a,b)=\frac{a}{b}\)と定めればこれは全単射です。つまり、\(\mathrm{card}(\mathbb{Q})= \mathrm{card}(\mathbb{Z}\times \mathbb{N}) \)です。整数のケースの関数と同じようなものを作ることで、\(\mathrm{card}(\mathbb{Z}\times \mathbb{N})=\mathrm{card}(\mathbb{N}\times \mathbb{N}) \)となります。

ここで、\(\mathrm{card}(\mathbb{N}\times \mathbb{N})= \aleph _0 \)が言えます。任意の自然数\(n\in \mathbb{N}\)は、素数の積として表せます(素因数分解)。

参考:算術の基本定理 – Wikipedia

\(n = 2^{(a-1)} \cdot p_1 \cdot \cdots \cdot p_N\)、\(a \in \mathbb{N}\)で、\(p_1,\dots,p_N\)は2でない素数。そして2以外の素数の積は奇数なので、\(n = 2^{(a-1)} (2b -1),a,b\in \mathbb{N}\)と表せます。\(g:\mathbb{N}\to\mathbb{N}\times \mathbb{N}\)を\(g(n)=(a,b)\)と定めましょう。これは全単射です。全射性はその定め方より明らかで、単射性は素因数分解の一意性にもとづいています。

以上によって、\(\mathrm{card}(\mathbb{Q})= \aleph _0 \)が言えました。

 

まとめると、\(\aleph _0=\mathrm{card}(\mathbb{N})=\mathrm{card}(\mathbb{Z})=\mathrm{card}(\mathbb{Q})\)となるのでした。

包含関係として見れば\(\mathbb{N}\subsetneq\mathbb{Z}\subsetneq\mathbb{Q}\)ですが、濃度として見ればこれらは等しいんですね。

自然数と同じ濃度を持つ集合を、自然数によって数え切れるということで、可算集合(countable set)と言います。整数や有理数は可算集合です。

 

さて、実数の集合の濃度を考えてみましょう。その濃度は、\(\aleph\)と書かれるのでした。

\(\mathbb{R}\)の開区間\((-1,1)\)を、\((-1,1):=\{x \in \mathbb{R} \mid -1<x<1\}\)で定めます。

画像引用:Wolfram

このとき、\(\mathrm{card}((-1,1))=\aleph\)です。\(f:(-1,1)\to \mathbb{R},f(x)=\frac{x}{1-x^2}\)と定めると、この写像は全単射です。\(x\)について単調増加なので単射です。また、任意の\(y\in \mathbb{R}\)に対し、その正負に合わせて\(x= \frac{-1\pm \sqrt{1+4y^2}}{2y}\)と定めれば、\(f(x)=y\)、\(x\in (-1,1)\)となり全射です(\(y=0\)なら\(x=0\)とする。確かめてみてください)。

このように、幾何学的に見れば有限の大きさしか持たない区間\((-1,1)\)ですが、実数と等しい濃度を持っています

さらには、平面の濃度すら実数の濃度に等しい\(\mathrm{card}(\mathbb{R}^2)= \aleph\)ことが知られています。

彼は数直線 R と平面 R2の間に全単射があるかという問題に取り組んで、3年にわたる研究の結果、それらの集合の間に全単射が存在することを示した。彼はその証明を伝えたデーデキントへの(ドイツ語の)書簡の中で、有名な “Je le vois, mais je ne le crois pas”「私にはそれが見えるが、しかし信じることができない」という(フランス語の)言葉を書き残している。

引用:集合論 – Wikipedia

集合論の父と言われるカントール(Cantor)ですら、この結果は(正しいが)信じられないと思えたようです。

濃度という観点から見れば数直線\(\mathbb{R}\)と平面\(\mathbb{R}^2\)は同じである。このように幾何学的な直観が通用しないものなんですね。

数直線と平面の違いを考えるためには、濃度ではなく別の性質(代数的構造、順序的構造)を考える必要があります。詳しくは、集合論の教科書で学ぶことができるでしょう。

 

実数の濃度は非可算無限、対角線論法とは

自然数の濃度\(\aleph_0\)と実数の濃度\(\aleph\)についての具体例を見てきました。これらはどういう関係にあるのか。

じつは、\(\aleph_0<\aleph\)です。実数は自然数によって数え上げることができず、可算集合ではないのです(非可算無限集合 uncountable set )

 

このことを示すために使われるのが、カントールの対角線論法です。

\(\aleph_0\leq\aleph\)であることは明らかです。自然数の集合から実数への集合は明らかに単射が存在します(\(f(n)=n\)とすれば良い)。

示すべきことは、\(\aleph_0\neq\aleph\)、つまり\(\mathbb{N}\)から\(\mathbb{R}\)への全射が存在しないということです。

さきほどの議論によって、\(\aleph=\mathrm{card}((-1,1))\)でしたが、\(g:(-1,1)\to (0,1)\)を\(g(x) = \frac{1}{2}x +\frac{1}{2}\)と定めれば\(\aleph=\mathrm{card}((0,1))\)です。

つまり、\(\mathbb{N}\)から\((0,1)\)への全射が存在しないことを示せば十分となりました。

 

\(f:\mathbb{N}\to (0,1)\)を任意の写像とします。

\((0,1)\)の任意の要素、0より大きく1より小さい実数\(x\)は、\(x=0.a_1 a_2 \cdots a_n \cdots\)、\(a_1,\dots,a_n\)は0から9までの整数、と小数によって表されます。例えば、\(x=0.114514\dots\)ならば\(a_1 =1,a_2=1,a_3=4\)といった具合です。

十進小数点展開して、その一桁一桁を\(a\)によって表すのです。ただし、\(0.50000\dots = 0.49999\dots\)のように2種類の表し方がある場合は、常に前者を採用し、小数点表示が一意となるようにします。逆に、0でない桁を持つ小数点表示は、ひとつの実数を定めます。

ある\(y=0.b_1 b_2 \cdots b_n \cdots \in (0,1)\)で、任意の\(n \in \mathbb{N}\)に対し、\(f(n)\neq y\)となるものが存在すれば、\(f\)は全射ではありません。

この\(y\)の作り方に使うのが対角線論法です。

まず今は\(f\)があるのですから、\(f(1),f(2),\dots,f(k),k\in \mathbb{N}\)を少数点表示してみましょう。

\(f(1) = 0. a_{1,1} a_{2,1} \dots a_{n,1} \dots\)

\(f(2) = 0. a_{1,2} a_{2,2} \dots a_{n,2} \dots\)

\(f(n) = 0. a_{1,n} a_{2,n} \dots a_{n,n} \dots\)

\(a_{i,j}\)は0から9までの整数で、一番目の添字\(i\)が小数点の桁数、二番目の添字\(j\)が\(f(j)\)の小数点展開であることを示しています。

さて、\(f(n)\neq y \)となる\(y\)はどう作れば良いでしょうか?

ふたつの実数は、小数点表示のどこか一桁でも異なれば違う数です。

\(y= 0. b_1 b_2 \dots b_n \dots\)を次のように定めてみましょう。

\[ \begin{aligned} b_n = \begin{cases} 1 & ( a_{n,n}が偶数のとき ) \\ 2 & ( a_{n,n}が奇数のとき ) \end{cases}\end{aligned} \]

するとどうでしょうか。

\(y,f(1)\)の1桁目を見てみると、\(b_1 \neq a_{1,1}\)なので、\(y\neq f(1)\)です。これは桁をずらせば同じ議論ができますね。\(y,f(n)\)のn桁目を見てみると、\(b_n \neq a_{n,n}\)なので、\(y\neq f(n)\)です。

\(f(n)\)を小数点展開し、その\(n\)桁目を奇数と偶数を入れ替えた値によって\(y\)の小数点展開を構成したのです。表の対角線部分で値が異なるようにしてあるわけですね。

よって、任意の\(n\in \mathbb{N}\)に対し\(f(n)\neq y\)であり、\(f\)は全射でありません。

写像\(f\)も任意のものでしたから、\(\mathbb{N}\)から\((0,1)\)への全射は存在しません。これによって、\(\aleph_0\neq\aleph\)を示すことができました。

 

証明を見ればわかるように、これは実数が十進小数点展開できるという性質を利用しています。これは実数の連続性と呼ばれる性質から導かれるものです(解析学の基礎的なテーマのひとつ)。

このことから、実数の濃度、非加算濃度\(\aleph\)は連続の濃度とも呼ばれます。

有理数には対角線論法は使えません。\( 0. b_1 b_2 \dots b_n \dots\)が無理数となるような\(f\)を考えると、\( y=0. b_1 b_2 \dots b_n \dots \not \in \mathbb{Q}\)なので\(f: \mathbb{N}\to (0,1)\cap \mathbb{Q}\)が全射でないとは言えません(そもそも\(\mathrm{card}(\mathbb{Q})=\aleph_0\)なので、全射は存在する)。

証明はしませんが、ユークリッド空間\(\mathbb{R}^N\)や複素数全体の集合\(\mathbb{C}\)の濃度も非可算無限である(\(\mathrm{card}(\mathbb{R}^N)=\mathrm{card}(\mathbb{C})=\aleph\))ことが知られています。

 

連続体仮説とは

最後に、少し発展的な話を紹介して終わりにしましょう。

可算濃度と非加算の濃度は真に異なるものである、\(\aleph_0<\aleph\)であることを紹介しました。

では、その中間の濃度は存在するのか? すなわち、\(\aleph_0<\mathrm{card}(X)<\aleph\)となる集合\(X\)は存在するのか?

存在しないのではないか」というのが、カントールによって提唱された連続体仮説(continuum hypothesis)です。言い換えれば、連続の濃度は可算濃度より大きい最小の濃度ではないか、ということ。彼はそれを証明できずに終わりました。

連続体仮説は、ヒルベルト(Hilbert)の23問題のうちの第1問題として重要視されました。

参考:ヒルベルトの23の問題 – Wikipedia

 

のちの数学の研究(ゲーデルやコーエン)によって、連続体仮説は、標準的な集合論の立場(ZFC公理系)からは「証明も反証もできない命題である」ことが知られています。つまり、連続体仮説が正しいとしても正しくない(偽)としても矛盾が起こらないこと(無矛盾性)、連続性仮説のZFC公理系からの独立性が証明されたのです。正しいとしても正しいとしなくても、どちらでも問題なく数学が展開できるということですね。

参考:連続体仮説 – WikipediaThe Consistency of the Continuum Hypothesis by Kurt Godel

 

集合の要素の個数の考え方の話、伝わりましたでしょうか。

一つ一つ数えるのではなく、対応関係、すなわち写像の全単射性によって集合と集合の間で濃度を比べることができる、という考え方でした。

自然数や整数は同じ濃度で可算濃度\(\aleph _0\)、実数はそれよりも大きい濃度で非加算濃度\(\aleph\)という話を紹介しました。

同じ「無限」といっても、数えられる無限と数えられない無限がある……そんな考え方は、とても面白いと思います。

木村すらいむ(@kimu3_slime)でした。ではでは。

 

 

集合・位相入門

集合・位相入門

posted with amazlet at 18.07.28
松坂 和夫
岩波書店
売り上げランキング: 19,669

 

The Consistency of the Continuum Hypothesis by Kurt Godel
Kurt Gdel Kurt Godel
Ishi Press
売り上げランキング: 201,198

 

こちらもおすすめ

集合論のはじまり、全称命題と存在命題、論理記号を知ろう

集合、構造、空間とは何か? ユークリッド空間R^Nを例に考える

集合の定義、よく使う数の集合、ラッセルのパラドックスとは

ガリレオのパラドックスとヒルベルトの無限ホテルから感じる、無限集合の性質