順序型

数学でいう順序型（じゅんじょがた、order type）とは、全順序集合同士の "型" を比較するために、その構造のみに注目することによって得られる概念である。

非公式な定義

二つの全順序集合 (A, <_A), (B, <_B) が同型のとき、(A, <_A) と (B, <_B) は全く同じ "型" をしていると言える。そこで、全順序集合 (A, <_A) の "型" を type(A, <_A) で表すことにすれば、任意の全順序集合 (A, <_A), (B, <_B) に対して

${\displaystyle {\mbox{type}}(A,<_{A})={\mbox{type}}(B,<_{B})\iff (A,<_{A})\cong (B,<_{B})}$　　　　・・・・・・(※)

が成り立つ。type(A, <_A) を (A, <_A) の順序型と呼ぶ。

正式な定義

上の説明では type(A, <_A) をきちんと定義したことにはならない。なぜなら、全順序集合の "型" とは何かが定義されていないからである。(※) をみたすようにすべての全順序集合 (A, <_A) に対して type(A, <_A) を定義する方法として、まず次のようなものが考えられる。それは、(A, <_A) と同型な順序集合全体の集合を type(A, <_A) と定義する方法である。実際、このように定義すれば (※) が成り立つことが示せるので何の問題もないように思えるかもしれない。だが、この方法には一つ大きな欠点がある。それは、A が空集合でない限り (A, <_A) と同型な順序集合全体の集合というものは存在しないことが（集合論の公理から）示されるということである。つまり、そのような集まりはあまりに大きすぎるため集合になることができないのである。したがって上のような仕方で type(A, <_A) を定義することはできない。そこで、この方法を少し修正して次のように順序型を定義する：

全順序集合 (A, <_A) に対して type(A, <_A) とは、(A, <_A) と同型な順序集合のうちで階数が最小のもの全体の集合である。type(A, <_A) を (A, <_A) の順序型と呼び、ある全順序集合の順序型であるものを単に順序型と呼ぶ^[1]。

全順序集合 (A, <_A) と同型な順序集合で階数が最小であるものの階数を α とすれば、type(A, <_A) の要素はすべて V_{α + 1} ^[2]に属するので、type(A, <_A) はきちんと集合として定義されている。このようにして定義された順序型が (※) の性質をみたしていることは次のようにして示すことができる：

(⇒) 　type(A, <_A) = type(B, <_B) と仮定する。定義から type(A, <_A) は空でないので、その要素の一つ (C, <_C) を取ると、仮定より (C, <_C) は type(B, <_B) にも属する。(C, <_C) ∈ type(A, <_A) より (A, <_A) と (C, <_C) は同型で、(C, <_C) ∈ type(B, <_B) より (B, <_B) と (C, <_C) は同型なので、(A, <_A) と (B, <_B) は同型である。

(⇐) 　(A, <_A) と (B, <_B) が同型であると仮定する。すると任意の順序集合 (C, <_C) に対して、(A, <_A) と (C, <_C) が同型であることと、(B, <_B) と (C, <_C) が同型であることは同値であるから、「(A, <_A) と同型な順序集合のうちで階数が最小のもの全体」と「(B, <_B) と同型な順序集合のうちで階数が最小のもの全体」は一致する。よって type(A, <_A) = type(B, <_B) 。

特別な順序型

Q を有理数全体の集合、R を実数全体の集合とし、<_Q と <_R をそれぞれ Q 上と R 上の通常の大小関係とすると、(Q, <_Q) と (R, <_R) はともに全順序集合である。通常、type(Q, <_Q) は η 、type(R, <_R) は λ で表される。

整列順序型と順序数

整列集合の順序型を特に整列順序型と呼ぶ。α を順序数とし ∈_α を α 上の所属関係とすると、(α, ∈_α) は整列集合なので type(α, ∈_α) は整列順序型である。逆に、任意の整列集合は必ずある順序数 α に対する (α, ∈_α) と同型なので、整列順序型は必ずある順序数 α に対する type(α, ∈_α) の型で表すことができる。以下では type(α, ∈_α) を α で表す。

順序型の演算

順序型には和と積の演算を定義することができる。

和

ρ, σ を順序型とする。 全順序集合 (A, <_A), (B, <_B) を type(A, <_A) = ρ, type(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) の特定の取り方によらず一定である。そこで type(A ∪ B, <_A ⊕ <_B) を ρ と σ の和といい、これを ρ + σ で表す。直観的には、ρ + σ というのは (A, <_A) の後ろに (B, <_B) を並べてできる全順序集合の順序型である。

積

ρ, σ を順序型とする。 全順序集合 (A, <_A), (B, <_B) を type(A, <_A) = ρ, type(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) の特定の取り方によらず一定である。そこで type(A × B, <_A ⊗ <_B) を ρ と σ の積といい、これを ρ · σ で表す。

順序型の和と積について次が成り立つ：

1. (ρ + σ) + τ = ρ + (σ + τ) 。
2. (ρ · σ) · τ = ρ · (σ · τ) 。
3. ρ + 0 = 0 + ρ = ρ 。
4. ρ · 1 = 1 · ρ = ρ 。
5. ρ · 0 = 0 · ρ = 0 。
6. ρ · (σ + τ) = (ρ · σ) + (ρ · τ) 。
7. 任意の順序数 α , β に対して、α + β = α + β かつ α · β = α · β 。 したがって整列順序型同士の和、積は整列順序型である。