選択公理・Zornの補題・整列可能定理の同値性

集合論には、一見まったく異なる主張に見えながら実は互いに同値であることが知られている 3 つの命題があります。選択公理、Zorn の補題、整列可能定理です。これらはいずれも ZF（Zermelo-Fraenkel）集合論からは証明できず、独立した公理として扱われますが、どれか 1 つを認めれば残りの 2 つも導かれるという関係にあります。

3 つの命題の内容

まず、それぞれの主張を正確に述べておきます。

選択公理（Axiom of Choice, AC） は次のように定式化されます。空でない集合の族 $\{A_i{\}}_{i\in I}$（各 $A_i\ne \varnothing$）が与えられたとき、各 $A_i$ から 1 つずつ元を選ぶ写像

$$f:I\to \bigcup _{i\in I}{A}_i,f(i)\in A_i$$

が存在します。この写像 $f$ を選択関数と呼びます。有限個の集合から元を選ぶのは自明ですが、無限個の集合に対しても「一斉に選べる」ことを保証するのがこの公理の本質です。

Zorn の補題 は半順序集合に関する主張です。半順序集合 $(P,\le )$ において、すべての全順序部分集合（鎖）が $P$ の中に上界を持つならば、$P$ は極大元を持ちます。

整列可能定理（Well-Ordering Theorem） は、任意の集合 $X$ に対して、$X$ 上の整列順序が存在するという主張です。整列順序とは、全順序であって、かつ空でない任意の部分集合が最小元を持つような順序のことです。自然数 $\mathbb{N}$ は通常の大小関係で整列集合ですが、実数 $\mathbb{R}$ が整列できるというのは直観に反するかもしれません。しかし整列可能定理はまさにそれを主張しています。

同値性の証明の全体像

3 つの命題の同値性は、通常、循環的に証明します。

この循環を示せば、3 つの命題がすべて同値であることが確定します。以下では各ステップの証明の要点を述べていきます。

選択公理 → 整列可能定理

この方向の証明は Zermelo（1904）による歴史的に最も有名な結果です。与えられた集合 $X$ に対して、選択公理を用いて $X$ 上の整列順序を構成します。

選択公理により、$X$ の空でない部分集合の族 $\mathcal{P}(X)\setminus \{\varnothing \}$ 上の選択関数

$$f:\mathcal{P}(X)\setminus \{\varnothing \}\to X,f(A)\in A$$

が存在します。この $f$ を使って超限帰納法により $X$ の元を順に並べていきます。$x_0=f(X)$ とし、$x_1=f(X\setminus \{x_0\})$ とし、…と続けます。超限帰納法を正確に定式化すると、順序数 $\alpha$ に対して

$$x_{\alpha }=f\left(X\setminus \{x_{\beta }:\beta <\alpha \}\right)$$

と定義し、$X\setminus \{x_{\beta }:\beta <\alpha \}=\varnothing$ となった時点で停止します。この手続きが実際に $X$ 全体を整列順序で覆うことを示せば証明は完了です。

整列可能定理 → Zorn の補題

半順序集合 $(P,\le )$ がZornの補題の仮定を満たすとします。すなわち、$P$ のすべての鎖が上界を持つとします。整列可能定理により $P$ 上に整列順序 $⪯$ を入れることができます。

この整列順序を用いて、$P$ の中に鎖を超限帰納的に構成していきます。$⪯$-最小の元 $p_0$ から始め、各段階で「現在の鎖の上界であって、鎖に含まれない元」を $⪯$-順序で最小のものを取り、鎖に追加します。正確には、鎖 $C_{\alpha }=\{c_{\beta }:\beta <\alpha \}$ の上界全体の集合から $C_{\alpha }$ を除いた集合の $⪯$-最小元を $c_{\alpha }$ として追加していきます。

この手続きがこれ以上続けられなくなった時点で、鎖 $C$ の上界 $m$ が得られます。仮定より上界は存在し、この $m$ より真に大きい元があればさらに鎖を延長できるはずですから、$m$ は極大元でなければなりません。

Zorn の補題 → 選択公理

空でない集合の族 $\{A_i{\}}_{i\in I}$ に対して選択関数の存在を示します。部分選択関数の全体、すなわち

$$\mathcal{F}=\left\{f:J\to {\bigcup }_{i\in I}{A}_i|J\subseteq I,f(j)\in A_j(\forall j\in J)\right\}$$

を考えます。ここで $\mathcal{F}$ に包含関係（定義域の拡大）で半順序を入れます。つまり $f\le g$ を「$g$ が $f$ の拡張である」と定義します。

Zorn の補題により $\mathcal{F}$ は極大元 $f^{\ast }$ を持ちます。もし $f^{\ast }$ の定義域が $I$ 全体でないとすると、$i_0\in I$ で $f^{\ast }$ が定義されていないものが存在し、$A_{i_0}$ から 1 つ元を選んで $f^{\ast }$ を拡張できてしまいます。これは $f^{\ast }$ の極大性に矛盾するので、$f^{\ast }$ は $I$ 全体で定義された選択関数です。

なぜこの同値性が重要なのか

この 3 つの命題は、数学の異なる分野で異なる形で使われます。

例えば「任意のベクトル空間は基底を持つ」という定理は Zorn の補題を用いて証明されます。「任意の集合に対して濃度の比較が可能である」（$|A|\le |B|$ か $|B|\le |A|$ のどちらかが成り立つ）という事実は整列可能定理から従います。選択公理そのものは、無限直積 ${\prod }_{i\in I}{A}_i\ne \varnothing$ という形で測度論の構成などに現れます。

同値性が保証されているおかげで、場面に応じて最も使いやすい形を選んで適用できるのです。

選択公理をめぐる議論

選択公理は ZF 集合論から独立であることが証明されています。Gödel（1938）は ZF と選択公理が無矛盾であることを示し、Cohen（1963）は ZF と選択公理の否定が無矛盾であることを示しました。つまり、選択公理を認めても認めなくても矛盾は生じません。

選択公理を認めると、Banach-Tarski のパラドックスのような直観に反する結果が導かれます。球を有限個のピースに分割し、回転と平行移動だけでもとの球の 2 倍の体積の球を作れるという定理です。このような結果に対する違和感から、構成的数学の立場では選択公理を認めない流儀もあります。

しかし現代の数学では、選択公理（したがって Zorn の補題と整列可能定理）は広く受け入れられており、ZFC（ZF + 選択公理）が標準的な公理系として用いられています。位相空間論においても Tychonoff の定理の証明に選択公理が本質的に使われるなど、この公理なしでは成立しない重要な定理が多数存在します。