順序型

数学でいう順序型（じゅんじょがた、order type）とは、順序集合（特に全順序集合や整列集合）同士の構造を比較するために、同型という観点からその構造のみに注目することによって得られる概念である一般に、任意の集合上の二項関係に対しても同様に順序型を定義することができる。。

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

前述の素朴な説明では (※) の性質を満たすような「型」の正体が不明であるため、集合論的に順序型 type(A, <A) を厳密に定義する必要がある。このとき、(A, <A) と同型な順序集合全体の集合を type(A, <A) と定義するアプローチが考えられるが、A が空集合でない限り、同型な順序集合の集まりは大きすぎて真のクラスとなり、（集合論の公理の枠組みにおいては）集合として扱うことができない。

この問題を回避し、同値類を適切な集合として定義するために、同型な順序集合のうちで階数が最小のものだけを集めて集合とする手法（スコットのトリック、Scott's trick）が用いられる。すなわち、順序型は次のように定義される。 順序集合 (A, <A) に対して type(A, <A) とは、(A, <A) と同型な順序集合のうちで階数が最小のもの全体の集合である。 この type(A, <A) を (A, <A) の順序型と呼び、ある順序集合の順序型であるものを単に順序型と呼ぶ。

全順序集合 (A, <A) と同型な順序集合で階数が最小であるものの階数を α とすれば、type(A, <A) の要素はすべて Vα + 1 階数と Vα については「整礎的集合」を参照。に属するので、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 を、

<x1, y1> (<A ⊗ <B) <x2, y2> 　⇔　 y1 <B y2 または （y1 = y2 かつ x1 <A x2）

によって定義すれば、(A × B, <A ⊗ <B) は全順序集合であり、その順序型は (A, <A), (B, <B) の特定の取り方によらず一定である。そこで type(A × B, <A ⊗ <B) を ρ と σ の積といい、これを ρ · σ で表す。

順序型の和と積について次が成り立つ： (ρ + σ) + τ = ρ + (σ + τ) 。 (ρ · σ) · τ = ρ · (σ · τ) 。 ρ + 0 = 0 + ρ = ρ 。 ρ · 1 = 1 · ρ = ρ 。 ρ · 0 = 0 · ρ = 0 。 ρ · (σ + τ) = (ρ · σ) + (ρ · τ) 。 任意の順序数 α , β に対して、α + β = α + β かつ α · β = α · β 。 したがって整列順序型同士の和、積は整列順序型である。

注

参考文献

関連項目 集合 集合論 公理的集合論 順序集合 順序数 正則基数