あなたの鳩の巣原理はどこから？

私は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, 括弧を用いる.
    • ただし高度な知識は要しない.
  • 基本的述語記号は \in,= の2つのみとする.
    • これらから定義できる一般的な記号については,定義を述べずに用いる場合がある.
  • a,b,x,yなどの変数は全て集合を表すとする(集合一元論).
    • 特に集合の元はそれ自体集合であることに留意する.

§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"の元は"0","1"の2つである.
    • 同様に,集合"n"の元の個数はn個である.
  • 集合nはnより小さな自然数0,1,2,\cdots,n-1を元とする集合である.
    • 従って,(通常の意味で) 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 }

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

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

  1. 順序数 \alpha は「 \alpha より小さな順序数」全体の集合である.
  2. 順序数\alpha , \betaに対して, \alpha \in \beta , \alpha = \beta , \beta \in \alphaのいずれか一つだけが成り立つ.
  3. 順序数\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は順序数であるという.
  1. Xは推移的である.
  2. (非反射型)順序集合(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:嘘である(したくはない)