集合論メモ

動機

• 数学に関する記事を作成していて、分量が増えたため分割。
• 公理のところは難しくて、とても精確に理解できているとはいえない。が、圏論に関連の深い箇所ではあるので、理解できる範囲で定義、定理などを残しておこうと思う。

集合論

定義 (集合 , Set)

ものの集まりを集合(Set)という。集合 $X$ の要素(「もの」のうちの一個) $x$ を元(element)と呼び, 元 $x$ が集合 $X$ に所属することを $x \in X$ と書く。
要素を含まない集合を空集合といい $\varnothing$ で表す。

$x \in X$
$\varnothing$

定義 (部分集合 , Subset)

集合 $A$ が集合 $B$ の部分集合であるとは, $\forall a \in A$ に対して常に $a \in B$ が成り立つことであり、 $A \subseteq B$ と書く。

$\forall a \in A$
$A \subseteq B$

定義 (和集合/差集合/補集合/積集合 , union/set difference/complement/intersection)

(1) 集合$A,B$の和集合
　$A \cup B = \{ x | x \in A \lor x \in B \}$
(2) 集合$A,B$の積集合（または共通部分、交わり）
　$A \cap B = \{ x | x \in A \land x \in B \}$
(3) 集合$A,B$の差集合
　$A \setminus B = A - B = \{ x | x \in A \land x \notin B \}$
(4) $U$ を全体集合とし $A \subseteq U$ とする。$U$から$A$の元を除外して得られる集合を$A$の補集合とよぶ
　$A^c = \{ x | x \in U \land x \notin A \}$

$A \cup B = \\{ x | x \in A \lor x \in B \\}$
$A \cap B = \\{ x | x \in A \land x \in B \\}$
$A \setminus B = A - B = \\{ x | x \in A \land x \notin B \\}$
$A^c = \\{ x | x \in U \land x \notin A \\}$

定義 (集合族 , Family)

元がすべて集合となっているような集合を、集合族（集合の族）という。
$\{ S_{\lambda} \}_{\lambda \in \Lambda}$ のように書く。
たとえば$A, B, C$ を集合とすると、集合 $ \{ A, B, C \} $ は集合族である。

$\\{ S_{\lambda} \\}_{\lambda \in \Lambda}$ 
$ \\{ A, B, C \\} $

定義 (集合族の和)

$\underset{\lambda \in \Lambda}{ \cup } S_{\lambda} = \{ x \: | \: \exists \lambda \in \Lambda \; s.t. \; x \in S_{\lambda} \}$

$\underset{\lambda \in \Lambda}{ \cup } S_{\lambda} = \\{ x \\: | \\: \exists \lambda \in \Lambda \\; s.t. \\; x \in S_{\lambda} \\}$

定義 (写像 , Mapping)

$X,Y$を集合とする。
このとき、任意の $x \in X$ に対して、ただ一つの $y \in Y$ を対応させる規則を写像 $ f : X \rightarrow Y $ と呼ぶ。$X$ を写像 $f$ の定義域、 $Y$ を $f$ の値域という。

$ f : X \rightarrow Y $

定義 (集合の元の個数)

集合 $X$ の元の個数を $|X|$ と表す。

$|X|$

定義 (べき集合 , power set)

集合 $X$ のべき集合 $2^X$ とは $X$ の部分集合全体からなる集合である。
$2^X = \{ Aは集合 \: | \: A \subseteq X \}$

ここで $Y^X$ は以下を表す
$Y^X = \{ 写像 f : X \rightarrow Y \: | \: X, Yは集合 \}$

上記の $2^X$ は、写像で写った先が「2」だからということになるが、この2とは何なのかというと、集合 $\{0, 1 \}$ の元の個数と考えるとわかりやすい。

集合 $X$ のすべての元に $\{0, 1 \}$ つまり無または有を対応させる写像を考えると、この対応の仕方の全組み合わせを考えると集合 $X$ の部分集合がすべて取り出せる。
この対応の仕方の全組み合わせは重複順列と考えられるので、集合 $X$ の部分集合の元の個数は2の $|X|$ 乗個になる。

$2^X = \\{ Aは集合 \\: | \\: A \subseteq X \\}$

定義 (単射 , injection)

$X , Y$を集合とする。写像 $f : X \rightarrow Y$ が単射であるとは以下を満たすことである。
$\forall x_1 , x_2 \in X \: , \: f(x_1) = f(x_2) \Rightarrow x_1 = x_2 $

$\forall x_1 , x_2 \in X \\: , \\: f(x_1) = f(x_2) \Rightarrow x_1 = x_2 $
スペースの調整　\\:

定義 (全射 , surjection)

$X , Y$を集合とする。写像 $f : X \rightarrow Y$ が全射であるとは以下を満たすことである。
$\forall y \in Y , \exists x \in X \, s.t. \, y = f(x) $

$\forall y \in Y , \exists x \in X \, s.t. \, y = f(x) $
スペースの調整　\,

定義 (全単射 , bijection)

$X , Y$を集合とする。写像 $f : X \rightarrow Y$ が全単射であるとは $f$ が全射かつ単射であることである。

定義 (順序対 , ordered pair )

$X,Y$ を集合とする。 $x \in X , y \in Y$ とするとき、 以下のような集合 $(x, y)$ を順序対という。
$(x , y) = \{ \{ x \} , \{ x , y \} \}$
(順序対には、いくつかの定義方法があるが、これはクラトフスキーの定義。)

命題 (順序対の性質)

$(x , y) = (p , q) \quad \Leftrightarrow \quad (x = p) \land (y= q)$
並んでいる順序を変えると別のものになる、ということ。

(proof)
$(x , y) = (p , q)$ とすると $(x, y) \subseteq (p, q)$ かつ $(p, q) \subseteq (x, y)$である。
この時 $\{ \{ x \} , \{ x , y \} \} \subseteq \{ \{ p \} , \{ p , q \} \}$ かつ $\{ \{ p \} , \{ p , q \} \} \subseteq \{ \{ x \} , \{ x , y \} \}$ であるため
$\{ x \} = \{ p \}$から$x = p$ であり、 $\{ x , y \} = \{ p , q \}$ から $y = q$。
$\therefore (x = p) \land (y= q)$

逆に $(x = p) \land (y= q)$ とすると $(x , y) = (p , q)$ は自明。 $\blacksquare$

$(x , y) = (p , q) \quad \Leftrightarrow \quad (x = p) \land (y= q)$
スペースの調整　\quad
\therefore
\blacksquare

定義 (直積集合 , Direct Product)

集合族に対し、各集合から元を取り出して組としたものは、それを元として集合とすることができる。
$X,Y$を集合とする。このとき、任意の $x \in X , y \in Y$ の組(順序対)すべてからなる集合 $X \times Y = \{ \: (x, y) \: | \: x \in X , y \in Y \} $ を、 $X$ と $Y$ の直積という。

$X \times Y = \\{ \\: (x, y) \\: | \\: x \in X , y \in Y \\} $
スペースの調整 \\, , \\: , \\; , \quad

定義 (関係 , Relation)

集合 $A, B$ の直積 $A \times B$ の部分集合 $R$ を二項関係という。
特に集合が同じ場合、つまり $A = B$ のときに $R$ を $A$ 上の関係という。

$A \times A$の元 $(a, b)$ が関係 $R$ に属するとき、 $aRb$ と書く。
$(a, b) \in R \, \Leftrightarrow \, aRb \; \Leftrightarrow \; a, bはRの関係にある$

$(a, b) \in R \\, \Leftrightarrow \\, aRb \\; \Leftrightarrow \\; a, bはRの関係にある$

定義 (同値関係 , Equivalence relation)

集合 $A$ 上の関係 $R$ が以下をみたすとき、 $R$ は同値関係であるという。
(1)反射律 $\forall a \in A \Rightarrow (a,a) \in R$
(2)対称律 $\forall a, b \in A \: , \: (a,b) \in R \Rightarrow (b,a) \in R$
(3)推移律 $\forall a, b, c \in A \: , \: (a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R $

$\forall a, b, c \in A , (a, b) \in R \land (b, c) \in R \Rightarrow (a, c) \in R $

定義 (同値類 , Equivalence class)

$R$ を集合 $A$ 上の関係とする。このとき、$a \in A$ に対し集合
$[a]_{R} = \{ \: x \in A \: | \: (a, x) \in R \: \} $
を、集合 $a$ の関係 $R$ による同値類という。
$a$ を同値類 $[a]_R$ の代表元という。

$[a]\_{R} = \\{ \\: x \in A \\: | \\: (a, x) \in R \\: \\} $

定義 (商集合 , Quotient set)

集合 $A$ の同値関係を $R$ とする。このとき、すべての同値類の集合
$\{ \: [a]_R \: | \: a \in A \: \}$ を 集合 $A$ の同値関係 $R$ による商集合 $A/R$ と呼ぶ。

$A/R = \{ \: [a]_R \: | \: a \in A \: \} = \{ \: \{ x \in A | (a,x) \in R \} \: | \: a \in A \: \}$
同値類 $[a]_R$ は集合なので、商集合は集合の族である。

$A/R = \\{ \\: [a]\_R \\: | \\: a \in A \\: \\}$

定義 (前順序集合)

$X$ を集合、$\leq$ を $X$ 上で定義された二項関係 (つまり$X \times X$の部分集合) とする。
関係 $\leq$ が次の(1),(2)を満たすとき $\leq$ を$X$上の前順序という。
またこのとき、$(X, \leq)$を前順序集合といい、$X$は台または台集合と呼ばれる。
(1) 反射律
$\forall x \in X \: , \: x \leq x$
(2) 推移律
$\forall x, y, z \in X \: , \: (x \leq y) \land (y \leq z) \Rightarrow x \leq z$

$\forall x \in X \\: , \\: x \leq x$
$\forall x, y, z \in X \\: , \\: (x \leq y) \land (y \leq z) \Rightarrow x \leq z$

定義 (半順序集合)

$X$ を集合、$\leq$ を $X$ 上で定義された二項関係 ($X \times X$の部分集合) とする。
関係 $\leq$ が前順序かつ(3)を満たすとき $\leq$ を$X$上の半順序という。
またこのとき、$(X, \leq)$を半順序集合といい、$X$は台または台集合と呼ばれる。
(3) 反対象律
$\forall x, y \in X \: , \: (x \leq y) \land (y \leq x) \Rightarrow x = y$

$\forall x, y \in X \\: , \\: (x \leq y) \land (y \leq x) \Rightarrow x = y$

定義 (全順序集合)

$X$ を集合、$\leq$ を $X$ 上で定義された二項関係 ($X \times X$の部分集合) とする。
関係 $\leq$ が半順序かつ(4)を満たすとき $\leq$を$X$上の全順序という。
またこのとき、$(X, \leq)$を全順序集合といい、$X$は台または台集合と呼ばれる
(4) 全順序律
$\forall x, y \in X \: , \: (x \leq y) \lor (y \leq x)$

$\forall x, y \in X \\: , \\: (x \leq y) \lor (y \leq x)$

定義 (鎖 , chain)

$X$ を集合、$\leq$ を $X$ 上で定義された二項関係 ($X \times X$の部分集合) とする。
集合と全順序を組みにしたもの $(X, \leq)$ を鎖という

定義 (上界, upper bound, 下界 , lower bound)

$(X, \leq)$を半順序集合とし、$A$をその部分集合とする。
(1) $x \in X$が$A$の上界 $\Leftrightarrow \: \forall y \in A , y \leq x$
(2) $x \in X$が$A$の下界 $\Leftrightarrow \: \forall y \in A , x \leq y$

定義 (最大元 , muximum, 最小元, minimum)

$(X, \leq)$を半順序集合とし、$A$をその部分集合とする。
(1) $x \in X$が$A$の最大元 $\max A \: \Leftrightarrow \: (x \in A) \land (xはAの上界)$
(2) $x \in X$が$A$の最小元 $\min A \: \Leftrightarrow \: (x \in A) \land (xはAの下界)$

定義 (上限 , supremum , 下限 , infimum)

$(X, \leq)$を半順序集合とし、$A$をその部分集合とする。
(1) $x \in X$が$A$の上限 $\sup A \: \Leftrightarrow \: x = \min \{ x \in X | xはAの上界 \}$
(2) $x \in X$が$A$の下限 $\inf A \: \Leftrightarrow \: x = \max \{ x \in X | xはAの下界 \}$

定義 (極大元 , maximal element, 極小元 , minimal element)

$(X, \leq)$を半順序集合とし、$A$をその部分集合とする。
(1) $x \in X$が$A$の極大元 $\Leftrightarrow \: (x \in A) \land \lnot(\exists y \in A \: s.t. \: (y > x) $
(2) $x \in X$が$A$の極小元 $\Leftrightarrow \: (x \in A) \land \lnot(\exists y \in A \: s.t. \: (y < x) $

$ (x \in A) \land \lnot(\exists y \in A \\: s.t. \\: (y > x) $

定義　(有限集合、無限集合)

ある自然数$n \in \mathbb{N}$ に対して、集合 $\{ 1, 2, ... , n \}$との間に全単射写像が存在する集合を有限集合といい、そうでない集合は無限集合という。

感覚的には、数えることができる集合で有限なものが有限集合で、数えられる（自然数全体と対応づけできる、という意味）が無限なものが可算無限集合、そのどちらでもないもの（無限かつ数えられない）が非加算無限集合である。

公理、基礎論

昔、松坂の集合論の教科書でツォルンの補題のあたりをいろいろ勉強したはずだが、すっかり忘れているようである。。なお、このあたりについて興味ある部分は書いておこうと思うが、数学に関する一連のメモ記事はあくまで他の記事を理解したり興味をもつための取っ掛かりに過ぎないため、あまり深追いはしない方針としておく。

公理 (ツェルメロ=フレンケルの公理系 , ZF:Zermelo-Fraenkel)

ZF公理系とは、以下の公理からなるもの。
(1) 外延性
　集合 $A, B$ が同じ要素を持つなら集合 $A$, $B$は等しい。
　$\forall A , \forall B , ( \forall x , x \in A \Leftrightarrow x \in B ) \Rightarrow A = B$
(2) 空集合
　要素を持たない集合が存在する
　$\exists A \: s.t. \: \forall x \: (x \notin A) $
(3) 対の公理
　任意の要素 $x,y$ に対し $x,y$ のみを要素とする集合 $A$ が存在する
　$\forall x,y \: \exists A \: s.t. \: \forall t (t \in A \Leftrightarrow (t = x \lor t = y))$
(4) 和集合
　任意の集合 $X$ に対して $X$ の要素全体からなる集合 $A$ が存在する
　$\forall X \: \exists A \: s.t. \: \forall t (t \in A \Leftrightarrow \exists x \in X (t \in x))$
(5) 無限公理
　以下のような集合が存在する。
　(5-1) 空集合を要素として持つ
　(5-2) 任意の要素 $x$ に対して $x \cup \{x\}$ も要素に持つ
(6) 冪集合の公理
　任意の集合 $X$ に対して $X$ の部分集合全体の集合 $2^{X}$ が存在する
(7) 置換公理
　関数クラスによる集合の像は集合である
(8) 正則性公理
　空でない集合は、自分自身と交わらない要素を必ず持つ

公理 (選択公理 , Axiom of choice)

$X$ を集合の集合とし $X$ の要素は互いに交わらないような空ではない集合であるとする。
このとき $X$ の各要素から1つずつ要素を選択した集合（選択集合）が存在する。

補題 (ツォルンの補題)

$X$ を半順序集合とし、その全ての鎖(= 全順序部分集合)が $X$ に上界を持つとする。
このとき $X$ は少なくともひとつの極大元を持つ。
ZF集合論では、この補題は選択公理と同値である。

公理 (ZFC , Zermelo-Fraenkel set-theory with axiom of choice)

ZFに選択公理を加えた公理系を、ZFCという。
集合論は、このZFCをベースに構築されている。

定義 (基数 , cardinal number)

定義 (到達不能基数)

定義 (グロタンディーク宇宙 , Grothendieck Universe)

次の性質をもつ集合 $U$ をUniverseという。
(1) $x \in y \, , \, y \in U \: \Rightarrow \: x \in U$
(2) $x , y \in U \: \Rightarrow \{x,y\} \in U$
(3) $\forall X \in U , 2^X \in U$
(4) $I \in U , f: I \rightarrow U , \: f(i)=u_i \: (i \in I, u_i \in U) \: \Rightarrow \cup_{i \in I} u_i = \cup_{i \in I} f(i) \in U \: $

上記から $U$ の例として $\varnothing$ がある。($\varnothing \in U$)

定義 (小さい集合)

ユニバース $U$ の要素となっている集合を、小さい集合と呼ぶ。これは、公理的集合論を習うときに出てくるような、いわゆる普通の集合と思えばよさそうである。

定義 (クラス)

Universe $U$ の任意の部分集合をクラスと呼ぶ。
小さな集合はクラスだが、小さな集合ではないクラスもある。これを真のクラスという。

圏論と公理系の関連

圏論では、公理としてuniverseというものの存在を仮定して圏を定義することがある。
このuniverseは大きすぎない集合の範囲で圏論を展開するために導入しており、（したがってフォンノイマン宇宙ではなく）グロタンディーク宇宙を想定している。

だが、このグロタンディーク宇宙の存在は強到達不能基数の存在と同値であることが示されており、かつこの基数の存在はZFCからは証明できないことも示されている。したがって、公理系 ZFC からはこの宇宙の存在を証明できない。

定義 (整礎的集合)

定義 (整礎集合の階数, rank)

定義 (順序数)

定義 (累積的階層)

定義 (フォンノイマン宇宙)

グロタンディーク宇宙とフォンノイマン宇宙の関連

以下のような性質から関連はしているはずだが、関連性はまだ正確に私が理解できていない。

• グロタンディーク宇宙の例として、空集合と、すべての遺伝的有限集合の集合 $V_{\omega}$がある。
• 遺伝的有限集合のクラスは、フォンノイマン宇宙の部分クラスである。

以上