順序数

この項目では、数学的な観点からの順序数について説明しています。言語学的な観点での順序数については「序数詞」をご覧ください。

数学の特に集合論において、順序数（じゅんじょすう、英: 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 の要素の個数に等しい。

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

脚注[編集]

参考文献[編集]

関連項目[編集]

外部リンク[編集]

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

表 話 編 歴 集合論
基本	集合 元 包含関係 内包と外延 クラス ベン図
演算	和集合 非交和 共通部分 素集合 直積集合 分割 補集合 差集合 対称差 冪集合 ド・モルガンの法則 集合の代数学
関係	性質 反射関係 推移関係 推移閉包 対称関係 非対称関係 反対称関係 完全関係 同値関係 同値類 well-defined 整礎関係 逆関係 関係の合成 写像 定義域 終域 値域 単射 全射 全単射 逆写像 像と逆像 恒等写像 制限 包含写像 合成 射影 商写像 指示関数 配置集合 族 添字集合 順序対 順序組 列 集合族 グラフ 部分写像 対応 順序 前順序 有向 半順序 全順序 整列 稠密 有界 単調写像 順序同型 辞書式順序 順序型 推移的集合 順序数 0 後続 極限 自然数 ハッセ図 超限帰納法 ツォルンの補題 整列可能定理 整礎的集合 フォン・ノイマン宇宙
濃度	有限集合 空集合 単集合 遺伝的 可算集合 非可算集合 連続体濃度 始順序数 共終数 基数 正則 到達不能 巨大 一覧 ベルンシュタインの定理 カントールの対角線論法 カントールの定理 連続体仮説
公理化	素朴集合論 ラッセルのパラドックス 公理的集合論 ツェルメロ＝フレンケル集合論 フォン・ノイマン＝ベルナイス＝ゲーデル集合論 モース-ケリー集合論 新基礎集合論 外延性の公理 空集合の公理 分出公理 対の公理 和集合の公理 冪集合公理 置換公理 無限公理 正則性公理 選択公理 可算 従属
研究者	ゲオルク・カントール リヒャルト・デーデキント バートランド・ラッセル エルンスト・ツェルメロ アドルフ・フレンケル ジョン・フォン・ノイマン クルト・ゲーデル ポール・コーエン
カテゴリ

表 話 編 歴 数の体系
可算な体系	自然数 (${\displaystyle \mathbb {N} }$) 整数 (${\displaystyle \mathbb {Z} }$) 有理数 (${\displaystyle \mathbb {Q} }$) 作図可能数 代数的数 (${\displaystyle \mathbb {A} }$) 周期 計算可能数 定義可能実数 算術数（英語版） ガウス整数 (${\displaystyle \mathbb {Z} [i]}$) アイゼンシュタイン整数 (${\displaystyle \mathbb {Z} [\omega ]}$)
合成代数	通常型 実数 (${\displaystyle \mathbb {R} }$) 複素数 (${\displaystyle \mathbb {C} }$) 四元数 (${\displaystyle \mathbb {H} }$) 八元数 (${\displaystyle \mathbb {O} }$) 分解型 /${\displaystyle \mathbb {R} }$ 分解型複素数 分解型四元数（英語版） 分解型八元数 /${\displaystyle \mathbb {C} }$ 双複素数 双四元数（英語版） 双八元数
その他の多元数	二重数 二重四元数（英語版） 双曲四元数（英語版） 十六元数 (${\displaystyle \mathbb {S} }$) 分解型双四元数（英語版） 多重複素数
その他	基数 無理数 ファジー数（英語版） 超実数 レヴィ＝チヴィタ体 超現実数 超越数 順序数 p-進数 (${\displaystyle \mathbb {Q} _{p}}$) シュタイニッツ数 準超実数
一覧 カテゴリ:数