半順序集合

図1：包含によって順序付けられた3要素集合のすべての部分集合の集合のハッセ図。やのように上向きのパスで接続された集合は比較可能ですが、例えばや は比較できません${\displaystyle \{x,y,z\},}$ ${\displaystyle \emptyset }$ ${\displaystyle \{x,y\}}$ ${\displaystyle \{x\}}$ ${\displaystyle \{y\}}$

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

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

半順序関係

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

半順序

反射半順序、弱半順序、^[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. 推移性： かつ。${\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. 非対称性：ならば、そうではない。${\displaystyle a<b}$ ${\displaystyle b<a}$
3. 推移性： かつ。${\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つの半順序関係と を定義できます。ここで、は 上の非厳密半順序関係、は 上の関連する厳密半順序関係（の非反射核）、は の双対、は の双対です。厳密に言えば、半順序集合という用語は、これらの関係がすべて適切に定義された集合を指します。しかし実際には、 という単一の関係、または、またはまれな例では、非厳密関係と厳密関係を一緒に 、を考慮するだけで済みます。^[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]

有限半順序集合は、ハッセ図を通して視覚化できます。^[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≤Zbによって定義され、かつ次の場合に限り ます。

• _a , b ∈ Xかつa≤Xb 、または
• a , b ∈ Yかつ、または
• a ∈ Xかつb ∈ Y。

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

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

派生概念

例では、集合の包含によって順序付けられた3要素集合のすべての部分集合の集合からなる半順序集合を使用します（図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\}}$
• 全順序または線型順序とは、すべての要素のペアが比較可能な半順序、つまり三分法が成り立つ順序です。例えば、標準順序を持つ自然数です。
• 連鎖とは、全順序集合である半集合の部分集合です。例えば、は連鎖です。${\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またはa <: bと表記）によって覆われているとは、 aがbより厳密に小さく、かつ3つ目の元cがそれらの間に収まらない場合を指します。正式には、a ≤ bとa ≤ c ≤ 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最大元と最小元を削除した上の図。この縮小された半集合では、上の行の元はすべて最大元であり、下の行の元はすべて最小元ですが、最大元と最小元はありません。

半集合には、「最大元」と「最小元」の概念がいくつかあります。特に、 次のようになります${\displaystyle P,}$

• 最大元と最小元：元は、すべての元に対して であるとき、最大元です。元は、すべての元に対して であるとき、最小元です。poset は、最大元または最小元を 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の上限となる。特に、Aの上限となるためにはx が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 )は第二種スターリング数を指すことに注意してください。

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

同型までのみ数えると、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^{*}]}$

線形拡張

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

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

圏論において

すべてのposet（およびすべてのpreordered set ）は、オブジェクトとに対して、からへの射が最大で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).}$

posetは、同型である場合に限り互いに同値です。posetでは、最小の要素が存在する場合は始対象であり、最大の要素が存在する場合は終対象です。また、すべてのpreordered setはposetと同値です。最後に、posetのすべての部分圏は同型閉です

位相空間における半順序

が位相空間の構造も与えられている半順序集合である場合、慣例的に は位相積空間の閉部分集合であると仮定する。この仮定の下では、半順序関係は、すべての に対して かつ であるならば、^[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のイデアルの積として一意に表すことができる。

半集合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日). A Beginner's Guide to Discrete Mathematics. 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), pp. 14–15
5. Avigad, Jeremy; Lewis, Robert Y.; van Doorn, Floris (2021年3月29日). 「13.2. 順序についてさらに詳しく」. 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. ピーター・チェン、グオリ・ディン、スティーブ・セイデン。Poset Mergingについて（PDF）（技術レポート）。2ページ。 2022年1月5日閲覧。Sの2つの要素sとtの比較は、3つの異なる値、すなわちs≤t、s>t、またはs|tのいずれかを返します。
10. ヴァージル・プレヴォスト、マシュー・ジャウメ（2003年9月11日）。数学的構造の階層における証明の作成。CALCULEMUS-2003 – 第11回記号計算と機械化推論の統合シンポジウム。ローマ、イタリア：アラクネ。89  ～ 100ページ。
11. リチャード・E・メリフィールド、ハワード・E・シモンズ（1989年）。化学における位相的手法。ニューヨーク：ジョン・ワイリー・アンド・サンズ。28ページ。ISBN 0-471-83817-9. 2012年7月27日閲覧。半順序集合はハッセ図で簡単に表すことができます...
12. Neggers, J.; Kim, Hee Sik (1998)、「4.2 積順序と辞書式順序」、Basic Posets、World Scientific、  62～ 63ページ、ISBN  9789810235895
13. Davey & Priestley (2002)、17～18ページ
14. PR Halmos (1974) 『素朴集合論』、Springer、82ページ。ISBN  978-1-4757-1645-0。
15. Davey & Priestley (2002)、23～24ページ
16. Jech, Thomas (2008) [1973].選択公理、Dover Publications、ISBN 978-0-486-46624-8。
17. Ward, LE Jr (1954). 「半順序位相空間」. Proceedings of the American Mathematical Society . 5 (1): 144– 161. doi : 10.1090/S0002-9939-1954-0063016-5 . hdl :10338.dmlcz/101379.

参考文献

• Davey, BA; Priestley, HA (2002).格子と秩序入門（第2版）. ニューヨーク：ケンブリッジ大学出版局. 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個のラベルなし要素を持つ半順序集合（「半順序集合」）の数)