弱い順序

数学、特に順序理論において、弱い順序付けとは、集合の要素の一部が互いに同点である可能性がある集合の順位付けという直感的な概念を数学的に形式化したものである。弱い順序付けは、完全に順序付けられた集合（同点のない順位付け）の一般化であり、今度は（厳密に）部分的に順序付けられた集合と前順序付けによって一般化される。^[1]

弱い順序付けを形式化する一般的な方法には、互いに異なるが暗号形式（情報を失うことなく相互変換可能）であるものがいくつかあります。これらは、厳密な弱い順序付け（比較不可能性が推移的な関係である厳密に部分的に順序付けられた集合）、全事前順序付け（すべての要素のペア間に 2 つの可能な関係のうち少なくとも 1 つが存在する推移的な 2 項関係）、または順序付き分割（要素を互いに素な部分集合に分割し、部分集合に全順序付けを行う）として公理化できます。多くの場合、効用関数に基づく優先配置と呼ばれる別の表現も可能です。

弱い順序付けは、順序付けられたベル数によってカウントされます。コンピュータサイエンスではパーティション調整アルゴリズムの一部として、またC++標準ライブラリで使用されます。^[2]

競馬では、写真判定の導入により、同着または（この文脈ではデッドヒートと呼ぶ）一部の（全てではない）同着が解消されたため、競馬の結果は弱い順序付けでモデル化できるかもしれない。^{[3] 2007年の}メリーランドハントカップ障害競走の例では、ザ・ブルースが明確な勝者となったが、バグ・リバーとリア・チャームの2頭が2位で同着となり、残りの馬はさらに後ろで、3頭は完走しなかった。^[4]この結果を表す弱い順序付けでは、ザ・ブルースが1位となり、バグ・リバーとリア・チャームはザ・ブルースの後ろで完走した他のすべての馬よりも前にランクされ、完走しなかった3頭は最後尾となるが同着となる。

ユークリッド平面上の点は、原点からの距離によって順序付けることができ、これは、無限個の要素、無限個の同点要素の部分集合（原点を中心とする共通の円に属する点の集合）、およびこれらの部分集合内の無限個の点を伴う弱い順序付けの別の例となります。この順序付けには最小の要素（原点自体）がありますが、2番目に小さい要素や最大の要素はありません。

政治選挙における世論調査は、弱い順序付けに似ているが、数学的には他の方法でより適切にモデル化される順序付けのタイプの一例である。世論調査の結果では、一方の候補者が他方の候補者より明らかに先行している場合もあれば、2 人の候補者が統計的に同点である場合もある。これは、世論調査の結果が等しいということではなく、互いの誤差範囲内であることを意味する。しかし、候補者が と統計的に同点であり、 が と統計的に同点である場合、 がよりも明らかに優れている可能性が依然としてあるため、この場合、同点であることは推移的な関係ではない。この可能性のため、このタイプのランキングは、弱い順序付けよりも半順序付けとしてモデル化する方が適切である。 ^[5]${\displaystyle x}$${\displaystyle y,}$${\displaystyle y}$${\displaystyle z,}$${\displaystyle x}$${\displaystyle z,}$

全体にわたって が集合上の同次二項関係（つまり はの部分集合）であると仮定し、通常どおり が成り立つ、または が真となるのは の場合のみであると書きます。${\displaystyle \,<\,}$ ${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S\times S}$${\displaystyle x<y}$${\displaystyle x<y}$${\displaystyle (x,y)\in \,<.\,}$

比較不可能性と比較不可能性の推移性に関する予備的考察

の2つの要素とがに関して比較不可能であるとは、 も も真でない場合に言う。 ^[1]厳密な半順序 が厳密な弱順序 となるのは、 に関して比較不可能であることが同値関係である場合に限ります。 に関して比較不可能であることは、常に上の同次対称関係です。 が反射的で あるのは、 が非反射的（つまり は常に偽）である場合に限ります。この「比較不可能な関係」が同値関係となるために必要な唯一の特性は推移性であると仮定されます。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle x<y}$${\displaystyle y<x}$ ${\displaystyle \,<\,}$${\displaystyle \,<\,}$${\displaystyle \,<\,}$${\displaystyle S.}$${\displaystyle \,<\,}$${\displaystyle x<x}$

を宣言することによって 、に対する誘導同次関係も定義します 。ここで重要なことに、この定義は必ずしも次と同じではありません。 の場合に限り 2 つの要素がに関して比較不可能である場合に限りが に関して同値(または、簡潔に言えば-同値) であり、これは定義により両方とも真であることを意味します。したがって、「 に関して比較不可能」という関係は、「 は -同値である」という関係と同一 (つまり、 と等しい) です(したがって特に、前者が推移的である場合に限り、後者が推移的)。 が非反射的である場合、「比較不可能性の推移性」(以下に定義) として知られる特性は、まさに「 は -同値である」という関係が に対して同値関係を形成することを保証するために必要かつ十分な条件です。この場合 、を満たす任意の2 つの要素を単一のオブジェクトとして識別できます (具体的には、それらは共通の同値クラスで一緒に識別されます)。 ${\displaystyle \,\lesssim \,}$${\displaystyle S}$$${\displaystyle x\lesssim y{\text{ は真 }}\quad {\text{ の場合のみ }}\quad y<x{\text{ は偽}}}$$${\displaystyle x\lesssim y}$${\displaystyle x<y{\text{ または }}x=y.}$${\displaystyle x,y\in S}$${\displaystyle \,<\,}$${\displaystyle x{\text{ と }}y}$${\displaystyle \,\lesssim \,}$${\displaystyle \,\lesssim}$${\displaystyle x\lesssim y{\text{ と }}y\lesssim x}$${\displaystyle \,<}$${\displaystyle \,\lesssim}$${\displaystyle \,<\,}$${\displaystyle \,\lesssim}$${\displaystyle S.}$${\displaystyle x,y\in S}$${\displaystyle x\lesssim y{\text{ と }}y\lesssim x}$

意味

集合上の厳密な弱い順序とは、集合上の厳密な半順序であり、集合上の によって誘導される比較不可能関係は推移的な関係である。^[1] 明示的に言えば、集合上の厳密な弱い順序は集合上の同次関係であり、次の 4 つの特性をすべて備えている。 ${\displaystyle S}$ ${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$ ${\displaystyle \,<\,}$${\displaystyle S}$

1. 非反射性：すべての人にとって真実ではない${\displaystyle x\in S,}$${\displaystyle x<x.}$
   • この条件は、上の誘導関係 が反射的である場合に限り成立します。ここで、 は、が偽である場合に限りが真であると宣言することによって定義されます。${\displaystyle \,\lesssim \,}$${\displaystyle S}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y}$${\displaystyle y<x}$
2. 推移性：すべての場合において${\displaystyle x,y,z\in S,}$${\displaystyle x<y{\text{ および }}y<z}$${\displaystyle x<z.}$
3. 非対称性: すべてにおいて、が真であれば偽です。${\displaystyle x,y\in S,}$${\displaystyle x<y}$${\displaystyle y<x}$
4. 比較不可能性の推移性：すべてについて、がと比較不可能である（つまり、もも真ではない）場合、およびがと比較不可能である、はと比較不可能である。${\displaystyle x,y,z\in S,}$${\displaystyle x}$${\displaystyle y}$${\displaystyle x<y}$${\displaystyle y<x}$${\displaystyle y}$${\displaystyle z,}$${\displaystyle x}$${\displaystyle z.}$
   • 2 つの要素がに関して比較不可能なのは、それらが誘導関係に関して同等である場合に限ります(これは定義により、 が両方とも真であることを意味します)。ここで、前述のように、が偽である場合に限り、 が真であると宣言されます。したがって、この条件は、 「に関して同等である」によって定義される上の対称関係が推移的関係である場合に限り成立します。つまり、が-同等であり、 も-同等である場合は、必然的にも -同等です。これは次のように言い換えることもできます。 およびも である場合は、必然的にも${\displaystyle x{\text{ と }}y}$${\displaystyle \,<\,}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y{\text{ と }}y\lesssim x}$${\displaystyle x\lesssim y}$${\displaystyle y<x}$${\displaystyle S}$${\displaystyle x{\text{ と }}y}$${\displaystyle \,\lesssim \,}$${\displaystyle x{\text{ と }}y}$${\displaystyle \,\lesssim}$${\displaystyle y{\text{ と }}z}$${\displaystyle \,\lesssim}$${\displaystyle x{\text{ と }}z}$${\displaystyle \,\lesssim}$${\displaystyle x\lesssim y{\text{ と }}y\lesssim x}$${\displaystyle y\lesssim z{\text{ と }}z\lesssim y}$${\displaystyle x\lesssim z{\text{ および }}z\lesssim x.}$

性質(1)、(2)、(3)は厳密な半順序を定義する性質であるが、非対称性(3)は非反射性(1)を意味し、また非反射性(1)と推移性(2)はともに非対称性(3)を意味するため、このリストにはいくらかの冗長性がある。^[6]比較不可能関係は常に対称であり、非反射関係である場合に限り反射的となる（これは上記の定義で想定されている）。したがって、厳密な半順序は、その誘導された比較不可能関係が同値関係である場合に限り、厳密な弱順序である。この場合、その同値類はに分割され、さらに、これらの同値類の集合は、すべてに対して によって定義される とも表される二項関係によって厳密に全順序付けることができる。 ${\displaystyle \,<\,}$${\displaystyle \,<\,}$ ${\displaystyle S}$${\displaystyle {\mathcal {P}}}$${\displaystyle \,<,}$${\displaystyle A,B\in {\mathcal {P}}}$

${\displaystyle A<B{\text{ }}a<b の場合のみ}$一部の（または同等に、すべての）代表者にとって${\displaystyle a\in A{\text{ }}b\in B.}$

逆に、の分割上の任意の厳密な全順序は、によって定義されるの厳密な弱順序を生じ、その場合、この分割に次の集合が存在する場合に限ります。 ${\displaystyle {\mathcal {P}}}$${\displaystyle S}$${\displaystyle \,<\,}$${\displaystyle S}$${\displaystyle a<b}$${\displaystyle A,B\in {\mathcal {P}}}$${\displaystyle a\in A,b\in B,{\text{ and }}A<B.}$

すべての半順序が比較不可能性の推移法則に従うわけではありません。たとえば、関係によって定義されるセット内の半順序を考えてみましょう。ペアは比較不可能ですが、と は関連しているため、比較不可能性は同値関係を形成せず、この例は厳密な弱い順序ではありません。 ${\displaystyle \{a,b,c\}}$${\displaystyle b<c.}$${\displaystyle a,b{\text{ and }}a,c}$${\displaystyle b}$${\displaystyle c}$

比較不可能性の推移性には、以下の各条件が必要であり、厳密な部分順序には十分です。

• いずれか一方または両方に対して、${\displaystyle x<y}$${\displaystyle z,}$${\displaystyle x<z{\text{ or }}z<y}$
• が と比較できない場合、すべての について、( ) または ( ) または ( はと比較できず、 はと比較できません) のいずれかになります。${\displaystyle x}$${\displaystyle y}$${\displaystyle z}$${\displaystyle x<z{\text{ and }}y<z}$${\displaystyle z<x{\text{ and }}z<y}$${\displaystyle z}$${\displaystyle x}$${\displaystyle z}$${\displaystyle y}$

厳密な弱順序は全前順序または（厳密でない）弱順序と非常に密接に関連しており、厳密な弱順序でモデル化できる同じ数学的概念を全前順序でも同様にモデル化できます。全前順序または弱順序は、任意の2つの要素が比較可能な前順序です。 ^[7]全前順序は次の特性を満たします。 ${\displaystyle \,\lesssim \,}$

• 推移性：すべての場合において${\displaystyle x,y,{\text{ and }}z,}$${\displaystyle x\lesssim y{\text{ and }}y\lesssim z}$${\displaystyle x\lesssim z.}$
• 強いつながり：すべての人にとって${\displaystyle x{\text{ and }}y,}$ ${\displaystyle x\lesssim y{\text{ or }}y\lesssim x.}$
  • それは、すべての人にとっての反射性を意味する。${\displaystyle x,}$ ${\displaystyle x\lesssim x.}$

全順序は反対称な全順序、言い換えれば半順序でもある。全順序は優先順位関係と呼ばれることもある。

厳密な弱順序の補集合は全前順序であり、その逆もまた同様であるが、厳密な弱順序と全前順序を、要素の順序を逆にするのではなく保存する方法で関連付ける方が自然であると思われる。したがって、補集合の逆をとる。厳密な弱順序に対して、以下の場合を除いて、全前順序を定義する。逆に、以下の場合を除いて、全前順序から厳密な弱順序 < を定義するには、^[8]${\displaystyle \,<,}$${\displaystyle \,\lesssim \,}$${\displaystyle x\lesssim y}$${\displaystyle y<x.}$${\displaystyle \,\lesssim ,}$${\displaystyle x<y}$${\displaystyle y\lesssim x.}$

任意の前順序には、対応する同値関係があり、2 つの要素とは次の場合に同値であると定義されます。全前順序の場合、同値類の集合上の対応する部分順序は全順序です。2 つの要素が全前順序で同値なのは、対応する厳密な弱い順序で比較できない場合のみです。 ${\displaystyle x}$${\displaystyle y}$${\displaystyle x\lesssim y{\text{ and }}y\lesssim x.}$

集合の分割 とは、集合の空でない互いに素な部分集合の族で、その和集合が であるものである。分割は、分割の集合の全順序とともに、リチャード・P・スタンレーによって順序付き分割[ ^{9]と呼ばれ、}セオドア・モツキンによって集合のリスト^[10]と呼ばれる構造を与える。有限集合の順序付き分割は、分割内の集合の有限列として表すことができる。例えば、集合の 3 つの順序付き分割は、 ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle \{a,b\}}$$${\displaystyle \{a\},\{b\},}$$ $${\displaystyle \{b\},\{a\},\;{\text{ and }}}$$ $${\displaystyle \{a,b\}.}$$

厳密な弱い順序付けでは、比較不可能性の同値類は集合分割を与え、集合は要素から全順序付けを継承し、順序付き分割を生じます。反対方向では、順序付き分割は厳密な弱い順序付けを生じ、2 つの要素は分割内の同じ集合に属する場合は比較不可能であり、それ以外の場合はそれらを含む集合の順序を継承します。

十分に小さい濃度の集合に対しては、実数値関数に基づく第4の公理化が可能である。 が任意の集合である場合、 上の実数値関数はを設定することにより 上の厳密な弱順序を誘導する。 関連する全前順序は を設定することにより与えられ 、関連する同値は を設定することにより 与えられる。${\displaystyle X}$${\displaystyle f:X\to \mathbb {R} }$${\displaystyle X}$${\displaystyle X}$$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a)\leq f(b)}$${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a)=f(b).}$

を（合成関数）に置き換えても関係は変化しない。ここで、は少なくとも の範囲で定義される厳密に増加する実数値関数である。したがって、たとえば、効用関数は選好関係を定義する。この文脈では、弱い順序付けは優先配置とも呼ばれる。^[11]${\displaystyle f}$${\displaystyle g\circ f}$${\displaystyle g}$${\displaystyle f.}$

が有限または可算である場合、 上のすべての弱い順序は、このように関数によって表すことができます。^[12]しかし、対応する実数関数を持たない厳密な弱い順序が存在します。たとえば、上の辞書式順序にはそのような関数はありません。したがって、ほとんどの選好関係モデルでは、関係は順序保存変換までの効用関数を定義しますが、辞書式選好にはそのような関数はありません。 ${\displaystyle X}$${\displaystyle X}$${\displaystyle \mathbb {R} ^{n}.}$

より一般的には、が集合、が厳密な弱順序付けを持つ集合、 が関数である場合、 を設定することにより 、に厳密な弱順序付けが誘導されます 。 前述のように、関連する全順序付けは を設定することで与えられ 、関連する同値は を設定することで 与えられます。 ここでは が単射関数であるとは想定されていないため、 上の 2 つの同値な要素のクラスは、上のより大きな同値な要素のクラスを誘導する可能性があります。また、は全射関数であるとは想定されていないため、 上の同値な要素のクラスは、上のより小さいクラスまたは空のクラスを誘導する可能性があります。 ただし、 関数は、 上の分割を上の分割にマップする単射関数を誘導します。したがって、有限分割の場合、 のクラスの数は上のクラスの数以下になります。${\displaystyle X}$${\displaystyle Y}$${\displaystyle \,<,\,}$${\displaystyle f:X\to Y}$${\displaystyle f}$${\displaystyle X}$$${\displaystyle a<b{\text{ if and only if }}f(a)<f(b).}$$${\displaystyle a{}\lesssim {}b{\text{ if and only if }}f(a){}\lesssim {}f(b),}$${\displaystyle a{}\sim {}b{\text{ if and only if }}f(a){}\sim {}f(b).}$${\displaystyle f}$${\displaystyle Y}$${\displaystyle X.}$${\displaystyle f}$${\displaystyle Y}$${\displaystyle X.}$${\displaystyle f}$${\displaystyle X}$${\displaystyle Y.}$${\displaystyle X}$${\displaystyle Y.}$

半順序は厳密な弱順序を一般化するが、比較不可能性の推移性を仮定しない。^[13]三分法である厳密な弱順序は厳密な全順序と呼ばれる。^[14]この場合、その補順序の逆である全前順序は全順序である。

厳密な弱順序の場合、別の関連する反射関係は、その反射閉包、つまり（厳密でない）半順序です。2 つの関連する反射関係は、異なるとに関して異なりますが、これらに対しても は成り立ちません。厳密な弱順序に対応する全順序では、およびが得られますが、反射閉包によって与えられる半順序では、も は得られません。厳密な全順序の場合、これら 2 つの関連する反射関係は同じです。つまり、対応する（厳密でない）全順序です。^{[14]厳密な弱順序の反射閉包は}、直列-並列半順序の一種です。 ${\displaystyle \,<\,}$${\displaystyle \,\leq .}$${\displaystyle a}$${\displaystyle b}$${\displaystyle a<b}$${\displaystyle b<a}$${\displaystyle a\lesssim b}$${\displaystyle b\lesssim a,}$${\displaystyle a\leq b}$${\displaystyle b\leq a.}$

元集合上の異なる弱順序（厳密な弱順序または全前順序として表される）の数は、次のシーケンス（ OEISのシーケンスA000670） で与えられます。${\displaystyle n}$

S ( n , k )は第2種スターリング数を指すことに注意してください。

これらの数は、フビニ数または順序ベル数とも呼ばれます。

たとえば、ラベルの付いた 3 つのアイテムのセットの場合、3 つのアイテムすべてが同点となる弱い順序が 1 つあります。アイテムを 1 つのシングルトンセットと 2 つの同点アイテムの 1 つのグループに分割する方法は 3 つあり、これらの分割のそれぞれで 2 つの弱い順序 (シングルトンが 2 つのグループより小さいもの、およびこの順序が逆のもの) が生成され、このタイプの弱い順序が 6 つ生成されます。また、セットを 3 つのシングルトンに分割する方法は 1 つあり、これらは 6 つの異なる方法で順序付けできます。したがって、合計で 3 つのアイテムに対して 13 の異なる弱い順序が存在します。

部分順序とは異なり、与えられた有限集合上の弱い順序の族は、一般に、与えられた順序に単一の順序関係を追加または削除する動きによって接続されていません。たとえば、3 つの要素の場合、3 つの要素すべてが結びついている順序は、厳密な弱い順序または全前順序公理化のいずれにおいても、同じ集合上の他の弱い順序とは少なくとも 2 組異なります。ただし、集合上の弱い順序がより高度に接続されている、異なる種類の動きが可能です。2 つの同値類を持つ弱い順序として二分法を定義し、順序で関連しているすべての 2 つの要素が二分法で同じように関連しているか結びついている場合、二分法は与えられた弱い順序と互換性があると定義します。あるいは、二分法は弱い順序のデデキント切断として定義できます。その場合、弱い順序は互換性のある二分法の集合によって特徴付けられます。ラベル付けされたアイテムの有限集合に対して、すべての弱い順序付けのペアは、この二分法の集合に一度に1つの二分法を追加または削除する一連の動きによって互いに接続される場合があります。さらに、弱い順序付けを頂点とし、これらの動きを辺とする無向グラフは、部分立方体を形成します。^[15]

幾何学的には、与えられた有限集合の全順序はパーミュトヘドロンの頂点として表され、この同じ集合上の二分法はパーミュトヘドロンの面として表される。この幾何学的表現では、集合上の弱い順序はパーミュトヘドロンのすべての異なる次元の面に対応する（パーミュトヘドロン自体は面として含まれるが、空集合は面として含まれない）。面の余次元は、対応する弱い順序の同値類の数を与える。^{[16]この幾何学的表現では、弱い順序上の動きの部分立方体は、パーミュトヘドロンの}面格子の被覆関係を記述するグラフである。

たとえば、3 つの要素のパーミュトヘドロンでは、正六角形になります。六角形の面格子 (この場合も、六角形自体を面として含みますが、空集合は含みません) には、1 つの六角形、6 つの辺、6 つの頂点の 13 個の要素があり、これらは 1 つの完全に同点の弱い順序、1 つの同点がある 6 つの弱い順序、および 6 つの合計順序に対応します。これらの 13 個の弱い順序の移動のグラフを図に示します。 ${\displaystyle n=3,}$

上で述べたように、弱い順序は効用理論に応用されている。^[12]線形計画法やその他の組み合わせ最適化問題では、解や基底の優先順位は、実数値の目的関数によって決定される弱い順序によって与えられることが多い。これらの順序付けにおける同点の現象は「退化」と呼ばれ、退化によって引き起こされる問題を防ぐために、この弱い順序付けを全順序付けに改良するために、いくつかの種類の同点解消規則が使用されてきた。^[17]

弱い順序はコンピュータサイエンスでも使われており、辞書式幅優先探索や辞書式位相順序付けのためのパーティション改良アルゴリズムに使われている。これらのアルゴリズムでは、グラフの頂点の弱い順序付け（頂点を分割する集合の族と、集合の全順序付けを提供する二重連結リストとして表される）がアルゴリズムの過程で徐々に改良され、最終的にアルゴリズムの出力である全順序付けが生成される。^[18]

C++プログラミング言語の標準ライブラリでは、セットおよびマルチセットデータ型は、テンプレートのインスタンス化時に指定され、厳密な弱い順序付けを実装すると想定される比較関数によって入力をソートします。^[2]

• 比較可能性 – 不等式によって関連付けられる要素の特性
• 先行順序 – 反射的および推移的な二項関係
• 弱成分 - 有向グラフの頂点の分割 − 与えられた関係と一致する最も細かい弱順序における同値な部分集合