合計注文

数学において、全順序または線形順序は、任意の 2 つの要素が比較可能な部分順序です。つまり、全順序は、ある集合上の2 項関係 であり、内のすべてのおよびに対して以下を満たします。 ${\displaystyle \leq}$ ${\displaystyle X}$${\displaystyle a,b}$${\displaystyle c}$${\displaystyle X}$

1. ${\displaystyle a\leq a}$（再帰動詞）。
2. ならば（推移的）。${\displaystyle a\leq b}$${\displaystyle b\leq c}$${\displaystyle a\leq c}$
3. ならば（反対称）。​${\displaystyle a\leq b}$${\displaystyle b\leq a}$${\displaystyle a=b}$
4. ${\displaystyle a\leq b}$または（強く結合、以前は合計と呼ばれていました）。${\displaystyle b\leq a}$

反射性（1.）は連結性（4.）からすでに導かれるが、多くの著者は部分順序との親族関係を示すために、反射性を明示的に必要としている。^{[1]全順序は}単純順序、^[2] 連結順序、^[3]完全順序と も呼ばれる。^[4]

全順序を備えた集合は全順序集合である。^[5]単純順序集合^[2] 、線型順序集合^{[3] [5]}、ロセット^{[6] [7]}という用語も使用される。連鎖という用語は全順序集合^[5]の同義語として定義されることもあるが、一般的には与えられた半順序集合の全順序部分集合を指す。

与えられた半順序を全順序に拡張することを、その半順序の 線型拡張と呼びます。

集合 上の厳密な全順序とは、上の厳密な半順序であり、 内の任意の 2 つの異なる要素は比較可能です。つまり、厳密な全順序とは、内のすべてのおよびに対して以下を満たす、ある集合上の2 項関係です。 ${\displaystyle X}$${\displaystyle X}$ ${\displaystyle <}$ ${\displaystyle X}$${\displaystyle a,b}$${\displaystyle c}$${\displaystyle X}$

1. （非反射的）ではない。${\displaystyle a<a}$
2. そうでない場合（非対称）。${\displaystyle a<b}$${\displaystyle b<a}$
3. ならば（推移的）。${\displaystyle a<b}$${\displaystyle b<c}$${\displaystyle a<c}$
4. の場合、または(接続) です。${\displaystyle a\neq b}$${\displaystyle a<b}$${\displaystyle b<a}$

非対称性は推移性と非反射性から生じます。^[8]さらに、非反射性は非対称性から生じます。^[9]

限定のために、上で定義した全順序は非厳密順序と呼ばれることもあります。各（非厳密）全順序には、に関連付けられた厳密全順序と呼ばれる関連関係があり、これは 2 つの同等の方法で定義できます。 ${\displaystyle \leq}$${\displaystyle <}$${\displaystyle \leq}$

• ${\displaystyle a<b}$かつ（反射的還元）の場合。${\displaystyle a\leq b}$${\displaystyle a\neq b}$
• ${\displaystyle a<b}$そうでない場合（つまり、は の逆の補数です）。${\displaystyle b\leq a}$${\displaystyle <}$${\displaystyle \leq}$

逆に、厳密な全順序の反射閉包は（非厳密な）全順序です。 ${\displaystyle <}$

• 全順序集合Xの任意の部分集合は、 X上の順序の制限に対して全順序である。
• 空集合∅上の一意の順序は全順序です。
• 基数または順序数の任意の集合（より厳密に言えば、これらは整列順序です）。
• Xが任意の集合であり、fXから全順序集合への単射関数の場合、fはx 1 _≤ x 2_と設定することによってX上に全順序を誘導しますが、それはf ( x ₁ ) ≤ f ( x ₂ )の場合に限ります。
• 整列集合によってインデックス付けされた、全順序集合の族の直積上の辞書式順序は、それ自体が全順序です。
• 通常の「以下」(≤) または「以上」(≥) の関係で順序付けられた実数の集合は、完全に順序付けられています。したがって、自然数、整数、有理数などの実数の各サブセットは完全に順序付けられています。これらのそれぞれは、特定のプロパティを持つ全順序集合の唯一の (順序同型を除いて)「最初の例」であることが示されます (ここで、全順序Aは、 B がそのプロパティを持つときはいつでも、 AからBのサブセットへの順序同型がある場合、プロパティに対して初期です)。^{[10] [引用が必要]}
  • 自然数は、上限のない空でない初期の全順序集合を形成します。
  • 整数は、上限も下限もない、空でない初期の全順序集合を形成します。
  • 有理数は、実数に稠密な初期全順序集合を形成します。さらに、反射的縮約 < は、有理数上の稠密な順序です。
  • 実数は、順序位相（以下で定義）で接続された、初期の無制限の全順序集合を形成します。
• 順序体は定義により完全に順序付けられています。これには有理数と実数が含まれます。すべての順序体には、有理数と同型の順序部分体が含まれます。デデキント完全な順序体はどれも実数と同型です。
• 標準的な辞書の順序で並べられたアルファベットの文字、たとえばA < B < Cなどは、厳密な全順序です。

チェーンという用語は、全順序集合の同義語として定義されることもありますが、一般的には、誘導順序に対して全順序である半順序集合のサブセットを指すために使用されます。 ^{[1] [11]}通常、半順序集合は、包含によって順序付けられた特定の集合のサブセットの集合であり、この用語はチェーンの集合の特性を示すために使用されます。この用語の有用性は、集合のネストされたレベルの数が多いことからわかります。

全順序付き部分集合を指すために連鎖を使用する一般的な例としては、半順序付き集合X内のすべての連鎖がXに上限を持つ場合、Xには少なくとも 1 つの極大元が含まれると主張するツォルンの補題がある。^[12]ツォルンの補題は、X が部分集合の集合である場合によく使用され、この場合、上限は、X内の連鎖の元の和集合がXに含まれることを証明することによって得られる。これは、ベクトル空間にハメル基底があることや環に極大イデアルがあることを証明する場合に一般的に使用される方法である。

いくつかの文脈では、考慮される連鎖は、その通常の順序またはその逆の順序を持​​つ自然数と順序同型である。この場合、連鎖は単調なシーケンスと同一視でき、シーケンスが増加するか減少するかに応じて、昇順連鎖または降順連鎖と呼ばれる。^[13]

半順序集合は、すべての下降連鎖が最終的に安定する場合、下降連鎖条件を満たします。 ^[14]たとえば、順序が下降連鎖条件を満たす場合、順序は整列しています。同様に、昇順連鎖条件は、すべての昇順連鎖が最終的に安定することを意味します。たとえば、ネーター環は、そのイデアルが昇順連鎖条件を満たす 環です。

他の文脈では、有限集合である連鎖のみが考慮される。この場合、有限連鎖と呼ばれ、しばしば連鎖と短縮される。この場合、連鎖の長さは連鎖の連続する要素間の不等式（または集合包含）の数、つまり連鎖内の要素の数から1を引いた数である。^[15]したがって、単集合は長さ0の連鎖であり、順序付きペアは長さ1の連鎖である。空間の次元は、多くの場合、部分空間の連鎖の最大長として定義または特徴付けられる。たとえば、ベクトル空間の次元は線型部分空間の連鎖の最大長であり、可換環のクルル次元は素イデアルの連鎖の最大長である。

「チェーン」は、部分的に順序付けられた集合ではない構造の、完全に順序付けられたサブセットにも使用できます。例として、多項式の正規のチェーンが挙げられます。別の例としては、グラフ内のウォークの同義語として「チェーン」を使用することです。

完全順序集合を、特定の種類の格子、すなわち次のような格子 として定義することができる。

${\displaystyle \{a\vee b,a\wedge b\}=\{a,b\}}$すべてのa、bに対して。

このとき、 のときのみa ≤ b と書きます。したがって、全順序集合は分配格子です。 ${\displaystyle a=a\wedge b}$

単純な計数による議論により、空でない有限全順序集合 (したがってその空でない部分集合) には最小元があることが証明されます。したがって、すべての有限全順序は実際には整列順序です。直接証明するか、すべての整列順序が順序数と同型であることを観察することによって、すべての有限全順序が< で順序付けされた自然数の最初のセグメントと同型であることが示されます。言い換えると、 k個の要素を持つ集合の全順序は、最初のk 個の自然数との全単射を誘導します。したがって、有限全順序または順序タイプω の整列順序を、順序を尊重する方法 (0 または 1 から開始) で自然数 でインデックス付けするのが一般的です。

全順序集合は、半順序集合のカテゴリの完全なサブカテゴリを形成し、射は順序を尊重する写像、つまり、a ≤ bならばf ( a ) ≤ f ( b ) となるような写像fである。

2 つの順序を尊重する 2 つの全順序集合間の全単射 写像は、このカテゴリの 同型です。

任意の全順序集合Xに対して、開区間を定義することができる。

• ( a , b ) = { x | a < xかつx < b }、
• (−∞, b ) = { x | x < b }、
• ( a , ∞) = { x | a < x }であり、
• (−∞, ∞) = X .

これらの開区間を使用して、任意の順序付きセット上のトポロジ、つまり順序​​トポロジを定義できます。

集合に複数の順序が使用されている場合、特定の順序によって誘導される順序トポロジーについて言及します。たとえば、Nが自然数で、<がそれより小さく、> がそれより大きい場合、 <によって誘導されるN上の順序トポロジーと>によって誘導されるN上の順序トポロジーについて言及する場合があります(この場合、それらは偶然同一ですが、一般には同一ではありません)。

全秩序によって誘導される秩序トポロジーは遺伝的に正規であることが示される場合があります。

全順序集合は、上限 を持つすべての空でない部分集合に最小の上限がある場合に完全であると言われます。たとえば、実数の集合Rは完全ですが、有理数の集合Q は完全ではありません。言い換えると、完全性(「完全」であることと混同しないでください)のさまざまな概念は、制限には適用されません。たとえば、実数上の関係≤の特性は、 Rに上限を持つRの空でない部分集合S はすべて、 Rに最小の上限(上限とも呼ばれる) を持つということです。ただし、有理数の場合、この上限は必ずしも有理数ではないため、同じ特性は関係≤の有理数へ の制限には当てはまりません。

順序位相の特性と X の完全性を関連付ける結果は数多くあります。

• X上の順序トポロジが接続されている場合、X は完全です。
• Xが順序位相で連結されている場合、それは完全であり、 Xにギャップがないときのみです(ギャップとは、 X内の2 つの点aとbで、 a < bであり、どのc もa < c < b を満たさないことです)。
• Xが完全であるためには、順序位相で閉じているすべての有界集合がコンパクトである必要があります。

完全格子である全順序集合（順序位相を含む）はコンパクトである。例としては、実数の閉区間（単位区間[0,1] など）やアフィン拡張実数系（拡張実数直線）などがある。これらの例の間には 順序を保存する同相写像が存在している。

任意の 2 つの互いに素な全順序 および に対して 、集合 上には自然な順序が存在し、これは 2 つの順序の和、または単に と呼ばれることもあります。 ${\displaystyle (A_{1},\leq _{1})}$${\displaystyle (A_{2},\leq _{2})}$${\displaystyle \leq _{+}}$${\displaystyle A_{1}\cup A_{2}}$${\displaystyle A_{1}+A_{2}}$

については、次のいずれかが成立する場合に限り成立します。 ${\displaystyle x,y\in A_{1}\cup A_{2}}$${\displaystyle x\leq _{+}y}$

1. ${\displaystyle x,y\in A_{1}}$そして${\displaystyle x\leq _{1}y}$
2. ${\displaystyle x,y\in A_{2}}$そして${\displaystyle x\leq _{2}y}$
3. ${\displaystyle x\in A_{1}}$そして${\displaystyle y\in A_{2}}$

直感的に言えば、これは 2 番目のセットの要素が最初のセットの要素の上に追加されることを意味します。

より一般的には、が全順序付きインデックス集合であり、各に対して構造が線型順序であり、集合が対で互いに素である場合、上の自然な全順序は次のように定義される。 ${\displaystyle (I,\leq )}$${\displaystyle i\in I}$${\displaystyle (A_{i},\leq _{i})}$${\displaystyle A_{i}}$${\displaystyle \bigcup_{i}A_{i}}$

については、次の条件が成立します。 ${\displaystyle x,y\in \bigcup _{i\in I}A_{i}}$${\displaystyle x\leq y}$

1. どちらかが${\displaystyle i\in I}$${\displaystyle x\leq _{i}y}$
2. または、 ​​ ${\displaystyle i<j}$${\displaystyle I}$${\displaystyle x\in A_{i}}$${\displaystyle y\in A_{j}}$

全順序の第一階理論は決定可能である。つまり、すべての全順序に対してどの第一階の命題が成り立つかを決定するアルゴリズムが存在する。S2Sの解釈可能性を利用すると、可算全順序のモナド第二階理論も決定可能である。^[16]

2 つの完全に順序付けられた集合を取り、直積 上の順序 に拡張する方法はいくつかありますが、結果として得られる順序は部分的なだけになる場合があります。次に、これらの可能な順序のうち 3 つを示します。各順序は次の順序よりも強くなるようにリストされています。

• 辞書式順序: ( a、b ) ≤ ( c、d ) は、 a < cまたは ( a = cかつb ≤ d )の場合に限ります。これは全順序です。
• ( a , b ) ≤ ( c , d ) は、 a ≤ cかつb ≤ dの場合に限ります(積の順序)。これは半順序です。
• ( a , b ) ≤ ( c , d ) であるのは、 ( a < cかつb < d ) または ( a = cかつb = d ) の場合のみです (対応する厳密な全順序の直積の反射閉包)。これも半順序です。

これらの順序はそれぞれ、積の順序でx ≤ y が成り立つ場合、この関係は辞書式順序でも成り立つ、といった意味で次の順序を拡張します。3 つすべてを、2 つ以上のセットの直積に対して同様に定義できます。

これらをベクトル空間 R ⁿに適用すると、順序付きベクトル空間になります。

部分順序集合の例も参照してください。

R ⁿのサブセット上で定義されたn 個の実変数の実関数は、そのサブセット上で厳密な弱順序と対応する全順序を定義します。

反対称、推移的、反射的（必ずしも完全ではない）な二項関係は、半順序です。

互換性のある全順序を持つグループは全順序群です。

全順序の縮約である（と相互定義できる）非自明な構造はわずかしかない。方向を忘れると媒介関係が生じる。端点の位置を忘れると循環順序が生じる。両方のデータを忘れると分離関係が生じる。^[17]

• バーコフ、ギャレット(1967)。格子理論。コロキウム出版。第 25 巻。プロビデンス: アメリカ数学協会。
• Davey, Brian A.; Priestley, Hilary Ann (1990)。格子と秩序入門。ケンブリッジ数学教科書。ケンブリッジ大学出版局。ISBN 0-521-36766-2LCCN  89009753 。
• Fuchs, L (1963)。部分的に順序付けられた代数システム。Pergamon Press。
• ジョージ・グレーツァー (1971)。『格子理論: 最初の概念と分配格子』 WH Freeman and Co. ISBN 0-7167-0442-0 
• ハルモス、ポール R. (1968)。『素朴集合論』プリンストン: ノストランド。
• ジョン・G・ホッキング、ゲイル・S・ヤング（1961年）。トポロジー。訂正再版、ドーバー、1988年 。ISBN 0-486-65676-4 
• Rosenstein, Joseph G. (1982).線形順序付け. ニューヨーク: Academic Press.
• シュミット、ギュンター、ストレライン、トーマス (1993)。関係とグラフ: コンピュータ科学者のための離散数学。ベルリン: Springer- Verlag。ISBN 978-3-642-77970-1。

• 「全順序集合」、数学百科事典、EMS Press、2001 [1994]