順序数

数学の特に集合論において、順序数（じゅんじょすう、英: ordinal number）とは、整列集合同士の“長さ”を比較するために、自然数^[1]を拡張させた概念である。

整列集合 (A, <) に対して、A を定義域とする写像 G_{A, <} を超限帰納法によって

${\displaystyle G_{A,<}(a)=\{G_{A,<}(x)\mid x<a\}}$

と定義したとき、G_{A, <} の値域 ran(G_{A, <}) を (A, <) の順序数といい、これを ord(A, <) で表す。ある整列集合の順序数であるような集合を順序数と呼ぶ^[2]。

<_ω は自然数の通常の大小関係（を各集合に制限したもの）を表すものとすると、

${\displaystyle {\begin{aligned}\operatorname {ord} (\varnothing ,<_{\omega })&=\varnothing =0\\\operatorname {ord} (\{2\},<_{\omega })&=\{\varnothing \}=1\\\operatorname {ord} (\{2,3\},<_{\omega })&={\bigl \{}\varnothing ,\{\varnothing \}{\bigr \}}=\{0,1\}=2\\\operatorname {ord} (\{2,3,5\},<_{\omega })&={\Bigl \{}\varnothing ,\{\varnothing \},{\bigl \{}\varnothing ,\{\varnothing \}{\bigr \}}{\Bigr \}}=\{0,1,2\}=3\end{aligned}}}$

この例から推測されるように、一般に有限の整列集合 (A, <) に対して ord(A, <) は A の要素の個数に等しい。特に、任意の自然数 n に対して ord(n, <_ω) = n が成り立つので、自然数はすべて順序数である。

順序数に関して次が成り立つ：

1. 整列集合 (A, <_A) と整列集合 (B, <_B) が同型のとき、またそのときに限り ord(A, <_A) = ord(B, <_B)。
2. (A, <) が有限整列集合のとき、ord(A, <) は A の要素の個数に等しい。
3. 整列集合 (A, <) の順序数を α とし、∈_α を α 上の所属関係とすると、(α, ∈_α) は (A, <) と同型な整列集合である。
4. α が順序数であることと、α が ∈ によって整列された推移的集合であることは同値である。
5. α が順序数のとき、α の要素もすべて順序数である。

自然数全体の集合 ω は ∈ によって整列された推移的な集合であるから、上の事実 4. より ω は順序数である。

任意の順序数 α, β, γ に対して次が成り立つことが示される：

α ∉ α

α ∈ β かつ β ∈ γ ⇒ α ∈ γ

α ∈ β または α = β または β ∈ α

そこで、α ∈ β のとき β は α より大きいといい、α < β と書く。この定義と順序数の要素はまた順序数であるという性質から、すべての順序数は自分自身より小さな順序数全体の集合と等しいと言うことができる。ω より小さな順序数（すなわち自然数）を有限順序数と呼び、ω 以上の（すなわち ω と等しいか ω より大きい）順序数を超限順序数と呼ぶ。順序数の大小関係に関して次が成り立つ：

1. 整列集合 (A, <_A) が整列集合 (B, <_B) のある始切片と同型のとき、またそのときに限り ord(A, <_A) < ord(B, <_B)。
2. 有限順序数の範囲では、上で定義された大小関係は通常の大小関係と一致する。
3. α が順序数のとき、S(α) ≔ α ∪ { α } は α より大きな順序数のうちで最小のものである。S(α) を α の後続者 (successor of α)と呼ぶ。
4. O が順序数からなる集合のとき、${\textstyle \bigcup _{\alpha \in O}\alpha }$ もまた順序数であり、O の最小上界となっている。そこで、${\textstyle \bigcup _{\alpha \in O}\alpha }$ を sup(O) とも書く。
5. 順序数からなる空でない集合には必ず最小元が存在する。

順序数の並び方を次のように図示することができる：

0, 1, 2, 3, ............, ω, S(ω), S(S(ω)), S(S(S(ω))), ............, ω + ω, S(ω + ω), S(S(ω + ω)), S(S(S(ω + ω))), ..............................

まず、0 が最小の順序数である。その後に S(0) = 1, S(S(0)) = 2, S(S(S(0))) = 3, ... と有限順序数（自然数）が通常の順序で並んでいる。そして、すべての自然数が並び終えると、次に来るのが最小の超限順序数 ω である。ω の後にはまたその後続者たちが S(ω), S(S(ω)), S(S(S(ω))), ... と無限に続いていく。その後、それらの最小上界（後に ω + ω と呼ばれる）が並び、その後続者たちが無限に続く。だがそれで終わりではない。無限に続いた後には、必ずそれまでに並んだすべての順序数たちの最小上界が存在し、その後続者、そのまた後続者、... のように順序数の列は“永遠に”続いていくのである。

集合 x について以下はZFで同値である。

• x は順序数である。
• x は推移的集合であり帰属関係 ∈ に関する整列集合である。 （ジョン・フォン・ノイマンの定義）^[3][4]
• x は推移的集合であり y, z ∈ x ならば y ∈ z, y = z, y ∋ z のいずれか1つだけが成り立つ。
• x は推移的集合であり包含関係 ⊂ に関する全順序集合である。
• x は推移的集合であり x の要素もまた推移的集合である。

ただし正則性公理を仮定しない場合は必ずしも同値にならないので注意が必要である。

ブラリ＝フォルティの定理とは、「すべての順序数からなる集合は存在しない」という定理である。これは次のようにして示すことができる：

すべての順序数からなる集合 ON が存在すると仮定する。すると、順序数の要素はまた順序数であるという性質から ON は推移的な集合である。さらに、ON の空でない部分集合には必ず ∈ に関する最小元が存在するので、ON は ∈ によって整列されている。したがって ON は順序数であるので ON ∈ ON であるが、これは任意の順序数 α に対して α ∉ α であるという事実と矛盾する。よって順序数全体の集合は存在しない。

かつて、集合論が公理化される以前には、「集合全体の集合」や「順序数全体の集合」といったものも無制限に考えられていたため、上のように順序数全体の集合を考えたときに起こる矛盾はブラリ＝フォルティのパラドックスと呼ばれていた。

ある順序数 β が存在して α = S(β) となる順序数 α を後続順序数 (successor ordinal) と呼ぶ。0 でも後続順序数でもない順序数を極限順序数 (limit ordinal) と呼ぶ。定義より、すべての順序数 α に対して、

• α = 0
• α は後続順序数である
• α は極限順序数である

のいずれか一つだけが成り立つ。ω は最小の極限順序数である。また、任意の順序数 α に対して、α より大きな極限順序数が存在することが示される。

順序数の間には自然数の場合と同じく和、積、冪が定義できる。特に有限順序数の間の演算は通常のそれと一致する。

α, β を順序数とする。 整列集合 (A, <_A), (B, <_B) を ord(A, <_A) = α, ord(B, <_B) = β, A ∩ B = ∅ をみたすように取り、A ∪ B 上の関係 <_A ⊕ <_B を、

x (<_A ⊕ <_B) y 　⇔　 x <_A y または x <_B y または ⟨x, y⟩ ∈ A × B

によって定義すれば、(A ∪ B, <_A ⊕ <_B) は整列集合であり、その順序数は (A, <_A), (B, <_B) の特定の取り方によらず一定である。そこで ord(A ∪ B, <_A ⊕ <_B) を α と β の和といい、これを α + β で表す。直観的には、α + β というのは α の後ろに β を並べてできる整列集合の順序数である。

順序数の和について次が成り立つ：

1. &α, β が有限順序数ならば、和 α + β は自然数の間の通常の和と一致する。
2. (α + β) + γ = α + (β + γ) 。
3. α + 0 = 0 + α = α 。
4. α + S(β) = S(α + β) 。
5. γ が極限順序数のとき、α + γ = sup({ α + β  |  β < γ}) 。
6. β < γ ⇔ α + β < α + γ 。
7. β ≤ γ ⇒ β + α ≤ γ + α 。
8. 順序数の和は一般には可換でない。例えば、1 + ω = ω ≠ ω + 1 である。
9. α ≤ β ならば α + γ = β をみたす γ がただ一つ存在する。

α, β を順序数とする。 整列集合 (A, <_A), (B, <_B) を ord(A, <_A) = α, ord(B, <_B) = β をみたすように取り、A × B 上の関係 <_A ⊗ <_B を、

⟨x₁, y₁⟩ (<_A ⊗ <_B) ⟨x₂, y₂⟩　⇔　 y₁ <_B y₂ または （y₁ = y₂ かつ x₁ <_A x₂）

によって定義すれば、(A × B, <_A ⊗ <_B) は整列集合であり、その順序数は (A, <_A), (B, <_B) の特定の取り方によらず一定である。そこで ord(A × B, <_A ⊗ <_B) を α と β の積といい、これを α · β で表す。直観的には、α · β というのは α を β 個並べてできる整列集合の順序数である。

順序数の積について次が成り立つ：

1. α, β が有限順序数ならば、積 α · β は自然数の通常の積に一致する。
2. (α · β) · γ = α · (β · γ) 。
3. α · 0 = 0 · α = 0 。
4. α · S(β) = (α · β) + α 。
5. γ が極限順序数のとき、α · γ = sup({ α · β  |  β < γ}) 。
6. α · 1 = 1 · α = α 。
7. 0 < α のとき、β < γ ⇔ α · β < α · γ 。
8. β ≤ γ ⇒ β · α ≤ γ · α 。
9. 順序数の積は一般には可換でない。例えば、2 · ω = ω ≠ ω · 2 である。
10. α · (β + γ) = (α · β) + (α · γ) 。
11. (β + γ) · α = (β · α) + (γ · α) は一般には成り立たない。
12. 任意の順序数 α と 0 でない順序数 δ に対して、α = (δ · β) + γ かつ γ < δ をみたす順序数の組 β, γ がただ一組存在する。

α, β を順序数とする。 整列集合 (A, <_A), (B, <_B) を ord(A, <_A) = α, ord(B, <_B) = β をみたすように取り、F(A, B) = { f ∈ ^BA | { b ∈ B  |  f(b) ≠ min(A)} は有限集合 } 上の関係 <_A △ <_B を、

f (<_A △ <_B) g 　⇔　 f ≠ g かつ、 f(b) ≠ g(b) をみたす最大の b ∈ B に対して f(b) <_A g(b)

によって定義すれば、(F(A, B), <_A △ <_B) は整列集合であり、その順序数は (A, <_A), (B, <_B) の特定の取り方によらず一定である。そこで ord(F(A, B), <_A △ <_B) を α の β 乗といい、これを α^β で表す。

順序数の冪について次が成り立つ：

1. α, β が有限順序数ならば、冪 α^β は自然数の通常の冪に一致する。
2. 0⁰ = 1 。
3. 0 < β のとき、0^β = 0 。
4. α⁰ = 1 。
5. α^S(β) = (α^β) · α 。
6. 0 < α で、γ が極限順序数のとき、α^γ = sup({ α^β  |  β < γ}) 。
7. 1 < α のとき、β < γ ⇔ α^β < α^γ 。
8. β ≤ γ ⇒ β^α ≤ γ^α 。
9. α^{β + γ} = (α^β) · (α^γ) 。
10. (α^β)^γ = α^{β · γ} 。
11. (β · γ)^α = (β^α) · (γ^α) は一般には成り立たない。

集合 A から集合 B への全単射が存在するとき、A と B は同数 (equinumerous) であるといい、A ≈ B で表す。 選択公理を仮定すれば、整列定理により任意の集合 A に対して A と同数であるような順序数が存在することが言える。そこで、集合 A と同数であるような順序数の中で最小のものを A の濃度 (cardinality of A) といい、これを |A| あるいは card(A) で表す。ある集合 A に対して α = |A| である順序数 α を基数 (cardinal number) と呼ぶ。集合の濃度に関して次が成り立つ：

1. |A| = |B| 　⇔　 A ≈ B
2. A が有限集合のとき、|A| は A の要素の個数に等しい。

基数に対しても、上で定義した順序数の演算とは別に和、積、冪を定義することができる。

• 『順序数』 - コトバンク