弱い順序付け

Preliminaries on incomparability and transitivity of incomparability

Two elements ${\displaystyle x}$ and ${\displaystyle y}$ of ${\displaystyle S}$ are said to be incomparable with respect to ${\displaystyle \,<\,}$ if neither ${\displaystyle x<y}$ nor ${\displaystyle y<x}$ is true.^[1] A strict partial order${\displaystyle \,<\,}$ is a strict weak ordering if and only if incomparability with respect to ${\displaystyle \,<\,}$ is an equivalence relation. Incomparability with respect to ${\displaystyle \,<\,}$ is always a homogeneous symmetric relation on ${\displaystyle S.}$ It is reflexive if and only if ${\displaystyle \,<\,}$ is irreflexive (meaning that ${\displaystyle x<x}$ is always false), which will be assumed so that transitivity is the only property this "incomparability relation" needs in order to be an equivalence relation.

Define also an induced homogeneous relation ${\displaystyle \,\lesssim \,}$ on ${\displaystyle S}$ by declaring that $${\displaystyle x\lesssim y{\text{ が真であるのは、 y<x{\text{ が偽である場合に限る}}}$$ where importantly, this definition is not necessarily the same as: ${\displaystyle x\lesssim y}$ if and only if ${\displaystyle x<y{\text{ または }}x=y.}$ Two elements ${\displaystyle x,y\in S}$ are incomparable with respect to ${\displaystyle \,<\,}$ if and only if ${\displaystyle x{\text{ および }}y}$ are equivalent with respect to ${\displaystyle \,\lesssim \,}$ (or less verbosely, ${\displaystyle \,\lesssim }$-equivalent), which by definition means that both ${\displaystyle x\lesssim y{\text{ および }}y\lesssim x}$ are true. The relation "are incomparable with respect to ${\displaystyle \,<}$" is thus identical to (that is, equal to) the relation "are ${\displaystyle \,\lesssim }$-equivalent" (so in particular, the former is transitive if and only if the latter is). When ${\displaystyle \,<\,}$ is irreflexive then the property known as "transitivity of incomparability" (defined below) is exactly the condition necessary and sufficient to guarantee that the relation "are ${\displaystyle \,\lesssim }$-equivalent" does indeed form an equivalence relation on ${\displaystyle S.}$ この場合、任意の2つの要素が${\displaystyle x,y\in S}$満足${\displaystyle x\lesssim y{\text{ および }}y\lesssim x}$単一のオブジェクトとして識別される（具体的には、共通の同値クラスで一緒に識別される）。

意味

集合上の厳密な弱順序付け${\displaystyle S}$厳密な半順序である${\displaystyle \,<\,}$の上${\displaystyle S}$比較不可能な関係が引き起こす${\displaystyle S}$による${\displaystyle \,<\,}$は推移関係である。^{[ 1 ]} 具体的には、 上の厳密な弱順序は${\displaystyle S}$同次関係${\displaystyle \,<\,}$の上${\displaystyle S}$以下の4つの特性をすべて備えているもの：

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 }$-同等であり、また$yとz$は${\displaystyle \,\lesssim }$等価であれば必然的に${\displaystyle x{\text{ and }}z}$は${\displaystyle \,\lesssim }$-同等。これは次のように言い換えることもできます。${\displaystyle x\lesssim y{\text{ and }}y\lesssim x}$そしてまた${\displaystyle y\lesssim z{\text{ and }}z\lesssim y}$そうすれば必然的に${\displaystyle x\lesssim z{\text{ and }}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{ if and only if }}a<b}$一部の（あるいは同等に、すべての）代表者にとって${\displaystyle a\in A{\text{ and }}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.}$

全順序とは、反対称な全前順序、つまり部分順序のことである。全前順序は、選好関係とも呼ばれることがある。

厳密弱順序の補集合は全前順序であり、その逆もまた然りですが、厳密弱順序と全前順序の関係は、要素の順序を反転させるのではなく、保持する形で関連付ける方がより自然です。したがって、補集合の逆をとります。厳密弱順序の場合、${\displaystyle \,<,}$総予約数を定義する${\displaystyle \,\lesssim \,}$設定することで${\displaystyle x\lesssim y}$常にそうでない場合は${\displaystyle y<x.}$反対に、全前順序から厳密な弱順序 < を定義する${\displaystyle \,\lesssim ,}$セット${\displaystyle x<y}$常にそうでない場合は${\displaystyle y\lesssim x.}$^{[ 8 ]}

任意の順序関係には、2 つの要素が対応する同値関係が存在する。${\displaystyle x}$そして${\displaystyle y}$等価であると定義されるのは、${\displaystyle x\lesssim y{\text{ and }}y\lesssim x.}$全順序の場合、同値類集合上の対応する部分順序は全順序となる。2つの要素が全順序において同値であるのは、対応する厳密弱順序において比較不能である場合に限る。

集合の分割${\displaystyle S}$は、空でない互いに素な部分集合の族である。${\displaystyle S}$持っている${\displaystyle S}$それらの和集合として。分割は、分割された集合上の全順序とともに、リチャード・P・スタンレーによって順序付き分割^{[ 9 ]} 、セオドア・モツキンによって集合のリスト[ ^{10 ]と}呼ばれる構造を与える。有限集合の順序付き分割は、分割内の集合の有限列として記述できる。例えば、集合の3つの順序付き分割は、${\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).}$

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

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

より一般的に言えば、${\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}$は単射関数なので、 上の 2 つの同値な要素のクラス${\displaystyle Y}$等価要素のより大きなクラスを誘発する可能性がある${\displaystyle X.}$また、${\displaystyle f}$全射関数であるとは想定されていないため、上の同値要素のクラスは${\displaystyle Y}$より小さいクラスまたは空のクラスを誘発する可能性があります${\displaystyle X.}$しかし、その機能は${\displaystyle f}$分割を写像する単射関数を誘導する${\displaystyle X}$それについて${\displaystyle Y.}$したがって、有限分割の場合、クラスの数は${\displaystyle X}$クラスの数以下${\displaystyle Y.}$

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

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

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

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

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

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

例えば、${\displaystyle n=3,}$3つの要素からなる順列多面体は、正六角形です。この六角形の面格子（ここでも、六角形自体を面として含めますが、空集合は含めません）は、13個の要素から構成されます。1つの六角形、6つの辺、6つの頂点です。これらは、完全に同点の弱い順序付け1つ、同点の弱い順序付け6つ、および全順序付け6つに対応します。これらの13個の弱い順序付けにおける移動のグラフを図に示します。