順序数 - くたくたじゅうよん

順序数

濃度を数のように取り扱うために使う道具

集合のみによる定義 by John von Neumann

$ (\alpha,⋸)が整列集合となる推移的集合$ \alphaを順序数と呼ぶ

$ a⋸b:\iff a\underline\in b:\iff a\in b\lor a=bとしておく

冪集合の半順序集合

正則性公理を仮定するなら、$ (\alpha,⋸)は全順序集合であれば十分

証明

$ (\alpha,⋸)\text{は全順序集合}

$ \iff\begin{dcases}(\alpha,⋸)\text{は全順序集合}\\\forall A\in2^\alpha\setminus\{\varnothing\}\exists y\in A\forall x\in A:x\notin y)\end{dcases}

$ \because正則性公理

$ \iff\begin{dcases}(\alpha,⋸)\text{は全順序集合}\\\forall A\in2^\alpha\setminus\{\varnothing\}\exists y\in A\forall x\in A:\lnot(x⋸y)\lor x=y)\end{dcases}

$ \iff\begin{dcases}(\alpha,\in)\text{は全順序集合}\\\forall A\in2^\alpha\setminus\{\varnothing\}\exists y\in A\forall x\in A:y⋸x\lor x=y)\end{dcases}

$ \because全順序律

$ \underline{\iff(\alpha,⋸)\text{は整列集合}\quad}_\blacksquare

推移的集合を$ ⋸で表す

$ \forall x\forall y:y\in x\in X\implies y\in X

$ \iff\forall x\in X:x\subseteq X

$ \iff\forall x⋸ X:x\subseteq X

$ \implies\forall x\forall y:y⋸x⋸X\implies y⋸ X

$ (\alpha,⋸)の推移律の同値変形

$ \forall x,y,z\in\alpha:x\in y\in z\implies x\in z

$ \iff\forall z,y\in\alpha:y\in z\implies y\subseteq z

$ \iff\forall z\in\alpha\forall y\in\alpha\cap z:y\subseteq z

推移的集合の性質を使うと

$ \iff\forall z\in\alpha\forall y\in z:y\subseteq zー☆

第14章順序数

以下、$ \alpha,\betaを任意の順序数とする

定理 14.15 順序数の元は全て順序数

証明

$ \forall x:

$ x\in\alpha

$ \iff\begin{dcases}x\in\alpha\\\forall y\in x:y\subseteq x\end{dcases}

$ \because☆

$ \implies\begin{dcases}x\subseteq\alpha\\\forall y\in x:y\subseteq x\end{dcases}

$ \because\alphaは推移的集合

$ \iff\begin{dcases}x\subseteq\alpha\\\forall y\in x:y\subseteq x\\\forall A\in2^\alpha\setminus\{\varnothing\}\exist m\in A\forall y\in A:m⋸y\end{dcases}

$ \because(\alpha,⋸)は整列集合

$ \implies\begin{dcases}x\subseteq\alpha\\\forall y\in x:y\subseteq x\\\forall A\in2^x\setminus\{\varnothing\}\exist m\in A\forall y\in A:m⋸y\end{dcases}

$ x\subseteq\alphaを使った

$ \underline{\implies x\text{は順序数}\quad}_\blacksquare

補題14.16 $ \forall\beta\in\alpha:\alpha_{\in\beta}=\beta

証明：$ \forall\beta:

$ \beta\in\alpha

$ \implies\alpha_{\in\beta}=\alpha\cap\beta

$ =\beta

$ \because\alphaは推移的集合だから$ \beta\subseteq\alpha

$ \underline{\therefore\forall\beta\in\alpha:\alpha_{\in\beta}=\beta\quad}_\blacksquare

$ \alpha_{\in\beta}は$ \alphaの$ \betaによる切片 (整列集合)に相当する

補題14.17 $ \alpha\notin\alpha

証明：

$ \top

$ \iff\forall x\in\alpha:x\notin x

$ \because(\alpha,⋸)の狭義全順序$ \inの非反射律

$ \implies(\alpha\in\alpha\implies\alpha\notin\alpha)

$ \underline{\iff\alpha\notin\alpha\quad}_\blacksquare

正則性公理を仮定するなら、¬∃A:A∈Aから直ちに導ける

補題14.18 $ \varnothing⋸\alpha

証明：$ \alpha\neq\varnothing

$ \implies\exist m\in\alpha\forall a\in\alpha:m⋸a

$ \because(\alpha,⋸)は整列集合

$ \implies\exist m\in\alpha:\begin{dcases}\forall a\in\alpha:m⋸a\\\forall a:\end{dcases}

$ a\in m

$ \implies a\in m\in\alpha

$ \implies a\in\alpha\land m\in\alpha

$ \because\alphaは推移的集合

$ \implies m⋸a\in m

$ \because\forall a\in\alpha:m⋸a

$ \implies m\in m

$ \because mは順序数だから$ m\in a\in m\implies m\in m

$ \implies\bot

$ \because m\notin m 補題14.17

$ \implies\exist m\in\alpha:m=\varnothing

$ \iff\varnothing\in\alpha

$ \therefore\alpha\neq\varnothing\implies\varnothing\in\alpha

$ \iff\alpha=\varnothing\lor\varnothing\in\alpha

$ \underline{\iff\varnothing⋸\alpha\quad}_\blacksquare

空集合は順序数takker.icon

├∀x∈∅;P(x)より$ (\varnothing,⋸)が整列集合かつ推移的集合になるから

補題14.19 $ \alpha⋸\beta\iff\alpha\subseteq\beta

証明

(L)⇒(R)

$ \alpha⋸\beta

$ \implies\alpha\subseteq\beta

$ \because$ \betaは推移的集合

(R)⇒(L)

$ \alpha\subsetneq\beta

$ \implies\alpha\subsetneq\beta\land(

$ \beta=\varnothing

$ \implies\forall x\in\alpha:x\in\varnothing\land\alpha\neq\varnothing

$ \iff\alpha=\varnothing\land\alpha\neq\varnothing

$ \iff\bot

$ \implies\alpha\subsetneq\beta\land\beta\neq\varnothing

$ \implies\beta\setminus\alpha\neq\varnothing

$ \implies\exist m\in\beta\setminus\alpha\forall x\in\beta\setminus\alpha:m⋸x

$ \because(\beta,⋸)は整列集合, $ \beta\setminus\alpha\subseteq\beta

$ \iff\exist m\in\beta\setminus\alpha:\begin{dcases}\forall x\in\beta\setminus\alpha:m⋸x\\\forall\gamma:\end{dcases}

$ \gamma\in m

$ \implies\gamma\in\beta

$ \because\betaは推移的集合

$ \implies(

$ \gamma\notin\alpha

$ \iff\gamma\in\beta\setminus\alpha

$ \implies m⋸\gamma

$ \because\forall x\in\beta\setminus\alpha:m⋸x

$ \implies m\in m

$ \because mは順序数だから$ m\in\gamma\in m\implies m\in m

$ \implies\bot

$ \because m\notin m 補題14.17

$ )

$ \implies\gamma\in\alpha

$ \iff\exist m\in\beta:\begin{dcases}\forall x\in\beta\setminus\alpha:m⋸x\\m\subseteq\alpha\\m\notin\alpha\\\forall\gamma:\end{dcases}

$ \gamma\in\alpha

$ \iff\gamma\in\alpha\cap\beta

$ \because\alpha\subsetneq\beta

$ \implies(\gamma⋸ m\lor m⋸\gamma)\in\land\gamma\in\alpha

$ \because(\beta,⋸)の全順序律

$ \iff(\gamma⋸ m\land\gamma\in\alpha)\lor m⋸\gamma\in\alpha

$ \implies(\gamma\in m\cap\alpha\lor\gamma=m\in\alpha)\lor m\in\alpha

$ \because\alphaは推移的集合

$ \implies\gamma\in m

$ \because m\notin\alpha

$ \implies\exist m\in\beta:m=\alpha

$ \iff\alpha\in\beta

$ \therefore\alpha\subseteq\beta\implies\alpha⋸\beta

順序数の元は全て順序数だから、$ (\alpha,⋸)=(\alpha\subseteq)としていいとわかる

ここから、補題14.18は自明だとわかる

$ \because\top\implies\varnothing\subseteq\alpha\iff\varnothing⋸\alpha

($ \varnothingが順序数であることがわかったうえでの式変形)

$ x^+:=x\cup\{x\}

補題14.20$ \forall x,y:x\subseteq y\subseteq x^+\implies y=x\lor y=x^+

証明

$ \forall x,y:

$ x\subseteq y\subseteq x^+

$ \iff\begin{dcases}x\subseteq y\subseteq x^+\\\{x\}\subseteq y\end{dcases}

$ \implies x\cup\{x\}\subseteq y

$ \iff x^+\subseteq y

$ \implies x^+=y

$ \iff\begin{dcases}x\subseteq y\subseteq x^+\\\{x\}\subseteq y\implies y=x^+\\\{x\}\nsubseteq y\end{dcases}

$ \implies x\notin y

$ \implies x\notin y\land y\subseteq x^+

$ \implies x\notin y\land\forall a\in y:a\in x\lor a=x\in y

$ \implies\forall a\in y:a\in x\lor\bot

$ \iff y\subseteq x

$ \implies y=x

$ \implies y=x\lor y=x^+

もっときれいに証明したいtakker.icon

$ \forall x,y: x\subseteq y\subseteq x^+\implies y=\begin{dcases}x&\text{if }x\notin y\\x^+&\text{if }x\in y\end{dcases}とも書ける

$ x\in y^+\iff x\in y\cup\{y\}\iff x⋸yである

定理14.21 $ \alpha^+は順序数

証明

$ \top

$ \implies\forall x:

$ x\in\alpha^+

$ \iff x⋸\alpha

$ \implies x\subseteq\alpha

$ \because\alphaは推移的集合

$ \implies x\subseteq\alpha^+

$ \implies\forall x\in\alpha^+:x\subseteq\alpha^+

$ \implies\begin{dcases}\forall x\in\alpha^+:x\subseteq\alpha^+\\\forall A:\end{dcases}

$ A\in2^{\alpha^+}\setminus\{\varnothing\}

$ \implies A\setminus\{\alpha\}\in2^\alpha\setminus\{\varnothing\}\lor A=\{\alpha\}

$ \implies\exist m\in A\setminus\{\alpha\}\forall y\in A\setminus\{\alpha\}:m⋸y\lor\forall x\in A:\alpha =x

$ \because(\alpha,⋸)は整列集合, $ A\setminus\{\alpha\}\subseteq\alpha

$ \implies\exist m\in A\setminus\{\alpha\}\forall y\in A:m⋸y\lor\forall x\in A:\alpha ⋸x

$ \because \forall m\in\alpha\cup\{\alpha\}:m⋸\alpha

$ \iff\exist m\in A\setminus\{\alpha\}\forall y\in A:m⋸y\lor\exist m\in\{\alpha\}\forall y\in A:m⋸y

$ \iff\exist m\in A\forall y\in A:m⋸y

$ \implies\begin{dcases}\forall x\in\alpha^+:x\subseteq\alpha^+\\\forall A\in2^{\alpha^+}\setminus\{\varnothing\}\exist m\in A\forall y\in A:m⋸y\end{dcases}

$ \implies\alpha^+は順序数

定理14.22 $ \forall x\in\alpha:x^+⋸\alpha

証明

$ \forall x:

$ x\in\alpha

$ \implies x\in\alpha\land x\subseteq\alpha\land xは順序数

$ \because\alphaは推移的集合

$ \iff x^+\subseteq\alpha\land x^+は順序数

$ \implies x^+⋸\alpha

$ \because補題14.19

定理14.23.1 $ (\max\alpha)^+=\alpha

証明

$ (\max\alpha)^+\in\alpha

$ \implies(\max\alpha)^+⋸\max\alpha

$ \implies(\max\alpha)^+\subseteq\max\alpha

$ \because補題14.19,$ (\max\alpha)^+,\max\alpha\in\alphaだからどちらも順序数

$ \iff\max\alpha\in\max\alpha

$ \iff\bot

$ \because補題14.17

$ \implies(\max\alpha)^+\notin\alphaー①

よって、①と定理14.22より

$ (\max\alpha)^+⋸\alpha

$ \underline{\implies(\max\alpha)^+=\alpha\quad}_\blacksquare

定理14.23.2 $ \forall x\in\alpha\setminus\{\max\alpha\}:x\lessdot x^+

$ \lessdot：$ (\alpha,⋸)における被覆 (順序)

証明

$ \forall x:

$ x\in\alpha\setminus\{\max\alpha\}

$ \implies\forall y\in\alpha:

$ x\in y\in x^+

$ \iff x\in y⋸x

$ \iff x\in y\subseteq x

$ \because補題14.19

$ \implies x\in x

$ \iff\bot

$ \because補題14.17

$ \implies x\in x^+\land\lnot\exist y\in\alpha:x\in y\in x^+

$ \iff x\lessdot x^+

$ \underline{\implies\forall x\in\alpha\setminus\{\max\alpha\}:x\lessdot x^+\quad}_\blacksquare

これより、$ \alpha^+を$ \alphaの後続順序数と呼ぶ

$ \omega\neq\varnothing\land\lnot\exist x:x^+=\omegaである$ \omegaを極限順序数という

例えば無限公理で構築した自然数$ \Nは極限順序数のはず

$ \exist x:x^+=\N

$ \implies\exist x\in\N:x^+=\N

$ \implies\exist x\in\N:x^+\in\N=x^+

$ \because無限公理

$ \implies\N\in\N

$ \implies\bot

$ \because¬∃A:A∈A

$ \therefore\Nは極限順序数

そもそも$ \max\alphaは存在するのか？

$ \forall m\in\alpha\exist x\in\alpha:\lnot(x⋸m)

$ \iff\forall m\in\alpha\exist x\in\alpha:m⋸x

$ \iff\forall m\in\alpha\exist x\in\alpha:m\in x

なくてもおかしくなさそうだ

そもそも$ (\N,\le)みたく、最大元のない整列集合はいくらでもある

$ \max\alphaが存在しなければ、$ \forall x\in\alpha:x^+\in\alphaである

このとき$ \alphaは$ \bullet^+について閉じている

順序数の比較可能性

補題14.24 任意の順序数$ \alpha,\betaにて$ \alpha\subseteq\beta\lor\beta\subseteq\alpha

補題14.19と

定理14.25 任意の順序数$ \alpha,\betaにて$ (\alpha,⋸)\cong_o(\beta,⋸)\implies\alpha=\beta

$ \cong_o：順序同型

定理14.26 任意の順序数$ \alpha,\betaにて$ \alpha\in\beta\veebar\alpha=\beta\veebar\beta\in\alpha

三分律に相当する条件

定理14.27 $ \varnothingは最小の順序数である

定理14.28

任意の整列集合$ (X,\le)に対して、$ (X,\le)\cong_o(\alpha,⋸)となる順序数$ \alphaがただ一つ存在する

Burali-Fortiの定理

集合$ Xの部分集合となる順序数と、そこから生成される順序数を全て集めたクラスは集合になるだろうか？takker.icon

順序数の演算

$ \alpha+\beta:=

$ \alphaの元を全て並べ、その後ろに$ \betaの元を全て並べたものと等しい

$ (\alpha,\subseteq)が整列集合になることを順序数の定義とした場合の展開

順序数の元は全て順序数

$ \forall\beta:

$ \beta\in\alpha

$ \iff\beta\in\alpha\land\forall x:

$ x\in\beta

$ \implies x\in\beta\subseteq\alpha

$ \implies x\subseteq\beta\lor\beta\subseteq x

$ x\subseteq\alpha

$ \exist m\in x\setminus\beta\forall y\in x\setminus\beta:m\subseteq y

$ y\in x\in\beta

$ \implies y\in x\in\alpha\cap\beta\land\beta\in\alpha

$ \implies\beta,x,y\in\alpha\land\beta,x,y\subseteq\alpha\land y\in x\in\beta

References

Zermelo と von Neumann の無限公理の同値性

「集合・写像・数の体系　数学リテラシーとして」の草稿第14章順序数

https://ja.wikipedia.org/wiki/順序数

ordinal number

#2025-07-31 13:32:39

#2025-07-27 14:43:36

#2025-07-20 18:08:19