大学数学

集合.16　集合の濃度.1　濃度の定義と比較方法

有限集合と無限集合、濃度

直観的に意味がわかると思うのでここまでちゃんと定義していませんでしたが、改めて述べると、元の個数が有限個の集合を有限集合、無限個の集合を無限集合と言います。

そして、以前少しだけ例で述べましたが、元の個数のことを濃度と言うのでした。無限集合のときは個数はこれと言うことはできませんが、濃度を定義することができます。

写像の追加事項　全射、単射、全単射

濃度をきちんと定義するためには、写像についていくつか性質を定義しておく必要があります。

◆定義

f \colon X \rightarrow Y を写像とする。

\forall y \in Y, \exists x \in X \, \mathrm{s.t} \, f(x)=y のとき、f は全射

\forall a,b \in X, f(a)=f(b) \Rightarrow a=b のとき、f は単射

f が全射かつ単射であるとき、全単射であるという。

f が全射であるというのは、全がすべてを意味するように、すべての y \in Y は少なくとも一つの x \in X から写像によって移ってきたものであるということです。（二つ以上から移って来る場合もあります）

f が単射であるというのは、定義の対偶を取ってみればわかるのですが、

a \neq b \Rightarrow f(a) \neq f(b)

すなわち、異なるものは必ず違うところへ行くということなので、同じ行き先 y \in Y に送られる x \in X は高々一つしか存在しないということです。（一つも存在しない場合もあります）この高々一つという意味合いを単という字で表しています。

f が全単射であるというのは、全射と単射を合わせて考えると、すべての y \in Y は少なくとも一つの x \in X から移ってきて、かつそのような x は高々一つしか存在しないということなので、ただ一つ存在するということになります。

よって、次が成り立ちます。

◆定理

f \colon X \rightarrow Y は全単射である \Leftrightarrow \forall y \in Y, \exists! x \in X \, \mathrm{s.t.} \, f(x)=y

f が全単射のとき、一つの x \in X に対してちょうど一つの y \in Y が対応することになるので一対一対応であるとも言います。

さて、f \colon X \rightarrow Y が全単射であり、X,Y はともに有限集合としましょう。

このとき、X の元と Y の元には一対一対応が付くので、X と Y の元の個数（濃度）は等しいです。

X,Y が無限集合の場合には、個数は無限個というしかありませんが、もし X と Y に全単射があれば一対一対応が付くわけなので、有限集合の場合と同様に濃度は等しいと考えることができるでしょう。

この直観を逆手にとって、濃度が等しいことを全単射（一対一対応）が存在することとして定義するわけです。

濃度の定義

◆定義

集合 X の濃度を、|X|,\mathbf{card} (X), \# X などと表す。

ここでは \mathbf{card} (X) と表すことにしましょう。

次に、基準になる集合の濃度を定義します。

◆定義

\mathbf{card} (\emptyset) \overset{\mathrm{def}}{=} 0
\mathbf{card} (\{ 1,2, \dots , n \}) \overset{\mathrm{def}}{=} n
\mathbf{card} (\mathbb{N}) \overset{\mathrm{def}}{=} \aleph_0
\mathbf{card} (\mathbb{R}) \overset{\mathrm{def}}{=} \aleph

任意の自然数 n について、n < \aleph_0

有限集合の濃度を有限の濃度と言い、無限集合の濃度を無限の濃度と言う。

\aleph_0 を可算の濃度と言い、濃度  \aleph_0 を持つ集合を可算無限集合と言う。 \aleph_0 以下の濃度しか持たない集合を高々可算集合であるといい、 \aleph_0 より大きな濃度を持つ集合を非可算集合という。

また、 \aleph を連続体濃度と言う。

※：この定義は厳密なものではありません。実際は公理的集合論という分野の概念によって厳密な定義がなされるのですが、ここではより具体的な集合の濃度を始めに規定することで定義としています。

上二つの式は直感的にも明らかだと思います。

自然数全体の集合の濃度ですが、可算というのは数えられるという意味です。自然数全体の集合は確かに無限個の元を持っていますが、\{ 1,2, \dots \} と順番に数えていくことですべての元を列挙することができます。

実は無限集合の濃度にもレベルがあって、数えられない無限集合（非可算集合）というものがあります。一番身近な例は実数全体の集合 \mathbb{R} です。\mathbb{R} のすべての元を書き並べることはできません。

次に、濃度が等しいことを定義しましょう。

◆定義

X,Y を集合とする。全単射 f \colon X \rightarrow Y が存在するとき、\mathbf{card} (X) \overset{\mathrm{def}}{=} \mathbf{card} (Y) と定義する。

ここまでで、基準となる集合との全単射が存在するかどうかによって、濃度が等しいかどうかを考えることができるようになりました。

◇例１

X = \{ 1,2,3 \} , Y = \{ 4,5,6 \} とします。

写像 f \colon X \rightarrow Y を f(1)=4,f(2)=5,f(3)=6 で定義すると、f は全単射になります。

したがって、 \mathbf{card} (Y) =\mathbf{card}(X) =3 となります。

◇例２

M = \{0,2,4,6 \dots \} 、すなわち 0 以上の偶数全体の集合とします。

写像 f \colon \mathbb{N} \rightarrow M を次のように定義します。

f(n) = 2n , n \in \mathbb{N}

すると、これは全単射になります。

実際、任意の偶数 2m, m \in \mathbb{N} に対して、f(n) = 2m となるような n は n=m のただ一つ存在するからです。

したがって、 \mathbf{card} (M) =\mathbf{card}(\mathbb{N}) = \aleph_0 となります。

明らかに M \subsetneq \mathbb{N} であり、M の元の個数の方が \mathbb{N} の元の個数より少ないと言いたいような気もするのですが、どちらも可算無限集合となり、濃度は等しいのです。

◇例３

写像 f \colon \mathbb{N} \rightarrow \mathbb{Z} を次のように定めます。

f(2m)= m,f(2m+1) = -(m+1) , m \in \mathbb{N}

これは、視覚的には次のように自然数と整数を対応させている

\mathbb{Z} \colon 0 \rightarrow -1 \rightarrow 1 \rightarrow -2 \rightarrow 2 \rightarrow -3 \cdots \rightarrow
\mathbb{N} \colon 0 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \cdots \rightarrow

ことになり、全単射です。

したがって、 \mathbf{card}(\mathbb{Z}) = \mathbf{card}(\mathbb{N}) = \aleph_0 となります。

やはり、明らかに \( \mathbb{N} \subsetneq \mathbb{Z} ですが、濃度は等しくなります。

◇例４

X = \{ 1,2,3 \} , Y = \{ 4,5,6,7,8 \} とします。

写像 f \colon X \rightarrow Y を f(1)=4,f(2)=5,f(3)=6 で定義すると、f は単射になります。

しかし、7,8 \in Y に行くx \in X が存在しないため、全射ではありません。

この場合、3= \mathbf{card} (X) < \mathbf{card}(Y) =5 が成り立っています。

単射、全射と濃度の大小

例４を一般の状況で考えると、一般の集合 X,Y に対し、単射 f \colon X \rightarrow Y が存在するとき、Y の元は X の元より多いと言えそうです。

実際、単射の定義から、X の元すべてを f によって Y に移したとき、異なる元同士は異なる元に移るので、濃度という意味で考えれば、Y の中に X の元すべてと同じ数だけの元が少なくとも含まれていると考えられるからです。

しかしながら、例２や例３が示すように、全単射、つまり単射でありかつ全射であるような場合には = となることもあります。

そこで、単射と濃度の大小関係について、次のように定義します。

◆定義

X,Y を集合とする。単射 f \colon X \rightarrow Y が存在するとき、\mathbf{card} (X) \overset{\mathrm{def}}{\leq} \mathbf{card} (Y) と定義する。

次に、全射と濃度の大小関係について考えてみましょう。

例５

X = \{ 1,2,3,4,5 \} , Y = \{ 6,7,8 \} とします。

写像 f を f(1)=6,f(2)=7,f(3)=8,f(4)=6,f(5) =7 で定義すると、f は全射になります。

実際、f(1)=f(4)=6,f(2)=f(5)=7,f(3) =8 ですから、すべての Y の元に対して X から移ってくるような元が存在しています。

このとき、濃度に関して、5= \mathbf{card} (X) > \mathbf{card}(Y) =3 が成り立っています。

\mathbf{card} (X) > \mathbf{card}(Y) なので、単射 g \colon Y \rightarrow X が存在するはずですが、例えば、全射 f から次のように構成することができます。

f(1)=f(4)=6 より、例えば g(6) = 1 とします。g(6) =4 としてもよいです。
f(2)=f(5)=7 より、例えば g(7)=2 とします。g(7) =5 としてもよいです。
f(3) =8 より、g(8)=3 とします。

このように、全射 f があるとき、Y の各元に対して、そこに送られてくる X の元が必ず少なくとも一つは存在するので、存在するうちのいずれか一つを選びます。

そうして構成した写像 g は、実は単射になっています。実際、この例では単射になっていますが、この構成法は一般の集合に一般化して考えることができます。

◆定理

全射 f \colon X \rightarrow Y とすると、単射 g \colon Y \rightarrow X が存在する。
したがって、\mathbf{card} (X) \geq \mathbf{card} (Y) である。

■証明

f は全射であるから、任意の y \in Y に対して、f(x) = y となるような x \in X が少なくとも一つ存在する。

f(x) = y となるような x \in X のうちの一つを取り、（ y に依存することを考慮して）x_{y} と表し、g(y) = x_{y} と定義する。

このようにして定義した g が単射であることを示す。単射の定義より、\forall y',y \in Y に対して、g(y')=g(y) ならば y'=y を示せばよい。

g(y')=g(y) すなわち、x_{y'} = x_{y} であるとする。

ここで x_{y'} は、g の定義から f(x_{y'})=y' となるような X の元であり、 x_{y} は f(x_{y})=y となるような X の元である。

x_{y'} = x_{y} より、y'=f(x_{y'})=f(x_{y})=y

よって示された。 □

ベルンシュタインの定理

最後に一つの定理を紹介して今回は終わりにしようと思います。これは直感的にいかにも成り立ちそうなことなのですが、実際証明するとなると案外大変なものです。ここでは証明は割愛したいと思います。

◆ベルンシュタインの定理

単射 f \colon X \rightarrow Y と単射 g \colon Y \rightarrow X が存在するとする。
このとき、全単射 h \colon X \rightarrow Y が存在する。

濃度で書けば、 \mathbf{card} (X) \leq \mathbf{card} (Y) かつ  \mathbf{card} (X) \geq \mathbf{card} (Y) ならば、 \mathbf{card} (X) = \mathbf{card} (Y) が成り立つ。

全射と濃度についての関係も合わせると、さらに次の系が成り立ちます。

◆系

単射 f \colon X \rightarrow Y と全射 g \colon X \rightarrow Y が存在するとする。
このとき、全単射 h \colon X \rightarrow Y が存在して、 \mathbf{card} (X) = \mathbf{card} (Y) が成り立つ。

全射、単射、全単射を駆使して、様々な集合の濃度を比較することができるようになりました。

 

集合　その１６へ>

<集合　その１４へ

記事一覧（大学数学）に戻る

関連記事

  1. 大学数学

    集合.14　商集合

    商集合前回の話で、同値類が集合の分割を与えるので、同値類をすべ…

  2. 大学数学

    写像.10　積集合の普遍性

    積集合の普遍性積集合とは何かを集合と元を用いて具体的に記述する…

  3. 大学数学

    論理記号.1　よく使う論理記号一覧、命題

    論理記号とは～数学を記述する上での基本言語～数学においてよく使…

  4. 大学数学

    大学数学概説.2　大学１、２年生レベルの科目

    微分積分学大学１、２年生で、数学科に限らず理系のかなりの割合の…

  5. 大学数学

    集合.10　直和（非交和、無縁和）

    直和（非交和、無縁和）◆Def.SetTop.2.…

  6. 大学数学

    写像.4　逆写像

    逆写像\( f \colon X \rightarrow Y …

コメント

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

アーカイブ

  1. 大学数学

    集合.22　整列可能定理、超限帰納法

  2. 大学数学

    論理記号.5　論理演算

  3. 大学数学

    集合.20　選択公理

  4. 大学数学

    集合.3　補集合、差集合

  5. 大学数学

    大学数学概説.3　大学３、４年生レベルの科目（代数）
PAGE TOP
error: Content is protected !!