一部注文済みのセット

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

形式的には、半順序とは、反射的、反対称的、推移的な同質な二項関係である。半順序集合（略して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つ以上の集合の直積についても同様に定義できる。

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

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

The examples use the poset ${\displaystyle ({\mathcal {P}}(\{x,y,z\}),\subseteq )}$ consisting of the set of all subsets of a three-element set ${\displaystyle \{x,y,z\},}$ ordered by set inclusion (see Fig. 1).

• a is related tob when a ≤ b. This does not imply that b is also related to a, because the relation need not be symmetric. For example, ${\displaystyle \{x\}}$ is related to ${\displaystyle \{x,y\},}$ but not the reverse.
• a and b are comparable if a ≤ b or b ≤ a. Otherwise they are incomparable. For example, ${\displaystyle \{x\}}$ and ${\displaystyle \{x,y,z\}}$ are comparable, while ${\displaystyle \{x\}}$ and ${\displaystyle \{y\}}$ are not.
• A total order or linear order is a partial order under which every pair of elements is comparable, i.e. trichotomy holds. For example, the natural numbers with their standard order.
• A chain is a subset of a poset that is a totally ordered set. For example, ${\displaystyle \{\{\,\},\{x\},\{x,y,z\}\}}$ is a chain.
• An antichain is a subset of a poset in which no two distinct elements are comparable. For example, the set of singletons${\displaystyle \{\{x\},\{y\},\{z\}\}.}$
• An element a is said to be strictly less than an element b, if a ≤ b and ${\displaystyle a\neq b.}$ For example, ${\displaystyle \{x\}}$ is strictly less than ${\displaystyle \{x,y\}.}$
• An element a is said to be covered by another element b, written a ⋖ b (or a <: b), if a is strictly less than b and no third element c fits between them; formally: if both a ≤ b and ${\displaystyle a\neq b}$ are true, and a ≤ c ≤ b is false for each c with ${\displaystyle a\neq c\neq b.}$ Using the strict order <, the relation a ⋖ b can be equivalently rephrased as "a < b but not a < c < b for any c". For example, ${\displaystyle \{x\}}$ is covered by ${\displaystyle \{x,z\},}$ but is not covered by ${\displaystyle \{x,y,z\}.}$

Extrema

There are several notions of "greatest" and "least" element in a poset ${\displaystyle P,}$ notably:

• Greatest element and least element: An element ${\displaystyle g\in P}$ is a greatest element if ${\displaystyle a\leq g}$ for every element ${\displaystyle a\in P.}$ An element ${\displaystyle m\in P}$ is a least element if ${\displaystyle m\leq a}$ for every element ${\displaystyle a\in P.}$ A poset can only have one greatest or least element. In our running example, the set ${\displaystyle \{x,y,z\}}$ is the greatest element, and ${\displaystyle \{\,\}}$ is the least.
• Maximal elements and minimal elements: An element ${\displaystyle g\in P}$ is a maximal element if there is no element ${\displaystyle a\in P}$ such that ${\displaystyle a>g.}$ Similarly, an element ${\displaystyle m\in P}$ is a minimal element if there is no element ${\displaystyle a\in P}$ such that ${\displaystyle a<m.}$ If a poset has a greatest element, it must be the unique maximal element, but otherwise there can be more than one maximal element, and similarly for least elements and minimal elements. In our running example, ${\displaystyle \{x,y,z\}}$ and ${\displaystyle \{\,\}}$ are the maximal and minimal elements. Removing these, there are 3 maximal elements and 3 minimal elements (see Fig. 5).
• Upper and lower bounds: For a subset A of P, an element x in P is an upper bound of A if a ≤ x, for each element a in A. In particular, x need not be in A to be an upper bound of A. Similarly, an element x in P is a lower bound of A if a ≥ x, for each element a in A. A greatest element of P is an upper bound of P itself, and a least element is a lower bound of P. In our example, the set ${\displaystyle \{x,y\}}$ is an upper bound for the collection of elements ${\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 .}$ If an order-embedding between two posets S and T exists, one says that S can be embedded into T. If an order-embedding ${\displaystyle f:S\to T}$ is bijective, it is called an order isomorphism, and the partial orders (S, ≤) and (T, ≼) are said to be isomorphic. Isomorphic orders have structurally similar Hasse diagrams (see Fig. 7a). It can be shown that if order-preserving maps ${\displaystyle f:S\to T}$ and ${\displaystyle g:T\to U}$ exist such that ${\displaystyle g\circ f}$ and ${\displaystyle f\circ g}$ yields the identity function on S and T, respectively, then S and T are order-isomorphic.^[15]

For example, a mapping ${\displaystyle f:\mathbb {N} \to \mathbb {P} (\mathbb {N} )}$ from the set of natural numbers (ordered by divisibility) to the power set of natural numbers (ordered by set inclusion) can be defined by taking each number to the set of its prime divisors. It is order-preserving: if x divides y, then each prime divisor of x is also a prime divisor of y. However, it is neither injective (since it maps both 12 and 6 to ${\displaystyle \{2,3\}}$) nor order-reflecting (since 12 does not divide 6). Taking instead each number to the set of its prime power divisors defines a map ${\displaystyle g:\mathbb {N} \to \mathbb {P} (\mathbb {N} )}$ that is order-preserving, order-reflecting, and hence an order-embedding. It is not an order-isomorphism (since it, for instance, does not map any number to the set ${\displaystyle \{4\}}$), but it can be made one by restricting its codomain to ${\displaystyle g(\mathbb {N} ).}$ Fig. 7b shows a subset of ${\displaystyle \mathbb {N} }$ and its isomorphic image under g. The construction of such an order-isomorphism into a power set can be generalized to a wide class of partial orders, called distributive lattices; see Birkhoff's representation theorem.

Sequence A001035 in OEIS gives the number of partial orders on a set of n labeled elements:

Note that S(n, k) refers to Stirling numbers of the second kind.

The number of strict partial orders is the same as that of partial orders.

If the count is made only up to isomorphism, the sequence 1, 1, 2, 5, 16, 63, 318, ... (sequence A000112 in the OEIS) is obtained.

A poset ${\displaystyle P^{*}=(X^{*},\leq ^{*})}$ is called a subposet of another poset ${\displaystyle P=(X,\leq )}$ provided that ${\displaystyle X^{*}}$ is a subset of ${\displaystyle X}$ and ${\displaystyle \leq ^{*}}$ is a subset of ${\displaystyle \leq }$. The latter condition is equivalent to the requirement that for any ${\displaystyle x}$ and ${\displaystyle y}$ in ${\displaystyle X^{*}}$ (and thus also in ${\displaystyle X}$), if ${\displaystyle x\leq ^{*}y}$ then ${\displaystyle x\leq y}$.

If ${\displaystyle P^{*}}$ is a subposet of ${\displaystyle P}$ and furthermore, for all ${\displaystyle x}$ and ${\displaystyle y}$ in ${\displaystyle X^{*}}$, whenever ${\displaystyle x\leq y}$ we also have ${\displaystyle x\leq ^{*}y}$, then we call ${\displaystyle P^{*}}$ the subposet of ${\displaystyle P}$induced by ${\displaystyle X^{*}}$, and write ${\displaystyle P^{*}=P[X^{*}]}$.

A partial order ${\displaystyle \leq ^{*}}$ on a set ${\displaystyle X}$ is called an extension of another partial order ${\displaystyle \leq }$ on ${\displaystyle X}$ provided that for all elements ${\displaystyle x,y\in X,}$ whenever ${\displaystyle x\leq y,}$ it is also the case that ${\displaystyle x\leq ^{*}y.}$ A linear extension is an extension that is also a linear (that is, total) order. As a classic example, the lexicographic order of totally ordered sets is a linear extension of their product order. Every partial order can be extended to a total order (order-extension principle).^[16]

In computer science, algorithms for finding linear extensions of partial orders (represented as the reachability orders of directed acyclic graphs) are called topological sorting.

Every poset (and every preordered set) may be considered as a category where, for objects ${\displaystyle x}$ and ${\displaystyle y,}$ there is at most one morphism from ${\displaystyle x}$ to ${\displaystyle y.}$ More explicitly, let hom(x, y) = {(x, y)} if x ≤ y (and otherwise the empty set) and ${\displaystyle (y,z)\circ (x,y)=(x,z).}$ Such categories are sometimes called thin.

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

もし${\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\}.}$

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

Media related to Hasse diagrams at Wikimedia Commons; each of which shows an example for a partial order