私はZFC公理系から

この記事は B4UT Advent Calendar 2020 12/8 に登録されています。 b4utmzi.wixsite.com

はじめに

東大数学サークルB4UT 代表のじょーどです。

鳩の巣原理とは、「 $n$ 個の物を $m$ 個のグループに振り分けるとき、 $n > m$ ならばどこかで重複が発生している」という内容の定理です。「10羽の鳩を9個の箱に重複なく収めることは出来ない」という例えが有名であることから名がついています。

この定理を集合論のことばで記述します。有限集合 $X$ の要素の個数は濃度 $|X|$ に一致*1しますから、

集合 $P,B$ に対し, $|P| > |B| \Rightarrow$ 単射 $f : P \rightarrow B$ は存在しない

と書き表すことができます*2。この対偶は

集合 $P,B$ に対し,単射 $f: P \rightarrow B$ が存在する $\Rightarrow |P| \leq |B|$

となります。

この記事の目標は、 ZFC公理系から出発して順序数と濃度の定義(の一つ)を述べ、上に示した定理を証明することです。個人的な興味と知識の確認を目的として執筆されているため、エンタメ的な面白さはあまり考慮していません。

第1章 ZFC公理系

§1 基本的な約束

一階述語論理における諸般の概念を前提とする.
- 特に記号系として変数 $,\lnot,\land,\lor,\rightarrow,\leftrightarrow,\forall,\exists,$ 括弧を用いる.
- ただし高度な知識は要しない.
基本的述語記号はの2つのみとする.
- これらから定義できる一般的な記号については,定義を述べずに用いる場合がある.
などの変数は全て集合を表すとする(集合一元論).
- 特に集合の元はそれ自体集合であることに留意する.

§2 ZFCの公理

(1) 外延性公理(Extensionality)

$\displaystyle{ \forall x \forall y (x=y \leftrightarrow \forall z (z\in x \leftrightarrow z\in y)) }$

Remark この公理によって、「2つの集合 $x,y$ が等しい」とはその中身が全く同じであることだと定められている.
(1)より=の

反射性: $a=a$
対称性: $a=b\leftrightarrow b=a$
推移性: $a=b \land b=c \rightarrow a=c$

が従う.

(2) 削除

(3) 空集合(Nullset)

$\displaystyle{ \exists x \forall y (y\notin x) }$

Remark 中に何も含まない集合 $x$ の存在を保証している.
(1)より $x _ 1$ と $x _ 2$ が(3)を満たすならば $x _ 1 = x _ 2$ .
従って空集合 $\varnothing$ は一意的である. 以下でも同様に一意性が言えることがあるが,いちいち断らない.

(4) 対(Pair)

$\displaystyle{ \forall x \forall y \exists z \forall w (w\in z \leftrightarrow w=x \lor w=y) }$

Remark 「元を好き勝手に集めたもの」は一般には集合にならない.
例えば「『自分自身を元に持たない集合』全体の集合」 $X$ ,すなわち

$\displaystyle{ X := \{ x | x \notin x \} }$

が存在することを認めれば, $X \in X$ であっても $X \notin X$ であっても矛盾が生じる*3. このような問題を回避したければ,「物の集まり」のうちあまりにも大きなものは集合と認めてはならない.
この公理系の意味するところは,公理系で認めた「対」「合併」「べき集合」などの操作から得られるものだけを集合と認め,議論の対象にしようということである.
集合とは限らない,単なる集まりのことはクラスと呼んで区別する. 特に,集合でないクラスのことを真のクラスという.

Remark/Definition (4)は任意の2元 $x,y$ に対し*4, $x$ と $y$ のみを元に持つ集合 $z$ が存在することを述べている.
多少意訳すれば,この公理は「2つの集合をペアにしたものは,再び集合になる」というルールを定めていると理解できる.(5)(6)(7)なども同じように理解するのが良い.
(1)より $z$ は一意的なので,これを $\{ x,y \}$ と書く.

Definition 集合 $a$ に対し, $\{a\}:=\{ a,a \}$ .

Definition(順序対) $\langle a,b \rangle:=\{ a,\{a,b\} \}$ .

Proposition $\langle a,b \rangle = \langle a',b' \rangle \leftrightarrow a=a' \land b=b'$ .

(5) 合併(Sum Set,Union)

$\displaystyle{ \forall x \exists y \forall z (z\in y \leftrightarrow \exists t (z\in t \land t\in x)) }$

Remark/Definition $y$ は $x$ の元である集合たちの合併のことであると考えられる.
(1)より $y$ は一意的なので,これを $\bigcup x$ と書く.

Definition(包含) $a\subseteq b \leftrightarrow \forall z (z\in a\rightarrow z\in b)$
$a\subsetneq b \leftrightarrow a\subseteq b \land a \neq b$

(6) べき集合(Power Set)

$\displaystyle{ \forall x \exists y \forall z (z\in y \leftrightarrow z\subseteq x) }$

Remark $y$ は集合 $x$ の部分集合を全て集めたものなので,べき集合のことであると考えられる.

(7) 置換公理(Replacement)

論理式 $\psi (x,y)$ に対して

$\begin{aligned} &\forall x \forall y \forall z (\psi(x,y)\land \psi(x,z)\rightarrow y=z) \\ \rightarrow &\forall u \exists v \forall r (r\in v \leftrightarrow \exists s (s\in u \land \psi(s,r))) \end{aligned}$

(8) 正則性公理(Regularity)

$\displaystyle{ \forall x (x\neq \varnothing \rightarrow \exists y (y\in x \land y\cap x =\varnothing)) }$

(9) 無限公理(Infinity)

$\displaystyle{ \exists x (\varnothing \in x \land \forall y (y\in x \rightarrow y\cup \{ y \} \in x)) }$

Definition

$\begin{aligned} & \mathrm{Fnc}(f,a,b)\\ \leftrightarrow & f \subseteq a\times b \land \forall u (u\in a\rightarrow \exists ! w(\langle u,w \rangle \in f)) \end{aligned}$

と定義し,さらに $\langle t,s \rangle \in f\leftrightarrow f(t)=s$ によって $f(t)\in b$ を定める.
これは関数 $f:a\rightarrow b$ *5のことであると考えられる.

(10) 選択公理(Axiom of Choice)

$\begin{aligned} & \forall x \exists f \\ & (\mathrm{Fnc}\left(f,x,\bigcup x\right) \land \\ & \forall y (y\in x \land y\neq \varnothing \rightarrow f(y)\in y)) \end{aligned}$

Remark 各 $y\in x$ から元 $f(y)\in y$ を一つずつ選んでくるような関数 $f:x\rightarrow \bigcup x$ の存在を保証する.

§3 正則性公理による帰結

Theorem 1.3.1

$\mathrm{(1)} \quad \forall a (a \notin a)\\ \mathrm{(2)} \quad \forall a_1 \forall a_2 \dots \forall a_n \\ \qquad \lnot(a_1\in a_2 \land \dots \land a_{n-1}\in a_n \land a_n \in a_1) \\$

(proof)
(1)
$a\in a$ なる $a$ が存在したとすると, $x=\{ a \}$ は正則性公理を満たさない.
(2)
$a_1\in a_2 \land \dots \land a_{n-1}\in a_n \land a_n \in a_1$ を仮定する.
$x=\{ a_1,a_2,\dots a_n \}$ とすると,

$\begin{aligned} \begin{cases} a_1 \cap x\ni a_n \\ a_i \cap x \ni a_{i-1} (2\leq i \leq n) \end{cases} \end{aligned}$

より $x$ は正則性公理を満たさない.

第2章順序集合

§1 反射型順序による定義

Definition 集合 $X$ 上の二項関係 $R$ が以下の条件を満たすとき, $R$ は $X$ 上の(反射型)順序であるといい, $(X,R)$ を順序集合という.

$\begin{aligned} \mathrm{(1)} & \text{(反射性)} \forall x \in X (xRx) \\ \mathrm{(2)} & \text{(反対称性)} \forall x,y \in X (xRy \land yRx \rightarrow x=y) \\ \mathrm{(3)} & \text{(推移性)} \forall x,y,z \in X (xRy \land yRz \rightarrow xRz) \end{aligned}$

$xRy$ の代わりに $x \leq _ R y$ または単に $x \leq y$ と書くことが多い.

Definition 順序集合 $(X,R)$ 上の二項関係 $<$ を以下で定義する.

$\displaystyle{ x < y \leftrightarrow x \leq y \land x \neq y }$

Proposition 上で定義した二項関係 $<$ は以下の条件を満たす.

$\begin{aligned} \mathrm{(1)} & \forall x \in X \lnot (x < x) \\ \mathrm{(2)} & \forall x,y,z \in X (x < y \land y < z \rightarrow x < z) \end{aligned}$

§2 非反射型順序による定義

Definition 集合 $X$ 上の二項関係 $R$ が以下の条件を満たすとき, $R$ は $X$ 上の(非反射型)順序であるといい, $(X,R)$ を順序集合という.

$\begin{aligned} \mathrm{(1)} & \text{(非反射性)} \forall x \in X \lnot (x < x) \\ \mathrm{(2)} & \text{(推移性)} \forall x,y,z \in X (x < y \land y < z \rightarrow x < z) \end{aligned}$

$xRy$ の代わりに $x < _ R y$ または単に $x < y$ と書くことが多い.

Definition 順序集合 $(X,R)$ 上の二項関係 $\leq$ を以下で定義する.

$\displaystyle{ x \leq y \leftrightarrow x < y \lor x = y }$

Proposition 上で定義した二項関係 $\leq$ は以下の条件を満たす.

$\begin{aligned} \mathrm{(1)} & \forall x \in X (x \leq x) \\ \mathrm{(2)} & \forall x,y \in X (x \leq y \land y \leq x \rightarrow x=y) \\ \mathrm{(3)} & \forall x,y,z \in X (x \leq y \land y \leq z \rightarrow x \leq z) \end{aligned}$

上で見たように,順序集合を定義する際は, 反射型順序 $\leq$ から出発しても, 非反射型順序 $\lt$ から出発しても, 同等の結果が得られる.
今後は順序関係 $R$ は上のどちらか一方で定義されているものとし, 断りなく $\leq$ および $\lt$ を用いる.

§3 順序集合に関する基本的概念

Definition(全順序) 順序集合 $(X,R)$ が以下の同値な条件を満たすとき, $R$ は全順序であるといい, $(X,R)$ は全順序集合であるという.

$\displaystyle{ \forall x,y \in X (x \leq y \lor y \leq x) }$

あるいは

$\displaystyle{ \forall x,y \in X (x < y \lor x=y \lor y < x) }$

このとき, 単に「 $\leq$ (あるいは $<$ )は全順序である」ということもある.

Definition(最小元) 順序集合 $(X,R)$ の元 $x$ が $\forall y \in X (x \leq y)$ を満たすとき, $x$ を $X$ の最小元という.

Definition(始切片) 順序集合 $(X,R)$ と $a \in X$ に対し,

$\displaystyle{ X(a) := \{ x \in X | x < a \} }$

を $a$ による $X$ の始切片という.

Definition(順序保存写像,順序同型写像) 2つの順序集合 $(X,R) , (Y,S)$ と写像 $f : X \rightarrow Y$ が

$\displaystyle{ \forall x,y \in X(x \leq _ R y \rightarrow f(x) \leq _ S f(y)) }$

を満たすとき, $f$ は順序保存写像であるという.
さらに $f$ が全単射で逆写像 $f ^ {-1} : Y \rightarrow X$ も順序保存写像であるとき, $f$ は順序同型写像であるという.
$X$ と $Y$ の間に順序同型写像 $f : X \rightarrow Y$ が存在するとき, $X$ と $Y$ は順序同型であるといい, $X \simeq Y$ とかく.

Remark $\simeq$ は同値関係である. すなわち,以下の3つの性質が成り立つ.

$\begin{aligned} \mathrm{(1)} & \forall X (X \simeq X) \\ \mathrm{(2)} & \forall X,Y (X \simeq Y \leftrightarrow Y \simeq X) \\ \mathrm{(3)} & \forall X,Y,Z (X \simeq Y \land Y \simeq Z \rightarrow X \simeq Z) \end{aligned}$

Remark 2つの全順序集合の間の全単射な順序保存写像は,順序同型写像である.

§4 整列集合

Definition(整列集合) 順序集合 $(X,R)$ の任意の空でない部分集合が最小元を持つとき, $(X,R)$ は整列集合であるという.

Theorem 2.4.1 整列集合 $(X,R)$ は全順序である.

(proof)
$x,y\in X$ を任意にとると, 仮定より $\{x,y \} \subseteq X$ は最小元を持つので, $x \leq y$ または $y\leq x$ が成り立つ.

Theorem 2.4.2 $(X,R)$ を整列集合, $f : X \rightarrow X$ を順序保存写像とすると,

$\displaystyle{ \forall x \in X , x \leq f(x) }$

(proof)
$E : = \{ x\in X | f(x) < x \}$ が空でないと仮定する.
$X$ は整列集合なので, $X$ の部分集合 $E$ は最小元 $x _ 0$ を持つ. このとき $f(x _ 0) < x _ 0$ であるが, $f$ は順序を保つから $f(f(x _ 0)) < f(x _ 0)$ .
従って $f(x _ 0) \in E$ であるが,これは $x _ 0$ の最小性に矛盾する.

Corollary 整列集合 $(X,R)$ から自身への順序同型写像は恒等写像に限る.

Corollary 2つの整列集合の間の順序同型写像は高々一つしか存在しない.

Lemma 整列集合 $(X,R)$ と任意の $a \in X$ に対し,

$\displaystyle{ X \not \simeq X(a) }$

(proof)
$X \simeq X(a)$ とすると, 順序同型写像 $f : X \rightarrow X(a)$ が存在する.
このとき $f(a) \in X(a) = \{ x < a \}$ であるから $f(a) < a$ .
これはThm 2.4.2に矛盾する.

Theorem 2.4.3 整列集合 $(X,R)$ と任意の $a,b \in X$ に対し,

$\displaystyle{ a \neq b \rightarrow X(a) \not \simeq X(b) }$

(proof)
$a < b$ としてよい. $X(a)$ は整列集合 $X(b)$ の $a \in X(b)$ による始切片なので, 上のLemmaから主張が従う.

Theorem 2.4.4 $(X,R),(Y,S)$ を2つの整列集合とする.
$(X,R)$ の任意の始切片が $(Y,S)$ のある始切片に順序同型ならば, $(X,R)$ は $(Y,S)$ あるいはそのある始切片に順序同型である.

(proof)

$\displaystyle{ f : = \{ \langle x,y \rangle \in X \times Y | X(x) \simeq Y(y) \} }$

と定義する. これは単射 $f : X\rightarrow Y$ を定める.
実際,仮定より定義域は $X$ 全体であり, Thm 2.4.3より $f$ が写像であることと単射性が分かる.

$f$ が順序保存写像であることを示す.
$x < x'$ なる $x,x' \in X$ をとる. $f$ の定義より

$\begin{cases} X(x) \simeq Y(f(x) ) \\ X( x ' ) \simeq Y(f( x ' ) ) \end{cases}$

従って $X(x)$ と $Y(f(x))$ の間には順序同型写像 $g : X(x) \rightarrow Y(f(x))$ が存在する.
もし $f(x) > f(x')$ であるとすると,

$\begin{aligned} & X(x') \\ \simeq & Y(f(x'))\\ = & Y(f(x)) \text{の} f(x') \text{による始切片} (\because f(x)>f(x'))\\ \simeq & X(x) \text{の} g^{-1}(f(x')) \text{による始切片} \\ = & X(x') \text{の} g^{-1}(f(x')) \text{による始切片} (\because x' > x) \end{aligned}$

となり, $X(x')$ が自身の始切片と順序同型になるので矛盾.
もし $f(x) = f(x')$ であるとすると,

$\displaystyle{ X(x) \simeq Y(f(x)) = Y(f(x')) \simeq X(x') }$

より $x = x'$ となり $x,x'$ のとり方に矛盾.
$Y$ は整列集合だから特に全順序である. よって $f(x) < f(x')$ であり, $f$ は順序保存写像である.

更に, $y \in \mathrm{Im} f \rightarrow \forall y' < y (y' \in \mathrm{Im} f)$ が成り立つ.
実際 $y' < y$ とすれば, $y \in \mathrm{Im} f$ より $\exists x \in X (f(x)=y)$ .
$f$ の定義から順序同型写像 $g : X(x) \rightarrow Y(y)$ が存在するので, 順序同型 $X(g ^ {-1} (y')) \simeq Y(y')$ が成り立つ.
従って $f(g ^ {-1} (y'))=y'$ であり, $y' \in \mathrm{Im} f$ .

$f$ が全射でなければ, $y _ 0$ を $Y \backslash \mathrm{Im} f$ の最小元とすると, 上で示した性質から $\mathrm{Im} f = Y(y _ 0)$ となる.
$f$ は2つの整列集合 $(X,R),(Y(y _ 0),S)$ の間の全単射な順序保存写像なので, 順序同型写像である. 従って $X \simeq Y(y _ 0)$ .
$f$ が全射なら $\mathrm{Im} f = Y$ であるから, 上と同様にして $X \simeq Y$ .
以上で主張を得た.

Theorem 2.4.5(整列集合の比較定理) $(X,R),(Y,S)$ を2つの整列集合とする. このとき,次の(a)~(c)のうち1つだけが必ず成立する.

$\begin{aligned} \mathrm{(a)} & X \simeq Y \\ \mathrm{(b)} & \exists y \in Y , X \simeq Y(y) \\ \mathrm{(c)} & \exists x \in X , X(x) \simeq Y \end{aligned}$

(proof)
整列集合は自身の始切片と同型でないから,2つ以上が成り立たないことが分かる.

以下1つは成り立つことを示す.(c)が成り立つ場合はよい.
(c)が成り立たないとする. このとき, $(X,R)$ の任意の始切片は $(Y,S)$ のある始切片に順序同型である.
実際,そうでないとすると, $\{ x \in X | \forall y \in Y , X(x) \not \simeq Y(y) \} \subseteq X$ は最小元 $x _ 0$ をもつ. 最小性から $\forall x \in X(x _ 0) \exists y \in Y (X(x) \simeq Y(y))$ なので, Thm 2.4.4より $X(x _ 0)$ は $Y$ またはそのある始切片と順序同型である.
これは $x _ 0$ のとり方と(c)が成り立たないという仮定に矛盾する.

再びThm 2.4.4を用いれば, $(X,R)$ は $(Y,S)$ またはそのある始切片と順序同型である. 従って(a)または(b)が成り立つ.
以上で主張を得た.

第3章順序数と基数

この章では順序数の定義,および集合の濃度の定義を与える.
§0では一度本筋を離れ,具体例を交えながら順序数のイメージと満たすべき性質を提示する.
§1では順序数の厳密な定義を与える.

§0 自然数

普段使っている「自然数」に相当するものを以下のように構成する.

自然数の一つひとつにある集合を対応させる.

$\begin{aligned} \circ 0 := &\varnothing \text{とする.} \\ \circ 1 := &0 \cup \{ 0 \} \\ = &\varnothing \cup \{ \varnothing \} \\ = &\{ \varnothing \} \text{とする.} \\ \circ 2 := &1 \cup \{ 1 \} \\ = &\{ \varnothing \} \cup \{ \{ \varnothing \} \} \\ = &\{ \varnothing , \{ \varnothing \} \} \text{とする.} \end{aligned}$

以下同様にして, $n$ の次の自然数 $n+1$ を

$\displaystyle{ n+1 := n \cup \{ n \} }$

によって定義する.

$0 = \varnothing$ , $1 = \{ \varnothing \}$ であるから, $2 = \{ \varnothing , \{ \varnothing \} \} = \{ 0,1\}$ である.
同様にして, $n = \{ 0,1,2, \dots ,n-1 \}$ が成り立つ.
このことから,特に以下の性質が成り立つ.

上で定義した集合""の元は"",""の2つである.
- 同様に,集合" $n$ "の元の個数は $n$ 個である.
集合はより小さな自然数,,,,を元とする集合である.
- 従って,(通常の意味で) $m \lt n$ であることは, $m \in n$ であることと同値である.
自然数 $n,m$ に対して, $n \in m , n = m , m \in n$ のいずれか一つだけが成り立つ.

ただし,ここでの目的は自然数を構成することであるから,

集合" $n$ "と集合 $X$ との間に全単射が存在するとき,「 $X$ の元の個数は $n$ である」という.
$m \in n$ であるとき,「 $m$ は $n$ より小さい」という.

と考えるのが正当である.
この大小関係に関して任意の2つの自然数は比較可能であり, 更に推移律

$\displaystyle{ l \in m \land m \in n \rightarrow l \in n }$

が成り立つ.
これらに対して通常の加法や乗法に相当する演算を, 集合の言葉で定義することは易しい.

これを少し広げた「順序数」というものを考える.
要請される性質は以下のようなものである.

順序数 $\alpha$ は「 $\alpha$ より小さな順序数」全体の集合である.
順序数 $\alpha , \beta$ に対して, $\alpha \in \beta , \alpha = \beta , \beta \in \alpha$ のいずれか一つだけが成り立つ.
順序数 $\alpha , \beta , \gamma$ に対して, $\alpha \in \beta \land \beta \in \gamma \rightarrow \alpha \in \gamma$

例えば自然数 $0,1,2,\dots$ は全て順序数である*6.
また,自然数全体の集合 $\omega := \{ 0,1,2,\dots \}$ は, 任意の自然数よりも大きな最小の順序数である.
$\omega$ が集合であることは無限公理によって保証されている.

以上の内容を背景として,次節では順序数の厳密な定義を与える.

§1 順序数

Definition(推移的) 集合 $X$ が $\forall x,y( y \in x \land x\in X \rightarrow y \in X)$ を満たすとき, $X$ は推移的であるという.

Theorem 3.1.1 $X$ が推移的であるとき, $x\in X \rightarrow x \subsetneq X$ が成り立つ.

(proof)
$x\subseteq X$ は上の定義から従う. $x = X$ と仮定するとThm 1.3.1に矛盾する.

Definition(順序数) 集合 $X$ が以下の2つの条件を満たすとき, $X$ は順序数であるという.

$X$ は推移的である.
(非反射型)順序集合 $(X,\in)$ は全順序である.

また,順序数全体の集まりを $\mathrm{OR}$ とかく.

任意の自然数(例えば $2 = \{ \varnothing , \{ \varnothing \} \}$ )が上の定義を満たすことが確認できる. ゆえに $\mathrm{OR}$ は空ではない.
また,後で述べるが $\mathrm{OR}$ は集合ではなく,真のクラスである.

Theorem 3.1.2 $\alpha$ が順序数であるとき, $( \alpha , \in )$ は整列集合である.

(proof)
$\alpha$ の空でない部分集合 $\gamma \subseteq \alpha$ を任意にとる.
正則性公理より, $y \in \gamma$ が存在して $\gamma \cap y = \varnothing$ を満たす.
$y$ と異なる元 $z \in \gamma$ を任意にとると, $( \alpha , \in )$ が全順序であることから $y \in z$ または $z \in y$ が成立する. $z \in y$ であるとすると $\gamma \cap y = \varnothing$ に反するから, $y \in z$ でなければならない.
従って $y$ は $\gamma$ の最小元である.

Theorem 3.1.3 $\alpha$ が順序数であるとき, $\beta \in \alpha \rightarrow \beta = \alpha(\beta)$

(proof)
Thm 3.1.1より $\beta \subsetneq \alpha$ が成り立つ. ゆえに

$\displaystyle{ \alpha ( \beta ) = \{ x | x\in \alpha \land x \in \beta \} = \{ x | x \in \beta \} = \beta }$

Theorem 3.1.4 $\alpha$ が順序数であるとき, $\beta \in \alpha \rightarrow \beta$ は順序数

(proof)
Thm3.1.1より $\beta \subsetneq \alpha$ なので, $( \beta , \in)$ は全順序である.
$\beta$ が推移的であることを示す.
$y \in x \in \beta$ なる $x,y$ を任意にとる. $\alpha$ は推移的なので $y \in \alpha$ .
Thm 1.3.1より $y \neq \beta$ と $\beta \notin y$ が成り立つ. $( \alpha , \in )$ は全順序なので $y \in \beta$ でなければならない.
従って $\beta$ は推移的である.

この定理(とThm.3.1.7で述べる順序数の比較可能性)から分かるように, 順序数 $\alpha$ は $\alpha$ 自身よりも ( $\in$ の意味で)小さな順序数全体の集合である.
最小の順序数は $\varnothing$ であり, 次いで小さいのは $\{ \varnothing \}$ , その次は $\{ \varnothing , \{ \varnothing \} \}$ ,と続く.

Theorem 3.1.5 $\alpha$ が順序数で, $u \subsetneq \alpha$ が推移的であるとき, $u \in \alpha$ が成り立つ.

(proof)
$\alpha \backslash u$ の最小元を $y$ とすると, $(\alpha , \in)$ が全順序であることと $u$ が推移的であることから, $u = \alpha (y)$ が成り立つ.
他方 $y \in \alpha$ とThm3.1.3より $y = \alpha(y)$ であるから $u=y$ .
よって $u \in \alpha$ が成り立つ.

Theorem 3.1.6 $\alpha , \beta$ が順序数であるとき, $\alpha \subseteq \beta \lor \beta \subseteq \alpha$ が成り立つ.

(proof)
$\alpha \not \subseteq \beta \land \beta \not \subseteq \alpha$ であると仮定する.
$\beta \backslash \alpha$ の最小元を $x _ 0$ , $\alpha \backslash \beta$ の最小元を $y _ 0$ とおくと, $x _ 0 \in \beta , y _ 0 \notin \beta$ であることから $x _ 0 \neq y _ 0$ が成り立つ.

$\alpha \cap \beta = x _ 0$ を示す.
$t \in \alpha \cap \beta$ を任意にとると, $( \beta , \in)$ が全順序であることから

$\displaystyle{ t \in x _ 0 \lor t = x _ 0 \lor x _ 0 \in t }$

が成り立つ.
$\alpha$ は推移的なので, $t = x _ 0 \lor x _ 0 \in t$ の場合は $x _ 0 \in \alpha$ となり $x _ 0$ のとり方に反する. 従って $t \in x _ 0$ でなければならない. $t$ は任意なので $\alpha \cap \beta \subseteq x _ 0$ が成り立つ.
一方 $s \in x _ 0$ とすると $\beta$ の推移性から $s \in \beta$ .
$x _ 0$ の最小性から $s \notin \beta \backslash \alpha$ であり, 従って $s \in \alpha \cap \beta$ である. ゆえに $x _ 0 \subseteq \alpha \cap \beta$ .
以上より $\alpha \cap \beta = x _ 0$ が成り立つ.

全く同様にして $\alpha \cap \beta = y _ 0$ が示されるが, これは $x _ 0 \neq y _ 0$ に矛盾する.

Theorem 3.1.7 順序数の全体 $\mathrm{OR}$ は推移的かつ全順序である.
正確には以下の性質が成り立つ.

$\begin{aligned} \mathrm{(1)} & \forall \alpha,\beta ( \beta \in \alpha \land \alpha \in \mathrm{OR} \rightarrow \beta \in \mathrm{OR}) \\ \mathrm{(2)} & \forall \alpha , \beta ,\gamma \in \mathrm{OR} \\ &(\alpha \in \beta \land \beta \in \gamma \rightarrow \alpha \in \gamma) \\ \mathrm{(3)} & \forall \alpha , \beta \in \mathrm{OR}\\ & (\alpha \in \beta \lor \alpha = \beta \lor \beta \in \alpha) \end{aligned}$

(proof)
(1)
Thm 3.1.4として示した.

(2)
順序数 $\gamma$ が推移的であることから従う.

(3)
$\alpha , \beta \in \mathrm{OR}$ かつ $\alpha \neq \beta$ とすると, Thm 3.1.6より $\alpha \subsetneq \beta \lor \beta \subsetneq \alpha$ .
$\alpha,\beta$ は順序数なので特に推移的である. ゆえにThm 3.1.5より $\alpha \in \beta$ あるいは $\beta \in \alpha$ のいずれかが成り立つ.
以上で示された.

Corollary $\mathrm{OR}$ は集合ではない(真のクラスである).

(proof)
もし $\mathrm{OR}$ が集合であるとすると, Thm 3.1.7より $\mathrm{OR}$ 自身も順序数となる. これは $\mathrm{OR} \in \mathrm{OR}$ を意味するので矛盾.

以下では順序数 $\alpha,\beta$ の大小を

$\begin{aligned} \alpha < \beta & \leftrightarrow \alpha \in \beta \\ \alpha \leq \beta & \leftrightarrow \alpha < \beta \lor \alpha = \beta \end{aligned}$

で書き表す.

Definition(後続者 Successor) 集合 $\alpha$ に対し $\alpha +1 : = \alpha \cup \{ \alpha \}$ と定める.
このとき $\alpha \in \mathrm{OR} \leftrightarrow \alpha + 1 \in \mathrm{OR}$ が成り立つ.
$\alpha$ が順序数であるとき, $\alpha + 1$ を $\alpha$ の後続者という.

Proposition $\alpha$ が順序数であるとき, $\alpha < \beta < \alpha +1$ を満たす順序数 $\beta$ は存在しない.

(proof)
$\beta$ が存在したとする.
$\beta < \alpha +1$ より $\beta \in \alpha \cup \{ \alpha \}$ . 従って $\beta \in \alpha \lor \beta = \alpha$ .
これは $\alpha <\beta$ に反する.

次の定理は $X$ が集合の場合には明らかだが, 一般の場合にはそうではない.

Theorem 3.1.8 $X$ は順序数を元とする空でないクラスであるとする. このとき $X$ は最小元を持つ.

(proof)
$\beta \in X$ を一つとる.
$\beta +1 \cap X$ は順序数 $\beta +1$ の部分集合であり, $\beta$ を元に持つから空でない.
従って $\beta + 1 \cap X$ は最小元 $\alpha _ 0$ を持つ.

この $\alpha _ 0$ が $X$ の最小元であることを示す.
$\alpha \in X$ とする.
$\alpha \in \beta + 1$ ならば $\alpha _ 0$ のとり方から $\alpha _ 0 \leq \alpha$ .
$\alpha \notin \beta + 1$ ならば, $\alpha \geq \beta + 1 > \alpha _ 0$ なので $\alpha _ 0 < \alpha$ .
ゆえに $\alpha _ 0$ は $X$ の最小元である.

§2 基数と濃度

Definition(対等) 2つの集合 $A,B$ の間に全単射 $f : A\rightarrow B$ が存在するとき, $A$ と $B$ は対等であるといい, $A \sim B$ とかく.

Remark $\sim$ は同値関係である.

ZFCで成り立つ以下の定理を証明せずに用いる*7.

Theorem 3.2.1(整列可能定理) 任意の集合 $X$ に対してある $X$ 上の順序 $R$ が存在して, $(X,R)$ は整列集合となる.

Theorem 3.2.2 $(X,R)$ が整列集合ならば, ある順序数 $\gamma$ が存在して, $(X,R)$ は $(\gamma , \leq)$ または $(\gamma , <)$ と順序同型である.

これらの定理によれば, 任意の集合 $X$ は適当な順序 $R$ を入れることによりある順序数 $\gamma$ と順序同型にできる.
順序同型写像は全単射なので, このとき $X$ と $\gamma$ は対等である. 従って, $X$ と対等な順序数全体のなすクラスは空ではない.
Thm 3.1.8により, このクラスは最小元を持つ. これを $X$ の濃度という.

Definition(濃度) 集合 $X$ と対等な順序数のうち最小のものを $X$ の濃度といい, $|X|$ とかく.

Definition(基数) ある集合の濃度となるような順序数のことを基数という.
順序数 $\alpha$ が基数であることは, $| \alpha | = \alpha$ であることと同値である.

Theorem 3.2.3 集合 $x,y$ に対し, $x \sim y \leftrightarrow |x| = |y|$

(proof)

$\begin{aligned} x \sim y \leftrightarrow & |x| \sim |y| \\ & \qquad (\because x \sim |x| , y \sim |y|) \\ \leftrightarrow & |x| \leq |y| \land |y| \leq |x| \\ & \qquad (\because |x|,|y| \text{の最小性})\\ \leftrightarrow & |x| = |y| \end{aligned}$

Theorem 3.2.4 集合 $x,y$ に対し $x \subseteq y \rightarrow |x| \leq |y|$

(proof)
$x \subseteq y \sim |y|$ より, $x \sim z$ を満たす $|y|$ の部分集合 $z$ が存在する.
$z$ は整列集合なので, Thm3.2.2よりある順序数 $\alpha$ と $z$ との間の順序同型写像 $f : \alpha \rightarrow z$ が存在する. 特に $\alpha \sim z \sim x$ なので $x$ と $\alpha$ は対等.
$|x|$ は $x$ と対等な最小の順序数であるから $|x| \leq \alpha$ .

ここで $\alpha >|y|$ と仮定するとThm 3.1.3より $|y| = \alpha (|y|)$ .
$f$ の値域を $\alpha$ だとみなせばThm2.4.2より $f(|y|) \geq |y|$ .
従って $f(|y|) \notin \{ x\in \alpha | x < |y| \} = \alpha (|y|) = |y|$ .
これは $\mathrm{Im} f \subseteq z \subseteq |y|$ に矛盾する. 従って $\alpha \leq |y|$ .

以上より $|x| \leq \alpha \leq |y|$ であるから主張が成り立つ.

Theorem 3.2.5(鳩の巣原理とその逆) 集合 $x,y$ に対して以下は同値.

$\begin{aligned} \mathrm{(1)} & \text{単射} f : x \rightarrow y \text{が存在する} \\ \mathrm{(2)} & |x| \leq |y| \end{aligned}$

(proof)
(1) $\rightarrow$ (2)
$z : = \mathrm{Im}f \subseteq y$ とおくと, $x \sim z \subseteq y$ が成り立つ.
Thm 3.2.3より $|x|= |z|$ ,
Thm 3.2.4より $|z| \leq |y|$ であるから(2)が成り立つ.

(2) $\rightarrow$ (1)
$|x|=|y|$ なら全単射 $x \xrightarrow{\sim} |x| = |y| \xrightarrow{\sim} y$ がある.
$|x| < |y|$ なら $x \xrightarrow{\sim} |x| \xrightarrow{\text{包含写像}} |y| \xrightarrow{\sim} y$ が単射である.

以上で鳩の巣原理が証明された.

おわりに

軽い気持ちで執筆を始めたら思いのほか長大になりました。
Thm 3.2.1およびThm 3.2.2は証明なしに認めましたが、これらを示すには超限帰納法を導入する必要があるため、字数を考慮し証明を省略しました。
今後機会があればこの部分を補完したいと考えています*8。

参考文献

倉田令次朗，篠田寿一．公理論的集合論．名古屋，河合文化教育研究所，1996，152p．
田中尚夫．公理的集合論(現代数学レクチャーズB-10)．培風館，1982，273p．
田中尚夫．選択公理と数学【増訂版】，“発生と論争，そして確立への道”．増訂版，遊星社，2005，262p．
松坂和夫．集合・位相入門．岩波書店，1968，329p．

*1:論理的には「一致」よりも「対応」とでも表現する方が適切かもしれない

*2:鳩に対応する集合を $P$ ,箱に対応する集合を $B$ としている

*3:ラッセルのパラドックス

*4:元と集合は区別されないので2集合と呼ぶべきかも知れない

*5:この $\rightarrow$ は「ならば」の意味ではなく写像の定義域と値域を表す矢印である

*6:「性質1-3からそれが分かる」と言っている訳ではなく,単に事実を紹介しているに過ぎない.実際,どの集合が順序数であるのかを確定させなければ,性質1-3が成り立つか否かを判断することは出来ない

*7:ZF(ZFCから選択公理を除いた公理系)のもとでは,整列可能定理は選択公理と同値な主張であることが知られている

*8:嘘である(したくはない)