一部注文済みのセット

数学、特に順序理論において、集合上の半順序とは、ある要素のペアについて、一方が他方より先に現れるような配置のことである。「半」という言葉は、すべての要素のペアが比較可能である必要はないことを示すために用いられる。つまり、どちらの要素も他方より先に現れないペアも存在し得る。したがって、半順序は、すべてのペアが比較可能である全順序を一般化したものである。

形式的には、半順序とは、反射的、反対称的、推移的な同質な二項関係である。半順序集合（略してposet ）とは、順序対のことである。${\displaystyle P=(X,\leq )}$一連の${\displaystyle X}$（グラウンドセットと呼ばれる）${\displaystyle P}$）と部分順序${\displaystyle \leq }$の上${\displaystyle X}$文脈から意味が明確で、部分順序に曖昧さがない場合、集合は${\displaystyle X}$それ自体は、時として半順序集合と呼ばれる。

部分順序という用語は通常、反射的な部分順序関係を指し、この記事ではこれを非厳密な部分順序と呼びます。しかし、一部の著者は、もう一つの一般的なタイプの部分順序関係である非反射的な部分順序関係（厳密な部分順序とも呼ばれる）に対してこの用語を使用します。厳密な部分順序と非厳密な部分順序は1対1に対応させることができるため、すべての厳密な部分順序には一意の対応する非厳密な部分順序が存在し、その逆もまた同様です。

厳密な部分順序関係と非厳密な部分順序関係の対応関係

集合上の厳密な部分順序と非厳密な部分順序${\displaystyle P}$密接に関連している。非厳密な部分順序${\displaystyle \leq }$形式のすべての関係を削除することにより、厳密な部分順序に変換できます。${\displaystyle a\leq a;}$すなわち、厳密な半順序は集合である${\displaystyle <\;:=\ \leq \ \setminus \ \Delta _{P}}$どこ${\displaystyle \Delta _{P}:=\{(p,p):p\in P\}}$は恒等関係です${\displaystyle P\times P}$そして${\displaystyle \;\setminus \;}$は集合の減算を表します。逆に、 は厳密な部分順序 < を表します。${\displaystyle P}$その形式のすべての関係を隣接させることにより、非厳密な部分順序に変換できます。つまり、${\displaystyle \leq \;:=\;\Delta _{P}\;\cup \;<\;}$は非厳密な半順序です。したがって、${\displaystyle \leq }$が非厳密な半順序である場合、対応する厳密な半順序 < は、次式で与えられる 非反射的カーネルである。$${\displaystyle a<b{\text{ if }}a\leq b{\text{ and }}a\neq b.}$$ 逆に、< が厳密な半順序である場合、対応する非厳密な半順序は${\displaystyle \leq }$反射閉包は次のように表される。 $${\displaystyle a\leq b{\text{ if }}a<b{\text{ or }}a=b.}$$

集合が与えられた${\displaystyle P}$そして、半順序関係（典型的には非厳密半順序）${\displaystyle \leq }$我々は、独自の方法で表記法を拡張して、4つの部分順序関係を定義することができる。${\displaystyle \leq ,}$${\displaystyle <,}$${\displaystyle \geq ,}$そして${\displaystyle >}$、 どこ${\displaystyle \leq }$は、非厳密な部分順序関係である。${\displaystyle P}$、${\displaystyle <}$は、関連する厳密な部分順序関係です。${\displaystyle P}$（反射しない核）${\displaystyle \leq }$)${\displaystyle \geq }$は${\displaystyle \leq }$、 そして${\displaystyle >}$は${\displaystyle <}$厳密に言えば、部分順序集合という用語は、これらの関係がすべて適切に定義された集合を指します。しかし実際には、単一の関係だけを考慮すれば十分です。${\displaystyle (P,\leq )}$または${\displaystyle (P,<)}$または、まれなケースでは、非厳密な関係と厳密な関係が一緒に、${\displaystyle (P,\leq ,<)}$[ ^{5 ]​}

順序集合という用語は、文脈から他の種類の順序を意味していないことが明確である限り、部分順序集合の略記として使用されることがあります。特に、完全順序集合も「順序集合」と呼ばれることがあり、特にこれらの構造が半順序集合よりも一般的な分野ではそうです。一部の著者は、異なる記号を使用しています。${\displaystyle \leq }$のような${\displaystyle \sqsubseteq }$^{[ 6 ]}または${\displaystyle \preceq }$^{[ 7 ]}部分順序と全順序を区別するため。

部分順序を参照する場合、${\displaystyle \leq }$補語として解釈すべきではない${\displaystyle >}$関係${\displaystyle >}$は、非反射核の逆である。${\displaystyle \leq }$これは常に の補集合の部分集合である${\displaystyle \leq }$、 しかし${\displaystyle >}$は、の補数に等しい。${\displaystyle \leq }$の場合に限り、${\displaystyle \leq }$は全順序である。^{[ a ]}

コンピュータサイエンスで見られる、部分順序を定義するもう1つの方法は、比較の概念を用いることです。具体的には、${\displaystyle \leq ,<,\geq ,{\text{ and }}>}$前述のように、2つの要素xとyは、互いに排他的な4つの関係のいずれかをとる可能性があることがわかります。すなわち、 x < y、x = y、x > y、またはxとyは比較できない、のいずれかです。これは関数で表すことができます。${\displaystyle {\text{compare}}:P\times P\to \{<,>,=,\vert \}}$2 つの要素が与えられたときに 4 つのコードのいずれかを返す。^{[ 8 ] [ 9 ]}この定義は、集合の等価性ではなく定義された同値関係として等価性が取られる集合の半順序と同等である。^{[ 10 ]}

ウォリスは、より一般的な半順序関係の概念を、推移的かつ反対称的な同質関係として定義している。これには、反射的および非反射的な半順序の両方がサブタイプとして含まれる。^{[ 1 ]}

有限半順序集合はハッセ図によって視覚化できる。^{[ 11 ]}具体的には、厳密な半順序関係をとると、${\displaystyle (P,<)}$有向非巡回グラフ(DAG) は、各要素を${\displaystyle P}$ノードであり、各要素は${\displaystyle <}$エッジとなる。このDAG ^{[ b ]}の推移的縮小がハッセ図となる。同様に、このプロセスを逆にして、特定のDAGから厳密な部分順序を構築することができる。対照的に、非厳密な部分順序に関連付けられたグラフは、すべてのノードに自己ループを持つため、DAGではない。非厳密な順序がハッセ図で表されていると言われる場合、実際には対応する厳密な順序が示されている。

数学において出現する半順序集合の標準的な例としては、以下のようなものがある。

• 実数、あるいは一般に、標準的な小等号関係 ≤ によって順序付けられた任意の全順序集合は、半順序である。
• 実際の数字について${\displaystyle \mathbb {R} }$通常の「より小さい」関係 < は厳密な半順序である。通常の「より大きい」関係 > についても同様である。${\displaystyle \mathbb {R} }$。
• 定義上、すべての厳密な弱順序は厳密な半順序である。
• 与えられた集合の部分集合（その冪集合）を包含関係で順序付けしたもの（図1参照）。同様に、部分列で順序付けされたシーケンス の集合、および部分文字列で順序付けされた文字列の集合。
• 整除性という関係を備えた自然数の集合。（図3および図6を参照）  
• 到達可能性によって順序付けられた有向非巡回グラフの頂点集合。
• ベクトル空間の部分空間の集合を、包含関係によって順序付けしたもの。
• 半順序集合Pに対して、Pの要素のすべてのシーケンスを含むシーケンス空間。シーケンスaは、シーケンスbの対応する要素がaのすべての項目より前に来る場合に、シーケンスbより前に来る。形式的には、${\displaystyle \left(a_{n}\right)_{n\in \mathbb {N} }\leq \left(b_{n}\right)_{n\in \mathbb {N} }}$かつその場合に限り${\displaystyle a_{n}\leq b_{n}}$すべての人々のために${\displaystyle n\in \mathbb {N} }$;つまり、コンポーネントごとの順序。
• 集合Xと半順序集合Pに対して、XからPへのすべての関数を含む関数空間は、f ≤ gであるのは、すべてのx に対してf ( x ) ≤ g ( x )である場合に限る。${\displaystyle x\in X.}$
• フェンスとは、順序関係a < b > c < d ...の交互のシーケンスによって定義される部分的に順序付けられた集合である。
• 特殊相対性理論およびほとんどの場合^{[ c ]}一般相対性理論における事象の集合で、2つの事象XとYについて、YがXの未来の光円錐内にある場合に限りX ≤ Yとなる。事象Yは、 X ≤ Yの場合にのみXによって因果的に影響を受ける。

部分的に順序付けられた集合の身近な例として、系譜上の子孫関係に基づいて並べられた人々の集合が挙げられる。ある人々のペアは子孫と祖先の関係にあるが、他の人々のペアは比較不可能であり、どちらも相手の子孫ではない。

部分的に順序付けられた集合のデカルト積の順序

図4a辞書順${\displaystyle \mathbb {N} \times \mathbb {N} }$

図4b製品の注文${\displaystyle \mathbb {N} \times \mathbb {N} }$

図4c厳密な直積順序の反射閉包${\displaystyle \mathbb {N} \times \mathbb {N} .}$(3, 3)で覆われている要素と、 (3, 3)を覆っている要素は、それぞれ緑色と赤色で強調表示されます。

強さの増減順、つまりペアの集合の減少順に、 2つの部分順序集合のデカルト積上の可能な部分順序のうち3つは次のとおりである（図 4参照）。

• 辞書順: ( 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 ) の場合)。 

これら3つはすべて、2つ以上の集合の直積についても同様に定義できる。

同じ体上の順序付きベクトル空間に適用した場合、結果はいずれの場合も順序付きベクトル空間となる。

完全順序集合のデカルト積の順序も参照してください。

例では半順序集合を使用しています${\displaystyle ({\mathcal {P}}(\{x,y,z\}),\subseteq )}$3つの要素からなる集合のすべての部分集合の集合から成る${\displaystyle \{x,y,z\},}$集合の包含関係に基づいて順序付けられています（図 1を参照）。

• a ≤ bの場合、aはbと関係 があります。これは、 bもaと関係があることを意味するものではありません。なぜなら、その関係は対称である必要はないからです。たとえば、${\displaystyle \{x\}}$は${\displaystyle \{x,y\},}$しかし、その逆は当てはまらない。
• aとbは、 a ≤ bまたはb ≤ aの場合に比較可能です。それ以外の場合は比較できません。たとえば、${\displaystyle \{x\}}$そして${\displaystyle \{x,y,z\}}$比較可能である一方、${\displaystyle \{x\}}$そして${\displaystyle \{y\}}$そうではない。
• 全順序または線形順序とは、すべての要素のペアが比較可能であるような部分順序のことです。つまり、三分割法が成り立ちます。例えば、自然数とその標準順序がこれに該当します。
• 鎖とは、全順序集合である半順序集合の部分集合のことです。例えば、${\displaystyle \{\{\,\},\{x\},\{x,y,z\}\}}$鎖です​​。
• 反鎖とは、2つの異なる要素が比較できない半順序集合の部分集合のことである。例えば、単一要素の集合${\displaystyle \{\{x\},\{y\},\{z\}\}.}$
• 要素aは、 a ≤ bかつ、かつ、要素bより厳密に小さいと言われる。${\displaystyle a\neq b.}$例えば、${\displaystyle \{x\}}$より厳密に小さい${\displaystyle \{x,y\}.}$
• 要素aが別の要素bに覆われていると言われるのは、a がbより厳密に小さく、その間に第 3 の要素 c が入らない場合です。正式には、 a ≤ bかつ${\displaystyle a\neq b}$は真であり、各cに対してa ≤ c ≤ bは偽である。${\displaystyle a\neq c\neq b.}$厳密な順序 < を使用すると、関係a ⋖ bは「任意のcに対してa < bだがa < c < bではない」と同等に言い換えることができます。たとえば、${\displaystyle \{x\}}$カバーされている${\displaystyle \{x,z\},}$しかし、${\displaystyle \{x,y,z\}.}$

エクストリーマ

半順序集合における「最大」要素と「最小」要素にはいくつかの概念がある。${\displaystyle P,}$特に：

• 最大の要素と最小の要素：要素${\displaystyle g\in P}$最大の要素は${\displaystyle a\leq g}$すべての要素について${\displaystyle a\in P.}$要素${\displaystyle m\in P}$最小要素である場合${\displaystyle m\leq a}$すべての要素について${\displaystyle a\in P.}$半順序集合は、最大要素または最小要素を 1 つしか持つことができません。この例では、集合は${\displaystyle \{x,y,z\}}$は最大の要素であり、${\displaystyle \{\,\}}$最も少ない。
• 最大要素と最小要素：要素${\displaystyle g\in P}$要素が存在しない場合、それは極大要素である。${\displaystyle a\in P}$そのため${\displaystyle a>g.}$同様に、要素${\displaystyle m\in P}$要素が存在しない場合は最小要素です${\displaystyle a\in P}$そのため${\displaystyle a<m.}$半順序集合に最大要素が存在する場合、それは唯一の最大要素でなければなりませんが、そうでない場合は最大要素が複数存在することができ、最小要素と極小要素についても同様です。実行中の例では、${\displaystyle \{x,y,z\}}$そして${\displaystyle \{\,\}}$これらは最大要素と最小要素です。これらを除くと、最大要素が3つ、最小要素が3つ残ります（図 5参照）。
• 上限と下限：集合Pの部分集合Aに対して、 Pの要素xは、 Aの各要素aについてa ≤ xが成り立つ場合、 Aの上限となります。特に、x はAの上限となるためにAに含まれる必要はありません。同様に、 Pの要素xは、 Aの各要素aについてa ≥ xが成り立つ場合、 Aの下限となります。P の最大要素はP自体の上限であり、最小要素はPの下限です。この例では、集合は    ${\displaystyle \{x,y\}}$は要素の集合の上限です${\displaystyle \{\{x\},\{y\}\}.}$

別の例として、正の整数を割り切れる順に並べた例を考えてみましょう。1は他のすべての要素を割り切るので最小要素ですが、この半順序集合には最大要素がありません。この半順序集合には最大要素も存在しません。例えば、任意のgは2gを割り切るので、gは最大要素ではありません。1より大きい要素の順序を割り切れるという条件を維持したまま、1を除外すると、結果として得られる半順序集合には最小要素はありませんが、任意の素数が最小要素になります。この半順序集合では、60は部分集合の上限（ただし最小上限ではない）です。${\displaystyle \{2,3,5,10\},}$1 は半順序集合に含まれていないため、下限はありません。一方、2 は 2 のべき乗の部分集合の下限であり、上限はありません。0 を含めると、これはすべての整数の倍数であるため、最大の要素になります (図 6 を参照)。

図7a順序を保存するが、順序を反映しない写像（f ( u )≼f ( v )であるが、uはそうではないため）${\displaystyle \leq }$v)

図7b 120の約数（割り切れるかどうかで部分的に順序付けられている）と{2, 3, 4, 5, 8}の約数閉部分集合（集合の包含関係で部分的に順序付けられている）との間の順序同型性

2 つの半順序集合( S , ≤)と( T , ≼)が与えられたとき、関数${\displaystyle f:S\to T}$すべての に対して が成り立つ場合、は順序保存、単調、または等調と呼ばれる。${\displaystyle x,y\in S,}$${\displaystyle x\leq y}$f ( x ) ≼ f ( y )を意味します。( U , ≲)も半順序集合であり、${\displaystyle f:S\to T}$そして${\displaystyle g:T\to U}$順序を保持する、その構成${\displaystyle g\circ f:S\to U}$順序保存機能も備えています。${\displaystyle f:S\to T}$すべての​${\displaystyle x,y\in S,}$f ( x ) ≼f ( y )は${\displaystyle x\leq y.}$f が順序保存かつ順序反映である 場合、それは( S , ≤)から( T , ≼)への順序埋め込みと呼ばれる。後者の場合、fは必然的に単射である。${\displaystyle f(x)=f(y)}$暗示する${\displaystyle x\leq y{\text{ and }}y\leq x}$そして今度は${\displaystyle x=y}$反対称性によれば${\displaystyle \leq .}$2 つの半順序集合SとTの間に順序埋め込みが存在する場合、 S はTに埋め込むことができると言います。${\displaystyle f:S\to T}$が全単射である場合、それは順序同型と呼ばれ、部分順序( S , ≤)と( T , ≼)は同型であると言われます。同型順序は構造的に類似したハッセ図を持ちます(図 7a を参照)。順序保存写像が${\displaystyle f:S\to T}$そして${\displaystyle g:T\to U}$存在するので${\displaystyle g\circ f}$そして${\displaystyle f\circ g}$それぞれSとT上で恒等関数が得られるので、SとTは順序同型である。^{[ 15 ]}

例えば、マッピング${\displaystyle f:\mathbb {N} \to \mathbb {P} (\mathbb {N} )}$自然数の集合（割り切れるかどうかで順序付けられている）から自然数の冪集合（集合の包含関係で順序付けられている）への写像は、各数をその素因数の集合に対応させることで定義できます。これは順序保存です。つまり、 x がy を割り切る場合、 xの各素因数はyの素因数でもあります。ただし、これは単射ではありません（12 と 6 の両方を写像するため）。${\displaystyle \{2,3\}}$）でも順序も反映しない（12は6を割り切れないため）。代わりに各数をその素数のべき乗の約数の集合に取り込むことで、写像が定義される。${\displaystyle g:\mathbb {N} \to \mathbb {P} (\mathbb {N} )}$これは順序保存写像であり、順序反映写像であり、したがって順序埋め込み写像である。これは順序同型写像ではない（例えば、どの数も集合に写像しないため）。${\displaystyle \{4\}}$）だが、その値域を に制限することで にすることができる。${\displaystyle g(\mathbb {N} ).}$図 7bは、${\displaystyle \mathbb {N} }$そして、 gによる同型像。このような順序同型を冪集合に構成することは、分配束と呼ばれる広いクラスの半順序に一般化できます。バーコフの表現定理を参照してください。

OEISのシーケンスA001035は、 n個のラベル付き要素の集合における部分順序の数を示します。

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

厳密な部分順序の数は、部分順序の数と同じである。

同型性までのみカウントすると、1、1、2、5、16、63、318、... （OEISのシーケンスA000112）というシーケンスが得られます。

半順序集合${\displaystyle P^{*}=(X^{*},\leq ^{*})}$別の半順序集合の部分順序集合と呼ばれる。${\displaystyle P=(X,\leq )}$ただし、${\displaystyle X^{*}}$は、​${\displaystyle X}$そして${\displaystyle \leq ^{*}}$は、${\displaystyle \leq }$後者の条件は、任意の${\displaystyle x}$そして${\displaystyle y}$で${\displaystyle X^{*}}$（したがって、${\displaystyle X}$）、 もし${\displaystyle x\leq ^{*}y}$それから${\displaystyle x\leq y}$。

もし${\displaystyle P^{*}}$は部分順序集合である${\displaystyle P}$さらに、すべての${\displaystyle x}$そして${\displaystyle y}$で${\displaystyle X^{*}}$、 いつでも${\displaystyle x\leq y}$また、${\displaystyle x\leq ^{*}y}$すると、私たちは${\displaystyle P^{*}}$部分順序集合${\displaystyle P}$誘発される${\displaystyle X^{*}}$、そして書く${\displaystyle P^{*}=P[X^{*}]}$。

部分順序${\displaystyle \leq ^{*}}$撮影現場で${\displaystyle X}$これは別の半順序の拡張と呼ばれます${\displaystyle \leq }$の上${\displaystyle X}$ただし、すべての要素について${\displaystyle x,y\in X,}$いつでも${\displaystyle x\leq y,}$また、${\displaystyle x\leq ^{*}y.}$線形拡張とは、線形（つまり全）順序でもある拡張のことである。古典的な例として、全順序集合の辞書式順序は、それらの積順序の線形拡張である。すべての半順序は全順序に拡張できる（順序拡張原理）。^{[ 16 ]}

コンピュータサイエンスでは、部分順序（有向非巡回グラフの到達可能性順序として表される）の線形拡張を見つけるアルゴリズムは、トポロジカルソートと呼ばれます。

すべての順序集合（およびすべての順序付き集合）は、オブジェクトに対して、${\displaystyle x}$そして${\displaystyle y,}$から最大で 1 つの射が存在する${\displaystyle x}$に${\displaystyle y.}$より具体的には、x ≤ yの場合hom( x , y ) = {( x , y )} (それ以外の場合は空集合) とし、${\displaystyle (y,z)\circ (x,y)=(x,z).}$このようなカテゴリーは、薄いと呼ばれることもあります。

半順序集合は、同型である場合に限り、互いに同値である。半順序集合において、最小の要素が存在する場合は始点対象、最大の要素が存在する場合は終点対象となる。また、すべての前順序集合は半順序集合と同値である。最後に、半順序集合のすべての部分圏は同型閉である。

もし${\displaystyle P}$は位相空間の構造も与えられた半順序集合である。その場合、慣例として、${\displaystyle \{(a,b):a\leq b\}}$位相積空間の閉部分集合である${\displaystyle P\times P.}$この仮定の下では、部分順序関係は極限において、${\displaystyle \lim _{i\to \infty }a_{i}=a,}$そして${\displaystyle \lim _{i\to \infty }b_{i}=b,}$そしてすべての${\displaystyle i,}$${\displaystyle a_{i}\leq b_{i},}$それから${\displaystyle a\leq b.}$^{[ 17 ]}

半順序集合Pにおける凸集合とは、 Pの部分集合Iであって、 Iの任意のxとy 、およびPの任意のzに対して、x ≤ z ≤ yならばzもIに含まれるという性質を持つ集合のことである。この定義は、実数の区間の定義を一般化したものである。幾何学における凸集合との混同が生じる可能性がある場合は、「凸」の代わりに「順序凸」という用語を用いる。

格子Lの凸部分格子とは、 Lの部分格子であり、かつLの凸集合でもある部分格子のことである。空でない凸部分格子はすべて、 Lのフィルタとイデアルの交点として一意に表現できる。

半順序集合Pにおける区間とは、区間表記で定義できる部分集合のことである。

• a ≤ bの場合、閉区間[ a , b ]は、 a ≤ x ≤ bを満たす要素xの集合です(つまり、a ≤ xかつx ≤ bです)。少なくとも要素aとbを含みます。
• 対応する厳密な関係「<」を用いると、開区間( a , b )はa < x < bを満たす要素xの集合(つまりa < xかつx < b ) です。開区間はa < bであっても空になることがあります。例えば、整数の開区間(0, 1)は、0 < x < 1となる整数x が存在しないため空です。
• 半開区間[ a , b )と( a , b ]も同様に定義されます。

a ≤ bが成り立たない場合、これらの区間はすべて空になります。すべての区間は凸集合ですが、その逆は成り立ちません。たとえば、120 の約数の半順序集合を割り切れる順に並べた場合 (図 7b を参照)、集合{1, 2, 4, 5, 8}は凸集合ですが、区間ではありません。

区間Iは、要素が存在する場合に有界である。${\displaystyle a,b\in P}$I ⊆ [ a , b ]となるような区間。区間表記で表せる区間は明らかに有界だが、その逆は真ではない。例えば、実数の部分順序集合としてP = (0, 1) ∪ (1, 2) ∪ (2, 3)とする。部分集合(1, 2)は有界区間だが、 Pには下限も上限もないので、 Pの要素を使って区間表記で表すことはできない。  

半順序集合は、すべての有界区間が有限である場合に局所的に有限であると呼ばれる。例えば、整数は自然順序の下で局所的に有限である。デカルト積の辞書式順序${\displaystyle \mathbb {N} \times \mathbb {N} }$は局所的に有限ではありません。なぜなら、(1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1)だからです。区間表記法を用いると、「 aはbで覆われている」という性質は、次のように言い換えることができます。${\displaystyle [a,b]=\{a,b\}.}$

部分順序における区間という概念は、区間順序として知られる特定の種類の部分順序と混同してはならない。

ウィキメディア・コモンズにあるハッセ図に関連するメディア。それぞれが半順序の例を示している。