整列順序

整列集合（せいれつしゅうごう、英: well­ordered set）、または整列順序付けられた集合（せいれつじゅんじょづけられたしゅうごう）とは、数学における概念の1つで、整列順序を備えた集合のことをいう。ここで、集合 S 上の整列順序関係 (well­order) とは、S 上の全順序関係 "≤" であって、S の空でない任意の部分集合が必ず ≤ に関する最小元をもつものをいう。あるいは同じことだが、整列順序とは整礎な全順序関係のことである。整列集合 (S, ≤) を慣例に従ってしばしば単純に S で表す。

導入

整列集合 X の任意の元 s は、それが X の最大元でない限り、ただ一つの後者（successor; 後継、次の元、直後の元）を持つ。これはつまり、s よりも大きな X の元全体の成す部分集合における最小元として s の後者が決まるということである。また、整列集合 X の中で上に有界な任意の部分集合は（その上界全体の成す X の部分集合に最小元がとれるから）必ず上限を持つ。あるいは整列集合 X には、前者（predecessor; 直前の元）を持たない元が必ず存在する（それはもちろん、X 全体における最小元である）。

集合に整列順序が与えられれば、そこでは集合の全ての元に対する命題の超限帰納法を用いた証明を考えることができる。

自然数全体の成す集合 N が通常の大小関係 "<" に関して整列集合となるという事実は、一般にと呼ばれる。

（選択公理に同値な）整列可能定理は、任意の集合が整列順序付け可能であることを主張するものである。整列可能定理はまたツォルンの補題とも同値である。

順序数

詳細は「順序数」を参照

任意の整列集合は、その整列集合の順序型と呼ばれるただ一つの順序数にである。順序集合の各元の位置は順序集合によっても与えられる。有限集合の場合、数え上げという基本的な操作によって対象の一つ一つに（何番目の元であるかを意味する）順序数を割り当てることで、特定の対象の順序数を求めることができ、あるいは特定の順序数をもつ対象を求めることもできる。有限集合ではその大きさ、つまりその元の個数を意味する基数と、その順序型である順序数とは一致すると考えることができる。これは、日常的な意味での数え上げは 1 から始めると思うが、そうすると有限集合の各対象に順番に順序数を振っていって最後の元となる対象に振られる順序数はその集合の基数になっているという意味である。

実際にはここでいう順序数は、順序同型にしたがって定義される厳密な意味での順序数よりも 1 だけ大きいことに注意すべきである。厳密な意味での順序数はその対象よりも前にある対象の数に等しい（あるいはこれは 0 から数え始めることに対応する）。ゆえに有限な n に対して、整列集合の「n-番目の元」というとき、その文脈では 0 から数え始めたか 1 から数え始めたかは明らかである必要がある。β が超限順序数（無限順序数）であるときも「β-番目の元」というような書き方をすることがあり、この場合典型的には 0 から数える。

無限集合についても、その順序型はそれに属する基数を一意的に決定するが、逆は成り立たず、同じ基数をもつ整列集合で相異なる順序型を持つものが無数に存在しうる。たとえ可算無限集合だとしても、その集合の順序型として可能なものの数は非可算である。

例と反例

自然数の全体 N

（0 を含む）自然数全体の成す集合 N は通常の大小関係 ≤ が整列順序を与える。この整列集合の順序型は ω で表される。さらに、0 でない任意の自然数は唯一の直前元を持つ。

N における別な整列順序としては、例えば、どの偶数もどんな奇数よりも小さいものとし、偶数同士あるいは奇数同士では通常の大小関係を適用することで得られる順序

0, 2, 4, 6, 8, …, 1, 3, 5, 7, 9, …

が挙げられる。この順序に関する整列集合の順序型は ω + ω である。任意の元が直後の元を持つ（したがって最大元は存在しない）が、直前の元を持たない元が 0 と 1 の二つ存在する。

整数の全体 Z

自然数の全体に通常の大小関係を考えたものとは異なり、整数全体の成す集合 Z に通常の大小関係 ≤ を考えたものは整列集合ではない。たとえば、負の整数全体の成す集合には最小元が存在しない。

たとえば、次のような二項関係 R を考えれば、Z を整列集合にすることができる。

ふたつの整数 x, y に対して、xRy となるための必要十分条件は

1. x = 0;
2. x が正で y が負;
3. x, y がともに正で、x ≤ y;
4. x, y がともに負で |x| ≤ |y|

のうちのいずれか一つが成立することと定める。この関係 R は要するに

0, 1, 2, 3, 4, …, −1, −2, −3, …

となる順序として表すことができる。この整列順序 R に関する整列集合 Z の順序型は順序数 ω + ω に順序同型である。

Z の別な整列順序の例としては、x ≤_Zy ⇔ |x| < |y| または [|x| = |y| かつ x ≤ y] として定まる順序 ≤_Z が挙げられる。図示すれば

0, −1, 1, −2, 2, −3, 3, −4, 4, …

である。これは ω を順序型とする整列順序である。

実数からなる集合

正の実数全体の成す集合 R₊ に通常の大小関係 ≤ を考えたものは整列順序ではない。例えば開区間 (0, 1) は最小元を持たない。一方、選択公理を含む集合論の ZFC 公理系からは、実数全体の成す集合 R 上の整列順序が存在することが示せる。しかし、ZFC や、一般連続体仮説を加えた体系 ZFC+GCH においては、R 上の整列順序を定義する論理式は存在しない。ただし、R 上の定義可能な整列順序の存在は ZFC と(相対的に)無矛盾である。例えば は ZFC と(相対的に)無矛盾であり、ZFC+V=L ではある特定の論理式が R（実際には任意の集合）を整列順序付けることが従う。

R の非可算部分集合に通常の大小関係を入れたものが整列集合にならないことは、実数直線 R を互いに交わりを持たない区間の和に分割するとき、そのような区間の数が高々可算であることからわかる。可算無限集合ならば、通常の大小関係 ≤ が整列順序となることも、ならないこともありうる。整列順序となる例としては次のようなものが挙げられる。

• 集合 {−2⁻ⁿ  |  0 ≤ n < ω} は ω を順序型に持つ。
• 集合 {−2⁻ⁿ − 2^−m−n  |  0 ≤ m, n < ω} は順序型 ω² を持つ。一つ前の例に挙げた集合は、この集合に集積点の集合として含まれる。実数全体の成す集合 R の中では（通常の位相でも順序位相でも）0 も集積点に含まれる（これは集積点全体の成すの集合の集積点にもなっている）。
• 集合 {−2⁻ⁿ  |  0 ≤ n < ω} ∪ {1} は順序型 ω + 1 である。この集合にを考えれば、1 は集積点であるが、R に通常の位相（順序位相でも同じことだが）を入れても 1 は集積点にはならない。

同値な定式化

順序集合 X が全順序集合である場合には、以下の条件はどれも互いに同値である。

1. X は整列集合である。つまり、空でない任意の部分集合が最小元を持つ。
2. X の全体で超限帰納法が有効である。
3. X の元からなる任意の狭義単調減少列は必ず有限な長さで停止する（ただし、従属選択公理を仮定する）。

順序位相

任意の整列集合はを与えて位相空間にすることができる。順序位相に関して、この位相空間の元は次の二種類に分けることができる。

• 孤立点: 最小元や直前の元を持つ元などはこちらの種類の点になる。
• 集積点: 有限整列集合ではこの種類の元は存在できない。また、無限整列集合は集積点を持つことも持たないこともある。集積点を持たない無限整列集合（たとえば N）は順序型 ω を持つ。

また、この位相空間の部分集合については以下のように区別できる。

• 最大元を持つ部分集合（つまり、それ自身で有界な集合）。このような部分集合の最大元は、全体集合の孤立点となる場合も集積点となる場合もある。後者の場合に、それがその部分集合の集積点であるかどうかは場合による。
• それ自身は有界ではないが、全体集合の中では有界な部分集合。このような部分集合は最大元を持たないが、部分集合に属さない上限を持つ。この部分集合が空でないならば、この上限はこの部分集合の集積点であり、したがって全体集合の集積点でもある。一方、空集合の場合は上限は全体集合における最小元である。
• 全体集合においても有界でない部分集合。

部分集合が (cofinal) であるための必要十分条件は、それが全体集合の中で有界でないか、それが全体集合の中でも最大元となるような最大元をもつことである。

位相空間としての整列集合が、第一可算空間となるための必要十分条件は、それが ω₁ 以下の順序数を順序型に持つことである。これはつまり、その集合が可算であるか、または最小の非可算順序型を持つということを言っている。

関連項目

• 整列可能定理
• 順序数
• （英語版）
• （英語版）
• 有向集合

参考文献

1. ^ S. Feferman: "Some Applications of the Notions of Forcing and Generic Sets", Fundamenta Mathematicae, 56 (1964) 325-345

外部リンク

• well-order in nLab
• well ordered set - PlanetMath.（英語）
• Definition:Well-Ordered Set at ProofWiki
• Efimov, B.A.; Fofanova, T.S. (2001), “Well-ordered set”, in Hazewinkel, Michiel, Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=Well-ordered_set