半順序集合

図1包含順序に従って並べられた3要素集合のすべての部分集合のハッセ図。上向きのパスで結ばれた集合、例えばと は比較可能だが、と は比較不可能である。${\displaystyle \{x,y,z\},}$ ${\displaystyle \emptyset }$ ${\displaystyle \{x,y\}}$ ${\displaystyle \{x\}}$ ${\displaystyle \{y\}}$

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

正式には、半順序とは、反射的、反対称的、推移的な同次二項関係です。半順序集合（半順序集合、略してposet）とは、集合（の基底集合と呼ばれる）と半順序からなる順序付きペアです。文脈から意味が明確で、半順序に曖昧さがない場合は、集合自体をposetと呼ぶことがあります。 ${\displaystyle P=(X,\leq )}$ ${\displaystyle X}$ ${\displaystyle P}$ ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle X}$

半順序関係

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

部分注文

再帰的な、弱い、 [ ^1]または非厳密半順序^[2]、半順序とも呼ばれ、反射的、反対称的、推移的な集合上同次関係≤。つまり、すべてのに対して以下を満たす必要がある。 ${\displaystyle P}$ ${\displaystyle a,b,c\in P,}$

1. 反射性：つまり、すべての要素はそれ自体に関連しています。${\displaystyle a\leq a}$
2. 反対称性: かつ の場合、つまり2 つの異なる要素が互いに先行することはない。${\displaystyle a\leq b}$ ${\displaystyle b\leq a}$ ${\displaystyle a=b}$
3. 推移性: ifかつthen 。${\displaystyle a\leq b}$ ${\displaystyle b\leq c}$ ${\displaystyle a\leq c}$

非厳密な半順序は、反対称前順序とも呼ばれます。

厳密な半順序

非反射的な強い[ 1 ^]または厳密な半順序は、非反射的、非対称的、推移的な集合上の同次関係<である。つまり、すべての${\displaystyle P}$ ${\displaystyle a,b,c\in P:}$

1. 非反射性: つまり、どの要素もそれ自体とは関連がありません (反反射性とも呼ばれます)。${\displaystyle \neg \left(a<a\right)}$
2. 非対称性: if then not 。${\displaystyle a<b}$ ${\displaystyle b<a}$
3. 推移性: ifかつthen 。${\displaystyle a<b}$ ${\displaystyle b<c}$ ${\displaystyle a<c}$

推移的関係は、それが非反射的である場合にのみ非対称的である。^[3]したがって、非反射性または非対称性のどちらか一方を省略した場合（両方を省略した場合ではない）でも定義は同じである。

厳密な半順序は、厳密な事前順序とも呼ばれます。

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

図2 厳密な関係と非厳密な関係とその双対関係の関係に関する可換図。反射閉包（ cls）、非反射核（ker）、逆関係（cnv ）の操作を用いて表される。各関係は、中央にハッセ図が描かれたポセットの論理行列で表される。例えば、左下の行列の3行4列目は空である。${\displaystyle 3\not \leq 4}$

集合上の厳密な半順序と非厳密な半順序は密接に関連しています。非厳密な半順序は、 という形式の関係をすべて削除することで厳密な半順序に変換できます。つまり、 という厳密な半順序は、 が上の恒等関係であり、 が集合の減算を表す集合です。逆に、 上の厳密な半順序 < は、その形式の関係をすべて付加することで非厳密な半順序に変換できます。つまり、は非厳密な半順序です。したがって、が非厳密な半順序である場合、対応する厳密な半順序 < は、次で示される 非反射核です 。逆に、 < が厳密な半順序である場合、対応する非厳密な半順序は、次で示される反射閉包です。 ${\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.}$$

二重注文

半順序関係の双対（または反対）は、を の逆関係とすることで定義されます。つまり、のときのみ、 となります。非厳密な半順序の双対は非厳密な半順序であり、^[4]厳密な半順序の双対は厳密な半順序です。関係の双対の双対は元の関係です。 ${\displaystyle R^{\text{op}}}$ ${\displaystyle R}$ ${\displaystyle R^{\text{op}}}$ ${\displaystyle R}$ ${\displaystyle xR^{\text{op}}y}$ ${\displaystyle yRx}$

表記

集合と半順序関係（通常は非厳密な半順序 ）が与えられれば、表記を一意に拡張して 4 つの半順序関係 および を定義できます。ここでは 上の非厳密な半順序関係、は（の非反射核）上の関連付けられた厳密な半順序関係、は の双対、は の双対です。厳密に言えば、半順序集合という用語は、これらすべての関係が適切に定義された集合を指します。しかし実際には、 という 1 つの関係だけを考えれば十分です。あるいは、まれなケースでは、非厳密な関係と厳密な関係を一緒に考えれば十分です。^[5]${\displaystyle P}$ ${\displaystyle \leq }$ ${\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 ,<)}$

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

半順序について言及する場合、は の補集合として捉えるべきではない。この関係は の非反射核の逆であり、 は常に の補集合の部分集合となるが、が全順序である場合、かつ がの補集合である場合に限り、 は に等しい。^[a]${\displaystyle \leq }$ ${\displaystyle >}$ ${\displaystyle >}$ ${\displaystyle \leq }$ ${\displaystyle \leq }$ ${\displaystyle >}$ ${\displaystyle \leq }$ ${\displaystyle \leq }$

代替定義

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

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

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

例

図3 1から4までの数の割り切れるグラフ。この集合は部分的に順序付けられているが、完全に順序付けられているわけではない。1から他のすべての数への関係があるが、2から3や3から4への関係はないからである。

数学で生じる半順序集合の標準的な例には次のものがあります。

• 実数、または一般に、標準的な以下関係 ≤ で順序付けられた完全に順序付けられた任意の集合は、半順序です。
• 実数 において、通常の「より小さい」関係 < は厳密な半順序関係である。 における通常の「より大きい」関係 > についても同様である。${\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とは常にf ( x ) ≤ g ( x )がすべての関数に対して成り立つときである。${\displaystyle x\in X.}$
• フェンスは、順序関係a < b > c < d ...の交互のシーケンスによって定義される部分的に順序付けられたセットです。
• 特殊相対性理論、および多くの場合^[c] 一般相対性理論における事象の集合。2つの事象XとYに対して、X ≤ Yは、 YがXの未来光円錐内にある場合にのみ成立する。事象YがXの因果的影響を受けるのは、X ≤ Yの場合のみである。

半順序集合のよく知られた例としては、系図上の子孫順に並べられた人々の集合が挙げられます。子孫と祖先の関係を持つペアもあれば、どちらも他方の子孫ではない、比較不可能なペアもあります。

半順序集合の直積上の順序

強度が増す順に、つまりペアのセットが減少する順に、2 つの半順序付きセットの直積上の可能な半順序のうち 3 つは次のとおりです (図 4 を参照)。

• 辞書式順序：   a < cまたは ( a = cかつb ≤ d )の場合、( a、b )≤( c、d )。
• 積の順序: a ≤ cかつb ≤ dの場合、 ( a , b ) ≤ ( c , d ) 。
• 対応する厳密順序の   直積の反射閉包: ( a , b ) ≤ ( c , d ) 、 ( a < cかつb < d ) または ( a = cかつb = d ) の場合。

これら 3 つは、3 つ以上のセットの直積に対しても同様に定義できます。

同じ体上の順序付きベクトル空間に適用すると、結果はそれぞれの場合も順序付きベクトル空間になります。

全順序集合の直積の順序も参照してください。

半順序集合の和

2つの（互いに素な）半集合を結合する別の方法は順序和^[12]（または線形和）^[13] Z = X ⊕ Yであり、これは基底集合XとYの和集合上で順序a ≤ _Z bによって定義され、次の場合に限ります。

• a , b ∈ X（a ≤ _X b ）、または
• a , b ∈ Y（a ≤ _Y b ）、または
• a ∈ Xかつb ∈ Y。

2つの半順序集合が順序付けられている場合、それらの順序和も順序付けられます。^[14]

直列並列半順序は、順序和演算（この文脈では直列合成と呼ばれる）と並列合成と呼ばれる演算から構成されます。並列合成とは、 2つの半順序集合の互いに素な和集合であり、一方の集合の要素ともう一方の集合の要素の間に順序関係はありません。

派生概念

例では、集合の包含順に並べられた3 要素集合のすべての部分集合からなるposet を使用します(図 1 を参照)。 ${\displaystyle ({\mathcal {P}}(\{x,y,z\}),\subseteq )}$ ${\displaystyle \{x,y,z\},}$

• 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\}}$
• 全順序または線型順序とは、すべての要素のペアが比較可能な半順序、すなわち三分法が成立する順序です。例えば、標準順序を持つ自然数が挙げられます。
• 連鎖とは、全順序集合である poset の部分集合です。例えば、は連鎖です。${\displaystyle \{\{\,\},\{x\},\{x,y,z\}\}}$
• 反連鎖とは、2つの異なる要素が比較できないような半集合の部分集合である。例えば、単集合の集合は ${\displaystyle \{\{x\},\{y\},\{z\}\}.}$
• 要素aが要素bより真に小さいとは、a ≤ bかつ例えば が真に小さいときである。${\displaystyle a\neq b.}$ ${\displaystyle \{x\}}$ ${\displaystyle \{x,y\}.}$
• 要素aが別の要素bによって覆われている（ a ⋖ b（またはa <: b）と表記）とは、 a がbより厳密に小さく、かつ 3 番目の要素c がそれらの間に位置しない場合である。正式には、a ≤ bと が両方とも真であり、かつ が成り立つ各cに対してa ≤ c ≤ bが偽である場合である。厳密な順序 < を用いると、関係a ⋖ b は「任意のcに対してa < bだがa < c < bではない」と言い換えることができる。例えば、は によって覆われているが は によって覆われていない。${\displaystyle a\neq b}$ ${\displaystyle a\neq c\neq b.}$ ${\displaystyle \{x\}}$ ${\displaystyle \{x,z\},}$ ${\displaystyle \{x,y,z\}.}$

極値

図5最大元と最小元を取り除いた上の図。この縮約されたポーズセットでは、上段の要素はすべて最大元であり、下段の要素はすべて最小元であるが、最大元と最小元は存在しない。

poset には「最大」要素と「最小」要素の概念がいくつかあります。 ${\displaystyle P,}$

• 最大元と最小元：ある元が最大元であるとは、すべての元に対してであることを意味します。ある元が最小元であるとは、すべての元に対してであることを意味します。半集合は最大元または最小元を1つしか持つことができません。この例では、集合は最大元であり、最小元です。${\displaystyle g\in P}$ ${\displaystyle a\leq g}$ ${\displaystyle a\in P.}$ ${\displaystyle m\in P}$ ${\displaystyle m\leq a}$ ${\displaystyle a\in P.}$ ${\displaystyle \{x,y,z\}}$ ${\displaystyle \{\,\}}$
• 最大元と最小元： となる元が存在しないとき、その元は最大元である。同様に、 となる元が存在しないとき、その元は最小元である。 poset に最大元が存在する場合、それは唯一の最大元でなければならないが、そうでない場合は複数の最大元が存在する可能性がある。最小元と最小元についても同様である。実行例では、と が最大元と最小元である。これらを除くと、3つの最大元と3つの最小元が存在する（図5を参照）。${\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 \{\,\}}$
• 上限と下限： Pの部分集合Aにおいて、Aの各要素aについて、 a  ≤  xであるとき、 Pの要素 x はAの上限となる。特に、x がAの上限となるためにはAに存在する必要はない。同様に、 A の各要素 a について、a  ≥  xであるとき、 Pの要素xはAの下限となる。 Pの最大要素はP自身の上限であり、最小要素はPの下限である。この例では、集合は要素の集合の上限となる。${\displaystyle \{x,y\}}$ ${\displaystyle \{\{x\},\{y\}\}.}$

図6割り切れる順に並べられた非負整数の格子の一部

別の例として、割り切れる順で並べた正の整数を考えてみましょう。1 は他のすべての要素を割り切るので最小元です。一方で、この poset には最大元がありません。この部分的に順序付けられたセットには最大元さえありません。任意のgは、たとえばそれとは異なる2 gを割り切るので、 g は最大ではありません。数値 1 を除外し、割り切れるかどうかを 1 より大きい要素の順序として維持すると、結果の poset には最小元はありませんが、任意の素数はその最小元になります。この poset では、60 は、下限を持たない部分集合の上限です(1 は poset に含まれないため)。一方で、2 は 2 のべき乗の部分集合の下限であり、上限はありません。数値 0 が含まれる場合、これはすべての整数の倍数であるため、最大元になります (図 6 を参照)。 ${\displaystyle \{2,3,5,10\},}$

半順序集合間のマッピング

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

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

部分注文の数

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

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

厳密な半順序の数は半順序の数と同じです。

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

部分集合

がの部分集合であり、がの部分集合であるとき、その poset は別の poset の部分集合と呼ばれる。後者の条件は、における任意のおよび（したがって においても）に対して、ならばとなるという要件と同等である。 ${\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^{*}]}$

線形拡張

集合上の半順序は、任意の要素に対して常に次の条件を満たす、集合上の別の半順序の拡張と呼ばれる。線型拡張とは、線型（つまり全）順序でもある拡張である。典型的な例として、全順序集合の辞書式順序は、その積順序の線型拡張である。すべての半順序は全順序に拡張できる（順序拡張原理）。^[16]${\displaystyle \leq ^{*}}$ ${\displaystyle X}$ ${\displaystyle \leq }$ ${\displaystyle X}$ ${\displaystyle x,y\in X,}$ ${\displaystyle x\leq y,}$ ${\displaystyle x\leq ^{*}y.}$

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

カテゴリー理論では

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

半集合が互いに同値であるためには、それらが同型でなければならない。半集合において、最小の要素は（もし存在するなら）始対象であり、最大の要素は（もし存在するなら）終対象である。また、すべての順序付き集合は半集合と同値である。最後に、半集合のすべての部分圏は同型閉である。

位相空間における半順序

が位相空間の構造も与えられている半順序集合である場合、位相積空間の閉部分集合であると仮定するのが通例である。この仮定の下では、半順序関係は、すべてのに対してかつが成り立つ場合、次の意味で極限において良好に振る舞う。^[17]${\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.}$

間隔

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

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

poset P内の区間は、区間表記法で定義できる部分集合です。

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

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

区間Iが有界であるとは、 I ⊆ [ a , b ]を満たす元が存在する場合である。区間表記で表せるすべての区間は明らかに有界であるが、逆は真ではない。例えば、実数の部分集合としてP = (0, 1) ∪ (1, 2) ∪ (2, 3)を考える。部分集合(1, 2)は有界区間であるが、 Pには 最小値も最大値も存在しないため、 Pの元を用いた区間表記では表すことができない 。 ${\displaystyle a,b\in P}$

任意の有界区間が有限であるとき、半集合は局所有限であると呼ばれる。例えば、整数は自然順序付けのもとで局所有限である。直積上の辞書式順序は局所有限ではない。なぜなら、(1, 2) ≤ (1, 3) ≤ (1, 4) ≤ (1, 5) ≤ ... ≤ (2, 1) であるからである。区間記法を用いると、「 aはbによって覆われる」という性質は次のように言い換えられる。${\displaystyle \mathbb {N} \times \mathbb {N} }$ ${\displaystyle [a,b]=\{a,b\}.}$

半順序における区間の概念は、区間順序として知られる半順序の特定のクラスと混同しないでください。

参照

• 反マトロイド、半集合よりも一般的な順序付けの族を許容する集合上の順序付けの形式化
• 因果集合、量子重力へのポセットベースのアプローチ
• 比較可能性グラフ – 比較可能な要素のペアを半順序で結ぶグラフ
• 完全半順序 – 数学的表現
• 有向集合 – 上限を持つ数学的順序
• 段階付きポセット
• 結合代数 – 組合せ論で使用される結合代数
• 格子 – 最小値と最大値を持つペアの集合
• 局所有限半順序集合
• 半順序集合上のメビウス関数 – 組合せ論で用いられる結合代数
• ネストされたセットコレクション
• 順序多面体
• 順序体 – 順序構造を持つ代数的対象
• 順序付きグループ – 互換性のある半順序を持つグループPages displaying short descriptions of redirect targets
• 順序付きベクトル空間 – 半順序を持つベクトル空間
• ポセット位相幾何学は、任意のポセットから定義できる位相空間の一種である。
• スコット連続性– 2 つの半順序間の関数の連続性。
• 半格子 – 結合による半順序
• セミオーダー – 誤差のある数値順序
• シュピルライン拡張定理– すべての部分順序は何らかの全順序に含まれる。
• 確率的優位性 – 確率変数間の半順序
• 厳密な弱い順序付け- 関係「 a < bでもb < aでもない 」が推移的である厳密な半順序「<」。
• 全順序 – すべての要素が比較可能な順序
• ツォルンの補題 – 選択公理と同値な数学的命題

注記

1. 証明はここにあります。
2. は常に存在し、有限であると仮定されているので一意である。${\displaystyle P}$
3. 一般相対性理論§タイムトラベルを参照。

引用

1. Wallis, WD (2013年3月14日). 『離散数学入門』 Springer Science & Business Media. p. 100. ISBN 978-1-4757-3826-1。
2. Simovici, Dan A. & Djeraba, Chabane (2008). 「半順序集合」.データマイニングのための数学的ツール：集合論、半順序、組合せ論. Springer. ISBN 9781848002012。
3. Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). 「二項関係の推移閉包 I」. Acta Universitatis Carolinae. Mathematica et Physica . 48 (1). プラハ: カレル大学数学・物理学部: 55– 69.補題1.1 (iv)。この文献では、非対称な関係を「厳密に反対称的な」関係と呼んでいます。
4. Davey & Priestley (2002)、14～15ページ。
5. Avigad, Jeremy; Lewis, Robert Y.; van Doorn, Floris (2021年3月29日). "13.2. More on Orderings". Logic and Proof (リリース3.18.4版). 2023年4月3日時点のオリジナルよりアーカイブ。 2021年7月24日閲覧。したがって、すべての半順序は実際にはペアであり、弱い半順序とそれに関連する厳密な半順序から構成されると考えることができます。
6. Rounds, William C. (2002年3月7日). 「講義スライド」(PDF) . EECS 203: 離散数学. 2021年7月23日閲覧。
7. Kwong, Harris (2018年4月25日). 「7.4: 部分順序と全順序」. 離散数学のためのスパイラルワークブック. 2021年7月23日閲覧。
8. "有限posets". Sage 9.2.beta2 リファレンスマニュアル: 組合せ論. 2022年1月5日閲覧. compare_elements( x , y ): poset内のxとy を比較する。 x < yの場合は-1を返す。x = yの場合は0を返す。x > yの場合は1を返す。 xとy が比較できない場合はNoneを返す。
9. Chen, Peter; Ding, Guoli; Seiden, Steve. On Poset Merging (PDF) (技術レポート). p. 2 . 2022年1月5日閲覧。S内の2つの要素 s, t の比較は、3つの異なる値、すなわち s≤t、s>t、または s|t のいずれかを返します。
10. Prevosto, Virgile; Jaume, Mathieu (2003年9月11日). 階層的な数学的構造における証明の作成. CALCULEMUS-2003 – 第11回記号計算と機械化推論の統合に関するシンポジウム. ローマ, イタリア: Aracne. pp.  89– 100.
11. メリフィールド, リチャード E.;シモンズ, ハワード E. (1989).化学におけるトポロジカル手法. ニューヨーク: ジョン・ワイリー・アンド・サンズ. pp. 28. ISBN 0-471-83817-9. 2012年7月27日閲覧。半順序集合はハッセ図で簡単に表すことができます...
12. Neggers, J.; Kim, Hee Sik (1998)、「4.2 積順序と辞書式順序」、Basic Posets、World Scientific、pp.  62– 63、ISBN  9789810235895
13. Davey & Priestley (2002)、17～18ページ。
14. PR ハルモス (1974)。素朴集合論。スプリンガー。 p. 82.ISBN​ 978-1-4757-1645-0。
15. Davey & Priestley (2002)、23～24頁。
16. ジェック、トーマス(2008) [1973]. 『選択公理』ドーバー出版. ISBN 978-0-486-46624-8。
17. Ward, LE Jr (1954). 「部分的に順序付けられた位相空間」.アメリカ数学会誌. 5 (1): 144– 161. doi : 10.1090/S0002-9939-1954-0063016-5 . hdl :10338.dmlcz/101379.

参考文献

• Davey, BA; Priestley, HA (2002). 『格子と秩序入門』（第2版）. ニューヨーク: Cambridge University Press. ISBN 978-0-521-78451-1。
• デシュパンデ, ジャヤント V. (1968). 「半順序の連続性について」.アメリカ数学会報. 19 (2): 383– 386. doi : 10.1090/S0002-9939-1968-0236071-7 .
• シュミット、グンター（2010年）『関係数学』『数学とその応用百科事典』第132巻、ケンブリッジ大学出版局、ISBN 978-0-521-76268-7。
• ベルント・シュレーダー（2016年5月11日）『順序集合：組合せ論から位相幾何学への接続を含む入門』ビルクハウザー社。ISBN 978-3-319-29788-0。
• スタンリー、リチャード・P. (1997).列挙的組合せ論 1.ケンブリッジ高等数学研究第49巻. ケンブリッジ大学出版局. ISBN 0-521-66351-2。
• アイレンバーグ、S. (2016). 『代数的位相幾何学の基礎』プリンストン大学出版局.
• Kalmbach, G. (1976). 「ホモロジー理論の半順序集合への拡張」J. Reine Angew. Math . 280 : 134–156 .

外部リンク

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

• OEISシーケンスA001035（n個のラベル付き要素を持つポセットの数）
• OEISシーケンス A000112 (n 個のラベルなし要素を持つ半順序集合 (「poset」) の数)