準秩序性

数学、特に順序論において、集合上の準順序付け（準順序付けwqo ）とは、集合の任意の無限列に、次式で表される増加ペアが含まれる準順序付けである。${\displaystyle X}$${\displaystyle X}$${\displaystyle x_{0},x_{1},x_{2},\ldots }$${\displaystyle X}$${\displaystyle x_{i}\leq x_{j}}$${\displaystyle i<j.}$

整根拠帰納法は、整根拠関係を持つ任意の集合に使用できるため、準順序が整根拠である場合に興味があります。(ここでは、用語の乱用により、対応する厳密な順序が整根拠関係である場合に、準順序は整根拠であるとされています。) ただし、整根拠準順序のクラスは、特定の操作に対して閉じられていません。つまり、準順序を使用して、元の集合から派生した構造の集合で新しい準順序を取得する場合、この準順序は整根拠ではないことがわかります。元の整根拠準順序に強い制約を課すことで、導出された準順序が依然として整根拠であることを保証できます。 ${\displaystyle \leq}$${\displaystyle x\leq y\land y\nleq x}$

一例として、べき乗集合演算が挙げられます。集合の準順序付けが与えられた場合、の各要素に対して に関してそれよりも大きい の要素を見つけることができる場合のみ、を設定することにより、 のべき乗集合上の準順序付けを定義できます。上のこの準順序付けは必ずしも整列している必要はないことを示すことができますが、元の準順序付けを整列準順序付けと見なすと、整列準順序付けになります。 ${\displaystyle \leq}$${\displaystyle X}$${\displaystyle \leq ^{+}}$${\displaystyle X}$${\displaystyle P(X)}$${\displaystyle A\leq ^{+}B}$${\displaystyle A}$${\displaystyle B}$${\displaystyle \leq}$${\displaystyle P(X)}$

集合上のwell -quasi-ordering は、からの任意の無限の要素シーケンスに を伴う増加ペアが含まれるような準順序付け(つまり、反射的、推移的な二項関係)です。この集合はwell-quasi-ordered、または簡単にwqoであると言われます。 ${\displaystyle X}$ ${\displaystyle x_{0},x_{1},x_{2},\ldots }$${\displaystyle X}$${\displaystyle x_{i}\leq x_{j}}$${\displaystyle i<j}$${\displaystyle X}$

部分順序( wpo ) は、適切な順序関係である、つまり反対称である wqo です。

wqoを定義する他の方法の一つは、wqoが（形式の）無限の厳密な減少シーケンス^[1]や、 2つを比較できない要素の無限シーケンスを含まない準順序であると言うことです。したがって、準順序（X 、≤）は、（ X、<）が整基礎であり、無限の反連鎖を持たない場合にのみwqoです。 ${\displaystyle x_{0}>x_{1}>x_{2}>\cdots }$

を部分的に順序付けされたものとする。とのペアを含まないの要素の（必然的に有限な）シーケンスは、通常、不良シーケンスと呼ばれる。不良シーケンスのツリーは、各不良シーケンスの頂点と、空でない各不良シーケンスをその親に接続する辺を含むツリーである。 のルートは、空のシーケンスに対応します。には無限の不良シーケンスが含まれていないため、ツリーにはルートから始まる無限パスが含まれません。^[要出典]したがって、の各頂点には順序高さ があり、これは超限帰納法によって と定義されます。の順序型は、のルートの順序高さです。 ${\displaystyle X}$${\displaystyle (x_{1},x_{2},\ldots ,x_{n})}$${\displaystyle X}$${\displaystyle x_{i}\leq x_{j}}$${\displaystyle i<j}$ ${\displaystyle T_{X}}$${\displaystyle (x_{1},\ldots,x_{n-1},x_{n})}$${\displaystyle (x_{1},\ldots,x_{n-1})}$${\displaystyle T_{X}}$${\displaystyle X}$${\displaystyle T_{X}}$${\displaystyle v}$${\displaystyle T_{X}}$${\displaystyle o(v)}$${\displaystyle o(v)=\lim _{w\mathrm {\ child\ of​​\ } v}(o(w)+1)}$${\displaystyle X}$${\displaystyle o(X)}$${\displaystyle T_{X}}$

の線形化は、半順序を全順序に拡張したものです。が のすべての線形化の順序型の上限であることは簡単に検証できます。De Jongh と Parikh ^[1]は、実際に最大の順序型 を実現するの線形化が常に存在することを証明しました。 ${\displaystyle X}$${\displaystyle o(X)}$${\displaystyle X}$${\displaystyle X}$${\displaystyle o(X)}$

• ${\displaystyle (\mathbb {N} ,\leq )}$標準的な順序付けを持つ自然数の集合 は、整部分順序（実際は整順序）です。しかし、正負の整数の集合 は、整準順序ではありません。なぜなら、整基礎ではないからです（図 1 を参照）。${\displaystyle (\mathbb {Z} ,\leq )}$
• ${\displaystyle (\mathbb {N} ,|)}$割り切れる順に並べられた自然数の集合は準整列順序ではない。素数は無限反鎖である（図2を参照）。
• ${\displaystyle (\mathbb {N} ^{k},\leq )}$、自然数のベクトルの集合（ただし は有限）で、成分ごとの順序付け は、整半順序です（ディクソンの補題、図3を参照）。より一般的には、 が整準順序である場合、もすべての に対して整準順序です。${\displaystyle k}$${\displaystyle k}$${\displaystyle (X,\leq )}$${\displaystyle (X^{k},\leq ^{k})}$${\displaystyle k}$
• を少なくとも 2 つの要素を持つ任意の有限集合とします。 を辞書式に順序付けした(辞書のように)単語の集合は、無限減少シーケンス を含むため、準整列ではありません。同様に、接頭辞関係で順序付けされた は準整列ではありません。前のシーケンスがこの部分順序の無限反連鎖であるためです。ただし、部分列関係で順序付けされた は準整列です。^[2] ( が1 つの要素のみである場合、これら 3 つの部分順序は同一です。)${\displaystyle X}$${\displaystyle X^{*}}$ ${\displaystyle X}$${\displaystyle b,ab,aab,aaab,\ldots }$${\displaystyle X^{*}}$${\displaystyle X^{*}}$${\displaystyle X}$
• より一般的には、 のとき、埋め込みによって順序付けられた有限 -シーケンスの集合は、が準順序である場合に限り、準順序になります ( Higman の補題)。シーケンスをシーケンスに埋め込むには、と同じ長さを持ち、 を項ごとに支配する の部分シーケンスを見つけることを思い出してください。 が順序付けられていない集合である場合、が の部分シーケンスである場合に限ります。${\displaystyle (X^{*},\leq )}$${\displaystyle X}$${\displaystyle (X,\leq )}$${\displaystyle u}$${\displaystyle v}$${\displaystyle v}$${\displaystyle u}$${\displaystyle (X,=)}$${\displaystyle u\leq v}$${\displaystyle u}$${\displaystyle v}$
• ${\displaystyle (X^{\omega },\leq )}$埋め込みによって順序付けられた、よく準順序 上の無限シーケンスの集合は、一般によく準順序ではありません。つまり、ヒグマンの補題は無限シーケンスには適用されません。ヒグマンの補題を任意の長さのシーケンスに一般化するために、よりよい準順序が導入されました。${\displaystyle (X,\leq )}$
• wqo の要素によってラベル付けされたノードを持つ有限ツリー間の埋め込みはwqo です (クラスカルのツリー定理)。${\displaystyle (X,\leq )}$
• wqo の要素によってラベル付けされたノードを持つ無限ツリー間の埋め込みはwqo です (ナッシュ-ウィリアムズの定理)。${\displaystyle (X,\leq )}$
• 可算な散在 線形順序型間の埋め込みは、準秩序である (レーバーの定理)。
• 可算ブール代数間の埋め込みは準整列順序です。これは、レーバーの定理とケトネンの定理から導かれます。
• 「グラフマイナー」と呼ばれる埋め込みの概念によって順序付けられた有限グラフは、準順序付けされます (ロバートソン-シーモア定理)。
• 誘導サブグラフ関係によって順序付けられた有限木の深さのグラフは、誘導サブグラフによって順序付けられたコグラフと同様に、準順序を形成します。^{[3] [4]}

とを2つの互いに素なwpo集合とする。、およびを、同じおよびに対してが成り立つと仮定して、 上の部分順序を定義する。すると はwpoとなり、 となる。ここで は順序数の自然和 を表す。^[1]${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle Y=X_{1}\cup X_{2}}$${\displaystyle Y}$${\displaystyle y_{1}\leq _{Y}y_{2}}$${\displaystyle y_{1},y_{2}\in X_{i}}$${\displaystyle i\in \{1,2\}}$${\displaystyle y_{1}\leq _{X_{i}}y_{2}}$${\displaystyle Y}$${\displaystyle o(Y)=o(X_{1})\oplus o(X_{2})}$${\displaystyle \oplus }$

wpo集合およびが与えられたとき、かつのときのみ とすることで、直積 上の半順序を定義します。すると はwpo となり（これはディクソンの補題の一般化です）、 となります。ここで は順序数の自然積を表します。 ^[1]${\displaystyle X_{1}}$${\displaystyle X_{2}}$${\displaystyle Y=X_{1}\times X_{2}}$${\displaystyle (a_{1},a_{2})\leq _{Y}(b_{1},b_{2})}$${\displaystyle a_{1}\leq _{X_{1}}b_{1}}$${\displaystyle a_{2}\leq _{X_{2}}b_{2}}$${\displaystyle Y}$${\displaystyle o(Y)=o(X_{1})\otimes o(X_{2})}$${\displaystyle \otimes }$

wpo集合 が与えられたとき、を の要素の有限列の集合とし、部分列関係によって部分的に順序付けられるとする。つまり、 が各 に対して となるようなインデックスが存在する場合のみ とみなす。ヒグマンの補題により、は wpo である。 の順序型は^{[1] [5]}である。${\displaystyle X}$${\displaystyle X^{*}}$${\displaystyle X}$${\displaystyle (x_{1},\ldots ,x_{n})\leq _{X^{*}}(y_{1},\ldots ,y_{m})}$${\displaystyle 1\leq i_{1}<\cdots <i_{n}\leq m}$${\displaystyle x_{j}\leq _{X}y_{i_{j}}}$${\displaystyle 1\leq j\leq n}$${\displaystyle X^{*}}$${\displaystyle X^{*}}$ $${\displaystyle o(X^{*})={\begin{cases}\omega ^{\omega ^{o(X)-1}},&o(X){\text{ finite}};\\\omega ^{\omega ^{o(X)+1}},&o(X)=\varepsilon _{\alpha }+n{\text{ for some }}\alpha {\text{ and some finite }}n;\\\omega ^{\omega ^{o(X)}},&{\text{otherwise}}.\end{cases}}}$$

wpo集合 が与えられたとき、を頂点が の要素でラベル付けされた有限根付き木全体の集合とします。 は木の埋め込み関係によって部分的に順序付けられます。クラスカルの木定理により、は wpo です。 この結果は （ラベル付けされていない木に対応する）場合でも自明ではなく、その場合 は小さなヴェブレン順序数に等しくなります。 一般に、可算 に対して、順序数崩壊関数に関して上限が得られます。 （小さなヴェブレン順序数は、この順序数表記では に等しくなります。）^[6]${\displaystyle X}$${\displaystyle T(X)}$${\displaystyle X}$${\displaystyle T(X)}$${\displaystyle T(X)}$${\displaystyle |X|=1}$${\displaystyle o(T(X))}$${\displaystyle o(X)}$${\displaystyle o(T(X))\leq \vartheta (\Omega ^{\omega }o(X))}$${\displaystyle \vartheta }$ ${\displaystyle \vartheta (\Omega ^{\omega })}$

実際には、操作する wqo は順序ではないことが非常に多く (上記の例を参照)、反対称性を必要としない場合は理論は技術的にスムーズになるため^{[引用が必要]}、wqo を基本概念として構築されます。一方、Milner 1985 によると、部分順序ではなく準順序を考慮しても、一般性において実際の利点は得られません...単にそうする方が便利であるというだけです。

wpo は wqo であり、wqo は wqo の核によって誘導される同値類間の wpo を生成することに注意してください。たとえば、割り切れる順に並べると、の場合にのみとなり、 となります。 ${\displaystyle \mathbb {Z} }$${\displaystyle n\equiv m}$${\displaystyle n=\pm m}$${\displaystyle (\mathbb {Z} ,|)\approx (\mathbb {N} ,|)}$

が wqo の場合、すべての無限シーケンスには無限増加サブシーケンス( )が含まれます。このようなサブシーケンスは完全 と呼ばれることがあります。これは、 Ramsey の議論によって証明できます。つまり、あるシーケンス が与えられたときに、 の右側により大きいか等しい が存在しないようなインデックスの集合、つまり が無限の場合を考えます。が無限の場合、 から抽出されたサブシーケンスは wqo であるという仮定に矛盾します。したがって は有限であり、のどのインデックスよりも大きいは、無限増加サブシーケンスの開始点として使用できます。 ${\displaystyle (X,\leq )}$${\displaystyle x_{0},x_{1},x_{2},\ldots ,}$${\displaystyle x_{n_{0}}\leq x_{n_{1}}\leq x_{n_{2}}\leq \cdots }$${\displaystyle n_{0}<n_{1}<n_{2}<\cdots }$${\displaystyle (x_{i})_{i}}$${\displaystyle I}$${\displaystyle i}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle i<j}$${\displaystyle I}$${\displaystyle I}$${\displaystyle X}$${\displaystyle I}$${\displaystyle x_{n}}$${\displaystyle n}$${\displaystyle I}$

このような無限増加部分列の存在は、準順序付けの定義として解釈されることがあり、同等の概念につながります。

• 準順序付けが与えられたとき、によって定義される 準順序付けはwqoであるときのみ整列している。 ^[7]${\displaystyle (X,\leq )}$${\displaystyle (P(X),\leq ^{+})}$${\displaystyle A\leq ^{+}B\iff \forall a\in A,\exists b\in B,a\leq b}$${\displaystyle (X,\leq )}$
• 準順序付けは、対応する半順序付け（ を で割って得られる）に無限降順シーケンスまたは反連鎖がない場合にのみ、 wqo です。（これは、上記のようにラムゼーの議論を使用して証明できます。）${\displaystyle x\sim y\iff x\leq y\land y\leq x}$
• 準整列 が与えられた場合、任意の上向きに閉じた部分集合のシーケンスは最終的に安定します (つまり、となる が存在する; のとき、部分集合は上向きに閉じていると呼ばれます)。その逆を仮定すると、無限の非昇順部分シーケンスを抽出することによって矛盾に達します。${\displaystyle (X,\leq )}$${\displaystyle S_{0}\subseteq S_{1}\subseteq \cdots \subseteq X}$${\displaystyle n\in \mathbb {N} }$${\displaystyle S_{n}=S_{n+1}=\cdots }$${\displaystyle S\subseteq X}$${\displaystyle \forall x,y\in X,x\leq y\wedge x\in S\Rightarrow y\in S}$${\displaystyle \forall i\in \mathbb {N} ,\exists j\in \mathbb {N} ,j>i,\exists x\in S_{j}\setminus S_{i}}$
• 準順序付けされた が与えられた場合、の任意の部分集合はに関して有限個の最小元を持ちます。そうでない場合、 の最小元は無限反鎖を構成するからです。${\displaystyle (X,\leq )}$${\displaystyle S}$${\displaystyle X}$${\displaystyle \leq }$${\displaystyle S}$

• より良い準順序付け – 数学的関係Pages displaying wikidata descriptions as a fallback
• プレウェル順序付け – 集合論の概念
• 整列順序 – 数学的順序のクラス

^ここでx < yは次を意味します:そして${\displaystyle x\leq y}$${\displaystyle x\neq y.}$

• ディクソン、LE ( 1913)。「 r個の異なる素因数を持つ奇数の完全数と原始多値の有限性」。アメリカ数学ジャーナル。35 ( 4): 413–422。doi :10.2307/2370405。JSTOR  2370405。
• Higman, G. (1952). 「抽象代数における割り切れる順序」.ロンドン数学会紀要. 2 : 326–336. doi :10.1112/plms/s3-2.1.326.
• Kruskal, JB (1972). 「よく準順序付けされた理論: 頻繁に発見される概念」.組合せ理論ジャーナル. シリーズ A. 13 (3): 297–305. doi : 10.1016/0097-3165(72)90063-5 .
• ケトネン、ユッシ (1978)。「可算ブール代数の構造」。数学年報。108 ( 1 ) : 41–89。doi : 10.2307/1970929。JSTOR  1970929。
• Milner, EC (1985)。「基本的な WQO および BQO 理論」。Rival, I. (編)著「グラフと順序。順序付き集合の理論とその応用におけるグラフの役割」。D. Reidel Publishing Co. pp. 487–502。ISBN 90-277-1943-8。
• Gallier, Jean H. (1991). 「クラスカルの定理と順序数 Γo の何が特別なのか? 証明理論におけるいくつかの結果の調査」Annals of Pure and Applied Logic . 53 (3): 199–260. doi :10.1016/0168-0072(91)90022-E.