整列可能定理(4) - 非専門的シンギュラリティー研究所

前回の証明では順序数の集合 $X$ の上限が存在することを確認する前に関数を定義していますが、その根拠が不明です。『公理的集合論への一歩　無限についてのおはなし (数学セミナーライブラリー)』では集合論の公理の説明の前にこの定理が出てきているので説明されていないようです。『集合論入門 (ちくま学芸文庫)』の証明を見てみると、これを書き直せば関数を定義したのと同じことになるのではないかと思われます。

順序数全体から集合 $A$ への「類関数」の代わりにそれによってできる整列集合を考えます。
$A$ の部分集合である整列集合の全体は集合です。
整列集合に順序数を対応させる「類関数」による $A$ の部分集合である整列集合の全体の像 $X$ は集合です。
$X$ の上限が存在します。
それ以後はその上限以下の順序数の集合に関する議論となります。

ChatGPT で調べてみました。

順序数全体から一つの集合への写像の像が定義できる条件は何ですか？

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

はい。ここでは「順序数全体」を
$\mathrm{Ord}=\{\alpha\mid \alpha\text{ は順序数}\}$
とし、これは集合ではなく真の類であることが重要です。

1. 通常の関数なら「像が集合」になる

集合 $A$ から集合 $B$ への関数
$f:A\to B$
なら、
$f[A]=\{f(a)\mid a\in A\}$
は必ず集合です。これは 置換公理（Replacement） によります。
ところが
$F:\mathrm{Ord}\to B$
では、定義域 $\mathrm{Ord}$ が集合ではないので、置換公理をそのまま適用することはできません。

2. しかし終域が一つの集合なら、通常は像を集合として定義できる

例えば
$F:\mathrm{Ord}\to B$
で $B$ が集合であり、 $F$ が集合論の言語で定義可能な類関数なら、
$\operatorname{Im}(F) = \{y\in B\mid \exists\alpha\, (\alpha\text{ は順序数}\land F(\alpha)=y)\}$
と書けます。
ここで重要なのは、これは $B$ の部分集合として定義されていることです。
したがって分出公理（Separation）によって
$\operatorname{Im}(F)\subseteq B$
は集合になります。
つまり、

定義可能な類関数 $F:\mathrm{Ord}\to B$ の終域 $B$ が集合なら、その像は集合である。

ということが言えます。

3. 例えば

$F(\alpha)= \begin{cases} 0 & \alpha\text{ が有限}\\ 1 & \alpha\text{ が無限} \end{cases}$
とすると、
$F:\mathrm{Ord}\to\{0,1\}$
ですから、
$F[\mathrm{Ord}]=\{0,1\}$
は明らかに集合です。
もっと一般に
$F(\alpha)=\alpha\bmod 2$
のような関数なら
$F:\mathrm{Ord}\to\{0,1\}$
なので像は集合です。

4. 「終域が集合」という条件はかなり本質的

例えば
$F:\mathrm{Ord}\to\mathrm{Ord}, \qquad F(\alpha)=\alpha$
を考えると、
$F[\mathrm{Ord}]=\mathrm{Ord}.$
しかし $\mathrm{Ord}$ は集合ではありません。
したがって、
$F:\mathrm{Ord}\to\mathrm{Ord}$
だからといって、像が集合になるわけではありません。

5. より一般的な条件

実は、
$F:\mathrm{Ord}\to V$
のような「順序数全体上の類関数」については、
$\{F(\alpha)\mid\alpha\in\mathrm{Ord}\}$
が集合になるための非常に自然な条件は、

すべての $F(\alpha)$ を含む集合 $A$ が存在すること

です。
すなわち
$\exists A\quad \forall\alpha\in\mathrm{Ord}\;(F(\alpha)\in A).$
この条件があれば、
$F[\mathrm{Ord}] = \{x\in A\mid \exists\alpha\in\mathrm{Ord}\;(F(\alpha)=x)\}$
として分出公理によって集合になります。
そして、像そのものが集合なら当然それ自身を $A$ に取れるので、（定義可能な類関数について）
$\boxed{ F[\mathrm{Ord}]\text{ が集合} \iff \exists A\text{（集合）}\; \forall\alpha\in\mathrm{Ord}\,F(\alpha)\in A }$
と考えることができます。

6. 特に「ある段階以降は新しい値を取らない」なら集合になる

例えば、ある順序数 $\beta$ が存在して
$\forall\alpha\geq\beta,\qquad F(\alpha)=F(\beta)$
なら、
$F[\mathrm{Ord}] = F[\beta]\cup\{F(\beta)\}.$
ここで $\beta$ は集合なので、置換公理によって $F[\beta]$ は集合です。したがって全体の像も集合です。
これは超限再帰などで非常によく使われる考え方です。

まとめ

関数像

$f:A\to B$ 、 $A,B$ が集合必ず集合

$F:\mathrm{Ord}\to B$ 、 $B$ が集合 定義可能な類関数なら集合

$F:\mathrm{Ord}\to\mathrm{Ord}$ 集合とは限らない

$F(\alpha)=\alpha$ 像は $\mathrm{Ord}$ なので真の類

$F(\mathrm{Ord})$ がある集合 $A$ に含まれる像は集合

特に重要なのは、「定義域が集合である」という条件の代わりに、「像があらかじめ一つの集合の中に収まっている」という条件を使えるという点です。
これは、前に質問されていた「順序数全体から順序数全体への写像」や「整列集合から定まる順序数を関数として扱う」という話にも直接関係します。

関数	像
$f:A\to B$ 、 $A,B$ が集合	必ず集合
$F:\mathrm{Ord}\to B$ 、 $B$ が集合	定義可能な類関数なら集合
$F:\mathrm{Ord}\to\mathrm{Ord}$	集合とは限らない
$F(\alpha)=\alpha$	像は $\mathrm{Ord}$ なので真の類
$F(\mathrm{Ord})$ がある集合 $A$ に含まれる	像は集合

順序数全体から一つの集合への関数は超限再帰的に定義しても良いですか？

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

はい、できます。ただし、「どの集合を値域とするか」と「超限再帰の定義式」が集合論的に正当化できることが重要です。
例えば、集合 $A$ に値を取る関数
$F:\mathrm{Ord}\to A$
を超限再帰的に
$F(\alpha)=G\bigl(\alpha,F\mathbin{\upharpoonright}\alpha\bigr)$
によって定義するとします。
ここで
$F\mathbin{\upharpoonright}\alpha = \{(\beta,F(\beta))\mid\beta<\alpha\}$
です。

1. 各段階では問題ない

任意の順序数 $\alpha$ について、
$F\mathbin{\upharpoonright}\alpha:\alpha\to A$
は集合として存在します。
なぜなら $\alpha$ は集合なので、これまでの値
$F(0),F(1),\ldots,F(\beta),\ldots\quad(\beta<\alpha)$
を置換公理によって一つの集合としてまとめられるからです。
したがって、
$G(\alpha,F\mathbin{\upharpoonright}\alpha)\in A$
を返すような $G$ が定義できれば、次の値 $F(\alpha)$ を決められます。

2. そして「すべての順序数」まで再帰できる

ここが少し面白いところです。
通常の超限再帰定理は、ある集合である整列順序の上で再帰を行います。
しかし、順序数全体
$\mathrm{Ord}$
は真の類です。
それでも集合論では、適切な定義可能性条件を満たす再帰式に対して、
$F:\mathrm{Ord}\to A$
という類関数を超限再帰によって定義できます。
例えば
$F(0)=a$
$F(\alpha+1)=H(F(\alpha))$
$F(\lambda)=K(F\mathbin{\upharpoonright}\lambda) \qquad(\lambda\text{ は極限順序数})$
のような定義です。

3. 重要なのは「 $F$ 自体は集合ではない」こと

ここは前の質問との関係で非常に重要です。
$F:\mathrm{Ord}\to A$
では、通常
$F=\{(\alpha,F(\alpha))\mid\alpha\in\mathrm{Ord}\}$
は集合ではありません。
なぜなら定義域 $\mathrm{Ord}$ が真の類だからです。
したがって $F$ は正確には

集合ではなく、定義可能な類関数

として扱います。
一方、任意の個々の $\alpha$ については
$F\mathbin{\upharpoonright}\alpha$
は集合です。
つまり、
$\boxed{ F:\mathrm{Ord}\to A \quad\text{は類関数だが、}\quad F\mathbin{\upharpoonright}\alpha\text{ は各 }\alpha\text{について集合} }$
となります。

4. 例えば自然数への超限再帰

非常に単純な例として、
$F:\mathrm{Ord}\to\{0,1\}$
を
$F(0)=0,$
$F(\alpha+1)=1-F(\alpha),$
$F(\lambda)=0 \quad(\lambda\text{ が極限順序数})$
と定義できます。
これは順序数全体にわたる超限再帰的定義です。
この場合、値域は
$\{0,1\}$
という一つの集合に収まっています。

5. ただし「任意の式でよい」わけではない

例えば
$F(\alpha)=\{F(\beta)\mid\beta<\alpha\}$
なら問題ありません。これは通常の超限再帰です。
一方、
$F(\alpha)=\mathrm{Ord}$
としたら、これは「一つの集合への関数」にはなりません。値 $F(\alpha)$ 自体が集合ではなく真の類だからです。
また、
$F(\alpha)=\alpha$
とすると
$F:\mathrm{Ord}\to\mathrm{Ord}$
ですが、値域を「一つの集合」に制限することはできません。
したがって、質問への答えを簡潔に言うと、
$\boxed{\text{はい。順序数全体上の関数を超限再帰によって定義できます。}}$
ただし、
$\boxed{\text{各段階で得られる値が集合 }A\text{ に属し、再帰式が集合論的に定義可能であること}}$
が必要です。
そして、この場合に得られる $F$ は通常集合としての関数ではなく、類関数です。
なお、この点は「超限再帰定理」を ZF/ZFC の公理からどう定式化・証明するかという話につながります。特に「集合上の超限再帰」と「 $\mathrm{Ord}$ 全体上の超限再帰」は少し違うので、そこを区別するとかなり明確になります。

一つの集合から順序数全体への関数の像が定義できる条件は何ですか？

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

はい。ここでは前の質問と逆に、
$f:A\to\mathrm{Ord}$
を考えます。 $A$ は一つの集合、 $\mathrm{Ord}$ は順序数全体（真の類）です。
この場合は、実は前のケースより単純です。

結論

$\boxed{\text{$A$ が集合なら、任意の関数 }f:A\to\mathrm{Ord}\text{ の像 }f[A]\text{ は集合です。}}$
これは 置換公理を使えば示せます。

なぜか

$A$ は集合なので、
$f[A]=\{f(a)\mid a\in A\}$
に置換公理を適用できます。
したがって、 $f(a)$ がすべて順序数であることから、
$f[A]$
は順序数だけからなる集合になります。
例えば
$f:\mathbb N\to\mathrm{Ord}$
で
$f(n)=\omega+n$
とすれば、
$f[\mathbb N] = \{\omega,\omega+1,\omega+2,\ldots\}$
は集合です。

さらに重要なこと：像には上限が存在する

$f[A]$ が順序数の集合なら、その和
$\sup f[A]=\bigcup f[A]$
も順序数になります。
したがって、ある順序数 $\gamma$ が存在して
$\forall a\in A,\qquad f(a)<\gamma$
となります。
例えば
$\gamma=\sup\{f(a)+1\mid a\in A\}$
と取れば、
$f[A]\subseteq\gamma$
です。
つまり、
$\boxed{ A\text{ が集合},\quad f:A\to\mathrm{Ord} \quad\Longrightarrow\quad f[A]\text{ は集合で、しかも一つの順序数の中に収まる} }$
となります。

これは「順序数全体を集合で覆えない」ことと対照的

例えば恒等写像
$\operatorname{id}:\mathrm{Ord}\to\mathrm{Ord}$
では
$\operatorname{id}[\mathrm{Ord}]=\mathrm{Ord}$
なので像は集合ではありません。
一方、定義域が集合 $A$ なら、
$f:A\to\mathrm{Ord}$
の像は必ず集合です。
この違いは、
$\boxed{ \begin{array}{c} A\to\mathrm{Ord}\\ A\text{ が集合} \end{array} } \quad\Longrightarrow\quad \text{像は集合}$
に対して、
$\boxed{ \begin{array}{c} \mathrm{Ord}\to\mathrm{Ord}\\ \mathrm{Ord}\text{ は真の類} \end{array} } \quad\Longrightarrow\quad \text{像は集合とは限らない}$
というものです。
さらに一歩進めると、「集合 $A$ から $\mathrm{Ord}$ への関数は、その像が必ずある順序数 $\beta$ より小さい」という事実は、正則性や置換公理との関係で非常に重要です。特に「集合から順序数全体への写像」と「順序数全体から集合への写像」を対比すると、前の質問との違いがきれいに整理できます。