順序集合

順序集合（じゅんじょしゅうごう、）は集合の要素の間に順序が定義された集合である。順序とは二項関係であって後述する反射律・推移律などを満たすものであり、実数の大小関係や整除関係、集合の包含関係などを一般化したものである。

順序が満たす公理の種類により、前順序集合、半順序集合、全順序集合がある。多く場合、半順序集合を指して「順序集合」と呼ぶが、分野によっては前順序集合や全順序集合を指す。

定義
P を集合とし、≤ を P 上に定義された二項関係とする。P を (P, ≤) の台集合（）または台（）という。

≤ が反射律と推移律を満たすとき、≤ を P 上の前順序（）または擬順序（）といい、(P, ≤) を前順序集合という。

反射律

推移律

≤ が前順序でかつ反対称律を満たすとき、≤ を P 上の半順序（）といい、(P, ≤) を半順序集合（）という。

反対称律

≤ が半順序でかつ全順序律を満たすとき、≤ を P 上の全順序（）といい、(P, ≤) を全順序集合（）という。全順序を線型順序、全順序集合を鎖ということもある。

全順序律

≤ が全順序律を満たさない（a ≤ b でも b ≤ a でもない）とき、a と b は比較不能（）であると言う。全ての二要素が比較可能な（順序が定義されている）順序集合は、全順序集合である。

紛らわしくなければ ≤ を省略し、P を（いずれかの意味で）順序集合という。順序集合 (P, ≤) に対し、≤ を台 P 上の順序関係ともいう。

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

半順序集合の部分集合 A で A の任意の異なる二元が比較不能であるものをという。が部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。

半順序集合の元 a が他の元 b によって （a <: b）とは、b が a より真に大きく、かつ a と b の間に他の元がないことを意味する。つまり a <: b とは下の三条件を全て満たすことである。

 とも表せる。

例
任意の二つの有限集合の濃度（元の数）の比較 ≼ は、前順序である。なお、紛らわしくも全順序律を満たすが、反対称律を満たさない（同じ濃度の異なる集合の対がある）ため半順序でさえない。
実数全体の集合について、算術的大小関係 ≤ は全順序である。その真部分集合（代数的数全体、有理数全体、整数全体、自然数全体など）についても同様である。
しかし、複素数全体の集合には複素数の乗法と"両立"する全順序は存在しない（順序体でない）。単に全順序を入れるだけであれば、直積集合 R = R × R に辞書式順序を定めることができる。

自然数全体の集合は、整除関係 &mid; を順序とする半順序集合であるが、全順序集合ではない。

任意の単元集合 {e} の冪集合 2{e} = {∅, {e}} は、包含関係 ⊆ を順序とする全順序集合である。

任意の二元以上の集合 S の冪集合 2 は、包含関係 ⊆ を順序とする半順序集合であるが、全順序集合ではない。例えば、2{1, 2, 3} = {∅, {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 の元の（自然数で添え字付けられた）列全体の成す集合は、列 1 = a = (an)n∈N, 1 = b = (bn)n∈N について、

と定めると半順序集合となる。

 集合 X と半順序集合 P に対し、X から P への写像全体の成すは、二つの写像 f, g に対して、f ≤ g を X の任意の元 x に対して f(x) ≤ g(x) となることとして定義すると、半順序集合になる。

 有向非巡回グラフの頂点集合は、到達不可能性によって順序付けられる。

逆順序、狭義順序、双対順序
前述の ≤ は、直観的には「左辺が右辺より小さい、または両辺が等しい」ことを意味するが、逆に「左辺が右辺より大きい、または両辺が等しい」順序関係や、等しさを許容しない順序関係も考案できる。

逆順序
「大きい、または等しい」ことを意味する順序関係 ≥ を ≤ の逆順序といい、下式のように定義される。

 狭義の順序 
一方、等しいことを許容しない順序は狭義の（半）順序と呼ばれ、以下のように定義される：
  …(1)
狭義の逆順序「」も同様に定義される。

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

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

「」が半順序であるとき、その反射的簡約「」は任意の  に対して以下を満たす：
非反射性：;
非対称性： ならば ; （非反射性と推移性から従う）
推移性： かつ  ならば 

以上では広義の順序を定義してから狭義の順序を定義したが、逆に上の三性質（非対称性は非反射性と推移性より得られるので条件としては不要）を満たすものを狭義の順序として定義し、広義の順序を
  …(2)
により定義することもできる。この場合、(2) 式で定義された「」を「」のという。「」が前述の3条件を満たせば反射閉包「」が半順序であることを簡単に示すことができる。

 双対順序集合 
 を順序集合とするとき、P 上の二項関係「」を

と定義する（すなわち「」は「」の逆順序を順序と見なしたものである）。すると、「」も  上の順序になっていることが容易に分かる。 を  の双対順序集合という。

双対順序集合はその定義  よりもとの順序集合  とは"大小が逆転"している。したがって  における上限、極大元、最大元（定義は後述）は  ではそれぞれ下限、極小元、最小元に対応している。

 ハッセ図 
150px|thumb|三元集合  の部分集合の全体を包含関係を順序とする順序集合と見たときのハッセ図
 を有限集合とし、「」を  上の狭義の半順序とするとき、以下のようにして  を自然に単純有向グラフと見なせる：

 頂点： の元
  から  への辺がある  であり、しかも  を満たす  が存在しない
（すなわち  は  を被覆している）

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

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

なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に  を閉路を持たない有限な単純有向グラフとすると、 上に以下の順序を入れることで  を半順序集合と見なせる：
  から  への道がある
したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。

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

  が  の上界 () であるとは、 の任意の元  に対して  となること。
  が  の上限 () あるいは最小上界 () であるとは、 が  の上界全体の集合の最小元となること。これは存在すれば一意的に決まり、 あるいは  と表される。
  が  の最大元 () であるとは、 は  の元であり、かつ  は  の上界であること。これは存在すれば一意的に決まり、 で表される。
  が  の極大元 () であるとは、 は  の元であり、かつ  を満たす  が存在しないこと。

  が  の下界 () であるとは、 の任意の元  に対して  となること。
  が  の下限 () あるいは最大下界 () であるとは、 が  の下界全体の集合の最大元となること。これは存在すれば一意的に決まり、 あるいは  と表される。
  が  の最小元 () であるとは、 は  の元であり、かつ  は  の下界であること。これは存在すれば一意的に決まり、 で表される。
  が  の極小元 () であるとは、 は  の元であり、かつ  を満たす  が存在しないこと。

上界および上限の定義において、  が必ずしも  の元であるとは限らない、ことには注意が必要である。左閉右開の半開区間  には最大元は存在しないが上界および上限は存在する（つまり、 ）。

極大元の概念と最大元の概念は以下の点で異なる。まず  が  の極大元であるとは、 の元は「 以下である」か、もしくは「 とは大小が比較不能である」かのいずれかである事を意味する。一方  が  の最大元であるとは  の元は常に  以下である事を意味する（このとき  は  の任意の元と比較が可能である）。したがって最大元は必ず極大元であるが、極大元は必ずしも最大元であるとは限らない（下の具体例参照）。全順序集合においては必ず極大元は最大元に一致する。

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

 具体例 
x150px|thumb|三元集合の冪集合のハッセ図から最大元と最小元を取り除いたもの。この図の一番上の行にある各元がこの半順序の極大元であり、一番下の行の各元は極小元である。最大元と最小元はない。集合 {x, y} は元の族 {{x}, {y}} に対する上界を与える。x150px|thumb|整除性によって順序付けられた非負整数のハッセ図
正整数全体の成す集合を整除関係で順序付けるとき、 は任意の正整数を割り切るという意味において  は最小元である。しかしこの半順序集合には最大元は存在しない（任意の正整数の倍数としての  を追加して考えたとするならば、それが最大元になる）。この半順序集合には極大元も存在しない。実際、任意の元  はそれとは異なる。例えば  を割り切るから  は極大ではありえない。この半順序集合から最小元である  を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の素数をとることができる。この半順序に関して  は部分集合  の上界（上限ではない）を与えるが、 は除かれているので下界は持たない。他方、 の冪全体の成す部分集合に対して  はその下界（これは下限でもある）を与えるが、上界は存在しない。

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

 定義 
 を順序集合とし、 を写像とする。このとき
  が(order-preserving)（同調 (isotone) とも）とは、
任意の  に対して 
  が順序を逆にする（）とは、
任意の  に対して 
 上の2つを合わせて単調 (monotone) 写像という。
  が順序を反映する (order-reflecting) とは、
任意の  に対して 
  がであるとは、
任意の  に対して 
  がであるとは、 が順序埋め込みな全単射であることをいう。

 が順序埋め込みであるとき、 は  によって  に（順序集合として）埋め込まれるという。
また順序同型  が存在するとき、 と  は順序同型あるいは単に同型であるという。

 性質 
上で述べた概念は以下の性質を満たす：
 順序を反映する写像は単射である。実際  かつ  かつ  である。
  が順序埋め込みである必要十分条件は  が順序を保存し、しかも順序を反映することである。また全単射  とその逆関数  が順序同型なら ,  は順序同型である。 
 順序を保つ写像と順序を保つ写像の合成は順序を保つ。順序を反映する写像と順序を反映する写像の合成も順序を反映する。

 具体例 
x150px|thumb|順序を保つが順序を反映しない写像 だが  でない)x150px|thumb| の約数全体の成す半順序集合（整除関係で順序を入れる）と  の整除関係で閉じた部分集合族（包含関係で順序を入れる）との間の順序同型
自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像  を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合である（すなわち、 が  を割るならば  の各素因数は  の素因数にもなる）が単射ではない（例えば  も  もこの写像で  に写る）し、順序を反映もしない（例えば  は  を割らない）。少し設定を変えて、各自然数にその素冪因子の集合を対応させる写像  を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない（実際、たとえば単集合  に移る数は無い）が終域を  の値域  に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎なと呼ばれる半順序集合のクラスに対して一般化することができる（の項を参照）。

 区間 
 を順序集合とし、 を  の元とするとき、閉区間  と開区間  を以下のように定義する：


さらに  および  を以下のように定義し、半開区間と呼ぶ：


文献によっては , ,  のことを , ,  と表す場合もある。

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

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

 順序構造と位相構造 

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


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

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

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

を考えると、A からB に誘導される位相では一元集合  は明らかに開集合であるが、B は順序集合としてみたときはそうではない。実際 B は（2を1に移す写像により） と順序同型だが、C の順序位相で  は開集合ではないので B の順序位相で は開集合ではない。

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

実数体  上の上極限位相とは

全体の集合を開基とする位相のことであり、同様に  上のとは逆向きの半開区間

全体の集合を開基とする位相のことである。

実数体に下極限位相を入れた空間はしばし  と書かれ、ゾルゲンフライ直線と呼ばれる。またゾルゲンフライ直線2つの直積  はと呼ばれる。

 overlapping interval topology 
区間 [-1,1] 上の overlapping interval topology とは
  for 
  for 
を準開基とする位相である。

 半順序集合の位相 
 半順序空間 
位相構造を持つ半順序集合P で以下の性質を満たすものをという：
  を満たす任意の に対し、a の開近傍Uで上方集合であるものと b の開近傍V で下方集合であるものが存在することである。

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

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

半順序空間では以下が成立する：
 かつ任意の i に対して  ならば  である

位相構造を持つ半順序集合P が半順序空間である必要十分条件は以下を満たすことである：
 半順序集合P 上の位相構造として、{(a, b) ∈ P × P | a ≤ b } が直積位相に関する閉部分集合になる。

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

 上方位相、下方位相 
順序集合 P 上の以下の2つの位相は同一である事が簡単に示せる。以下のいずれか一方（したがって両方）の条件を満たす位相をという。
 {x ∈ P | x &leq; a} for  を全て閉集合とする最弱の位相
 任意の に対し、一点集合 の閉包が{x ∈ P | x &leq; a} と一致する最弱の位相
下方位相も同様にして定義できる。

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

アレクサンドロフ空間は前順序集合と自然に1対1対応していることが知られている。
実際任意の前順序集合 P に対し、
 U が P の開集合 ⇔ U が P の上方集合
により P に位相を入れたものはアレクサンドロフ空間になる。（この位相を P のアレクサンドロフ位相という。）

逆に任意のアレクサンドロフ空間 P に対し P 上の「」を前順序とすることで P を前順序集合と見なすことができる。

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

で定義される前順序のことである。上式では一元集合 の閉包である。（なお、P がT空間であればspecialization preorder は半順序であることが知られている。）

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

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

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

 スコット位相 
上で述べたようにアレクサンドロフ位相は  のような「下に閉じた」集合すらも開集合と見なしてしまう。アレクサンドロフ位相からこのような不自然さを取り除いたのがスコット位相である。順序集合 P 上のスコット位相 (Scott topology) とは、以下の2条件を満たす P の部分集合 O 全体の集合を開集合族とする位相である：
 O ⊂ P は上方集合である
 P の有向部分集合 A で（A を自然に有向点族と見なしたときの）A の極限がO に入っていれば、A の点でO に含まれるものが存在する
後者の条件は内点概念の点列による特徴づけ（O の内点x に収束する点列はO と共通部分を持つ）に類似しており、この条件が「下に閉じた」集合を排除する。

よって実数体にスコット位相を入れた際、実数体上の開集合は以下のもののいずれかになる：
  for some a 
 空集合 、全体集合 
スコット位相を入れた順序集合をスコット空間といい、スコット空間からスコット空間への連続写像をスコット連続 (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 )} = f (sup{x , y }) = f (x ) となる。これは を意味する。

なお、スコット位相と下方位相のいずれよりも強い位相構造の中で最弱のものをという。

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

 直積集合上の順序 
2つの半順序集合（の台集合）の直積集合上の半順序としては次の三種類がある。
 辞書式順序：
 積順序： 

最後の順序は対応する狭義全順序の直積の反射閉包である。これらの三種類の半順序は、いずれも3個以上の半順序集合の直積に対しても同様に定義される。

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

 圏としての順序集合 
任意の半順序集合（および前順序集合）は、任意の射集合が高々一つの元からなる圏と見なすことができる。具体的には、射の集合を  ならば （それ以外の場合は空集合）とし、 と定義する。2つの半順序集合が圏として同値となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏はいる。

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

 その他 
 （半順序関係の総数） 個の元からなる集合上の半順序の総数（狭義半順序の総数も同じ）は  （）。同型を除いた総数は  （）。
 （線型順序拡大）半順序集合  の全順序集合への埋め込みを (linear extension) という。任意の半順序は全順序に拡張することができる（）。計算機科学において（有向非循環グラフの順序として表現される）半順序の線型拡張を求めるアルゴリズムは位相ソート  と呼ばれる。

 関連項目 
 : 半順序集合よりも一般の順序付けの族を許すような、集合上の順序付けの一般化
 因果集合

 有向集合

 半束
 束 (束論)
 順序群
  (semiorder)

 : "a < b または b < a の何れかが成り立つ" という関係が推移的となるような狭義半順序 "<"
 完備半順序 (cpo)
 ツォルンの補題
 コンパクト要素
 ：半順序集合における順序関係の向きが  というように交互に入れ替わる列

 脚注 

 注釈 

 出典 

 参考文献 







 外部リンク 

 : Number of posets with n labeled elements in the OEIS
 : Number of posets with n unlabeled elements in the OEIS

*
Category:数学に関する記事