より良い準順序付け

順序理論では、より良い準順序付け( bqo)は、特定の種類の不良配列を許容しない準順序付けです。すべてのより良い準順序付けは、良好な準順序付けです。

よく準順序付けは魅力的な概念だが、多くの重要な無限演算はよく準順序付けされた状態を維持しない。リチャード・ラドの例がこれを示している。^[1] 1965 年の論文で、クリスピン・ナッシュ＝ウィリアムズは、高さωの木のクラスが位相小数点関係の下でよく準順序付けされていることを証明するために、より強い概念であるよりよい準順序付けを定式化した。^[2]それ以来、多くの準順序付けは、よりよい準順序付けであることを証明することによってよく準順序付けであることが証明されてきた。例えば、リチャード・レーバーは、散在する線型順序のクラスがよりよい準順序付けされていることを証明することによって、レーバーの定理(以前はローランド・フレッセの予想だった)を確立した。 ^{[3]最近では、カルロス・マルティネス・ラネロは、}適切な強制公理の下で、アロンザイン直線のクラスが埋め込み可能性関係の下でより良い準順序付けされていることを証明した。 ^[4]

より良い準順序付け理論では、最初の項を省略した数列を と書くことが一般的です。 の項を持つ有限の厳密に増加な数列の集合を と書き、 上の関係を次のように定義します。がの厳密な初期線分であり であるような数列が存在する場合、は推移的ではありません。関係はに推移的ではありません。 ${\displaystyle {_{*}}x}$${\displaystyle x}$${\displaystyle [\omega ]^{<\omega }}$${\displaystyle \omega}$${\displaystyle \triangleleft}$${\displaystyle [\omega ]^{<\omega }}$${\displaystyle s\triangleleftt}$${\displaystyle u\in [\omega ]^{<\omega }}$${\displaystyle s}$${\displaystyle u}$${\displaystyle t={}_{*}u}$${\displaystyle \triangleleft}$

ブロックは 、のすべての無限部分集合の初期セグメント^{[明確化が必要]}を含む の無限部分集合です。準順序 の場合、-パターンは、何らかのブロックからへの関数です。となるすべてのペアに対して^{[明確化が必要]}である場合、-パターンは悪いと言われ、それ以外の場合は良いです。悪い -パターンがない場合は、準順序付けはより良い準順序付けと呼ばれます。 ${\displaystyle B}$${\displaystyle [\omega ]^{<\omega }}$${\displaystyle \bigcup B}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle B}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle f\colon B\to Q}$${\displaystyle f(s)\not \leq _{Q}f(t)}$${\displaystyle s,t\in B}$${\displaystyle s\triangleleftt}$${\displaystyle f}$${\displaystyle Q}$${\displaystyle Q}$

この定義を扱いやすくするために、ナッシュ=ウィリアムズは、包含関係 の下で要素がペアで比較できないブロックをバリアとして定義します。-配列は、ドメインがバリアである -パターンです。すべてのブロックにバリアが含まれていることを観察すると、悪い -配列が存在しない場合に限り、 がより良い準順序付けであることがわかります。 ${\displaystyle \subset }$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle Q}$

シンプソンはボレル関数の観点からより良い準順序付けの別の定義を導入した。ここで、 の無限部分集合の集合には、通常の積位相が与えられる。^[5] ${\displaystyle [\omega ]^{\omega }\to Q}$${\displaystyle [\omega ]^{\omega }}$${\displaystyle \omega}$

を準順序付けとし、離散位相を付与します。-配列は、の無限部分集合に対するボレル関数です。-配列は、任意の に対して である場合は悪い配列であり、 それ以外の場合は良い配列です。この意味で 悪い -配列が存在しない場合は、準順序付けはより良い準順序付けです。${\displaystyle Q}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle [A]^{\omega }\to Q}$${\displaystyle A}$${\displaystyle \omega}$${\displaystyle Q}$${\displaystyle f}$${\displaystyle f(X)\not \leq _{Q}f({_{*}}X)}$${\displaystyle X\in [A]^{\omega }}$${\displaystyle f}$${\displaystyle Q}$${\displaystyle Q}$

より良い準順序付け理論における多くの主要な結果は、シンプソンの論文^[5]に次のように記載されている最小不良配列補題の結果です。最小不良配列補題が結果として初めて述べられたレーバーの論文^[6]も参照してください。この手法は、ナッシュ・ウィリアムズの 1965 年のオリジナルの論文に存在していました。

が準順序であるとします。^{[説明が必要]}の部分順位付けは、 となるの整基礎部分順序付けです。不正な-配列 (シンプソンの意味で)および に対して、次のように定義します。 ${\displaystyle (Q,\leq _{Q})}$ ${\displaystyle \leq '}$${\displaystyle Q}$ ${\displaystyle Q}$${\displaystyle q\leq 'r\to q\leq _{Q}r}$${\displaystyle Q}$${\displaystyle f\colon [A]^{\omega }\to Q}$${\displaystyle g\colon [B]^{\omega }\to Q}$

${\displaystyle g\leq ^{*}f{\text{ }}B\subseteq A{\text{ かつ }}g(X)\leq 'f(X){\text{ 任意の }}X\in [B]^{\omega }} の場合$

${\displaystyle g<^{*}f{\text{ }}B\subseteq A{\text{ かつ }}g(X)<'f(X){\text{ 任意の }}X\in [B]^{\omega }} の場合$

となるような悪い-配列が存在しないとき、悪い -配列は（部分順位付けに関して）極小悪いと言います。 と の定義は、の部分順位付けに依存します。 関係は、関係 の厳密な部分ではありません。 ${\displaystyle Q}$${\displaystyle g}$${\displaystyle \leq '}$${\displaystyle Q}$${\displaystyle f}$${\displaystyle f<^{*}g}$${\displaystyle \leq ^{*}}$${\displaystyle <'}$${\displaystyle \leq '}$${\displaystyle Q}$${\displaystyle <^{*}}$${\displaystyle \leq ^{*}}$

定理(最小の不良配列補題) が部分順位付けを備えた準順序であり、が不良 -配列であるとします。このとき、となる最小の不良-配列が存在します。 ${\displaystyle Q}$${\displaystyle f}$${\displaystyle Q}$${\displaystyle Q}$${\displaystyle g}$${\displaystyle g\leq ^{*}f}$

• 準秩序性
• 秩序ある