# 公理的集合論 ZFC：数学のすべてを「集合」から組み立てる > ZFC の公理を一つずつ述べ、自然数・整数・有理数・実数を集合として構成して上限性質を証明する。順序数と超限帰納法、基数算術 κ·κ=κ、選択公理の同値形を示し、連続体仮説の独立性を述べる。 > https://rikai.mugen-giken.com/mathematics/logic-and-type-theory/axiomatic-set-theory ## 0. この記事の要点 数学で扱う数も関数も空間も、じつはすべて「集合」という一種類のものだけで作れます。この記事は、そのために「集合についてどんな主張を出発点にしてよいか」を決める約束事（公理）を一つずつ確かめ、そこから自然数や実数を実際に組み立てます。読み終えると、実数の「切れ目のなさ」が仮定ではなく証明できる事実だと分かり、さらに「無限の大きさ」を比べる道具である順序数と基数が使えるようになります。 - **ZFC** は、記号 $\in$ だけをもつ一階述語論理の理論です。公理は ZF の 9 個（うち 2 個は図式）に選択公理を加えた 10 個で、数学で使う対象（数、関数、空間、写像の族）はすべてこの公理から存在を示せる「集合」として作れます。Rikai の数学の記事で使う命題を前提へ前提へとさかのぼると、最後はこの記事の公理に着きます。 - 自然数は $0=\varnothing$、$n+1=n\cup\{n\}$ と作り、ペアノの公理と再帰的定義の原理を**定理として**証明します（、）。整数・有理数は同値関係の商として、実数はデデキントの切断として作り、実数の上限性質を証明します（）。 - **順序数**は「整列集合の標準的な代表」です。順序数どうしは $\in$ で比較でき（）、どの整列集合もただ一つの順序数と同型になります（）。超限帰納法と超限再帰はこの上で動きます。 - **基数**は「それより小さい順序数とは対等にならない順序数」です。無限基数 $\kappa$ について $\kappa\cdot\kappa=\kappa$（）が成り立ち、無限基数の和と積は大きいほうに一致します。 - 選択公理は Zorn の補題・整列可能定理と同値です（既出の同値定理を ZFC の中で読み直します）。連続体仮説 $2^{\aleph_0}=\aleph_1$ は ZFC から証明も反証もできません（ゲーデルとコーエン。主張として述べます）。 ## 1. 動機：「集合とは何か」に答えずに数学を始めるために ### 1.1. 素朴な集合論はどこで壊れるか [集合と論理](/mathematics/foundations/sets-and-logic) では、集合を「ものの集まり」と説明しました。ふだんの数学はこれで困りません。けれども、「性質 $P(x)$ を満たす $x$ 全体」がいつでも集合になると考えると、$P(x)$ として $x\notin x$ をとった瞬間に破綻します。$R=\{x\mid x\notin x\}$ が集合なら、$R\in R$ と $R\notin R$ が同値になってしまうからです（ラッセルのパラドックス、1901 年）。 この矛盾は「集合」という言葉の意味を日常語に任せていたことから来ています。そこで 20 世紀の初めに、ツェルメロ (1908) とフレンケル・スコーレム (1922) は、意味を定義する代わりに**使ってよい操作を公理として列挙する**ことにしました。「集合とは何か」には答えず、「どういう集合が存在すると言ってよいか」だけを決めるのです。これが ZFC（Zermelo–Fraenkel + Choice）です。 ### 1.2. Rikai の閉包の終点 この記事には、Rikai 全体の中で特別な役目があります。Rikai の記事では、定理の証明で使う事実を、記事内で証明するか、既出の定理として参照するかのどちらかにしています。参照を順にたどると、解析学の定理は [実数の完備性とコーシー列](/mathematics/real-analysis/completeness-and-cauchy) の完備性の公理に、その公理は [数とは何か](/mathematics/foundations/what-is-a-number) の実数の公理に行き着きます。けれども、そこで止まってしまうと「実数の公理を満たすものは本当にあるのか」という問いが残ります。 この記事はその問いに答えます。ZFC の公理だけから、自然数・整数・有理数・実数を**実際に作り**、実数の公理（とくに上限性質）を**定理として証明**します。これで、実数の公理は仮定ではなく ZFC の定理になり、解析学の命題は ZFC までさかのぼれます。
ZFC 記号は ∈ だけ ω = ℕ∪{0} 無限公理・ペアノ ℤ と ℚ 対の同値類 ℝ デデキント切断 上限性質 → 解析学の完備性 定理 ペアノ・再帰 商集合 定理 切断の上限 系 単調収束
後半では、無限の大きさを測る道具（順序数と基数）を ZFC の中で作り、選択公理と連続体仮説の位置を確かめます。「ZFC で証明できる」とは [一階述語論理と完全性定理](/mathematics/logic-and-type-theory/first-order-logic) の意味での導出があることで、完全性定理により「ZFC のすべてのモデルで成り立つ」と同じことです。 ## 2. ZFC の公理 ### 2.1. 言語と公理の一覧 ZFC の言語は、2 変数関係記号 $\in$ と等号だけからなる一階の言語です。対象はすべて集合で、「元」も集合です。$x\subseteq y$ は $\forall z\,(z\in x\to z\in y)$ の略記とします。 1. **外延性**：$\forall x\,\forall y\,\bigl(\forall z\,(z\in x\leftrightarrow z\in y)\to x=y\bigr)$。同じ元をもつ集合は等しい。 2. **空集合**：元をもたない集合 $\varnothing$ が存在する。 3. **対**：任意の $a,b$ に対し、元がちょうど $a,b$ である集合 $\{a,b\}$ が存在する。 4. **和集合**：任意の $x$ に対し、$x$ の元の元全体からなる集合 $\bigcup x$ が存在する。 5. **冪集合**：任意の $x$ に対し、$x$ の部分集合全体からなる集合 $\mathcal{P}(x)$ が存在する。 6. **分出（図式）**：各論理式 $\varphi(z,\vec p)$ ごとに、任意の $x$ と $\vec p$ に対して $\{z\in x\mid \varphi(z,\vec p)\}$ が存在する。 7. **置換（図式）**：各論理式 $\varphi(u,v,\vec p)$ ごとに、$\varphi$ が $x$ 上で関数的（各 $u\in x$ に対して $\varphi(u,v)$ を満たす $v$ がただ一つ）ならば、その $v$ 全体の集合 $\{v\mid \exists u\in x\ \varphi(u,v)\}$ が存在する。 8. **無限**：$\varnothing\in I$ かつ $\forall y\,(y\in I\to y\cup\{y\}\in I)$ を満たす集合 $I$ が存在する。 9. **正則性（基礎）**：空でない任意の $x$ は、$x$ と共通部分をもたない元 $y\in x$（$y\cap x=\varnothing$）をもつ。 これらを **ZF** と呼び、ZF に次を加えたものを **ZFC** と呼ぶ。 10. **選択**：空でない集合からなる任意の集合 $x$ に対し、各 $y\in x$ に $y$ の元 $f(y)\in y$ を対応させる関数 $f$ が存在する。 外延性により、2〜5 で存在が主張される集合はただ一つに決まります。だから $\varnothing$、$\{a,b\}$、$\bigcup x$、$\mathcal{P}(x)$ という記号を使ってよいのです。$x\cup y=\bigcup\{x,y\}$、$\{a\}=\{a,a\}$、$x\cap y=\{z\in x\mid z\in y\}$ のように、おなじみの操作はすべてこれらの組み合わせです。分出と置換は無限個の公理をまとめた**図式**で、論理式ごとに一つの公理があります。分出は「すでにある集合から、条件を満たす元だけを切り出す」公理、置換は「集合の各元を一つずつ別の集合の元に置き換えたものも集合になる」公理で、たとえば $x=\{0,1,2\}$ の各元 $n$ を $n+10$ に置き換えた集まりが集合になる、といった形で使います。選択公理の内容は [選択公理と Zorn の補題](/mathematics/foundations/axiom-of-choice-zorn) の と同じです。 すべての集合を元にもつ集合 $V$ は存在しない。 $V$ が存在したとする。分出公理を論理式 $z\notin z$ に使うと、集合 $R=\{z\in V\mid z\notin z\}$ が存在する。$R$ も集合だから $R\in V$ である。したがって $R\in R\leftrightarrow (R\in V\wedge R\notin R)\leftrightarrow R\notin R$ となり矛盾する。 ラッセルのパラドックスは、ZFC では「矛盾」ではなく「$V$ は集合ではない」という定理になります。分出公理は**すでにある集合 $x$ の中から**切り出すことしか許さないので、$\{z\mid z\notin z\}$ を作れないのです。$V$ や「すべての順序数」のように、論理式で定まるが集合とは限らない集まりを**クラス**と呼び、あくまで論理式の略記として扱います。 ### 2.2. 順序対・直積・関数 関数や関係も集合として表します。鍵は順序対です。 $(a,b)=\{\{a\},\{a,b\}\}$ と定める。集合 $A,B$ の**直積**を $A\times B=\{p\in\mathcal{P}(\mathcal{P}(A\cup B))\mid \exists a\in A\ \exists b\in B\ p=(a,b)\}$ とする。$A\times B$ の部分集合を**関係**、各 $a\in A$ に対して $(a,b)\in f$ となる $b\in B$ がただ一つある関係 $f\subseteq A\times B$ を $A$ から $B$ への**関数**という。 $a,b\in A\cup B$ なら $\{a\},\{a,b\}\subseteq A\cup B$ なので $(a,b)\in\mathcal{P}(\mathcal{P}(A\cup B))$ です。だから直積は冪集合と分出で作れます。 $(a,b)=(c,d)$ ならば $a=c$ かつ $b=d$ である。 **$a=b$ の場合。** $(a,b)=\{\{a\}\}$ は元を一つしかもたないので、$\{\{c\},\{c,d\}\}$ も元が一つであり、$\{c\}=\{c,d\}=\{a\}$。よって $c=d=a=b$。 **$a\ne b$ の場合。** $(a,b)$ は 1 元集合 $\{a\}$ と 2 元集合 $\{a,b\}$ からなる。$(c,d)$ も元を二つもつので $c\ne d$ であり、$\{c\}$ は 1 元、$\{c,d\}$ は 2 元である。外延性により 1 元集合どうし、2 元集合どうしが等しいので $\{a\}=\{c\}$、$\{a,b\}=\{c,d\}$。前者から $a=c$。後者から $b\in\{a,d\}$ で $b\ne a$ だから $b=d$。 ## 3. 自然数 ### 3.1. 無限公理から $\omega$ へ 集合 $x$ の**後者**を $S(x)=x\cup\{x\}$ とする。$\varnothing$ を含み $S$ で閉じた集合を**帰納的集合**という。無限公理の $I$ をとり、 $$ \omega=\{n\in I\mid n \text{ はすべての帰納的集合の元である}\} $$ と定める（分出公理）。$0=\varnothing$、$1=S(0)=\{0\}$、$2=S(1)=\{0,1\}$、… と書く。 $\omega$ の定義は $I$ の選び方によりません（どの帰納的集合 $J$ を使っても、$I$ と $J$ の両方に属することと、すべての帰納的集合に属することは同値だからです）。各自然数 $n$ は「$n$ より小さい自然数全体」$\{0,1,\ldots,n-1\}$ そのものになっています。この記事では $\omega$ は $0$ を含みます。Rikai の既定の記号では $\mathbb{N}=\{1,2,\ldots\}$ なので、$\omega=\mathbb{N}\cup\{0\}$ です。 次が成り立つ。 1. $0\in\omega$ であり、$n\in\omega$ ならば $S(n)\in\omega$。 2. 任意の $n\in\omega$ について $S(n)\ne 0$。 3. $m,n\in\omega$ かつ $S(m)=S(n)$ ならば $m=n$。 4. （帰納法）$A\subseteq\omega$ が $0\in A$ を満たし、$n\in A$ ならば $S(n)\in A$ であるとき、$A=\omega$。 これは [証明の技術](/mathematics/foundations/proof-techniques) でペアノの公理（）として**仮定**したものです。ZFC ではそれが定理になります。 (1) $\omega$ の元はすべての帰納的集合に属する。$\varnothing$ はどの帰納的集合にも属し、$n$ がすべての帰納的集合に属せば $S(n)$ もそうである。したがって $\omega$ 自身が帰納的集合である。 (4) 仮定より $A$ は帰納的集合だから、$\omega$ の定義により $\omega\subseteq A$。よって $A=\omega$。 (2) $n\in S(n)$ なので $S(n)\ne\varnothing$。 (3) まず二つの補助命題を (4) で示す。 (a) **各 $n\in\omega$ は推移的**（$x\in n\Rightarrow x\subseteq n$）。$0=\varnothing$ では自明に成り立つ。$n$ が推移的とし、$x\in S(n)=n\cup\{n\}$ とする。$x\in n$ なら $x\subseteq n\subseteq S(n)$、$x=n$ なら $x\subseteq S(n)$。よって $S(n)$ も推移的。 (b) **各 $n\in\omega$ について $n\notin n$**。$0\notin 0$ は自明。$n\notin n$ とし、$S(n)\in S(n)$ と仮定する。すると $S(n)\in n$ または $S(n)=n$。後者なら $n\in S(n)=n$ で矛盾。前者なら $n\in S(n)$ と (a) の推移性 $S(n)\subseteq n$ から $n\in n$ となり矛盾。 さて $S(m)=S(n)$ かつ $m\ne n$ とする。$m\in S(m)=S(n)$ かつ $m\ne n$ なので $m\in n$。同様に $n\in m$。(a) より $n\subseteq m$ なので $m\in n\subseteq m$、すなわち $m\in m$ となり (b) に反する。 (b) は正則性公理からも直ちに従いますが、ここでは正則性を使わずに示しました。自然数の理論は正則性公理なしで展開できる、ということです。 ### 3.2. 再帰的定義 足し算 $m+0=m$、$m+S(n)=S(m+n)$ のような再帰的定義が実際に関数を一つ定めることも、ZFC では証明が要ります。 集合 $A$、元 $a\in A$、関数 $g:A\to A$ が与えられたとき、 $$ F(0)=a,\qquad F(S(n))=g(F(n))\quad(n\in\omega) $$ を満たす関数 $F:\omega\to A$ がただ一つ存在する。 この定理のねらいは、「$F(0)$ を決め、$F(n)$ から $F(S(n))$ を決める」という書き方が、本当に一つの関数を定めると保証することです。証明の方針は、この二つの条件を満たす関係（対の集合）を全部集め、その共通部分、つまり必要最小限の関係を取り、それが各 $n$ にちょうど一つの値を与える（関数になる）ことを帰納法で確かめる、というものです。 関係 $R\subseteq\omega\times A$ が**適合的**であるとは、$(0,a)\in R$ であり、$(n,y)\in R$ ならば $(S(n),g(y))\in R$ であることとする。$\omega\times A$ 自身は適合的である。$F$ を適合的な関係すべての共通部分とする（$\mathcal{P}(\omega\times A)$ から分出で作れる）。$F$ も適合的であり、適合的な関係の中で最小である。 $F$ が $\omega$ から $A$ への関数であることを、$D=\{n\in\omega\mid (n,y)\in F \text{ となる } y \text{ がただ一つ}\}$ に (4) を使って示す。 - $0\in D$：$(0,a)\in F$。$b\ne a$ で $(0,b)\in F$ なら、$F\setminus\{(0,b)\}$ も適合的である（ (2) より $0$ はどの $S(n)$ とも異なるので、取り除いた対が適合性のために必要になることはない）。これは $F$ の最小性に反する。 - $n\in D\Rightarrow S(n)\in D$：$(n,y)\in F$ となる $y$ がただ一つとする。適合性より $(S(n),g(y))\in F$。$z\ne g(y)$ で $(S(n),z)\in F$ なら、$F'=F\setminus\{(S(n),z)\}$ が適合的であることを確かめる。$(0,a)\in F'$ は $S(n)\ne0$ から。$(m,w)\in F'$ のとき $(S(m),g(w))\in F$ であり、これが $(S(n),z)$ に等しければ (3) より $m=n$、$n\in D$ より $w=y$、よって $g(w)=g(y)\ne z$ となり矛盾する。したがって $(S(m),g(w))\in F'$。$F$ の最小性に反する。 よって $D=\omega$ で、$F$ は関数であり、適合性がそのまま求める等式である。一意性：$F,F'$ が両方とも等式を満たせば、$\{n\mid F(n)=F'(n)\}$ は $0$ を含み $S$ で閉じるので $\omega$ に等しい。 この定理を $A=\omega$、$a=m$、$g=S$ に使えば $n\mapsto m+n$ が定まり、$a=0$、$g(y)=y+m$ に使えば $n\mapsto m\cdot n$ が定まります。結合法則・交換法則・分配法則・順序の性質は、 (4) による帰納法で順に示せます（[証明の技術](/mathematics/foundations/proof-techniques) の帰納法の議論がそのまま使えます）。$\omega$ 上の順序は $m $\omega\times\omega$ 上の関係 $(a,b)\sim(c,d)\iff a+d=b+c$ は同値関係であり、その商集合を $\mathbb{Z}$ とする。$(a,b)$ の同値類を $a-b$ と書く。和と積を $$ [(a,b)]+[(c,d)]=[(a+c,\,b+d)],\qquad [(a,b)]\cdot[(c,d)]=[(ac+bd,\,ad+bc)] $$ で定める。さらに $\mathbb{Z}\times(\mathbb{Z}\setminus\{0\})$ 上の関係 $(a,b)\sim(c,d)\iff ad=bc$ による商集合を $\mathbb{Q}$ とし、$(a,b)$ の類を $a/b$ と書く。 $\mathbb{Z}$ の関係の推移律には、$\omega$ での簡約律 $a+x=b+x\Rightarrow a=b$（$x$ についての帰納法）を使います。$\mathbb{Q}$ のほうの関係が[同値関係](/mathematics/foundations/equivalence-relations#def-equivalence)であることは で示しました。和と積が代表元の取り方によらないこと（well-defined 性）は [関係と同値関係](/mathematics/foundations/equivalence-relations) の と同じ型の計算で確かめられます。商集合は $\mathcal{P}(\omega\times\omega)$ の部分集合として分出公理で作れるので、ここまですべて ZF の中の構成です。$n\in\omega$ を $n-0\in\mathbb{Z}$ と、$k\in\mathbb{Z}$ を $k/1\in\mathbb{Q}$ と同一視します。こうして $\mathbb{Q}$ は順序体（）になります。 ### 4.2. 実数：デデキントの切断 $\mathbb{Q}$ の部分集合 $A$ が次の 3 条件を満たすとき、**切断**という。 1. $A\ne\varnothing$ かつ $A\ne\mathbb{Q}$。 2. （下に閉じる）$a\in A$ かつ $q 切断 $A$ は「実数 $x$ より小さい有理数全体」のつもりです。$\sqrt2$ には $\{q\mid q<0 \text{ または } q^2<2\}$ が対応します（[数とは何か](/mathematics/foundations/what-is-a-number) の ）。 (1) $(\mathbb{R},\le)$ は全順序集合である。 (2) $\mathbb{R}$ の空でない部分集合 $\mathcal{S}$ が上に有界ならば、$\mathcal{S}$ は $\mathbb{R}$ の中に上限をもち、それは和集合 $\bigcup\mathcal{S}$ である。 (1) 包含関係は半順序である。全順序性を示す。$A\not\subseteq B$ とし、$a\in A\setminus B$ をとる。$b\in B$ とする。もし $a\le b$ なら、$a=b$ のときは $a\in B$、$a 上限性質は、包含で順序を入れた**集合の族の和集合**という、ほとんど自明な操作から出てきました。困難は体の演算のほうにあります。 切断 $A,B$ に対し $A+B=\{a+b\mid a\in A,\ b\in B\}$、$-A=\{q\in\mathbb{Q}\mid \exists r>0,\ -q-r\notin A\}$ とする。$A,B\ge0^{*}$ のとき $A\cdot B=\{q\in\mathbb{Q}\mid q<0\}\cup\{ab\mid a\in A,\ b\in B,\ a\ge0,\ b\ge0\}$ とし、一般の符号へは $(-A)\cdot B=-(A\cdot B)$ などで拡げる。 $A+0^{*}=A$ を確かめます。$a\in A$、$r<0$ なら $a+r 同じ型の計算（各公理について $\mathbb{Q}$ での等式を代表元ごとに使い、条件 3 で端を調整する）で、$(\mathbb{R},+,\cdot,\le)$ が順序体であり、$q\mapsto q^{*}$ が $\mathbb{Q}$ からの順序体の埋め込みであることが確かめられます。乗法の逆元と分配法則の検証は場合分けが多く長いので、ここでは省略し、全体を書き下した文献として Rudin の *Principles of Mathematical Analysis* 第 1 章付録を挙げます（参考文献）。この検証は有理数の四則と大小だけを使う有限の計算で、新しい公理は要りません。 上で構成した $\mathbb{R}$ において、単調増加で上に有界な数列 $(a_n)$ は $s=\sup_n a_n$ に収束する。 $\{a_n\}$ は空でなく上に有界なので、 により上限 $s$ が存在する。$\varepsilon>0$ とする。$s-\varepsilons-\varepsilon$ となる $N$ がある。単調性から $n\ge N$ で $s-\varepsilon これで、[数とは何か](/mathematics/foundations/what-is-a-number) の上限性質（）と、[実数の完備性とコーシー列](/mathematics/real-analysis/completeness-and-cauchy) が出発点に置いた単調収束の公理（）は、どちらも ZFC の**定理**になりました。そこから先、コーシー列の収束（）や Bolzano–Weierstrass の定理は、それぞれの記事の証明がそのまま ZFC の中の証明になります。 有理数のコーシー列の同値類として実数を作ることもできます（）。どちらの構成でも上限性質をもつ順序体が得られ、上限性質をもつ順序体は互いに順序体として同型です。したがって「実数とは何か」は構成の選び方によりません。数学者が実数を使うときに参照しているのは、個々の構成ではなく、この同型類だといえます。 ## 5. 順序数と超限帰納法 $\omega$ は $0,1,2,\ldots$ を「それより前の自然数全体」として並べたものでした。この並べ方を $\omega$ の先まで続けたものが順序数です。 ### 5.1. 定義と基本性質 集合 $\alpha$ が**推移的**であるとは、$x\in\alpha$ ならば $x\subseteq\alpha$ であることをいう。推移的であって、関係 $\in$ が $\alpha$ 上の狭義の整列順序（狭義全順序で、空でない任意の部分集合が $\in$ に関する最小元をもつ）であるような集合を**順序数**という。順序数 $\alpha,\beta$ について $\alpha<\beta$ を $\alpha\in\beta$ で定める。 の証明の (a) と同様の帰納法で、各 $n\in\omega$ と $\omega$ 自身が順序数であることが示せます。$\omega+1=S(\omega)=\omega\cup\{\omega\}$、$\omega+2$、… も順序数です。 $\alpha,\beta$ を順序数とする。 1. $\alpha\notin\alpha$。 2. $\alpha$ の元は順序数である。 3. $\alpha\cap\beta$ は順序数である。 4. $\alpha\subsetneq\beta$ ならば $\alpha\in\beta$。 (1) $\alpha\in\alpha$ なら、$\alpha$ は $\alpha$ の元で、$\in$ が $\alpha$ 上で非反射的であることに反する。 (2) $\beta'\in\alpha$ とする。推移性から $\beta'\subseteq\alpha$ なので、$\beta'$ 上の $\in$ は $\alpha$ 上の整列順序の制限であり、整列順序である。$\beta'$ が推移的であること：$\delta\in\gamma\in\beta'$ とすると、$\gamma\in\alpha$、さらに $\delta\in\alpha$（$\alpha$ の推移性を 2 回）。$\in$ は $\alpha$ 上で推移的な関係だから $\delta\in\beta'$。 (3) 推移的集合の共通部分は推移的であり、$\alpha\cap\beta\subseteq\alpha$ 上の $\in$ は整列順序の制限である。 (4) $\beta\setminus\alpha\ne\varnothing$ の $\in$ に関する最小元を $\gamma$ とし、$\gamma=\alpha$ を示す。$\delta\in\gamma$ なら $\delta\in\beta$（推移性）で、最小性より $\delta\notin\beta\setminus\alpha$、つまり $\delta\in\alpha$。よって $\gamma\subseteq\alpha$。逆に $\delta\in\alpha$ とする。$\delta,\gamma\in\beta$ は $\in$ で比較できる。$\delta=\gamma$ は $\gamma\notin\alpha$ に反し、$\gamma\in\delta$ なら $\alpha$ の推移性で $\gamma\in\alpha$ となり反する。よって $\delta\in\gamma$。ゆえに $\alpha=\gamma\in\beta$。 順序数 $\alpha,\beta$ について、$\alpha\in\beta$、$\alpha=\beta$、$\beta\in\alpha$ のちょうど一つが成り立つ。さらに、順序数からなる空でない集合は $\in$ に関する最小元をもつ。 $\delta=\alpha\cap\beta$ は順序数である（ (3)）。$\delta\ne\alpha$ かつ $\delta\ne\beta$ なら、 (4) より $\delta\in\alpha$ かつ $\delta\in\beta$、つまり $\delta\in\delta$ となり (1) に反する。よって $\delta=\alpha$ または $\delta=\beta$。$\delta=\alpha$ なら $\alpha\subseteq\beta$ で、$\alpha=\beta$ か（(4) より）$\alpha\in\beta$。$\delta=\beta$ も同様。二つが同時に成り立たないこと：$\alpha\in\beta$ と $\beta\in\alpha$ なら推移性で $\alpha\in\alpha$、$\alpha\in\beta=\alpha$ も $\alpha\in\alpha$ で、いずれも (1) に反する。 最小元：$C$ を順序数の空でない集合とし、$\alpha\in C$ をとる。$\alpha\cap C=\varnothing$ なら、どの $\beta\in C$ も $\beta\in\alpha$ ではないので、比較可能性より $\alpha\le\beta$、$\alpha$ が最小元。$\alpha\cap C\ne\varnothing$ なら、その $\alpha$ における最小元 $\gamma$ が $C$ の最小元である（$\beta\in C$ が $\beta\in\gamma$ なら $\beta\in\alpha\cap C$ で $\gamma$ の最小性に反する）。 (1) 順序数からなる推移的集合は順序数である。特に順序数からなる集合 $X$ に対し $\bigcup X$ は順序数で、$X$ の上限である。 (2)（ブラリ＝フォルティ）すべての順序数を元とする集合は存在しない。 (1) 推移的で、 により $\in$ は狭義全順序（推移律は順序数 $\gamma$ の推移性から：$\alpha\in\beta\in\gamma\Rightarrow\alpha\in\gamma$）、最小元も存在する。$\bigcup X$ は順序数の元すなわち順序数（ (2)）からなり、推移的集合の和集合は推移的である。$\alpha\in X$ なら $\alpha\subseteq\bigcup X$ なので $\alpha\le\bigcup X$ で、上界 $\beta$ に対しては各 $\alpha\subseteq\beta$ だから $\bigcup X\subseteq\beta$。 (2) そのような集合 $\Omega$ は (1) により順序数であり、$\Omega\in\Omega$ となって (1) に反する。 順序数は $0$、後者 $S(\alpha)$、そして後者でない $0$ 以外の順序数（**極限順序数**。$\omega$ が最小）の 3 種類に分かれます。 ### 5.2. 超限帰納法と超限再帰 (1) 論理式 $\varphi(\alpha)$ について、すべての順序数 $\alpha$ で「すべての $\beta<\alpha$ で $\varphi(\beta)$ ならば $\varphi(\alpha)$」が成り立つなら、すべての順序数で $\varphi(\alpha)$ が成り立つ。 (2) 論理式で定まる「関数」$G$（各集合 $x$ に集合 $G(x)$ をただ一つ対応させるもの）が与えられたとき、すべての順序数 $\alpha$ について $F(\alpha)=G(F\restriction\alpha)$ を満たす $F$ がただ一つ存在する。ここで $F\restriction\alpha$ は $\alpha$ に制限した関数（集合）である。 (1) は自然数の帰納法を順序数に広げたもの、(2) は再帰的定義を順序数に広げたものです。(2) の証明の方針は、「$\delta$ 未満の部分だけ正しく定まった関数」（近似）を考え、近似が一つしかないことと、各 $\delta$ に近似があることを (1) で示し、最後にそれらを貼り合わせて $F$ を作る、というものです。 (1) $\varphi(\alpha_0)$ が偽となる $\alpha_0$ があれば、集合 $\{\beta\in S(\alpha_0)\mid\neg\varphi(\beta)\}$ は空でなく、最小元 $\alpha$ をもつ（）。$\beta<\alpha$ では $\varphi(\beta)$ が成り立つので仮定から $\varphi(\alpha)$ となり矛盾する。 (2) 順序数 $\delta$ を定義域とする関数 $f$ で、すべての $\alpha<\delta$ について $f(\alpha)=G(f\restriction\alpha)$ を満たすものを **$\delta$-近似**と呼ぶ。二つの近似は共通の定義域で一致する（一致しない最小の $\alpha$ をとると、そこまでの制限が等しいので値も等しく、矛盾）。各 $\delta$ に $\delta$-近似が存在することを (1) で示す。$\beta<\delta$ について $\beta$-近似 $f_\beta$ がある（一意）とする。置換公理で集合 $\{f_\beta\mid\beta<\delta\}$ を作り、その和集合 $f$ は（互いに整合するので）定義域 $\bigcup_{\beta<\delta}\beta$ の近似になる。$\delta$ が極限順序数ならこれが $\delta$-近似、$\delta=S(\beta)$ なら $f_\beta\cup\{(\beta,G(f_\beta))\}$ が $\delta$-近似である。$F(\alpha)$ を「任意の $\delta>\alpha$ の $\delta$-近似の $\alpha$ での値」と定めればよい。一意性は (1) による。 [選択公理と Zorn の補題](/mathematics/foundations/axiom-of-choice-zorn) の超限帰納法（）は一つの[整列集合](/mathematics/foundations/axiom-of-choice-zorn#def-wellorder)の上の議論でした。ここでは順序数全体という「集合でない」範囲で同じ議論をしています。次の定理によって、二つの見方は一致します。 任意の整列集合 $(W,<)$ は、ただ一つの順序数と順序同型である。 この定理は、どんな整列集合も「並べ方の見本」である順序数のどれかと同じ並びをもつ、という主張です。証明では、$W$ の元 $w$ より前の部分 $W_{ **一意性。** 順序数 $\alpha,\beta$ の間の順序同型 $f$ は恒等写像であることを示す。$\gamma<\alpha$ について、$\delta<\gamma$ なら $f(\delta)=\delta$ だとする。$f$ は順序同型だから $\beta$ のうち $f(\gamma)$ より小さい元全体、すなわち集合 $f(\gamma)$ は $\{f(\delta)\mid\delta<\gamma\}=\gamma$ に等しい。よって $f(\gamma)=\gamma$。 (1) により $f$ は恒等写像で、$\alpha=\beta$。 **存在。** $w\in W$ に対し $W_{ (1)）、$F:W'\to\beta$ は順序同型である。 $W'\ne W$ と仮定し、$W\setminus W'$ の最小元を $w$ とする。$W'$ は始切片で $w\notin W'$ だから $W'=W_{ 存在の証明で置換公理を使いました。実際、置換公理を除いた体系（ツェルメロの集合論 Z）では、順序数 $\omega+\omega=\omega\cdot2$ の存在すら証明できないことが知られています。$\omega,\ \mathcal{P}(\omega),\ \mathcal{P}(\mathcal{P}(\omega)),\ldots$ を並べた集合を作るにも置換公理が要ります。置換公理は「関数の像は集合」という自然な原理ですが、日常の数学ではほとんど意識されず、超限的な構成で初めて表に出ます。 ## 6. 基数と基数算術 ### 6.1. 基数の定義 [濃度と無限](/mathematics/foundations/cardinality-and-infinity) では「$A$ と $B$ が[対等](/mathematics/foundations/cardinality-and-infinity#def-equipotent)」という関係だけを扱い、「濃度そのもの」の定義は保留しました（）。順序数を使うと、各同値類から標準的な代表を一つ選べます。 順序数 $\kappa$ が、どの $\alpha<\kappa$ とも対等でないとき、$\kappa$ を**基数**という。集合 $X$ がある順序数と対等なとき、$X$ と対等な最小の順序数（これは基数である）を $|X|$ と書く。基数 $\kappa,\lambda$ に対し $$ \kappa+\lambda=|\kappa\times\{0\}\cup\lambda\times\{1\}|,\qquad \kappa\cdot\lambda=|\kappa\times\lambda|,\qquad 2^{\kappa}=|\mathcal{P}(\kappa)| $$ と定める（右辺の $|\cdot|$ が定義されることは選択公理のもとで保証される。）。 各 $n\in\omega$ と $\omega$ は基数です（$n$ については鳩の巣原理を $n$ に関する帰納法で示せばよく、$\omega$ についてはそれが有限でないことから）。$\aleph_0=\omega$ と書きます。$\omega+1$ は $\omega$ と対等なので基数ではありません。この観察を一般化します。 無限基数 $\kappa$（すなわち $\kappa\ge\omega$ である基数）は極限順序数である。 $\kappa=S(\gamma)=\gamma\cup\{\gamma\}$ とすると、$\kappa\notin\omega$ だから $\gamma\notin\omega$、つまり $\omega\le\gamma$。$f(\gamma)=0$、$f(n)=n+1$（$n\in\omega$）、それ以外の $\xi$ で $f(\xi)=\xi$ と定めると、$f:S(\gamma)\to\gamma$ は全単射である。$\gamma<\kappa$ と $\kappa$ が対等になり、$\kappa$ が基数であることに反する。 ### 6.2. 無限基数の積 任意の無限基数 $\kappa$ について $\kappa\cdot\kappa=\kappa$。 $\aleph_0\cdot\aleph_0=\aleph_0$ は [濃度と無限](/mathematics/foundations/cardinality-and-infinity) の で、対角線に沿って数える方法で示しました。一般の $\kappa$ でもアイデアは同じで、「正方形 $\mu\times\mu$ を大きくしていく順」に並べます。証明の筋は、$\kappa\times\kappa$ を整列して並べると、各元の前にくる元の個数が $\kappa$ 未満になる、というものです。もし並べた全体が $\kappa$ より長ければ、ある元の前に $\kappa$ 個の元が並んでしまい、これと矛盾します。 無限基数 $\kappa$ についての超限帰納法（ (1)）で示す。$\kappa$ より小さい無限基数 $\nu$ では $\nu\cdot\nu=\nu$ と仮定する。 $\kappa\times\kappa$ に順序 $\lhd$ を $$ (\alpha,\beta)\lhd(\gamma,\delta)\iff \bigl(\max(\alpha,\beta),\alpha,\beta\bigr) \text{ が } \bigl(\max(\gamma,\delta),\gamma,\delta\bigr) \text{ より辞書式に小さい} $$ で定める。これは整列順序である：空でない部分集合に対し、まず $\max$ の値が最小のものに絞り、その中で $\alpha$ が最小のもの、さらに $\beta$ が最小のものをとればよい（ を 3 回使う）。 $(\alpha,\beta)\in\kappa\times\kappa$ を固定し、$\mu=S(\max(\alpha,\beta))$ とおく。$(\gamma,\delta)\lhd(\alpha,\beta)$ なら $\max(\gamma,\delta)\le\max(\alpha,\beta)<\mu$ なので、$(\alpha,\beta)$ の前にある元全体は $\mu\times\mu$ に含まれる。 より $\mu<\kappa$ である。$\mu$ が有限なら $\mu\times\mu$ は有限。$\mu$ が無限なら $\nu=|\mu|$ は $\nu\le\mu<\kappa$ を満たす無限基数で、帰納法の仮定から $|\mu\times\mu|=\nu\cdot\nu=\nu<\kappa$。いずれにせよ、**各元の前にある元全体は $\kappa$ より小さい順序数と対等**である。 により $(\kappa\times\kappa,\lhd)$ はある順序数 $\theta$ と同型である。$\kappa<\theta$ なら、同型で $\kappa\in\theta$ に対応する元 $p$ の前にある元全体は $\kappa$ と同型、とくに対等となり、前段に反する。よって $\theta\le\kappa$ で、$\kappa\times\kappa$ から $\theta\subseteq\kappa$ への単射がある。逆向きには $\alpha\mapsto(\alpha,0)$ が単射である。カントール–シュレーダー–ベルンシュタインの定理（）により $|\kappa\times\kappa|=\kappa$。 基数 $\kappa,\lambda$ の少なくとも一方が無限で、どちらも $0$ でないとき、$\kappa+\lambda=\kappa\cdot\lambda=\max(\kappa,\lambda)$。 $\mu=\max(\kappa,\lambda)$ とおくと $\mu$ は無限基数。単射の列 $$ \mu\hookrightarrow\kappa\times\{0\}\cup\lambda\times\{1\}\hookrightarrow\mu\times\{0,1\}\hookrightarrow\mu\times\mu $$ と より $\mu\le\kappa+\lambda\le\mu$。積も $\mu\hookrightarrow\kappa\times\lambda\hookrightarrow\mu\times\mu$（最初の単射は、小さいほうの因子の元 $0$ を固定して作る）から同様である。 和と積が「大きいほうを取る」だけになってしまうのに対し、冪は本当に大きくなります。カントールの定理（）により $2^{\kappa}>\kappa$ です。無限基数を小さい順に $\aleph_0<\aleph_1<\aleph_2<\cdots<\aleph_\omega<\cdots$ と並べることもできます。$\aleph_{\alpha+1}$ は $\aleph_\alpha$ より大きい最小の基数、極限順序数 $\lambda$ では $\aleph_\lambda=\sup_{\alpha<\lambda}\aleph_\alpha$ と、超限再帰（ (2)）で定めます。$\aleph_{\alpha}$ より大きい基数が存在することは、選択公理のもとでは $\mathcal{P}(\aleph_\alpha)$ を整列すれば分かります（選択公理がなくてもハルトークスの定理で示せます）。 ### 6.3. 共終数と正則基数 和と積は「大きいほうを取る」でしたが、無限基数はもう一つ、「下から何段で届くか」という量を持ちます。$\omega$ には $0, 1, 2, \ldots$ の $\omega$ 段で届き、$\aleph_\omega$ にも $\aleph_0, \aleph_1, \aleph_2, \ldots$ の $\omega$ 段で届きますが、$\aleph_1$ には[可算](/mathematics/foundations/cardinality-and-infinity#def-countable)段では届きません。この違いを捉えるのが共終数です。次の定義の「非有界な写像」とは、$\beta$ 段の階段を上がっていくとき、$\alpha$ より小さいどの順序数も、いつかは踏み越えられる、という性質をもつ写像のことです。 $\alpha$ を順序数とする。順序数 $\beta$ からの写像 $f : \beta \to \alpha$ が $\alpha$ で**非有界**であるとは、すべての $\gamma < \alpha$ に対し $\gamma \le f(\xi)$ となる $\xi < \beta$ が存在することをいう。非有界な写像 $f : \beta \to \alpha$ が存在するような順序数 $\beta$ の最小のものを $\alpha$ の**共終数**といい、$\mathrm{cf}(\alpha)$ と書く（$\beta = \alpha$、$f$ = 恒等写像が条件を満たすので、$S(\alpha)$ の部分集合の最小元として存在する。）。無限基数 $\kappa$ が $\mathrm{cf}(\kappa) = \kappa$ を満たすとき、$\kappa$ は**正則**であるといい、そうでないとき**特異**であるという。 1. $\mathrm{cf}(0) = 0$ で、$\mathrm{cf}(S(\gamma)) = 1$ である。 2. $\alpha$ が極限順序数なら $\omega \le \mathrm{cf}(\alpha) \le \alpha$ である。とくに $\mathrm{cf}(\omega) = \omega$ である。 3. $\mathrm{cf}(\aleph_\omega) = \omega$ である。したがって $\aleph_\omega$ は特異基数である。 1: $\alpha = 0$ では、空写像 $0 \to 0$ が（$\gamma < 0$ となる $\gamma$ がないので）非有界で、$\beta = 0$ が最小です。$\alpha = S(\gamma)$ では、$\gamma \le f(\xi)$ となる $\xi$ が必要なので $\beta \ne 0$ で、$f(0) = \gamma$ とおけば $\beta = 1$ の非有界写像です。 2: $\le \alpha$ は恒等写像です。$\beta = n \in \omega$ とし $f : n \to \alpha$ を取る。$n = 0$ なら $\gamma = 0 < \alpha$ に対し $\gamma \le f(\xi)$ となる $\xi$ がなく非有界でない。$n \ge 1$ なら $m = \max_{\xi）、2 より $\mathrm{cf}(\aleph_\omega) = \omega < \aleph_\omega$ です。 $\alpha$ が極限順序数ならば、$\mathrm{cf}(\alpha)$ は正則基数である。すなわち $\mathrm{cf}(\alpha)$ は無限基数で、$\mathrm{cf}(\mathrm{cf}(\alpha)) = \mathrm{cf}(\alpha)$ である。 $\beta = \mathrm{cf}(\alpha)$ とし、非有界写像 $f : \beta \to \alpha$ を 1 つ取る。 の 2 より $\beta \ge \omega$ である。 **(i) $\beta$ は極限順序数である。** $\beta = \delta + 1$ とすると、$\beta \ge \omega$ から $\delta \ge \omega$、とくに $\delta > 0$ である。$g(\eta) = \max(f(\eta), f(\delta))$（$\eta < \delta$）と定めると、$g : \delta \to \alpha$ は非有界である。実際、$\gamma < \alpha$ に対し $\gamma \le f(\xi)$ となる $\xi \le \delta$ をとり、$\xi < \delta$ なら $\gamma \le g(\xi)$、$\xi = \delta$ なら $\gamma \le f(\delta) \le g(0)$ である。これは $\beta$ の最小性に反する。 **(ii) $f$ は単調非減少としてよい。** $f'(\xi) = \sup_{\eta \le \xi} f(\eta)$（ (1) により $\bigcup_{\eta \le \xi} f(\eta)$）と定める。$f'(\xi) \ge f(\xi)$ で $f'$ は単調非減少である。$f'(\xi) = \alpha$ となる $\xi < \beta$ があれば、$\gamma < \alpha = \sup_{\eta \le \xi}f(\eta)$ から $\gamma < f(\eta)$ となる $\eta \le \xi$ があるので、$f$ を $\xi + 1$ に制限した写像が非有界になる。(i) より $\xi + 1 < \beta$ なので、これも $\beta$ の最小性に反する。したがって $f' : \beta \to \alpha$ は単調非減少な非有界写像である。 **(iii) $\mathrm{cf}(\beta) = \beta$。** $\mathrm{cf}(\beta) \le \beta$ は の 2 による。$h : \gamma \to \beta$ を非有界写像で $\gamma < \beta$ とする。このとき $f' \circ h : \gamma \to \alpha$ は非有界である：$\delta < \alpha$ に対し $\delta \le f'(\xi)$ となる $\xi < \beta$ があり、$h$ が非有界なので $\xi \le h(\eta)$ となる $\eta < \gamma$ があり、$f'$ の単調性から $\delta \le f'(\xi) \le f'(h(\eta))$ である。これは $\beta$ の最小性に反するので、$\mathrm{cf}(\beta) = \beta$ である。 **(iv) $\beta$ は基数である。** そうでなければ、ある $\delta < \beta$ と全単射 $k : \delta \to \beta$ がある（）。全射なので $k$ は非有界で、$\mathrm{cf}(\beta) \le \delta < \beta$ となり (iii) に反する。 この証明は選択公理を使わない（(ii) の単調化も上限を取るだけで、選択は要らない）。 選択公理を仮定する。$\kappa$ を無限基数、$\lambda$ を $\kappa$ より大きい最小の基数とする。このとき $\lambda$ は正則基数である。とくに $\aleph_1$ は正則で、$\aleph_1$ の可算部分集合は $\aleph_1$ の中に上界を持つ。 $\lambda$ は無限基数なので極限順序数で（）、 の 2 より $\mathrm{cf}(\lambda) \le \lambda$ である。非有界写像 $f : \beta \to \lambda$ で $\beta < \lambda$ のものがあったと仮定して矛盾を導く。 $\beta < \lambda$ なら $|\beta| \le \beta < \lambda$ で、$|\beta|$ は基数なので $\lambda$ の最小性から $|\beta| \le \kappa$ である。同様に $f(\xi) < \lambda$ から、$|f(\xi) + 1| \le \kappa + 1 = \kappa$ である（）。非有界性から $\lambda = \bigcup_{\xi < \beta} (f(\xi) + 1)$ である。選択公理により、各 $\xi < \beta$ に単射 $g_\xi : f(\xi) + 1 \to \kappa$ を選ぶ。$\gamma < \lambda$ に対し $\xi_\gamma$ を $\gamma \le f(\xi)$ となる最小の $\xi$ とし、$\Phi(\gamma) = (\xi_\gamma, g_{\xi_\gamma}(\gamma)) \in \beta \times \kappa$ と定める。$\Phi(\gamma) = \Phi(\gamma')$ なら $\xi_\gamma = \xi_{\gamma'}$ で、$g_{\xi_\gamma}$ の単射性から $\gamma = \gamma'$ である。よって $\Phi$ は単射で、$|\beta| \le \kappa$ と から $\lambda \le |\beta \times \kappa| \le \kappa \cdot \kappa = \kappa$ となり、$\lambda > \kappa$ に反する。したがって $\mathrm{cf}(\lambda) = \lambda$ である。 $\lambda = \aleph_1$（$\kappa = \aleph_0$）の場合の後半：可算部分集合 $X \subseteq \aleph_1$ が上界を持たないとすると、$X$ を可算順序数 $\beta \le \omega$ で数え上げる（$X$ が有限なら最大元があり上界を持つので、$X$ は可算無限としてよい）ことで非有界写像 $\beta \to \aleph_1$ ができ、$\mathrm{cf}(\aleph_1) \le \omega < \aleph_1$ となって前半に反する。 順序数に限らず、半順序集合 $P$ の部分集合 $S$ が**共終**であるとは、すべての $p \in P$ に対し $p \le s$ となる $s \in S$ があることをいい、共終な部分集合の濃度の最小値を $P$ の共終数と呼びます。たとえば $\mathbb{R}$ の共終数は $\aleph_0$（$\mathbb{N}$ が共終）、最大元をもつ半順序集合では $1$ です。順序数 $\alpha$（極限順序数）の場合、共終な部分集合の濃度の最小値は、ここで定義した $\mathrm{cf}(\alpha)$ と一致します。 の (ii) の単調化と同じ議論で、非有界写像から共終な部分集合（像）が、共終な部分集合を整列して数え上げれば非有界写像が得られるからです。 ## 7. 選択公理の同値形 [選択公理と Zorn の補題](/mathematics/foundations/axiom-of-choice-zorn) では、選択公理、Zorn の補題、整列可能定理が同値であることを示しました（）。その証明が使っているのは、部分集合の切り出し、和集合、冪集合、関数の制限と合併、そして整列集合上の超限帰納法だけです。どれも ZF の公理で正当化できる操作なので、あの同値定理は**ZF の定理**として読めます。ここに、順序数を使った同値形を一つ加えます。 ZF において、次は同値である。 1. 選択公理。 2. すべての集合はある順序数と対等である（したがって $|X|$ が定義される）。 (1)⇒(2)：選択公理から整列可能定理（）により $X$ に整列順序が入り、 により $X$ はある順序数と順序同型、とくに対等である。 (2)⇒(1)：$x$ を空でない集合からなる集合とし、$\bigcup x$ と順序数 $\alpha$ の全単射 $g:\bigcup x\to\alpha$ をとる。$y\in x$ に対し、$g[y]\subseteq\alpha$ は空でないので最小元をもつ。$f(y)=g^{-1}(\min g[y])$ と定めれば $f(y)\in y$ であり、$f$ は（分出公理で $x\times\bigcup x$ の部分集合として作れる）選択関数である。 (2)⇒(1) の証明では、選ぶたびに「最小のもの」という規則を使っているので、選択公理は要りません。整列された世界では選択は自由にできる、というのが選択公理の正体だと読むことができます。 選択公理は、ベクトル空間の基底の存在（）や極大イデアルの存在（）のほか、[Banach 空間の基本定理](/mathematics/functional-analysis/banach-spaces) のハーン–バナッハの定理（一般の場合）で使われます。解析学でも、可算個の選択（ の証明で各 $n$ に単射を選んでいる箇所など）は頻繁に現れます。これらの定理を ZFC までさかのぼるときには、公理 10 を使っていることになります。 ## 8. 連続体仮説と独立性 $|\mathbb{R}|=|\mathcal{P}(\mathbb{N})|=2^{\aleph_0}$ でした（）。カントールの定理から $2^{\aleph_0}\ge\aleph_1$ です。カントールは等号が成り立つと予想しました。 **連続体仮説** (CH) とは、$2^{\aleph_0}=\aleph_1$ という主張である。すなわち、$\mathbb{R}$ の無限部分集合は $\mathbb{N}$ と対等か $\mathbb{R}$ と対等かのいずれかである。 ZF が無矛盾ならば、 1. （ゲーデル 1938）ZFC + CH は無矛盾である。 2. （コーエン 1963）ZFC + ¬CH は無矛盾である。 したがって ZFC が無矛盾なら、CH は ZFC から証明も反証もできない。同じことが選択公理と ZF の間にも成り立つ。 この定理は主張だけを述べます。(1) はゲーデルの**構成可能集合のクラス** $L$ が ZFC + CH のモデルになることを示し、(2) はコーエンの**強制法**で、ZFC のモデルに $\aleph_2$ 個の新しい実数を付け加えたモデルを作ります。いずれも本格的な道具立てが要り、Kunen や Jech の教科書（参考文献）で 1 章から数章を占めます。 が「ZF が無矛盾ならば」という条件付きの形をしているのには理由があります。ZFC は自然数の算術を含む帰納的に公理化された理論なので、第二不完全性定理（）により、ZFC が無矛盾なら ZFC は自分の無矛盾性を証明できません。だから独立性の結果は、いつも相対的な無矛盾性として述べられます。CH の独立性は、不完全性定理の「ゲーデル文」とは性質が違い、算術の文ではない点にも注意してください（）。 ZFC は Rikai の数学側の土台ですが、ZFC で決まらない自然な問いがあることも、この節が示しています。この先の章では、同じ「証明とは何か」を別の角度、つまり計算と型の側から見直します。[型なしラムダ計算](/mathematics/logic-and-type-theory/lambda-calculus) で計算の素朴なモデルを作り、カリー＝ハワード対応を経て、集合ではなく**型**を土台に数学を組み立てる依存型理論と Lean へ進みます。 ## 9. 演習 正則性公理から、どの集合 $x$ についても $x\notin x$ であること、また $x\in y$ かつ $y\in x$ となる $x,y$ は存在しないことを示せ。 $x\in x$ とする。集合 $\{x\}$ に正則性公理を使うと、$\{x\}$ の元で $\{x\}$ と交わらないものがある。元は $x$ だけなので $x\cap\{x\}=\varnothing$。しかし $x\in x$ より $x\in x\cap\{x\}$ で矛盾。$x\in y\in x$ なら、$\{x,y\}$ に正則性公理を使う。$x\cap\{x,y\}$ は $y$ を含み、$y\cap\{x,y\}$ は $x$ を含むので、どちらの元も $\{x,y\}$ と交わり、矛盾。 順序数 $\alpha,\beta$ に対し、$\alpha\times\{0\}\cup\beta\times\{1\}$ に「$\{0\}$ の部分をすべて $\{1\}$ の部分より前に置き、各部分の中では元の順序」で整列順序を入れ、その順序型（）を $\alpha+\beta$ と書く。$1+\omega=\omega$ だが $\omega+1\ne\omega$ であることを示せ。 $1+\omega$ は $(0,0)$ のあとに $(0,1),(1,1),(2,1),\ldots$ が続く順序である。$(0,0)\mapsto0$、$(n,1)\mapsto n+1$ は $\omega$ への順序同型なので、 の一意性から $1+\omega=\omega$。一方 $\omega+1$ には最大元 $(0,1)$ があるが、$\omega$ には最大元がない（$n (1) 任意の集合 $X$ について、$\mathcal{P}(X)\times\mathcal{P}(X)$ と $\mathcal{P}(X\times\{0,1\})$ は対等であることを示せ（選択公理は使わない）。(2) これと を使い、$|\mathbb{R}\times\mathbb{R}|=|\mathbb{R}|$ を示せ。 (1) $(A,B)\mapsto A\times\{0\}\cup B\times\{1\}$ は全単射で、逆写像は $C\mapsto(\{x\mid(x,0)\in C\},\{x\mid(x,1)\in C\})$。順序対の性質（）で 2 つの成分が区別できることを使っている。(2) $|\mathbb{R}|=|\mathcal{P}(\omega)|$（。$\mathbb{N}$ と $\omega$ は対等）。(1) より $\mathbb{R}\times\mathbb{R}$ は $\mathcal{P}(\omega\times\{0,1\})$ と対等で、 より $\omega\times\{0,1\}$ は $\omega$ と対等（ここは $\aleph_0+\aleph_0=\aleph_0$ なので、偶数と奇数に振り分ける明示的な全単射でもよい）。対等な集合の冪集合は対等なので、$|\mathbb{R}\times\mathbb{R}|=|\mathcal{P}(\omega)|=|\mathbb{R}|$。平面と直線は「点の個数」では区別できません。 $\omega_1=\aleph_1$ を最小の非可算順序数とする。選択公理を仮定して、$\omega_1$ の可算部分集合 $X$ は $\omega_1$ の中に上界をもつこと（すなわち $\sup X<\omega_1$）を示せ。 $X$ の各元 $\alpha$ は $\alpha<\omega_1$ なので高々可算である（$\omega_1$ は最小の非可算順序数）。 (1) より $\sup X=\bigcup X$ は順序数で、可算個の高々可算集合の和集合だから、（各 $\alpha$ に単射を選ぶところで選択公理を使う）により高々可算である。よって $\bigcup X\ne\omega_1$ で、比較可能性（）から $\bigcup X<\omega_1$。$\bigcup X+1<\omega_1$（）も上界になる。可算の段数で $\omega_1$ に届かないこの性質は、ボレル集合の階層などで繰り返し使われます。 ## 参考文献 - K. Kunen, *Set Theory*, Studies in Logic 34, College Publications, 2011 — 第 I 章（ZFC の公理、順序数、基数）、第 II 章（構成可能集合）、第 IV 章（強制法）。 - T. Jech, *Set Theory*, The Third Millennium Edition, Springer, 2003 — 第 1〜3 章（公理、順序数、基数算術）、第 13・14 章（$L$ と強制法）。 - H. B. Enderton, *Elements of Set Theory*, Academic Press, 1977 — 第 4・5 章（自然数と、整数・有理数・実数の構成）。 - W. Rudin, *Principles of Mathematical Analysis*, 3rd ed., McGraw-Hill, 1976 — 第 1 章付録（デデキント切断による実数の構成）。 - K. Gödel, "The consistency of the axiom of choice and of the generalized continuum-hypothesis", *Proceedings of the National Academy of Sciences* 24 (1938), 556–557. - P. J. Cohen, "The independence of the continuum hypothesis", *Proceedings of the National Academy of Sciences* 50 (1963), 1143–1148.