大学数学

集合.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 の元には一対一対応が付くので、XY の元の個数(濃度)は等しいです。

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

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

濃度の定義


◆定義

集合 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) と定義する。


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


◇例1

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

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

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



◇例2

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 となるような nn=m のただ一つ存在するからです。

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

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



◇例3

写像 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} ですが、濃度は等しくなります。



◇例4

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

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

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

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


単射、全射と濃度の大小

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

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

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

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


◆定義

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


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


例5

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

写像 ff(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) が成り立つ。


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

 

集合 その16へ>

<集合 その14へ

記事一覧(大学数学)に戻る

関連記事

  1. 大学数学

    写像.9 圏、特別な射と記号、可換図式

    圏、特別な射ここで、あまり深入りはしませんが、圏論的な全射、単…

  2. 大学数学

    集合.9 積集合(一般の場合)

    積集合(一般の場合)準備はできましたので、一般の集合族 \( …

  3. 大学数学

    写像.12 商集合の普遍性

    商集合の普遍性商集合を普遍性によって特徴付けます。…

  4. 大学数学

    写像.7 全射の性質

    全射の性質全射であることを同値な条件で言い替えることで特徴付け…

  5. 大学数学

    写像.3 写像の合成

    写像の合成高校数学で合成関数というものをやったかと思いますが、…

  6. 大学数学

    集合.8 「同一視する」という考え方

    写像を少しだけ予習一般の場合の積集合を定義するためには、写像と…

コメント

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

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

アーカイブ

  1. 大学数学

    集合.7 積集合(n個の場合)
  2. 大学数学

    集合.2 部分集合、べき集合
  3. 大学数学

    論理記号.5 論理演算
  4. 大学数学

    集合.11 二項関係.1 順序
  5. 大学数学

    写像.6 標準的な写像の例
PAGE TOP
error: Content is protected !!