|
|
1行目: |
1行目: |
− | {{Otheruses|数学的な観点からの順序数|言語学的な観点での順序数|序数詞}}
| |
− | [[数学]]でいう'''順序数'''(じゅんじょすう、{{lang-en-short|''ordinal number''}})とは、[[整列集合]]同士の"長さ"を比較するために、[[自然数]]<ref>本項目では、各自然数が自分自身より小さな自然数全体の集合と等しくなるような仕方で自然数が定義されているものとする。例えば、0 = ∅ , 1 = { 0 } , 2 = { 0, 1 } である。</ref>を拡張させた概念である。
| |
| | | |
− | == 定義 ==
| + | '''順序数'''(じゅんじょすう、{{lang-en-short|''ordinal number''}}) |
− | 整列集合 (''A'', <) に対して、''A'' を[[写像|定義域]]とする[[写像|関数]] ''G'' <small><sub>A,<</sub></small>を[[超限帰納法]]によって
| |
− | : ''G<small><sub>A,<</sub></small>''(''a'') = { ''G<small><sub>A,<</sub></small>''(''x'') | ''x'' < ''a'' }
| |
| | | |
− | と定義したとき、''G<small><sub>A,<</sub></small>'' の[[写像|値域]] ran(''G<small><sub>A,<</sub></small>'') を''' (''A'', <) の順序数'''といい、これを ord(''A'', <) で表す。ある整列集合の順序数であるような[[集合]]を'''順序数'''と呼ぶ<ref>順序数は本来、上で述べた定義とは異なる仕方で定義されていた。その定義とは、順序集合全体の集まりを「同型である」という "同値関係" によって類別したとき、順序集合 (''A'', <) の "同値類" を (''A'', <) の'''順序型'''(order type)と呼び、特に整列集合の順序型を順序数と呼ぶというものである。ところが現代の標準的な集合論においては、''A'' が空集合でない限り (''A'', <) と同型な順序集合全体の集合といったものは存在しないことが示される。したがって、このような順序数の定義の仕方は正当な方法であるとは認められない。これを克服するために考えられたのが上で述べた定義であり、現在は上の定義(あるいはそれと同値な定義)が広く用いられている。だが、順序型というアイデア自体が排除されたわけではない。順序数を上で述べたような仕方で定義した後、それを用いることによって順序型を正当な方法で定義できるということが知られている。ただし、整列集合の順序型と順序数は別のものになる。詳細は「[[順序型]]」を参照。</ref>。
| + | ものの個数を表す集合数に対し,並んでいる順序を表す数。序数ともいう。一般には,整列集合の順序型を順序数ということで,無限順序数を含む議論が展開できる。たとえば,表の右側の列が順序数である。整列集合を <i>M</i>,その順序型を○(<i>M</i>)で示す。第I型の順序型すなわち順序数は自然数であって有限順序数といわれ,第II型の順序数は有限順序数に続いてすぐあとにくるもので,超限順序数といわれる。可算無限集合に対応するこのような超限順序数を初めて考えたのは[[ゲオルク・カントル]]である。 |
− | | |
− | === 例 ===
| |
− | <<sub>ω</sub> は自然数の通常の大小関係(を各集合に制限したもの)を表すものとすると、
| |
− | : ord(∅, <<sub>ω</sub>) = ∅ = 0,
| |
− | : ord({ 2 }, <<sub>ω</sub>) = { ∅ } = { 0 } = 1,
| |
− | : ord({ 2, 3 }, <<sub>ω</sub>) = { ∅, { ∅ } } = { 0, 1 } = 2,
| |
− | : ord({ 2, 3, 5 }, <<sub>ω</sub>) = { ∅, { ∅ }, { ∅, { ∅ } } } = { 0, 1, 2 } = 3 。
| |
− | | |
− | この例から推測されるように、一般に有限の整列集合 (''A'', <) に対して ord(''A'', <) は ''A'' の要素の個数に等しい。特に、任意の自然数 ''n'' に対して ord(''n'', <<sub>ω</sub>) = ''n'' が成り立つので、自然数はすべて順序数である。
| |
− | | |
− | 順序数に関して次が成り立つ:
| |
− | # 整列集合 (''A'', <<sub>''A''</sub>) と整列集合 (''B'', <<sub>B</sub>) が[[同型]]のとき、またそのときに限り ord(''A'', <<sub>''A''</sub>) = ord(''B'', <<sub>B</sub>)。
| |
− | # (''A'', <) が有限整列集合のとき、ord(''A'', <) は ''A'' の要素の個数に等しい。
| |
− | # 整列集合 (''A'', <) の順序数を α とし、∈<sub>α</sub> を α 上の所属関係とすると、(α, ∈<sub>α</sub>) は (''A'', <) と同型な整列集合である。
| |
− | # α が順序数であることと、α が ∈ によって整列された[[推移的集合]]であることは同値である。
| |
− | # α が順序数のとき、α の要素もすべて順序数である。
| |
− | | |
− | 自然数全体の集合 ω は ∈ によって整列された推移的な集合であるから、上の事実 4. より ω は順序数である。
| |
− | | |
− | == 順序数の大小関係 ==
| |
− | 任意の順序数 α, β, γ に対して次が成り立つことが示される:
| |
− | : α ∉ α,
| |
− | : α ∈ β かつ β ∈ γ ⇒ α ∈ γ,
| |
− | : α ∈ β または α = β または β ∈ α 。
| |
− | そこで、α ∈ β のとき β は α より大きいといい、α < β と書く。この定義と順序数の要素はまた順序数であるという性質から、すべての順序数は自分自身より小さな順序数全体の集合と等しいと言うことができる。ω より小さな順序数(すなわち自然数)を'''有限順序数'''と呼び、ω 以上の(すなわち ω と等しいか ω より大きい)順序数を'''超限順序数'''と呼ぶ。順序数の大小関係に関して次が成り立つ:
| |
− | # 整列集合 (''A'', <<sub>''A''</sub>) が整列集合 (''B'', <<sub>B</sub>) のある始切片と同型のとき、またそのときに限り ord(''A'', <<sub>''A''</sub>) < ord(''B'', <<sub>B</sub>)。
| |
− | # 有限順序数の範囲では、上で定義された大小関係は通常の大小関係と一致する。
| |
− | # α が順序数のとき、''S''(α) := α ∪ { α } は α より大きな順序数のうちで最小のものである。''S''(α) を '''α の後続者'''(successor of α)と呼ぶ。
| |
− | # ''O'' が順序数からなる集合のとき、<math>\bigcup</math> ''O'' もまた順序数であり、''O'' の[[最小上界]]となっている。そこで、<math>\bigcup</math> ''O'' を sup(''O'') とも書く。
| |
− | # 順序数からなる空でない集合には必ず最小元が存在する。
| |
− | | |
− | 順序数の並び方を次のように図示することができる:
| |
− | : 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 公理系|ZF]]で同値である。
| |
− | * x は順序数である。
| |
− | * x は[[推移的集合]]であり帰属関係 ∈ に関する[[整列集合]]である。 ([[ジョン・フォン・ノイマン]]の定義)<ref name="von Neumann1923pp199-208">{{Harvnb|von Neumann|1923}}</ref><ref>{{harv|Levy|1979|page=52}} 著者はこの案をツェルメロの1916年の未公刊の仕事とノイマンの1920年代の数編の論文に帰している。</ref>
| |
− | * 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'', <<sub>''A''</sub>), (''B'', <<sub>''B''</sub>) を ord(''A'', <<sub>''A''</sub>) = α, ord(''B'', <<sub>''B''</sub>) = β, ''A'' ∩ ''B'' = ∅ をみたすように取り、''A'' ∪ ''B'' 上の関係 <<sub>''A''</sub> ⊕ <<sub>''B''</sub> を、
| |
− | | |
− | : ''x'' (<<sub>''A''</sub> ⊕ <<sub>''B''</sub>) ''y'' ⇔ ''x'' <<sub>''A''</sub> ''y'' または ''x'' <<sub>''B''</sub> ''y'' または〈''x'', ''y'' 〉 ∈ ''A'' × ''B''
| |
| | | |
− | によって定義すれば、(''A'' ∪ ''B'', <<sub>''A''</sub> ⊕ <<sub>''B''</sub>) は整列集合であり、その順序数は (''A'', <<sub>''A''</sub>), (''B'', <<sub>''B''</sub>) の特定の取り方によらず一定である。そこで ord(''A'' ∪ ''B'', <<sub>''A''</sub> ⊕ <<sub>''B''</sub>) を α と β の'''和'''といい、これを α + β で表す。直観的には、α + β というのは α の後ろに β を並べてできる整列集合の順序数である。
| + | {{テンプレート:20180815sk}} |
− | | |
− | 順序数の和について次が成り立つ:
| |
− | # α, β が有限順序数ならば、和 α + β は自然数の間の通常の和と一致する。
| |
− | # (α + β) + γ = α + (β + γ) 。
| |
− | # α + 0 = 0 + α = α 。
| |
− | # α + ''S''(β) = ''S''(α + β) 。
| |
− | # γ が極限順序数のとき、α + γ = sup({ α + β | β < γ }) 。
| |
− | # β < γ ⇔ α + β < α + γ 。
| |
− | # β ≤ γ ⇒ β + α ≤ γ + α 。
| |
− | # 順序数の和は一般には'''可換でない'''。例えば、1 + ω = ω ≠ ω + 1 である。
| |
− | # α ≤ β ならば α + γ = β をみたす γ がただ一つ存在する。
| |
− | | |
− | === 積 ===
| |
− | α, β を順序数とする。
| |
− | 整列集合 (''A'', <<sub>''A''</sub>), (''B'', <<sub>''B''</sub>) を ord(''A'', <<sub>''A''</sub>) = α, ord(''B'', <<sub>''B''</sub>) = β をみたすように取り、''A'' × ''B'' 上の関係 <<sub>''A''</sub> ⊗ <<sub>''B''</sub> を、
| |
− | | |
− | : 〈 ''x''<sub>1</sub>, ''y''<sub>1</sub> 〉 (<<sub>''A''</sub> ⊗ <<sub>''B''</sub>) 〈 ''x''<sub>2</sub>, ''y''<sub>2</sub> 〉 ⇔ ''y''<sub>1</sub> <<sub>''B''</sub> ''y''<sub>2</sub> または (''y''<sub>1</sub> = ''y''<sub>2</sub> かつ ''x''<sub>1</sub> <<sub>''A''</sub> ''x''<sub>2</sub>)
| |
− | | |
− | によって定義すれば、(''A'' × ''B'', <<sub>''A''</sub> ⊗ <<sub>''B''</sub>) は整列集合であり、その順序数は (''A'', <<sub>''A''</sub>), (''B'', <<sub>''B''</sub>) の特定の取り方によらず一定である。そこで ord(''A'' × ''B'', <<sub>''A''</sub> ⊗ <<sub>''B''</sub>) を α と β の'''積'''といい、これを α · β で表す。直観的には、α · β というのは α を β 個並べてできる整列集合の順序数である。
| |
− | | |
− | 順序数の積について次が成り立つ:
| |
− | # α, β が有限順序数ならば、積 α · β は自然数の通常の積に一致する。
| |
− | # (α · β) · γ = α · (β · γ) 。
| |
− | # α · 0 = 0 · α = 0 。
| |
− | # α · ''S''(β) = (α · β) + α 。
| |
− | # γ が極限順序数のとき、α · γ = sup({ α · β | β < γ }) 。
| |
− | # α · 1 = 1 · α = α 。
| |
− | # 0 < α のとき、β < γ ⇔ α · β < α · γ 。
| |
− | # β ≤ γ ⇒ β · α ≤ γ · α 。
| |
− | # 順序数の積は一般には'''可換でない'''。例えば、2 · ω = ω ≠ ω · 2 である。
| |
− | # α · (β + γ) = (α · β) + (α · γ) 。
| |
− | # (β + γ) · α = (β · α) + (γ · α) は一般には成り立たない。
| |
− | # 任意の順序数 α と 0 でない順序数 δ に対して、α = (δ · β) + γ かつ γ < δ をみたす順序数の組 β, γ がただ一組存在する。
| |
− | | |
− | === 冪 ===
| |
− | α, β を順序数とする。
| |
− | 整列集合 (''A'', <<sub>''A''</sub>), (''B'', <<sub>''B''</sub>) を ord(''A'', <<sub>''A''</sub>) = α, ord(''B'', <<sub>''B''</sub>) = β をみたすように取り、''F''(''A'', ''B'') = { ''f'' ∈ <sup>''B''</sup>''A'' | { ''b'' ∈ ''B'' | ''f''(''b'') ≠ min(''A'') } は有限集合 } 上の関係 <<sub>''A''</sub> △ <<sub>''B''</sub> を、
| |
− | | |
− | : ''f'' (<<sub>''A''</sub> △ <<sub>''B''</sub>) ''g'' ⇔ ''f'' ≠ ''g'' かつ、 ''f''(''b'') ≠ ''g''(''b'') をみたす最大の ''b'' ∈ ''B'' に対して ''f''(''b'') <<sub>''A''</sub> ''g''(''b'') | |
− | | |
− | によって定義すれば、(''F''(''A'', ''B''), <<sub>''A''</sub> △ <<sub>''B''</sub>) は整列集合であり、その順序数は (''A'', <<sub>''A''</sub>), (''B'', <<sub>''B''</sub>) の特定の取り方によらず一定である。そこで ord(''F''(''A'', ''B''), <<sub>''A''</sub> △ <<sub>''B''</sub>) を '''α の β 乗'''といい、これを α<sup>β</sup> で表す。
| |
− | | |
− | 順序数の冪について次が成り立つ:
| |
− | # α, β が有限順序数ならば、冪 α<sup>β</sup> は自然数の通常の冪に一致する。
| |
− | # 0<sup>0</sup> = 1 。
| |
− | # 0 < β のとき、0<sup>β</sup> = 0 。
| |
− | # α<sup>0</sup> = 1 。
| |
− | # α<sup>''S''(β)</sup> = (α<sup>β</sup>) · α 。
| |
− | # 0 < α で、γ が極限順序数のとき、α<sup>γ</sup> = sup({ α<sup>β</sup> | β < γ }) 。
| |
− | # 1 < α のとき、β < γ ⇔ α<sup>β</sup> < α<sup>γ</sup> 。
| |
− | # β ≤ γ ⇒ β<sup>α</sup> ≤ γ<sup>α</sup> 。
| |
− | # α<sup>β + γ</sup> = (α<sup>β</sup>) · (α<sup>γ</sup>) 。
| |
− | # (α<sup>β</sup>)<sup>γ</sup> = α<sup>β · γ</sup> 。
| |
− | # (β · γ)<sup>α</sup> = (β<sup>α</sup>) · (γ<sup>α</sup>) は一般には成り立たない。
| |
− | | |
− | == 集合の濃度と基数 ==
| |
− | {{main|濃度 (数学)}}
| |
− | | |
− | 集合 ''A'' から集合 ''B'' への[[全単射]]が存在するとき、''A'' と ''B'' は'''同数'''(equinumerous)であるといい、''A'' ≈ ''B'' で表す。
| |
− | [[選択公理]]を仮定すれば、[[順序集合|整列定理]]により任意の集合 ''A'' に対して ''A'' と同数であるような順序数が存在することが言える。そこで、集合 ''A'' と同数であるような順序数の中で最小のものを''' ''A'' の濃度'''(cardinality of ''A'')といい、これを |''A''| あるいは card(''A'') で表す。ある集合 ''A'' に対して α = |''A''| である順序数 α を'''基数'''(cardinal number)と呼ぶ。集合の濃度に関して次が成り立つ:
| |
− | # |''A''| = |''B''| ⇔ ''A'' ≈ ''B'' 。
| |
− | # ''A'' が有限集合のとき、|''A''| は ''A'' の要素の個数に等しい。
| |
− | | |
− | 基数に対しても、上で定義した順序数の演算とは別に和、積、冪を定義することができる。
| |
− | | |
− | == 注釈 ==
| |
− | {{Reflist}}
| |
− | | |
− | == 関連項目 ==
| |
− | *[[集合]]
| |
− | *[[集合論]]
| |
− | *[[公理的集合論]]
| |
− | *[[ブラリ=フォルティのパラドックス]]
| |
− | *[[濃度 (数学)|濃度]]
| |
− | *[[共終数]]
| |
− | *[[整礎的集合]]
| |
− | *[[構成可能集合]]
| |
− | *[[ヴェブレン階層]]
| |
− | | |
− | {{集合論}}
| |
| {{DEFAULTSORT:しゆんしよすう}} | | {{DEFAULTSORT:しゆんしよすう}} |
| [[Category:順序構造]] | | [[Category:順序構造]] |