集合論の基礎

<h2>はじめに</h2>
最近、大学時代の友人と趣味で集合論を学び直しました。
<b>内田伏一</b>先生の<b>「集合と位相」</b>(旧版)を、行間を全て埋める形で読み進めました。
せっかくなので記憶が新しいうちに学習内容を記事にして共有します。
全内容を網羅するわけでなく、初学者(数学を専攻したことがないエンジニア)向けに要点だけをかいつまんで書いていくので、興味があれば読んでみてください。
また、僕の思い付きで始めた勉強会に快く付き合ってくれた、京都大学大学院理学研究科・山崎君に感謝します。

<h2>エンジニアが集合論を学ぶ意義</h2>
集合論は確率論の基礎となり、確率論は統計学の基礎となっています。
そのため、データサイエンス系の道に進むことを考えている方にとって、統計学の学習の前段階として、集合論の基礎を知ることは重要かと思います。

<h2>集合とは</h2>
<b>「ある条件を満たすものの集まり」</b>を集合と言います。
集合を構成する一つ一つのものを<b>元</b>または<b>要素</b>と言います。
aが集合Aの元であるとき、<b>aはAに含まれる</b>と言い、<b>a∈A</b>と書きます。

<h2>集合の表記法</h2>
例として、「1以上5以下の整数」という集合Aを考えます。
集合Aの表記法としては、主に次の二つがあります。

① <b>{1, 2, 3, 4, 5}</b>
② <b>{x∈$\mathbb{N}$|1≦x≦5}</b>

①のように単純に元を書き並べてもよいですが、②のように
<b>{x|xの満たす条件}</b>
という形式で書くことも多いです。

<h2>部分集合</h2>
二つの集合A,Bについて、<b>「Aのどの元もBに含まれる」</b>とき、<b>AはBの部分集合である</b>と言い、<b>A⊂B</b>と書きます。
またこのとき、<b>AはBに包まれる</b>と言います。

(参考)
A⊂Bであることを、AはBに含まれると表現することも多いですが、元と集合との関係(a∈A)と、集合どうしの関係(A⊂B)とを区別するために、前者を「含まれる」、後者を「包まれる」と呼び分けることを個人的にはオススメします。

<h2>集合どうしが等しいことの証明</h2>
二つの集合A,BがA=Bであること(集合として等しいこと)を示したい場合、
<b>A⊂B かつ A⊃B</b>
であることを示します。
すなわち、
<b>①Aのどの元もBに含まれること(∀a∈A ⇒ a∈B)
②Bのどの元もAに含まれること(∀b∈B ⇒ b∈A)</b>
を示します。

(注)
∀は<b>「任意の」</b>を表す記号です。「任意の」というのは、<b>特別な選び方をしない</b>という意味です。任意のa∈Aについて条件Pが成り立つということは、(特別な選び方をせずに)どのように元を選んだとしても条件Pが成り立つということ、すなわち、全てのAの元に対して条件Pが成り立つということです。

<h2>集合族</h2>
時々躓く人がいる概念がこの集合族です。
集合族とは、<b>「集合の集合」</b>のことです。
集合とは単一の元だけを集めてできるものを指すとは限りません。
<b>集合を集めてできるもの</b>もまた集合です。
集合を集めてできる集合(<b>全ての元が集合であるような集合</b>)を強調して集合族と呼びます。

(例)
A,B,Cを集合とするとき、それらを元とする集合{A, B, C}は集合族

<h2>和集合と共通部分</h2>
<b>「Aの元とBの元とを全て合わせてできる集合」</b>を、AとBの<b>和集合</b>と言い、<b>A∪B</b>と書きます。
すなわち、
<b>A∪B = {x|x∈A または x∈B}</b>
です。
また、<b>「AとBの両方に含まれる元を全て集めてできる集合」</b>を、AとBの<b>共通部分</b>と言い、<b>A∩B</b>と書きます。
すなわち、
<b>A∩B = {x|x∈A かつ x∈B}</b>
です。

なお、和集合と共通部分については、交換法則・結合法則・分配法則が全て成り立ちます。
・A∪B = B∪A
・A∩B = B∩A
・(A∪B)∪C = A∪(B∪C)
・(A∩B)∩C = A∩(B∩C)
・A∪(B∩C) = (A∪B)∩(A∪C)
・A∩(B∪C) = (A∩B)∪(A∩C)
式変形する時、扱いやすくて助かりますね。
この性質も重要なので押さえておきたいです。

<h2>直積</h2>
二つのの集合A,Bに対して、<b>「a∈A かつ b∈B であるような全てのaとbの組(a,b)の集合」</b>をAとBの<b>直積</b>と言い、<b>A×B</b>と書きます。
エンジニアの方には、SQLの<b>CROSS JOIN</b>と言った方が馴染みがあるかもしれません。

(例)
A = {a, b, c}, B = {1, 2}のとき、
A×B = {(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)}

<h2>写像とは</h2>
写像をしっかり理解して使いこなせるかが集合論では肝要です。
<b>「集合Aの全ての元に対して集合Bの元を一つ対応させる規則f」</b>のことを、<b>AからBへの写像</b>と言い、<b>f:A→B</b>と書きます。
また、Aをfの<b>始域</b>、Bをfの<b>終域</b>と言います。
写像とは簡単に言えば<b>集合と集合との対応関係</b>のことですが、注意してほしいのが、集合と集合との対応関係ならば何でも写像と呼んでよいわけではないということです。
写像とは、Aの<b>「全ての」</b>元を、Bの元に<b>「一つ」</b>対応させる規則のことですから、例えば次のようにAの元をBの元に対応させきっていないものは写像とは言いません。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/2ee92517-a416-6b46-f2a5-2239a2141954.png)
ただし、Bの元でAからの対応がないものがあってもOKです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/b9bd8168-73c0-178f-fa23-eaf7979a192b.png)
また、Aの元がBの二つの元に対応してしまっているようなものも(AからBへの)写像とは言いません。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/19946618-e251-6bca-4fb1-2a165d8017d8.png)
ただし、Aの別々の元がBの同じ元に対応しているようなものはOKです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/b7b16549-db38-336f-db3b-2fe556f16506.png)

<b>・始域の元は全て終域に飛ばす
・始域の一つの元から出る矢印は一本</b>
ということを忘れないようにして下さい。

<h2>全射・単射</h2>
写像の中でも特に、<b>「終域の全ての元に矢印が伸びているようなもの」</b>を全射と言います。(終域の元を<b>全</b>て<b>射</b>つ)

(全射の例)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/8499d20f-0bf3-292c-faa7-8ef63afdb777.png)

(全射でない例)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/42e44c67-aa68-b223-132c-1f64e0b2fb1a.png)

写像の中でも特に、<b>「終域の一つの元に対して二本以上矢印が伸びていないもの」</b>を単射と言います。(終域の元を<b>単</b>(ひと)つ<b>射</b>つ)

(単射の例)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/004ca0a4-0073-c62a-299a-f2264e9df0be.png)

(単射でない例)
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/dac04033-6701-a9ef-1174-374f5b059c0f.png)

イメージとしては上記で問題ないですが、数学ですからもう少しキチンと定義しておく必要があります。
ここまでの図によるイメージが掴めていれば、正確な定義もスッと理解できると思います。

<b>fは全射である
⇔f:A→Bについて, Bのどんな元bに対してもb=f(a)となるAの元aが常に存在する</b>

<b>fは単射である
⇔Aの元a_1, a_2に対して、f(a_1)=f(a_2)ならば常にa_1=a_2である</b>

また、写像fが<b>全射かつ単射</b>であるとき、fは<b>全単射</b>であると言います。

(参考)
単射の定義は、
Aの元a_1, a_2に対して、a_1≠a_2ならば常にf(a_1)≠f(a_2)である
としてもよい(対偶をとっただけなので同じこと)ですが、f(a_1)=f(a_2)⇒a_1=a_2の方が使い勝手がよいので、こちらを覚えておくのがよいかと思います。

<h2>逆像と逆写像</h2>
敢えて取り上げる必要もない気がしますが、オマケです。言葉が似ていて意外とこんがらがる人が多いようなので注意です。
<b>逆像</b>とは、<b>写像fによりBの部分集合B'に飛ばされるようなAの元全体の集合</b>です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/957c9567-8e06-fd1e-19fe-423c69d6cd26.png)

<b>逆写像</b>とは、<b>写像fが全単射のとき、各元の矢印の向きをひっくり返してできる写像</b>です。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/1246243/aabe89a8-f39b-38aa-8c01-2bb151b53b42.png)