「順序集合」の版間の差分

削除された内容追加された内容

インライン

2015年4月27日 (月) 13:07時点における版

数学において順序集合（じゅんじょしゅうごう、英: ordered set）とは「順序」の概念が定義された集合の事で、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。

ただし順序集合内の２つの元a、b に順序関係が定まっている必要はなく、両者が「比較不能」であってもよい。よってa、b の関係は「a はb 以上である」、「b はa 以上である」、「a とb は比較不能である」の３通りのいずれかとなる。

比較不能のケースを許容している強調して順序集合の事を半順序集合（はんじゅんじょしゅうごう、英: partially ordered set, poset）ともいう。一方、半順序集合の中で特に比較不能のケースがないものをしないものを全順序集合(totally ordered set)という。（「半順序」という言葉が「全順序」の対義語ではない事に注意。全順序集合も半順序集合の一種である）。

全順序集合の簡単な例は整数の集合や実数の集合で、通常の大小比較を順序とみなしたものがある。

一方、全順序ではない半順序集合の例としては(2つ以上元を含む)集合の冪集合で、包含関係を順序とみなしたものがある。例えば3元集合P ={a,b,c}において{a,b}と{b,c}はいずれも他方を包含していないのでP の冪集合は全順序ではない。実生活に近い例では、「AさんはBさんの子孫である」という事を「A＜B」という大小関係とみなす事で人間全体の集合を半順序集合とみなせる。AさんとBさんはどちらも他方の子孫でない事もありうる（兄弟同士、叔父と甥、赤の他人等）ので、この順序集合は全順序ではない。

定義

全順序集合、半順序集合、およびこれらよりさらに弱い概念である前順序集合の定義を述べる為にまず以下の性質を考える。ここでP は集合であり、「≤」をP 上で定義された二項関係である。

反射律: $\forall a\in P:a\leq a$
推移律: $\forall a,b,c\in P:a\leq b\land b\leq c\to a\leq c$
反対称律: $\forall a,b\in P:a\leq b\land b\leq a\to a=b$
全順序律: $\forall a,b\in P:a\leq b\lor b\leq a$

「≤」が全順序律を満たさない場合、「a ≤ b」でも「b ≤ a」でもないケースがある。このような第三のケースにあるときa とbは比較不能であるという。

前順序・半順序・全順序

$P$ を集合とし、 $\leq$ を $P$ 上で定義された二項関係とする。

$\leq$ が反射律と推移律を満たすとき $\leq$ を $P$ 上の前順序という。
前順序な $\leq$ が反対称律をも満たすとき $\leq$ を $P$ 上の半順序という。
半順序な $\leq$ が全順序律をも満たすとき $\leq$ を $P$ 上の全順序という。

$\leq$ が前順序である $(P, \leq)$ を前順序集合という。同様に $\leq$ が半順序なら $(P, \leq)$ は半順序集合、全順序なら $(P, \leq)$ は全順序集合である。また集合 $P$ は $(P, \leq)$ の台 (support) と呼ばれる。紛れがなければ $\leq$ を省略し、 $P$ の事を（いずれかの意味で）順序集合という。

順序集合 $(P, \leq)$ に対し、 $\leq$ を台 $P$ 上の順序関係ともいう。なお多くの数学の分野では半順序集合を主に扱うので、単に順序あるいは順序集合といった場合はそれぞれ半順序、半順序集合を意味する場合が多いが、分野によっては、主な対象が半順序集合でなく前順序集合や全順序集合である場合があり、そのような分野では前順序集合や全順序集合の意味で「順序集合」という言葉が用いられることがあるので注意が必要である。

上では順序を記号 $\leq$ で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号 $\leq$ と区別する為、順序の記号として $\prec$ や $\ll$ を使うこともある。

全順序の事を線型順序ともいい、全順序集合のことを鎖と呼ぶこともある。また半順序集合の部分集合 $A$ で $A$ の任意の相異なる二元が比較不能であるものを反鎖（英語版）という。

半順序集合の元 $a$ が他の元 $b$ によって被覆される（英語版） $a <: b$ とは、 $a$ は $b$ よりも真に小さく、かつそれらの間に別の元が入ることはないこと（後述する狭義の記号を使って書けば $a < b$ かつ任意の $c$ に対して $a < c < b$ が偽となること）をいう。

順序集合の例

自然数全体の集合 N、整数全体の集合 Z、有理数全体の集合 Q、実数全体の集合 R は通常の代数的な大小関係によって全順序集合になるが、複素数はそうではない。複素数全体の集合 C に R × R としての辞書式順序を定めたものは全順序集合であるが、この順序は複素数の乗法とは両立しない。
自然数全体の成す集合は整除関係を順序として半順序集合である。
ある集合の冪集合は部分集合の包含関係を順序として半順序集合となる。これは一般には全順序ではない。例えば {1, 2, 3} の冪集合
$\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$
について、たとえば {1, 2} と {2, 3} を考えれば、これらは比較不能である（{1, 2} ≤ {2, 3} でも {2, 3} ≤ {1, 2} でもない）。
ベクトル空間の部分空間全体は包含関係で順序付けられた半順序集合である。
半順序集合 P に対し、P の元の列全体の成す集合は、列 a, b に対し、
$a=(a_{n})_{n\in \mathbb {N} }\leq b=(b_{n})_{n\in \mathbb {N} }\iff a_{n}\leq b_{n}(\forall n\in \mathbb {N} )$
と定めると半順序集合となる。
集合 X と半順序集合 P に対し、X から P への写像全体の成す写像空間は、ふたつの写像 f, g に対して、f ≤ g を X の任意の元 x に対して f(x) ≤ g(x) となることとして定義すると、半順序集合になる。
非循環有向グラフの頂点集合は、到達不可能性によって順序付けられる。
半順序集合における順序関係の向きが a < b > c < d ... というように交互に入れ替わる列をフェンスと呼ぶ。

逆順序、狭義の順序、双対順序

上で述べた順序関係「≤」は直観的には左辺が右辺よりも「小さい、もしくは等しい」事を意味しているが、逆に左辺が右辺よりも「大きい、もしくは等しい」順序関係や等しい事を許容しない順序関係を考える事もできる。

逆順序

「大きい、もしくは等しい」事を意味する順序関係は「≤」の逆順序と呼ばれ、

a\geq b\iff b\leq a

により定義される。

狭義の順序

一方、等しい事を許容しない順序は狭義の(半)順序と呼ばれ、以下のように定義される：

a<b\iff (a\leq b\land a\neq b)

...(1)

狭義の逆順序「>」も自然に定義される。

狭義の順序「<」の対義語として、等しい事も許容する順序「≤」の事を広義の(半)順序（もしくは弱い意味 (weak) の(半)順序、反射的 (reflexive) な(半)順序）という。

(1)式で定義された「<」を「≤」の反射的簡約 (reflexive reduction) という。

「≤」が半順序であるとき、その反射的簡約「<」は任意のa, b, c ∈ P に対して以下を満たす：

非反射性: ¬(a < a);
非対称性: a < b ならば ¬(b < a);
推移性: a < b かつ b < c ならば a < c

以上では広義の順序からスタートして狭義の順序を定義したが、逆に上の三性質を満たすものを狭義の順序として定義し、広義の順序を

a\leq b\iff a<b\lor a=b

...(2)

により定義する事もできる。この場合、(2)式で定義された「≤」を「<」の反射閉包（英語版）という。「<」が前述の３条件を満たせば反射閉包「≤」が半順序である事を簡単に示す事ができる。

双対順序集合

$(P, \leq)$ を順序集合とするとき、P 上の二項関係「 $\preccurlyeq$ 」を

a\preccurlyeq b\iff b\leq a

と定義する（すなわち「 $\preccurlyeq$ 」は「≤」の逆順序を順序とみなしたものである）。すると、「 $\preccurlyeq$ 」もP 上の順序になっている事が簡単に示せる。 $(P,\preccurlyeq )$ を $(P, \leq)$ の双対順序集合という。

双対順序集合はその定義 $(P,\preccurlyeq )$ よりもとの順序集合 $(P, \leq)$ とは大小が逆転している。したがって $(P, \leq)$ における上限、極大元、最大元は $(P,\preccurlyeq )$ ではそれぞれ下限、極小元、最小元になる。

ハッセ図

P を有限集合とし、「<」をP 上の狭義の半順序とするとき、以下のようにしてP を自然に単純有向グラフとみなせる：

頂点：Pの元

a ∈ P から b ∈ P への辺がある⇔

a < b

であり、しかも

a < c < b

を満たすc ∈ Pが存在しない。（すなわちb はa を被覆している）。

この有向グラフを図示したものをハッセ図という。

右に示した図がハッセ図の例である。この図では三元集合 {x, y, z}の部分集合の全体を包含関係を順序とする順序集合とみなしたものをハッセ図として表している。

ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。例えばこの図で {x} と {x,y,z} は比較可能だが、{x} と {y} は比較不能である。また一元集合の族 ${{x}, {y}, {z}}$ は反鎖である。さらに{x} は {x,z} によって被覆されるが、{x,y,z} には被覆されない。

なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に $(V, E)$ を閉路を持たない有限な単純有向グラフとすると、V 上に以下の順序を入れる事でV を半順序集合とみなせる：

a < b

⇔ a からb への道がある

したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。

上界、最大、極大、上限、上方集合

$P$ を半順序集合とし、 $A$ をその部分集合とし、 $x$ を $P$ の元とする。このとき上界、最大、極大、上限の概念、およびこれらの双対概念である下界、最小、極小、下限は以下のように定義される：

定義

$x$ が $A$ の上界（resp. 下界）: $\forall y \in A : y \leq x (resp. y \geq x)$
$x$ が $A$ の最大元（resp. 最小元）: $x$ は $A$ の元でしかも $x$ は $A$ の上界（resp. 下界）である
$x$ が $A$ の極大元（resp. 極小元）: $x$ は $A$ の元でしかも $y\gneqq x$ (resp. $y\lneqq x$ ) を満たす $y \in A$ が存在しない
$x$ が $A$ の上限（resp. 下限）: $x$ は集合 ${y \in P | y$ は $A$ の上界（resp. 下界） $}$ の最小元（resp. 最大元）

上界および上限の定義において $x$ が $A$ に必ずしも属さないことには注意が必要である。

極大元の概念と最大元の概念は以下の点で異なる。まず $x$ が $A$ の極大元であるとは、 $A$ の元は「 $x$ 以下である」か、もしくは「 $x$ とは大小が比較不能である」かのいずれかである事を意味する。一方 $x$ が $A$ の最大元であるとは $A$ の元は常に $x$ 以下である事を意味する（このとき $A$ の元は $x$ と比較可能である）。したがって最大元は極大元であるが、極大元は必ずしも最大元であるとは限らない。

さらに $A$ が $P$ の上方集合（resp. 下方集合）であるとは、任意の $a \in A$ と $x > a$ (resp. $x < a$ ) を満たす任意の $P$ の元に対し $x \in A$ となることをいう。

具体例

正整数全体の成す集合を整除関係で順序付ける時、 $1$ は任意の正整数を割り切るという意味において $1$ は最小元である。しかしこの半順序集合には最大元は存在しない（任意の正整数の倍数としての 0 を追加して考えたとするならば、それが最大元になる）。この半順序集合には極大元も存在しない。実際、任意の元 g はそれとは異なる例えば 2g を割り切るから g は極大ではありえない。この半順序集合から最小元である 1 を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の素数をとることができる。この半順序に関して 60 は部分集合 {2,3,5,10} の上界（上限ではない）を与えるが、1 は除かれているので下界は持たない。他方、 $2$ の冪全体の成す部分集合に対して $2$ はその下界（これは下限でもある）を与えるが、上界は存在しない。

写像と順序

順序に関する写像の概念に以下のものがある：

定義

S 、T を順序集合とし、f: S → T を写像とする。このとき

f: S → T が順序を保つ（order-preserving（英語版）。同調 (isotone)とも）とは、任意の x, y ∈ S に対して x ≤ y ⇒ f (x) ≤ f (y) である事を言う。
f: S → T が順序を逆にする（order-reversing（英語版））とは、任意の x, y ∈ S に対して x ≤ y ⇒ f (x) ≥ f (y) である事を言う。
上の2つを合わせて単調(monotone) 写像と言う。
fが順序を反映する (order-reflecting) とは任意の x, y ∈ S に対して f (x) ≤ f (y) ⇒ x ≤ y であることを言う。
f が順序埋め込み（英語版）であるとは、任意の x, y ∈ S に対しx ≤ y ⇔ f (x) ≤ f (y) である事を言う。
fが順序同型写像（英語版）であるとは、f が順序埋め込みな全単射である事を言う。

f: S → T が順序埋め込みであるとき、S はf によって T に（順序集合として）埋め込まれるという。またf: S → T が順序同型なとき、S とT は順序同型あるいは単に同型であるという。

性質

上で述べた概念は以下の性質を満たす：

順序を反映する写像は単射である。実際f (x) = f (y) ⇒f (x) ≤ f (y) かつ f (x) ≥ f (y) ⇒ x ≤ y かつ x ≥ y ⇒x = y である。
f が順序埋め込みである必要十分条件はf が順序を保存し、しかも順序を反映する事である。またf: S → T とその逆関数 f ^-1: T → S が順序同型ならf 、f ^-1は順序同型である。
順序を保つ写像と順序を保つ写像の合成は順序を保つ。順序を反映する写像と順序を反映する写像の合成も順序を反映する。

具体例

120 の約数全体の成す半順序集合（整除関係で順序を入れる）と {2,3,4,5,8} の整除関係で閉じた部分集合族（包含関係で順序を入れる）との間の順序同型

自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像 f: ℕ → ℙ(ℕ) を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合である（すなわち、x が y を割るならば x の各素因数は y の素因数にもなる）が単射ではない（例えば 12 も 6 もこの写像で {2,3} に写る）し、順序を反映もしない（例えば 12 は 6 を割らない）。少し設定を変えて、各自然数にその素冪因子の集合を対応させる写像 g: ℕ → ℙ(ℕ) を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない（実際、たとえば単元集合 {4} に写る数は無い）が終域を g の値域 g(ℕ) に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎な分配束（英語版）と呼ばれる半順序集合のクラスに対して一般化することができる（バーコフの表現定理（英語版）の項を参照）。

区間

P を順序集合とし、a、b をP の元とする時、閉区間 [a, b] と開区間 (a, b)を以下のように定義する：

[a,b]:=\{x\in P\mid a\leq x\leq b\}

(a,b):=\{x\in P\mid a<x<b\}

さらに[a,b) および (a,b] を以下のように定義し、半開区間と呼ぶ：

[a,b):=\{x\in P\mid a\leq x<b\}

(a,b]:=\{x\in P\mid a<x\leq b\}

文献によっては(a, b)、[a,b)、 (a,b] の事を ]a, b[、[a,b[、 ]a,b] と表す場合もある。

半順序集合が局所有限（英語版）であるとは、すべての区間が有限集合であることを言う。たとえば、整数全体の成す集合は通常の大小関係による半順序に関して局所有限である（端点の無い無限区間のようなものは今考えていない）。

順序集合における区間の概念と、区間順序（英語版）として知られる特定の半順序の類いとを混同してはならない。

順序構造と位相構造

全順序集合の位相

順序位相

全順序集合A に対し、無限半開区間

(-\infty ,b)=\{x\in A\mid x<b\}

(a,\infty )=\{x\in A\mid a<x\}

全体の集合を準開基とする位相を順序位相(order topology)という^[1]。例えば、通常の大小関係 ≤ によって実数全体の集合 $\mathbb {R}$ を全順序集合と見ると、その順序位相は通常の距離により定められる位相と同等になる。

全順序集合Aの部分集合B には、B を全順序集合とみなした時の順序位相と A の順序位相から誘導される位相との２つの位相が入る。しかしこの２つの位相は一致するとは限らない。（Bの順序位相における開集合は誘導位相でも開集合であるが逆は一般には成り立たない）。

例えばA を実数全体の集合とし、A の部分集合

B=\{x\mid 0<x<1\}\cup \{2\}

を考えると、A からB に誘導される位相では一元集合 ${2}$ は明らかに開集合であるが、B は順序集合としてみたときはそうではない。実際B は(2を1に移す写像により) $C=\{x\mid 0<x\leq 1\}$ と順序同型だが、C の順序位相で ${1}$ は開集合ではないのでB の順序位相で ${2}$ は開集合ではない。

上極限位相、下極限位相

単に「実数体上の位相」といった場合、前述の順序位相を指すがその他の位相を考える事も（主に反例として用いる為に）できる。

実数体 $\mathbb {R}$ 上の上極限位相とは

(a,b]=\{x\in \mathbb {R} ~:~a<x\leq b\}

全体の集合を開基とする位相の事であり、同様に $\mathbb {R}$ 上の下極限位相（英語版）とは逆向きの半開区間

[a,b)=\{x\in \mathbb {R} ~:~a\leq x<b\}

全体の集合を開基とする位相の事である^[2]。

実数体に下限位相を入れた空間はしばし $\mathbb {R} _{\ell }$ と書かれ、ゾルゲンフライ直線と呼ばれる。またゾルゲンフライ直線２つの直積 $\mathbb {R} _{\ell }\times \mathbb {R} _{\ell }$ はゾルゲンフライ平面（英語版）と呼ばれる。

overlapping interval topology

区間[-1,1]上のoverlapping interval topologyとは

[-1,a)

for

0<a

(b,1]

for

b<0

を準開基とする位相である。

半順序集合の位相

半順序空間

位相構造を持つ半順序集合P で以下の性質を満たすものを半順序空間（英語版）という：

a < b

を満たす任意の

a, b \in P

に対し、a の開近傍Uで上方集合であるものとb の開近傍V で下方集合であるものが存在する事である。

（P の位相構造でこの性質を満たすものは１つとは限らないが、それらを全て半順序空間という。）なお、半順序空間と名前の似たposet topology（英語版）は別概念であるので注意が必要である。

定義より明らかに半順序空間は常にハウスドルフ性を満たす。

半順序空間では以下が成立する：

a i \to a, b i \to b

かつ任意の i に対して

a i \leq b i

ならば

a \leq b

である^[3]

位相構造を持つ半順序集合P が半順序空間である必要十分条件は以下を満たす事である：

半順序集合P 上の位相構造として、{(a, b) ∈ P × P | a ≤ b } が直積位相に関する閉部分集合になる。

２つ半順序空間の間の順序を保つ連続写像の事をdimapという。

上方位相、下方位相

順序集合P 上の以下の２つの位相は同一である事が簡単に示せる。以下のいずれか一方（したがって両方）の条件を満たす位相を上方位相（英語版）という。

{x ∈ P | x ≥ a} for $a \in P$ を全て閉集合とする最弱の位相
任意の $a \in P$ に対し、一点集合 ${a}$ の閉包が{x ∈ P | x ≥ a}と一致する最弱の位相

下方位相も同様にして定義できる。

アレクサンドロフ空間

位相空間P がアレクサンドロフ空間（英語版）であるとは、P上の（有限または無限個の）任意の開集合の共通部分が必ず開集合になる事を言う。

アレクサンドロフ空間は前順序集合と自然に１対１対応している事が知られている。実際任意の前順序集合P に対し、

U がP の開集合 ⇔ U がP の上方集合

によりP に位相を入れたものはアレクサンドロフ空間になる。（この位相をP のアレクサンドロフ位相という。）

逆に任意のアレクサンドロフ空間P に対しP 上の「specialization preorder（英語版）」を前順序とする事でP を前順序集合とみなす事ができる。

ここで位相空間P のspecialization preorderとは

x\leq y\iff {\overline {\{x\}}}\subset {\overline {\{y\}}}

で定義される前順序の事である。上式で ${\overline {\{x\}}}$ は一元集合 ${x}$ の閉包である。（なお、PがT₀空間であればspecialization preorderは半順序である事が知られている。）

以上の対応関係により、集合P におけるアレクサンドロフ空間としての構造とP 上の前順序は１対１対応する。

specialization preorderはアレクサンドロフ空間でなくとも定義可能であるが、アレクサンドロフ空間でない位相空間上ではspecialization preorderに対して上方集合でない開集合も存在する。（なおこの場合でも開集合は常に上方集合である）。したがって前述したような、上方集合を開集合とする位相を考えても元の位相は復元できない。

実数体における例

実数体（に通常の順序をいれたもの）を前順序集合とみなす事で実数体にアレクサンドロフ位相を入れる事ができる。アレクサンドロフ位相における実数体上の開集合（すなわち上方集合）は以下のもののいずれかになる：

$(a,\infty )$ for some a
$[a,\infty )$ for some a
空集合 $\emptyset$ 、全体集合 $\mathbb {R}$

スコット位相

上で述べたようにアレクサンドロフ位相は $[a,\infty )$ のような「下に閉じた」集合すらも開集合とみなしてしまう。アレクサンドロフ位相からこのような不自然さを取り除いたのがスコット位相である。順序集合P 上のスコット位相(Scott topology)とは、以下の２条件を満たすP の部分集合O 全体の集合を開集合族とする位相である：

O ⊂ P は上方集合である
P の有向部分集合 A で(A を自然に有向点族とみなしたときの)A の極限がO に入っていれば、A の点でO に含まれるものが存在する

後者の条件は内点概念の点列による特徴づけ（O の内点x に収束する点列はO と共通部分を持つ）に類似しているおり、この条件が「下に閉じた」集合を排除する。

よって実数体にスコット位相を入れた際、実数体上の開集合は以下のもののいずれかになる：

$(a,\infty )$ for some a
空集合 $\emptyset$ 、全体集合 $\mathbb {R}$

スコット位相を入れた順序集合をスコット空間といい、スコット空間からスコット空間への連続写像をスコット連続(Scott continuity)という。順序集合P から順序集合Q への写像f がスコット連続である必要十分条件は以下の性質が成り立つ事である事が知られている：

P の任意の有向部分集合A に対し、A がP 内の上限を持てばf (A )もQ 内の上限を持ち、sup f (A) = f (sup A )が成立する。

スコット連続な関数は順序を保つ。実際、x ≥ y ⇒ sup{x , y } = x であるので、上述した条件より $sup{f (x), f (y)$ }が存在し、しかもsup{f (x ), f (y )} = f (sup{x , y }) = f (x )となる。これは $f (x) \geq f (y)$ を意味する。

なお、スコット位相と下方位相のいずれよりも強い位相構造の中で最弱のものをローソン位相（英語版）という。

ストーン双対性

位相空間の開集合全体の集合は包含関係により順序集合とみなせる。位相空間が「sober性」という弱い性質を満たす時はこの順序構造のみで位相空間の構造が特徴づけられる事が知られている（ストーンの双対性定理）。したがってsober性を満たす空間に話を限定すれば、点集合論に頼らなくても順序構造のみで位相空間論を展開できる（ポイントレス位相空間論）。

直積集合上の順序

ふたつの半順序集合（の台集合）の直積集合上の半順序としては次の三種類が考えられる。

辞書式順序: $(a,b)\leq (c,d)\iff a<c\lor (a=c\land b\leq d)$
積順序: $(a,b)\leq (c,d)\iff a\leq c\land b\leq d$
$(a,b)\leq (c,d)\iff (a<c\land b<d)\lor (a=c\land b=d)$

最後の順序は対応する狭義全順序の直積の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの半順序集合の直積に対しても同様に定義される。

体上の順序線型空間に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれもふたたび順序線型空間となる。

ℕ×ℕ 上の直積狭義順序の反射閉包。
ℕ×ℕ 上の積順序
ℕ×ℕ 上の辞書式順序

圏としての順序集合

任意の半順序集合（および前順序集合）は、任意の射集合が高々一つの元からなる圏と看做すことができる。具体的には、射の集合を x ≤ y ならば hom(x, y) = {(x, y)} (それ以外の場合は空集合) とし、(y, z)∘(x, y) = (x, z) と定義する。二つの半順序集合が圏として同値となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏は同型射について閉じて（英語版）いる。

半順序集合からの函手、すなわち半順序圏で添字付けられた図式は、可換図式である。

その他

(半順序関係の総数)n 個の元からなる集合上の半順序の総数（狭義半順序の総数も同じ）はオンライン整数列大辞典の数列 A001035 同型を除いた総数は 1, 1, 2, 5, 16, 63, 318, … オンライン整数列大辞典の数列 A000112.
(線型順序拡大)半順序集合P の全順序集合への埋め込みを線形順序拡大(linear extension)という。任意の半順序は全順序に拡張することができる（順序拡大原理（英語版）^[4]）。計算機科学において（有向非循環グラフの到達可能性（英語版）順序として表現される）半順序の線型拡張を求めるアルゴリズムは位相ソート (topological sorting) と呼ばれる。

注記

^ 原理的には半順序集合であっても同様の概念を定義できるが、本稿の英語版をはじめ、筆者が調べた範囲では全順序集合に対してのみorder topologyを定義している為、ここでは全順序のみに話を限定した。
^ 実数体でなくとも上極限位相と下極限位相を考える事ができるが、これも実数体以外に対してこれらの位相を定義した文献が見つけられなかったので、ここでは実数体のみを対象にした。
^ Ward, L. E. Jr (1954). “Partially Ordered Topological Spaces”. Proceedings of the American Mathematical Society 5 (1): 144–161. doi:10.1090/S0002-9939-1954-0063016-5.
^ Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 0-486-46624-8

参考文献

Deshpande, Jayant V. (1968). “On Continuity of a Partial Order”. Proceedings of the American Mathematical Society 19 (2): 383–386. doi:10.1090/S0002-9939-1968-0236071-7.
Schröder, Bernd S. W. (2003). Ordered Sets: An Introduction. Birkhäuser, Boston
Stanley, Richard P.. Enumerative Combinatorics 1. Cambridge Studies in Advanced Mathematics. 49. Cambridge University Press. ISBN 0-521-66351-2

外部リンク

オンライン整数列大辞典の数列 A001035: Number of posets with n labeled elements in the OEIS
オンライン整数列大辞典の数列 A000112: Number of posets with n unlabeled elements in the OEIS

[1] 原理的には半順序集合であっても同様の概念を定義できるが、本稿の英語版をはじめ、筆者が調べた範囲では全順序集合に対してのみorder topologyを定義している為、ここでは全順序のみに話を限定した。

[2] 実数体でなくとも上極限位相と下極限位相を考える事ができるが、これも実数体以外に対してこれらの位相を定義した文献が見つけられなかったので、ここでは実数体のみを対象にした。

[ward-1954-3] Ward, L. E. Jr (1954). “Partially Ordered Topological Spaces”. Proceedings of the American Mathematical Society 5 (1): 144–161. doi:10.1090/S0002-9939-1954-0063016-5.

[4] Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 0-486-46624-8

[1]

[2]

[3]

[4]