集合論

集合とはなにか？

集合とは、物の集まりであって、何か物を持ってきたときにそこに属すのか属さないのかどちらかに必ず定まるもののことである。例えば、「標高8500m以上の山」「都道府県であって、人口500万人未満のもの」「すべての二等辺三角形」「正の奇数すべて」などは集合である。ただし、「頭がいい人」のような、何が属して何が属さないのかが曖昧なものは集合とは呼ばないことにする。

集合に属している物のことを元と呼ぶ。先ほどの例から、「標高8500m以上の山」という集合では、「エベレスト、K2、カンチェンジュンガ、ローツェの4つの元がある」などと言う。「正の奇数すべて」の集合は、「1,3,5,...という無限個の元から成っている」と言える。元が集合に属していることを「$\in$」という記号で表す。例えば、自然数の全体という集合を$\mathbb{N}$とすると、$1 \in \mathbb{N}$と書ける。

なお、元が1つもない集合も集合とみなすことにする。そのような集合を空集合と呼び、$\phi$で表す。

記法と演算

外延的記法と内包的記法

集合をあらわすには、その集合に属している元をすべて書き表すのが最も簡単だ。例えば「1桁の素数」という集合なら{2,3,5,7}と書ける。このような書き方を外延的記法という。

しかし、集合の元の数が多くなってくると外延的記法は難しくなってくる。例えば、人口500万人未満の都道府県は38個もあるので全部列挙していたら大変だ。それどころか、正の奇数すべての集合の元は無限個あるので、全部書き表すことは不可能で、{1,3,5,7,...}と書くしかない。しかし、このような書き方は、どのような集合なのか誤解を招きやすい。ある人は、「奇数の素数と1」という集合{1,3,5,7,11,13,17,...}の意味でこのように書くかもしれない。

そこで、ある集合の元が満たすべき性質を書くことで集合をあらわすことを考える。そのような記法を内包的記法という。内包的記法では、集合の元を代表する文字と満たすべき条件を縦棒を挟んで並べて書く。例えば、正の奇数の集合は

$\{ x \mid x=2n-1 , n \in \mathbb{N}\}$

と書ける。

部分集合

集合Sのすべての元が集合Tに属しているとき、SはTの部分集合であるといい、$S \subset T$と表す。空集合は任意の集合の部分集合である。また、S自身もSの部分集合である。S自身以外の部分集合をSの真部分集合といい、TがSの真部分集合であることを$T \subsetneq S$とあらわす。

元が集合に属しているという関係と、元がひとつだけの集合が別の集合の部分集合であるという関係とは似て非なるものである。すなわち、$x \in X$と$\{ x \} \subset X$とは、同値ではあるが表していることは異なる。この違いにはよく注意すべきである。

$X \subset Y$かつ$Y \subset X$を満たすときX=Yと書き、この2つの集合は等しいという。何をくだらないことを定義するのか、と思ってはいけない。数学ではしばしばまったく別の方法で定義した2つの集合X,Yが実は同じ集合であることを証明すべきときがある。そのようなときには、$X \subset Y$かつ$Y \subset X$を示せばよいのである。

冪集合
集合があるとき、その集合の部分集合の集合というものを考えることができる。これをその集合の冪（べき）集合という。きちんと集合の記法で書けば、

$\mathcal{P}(X) = \{ S | S \subset X \}$

のことを、Xの冪集合という。

例
$\mathcal{P}(\{ 1,2,3 \} ) = \{\phi,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$

この例を見てもわかるように、有限個の元から成る集合（厳密な定義は後の節を参照）Xの冪集合$\mathcal{P}(X)$の元の個数は、Xの元の個数の2の冪である（この例でいえば、2³=8個）ので、$\mathcal{P}(X)$のことを$2^X$と書くこともある。

集合算

集合Sと集合Tの元をあわせた集合を和集合ないしは合併といい、$S \cup T$と表す。例えば、$\{1,2,3\} \cup \{3,4,5\} = \{1,2,3,4,5\}$である。

集合Sから集合Tの元を除いたものを差集合といい、S-Tないしは$S \setminus T$と表す。例えば、$\{1,2,3\} \setminus \{3,4,5\} = \{1,2\}$である。

集合Sと集合Tの共通する元の集合を積集合ないしは共通部分といい、$S \cap T$と表す。例えば、$\{1,2,3\} \cap \{3,4,5\} = \{3\}$である。

これらに関しては、次の性質（ド・モルガンの法則）が成り立つ。SとTをXの部分集合とすると、

$X \setminus (S \cap T) = (X \setminus S) \cup (X \setminus T)$

$X \setminus (S \cup T) = (X \setminus S) \cap (X \setminus T)$

また、次の性質（吸収法則）もよく知られている。

$(S \cap T) \cup S = S$

$(S \cup T) \cap S = S$

集合Sと集合Tの元の組の集合を直積といい、$S \times T$と表す。例えば、$\{ 1,2 \} \times \{ 3,4 \} = \{ (1,3),(1,4),(2,3),(2,4) \}$である。

写像

我々は、関数という概念を既に知っている。fが関数であるとは、xという数に対して別の数f(x)がただひとつ定まることであった。ここでは、関数の概念を一般化した写像という概念を考える。すなわち、集合XとYについて、任意の$x \in X$に対して$f(x) \in Y$がただひとつ定まるとき、この対応fはXからYへの写像であるといい、

$f:X \to Y , x \mapsto f(x)$

と書くことにする。2つの写像$f_1,f_2:X \to Y$について、

$f_1=f_2 \Leftrightarrow \forall x \in X \ f_1(x)=f_2(x)$

と定める。

2つの写像$f:X \to Y$と$g:Y \to Z$があるとき、写像$h:X \to Z , x \mapsto g(f(x))$が定まる。これをfとgの合成といい、$g \circ f$と書く。

像と逆像

写像$f:X \to Y$とXの部分集合Sがあるとき、Yの部分集合$\{ f(x)|x \in S \}$をfによるSの像といい、$f(S)$と書く。

写像$f:X \to Y$とYの部分集合Tがあるとき、Xの部分集合$\{ x|f(x) \in T \}$をfによるTの逆像といい、$f^{-1}(T)$と書く。

特に$T= \{ y \}$のときには$f^{-1}( \{ y \} )$を単に$f^{-1} (y)$と書くこともしばしばある。しかし、この記号は少し紛らわしいので注意すべきである。$f(S)$と$f^{-1}(T)$はどちらも集合であるのに対して、$f(x)$は集合の元だが$f^{-1}(y)$は集合である。

単射と全射

写像$f:X \to Y$が$f(x)=f(x') \Rightarrow x=x'$(対偶を取れば、$x \neq x' \Rightarrow f(x) \neq f(x')$)を満たすとき、fは単射であるという。また、$f(X)=Y$を満たすとき、fは全射であるという。全射かつ単射であることを全単射であるという。

例　集合Xと部分集合Sが与えられているとする。このとき、$i:S \to X$をi(x)=xで定めると、これは単射である。このiを包含写像という。特にS=Xのとき、iは全単射である。このとき恒等写像と呼び、特に$id_X$と書く。

特に空集合は任意の集合の部分集合なので、空集合からは任意の集合へ包含写像を考えることができる（実質的には何も定めていない写像だが、集合論的に考えることはできる、ということである）。これを特に空写像という。

写像$f:X \to Y$と$g:Y \to X$があって、$g \circ f =id_X$かつ$f \circ g =id_Y$を満たすとき、gはfの逆写像であるといい、$f^{-1}$と書く。

写像fに逆写像が存在することと、写像fが全単射であることは同値である。写像が全単射であることを証明するために、全射かつ単射であることを示すより、具体的に逆写像を構成してしまったほうが簡単な場合がしばしばある。

単射・全射については以下の命題も成り立つ。

命題 写像$g:Y \to Z$が単射で、$f_1,f_2:X \to Y$が$g \circ f_1=g \circ f_2$を満たすとき、$f_1=f_2$

（証明）
$x \in X$を任意にとると、$g(f_1(x))=g(f_2(x))$であり、gが単射なので、$f_1(x)=f_2(x)$である。よって$f_1=f_2$である。

命題 写像$f:X \to Y$が全射で、$g_1,g_2:Y \to Z$が$g_1 \circ f=g_2 \circ f$を満たすとき、$g_1=g_2$

（証明）
$y \in Y$を任意にとると、fが全射なので、$f(x)=y$なる$x \in X$がある。$g_1(f(x))=g_2(f(x))$なので、$g_1(y)=g_2(y)$である。よって、$g_1=g_2$である。

これらの命題は、単射や全射という概念を、集合の元という概念（もっといえば、集合という対象）を用いずに特徴づけているという点で重要な命題である。

写像の制限

写像$f:X \to Y$と集合$S \subset X$があるとき、$x \in S$に対して$x \mapsto f(x)$と定めることで、写像$S \to Y$が自然に定まる。このようにして定めた写像をfのSへの制限といい、$f|_S$であらわす。

はじめはfと$f|_S$はほとんど同じもののように感じるかもしれないが、区別したほうが便利である。たとえば、$f:\mathbb{R} \to \mathbb{R},x \mapsto x^2$と$S=\{ x \in \mathbb{R}| x \ge 0 \} \subset \mathbb{R}$を考えると、fは全射でも単射でもないが、$f|_S$は単射である。

写像の制限は、包含写像を使って表すことができる。$i:S \to X$を包含写像とすると、

$f|_S=f \circ i$

である。

同値関係と商集合

同値関係

「～」が集合A上の二項関係であるとは、任意の$a,b \in A$について、a～bであるかまたはそうでないかが必ず定まることである。例えば、実数の集合における「＝」「≦」などは二項関係である。さらに、二項関係であって次の3つを満たすもののことを同値関係と呼ぶ。

1. $a \in A \Rightarrow a \sim a$（反射律）
2. $a \sim b \Rightarrow b \sim a$（対称律）
3. $a \sim b , b \sim c \Rightarrow a \sim c$（推移律）

先ほど挙げた「＝」は同値関係であるが、「≦」は対称律を満たさないので同値関係ではない。他に同値関係の例として、自然数の集合上の、ある自然数nで割った余りが等しいという関係「≡(mod n)」などを挙げておく。

商集合

さて、同値関係が与えられたときに、各$a \in A$について次の集合を考える。

$C(a)= \{ x \in A | x \sim a \}$

すなわちC(a)とは、同値関係～によってaと同値な元全体の集合である。これを～に関するaの同値類と呼ぶ。このように定めると、次の性質が成り立つことが容易にわかる。

1. $C(a)=C(b) \Leftrightarrow a \sim b$
2. $C(a) \neq C(b) \Rightarrow C(a) \cap C(b) = \phi$

この2番目の性質は、同値関係が与えられると、元の集合Aは、互いに交わらない部分集合族によって分割（直和分解）されることを表している。この、Aを分割する部分集合族のことを、Aを同値関係～で割った商集合といい、A/～と書く。集合の言葉できちんと書くと下のようになる。

$A/ \sim = \{ C(a) | a \in A \}$

自然な写像

集合Aと部分集合Sを考えると、SからAへは包含写像という自然な単射を考えることができた。商集合でも、次のような自然な写像を考えることができる。

$\pi : A \to A/\sim , x \mapsto C(x)$

この写像は明らかに全射である。この写像のことを、標準的全射とか、自然な全射という。

濃度

濃度の概念

この節では、集合の元の個数について考える。いま、素朴に「個数」と書いたが、この概念は自明な概念ではない。確かに、$\{ 1,2,3 \}$という集合の元の個数は3個である、といったことは、素朴に考えてもすぐに言うことができる。しかし、では元が「無限個」ある場合はどうしたらよいのだろうか？これは案外難しい。

そこで、個数という概念を直接定義するのではなく、2つの集合の元の個数がひとしいとはどういうことなのか、ということをまず定義することにしたい。これはそれほど難しくない。以下のようにすればよい。

定義　2つの集合AとBの間に全単射があるとき、AとBは対等であるという。

元が有限個の場合に、これまでの素朴な「個数がひとしい」という概念と一致していることは容易にわかる。

さて、この集合と集合が対等であるという関係は、同値関係である。そこで、この同値関係によるAの同値類をcard Aと書き、これをAの濃度という。2つの集合が対等であるということを、2つの集合の濃度がひとしいという言葉で言い換えただけである。これによって、任意の集合に適用できる「個数」にあたる概念を手に入れることができた。もちろん（くどいかもしれないが）この濃度の概念は有限集合の場合は素朴な「個数」の概念と一致する。

Bernsteinの定理

2つの集合があったとき、その2つの集合の濃度がひとしいか否かというのはしばしば気になることである。しかし、2つの集合の濃度がひとしいということを示すには、今のところは全単射を具体的に構成するしかなく、これはしばしば大変なこともある。例えば、閉区間[0,1]と$\mathbb{R}$とは濃度がひとしいのだが、全単射を具体的に作るのは容易ではない。

そこで役に立つのが、次に挙げる定理である。

定理(Bernstein)
集合AとBがあり、AからBへの単射と、BからAへの単射があるとき、card A=card B

AからBへの単射があることと、BからAへの全射があることは同値であるから、定理のステートメントの「単射」をすべて「全射」と書き換えても構わない。

この定理を用いて、自然数の集合$\mathbb{N}$と、有理数の集合$\mathbb{Q}$が対等であることを示してみよう。$\mathbb{N}$から$\mathbb{Q}$へは自明な単射が存在するから、逆向きの単射を作ればよい。$\mathbb{Q}$から$\mathbb{N} \times \mathbb{N}$への単射は容易に作れるので、結局$\mathbb{N} \times \mathbb{N}$から$\mathbb{N}$への単射を作ればよい。$(a,b) \in \mathbb{N} \times \mathbb{N}$に対して$f((a,b))=2^{a-1}(2b-1)$と定めると、これは$\mathbb{N}$への単射である。したがって、これらを合成すると$\mathbb{Q}$から$\mathbb{N}$への単射が構成でき、Bernsteinの定理より$\mathbb{N}$と$\mathbb{Q}$は対等である。

問　Bernsteinの定理を用いて、閉区間[0,1]と$\mathbb{R}$は濃度が等しいことを証明せよ。

有限集合・可算集合・非可算集合

これまで「有限」という言葉をナイーブに未定義のままで使ってきたが、ここできちんと定義しておく。

定義　$[n]=\{1,2,...,n\}$とする。特に$[0]=\phi$とする。集合Aが有限集合であるとは、ある自然数nに対してAと$[n]$が対等であることである。

これまでナイーブに想像していた概念と一致することを確認してほしい。有限集合でない集合のことを無限集合という。

有限集合であるための同値な条件はこのほかにもあるが、ここではひとつ挙げておく。

命題^*　集合Aが有限集合であることは、Aと対等なAの真部分集合が存在しないことと同値。

たとえば、偶数の集合は整数の集合の真部分集合だが、これらは対等である。有限集合ではこのようなことは起きない。

無限集合の中でも、特に$\mathbb{N}$と対等な集合は特別視して、可算集合という（可算無限集合ということもあるが、重言である）。先ほどの議論から、$\mathbb{Q}$は可算集合である。有限集合と可算集合を合わせて高々可算な集合といい、高々可算でない集合のことを非可算集合という。

なぜ無限集合の中で可算集合を特別視するかというと、可算集合は「最も小さい」無限集合だからである。すなわち、

命題^*　任意の無限集合Aは、可算な部分集合を持つ。

つまり、非可算集合とは、自然数の集合よりも大きい集合のことである。

次の命題とその証明は非常によく知られている。

命題　$\mathbb{R}$は非可算集合である。

（証明）
全射$p:\mathbb{N} \to \mathbb{R}$が存在したとすると、$n \mapsto$($p(n)$の小数部分)と定めることで、全射$f:\mathbb{N} \to (0,1)$を作ることができる。したがって、任意の写像$f:\mathbb{N} \to (0,1)$が全射でないことを示せば十分である。

$f(n)$の小数第n桁目を$a_n$と定める。（ただし、小数による実数の表示は一意ではないので、ここでは同じ実数について無限に9が続く表示と無限に0が続く表示がある場合は後者を採用することにする。）このとき、数列$b_n$を

$b_n=\begin{cases}0 & if \ a_n=1 \\ 1 & if \ a_n \ne 1\end{cases}$

と定め、cを、整数部分が0で、小数第n桁目が$b_n$であるような実数とする。すると、明らかにcはfの値域に入っていない。よって、fは全射ではない。//

この有名な議論を、Cantorの対角線論法という。