# 選択公理と Zorn の補題：「無限個の選択」を極大元に置き換える > 選択公理・Zorn の補題・整列可能定理が互いに同値であることを証明し、超限帰納法、Cantor–Bernstein の定理、Hamel 基底と極大イデアルの存在への使い方を示す。 > https://rikai.mugen-giken.com/mathematics/foundations/axiom-of-choice-zorn ## 0. この記事の要点 中身の入った箱が無限個あるとき、どの箱からも中身を 1 つずつ取り出して並べられるでしょうか。箱が有限個なら当たり前ですが、無限個になると、「できる」と認めるかどうかが数学の大事な分かれ目になります。この記事ではその認め方（選択公理）と、それと同じ強さをもつ 2 つの主張を取り上げ、読み終えると、「存在するが書き下せない」対象（ベクトル空間の基底など）を示すときの定石を使えるようになります。 - **選択公理**は「空でない集合を無限個並べたとき、各集合から 1 個ずつ同時に選べる」という主張です。有限個なら論理だけで証明できますが、無限個では公理として仮定しなければ導けません。 - **Zorn の補題**（空でない半順序集合で、どの鎖も上界を持てば極大元が存在する。鎖は大小がすべて比較できる部分集合、極大元は「それより真に大きい元がない」元のことで、§2 で定義します）と**整列可能定理**（どんな集合にも整列順序、つまりどの空でない部分集合にも最小元がある順序が入る）は、選択公理と同値です。この記事では 3 つの同値を循環させて完全に証明します。 - 整列集合では**超限帰納法**が使えます。これは「最小元が存在する」という性質の言い換えにすぎません（数学的帰納法を、自然数以外の整列集合に広げたものです）。 - 実際の使い方は決まっています。「条件を満たす部分的な対象全体」を包含で順序づけ、鎖の合併が上界になることを確かめ、極大元が欲しいものであることを示します。この記事では、任意の 2 集合の濃度の比較可能性、**Hamel 基底**（[ベクトル空間](/mathematics/linear-algebra/vector-spaces#def-vector-space)の基底）の存在、**極大イデアル**（これ以上大きくできない真のイデアル）の存在を、この型で証明します。 - Cantor–Bernstein の定理は選択公理を使わずに証明できます。その証明も与えます。 ## 1. 動機：有限回の選択と無限回の選択 靴下が無限組あるとします。各組から 1 個ずつ選ぶには、「左足の方」と指定すれば足ります。靴ならこれで終わりです。靴下は左右の区別がないので、1 組ごとに 2 個のどちらかを恣意的に決めるしかなく、無限組を同時に決める一般的な規則がありません。ラッセルが挙げたこの例は、選択公理が「見えにくいが確かに存在する仮定」であることを教えてくれます。 有限個の集合 $A_1, \ldots, A_n$ が空でないとき、各 $A_i$ から元 $a_i$ を選ぶことは、$n$ についての帰納法で論理だけから示せます。「$A_1$ には元が存在する」から 1 個取り、次に $A_2$ から取り、……と進めれば $n$ 回で終わります。無限個の集合の族に対しては、この手続きが終わりません。族全体から一斉に選ぶ関数が存在するという主張は、集合論の他の公理（[集合と論理](/mathematics/foundations/sets-and-logic)で触れた外延性など）からは導けないことが知られています（Cohen 1963）。そこで公理として採用します。 選択公理は気づかないうちに使われています。たとえば[濃度と無限](/mathematics/foundations/cardinality-and-infinity)の の証明では、各 $A_n$ から $\mathbb{N}$ への単射 $u_n$ を「1 つずつ選んで固定」しました。可算個の選択なので選択公理の弱い形（可算選択公理）で済みますが、選択が入っていることに変わりはありません。 選択公理を採用すると、次のような「存在するが具体的に書けない」対象が手に入ります。 - 任意のベクトル空間に基底がある（実数全体を有理数体上のベクトル空間とみたときの基底が存在する）。 - 単位元をもつ可換環の真のイデアルは極大イデアルに含まれる。 - 任意の集合に整列順序が入る。実数全体にもです。 反対側には、Banach–Tarski のパラドックス（球を有限個に分割して並べ替えると同じ球が 2 個できる）のような直観に反する帰結があります。この記事は選択公理の是非を論じず、**何が選択公理と同値で、どう使われるか**を定理として確定させます。後続の記事では、Hahn–Banach の定理、Tychonoff の定理（[積位相・商位相と Tychonoff の定理](/mathematics/topology/products-quotients-tychonoff)）、極大イデアルを使う議論が、すべてここで証明する Zorn の補題に帰着します。 ## 2. 準備：半順序と整列集合 集合 $P$ 上の二項関係 $\le$ が**半順序**であるとは、次の 3 条件を満たすことをいう（順序関係の用語は[関係と同値関係](/mathematics/foundations/equivalence-relations)の反射律・推移律と同じ）。 1. （反射律）$x \le x$。 2. （反対称律）$x \le y$ かつ $y \le x$ ならば $x = y$。 3. （推移律）$x \le y$ かつ $y \le z$ ならば $x \le z$。 組 $(P, \le)$ を**半順序集合**という。$x \le y$ かつ $x \ne y$ のとき $x < y$ と書く。任意の $x, y \in P$ について $x \le y$ または $y \le x$ が成り立つとき、$\le$ は**全順序**であるという。$P$ の部分集合 $C$ が、$\le$ を制限したとき全順序になっているなら、$C$ を**鎖**という。空集合も鎖である。 $(P, \le)$ を半順序集合、$S \subseteq P$ とする。 1. $u \in P$ が $S$ の**上界**であるとは、すべての $s \in S$ について $s \le u$ が成り立つことをいう。 2. $m \in P$ が $P$ の**極大元**であるとは、$m < x$ となる $x \in P$ が存在しないことをいう。 3. $g \in P$ が $P$ の**最大元**であるとは、すべての $x \in P$ について $x \le g$ が成り立つことをいう。 極大元と最大元は別の概念です。最大元はすべての元より大きく、極大元は「それより真に大きい元がない」だけです。比較できない元があれば、極大元が複数あることも、最大元がまったくないこともあります。 $P = \{0, 1, 2, 3, 4, 5\}$ に、次の関係から生成される半順序（反射・推移で閉じたもの）を入れます。 $$ 0 < 1,\quad 0 < 2,\quad 1 < 3,\quad 1 < 4,\quad 2 < 5. $$ 極大元は $3, 4, 5$ の 3 個です（これらより真に大きい元はない）。最大元はありません。実際 $3 \le 4$ も $4 \le 3$ も成り立たないので、$3$ と $4$ はどちらも最大元でなく、$5$ も同様です。鎖 $\{0, 1, 3\}$ は上界 $3$ を持ち、鎖 $\{0, 1\}$ の上界は $1, 3, 4$ の 3 個あります。鎖 $\{0\}$ の上界は $0$ から $5$ のすべてです。
0 1 2 3 4 5
有限な空でない半順序集合には、必ず極大元があります。$x_0$ を任意に取り、$x_0 < x_1$ となる $x_1$ があれば取り、これをくり返すと、$x_0 < x_1 < x_2 < \cdots$ はすべて異なる元なので、元の個数が有限である限り有限回で止まります。止まった元が極大元です。無限の場合、この手続きが止まる保証がないので、「鎖が上界を持つ」という追加の条件が要ります。それが Zorn の補題です。 全順序集合 $(W, \le)$ が**整列集合**であるとは、$W$ の空でない任意の部分集合が最小元を持つことをいう。このときの $\le$ を**整列順序**という。$W$ の部分集合 $S$ が**始切片**であるとは、$x \in S$ かつ $y \le x$ ならば $y \in S$ が成り立つことをいう。$a \in W$ に対し $W_{ $\mathbb{N}$ は通常の大小で整列集合です（[証明の技術](/mathematics/foundations/proof-techniques)の ）。$\mathbb{Z}$ や区間 $[0, 1]$ は通常の大小では整列集合ではありません（最小元をもたない部分集合 $\mathbb{Z}$、$(0, 1]$ がある）。ただし整列可能定理（）によれば、$\mathbb{Z}$ にも $[0, 1]$ にも別の順序で整列順序が入ります。$\mathbb{Z}$ は $0, 1, -1, 2, -2, \ldots$ と並べれば明示的に整列できますが、$[0, 1]$ の整列順序は具体的には書き下せません。 ### 2.1. 擬順序・辞書式順序・順序同型 半順序の周辺で、この先の記事が使う言葉を 3 つ足しておきます。この節は寄り道で、§3 以降の同値定理の証明には使いません。急ぐ場合は読み飛ばして §3 に進んでかまいません。 集合 $P$ 上の二項関係 $\lesssim$ が反射律（$x \lesssim x$）と推移律（$x \lesssim y$ かつ $y \lesssim z$ なら $x \lesssim z$）を満たすとき、$\lesssim$ を**擬順序**（前順序）といい、$(P, \lesssim)$ を擬順序集合という。反対称律は要求しない。 半順序は擬順序で、擬順序は「反対称律を落とした半順序」です。反対称律が成り立たない原因は $x \lesssim y$ かつ $y \lesssim x$ なのに $x \ne y$ という元の組ですが、そうした元をまとめて 1 つの元と見ると半順序に戻せます。 $(P, \lesssim)$ を擬順序集合とし、$x \sim y$ を「$x \lesssim y$ かつ $y \lesssim x$」で定める。 1. $\sim$ は $P$ 上の同値関係である。 2. 商集合 $P/{\sim}$ 上で $[x] \le [y] \iff x \lesssim y$ と定めると、これは代表元の取り方によらず定まり（well-defined）、半順序である。 3. $\lesssim$ が半順序であることは、$\sim$ が等号であることと同値である。 1: 反射律は $\lesssim$ の反射律から、対称律は定義の対称性から、推移律は $x \lesssim y \lesssim z$ と $z \lesssim y \lesssim x$ に $\lesssim$ の推移律を使って従います。 2: $x \sim x'$、$y \sim y'$ とする。$x \lesssim y$ なら $x' \lesssim x \lesssim y \lesssim y'$ から $x' \lesssim y'$ です。逆も対称です。よって $[x] \le [y]$ の定義は代表元によりません（ の考え方、すなわち well-defined の確認です）。反射律・推移律は $\lesssim$ から遺伝します。反対称律：$[x] \le [y]$ かつ $[y] \le [x]$ なら $x \lesssim y$ かつ $y \lesssim x$ で、$x \sim y$、つまり $[x] = [y]$ です。 3: $\lesssim$ が反対称なら、$x \sim y$ は $x = y$ を意味します。逆に $\sim$ が等号なら、$x \lesssim y$ かつ $y \lesssim x$ から $x = y$ です。 (a) $\mathbb{Z}$ 上の整除 $a \mid b \iff \exists k \in \mathbb{Z},\ b = ka$ は擬順序です（反射律は $k = 1$、推移律は $k$ の積）。$a \mid b$ かつ $b \mid a$ なら、$b = ka$、$a = lb$ から $a = lka$ で、$a = 0$ か $lk = 1$（$k = \pm1$）なので、$a \sim b \iff a = \pm b$ です。$\mathbb{Z}/{\sim}$ は、非負整数の整除による半順序集合と同一視でき、$0$ が最大元になります。 (b) ある集合 $X$（たとえば $\mathbb{R}$）の部分集合の全体の上で $A \lesssim B$ を「$A$ から $B$ への単射がある」で定めると擬順序です。$A \sim B$ は対等で、 は、商 $\lesssim/{\sim}$、すなわち濃度の大小（）が反対称、つまり半順序になることを述べています。擬順序であって半順序でないことは、$\mathbb{N} \lesssim \mathbb{Z}$、$\mathbb{Z} \lesssim \mathbb{N}$、$\mathbb{N} \ne \mathbb{Z}$ から分かります。 次に、全順序を積に延ばす最も基本的な方法です。 $(P, <_P)$、$(Q, <_Q)$ を全順序集合（$<$ は狭義の順序）とする。直積 $P \times Q$ の**辞書式順序** $<_{\mathrm{lex}}$ を $$ (p, q) <_{\mathrm{lex}} (p', q') \iff p <_P p' \ \text{ または }\ (p = p' \text{ かつ } q <_Q q') $$ で定める。$n$ 個の直積 $P_1 \times \cdots \times P_n$ には、$P_1 \times (P_2 \times \cdots \times P_n)$ として帰納的に辞書式順序を入れる。 辞書で単語を引くとき、最初の文字を比べ、同じなら次の文字を比べる、という規則そのものです。 $(P, <_P)$、$(Q, <_Q)$ を全順序集合とする。 1. $<_{\mathrm{lex}}$ は $P \times Q$ 上の全順序である。 2. 成分ごとの順序（$p \le_P p'$ かつ $q \le_Q q'$）で $(p, q)$ が $(p', q')$ 以下なら、$(p, q) \le_{\mathrm{lex}} (p', q')$ である。 3. $P, Q$ がともに整列集合なら、$(P \times Q, <_{\mathrm{lex}})$ も整列集合である。 1: 非反射的なこと：$(p, q) <_{\mathrm{lex}} (p, q)$ なら $p <_P p$ または $q <_Q q$ で、どちらも起きません。推移律：$(p, q) < (p', q') < (p'', q'')$ とします。定義から $p \le_P p' \le_P p''$ です。この 2 つの不等号の少なくとも一方が狭義なら $p <_P p''$ で、$(p, q) < (p'', q'')$ です。どちらも等号なら $p = p' = p''$ で、$q <_Q q' <_Q q''$ から $q <_Q q''$ なので、やはり $(p, q) < (p'', q'')$ です。全順序性：$(p, q) \ne (p', q')$ とする。$p \ne p'$ なら $<_P$ の全順序性で $p <_P p'$ か $p' <_P p$ の一方が成り立ち、それが辞書式の大小を決めます。$p = p'$ なら $q \ne q'$ で、$q$ と $q'$ の大小が決めます。 2: $p <_P p'$ ならそのまま辞書式で小さい。$p = p'$ のとき $q \le_Q q'$ なので、$q = q'$（等しい）または $q <_Q q'$ です。 3: $S \subseteq P \times Q$ を空でないとする。第 1 成分の集合 $\{p \mid \exists q,\ (p, q) \in S\}$ の最小元 $p_0$ をとり、$\{q \mid (p_0, q) \in S\}$ の最小元 $q_0$ をとる。$(p, q) \in S$ なら $p_0 \le_P p$ で、$p_0 <_P p$ なら $(p_0, q_0) <_{\mathrm{lex}} (p, q)$、$p_0 = p$ なら $q_0 \le_Q q$ です。よって $(p_0, q_0)$ は $S$ の最小元です。 $\mathbb{N}^2$ に成分ごとの順序を入れると、$(1, 2)$ と $(2, 1)$ は比較できません。辞書式順序では $(1, 2) <_{\mathrm{lex}} (2, 1)$ で、任意の 2 元が比較できます。 の 3 により $(\mathbb{N}^2, <_{\mathrm{lex}})$ は整列集合で、$(1, 1), (1, 2), (1, 3), \ldots$ がすべて $(2, 1)$ より前に来るため、$(2, 1)$ は「$\omega$ 個の元の後ろ」にある元です。この順序型は[順序数](/mathematics/logic-and-type-theory/axiomatic-set-theory#def-ordinal) $\omega \cdot \omega$ です。 最後に、順序を保つ対応です。 $(P, \le_P)$、$(Q, \le_Q)$ を半順序集合とする。写像 $f : P \to Q$ が $x \le_P y \iff f(x) \le_Q f(y)$ をすべての $x, y \in P$ で満たすとき**順序埋め込み**という。全射な順序埋め込みを**順序同型**といい、順序同型が存在するとき $P \cong Q$ と書く。 1. 順序埋め込みは単射である。順序同型の逆写像と合成は順序同型であり、$\cong$ は反射的・対称的・推移的である。 2. $P, Q$ が全順序集合のとき、狭義単調増加（$x < y \Rightarrow f(x) < f(y)$）な全射 $f : P \to Q$ は順序同型である。半順序集合では、順序を保つ全単射（$x \le y \Rightarrow f(x) \le f(y)$）が順序同型であるとは限らない。 3. 順序同型は最大元・最小元・鎖・整列性を保つ。 1: $f(x) = f(y)$ なら $f(x) \le f(y)$ と $f(y) \le f(x)$ から $x \le y$ と $y \le x$ で、反対称律により $x = y$ です。恒等写像は順序同型です。順序同型 $f$ の逆写像 $g$ は、$g(u) \le g(v) \iff f(g(u)) \le f(g(v)) \iff u \le v$ で順序同型です。合成も同様に、同値の連鎖で確かめられます。 2: $f(x) \le f(y)$ とする。$y < x$ なら全順序性より $f(y) < f(x)$ で矛盾するので $x \le y$ です。反例：$P = \{a, b\}$（$a, b$ は比較不能）、$Q = \{0 < 1\}$ とし、$f(a) = 0$、$f(b) = 1$ とすると、$f$ は順序を保つ全単射ですが、$f(a) \le f(b)$ なのに $a \le b$ ではなく、順序同型ではありません。 3: $m$ が $P$ の最大元なら、任意の $v \in Q$ は全射性から $v = f(x)$ と書け、$x \le m$ から $v = f(x) \le f(m)$ なので、$f(m)$ は $Q$ の最大元です。最小元、鎖（比較可能性は $\iff$ で保たれる）、整列性（部分集合の最小元は像の最小元に写る）も同様です。 $x \mapsto \dfrac{x}{1 + |x|}$ は $\mathbb{R}$ から $(-1, 1)$ への狭義単調増加な全単射で（逆は $y \mapsto \dfrac{y}{1 - |y|}$）、 の 2 により $(\mathbb{R}, <) \cong ((-1, 1), <)$ です。一方、$[0, 1]$ には最大元があり $(0, 1)$ には無いので、$[0, 1] \not\cong (0, 1)$ です。$\mathbb{N}$ には最小元があり $\mathbb{Z}$ には無いので $\mathbb{N} \not\cong \mathbb{Z}$、また $\mathbb{Z}$ は隣り合う元があるが $\mathbb{Q}$ には無い（稠密）ので $\mathbb{Z} \not\cong \mathbb{Q}$ です。$\mathbb{Q}$ と $\mathbb{R}$ は、濃度（）が違うので順序同型ではありません。 可算な全順序について、驚くほど強い分類定理があります。証明の方針は「往復」です。$A$ の元と $B$ の元を交互に 1 つずつ取り上げ、そのたびに順序を保つ対応を 1 点ずつ増やしていけば、最後には $A$ の元も $B$ の元も取り残さずに対応がつく、というものです。 $(A, <)$、$(B, <)$ を、空でなく、可算で、稠密（$x < y$ ならある $z$ が $x < z < y$）で、最小元も最大元も持たない全順序集合とする。このとき $A \cong B$ である。とくに、このような全順序集合はすべて $(\mathbb{Q}, <)$ と順序同型である。 $A, B$ は最大元を持たない空でない全順序集合なので無限集合で、したがって可算無限です。$A = \{a_0, a_1, \ldots\}$、$B = \{b_0, b_1, \ldots\}$ と番号を付けます（）。 **有限部分同型.** 有限部分集合 $F \subseteq A$ から $B$ への狭義単調増加写像を**有限部分同型**と呼びます。次の拡張補題を示します：有限部分同型 $f : F \to B$ と $a \in A \setminus F$ に対し、$f \cup \{(a, b)\}$ も有限部分同型になる $b \in B$ がある。$F = \{x_1 < \cdots < x_k\}$ とします。$F = \varnothing$ なら任意の $b$ でよい。$a < x_1$ のときは、$B$ に最小元がないので $b < f(x_1)$ となる $b$ を取る。$x_i < a < x_{i+1}$ のときは、$f(x_i) < f(x_{i+1})$ で $B$ は稠密なので、間の $b$ を取る。$x_k < a$ のときは、$B$ に最大元がないので $b > f(x_k)$ となる $b$ を取る。いずれの場合も $f \cup \{(a, b)\}$ は狭義単調増加です。$A$ と $B$ の役割を入れ替えても（$A$ の最小元・最大元の非存在と稠密性を使って）同様で、$b \in B \setminus \operatorname{ran} f$ に対し $f \cup \{(a, b)\}$ が有限部分同型となる $a \in A$ がある。 **往復の構成.** $f_0 = \varnothing$ とし、$f_{2n+1}$ は、$a_n \in \operatorname{dom} f_{2n}$ ならば $f_{2n}$、そうでなければ $f_{2n} \cup \{(a_n, b)\}$（$b$ は拡張補題を満たす番号が最小のもの）とします。$f_{2n+2}$ は、$b_n \in \operatorname{ran} f_{2n+1}$ ならば $f_{2n+1}$、そうでなければ $f_{2n+1} \cup \{(a, b_n)\}$（$a$ は番号が最小のもの）とします。番号が最小のものを選ぶので、選択公理は使いません。すると $f = \bigcup_n f_n$ は写像で（各 $f_n$ が前の拡大）、$\operatorname{dom} f \ni a_n$（$f_{2n+1}$ の構成）、$\operatorname{ran} f \ni b_n$（$f_{2n+2}$ の構成）なので $\operatorname{dom} f = A$、$\operatorname{ran} f = B$ です。$x < y$ なら、両方が十分大きな $f_m$ の定義域に入り、$f_m$ が狭義単調増加なので $f(x) < f(y)$ です。 の 2 より $f$ は順序同型です。最後の主張は、$\mathbb{Q}$ が空でなく可算で稠密で端点を持たない（）ことから従います。 たとえば $(0, 1) \cap \mathbb{Q}$、$\mathbb{Q}$、二進有理数の全体 $\{m/2^n\}$ は、すべて順序集合として同じものです。同じ「$\mathbb{Q}$ の中の位置関係」だけを持つこれらを、順序だけを見て区別する手段はありません。実数にあって有理数にないのは、順序の完備性（）です。 ## 3. 選択公理 $I$ を集合とし、各 $i \in I$ に空でない集合 $A_i$ が対応しているとする。このとき、写像 $f : I \to \bigcup_{i \in I} A_i$ で、すべての $i \in I$ について $f(i) \in A_i$ となるものが存在する。$f$ を族 $\{A_i\}_{i \in I}$ の**選択関数**という。 直積 $\prod_{i \in I} A_i$ とは、$f(i) \in A_i$ を満たす写像 $f : I \to \bigcup_i A_i$ 全体の集合のことですから、選択公理は「空でない集合の族の直積は空でない」と言い換えられます。 選択公理から次が従う。 1. 全射 $p : X \to Y$ には右逆写像、すなわち $s : Y \to X$ で $p \circ s = \mathrm{id}_Y$ となるものが存在する。 2. 互いに素な空でない集合の族 $\{A_i\}_{i \in I}$ に対し、各 $A_i$ とちょうど 1 点で交わる集合 $T \subseteq \bigcup_i A_i$ が存在する。 1. 各 $y \in Y$ に対し $A_y := p^{-1}(\{y\})$ は、$p$ が全射なので空でない。選択関数 $s$ を取れば $s(y) \in A_y$、すなわち $p(s(y)) = y$ である。 2. 選択関数 $f$ に対し $T := \{f(i) : i \in I\}$ とおく。各 $T \cap A_i$ は $f(i)$ を含み、$f(j) \in A_j$ と $A_i \cap A_j = \emptyset$（$i \ne j$）により $f(j) \notin A_i$ だから、$T \cap A_i = \{f(i)\}$ である。 2 は[関係と同値関係](/mathematics/foundations/equivalence-relations)の商集合で言えば、「各同値類から代表元を 1 個ずつ選んだ集合（完全代表系）が存在する」という主張です。有限個の同値類のときは自明ですが、一般には選択公理が必要です。 ## 4. 超限帰納法 整列集合の最大の取り柄は、数学的帰納法が一般の順序に拡張されることです。 $(W, \le)$ を整列集合、$P(x)$ を $x \in W$ についての命題とする。すべての $a \in W$ について $$ \bigl( \forall x < a,\ P(x) \bigr) \implies P(a) $$ が成り立つならば、すべての $a \in W$ について $P(a)$ が成り立つ。 $P(a)$ が成り立たない $a \in W$ があると仮定する。$S := \{a \in W : P(a)\text{ は偽}\}$ は空でないので、最小元 $a_0$ を持つ。$x < a_0$ なる $x$ は $S$ に属さない（$a_0$ の最小性）ので、$P(x)$ が成り立つ。仮定により $P(a_0)$ が成り立ち、$a_0 \in S$ に反する。 $W = \mathbb{N}$ のとき、これは強い帰納法（[証明の技術](/mathematics/foundations/proof-techniques)の ）です。基底ステップ（$a$ が最小元のとき $\forall x < a$ は空虚に成り立つ）が帰納ステップに吸収されている点に注意してください。 $(W, \le)$ を整列集合とし、$f : W \to W$ が狭義単調増加（$x < y \Rightarrow f(x) < f(y)$）であるとする。このとき、すべての $x \in W$ について $x \le f(x)$ である。とくに、$W$ から自分の真の始切片 $W_{ 超限帰納法で示す。$a \in W$ とし、$x < a$ なるすべての $x$ について $x \le f(x)$ が成り立つとする。$f(a) < a$ だと仮定すると、$x := f(a)$ は $x < a$ を満たすので、帰納法の仮定より $f(a) \le f(f(a))$ となる。一方 $f(a) < a$ と $f$ の狭義単調性から $f(f(a)) < f(a)$ である。これは矛盾なので、$a \le f(a)$ である。 後半。$g : W \to W_{ 超限帰納法で何かを**示す**ことと並んで、超限帰納法で何かを**定義する**（超限再帰）こともできます。この記事では、証明のための帰納法だけを使います。再帰的定義と順序数による一般論は、公理的集合論の話題です。 ## 5. 3 つの同値：選択公理・Zorn の補題・整列可能定理 この記事の山場です。示すことは、選択公理 $\Rightarrow$ Zorn の補題 $\Rightarrow$ 整列可能定理 $\Rightarrow$ 選択公理 と一周できることです。最も長いのは最初の $\Rightarrow$（§5.1）で、方針は次のとおりです。極大元がないとして、鎖ごとに「それより真に大きい元」を 1 つ選ぶ規則を選択公理で固定します。その規則に従って下から 1 段ずつ元を積み上げていくと、積み上げられるものすべての全体にもさらに 1 つ上が選べてしまい、「全体」と言ったことに反して矛盾する、という流れです。 $(P, \le)$ を空でない半順序集合とする。$P$ の空でない任意の鎖が $P$ の中に上界を持つならば、$P$ は極大元を持つ。 私たちは ZFC、すなわち選択公理（）を仮定した集合論の中で考えています。したがって、選択公理から Zorn の補題を導く §5.1 の議論「(1) $\Rightarrow$ (2) の証明」が、そのままこの定理の証明です。要点は、極大元がないと仮定して、選択公理で鎖ごとに狭義上界を選ぶ写像 $g$ を固定し、$g$ に従って下から積み上げた整列集合（$g$-整合的集合）すべての合併 $U$ を作ることです。 と により $U$ 自身が整合的な整列集合になり、$U \cup \{g(U)\}$ もまた整合的なので $g(U) \in U$ となって矛盾します。 任意の集合 $X$ に対し、$X$ 上の整列順序が存在する。 Zorn の補題（）から導きます。議論は §5.2 の「(2) $\Rightarrow$ (3) の証明」そのものです。$X$ の部分集合とその上の整列順序の組全体を「始切片として延びる」という順序で半順序集合とみなすと、空でない鎖の合併は により上界になるので、Zorn の補題から極大元 $(M, \le_M)$ が存在します。$M \ne X$ なら $X \setminus M$ の 1 点を最大元として付け足して真に延ばせるので極大性に反し、$M = X$ です。 次の 3 つは互いに同値である。 1. 選択公理（）。 2. Zorn の補題（）。 3. 整列可能定理（）。 証明は循環 (1) $\Rightarrow$ (2) $\Rightarrow$ (3) $\Rightarrow$ (1) で行います。各段階で、選択公理・Zorn の補題・整列可能定理のどれを仮定しているかを明示します。
選択公理 Zorn の補題 整列可能定理 強上界の選択関数 部分整列の拡張 各集合の最小元を選ぶ (1) ⇒ (2) ⇒ (3) ⇒ (1)
### 5.1. 選択公理から Zorn の補題へ 整列集合の「増える列」の合併が再び整列集合になる、という補題を先に用意します。2 回使います。条件に出てくる始切片は、「自分に属する各元について、それより下の元をすべて含む部分集合」、つまり並びの先頭側を丸ごと切り取った部分のことです。補題は、先頭側が互いに入れ子になっている整列集合をつなぎ合わせても、先頭から順に並んだ 1 本の整列集合になる、と言っています。 $\mathcal{C}$ を整列集合 $(A, \le_A)$ の空でない族（空の整列集合を含んでもよい）で、次を満たすものとする：任意の $(A, \le_A), (B, \le_B) \in \mathcal{C}$ について、一方が他方の**始切片**になっている。すなわち（たとえば）$A \subseteq B$、$\le_B$ を $A$ に制限したものが $\le_A$ に等しく、$A$ は $(B, \le_B)$ の始切片である。このとき $A^{*} := \bigcup_{A \in \mathcal{C}} A$ 上に、各 $\le_A$ の合併として定まる順序 $\le^{*}$ は整列順序であり、すべての $(A, \le_A) \in \mathcal{C}$ は $(A^{*}, \le^{*})$ の始切片である。 **順序の定義と全順序性。** $x, y \in A^{*}$ とすると、$x \in A$、$y \in B$ なる $A, B \in \mathcal{C}$ がある。一方が他方の始切片なので、$x, y$ は大きい方の整列集合に共に属する。$x \le^{*} y$ を、$x, y$ をともに含む任意の $C \in \mathcal{C}$ での $x \le_C y$ と定める。これが $C$ の取り方によらないのは、$C \subseteq C'$ ならば $\le_{C'}$ の $C$ への制限が $\le_C$ だからである。任意の有限個の元はある 1 つの $C$ にすべて属するから、反射律・反対称律・推移律・全順序性（比較可能性）は、その $C$ の上で成り立つことから従う。 **整列性。** $M \subseteq A^{*}$ を空でない部分集合とする。$x_0 \in M$ を取り、$x_0 \in A$ なる $A \in \mathcal{C}$ を取る。$M \cap A$ は空でないので $A$ の中に最小元 $m_0$ がある。$m_0$ が $M$ 全体の最小元であることを示す。$y \in M$ をとり、$y \in B \in \mathcal{C}$ とする。$B$ が $A$ の始切片なら $y \in A$ で、$m_0$ の取り方から $m_0 \le y$。$A$ が $B$ の始切片なら、もし $y <_B m_0$ だとすると、$A$ が始切片であることから $y \in A$ となり $M \cap A$ における $m_0$ の最小性に反する。$\le_B$ は全順序なので、$m_0 \le y$。 **始切片であること。** $A \in \mathcal{C}$、$x \in A$、$y \in A^{*}$、$y \le^{*} x$ とする。$y \in B \in \mathcal{C}$ とすると、$B$ が $A$ の始切片なら $y \in B \subseteq A$。$A$ が $B$ の始切片なら $y \le_B x$ と $x \in A$ から $y \in A$。いずれにせよ $y \in A$ である。 **(1) $\Rightarrow$ (2) の証明。** 選択公理を仮定し、$(P, \le)$ が Zorn の補題の仮定を満たすのに極大元を持たないと仮定して矛盾を導きます。 まず、$P$ が空でないことと「空の鎖」の扱いを整えます。$P \ne \emptyset$ なので、空の鎖の上界として $P$ の任意の元が取れます。したがって $P$ の**すべて**の鎖（空も含む）が上界を持ちます。 鎖 $C$ の**狭義上界**を、すべての $c \in C$ について $c < u$ となる $u \in P$ と定義します。極大元がない仮定のもとで、すべての鎖 $C$ は狭義上界を持ちます。実際 $C$ の上界 $u$ を 1 つ取ると、$u$ は極大でないので $u < v$ なる $v$ がある。このとき $c \le u < v$ より $v$ は狭義上界です。そこで、$P$ の鎖全体の集合 $\mathcal{K}$ は $\mathcal{P}(P)$ の部分集合として集合であり、各 $C \in \mathcal{K}$ に対し狭義上界の集合は空でないので、選択公理により、$g(C)$ が $C$ の狭義上界であるような写像 $g : \mathcal{K} \to P$ が存在します。これを固定します。 $A \subseteq P$ が**$g$-整合的**であるとは、$A$ が $\le$ に関して整列集合であり、かつすべての $a \in A$ について $$ a = g\bigl(A_{ $A, B \subseteq P$ がともに $g$-整合的ならば、一方は他方の始切片である。 $S := \{x \in A \cap B : A_{ **証明の続き。** $U$ を、すべての $g$-整合的集合の合併とします。 により、整合的集合の族は の仮定を満たします（順序はどれも $P$ の $\le$ の制限なので一致している）。したがって $U$ は整列集合で、すべての整合的集合は $U$ の始切片です。$U$ が整合的であることを示します。$a \in U$ とし、$a \in A$（$A$ は整合的）とします。$A$ は $U$ の始切片なので $U_{ の仮定を満たします。よって合併 $(A^{*}, \le^{*})$ は整列集合で、すべての $(A, \le_A) \in \mathcal{C}$ に対し $(A, \le_A) \sqsubseteq (A^{*}, \le^{*})$ なので、$\mathcal{C}$ の上界です。Zorn の補題（）により、$\mathcal{W}$ は極大元 $(M, \le_M)$ を持ちます。 $M = X$ を示します。$M \ne X$ とし、$x \in X \setminus M$ を取ります。$M' := M \cup \{x\}$ に、$\le_M$ を拡張して $x$ を最大元とする順序を入れます。この順序は整列順序で（空でない部分集合 $T$ は、$T \cap M \ne \emptyset$ なら $T \cap M$ の最小元、$T = \{x\}$ なら $x$ が最小元）、$M$ はその始切片です。すると $(M, \le_M) \sqsubset (M', \le')$ は真の拡大となり、$(M, \le_M)$ の極大性に反します。したがって $M = X$ であり、$\le_M$ は $X$ 上の整列順序です。$\blacksquare$ ### 5.3. 整列可能定理から選択公理へ **(3) $\Rightarrow$ (1) の証明。** $\{A_i\}_{i \in I}$ を空でない集合の族とし、$X := \bigcup_{i} A_i$ に整列順序 $\le$ を取ります（整列可能定理）。各 $i$ に対し $A_i \subseteq X$ は空でないので最小元 $f(i)$ を持ちます。$f(i) \in A_i$ なので $f$ は選択関数です。ここで各 $A_i$ から選ぶ規則（最小元を取る）が明示的に決まっているので、選択を何度もくり返す必要がありません。$\blacksquare$ 3 つの含意はそれぞれ上で示しました。(1) $\Rightarrow$ (2) は §5.1 で、選択公理だけを使い、 と を経て示しました。(2) $\Rightarrow$ (3) は §5.2 で、Zorn の補題だけを使って示しました。(3) $\Rightarrow$ (1) は §5.3 で、整列順序の最小元を選ぶことで示しました。各段では、仮定した命題のほかに選択公理を使っていません（§5.2 と §5.3 の議論は ZF の中で行えます）。含意が (1) $\Rightarrow$ (2) $\Rightarrow$ (3) $\Rightarrow$ (1) と一巡するので、3 つは互いに同値です。 選択公理には他にも多くの同値形があります。有限性の性質を持つ集合族が極大元を持つという Tukey の補題、任意の 2 つの濃度が比較可能であるという主張（）、任意のベクトル空間が基底を持つという主張（Blass 1984）、一般の（ハウスドルフとは限らない）コンパクト空間の族の直積がコンパクトであるという Tychonoff の定理（Kelley 1950）などです。後の 2 つは、一見すると選択公理から遠い分野の定理が、実は選択公理と同値であることを意味します。Zorn の補題が数学の各分野の存在定理に現れる理由はここにあります。 ## 6. Zorn の補題の使い方 Zorn の補題の使い方は型が決まっています。 1. 「欲しい対象の部分的なもの」全体 $\mathcal{P}$ を、包含や延長で半順序集合にする。 2. $\mathcal{P}$ が空でないことと、空でない鎖が上界（通常は合併）を持つことを確かめる。 3. Zorn の補題により極大元 $m$ を取る。 4. $m$ が実は欲しい対象全体であることを、「もし足りなければもう少し延長できて、$m$ の極大性に反する」という形で示す。
合併 ＝ 上界（どの T も含む） … T₃ T₂ T₁
### 6.1. 濃度の比較可能性と Cantor–Bernstein の定理 任意の集合 $A, B$ について、単射 $A \to B$ または単射 $B \to A$ が存在する。 $\mathcal{P}$ を、$A' \subseteq A$ から $B$ への単射 $\varphi : A' \to B$ 全体とする（部分写像）。$\varphi$ をそのグラフ $\{(a, \varphi(a))\} \subseteq A \times B$ と同一視し、包含 $\subseteq$ で順序づける。$\mathcal{P}$ は空写像を含むので空でない。$\mathcal{C}$ を $\mathcal{P}$ の鎖とし、$\psi := \bigcup_{\varphi \in \mathcal{C}} \varphi$ とおく。$\psi$ が写像であること：$(a, b), (a, b') \in \psi$ なら、$(a, b) \in \varphi$、$(a, b') \in \varphi'$ で、鎖なので一方が他方に含まれ、同じ $\varphi$ の中で $b = b'$。単射であることも同様に、$\psi(a) = \psi(a')$ の 2 点は 1 つの $\varphi$ の中にあるので $a = a'$。したがって $\psi \in \mathcal{P}$ は $\mathcal{C}$ の上界である。 Zorn の補題により、極大元 $\varphi_0 : A_0 \to B$ が存在する。$A_0 \ne A$ かつ $\varphi_0(A_0) \ne B$ なら、$a \in A \setminus A_0$ と $b \in B \setminus \varphi_0(A_0)$ を取って $\varphi_0$ に $(a, b)$ を付け加えた写像が単射となり、極大性に反する。よって $A_0 = A$（このとき $\varphi_0$ は $A \to B$ の単射）か、$\varphi_0(A_0) = B$（このとき $\varphi_0 : A_0 \to B$ は全単射で、逆写像 $B \to A_0 \subseteq A$ が単射）のいずれかが成り立つ。 これと次の定理を合わせると、任意の 2 つの濃度の大小が必ず決まります。 単射 $f : A \to B$ と単射 $g : B \to A$ が存在するならば、全単射 $h : A \to B$ が存在する。 この定理は[濃度と無限](/mathematics/foundations/cardinality-and-infinity)の と同じ主張です。そちらの証明（Appendix）とは別の形で、証明の全体が選択公理を使っていないことが見えるように書いておきます。 $A_0 := A \setminus g(B)$、$A_{n+1} := g(f(A_n))$ と帰納的に定め、$C := \bigcup_{n \ge 0} A_n$ とおく。写像 $h : A \to B$ を $$ h(x) := \begin{cases} f(x) & (x \in C),\\ g^{-1}(x) & (x \notin C) \end{cases} $$ で定める。$x \notin C$ なら $x \notin A_0$ なので $x \in g(B)$ であり、$g$ が単射なので $g^{-1}(x)$ はただ 1 つ定まる。 **単射。** 両方 $C$ の元なら $f$ の単射性から、両方 $C$ の外なら $g^{-1}$ の単射性から従う。$x \in C$、$y \notin C$、$f(x) = g^{-1}(y)$ とすると $y = g(f(x))$ である。$x \in A_n$ なら $y \in A_{n+1} \subseteq C$ となり矛盾。 **全射。** $b \in B$ とする。$g(b) \notin C$ なら $h(g(b)) = g^{-1}(g(b)) = b$。$g(b) \in C$ なら、$g(b) \in g(B)$ より $g(b) \notin A_0$ なので $g(b) \in A_{n+1}$ なる $n \ge 0$ がある。$g(b) = g(f(a))$ なる $a \in A_n$ が存在し、$g$ の単射性から $b = f(a)$。$a \in C$ より $h(a) = f(a) = b$。 選択公理が不要なのは、$h$ が $f$, $g$ から明示的に定義されているからです。一方、 の $h$ は選択公理（Zorn）を要し、実際、選択公理がなければ濃度が比較不能な 2 集合の存在を否定できません。 ### 6.2. Hamel 基底の存在 $V$ を体 $K$ 上のベクトル空間とし、$S \subseteq V$ を線形独立な部分集合とする（）。このとき $S \subseteq B$ を満たす $V$ の基底 $B$ が存在する。とくに（$S = \emptyset$ として）すべてのベクトル空間は基底を持つ。 $\mathcal{P}$ を、$S \subseteq T$ を満たす線形独立な部分集合 $T \subseteq V$ 全体とし、包含で順序づける。$S \in \mathcal{P}$ なので空でない。 $\mathcal{C}$ を $\mathcal{P}$ の空でない鎖、$T^{*} := \bigcup_{T \in \mathcal{C}} T$ とする。$T^{*}$ の相異なる有限個の元 $v_1, \ldots, v_m$ を取ると、各 $v_i$ は $T_i \in \mathcal{C}$ に属し、$\mathcal{C}$ は鎖なので、$T_1, \ldots, T_m$ のうち最大のものに $v_1, \ldots, v_m$ はすべて属する。その集合は線形独立だから、$v_1, \ldots, v_m$ は線形独立である。よって $T^{*}$ は線形独立で $S \subseteq T^{*}$、すなわち $T^{*} \in \mathcal{P}$ は $\mathcal{C}$ の上界である。 Zorn の補題により極大元 $B$ が存在する。$B$ が $V$ を生成することを示す。$v \in V \setminus \operatorname{span}(B)$ があるとして、$B \cup \{v\}$ が線形独立であることを示す。$cv + a_1 b_1 + \cdots + a_m b_m = \boldsymbol{0}$（$b_i \in B$ は相異なる）とする。$c \ne 0$ なら $v = -c^{-1}(a_1 b_1 + \cdots + a_m b_m) \in \operatorname{span}(B)$ となり矛盾。$c = 0$ なら、$B$ の線形独立性から $a_i = 0$。よって $B \cup \{v\}$ は $\mathcal{P}$ の元で $B$ を真に含み、極大性に反する。ゆえに $\operatorname{span}(B) = V$ で、$B$ は線形独立な生成系、つまり基底である。 有限次元なら、取り替え補題（）から基底が構成できました。無限次元では、この存在定理が選択公理に頼る以外の方法を持ちません。 実数全体 $\mathbb{R}$ は、足し算と有理数倍で $\mathbb{Q}$ 上のベクトル空間です。$1$ と $\sqrt{2}$ は $\mathbb{Q}$ 上線形独立です。$a + b\sqrt{2} = 0$（$a, b \in \mathbb{Q}$）で $b \ne 0$ なら $\sqrt{2} = -a/b \in \mathbb{Q}$ となり、これは に反する。よって $b = 0$、続いて $a = 0$ である。 により、$1, \sqrt{2}$ を含む $\mathbb{R}$ の $\mathbb{Q}$ 上の基底 $B$ が取れます。各 $x \in \mathbb{R}$ は $x = \sum_{b \in B} q_b(x)\, b$（有限個を除き $q_b(x) = 0$、係数は $\mathbb{Q}$ の元で一意）と書けるので、$f(x) := q_{\sqrt{2}}(x)$（$\sqrt{2}$ の係数）と定めると、$f : \mathbb{R} \to \mathbb{Q} \subseteq \mathbb{R}$ は加法的です：$f(x + y) = f(x) + f(y)$。また $f(1) = 0$、$f(\sqrt{2}) = 1$ です。 もし $f$ が連続なら、$f(x) = f(1) x = 0$ となるはずです。実際、加法性から $f(0) = 0$、$f(-x) = -f(x)$、帰納法で $f(nx) = nf(x)$（$n \in \mathbb{N}$）、したがって $f(p/q) = (p/q) f(1)$（有理数）が従い、有理数の稠密性と連続性から任意の実数 $x$ で $f(x) = x f(1)$ となります。これは $f(\sqrt{2}) = 1$ と矛盾します。したがって $f$ は加法的ですが連続でない関数であり、しかもそのグラフは $\mathbb{R}^2$ で稠密になることが知られています。このような関数を具体的に書き下すことはできません。実際、選択公理を弱めた集合論には、加法的な実関数がすべて連続になるもの（Solovay のモデル）が知られています。 ### 6.3. 極大イデアルの存在 $R$ を $1 \ne 0$ の可換環とし、$I$ を $R$ の真のイデアル（$I \ne R$）とする。このとき $I$ を含む $R$ の極大イデアル（）が存在する。 $\mathcal{P}$ を、$I$ を含む真のイデアル全体とし、包含で順序づける。$I \in \mathcal{P}$ なので空でない。$\mathcal{C}$ を空でない鎖、$J^{*} := \bigcup_{J \in \mathcal{C}} J$ とする。$a, b \in J^{*}$ なら $a \in J_1$、$b \in J_2$ で、鎖なので大きい方の $J$ に両方入り、$a + b \in J \subseteq J^{*}$。$r \in R$ に対し $ra \in J_1 \subseteq J^{*}$。$0 \in J^{*}$ も明らか。よって $J^{*}$ はイデアルである（ の条件）。さらに、$1 \in J^{*}$ なら $1 \in J$ なる $J \in \mathcal{C}$ があり、 により $J = R$ となって $J$ が真であることに反する。よって $J^{*} \in \mathcal{P}$ は $\mathcal{C}$ の上界である。 Zorn の補題により $\mathcal{P}$ の極大元 $M$ が存在する。$M$ が極大イデアルであることを確かめる。$M \subseteq J \subseteq R$ なるイデアル $J$ が $J \ne R$ なら $J \in \mathcal{P}$ で、$M$ の極大性から $J = M$。よって $J = M$ または $J = R$ である。 とくに、$I = \{0\}$ とすれば、任意の（$1 \ne 0$ の）可換環に極大イデアルが存在します。これが[イデアルと剰余環](/mathematics/algebra/ideals-and-quotient-rings)で取り上げられる、極大イデアルによる体の構成（剰余環が体になること）の存在保証です。 ## 7. 演習 選択公理を仮定して、全射 $p : X \to Y$ が右逆写像 $s : Y \to X$（$p \circ s = \mathrm{id}_Y$）を持つことを示し、$s$ が単射であることも示せ。 $y \in Y$ に対し $A_y := p^{-1}(\{y\})$ は $p$ の全射性より空でない。選択関数 $s$ により $s(y) \in A_y$ とすれば $p(s(y)) = y$。$s(y) = s(y')$ なら $y = p(s(y)) = p(s(y')) = y'$ なので $s$ は単射である。 整列集合 $(W, \le)$ には、狭義単調減少な無限列 $x_1 > x_2 > x_3 > \cdots$ が存在しないことを示せ。 そのような列があるとすると、$\{x_n : n \in \mathbb{N}\}$ は空でない部分集合なので最小元 $x_k$ を持つ。ところが $x_{k+1} < x_k$ なので、最小性に反する。（逆に、無限降下列を持たない全順序集合は整列集合だが、これを示すには選択公理の弱い形（従属選択公理）が要る。） $(P, \le)$ を半順序集合とする。Zorn の補題を使って、$\le$ を含む（$x \le y \Rightarrow x \preceq y$ を満たす）$P$ 上の全順序 $\preceq$ が存在することを示せ（Szpilrajn の拡大定理）。 $\mathcal{P}$ を、$\le$ を含む $P$ 上の半順序全体とし、包含（関係の集合として）で順序づける。$\le \in \mathcal{P}$ なので空でない。空でない鎖 $\mathcal{C}$ の合併 $\rho^{*}$ は半順序である。反射律は明らか。推移律：$(x, y) \in \rho$、$(y, z) \in \rho'$（$\rho, \rho' \in \mathcal{C}$）なら、$\rho, \rho'$ の大きい方に両方の対が入るので、そこで $(x, z)$ が入る。反対称律も $(x, y)$ と $(y, x)$ が大きい方の半順序に入ることから従う。よって鎖は上界を持ち、Zorn の補題により極大元 $\preceq$ が取れる。 $\preceq$ が全順序であることを示す。比較不能な $x, y$ があるとし、 $$ \preceq' \,:=\, \preceq \,\cup\, \{(a, b) \in P \times P : a \preceq x,\ y \preceq b\} $$ とおく（右の集合の元を「新しい対」と呼ぶ）。$\preceq'$ が半順序であることを示せば、$\preceq' \supseteq \preceq \supseteq \le$ であり、$(x, y)$ は新しい対（$x \preceq x$、$y \preceq y$）だが $\preceq$ には入らない（$x, y$ は比較不能）ので、$\preceq'$ は $\preceq$ の真の拡大となり、極大性に反する。 反射律は $\preceq$ から従う。**反対称律**：$(a, b)$ と $(b, a)$ がともに $\preceq'$ に入るとする。ともに $\preceq$ の元なら $a = b$。そうでないとき、新しい対を含む場合ごとに $y \preceq x$ が導かれて矛盾する。$(a, b)$ が新しく $(b, a) \in \preceq$ なら $y \preceq b \preceq a \preceq x$。$(a, b) \in \preceq$ で $(b, a)$ が新しいなら $y \preceq a \preceq b \preceq x$。ともに新しいなら $y \preceq a \preceq x$。いずれも $y \preceq x$ を与え、$x, y$ が比較不能であることに反する。**推移律**：$(a, b), (b, c) \in \preceq'$ とする。ともに $\preceq$ の元なら $\preceq$ の推移律。$(a, b)$ が新しく $(b, c) \in \preceq$ なら、$a \preceq x$、$y \preceq b \preceq c$ なので $(a, c)$ は新しい対。$(a, b) \in \preceq$ で $(b, c)$ が新しいなら、$a \preceq b \preceq x$、$y \preceq c$ なので $(a, c)$ は新しい対。ともに新しいなら $a \preceq x$、$y \preceq c$ なので $(a, c)$ は新しい対。以上で $\preceq'$ は半順序である。 $V$ を体 $K$ 上のベクトル空間、$W$ を部分空間とする。$V = W \oplus W'$（$W + W' = V$ かつ $W \cap W' = \{\boldsymbol{0}\}$）となる部分空間 $W'$ が存在することを示せ。 を $W$ に適用して $W$ の基底 $S$ を取り、$S$ は $V$ の線形独立な部分集合でもあるから、$S \subseteq B$ なる $V$ の基底 $B$ が存在する。$W' := \operatorname{span}(B \setminus S)$ とおく。$V = \operatorname{span}(B) = \operatorname{span}(S) + \operatorname{span}(B \setminus S) = W + W'$。$v \in W \cap W'$ とすると、$v$ は $S$ の線形結合であり、同時に $B \setminus S$ の線形結合でもある。この 2 つの表示を引き算すると、$B$ の相異なる元の線形結合が $\boldsymbol{0}$ となるので、$B$ の線形独立性から係数はすべて $0$、$v = \boldsymbol{0}$ である。 ## 参考文献 - P. R. Halmos, *Naive Set Theory*, Springer, 1974 — 整列可能定理・Zorn の補題・選択公理の各章。 - K. Kunen, *Set Theory*, College Publications, 2011 — 選択公理と Zorn の補題、基数の比較可能性。 - 松坂和夫『集合・位相入門』岩波書店、1968 — 順序集合と選択公理、Zorn の補題の節。 - T. J. Jech, *The Axiom of Choice*, North-Holland, 1973 — 選択公理の独立性と同値形。 - S. Lang, *Algebra*, Springer, 2002 — Appendix 2（Zorn の補題）。