証明路開発支援システム(23) - 非専門的シンギュラリティー研究所

整列可能定理(3)

ChatGPT で調べてみました。

整列可能定理について教えてください

と入力すると以下のようになりました。

「整列可能定理（well-ordering theorem）」は、集合論における非常に重要な定理です。簡単にいうと、
任意の集合は、適切な順序を入れることによって「整列集合」にできる
という主張です。

1. 整列とは何か

まず、順序集合 $(A,<)$ が整列集合であるとは、
$\forall B\subseteq A,\quad B\neq\varnothing \Rightarrow \exists b\in B\quad \forall x\in B,\ b\leq x$
が成り立つことです。
つまり、
任意の空でない部分集合が最小元を持つ
という性質です。
例えば自然数
$\mathbb N=\{0,1,2,\ldots\}$
は通常の大小関係で整列されています。
実際、自然数の空でない部分集合には必ず最小の元があります。
一方、整数
$\mathbb Z$
は通常の大小関係では整列されていません。
例えば
$\mathbb Z$
自身には最小元がありません。
しかし、整数にも**別の順序**を入れれば整列集合にできます。例えば
$0,-1,1,-2,2,-3,3,\ldots$
という順番で
$0\prec -1\prec 1\prec -2\prec2\prec-3\prec3\prec\cdots$
とすれば、これは整列になります。
したがって整列可能定理は、
$\boxed{\text{「今ある順序で整列する」ではなく「何らかの順序を入れて整列する」}}$
という定理です。

2. 整列可能定理

正確には、
$\boxed{\text{任意の集合 }A\text{ に対して、}A\text{ を整列集合にする順序関係が存在する。}}$
という定理です。
例えば実数集合
$\mathbb R$
についても、通常の大小関係
$<$
では整列されません。
例えば
$(0,1)$
には最小元がありません。
しかし整列可能定理によれば、
$\mathbb R$
には通常の大小関係とは全く別の順序を入れて整列集合にすることができます。
ただし、実際にその順序を具体的に書き下すことは一般にはできません。

3. なぜ重要なのか

整列可能定理は、選択公理（Axiom of Choice）と同値です。
つまり、通常のZF集合論において、
$\boxed{ \text{選択公理} \iff \text{整列可能定理} }$
が成り立ちます。
さらに、
$\boxed{ \text{整列可能定理} \iff \text{ツォルンの補題} \iff \text{選択公理} }$
です。
これは集合論で非常に重要な3つの原理です。

4. 選択公理との関係

選択公理は大まかにいうと、

空でない集合をいくつか集めてきたとき、それぞれの集合から1個ずつ元を選ぶことができる。

という主張です。
例えば
$\{A_i\}_{i\in I}$
が空でない集合族なら、
$\forall i\in I,\quad A_i\neq\varnothing$
から、
$f(i)\in A_i$
となる関数
$f:I\to\bigcup_{i\in I}A_i$
が存在する、というものです。
この「無限個の集合から同時に1個ずつ選ぶ」という操作が、整列可能定理と深く結びついています。

5. 整列可能定理から選択公理を証明する

ここは整列可能定理の意味がよく分かるところです。
集合族
$\{A_i\}_{i\in I}$
があり、それぞれ
$A_i\neq\varnothing$
とします。
整列可能定理によって、各 $A_i$ を整列する順序を選べます。
すると各 $A_i$ には最小元
$a_i=\min A_i$
が存在します。
そこで
$f(i)=a_i$
と定義すれば、
$f(i)\in A_i$
ですから、 $f$ は選択関数になります。
したがって
$\boxed{\text{整列可能定理}\Rightarrow\text{選択公理}}$
となります。
ただし、この証明では「各 $A_i$ に整列順序を選ぶ」という部分に注意が必要です。厳密なZFでの同値性証明では、この部分を適切に処理します。

6. 逆方向はもっと面白い

逆に、
$\text{選択公理}\Rightarrow\text{整列可能定理}$
を示すこともできます。
その代表的な証明がツォルンの補題を使うものです。
考え方としては、
1. $A$ の部分集合をできるだけ大きく整列する
2. もしまだ $A$ の元が残っていれば、それを追加する
3. そのような「最大の整列」を考える
4. 最大なのに元が残っていると矛盾する
5. よって $A$ 全体が整列されている
というものです。
この「できるだけ大きなものを作る」という議論を厳密に保証するのがツォルンの補題です。

7. 整列可能定理と数学

整列可能定理を認めると、任意の集合 $A$ に対して、その濃度をある基数で表すことができます。
例えば、
$|\mathbb N|=\aleph_0$
です。
そして整列可能定理によって、任意の集合 $A$ に対して
$|A|=\aleph$
となる基数 $\aleph$ が存在します。
つまり、
すべての集合の濃度を「基数」で比較できる
という非常に強力な結果が得られます。
例えば任意の2集合 $A,B$ に対して、
$|A|\leq |B|$
または
$|B|\leq |A|$
のどちらかが成立します。
これは基数の比較可能性と呼ばれる性質です。

8. 直感的には

整列可能定理を一言で表すなら、
「どんなに巨大で複雑な集合でも、元を『1番目、2番目、3番目、……』という形で並べることができる」
ということです。
ただし、ここで「……」には自然数だけでなく、超限順序数が現れます。
例えば
$0,1,2,\ldots,\omega,\omega+1,\omega+2,\ldots$
のような順序です。
したがって、非可算集合を整列する場合には、
$1番目,2番目,3番目,\ldots$
だけでは足りません。
例えば実数全体 $\mathbb R$ を整列すると、その順序型はある巨大な順序数になります。

9. 「実数を整列できる」という驚き

特に重要なのが、
$\boxed{\mathbb R\text{ は整列可能}}$
という結果です。
通常の順序では、
$0<\frac12<\frac13<\cdots$
のような集合は最小元を持たないので整列されません。
しかし、別の順序を使えば整列できます。
これは選択公理を受け入れた集合論では正しいのですが、

「その整列順序を具体的に構成できる」

という意味ではありません。
ここが非常に重要です。
もし興味があれば次に、「整列可能定理 ⇔ 選択公理」を、ツォルンの補題を使わずにできるだけ初等的に証明する方法、あるいは「なぜ実数を実際に整列する具体的なアルゴリズムを作れないのか」を説明できます。

選択公理から整列可能定理を初等的な方法で証明してください

と入力すると以下のようになりました。

はい。ツォルンの補題を使わずに、選択公理から整列可能定理を導く標準的で比較的初等的な証明があります。
ポイントは、Hartogs（ハルトークス）の定理を使うことです。これは「選択公理を使わなくても、どんな集合 $A$ よりも大きい順序数が存在する」という定理です。

1. 示したいこと

選択公理（AC）：

任意の空でない集合族 $\mathcal F$ に対して、各 $X\in\mathcal F$ から1個ずつ元を選ぶ関数が存在する。

から、

任意の集合 $A$ は整列可能である。

を示します。
つまり、ある順序 $<$ が存在して
$(A,<)$
が整列集合になることを証明します。

2. まず選択関数を1つ用意する

$A\neq\varnothing$ とします。
選択公理を、 $A$ の空でない部分集合全体に適用します。
$\mathcal F=\mathcal P(A)\setminus{\varnothing}$
とおきます。
選択公理によって関数
$c:\mathcal F\to A$
が存在し、
$X\neq\varnothing \quad\Longrightarrow\quad c(X)\in X$
となります。
つまり、
$\boxed{\text{A の任意の空でない部分集合から、機械的に1個を選ぶ関数 }c}$
を持っていることになります。
これを使って、 $A$ の元を1個ずつ選んでいきます。

3. ただし「何個選べるか」が問題

自然数を使って
$a_0=c(A)$
$a_1=c(A\setminus\{a_0\})$
$a_2=c(A\setminus\{a_0,a_1\})$
$\cdots$
と選ぶことはできます。
しかし、これだけでは $A$ 全体を取り尽くせるとは限りません。
例えば $A=\mathbb R$ なら、可算回選んだだけでは全部の実数を選べません。
そこで、
$0,1,2,\ldots$
だけではなく、すべての順序数を使って選び続けることを考えます。

4. Hartogs の定理

ここで次の定理を使います。

Hartogs の定理

任意の集合 $A$ に対して、ある順序数 $h(A)$ が存在して、
$\boxed{\text{$h(A)$ から $A$ への単射は存在しない}}$
が成り立つ。
つまり、
$h(A)\not\hookrightarrow A.$
一方、
$\alpha < h(A)$
なら、
$\alpha\hookrightarrow A$
となります。
この $h(A)$ を Hartogs 数と呼びます。
重要なのは、
$\boxed{\text{Hartogs の定理には選択公理が必要ない}}$
ということです。

5. Hartogs 数まで選び続けてみる

$h(A$ ) を $\kappa$ と書きます。
$\kappa=h(A).$
そこで、超限再帰によって
$a_\alpha\in A$
を
$\alpha<\kappa$
について定義してみます。
すでに
$a_\beta\qquad(\beta<\alpha)$
が選ばれているとします。
そのとき、
$R_\alpha={a_\beta\mid\beta<\alpha}$
を、それまでに選んだ元の集合とします。
もし
$A\setminus R_\alpha\neq\varnothing$
なら、選択関数 $c$ を使って
$\boxed{ a_\alpha=c(A\setminus R_\alpha) }$
と定義します。
つまり、
$a_0,a_1,a_2,\ldots,a_\omega,a_{\omega+1},\ldots$
という具合に、順序数を添字として $A$ の元を選び続けるわけです。

6. 途中で $A$ 全体を取り尽くしたら成功

ある
$\alpha<\kappa$
で
$A\setminus R_\alpha=\varnothing$
となったとします。
すると
$R_\alpha=A.$
つまり
$A=\{a_\beta\mid\beta<\alpha\}.$
しかも、各 $a_\beta$ は以前選んだ元とは異なります。
したがって
$\beta\longmapsto a_\beta$
は
$\alpha\to A$
の全単射になります。
そこで $A$ に
$a_\beta < a_\gamma \quad\Longleftrightarrow\quad \beta<\gamma$
と定義します。
すると $A$ は $\alpha$ と同じ順序型になります。
そして順序数 $\alpha$ は整列集合なので、
$\boxed{A\text{ は整列される}}$
ことが分かります。

7. では、永遠に取り尽くせなかったら？

ここが証明の核心です。
仮に、どの
$\alpha<\kappa$
についても
$A\setminus R_\alpha\neq\varnothing$
だったとします。
すると、上の超限再帰によって
$a_\alpha$
をすべての
$\alpha<\kappa$
について選べます。
しかも、 $a_\alpha$ はそれ以前に選んだ元とは異なります。
したがって、
$f:\kappa\to A$
を
$f(\alpha)=a_\alpha$
と定義すると、これは単射になります。
つまり、
$\kappa\hookrightarrow A$
が存在します。
しかし $\kappa=h(A)$ の定義から、
$h(A)\not\hookrightarrow A$
でした。
これは矛盾です。
したがって、
$\boxed{ \text{どこかの段階で必ず }A\text{ 全体を取り尽くす} }$
ことが分かります。

8. したがって整列が得られる

ある $\alpha<\kappa$ について
$A=\{a_\beta\mid\beta < \alpha\}$
となります。
各 $a_\beta$ は相異なるので、
$f:\alpha\to A,\qquad f(\beta)=a_\beta$
は全単射です。
そこで
$x < _{A}y$
を
$f^{-1}(x) < f^{-1}(y)$
によって定義します。
すると $A$ は $\alpha$ と順序同型です。
したがって、
$\boxed{(A, < _{A})\text{ は整列集合}}$
です。
以上で、
$\boxed{\mathrm{AC}\Longrightarrow\text{整列可能定理}}$
が証明されました。

9. この証明の構造

証明全体を非常に簡潔にまとめると、
$\boxed{ \begin{array}{c} \text{選択公理}\\ \Downarrow\\ \text{選択関数 }c\text{ を得る}\\ \Downarrow\\ \text{「まだ選んでいない元」を超限的に選ぶ}\\ \Downarrow\\ \text{どこまでも選べるなら }h(A)\hookrightarrow A\\ \Downarrow\\ \text{Hartogs 数の定義に矛盾}\\ \Downarrow\\ \text{途中で }A\text{ 全体を取り尽くす}\\ \Downarrow\\ A\text{ を整列できる} \end{array} }$
というものです。

10. なぜこの証明が面白いのか

この証明では、実は「最大の整列部分集合」を作るという議論をしていません。
ツォルンの補題を使う証明では、

「これ以上拡張できない整列部分集合」を取る

という発想になります。
それに対して今回の証明は、
「選択関数を使って、選べる限り超限的に選び続ける」
という非常に具体的な構成になっています。
そして、
$\text{「いつまでも選べる」}$
と仮定すると、
$h(A)\hookrightarrow A$
というHartogs 数の定義そのものに反する単射が作れてしまう、というのがポイントです。

さらに一歩進めると

この証明を理解すると、次の非常に興味深い事実も見えてきます。
$\boxed{ \text{整列可能定理} \iff \text{選択公理} \iff \text{ツォルンの補題} }$
のうち、

AC → 整列可能定理：今説明した「Hartogs 数＋超限再帰」

整列可能定理 → AC：各集合を整列して最小元を選ぶ

AC → ツォルンの補題

ツォルンの補題 → 整列可能定理

という4本の関係を順に証明すると、3つがなぜ同値なのかがかなり明確になります。