秩序ある

数学において、集合S上の整列(または整列させる、整列させる関係) は、 S上の全順序付けであり、Sの空でないすべての部分集合はこの順序付けの最小元を持つという性質を持つ。集合Sとその順序付けは、整列集合と呼ばれる。一部の学術論文や教科書では、これらの用語は、代わりにwellorder、wellordered、wellorderingまたはwell order、well ordered、well orderと書かれている。

空でないすべての整列集合には最小元がある。整列集合のすべての要素s は、最大元 の可能性を除いて、一意の後続元 (次の要素)、つまりsより大きいすべての要素の部分集合の最小元を持つ。最小元のほかに、先行元を持たない要素が存在する可能性がある (例については、以下の § 自然数 を参照)。整列集合Sには、上限を持つすべての部分集合Tに対して最小の上限、つまりS内のTのすべての上限の部分集合の最小元が含まれる。

≤ が非厳密な整列順序である場合、 < は厳密な整列順序です。関係が厳密な整列順序となるのは、それが整列した 厳密な全順序である場合のみです。厳密な整列順序と非厳密な整列順序の区別は、簡単に相互変換できるため、しばしば無視されます。

すべての整列集合は、整列集合の順序型と呼ばれる一意の順序数と一意に順序同型です。選択公理に相当する整列定理は、すべての集合が整列可能であることを述べています。集合が整列されている場合（または単に整列関係を許容する場合でも）、超限帰納法の証明手法を使用して、与えられたステートメントが集合のすべての要素に対して真であることを証明できます。

自然数が通常の「より小さい」関係によって整列しているという観察は、一般に「整列原理（自然数の場合）」と呼ばれます。

すべての整列集合は、整列集合の順序型と呼ばれる一意の順序数と一意に同型です。順序付き集合内の各要素の位置も順序数で与えられます。有限集合の場合、 を数えて特定のオブジェクトの順序数を見つける、または特定の順序数を持つオブジェクトを見つけるという基本的な操作は、オブジェクトに順序数を1つずつ割り当てることに対応します。有限集合のサイズ（要素数、基数）は、順序型に等しくなります。^[1]日常的な意味での数え上げは通常1から始まるため、各オブジェクトに、そのオブジェクトを最後の要素とする初期セグメントのサイズを割り当てます。これらの数は、同型順序に従った正式な順序数より1大きいことに注意してください。これは、これらが前のオブジェクトの数（0から数えることに相当）に等しいためです。したがって、有限のnの場合、整列したセットの「 n番目の要素」という表現では、これが 0 から数えるのか 1 から数えるのかを知るためにコンテキストが必要です。 β が無限の順序数になることもある「 β番目の要素」という表現では、通常は 0 から数えます。

無限集合の場合、順序の種類によって濃度が決まりますが、その逆は当てはまりません。特定の無限濃度の集合には、さまざまな順序の種類が存在します (例については、以下の § 自然数 を参照してください)。可算無限集合の場合、可能な順序の種類は非可算です。

自然数の標準的な順序 ≤ は整列順序であり、すべての非ゼロの自然数には一意の先行数があるという追加の特性があります。

自然数の別の適切な順序付けは、すべての偶数がすべての奇数より小さいと定義することによって与えられ、通常の順序付けは偶数と奇数の範囲内で適用されます。

${\displaystyle {\begin{matrix}0&2&4&6&8&\dots &1&3&5&7&9&\dots \end{matrix}}}$

これは順序型 ω + ωの整然とした集合です。すべての要素には後続の要素があります (最大の要素はありません)。2 つの要素 0 と 1 には先行要素がありません。

自然数の標準的な順序 ≤ とは異なり、整数の標準的な順序 ≤ は、たとえば、負の整数の集合に最小の要素が含まれていないため、適切な順序ではありません。

次の二項関係 R は整数の順序付けの例です: x R y は 、次の条件のいずれ かが満たされる場合に限ります:

1. x = 0
2. xは正で、yは負である
3. xとyは両方とも正であり、x ≤ y
4. xとy は両方とも負であり、| x | ≤ | y |

この関係R は次のように視覚化できます。

${\displaystyle {\begin{matrix}0&1&2&3&4&\dots &-1&-2&-3&\dots \end{matrix}}}$

R は順序数 ω + ωと同型です。

整数をうまく順序付けるための別の関係は、次の定義である：${\displaystyle x\leq _{z}y}$

${\displaystyle |x|<|y|\qquad {\text{or}}\qquad |x|=|y|{\text{ and }}x\leq y.}$

この井戸の順序は次のように視覚化できます。

${\displaystyle {\begin{matrix}0&-1&1&-2&2&-3&3&-4&4&\dots \end{matrix}}}$

これは順序型 ωを持ちます。

任意の実数区間の標準的な順序 ≤ は整列順序ではありません。これは、たとえば、開区間 ⁠ ⁠${\displaystyle (0,1)\subseteq [0,1]}$には最小元が含まれていないためです。集合論のZFC公理 (選択公理を含む) から、実数の整列順序があることを示すことができます。また、Wacław Sierpiński は、ZF + GCH (一般化連続体仮説) が選択公理を意味し、したがって実数の整列順序を意味することを証明しました。それでも、ZFC+GCH 公理だけでは、(式によって) 定義可能な実数の整列順序の存在を証明するのに十分ではないことを示すことは可能です。^[2]ただし、実数の定義可能な整列順序が存在することは ZFC と一致しています。たとえば、V=Lは ZFC と一致しており、ZFC+V=L から、特定の式が実数、または実際に任意の集合を整列することが分かります。

標準の順序 ≤ を持つ実数の非可算部分集合は整列順序にはなり得ません。Xが⁠ ⁠の${\displaystyle \mathbb {R} }$≤で整列した部分集合であるとします。 X内の各xに対して、s ( x ) をX上の≤順序におけるxの後続要素とします( x がXの最後の要素でない限り)。の要素が空でなく互いに素な区間であるとします。各区間には少なくとも 1 つの有理数が含まれるため、Aから⁠ ⁠への単射関数が存在します。 XからAへの単射があります( Xの最後の要素は例外で、後でゼロにマッピングされる可能性があります)。 また、 ⁠ ⁠から自然数への単射があることはよく知られています(ゼロにならないように選択できます)。 したがって、 Xから自然数への単射があり、これはXが可算であることを意味します。 一方、実数の可算無限部分集合は、標準の≤ を持つ整列順序である場合とそうでない場合があります。 たとえば、 ${\displaystyle A=\{(x,s(x))\,|\,x\in X\}}$${\displaystyle \mathbb {Q} .}$${\displaystyle \mathbb {Q} }$

• 自然数は、標準的な順序≤の下で整列しています。
• この集合には最小の要素がないので、標準的な順序付け≤では整列順序ではありません。${\displaystyle \{1/n\,|\,n=1,2,3,\dots \}}$

井戸の注文の例:

• 数値の集合は順序型ω を持ちます。${\displaystyle \{-2^{-n}\,|\,0\leq n<\omega \}}$
• 数の集合は順序型ω ²を持ちます。前の集合は集合内の極限点の集合です。実数の集合内では、通常の位相でも順序位相でも、0 も集合の極限点です。また、極限点の集合の極限点でもあります。${\displaystyle \{-2^{-n}-2^{-m-n}\,|\,0\leq m,n<\omega \}}$
• 数の集合は順序型ω + 1を持ちます。この集合の順序位相では、実数の通常の位相では唯一の極限点 0 から離れているにもかかわらず、1 は集合の極限点になります。${\displaystyle \{-2^{-n}\,|\,0\leq n<\omega \}\cup \{1\}}$

集合が全順序である場合、以下の集合は互いに同値です。

1. 集合は整然と並べられています。つまり、空でないすべての部分集合には最小の要素が存在します。
2. 超限帰納法は順序付けられた集合全体に対して機能します。
3. 集合の要素の厳密に減少するシーケンスはすべて、有限個のステップの後で終了する必要があります (従属選択公理を仮定)。
4. すべてのサブ順序は初期セグメントと同型です。

あらゆる整列集合は、順序位相を与えることによって位相空間にすることができます。

このトポロジに関しては、次の 2 種類の要素が考えられます。

• 孤立点- これらは最小値と先行要素を持つ要素です。
• 極限点— このタイプは有限集合には現れず、無限集合にも現れる場合と現れない場合があります。極限点のない無限集合は、順序タイプ ω の集合、たとえば自然数です 。${\displaystyle \mathbb {N} .}$

サブセットについては、次のことを区別できます。

• 最大値を持つ部分集合（つまり、それ自体で境界が定められている部分集合）。これは孤立点または集合全体の極限点である可能性があります。後者の場合、部分集合の極限点である場合とそうでない場合があります。
• 部分集合は、それ自体では有界ではないが、集合全体では有界である。これらの部分集合には最大値はないが、部分集合の外側に上限がある。部分集合が空でない場合、この上限は部分集合の極限点であり、したがって集合全体の極限点でもある。部分集合が空の場合、この上限は集合全体の最小値である。
• 集合全体の中で制限のない部分集合。

部分集合が全体集合において共終的となるのは、部分集合が全体集合において無限であるか、または部分集合の最大値が全体集合の最大値でもある場合に限られます。

位相空間としての整列集合は、その順序型が ω ₁ (オメガワン)以下である場合に限り、つまり、その集合が可算であるか、最小の不可算な順序型を持つ場合に限り、第一可算空間となります。

• ツリー（集合論）、一般化
• 序数
• 根拠のあるセット
• まあ部分的な順序
• プレウェルオーダー
• 監督セット