集合

集合と命題と写像

集合とはいくつかの「もの」の集まりであり、その集合に所属するかしないか判定できるものをいう（ことにする）。 ここでいう集合に所属する「もの」のことを元または要素という。 「もの」としては整数や実数のような「数」を想定しているが、関数や図形さらには集合自体まで「もの」として認めることがある。 つまり、集合の集合などもあり得て、実際後に述べる実数の実体は特殊な集合でありその集合が実数の集合としてこのテキストで頻繁に出てくる（が、集合としての実数は最初に基礎的な性質を示す時のみに使われてあとは集合であることを意識せずに数として扱うことができる）。 集合$𝐴$と「もの」$𝑎$に対して$𝑎$が$𝐴$の元であるとき、$𝑎$は$𝐴$に属するや含まれるあるいは入っているなどと表現し、$𝑎\in 𝐴$と表す。 そうでない時は、$𝑎\notin 𝐴$と書く。

集合を記述する方法にはいくつかありこのテキストでは四種類使う。 そのうち一つが外延記法といって元を列挙して記述する方法であり、例えば$1,2,3$の3つの元からなる集合は

$$\left\{1,2,3\right\}$$

と書かれる。 なお、この集合に対しては$1\in \left\{1,2,3\right\}$で、$5\notin \left\{1,2,3\right\}$である。 集合で重要なことは元が属するかどうかであり、属する順番は関係がない。 また、上記の記法で重複したものがあっても重複分は無視される。 つまり、

$$\left\{1,2,3\right\}=\left\{3,2,1\right\}=\left\{1,1,2,2,3,3\right\}$$

である。

このテキストでは元の列挙の際に誤解の余地がない場合にいくつかの元を省略する。 その際には記号$\dots$を用いる。 例えば、

$$\left\{0,1,2,3,4,5,6,7,8,9\right\}=\left\{0,1,2,3,\dots ,9\right\}=\left\{0,\dots ,9\right\}$$

や、$𝑁$を自然数として

$$\left\{0,1,2,3,\dots ,𝑁\right\}$$

などである（このテキストでは$0$も自然数として扱う）。

この省略に関係して、集合の二つ目の記法があり、列挙が無限に続く場合にも省略を用いた外延記法を認める。 これにより自然数全体の集合は

$$\left\{0,1,2,3,\dots \right\}$$

と表される。 さらにこのテキストでは前方にも省略を使うことを認めて、整数全体の集合を

$$\left\{\dots ,-3,-2,-1,0,1,2,3,\dots \right\}$$

や偶数全体の集合を

$$\left\{\dots ,-6,-4,-2,0,2,4,6,\dots \right\}$$

などと記述する。

上記二つの外延記法を使っている場合に限り、例えば「任意の$𝑛\in \left\{0,1,2,3,\dots ,𝑁\right\}$に対して」という記述を「任意の$𝑛=0,1,2,3,\dots ,𝑁$に対して」などと書くことがある。

三つ目の記法に関連する概念が命題である。 命題とは真か偽か判定可能な条件を記述した文字列である。 例えば$1\in \left\{1,2,3\right\}$は真の命題で、$5\in \left\{1,2,3\right\}$は偽の命題である。 命題はしばしば$𝑃$や$𝑄$の文字が割り当てられ、命題の中に変数$𝑥$や$𝑦$がある場合は$𝑃\left(𝑥\right)$や$𝑄\left(𝑥,𝑦\right)$などと書かれる。 集合$𝑋$が与えられてその元$𝑥\in 𝑋$のうち命題$𝑃\left(𝑥\right)$が真になるようなものを集めて得られる集合を

$$\left\{𝑥\in 𝑋|𝑃\left(𝑥\right)\right\}$$

と記述する。 命題については次の節で詳しく述べる。

四つ目の集合の記法を説明するために写像の概念を導入する。 集合$𝑋$から集合$𝑌$への写像とは$𝑋$の各元$𝑥$に対して$𝑌$のただ一つの元$𝑦$を対応させる規則である。 この時の集合$𝑋$を写像の定義域、集合$𝑌$を写像の値域といい、値域$𝑌$が数の集合のとき写像は特に関数と呼ばれる。 写像を

$$𝐹:𝑋\to 𝑌$$

や$𝑥$を$𝑦$に対応させていることを明示する際は

$$𝐹:𝑥\in 𝑋\mapsto 𝑦\in 𝑌$$

のように記述する。 また、$𝑥$に対して対応する$𝑦$のことを$𝐹\left(𝑥\right)$と書き、写像$𝐹$のことを$𝐹\left(𝑥\right)$や$𝑦=𝐹\left(𝑥\right)$などと書くこともある。

四つ目の集合の記法はこの写像$𝐹$を使ったものであり、$𝑋$の各元$𝑥$を集合$𝑌$の元$𝐹\left(𝑥\right)$に対応させ集めた集合を

$$\left\{𝐹\left(𝑥\right)|𝑥\in 𝑋\right\}$$

と書く。 三つ目と四つ目の記法を同時に用いて

$$\left\{𝐹\left(𝑥\right)|𝑥\in 𝑋,𝑃\left(𝑥\right)\right\}$$

と記述することもある。

三つ目と四つ目の記法を合わせて内包記法という。 この内包記法を用いることで様々な集合を記述することができる。

元を一つも持たない集合を空集合といい$\varnothing$で表す。 元の個数が有限個の集合を有限集合といい、有限集合でない集合は無限集合と呼ぶ。

命題と論理

命題から次のようにして新しい命題を作る。

定義 1 (命題の演算)

命題$𝑃$, $𝑄$に対して以下を定める。

• $𝑃$, $𝑄$の両方が真のときのみ真とする命題を「$𝑃$かつ$𝑄$」といい$𝑃\wedge 𝑄$と表す。
• $𝑃$, $𝑄$の両方または片方が真のときのみ真とする命題を「$𝑃$または$𝑄$」といい$𝑃\vee 𝑄$と表す。
• $𝑃$が真のとき偽、偽のとき真とする命題を「$𝑃$でない」といい$\neg 𝑃$と表す。
• $𝑄$が真または$𝑃$が偽のときのみ真とする命題を「$𝑃$ならば$𝑄$」といい$𝑃⟹𝑄$と表す。
• $𝑃$, $𝑄$の真偽が一致するときのみ真とする命題を「$𝑃$と$𝑄$は同値」といい$𝑃⟺𝑄$あるいは$𝑃=𝑄$と表す。

このうち「$𝑃$ならば$𝑄$」の定義で$𝑃$が偽のときならばの命題は真としていることは不自然に思えるかもしれない。 例えば極端な例では「円周率が$3$ならば$1=0$」という命題は真ということになる。 命題$1=0$は偽なのでおかしく感じるかもしれないが、以降の数学の議論を行う上ではこのようにした方が都合がよい。 論理と言語の間にはすこし隙間があると考えるとよいかもしれない。

これらの命題の演算を表にまとめると以下になる。

$𝑃$	$𝑄$	$𝑃\wedge 𝑄$	$𝑃\vee 𝑄$	$\neg 𝑃$	$\neg 𝑄$	$𝑃⟹𝑄$	$𝑃=𝑄$
真	真	真	真	偽	偽	真	真
真	偽	偽	真	偽	真	偽	偽
偽	真	偽	真	真	偽	真	偽
偽	偽	偽	偽	真	真	真	真

表 1: 命題の演算

注意 2

命題$𝑃⟺𝑄$は$𝑃⟹𝑄$かつ$𝑄⟹𝑃$と同値である。

前節でも述べたように命題中に変数$𝑥$や$𝑦$がある場合は$𝑃\left(𝑥\right)$や$𝑄\left(𝑥,𝑦\right)$などと書かれる。 この変数付き命題から以下の新しい命題を作る。

定義 3 (全称と存在)

$𝑋$を集合として各元$𝑥\in 𝑋$に対して命題$𝑃\left(𝑥\right)$が与えられるとする。

• すべての$𝑥\in 𝑋$に対して命題$𝑃\left(𝑥\right)$が真であるときのみ真である命題を「任意の$𝑥\in 𝑋$に対して$𝑃\left(𝑥\right)$」といい$\forall 𝑥\in 𝑋,𝑃\left(𝑥\right)$と表す。
• 命題$𝑃\left(𝑥\right)$が真である$𝑥\in 𝑋$が一つでもあるときのみ真である命題を「ある$𝑥\in 𝑋$が存在して$𝑃\left(𝑥\right)$」といい$\exists 𝑥\in 𝑋,𝑃\left(𝑥\right)$と表す。

注意 4

$𝑋$が空集合のとき、命題「任意の$𝑥\in 𝑋$に対して$𝑃\left(𝑥\right)$」は真とする。

命題の演算の性質として以下が挙げられる。

命題 5 (命題の演算)

1. （結合法則）任意の命題$𝑃$, $𝑄$, $𝑅$に対して、$\left(𝑃\wedge 𝑄\right)\wedge 𝑅=𝑃\wedge \left(𝑄\wedge 𝑅\right)$と$\left(𝑃\vee 𝑄\right)\vee 𝑅=𝑃\vee \left(𝑄\vee 𝑅\right)$が成り立つ。
2. （交換法則）任意の命題$𝑃$, $𝑄$に対して、$𝑃\wedge 𝑄=𝑄\wedge 𝑃$と$𝑃\vee 𝑄=𝑄\vee 𝑃$が成り立つ。
3. （分配法則）任意の命題$𝑃$, $𝑄$, $𝑅$に対して、$𝑃\wedge \left(𝑄\vee 𝑅\right)=\left(𝑃\wedge 𝑄\right)\vee \left(𝑃\wedge 𝑅\right)$と$𝑃\vee \left(𝑄\wedge 𝑅\right)=\left(𝑃\vee 𝑄\right)\wedge \left(𝑃\vee 𝑅\right)$が成り立つ。
4. （二重否定）任意の命題$𝑃$に対して、$\neg \left(\neg 𝑃\right)=𝑃$が成り立つ。
5. （ド・モルガンの法則）任意の命題$𝑃$, $𝑄$に対して、$\neg \left(𝑃\wedge 𝑄\right)=\neg 𝑃\vee \neg 𝑄$と$\neg \left(𝑃\vee 𝑄\right)=\neg 𝑃\wedge \neg 𝑄$が成り立つ。
6. （背理法の原理）任意の命題$𝑃$, $𝑄$に対して、$\neg \left(𝑃⟹𝑄\right)=𝑃\wedge \neg 𝑄$が成り立つ。
7. （対偶）任意の命題$𝑃$, $𝑄$に対して、$𝑃⟹𝑄=\neg 𝑄⟹\neg 𝑃$が成り立つ。
8. 任意の命題$𝑃\left(𝑥\right)$に対して、$\neg \left(\forall 𝑥\in 𝑋,𝑃\left(𝑥\right)\right)=\exists 𝑥\in 𝑋,\neg 𝑃\left(𝑥\right)$が成り立つ。
9. 任意の命題$𝑃\left(𝑥\right)$に対して、$\neg \left(\exists 𝑥\in 𝑋,𝑃\left(𝑥\right)\right)=\forall 𝑥\in 𝑋,\neg 𝑃\left(𝑥\right)$が成り立つ。

背理法の原理にもとづいて命題$𝑃⟹𝑄$が真であることを示すために$𝑃\wedge \neg 𝑄$が偽であることつまり$𝑃$と$\neg 𝑄$を仮定して矛盾を導くことを示す証明法を背理法という。 また、命題$𝑃⟹𝑄$が真であることを示すために対偶$\neg 𝑄⟹\neg 𝑃$が真であることを示す証明法を対偶論法という。

集合の演算

集合と集合の関係で重要なものとして以下の包含がある。

定義 1 (集合の包含)

$𝐴$, $𝐵$を集合とする。

• 任意の$𝑥\in 𝐴$が$𝑥\in 𝐵$となっている時、集合$𝐴$は集合$𝐵$に含まれるあるいは集合$𝐴$は集合$𝐵$の部分集合であるといい$𝐴\subset 𝐵$あるいは$𝐵\supset 𝐴$と表す。
• $𝐴\subset 𝐵$かつ$𝐴\supset 𝐵$のとき、集合$𝐴$と集合$𝐵$は等しいといい$𝐴=𝐵$と表す。

集合と集合から以下の集合を定義する。

定義 2 (集合の演算)

$𝑋$を集合として、$𝐴$, $𝐵$をその部分集合とする。

• 集合$\left\{𝑥\in 𝑋|𝑥\in 𝐴\wedge 𝑥\in 𝐵\right\}$を$𝐴$と$𝐵$の共通部分といい$𝐴\cap 𝐵$と表す。
• 集合$\left\{𝑥\in 𝑋|𝑥\in 𝐴\vee 𝑥\in 𝐵\right\}$を$𝐴$と$𝐵$の和集合といい$𝐴\cup 𝐵$と表す。
• 集合$\left\{𝑥\in 𝑋|𝑥\in 𝐴\wedge 𝑥\notin 𝐵\right\}$を$𝐴$と$𝐵$の差集合といい$𝐴\backslash 𝐵$と表す。
• 特に集合$\left\{𝑥\in 𝑋|𝑥\notin 𝐴\right\}=𝑋\backslash 𝐴$を$𝐴$の補集合といい${𝐴}^{𝑐}$と表す。 この時の$𝑋$を全体集合と表現することがある。

命題の演算の性質に対応して集合の演算には次の性質がある。

命題 3 (集合の演算)

1. （結合法則）任意の集合$𝐴$, $𝐵$, $𝐶$に対して、$\left(𝐴\cap 𝐵\right)\cap 𝐶=𝐴\cap \left(𝐵\cap 𝐶\right)$と$\left(𝐴\cup 𝐵\right)\cup 𝐶=𝐴\cup \left(𝐵\cup 𝐶\right)$が成り立つ。
2. （交換法則）任意の集合$𝐴$, $𝐵$に対して、$𝐴\cap 𝐵=𝐵\cap 𝐴$と$𝐴\cup 𝐵=𝐵\cup 𝐴$が成り立つ。
3. （分配法則）任意の集合$𝐴$, $𝐵$, $𝐶$に対して、$𝐴\cap \left(𝐵\cup 𝐶\right)=\left(𝐴\cap 𝐵\right)\cup \left(𝐴\cap 𝐶\right)$と$𝐴\cup \left(𝐵\cap 𝐶\right)=\left(𝐴\cup 𝐵\right)\cap \left(𝐴\cup 𝐶\right)$が成り立つ。
4. 任意の集合$𝐴$に対して、${\left({𝐴}^{𝑐}\right)}^{𝑐}=𝐴$が成り立つ。
5. （ド・モルガンの法則）任意の集合$𝐴$, $𝐵$に対して、${\left(𝐴\cap 𝐵\right)}^{𝑐}={𝐴}^{𝑐}\cup {𝐵}^{𝑐}$と${\left(𝐴\cup 𝐵\right)}^{𝑐}={𝐴}^{𝑐}\cap {𝐵}^{𝑐}$が成り立つ。

写像の像と逆像

写像は集合の元を別の集合の元に対応させるものであるが、そこから発展させて部分集合を対応させることを考えることが今後必要になってくる。

定義 1 (写像の像と逆像)

$𝐹$を集合$𝑋$から集合$𝑌$への写像として、$𝐴$を$𝑋$の部分集合、$𝐵$を$𝑌$の部分集合とする。

• 集合$\left\{𝐹\left(𝑥\right)|𝑥\in 𝐴\right\}$は$𝑌$の部分集合であり$𝐴$の$𝐹$による像といい$𝐹\left(𝐴\right)$と表す。
• 集合$\left\{𝑥\in 𝑋|𝐹\left(𝑥\right)\in 𝐵\right\}$は$𝑋$の部分集合であり$𝐵$の$𝐹$による逆像といい${𝐹}^{-1}\left(𝐴\right)$と表す。

例 2

$𝑓\left(𝑥\right)={𝑥}^2$を考えると、

$$𝑓\left(\left\{0,1\right\}\right)=\left\{0,1\right\},𝑓\left(\left\{0,1,-1\right\}\right)=\left\{0,1\right\}$$

である。 また、

$${𝑓}^{-1}\left(\left\{0,1\right\}\right)=\left\{0,1,-1\right\},{𝑓}^{-1}\left(\left\{-1\right\}\right)=\varnothing$$

が成り立つ。

写像の像と逆像については以下の性質がある。 ただし、$𝐹$は集合$𝑋$から集合$𝑌$への写像である。

命題 3 (写像の像と逆像)

1. 任意の$𝑋$の部分集合${𝐴}_1,{𝐴}_2$に対して、${𝐴}_1\subset {𝐴}_2$ならば$𝐹\left({𝐴}_1\right)\subset 𝐹\left({𝐴}_2\right)$が成り立つ。
2. 任意の$𝑌$の部分集合${𝐵}_1,{𝐵}_2$に対して、${𝐵}_1\subset {𝐵}_2$ならば${𝐹}^{-1}\left({𝐵}_1\right)\subset {𝐹}^{-1}\left({𝐵}_2\right)$が成り立つ。
3. 任意の$𝑋$の部分集合${𝐴}_1,{𝐴}_2$に対して、$𝐹\left({𝐴}_1\cap {𝐴}_2\right)\subset 𝐹\left({𝐴}_1\right)\cap 𝐹\left({𝐴}_2\right)$が成り立つ。
4. 任意の$𝑋$の部分集合${𝐴}_1,{𝐴}_2$に対して、$𝐹\left({𝐴}_1\cup {𝐴}_2\right)=𝐹\left({𝐴}_1\right)\cup 𝐹\left({𝐴}_2\right)$が成り立つ。
5. 任意の$𝑌$の部分集合${𝐵}_1,{𝐵}_2$に対して、${𝐹}^{-1}\left({𝐵}_1\cap {𝐵}_2\right)=𝐹\left({𝐵}_1\right)\cap 𝐹\left({𝐵}_2\right)$が成り立つ。
6. 任意の$𝑌$の部分集合${𝐵}_1,{𝐵}_2$に対して、${𝐹}^{-1}\left({𝐵}_1\cup {𝐵}_2\right)=𝐹\left({𝐵}_1\right)\cup 𝐹\left({𝐵}_2\right)$が成り立つ。
7. 任意の$𝑋$の部分集合$𝐴$に対して、${𝐹}^{-1}\left(𝐹\left(𝐴\right)\right)\supset 𝐴$が成り立つ。
8. 任意の$𝑌$の部分集合$𝐵$に対して、$𝐹\left({𝐹}^{-1}\left(𝐵\right)\right)\subset 𝐵$が成り立つ。

このうち、三番目の性質については等号が成り立たない可能性があるので注意する。

例 4

$𝑓\left(𝑥\right)={𝑥}^2$, ${𝐴}_1=\left\{1\right\}$, ${𝐴}_2=\left\{-1\right\}$を考えると、 $𝑓\left(\left\{1\right\}\cap \left\{-1\right\}\right)=𝑓\left(\varnothing \right)=\varnothing$であるが、 $𝑓\left(\left\{1\right\}\right)\cap 𝑓\left(\left\{-1\right\}\right)=\left\{1\right\}\cap \left\{1\right\}=\left\{1\right\}$である。

逆写像

写像には可逆と呼ばれる特殊な扱いのできるものがある。

定義 1 (逆写像)

$𝐹$を集合$𝑋$から集合$𝑌$への写像とする。 集合$𝑌$から集合$𝑋$への写像$𝐺$であって、任意の$𝑥\in 𝑋$と$𝑦\in 𝑌$に対して

$$𝐺\left(𝐹\left(𝑥\right)\right)=𝑥,𝐹\left(𝐺\left(𝑦\right)\right)=𝑦$$

が成り立つとき、$𝐹$は可逆であるといい$𝐺$は$𝐹$の逆写像という。 また、逆写像$𝐺$を${𝐹}^{-1}$と表す。

つまり、

$${𝐹}^{-1}\left(𝐹\left(𝑥\right)\right)=𝑥,𝐹\left({𝐹}^{-1}\left(𝑦\right)\right)=𝑦$$

である。 逆写像は存在すれば一つしかない。 逆像も逆写像も同じ記号${𝐹}^{-1}$を用いるがそれぞれ集合の元と部分集合を当てはめて対象が違う概念である。 とはいえ可逆つまり逆写像がある写像に対しては${𝐹}^{-1}\left(\left\{𝑦\right\}\right)=\left\{{𝐹}^{-1}\left(𝑦\right)\right\}$という関係式が成り立つ。 ここで、左辺の${𝐹}^{-1}$は逆像であり右辺の${𝐹}^{-1}$は逆写像として用いられている。

可逆は全単射とも呼ばれ、次の特徴づけがある。

命題 2

集合$𝑋$から集合$𝑌$への写像$𝐹$が可逆であることは次の二つの条件が成り立つことと同値である。

1. （全射性）$𝐹\left(𝑋\right)=𝑌$である。 すなわち、任意の$𝑦\in 𝑌$に対してある$𝑥\in 𝑋$が存在して$𝐹\left(𝑥\right)=𝑦$が成り立つ。
2. （単射性）任意の$𝑦\in 𝑌$に対して$𝐹\left(𝑥\right)=𝑦$となる$𝑥\in 𝑋$は一意である。 すなわち、${𝑥}_1,{𝑥}_2\in 𝑋$が$𝐹\left({𝑥}_1\right)=𝐹\left({𝑥}_2\right)$を満たすならば${𝑥}_1={𝑥}_2$が成り立つ。

証明

$𝐹$が可逆の時、逆写像${𝐹}^{-1}$が存在する。 全射性を示すために$𝑦\in 𝑌$を取ると$𝑥={𝐹}^{-1}\left(𝑦\right)$とすることで$𝐹\left(𝑥\right)=𝐹\left({𝐹}^{-1}\left(𝑦\right)\right)=𝑦$である。 よって、$𝐹\left(𝑋\right)\supset 𝑌$なので$𝐹\left(𝑋\right)=𝑌$がいえた。 単射性を示すために$𝐹\left({𝑥}_1\right)=𝐹\left({𝑥}_2\right)$を満たす${𝑥}_1,{𝑥}_2\in 𝑋$を取ると${𝑥}_1={𝐹}^{-1}\left(𝐹\left({𝑥}_1\right)\right)={𝐹}^{-1}\left(𝐹\left({𝑥}_2\right)\right)={𝑥}_2$である。 以上より全射性と単射性が示された。

逆に$𝐹$が全射性と単射性を満たす時、$𝑦\in 𝑌$に対して$𝐹\left(𝑥\right)=𝑦$となる$𝑥$が一意に存在するのでそれを$𝐺\left(𝑦\right)$とおいて$𝑌$から$𝑋$への写像$𝐺$を定める。 この時、$𝐹\left(𝐺\left(𝑦\right)\right)=𝑦$であり$𝐺\left(𝐹\left(𝑥\right)\right)=𝐺\left(𝑦\right)=𝑥$なので、$𝐺$は$𝐹$の逆写像となっている。