「集合と写像」2.3 直積やべき集合と濃度,カントールの定理

この記事では,濃度の比較について,直積やべき集合に関連するものを紹介する.

直積と濃度

直積によって構成されたふたつの集合について,直積を構成する集合(直積因子)同士の関係からわかることがある.

定理 2.3.1

\begin{align}
\mathrm{(i)}:\ &|A_1|\leq|B_1|かつ|A_2|\leq|B_2|\Rightarrow|A_1\times{}A_2|\leq{}|B_1\times{}B_2|\notag\\
\mathrm{(ii)}:\ &|A_1|=|B_1|かつ|A_2|=|B_2|\Rightarrow|A_1\times{}A_2|=|B_1\times{}B_2|\notag
\end{align}

証明

\(\mathrm{(i)}\) の証明

\(f:A_1\to{}B_1,g:A_2\to{}B_2\) を単射とする.\(F:A_1\times{}A_2\to{}B_1\times{}B_2\) を

$$F({}(a_1,a_2){})=(f(a_1),g(a_2){})$$
で定める.\(f,g\) はともに単射なので,\(F\) も単射である.

\(\mathrm{(ii)}\) の証明

\(f:A_1\to{}B_1,g:A_2\to{}B_2\) を全単射とする.\(F:A_1\times{}A_2\to{}B_1\times{}B_2\) を

$$F({}(a_1,a_2){})=(f(a_1),g(a_2){})$$

で定める.\(f,g\) はともに全単射なので,\(F\) も全単射である.

(証明終)

 上記の証明で,\(\mathrm{(i)}\) と \(\mathrm{(ii)}\) の違いは「単射」と「全単射」のみである.

 

例 2.3.2

\(|\mathbb{N}|=|\mathbb{Q}|\) であったので,\(|\mathbb{N}\times\mathbb{N}|=|\mathbb{Q}\times\mathbb{Q}|\) が成立している.

例 2.3.3

\(|\mathbb{N}\times\mathbb{N}|\leq|\mathbb{R}\times\mathbb{R}|\) である.単射は,包含写像を利用して簡単に作れる.

 

べき集合と濃度

べき集合と濃度について,まずは以下を示そう.

定理 2.3.4

\(A\) を元の個数が \(n\) 個の有限集合とする.このとき,\(\mathfrak{P}(A)\)1)\(\mathfrak{P}(A)\) は \(A\) のべき集合の元の個数は \(2^n\) である.

証明

\(A\) の元の個数に関する帰納法でおこなう.まず,\(A\) の元の個数が \(0\),すなわち \(A=\emptyset\) ならば,\(\mathfrak{P}(A)=\{\emptyset\}\) より成立している.

\(A\) の元の個数が \(k\) 個のとき,成立していると仮定する.\(A\) の元の個数が \(k+1\) とする.\(A\) の元をひとつ任意に与えて \(a\) とおく.\(A\setminus\{a\}=A’\) とする.このとき,\(A\) の部分集合で \(a\) を含まないものは,すべて \(A’\) の部分集合で,これは帰納法の仮定より \(2^k\) 個ある.また,\(A\) の部分集合で \(a\) を含むもの全体の集合を \(B\) とし,写像 \(F:\mathfrak{P}(A)\to{}B\) を

$$F(X)=X\cup\{a\}$$

とすると \(F\) は全単射であり,\(B\) の元の個数,すなわち \(A\) の部分集合で \(a\) を含むものの個数は \(2^k\) である.\(A\) の部分集合は \(a\) を含むか含まないか,どちらか一方のみが必ず成立するので,\(A\) の部分集合の個数は \(2^k+2^k=2^{k+1}\) である.

(証明終)

 以上のことから,以下のような記法を採用するのである.

定義 2.3.5

任意に与えられた集合 \(A,B\) について,\(|A|=|\mathfrak{P}(B)|\) であることを,

$$|A|=2^{|B|}$$

と書く.同様に,\(|A|\leq|\mathfrak{P}(B)|\) であることを,

$$|A|\leq2^{|B|}$$

と書く.

 

ここで,以下が成り立つ.端的に言えば,「べき集合」はもとの集合より真に大きいのである.

定理 2.3.6 カントールの定理

示すべきことは,\(A\) から \(\mathfrak{P}(A)\) への単射は存在するが全単射は存在しないことである.単射の存在は明らかである.\(f:A\to\mathfrak{P}(A)\)を\(f(a)=\{a\}\) で定めれば単射になる.全単射が存在しないことを背理法で示す.

\(A\) から \(\mathfrak{P}(A)\) への全単射が存在すると仮定し,\(f:A\to\mathfrak{P}(A)\) を全単射とする.

集合\(B=\{a\in{}A\mid{}a\notin{}f(a)\}\) について考える.\(f(a)=B\) なる \(A\) の元 \(a\) が,\(f\) が全単射であることよりただ一つ存在する.そのような \(a\in{}A\) について考える.

\(a\in{}B\) とすると,\(B\) の定義より \(a\notin{}f(a)\) であるが,これは \(f(a)=B\) であるので矛盾である.\(a\notin{}B\) とすると,\(B=f(a)\) より \(a\notin{}f(a)\) となり,\(B\) の定義より \(a\in{}B\) となって矛盾する.ところが,\(B\) は \(A\) の部分集合であり \(a\in{}A\) であるので,\(a\in{}B\) と \(a\notin{}B\) の少なくとも一方は成り立たねばならず,矛盾である.

以上より,\(A\) から \(\mathfrak{P}(A)\) への全単射は存在しない.

(証明終)

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

次の記事:2.4 可算と非可算2


参考書籍

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

 

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

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


 

 

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


 

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

次の記事:2.4 可算と非可算2

References   [ + ]

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