「集合と写像」2.1 濃度の大小,ベルンシュタインの定理

「濃度の比較」とは,集合の元の個数の比較を,より一般に拡大したものである.この記事では,「濃度の比較」の基礎となる「濃度の大小」の定義,および,その基本的な性質を紹介する.(なお,「濃度」そのものはこの記事では定義しない.のちに順序数について解説していく際に定義する.)

定義

まず,以下のように「濃度の大小」(濃度ではない!)を定義する.

定義 2.1.1

(i) 集合 \(A,B\) の間に少なくとも一つ全単射が存在するとき,$$|A|=|B|$$あるいは$$A~B$$と書き,集合 \(A,B\) の濃度は等しい,集合 \(A,B\) は対等である,集合 \(A,B\) は集合として同型である,などという.

(ii) 集合 \(A\) から \(B\) への単射が存在するとき,それを$$|A|\leq|B|$$で表し,\(A\) の濃度は \(B\) 以下である,\(B\) の濃度は \(A\) 以上である,という.

(iii) 集合 \(A\) から集合 \(B\) への単射が存在するが全単射は存在しないとき,それを$$|A|<|B|$$で表し,\(A\) の濃度は \(B\) より小さい,\(B\) の濃度は \(A\) より大きい,という.

 

上記の定義は,有限集合の場合に成立する内容をそのまま無限集合にも当てはめただけである.それでは,例を挙げよう.

注意(有限集合について):集合有限集合に含む.

例 2.1.2 濃度の比較1

\(A=\{0,1,2,\cdots,n-1\}\) としよう.\(A\) との間に全単射が存在する集合の元の個数は全て \(n\) 個である.\(A\) より濃度が小さい集合の元の個数は \(n\) 個未満である.\(A\) より濃度が大きい集合の元の個数は \(n\) より大きい.
以上のことは,すべて「個数」を「濃度」に置き換えて言い直しただけになっている.

例 2.1.3 濃度の比較2

\(A=\mathbb{N},B=\{2n\mid{}n\in\mathbb{N}\}\) とする.\(f:A\to{}B\) を \(f(n)=2n\) で定めれば,\(f\) は全単射である.したがって,\(|A|=|B|\) である.同様に,奇数全体の集合と自然数全体の集合も濃度が等しい.

 

濃度の比較の基本的性質

濃度の大小に関する記法で,\(=,\leq\) といった記号を使用した.これらの記号は,濃度の比較において,実数を扱う際の等号,不等号と同様に扱うことができる.

定理 2.1.4

任意に与えられた集合 \(A,B,C\) に対して以下が成り立つ

\begin{align}
\mathrm{(i)}&\ |A|=|A| \notag\\
\mathrm{(ii)}&\ |A|=|B|\ ならば\ |B|=|A|\notag\\
\mathrm{(iii)}&\ [\ |A|=|B|\ かつ\ |B|=|C|\ ]\ ならば\ |A|=|C|\notag
\end{align}

証明

\(\mathrm{(i)}\) は,\(\mathrm{id}_A\) (\(A\) から \(A\) への恒等写像)が全単射であることからわかる.\(\mathrm{(ii)}\) は,全単射 \(f:A\to{}B\) があれば,その逆写像 \(f^{-1}\) も全単射であることからわかる.\(\mathrm{(iii)}\) は,全単射の合成は全単射であることからわかる.

(証明終)

定理 2.1.5

任意に与えられた集合 \(A,B,C\) に対して,[\(|A|\leq|B|\)かつ\(|B|\leq|C|\)] ならば \(|A|\leq|C|\) である.また,\(|A|\leq|A|\) である.

証明

[ \(|A|\leq|B|\) かつ \(|B|\leq|C|\) ] ならば,単射 \(f:A\to{}B\),\(g:B\to{}C\) がある.このとき,\(g\circ{}f:A\to{}C\) は単射であるので,\(|A|\leq|C|\)となる.\(|A|\leq|A|\)は,\(\mathrm{id}_A\)  が単射であることからわかる.

(証明終)

 

 

ベルンシュタインの定理

\(|A|\leq|B|\ かつ\ |B|\leq|A|\) から \(|A|=|B|\) を得ることもできる.その証明はこれまでの内容ほど容易ではなく,この定理は「ベルンシュタインの定理」あるいは「カントール=ベルンシュタインの定理」と呼ばれる.

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

[\(|A|\leq|B|\ かつ\ |B|\leq|A|\)] ならば \(|A|=|B|\)

証明

\(f:A\to{}B,\ g:B\to{}A\) を単射とする.
$$B\setminus{}f(A)=B_0\\
g(B_0)=A_1\\
\ f(A_1)=B_1 $$
とし,以下 \(A_n,B_n\) を
$$f(A_n)=B_{n}\\ \ g(B_n)=A_{n+1}$$ として定める.言い換えれば,\(A\) から出発して \(B_0,A_1,B_1,\cdots\) を単射 \(f,g\) を利用して作っていくのである.ここで,

\begin{align}
A^*=\bigcup_{n=1}^{\infty}A_n,\ \ &A^{**}=A\setminus{}A^*\notag\\
B^*=\bigcup_{n=0}^{\infty}B_n,\ \ &B^{**}=B\setminus{}B^*\notag
\end{align}

とおく.このとき,

\begin{align}
f(A^{**})&=B^{**}\notag\\
g(B^*)&=A^*\notag
\end{align}

となっている.以下でこれを示す.

はじめに,\(f(A^{**})=B^{**}\) を示そう.\(f\) は単射なので,\(A^{**}=A\setminus{}A^*\) より\(f(A^{**})=f(A)\setminus{}f(A^*)\) である.ここで,\(B_0=B\setminus{}f(A)\)より\(f(A)=B\setminus{}B_0\) であり,

$$f(A^*)=f\left(\bigcup_{n=1}^{\infty}A_n\right)=\bigcup_{n=1}^{\infty}f(A_n)=\bigcup_{n=1}^{\infty}B_n$$

であるので,

$$f(A^{**})=(B\setminus{}B_0)\setminus{}\bigcup_{n=1}^{\infty}B_n=B\setminus{}\bigcup_{n=0}^{\infty}B_n=B\setminus{}B^*=B^{**}$$

となる.\(g(B^*)=A^*\)については,

$$g(B^*)=g\left(\bigcup_{n=0}^{\infty}B_n\right)=\bigcup_{n=0}^{\infty}g(B_n)=\bigcup_{n=1}^{\infty}A_n=A^*$$

が成立している.

\(f^{**}:A^{**}\to{}B^{**}\) および \(\ g^*:B^*\to{}A^*\) を

\begin{align}
f^{**}(x)&=f(x)\notag\\
g^*(x)&=g(x)\notag
\end{align}

として定めると,\(f,g\) が単射であることと,\(f(A^{**})=B^{**},\ g(B^*)=A^*\) より,\(f^{**},g^*\) は全単射である.そこで,さらに,\(f^{*}=(g^*)^{-1}\) とすると,これも全単射である.

したがって,\(h:A\to{}B\) を

$$h(x)=
\begin{cases}
f^{*}(x) & x\in{}A^* \\
f^{**}(x) & x\in{}A^{**}
\end{cases}
$$

と定めると,\(h\) は \(A,B\) 間の全単射となっている.したがって,\(|A|=|B|\) である.

(証明終)

前の記事:1.8 逆写像

次の記事:2.2 可算と非可算1


参考書籍

この記事の内容を勉強するにあたり,定番で,筆者も使用している本を紹介します.(定価は2020年05月16日時点のものを表記しています.)

 

まずひとつ目は,内田 伏一著「集合と位相」,通称「内田」です.筆者は主にこちらを使用しています.

数学の基礎となっている集合論の内容と位相空間論の内容をまとめた本です1)普通,大学の数学科では「集合と位相」というタイトルで講義が開講されるので,それに合わせた内容になっています..なお,筆者が用いているのはこれの旧版で,増補改訂版では,演習問題の解答が拡充されているようです.


 

 

  ふたつ目は,松坂 和夫著「集合・位相入門」,通称「松坂」です. 内田同様,位相空間まで網羅した内容となっているほか,濃度の演算や順序数の古典的な扱いにふれられています(内田では省略されている).なお,筆者は,こちらの本も旧版を使っています.  


 

前の記事:1.8 逆写像

次の記事:2.2 可算と非可算1

References   [ + ]

1. 普通,大学の数学科では「集合と位相」というタイトルで講義が開講されるので,それに合わせた内容になっています.