順序集合

数学において順序集合とは、大小関係や血縁関係のような順序が定義された集合のことである。順序は一般に二項関係として定義されるが、その順序集合の任意の2つの元に対して必ず定まるとは限らない。

比較不能の場合を許容する順序集合として典型的なのは後述する半順序集合である。特に、半順序集合で全ての2元が比較可能であるものを全順序集合という。

全順序の最も簡単な例は、実数における大小関係である。

一方、全順序ではない半順序集合の例としては、正の整数全体の集合に整除関係で順序を入れたものや、集合の冪集合において、包含関係を順序と見なしたものがある。例えば2元集合 //S// =}} mset において mset と mset はいずれも他方を包含していないので S}} の冪集合は全順序ではない。

1. 定義
-----

前順序、半順序、全順序を順に定義するために、まず以下の性質を考える。ここで P}} は集合であり、「≤}}」を P}} 上で定義された二項関係とする。

反射律：P}} の任意の元 a}} に対し、//a// ≤ //a//}} が成り立つ。
推移律：P}} の任意の元 a}}, b}}, c}} に対し、//a// ≤ //b//}} かつ //b// ≤ //c//}} ならば //a// ≤ //c//}} が成り立つ。
反対称律：P}} の任意の元 //a//, //b//}} に対し、//a// ≤ //b//}} かつ //b// ≤ //a//}} ならば //a// =}} //b//}} が成り立つ。
全順序律：P}} の任意の元 //a//, //b//}} に対し、//a// ≤ //b//}} または //b// ≤ //a//}} が成り立つ。「≤}}」が全順序律を満たさない場合、「//a// ≤ //b//}}」でも「//b// ≤ //a//}}」でもないときがある。このとき a}} と b}} は比較不能  であるという。

1.1. 前順序前順序・半順序・全順序
-------------------

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

≤}} が反射律と推移律を満たすとき、≤}} を P}} 上の前順序  または擬順序  という。
≤}} が前順序でありさらに反対称律を満たすとき、≤}} を P}} 上の半順序  という。
≤}} が半順序でありさらに全順序律を満たすとき、≤}} を P}} 上の全順序  という。≤}} が前順序であるとき }} を前順序集合という。同様に ≤}} が半順序なら }} は半順序集合、全順序なら }} は全順序集合という。また集合 P}} は }} の台集合  あるいは台 }} と呼ばれる。紛れがなければ ≤}} を省略し、P}} を順序集合という。

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

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

全順序を線型順序ともいい、全順序集合を鎖と呼ぶこともある。また半順序集合の部分集合 A}} で A}} の任意の異なる2元が比較不能であるものを反鎖という。半順序集合のことを部分順序集合と呼ぶこともあるが部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。

半順序集合の元 a}} が他の元 b}} によって被覆関係  とは、a}} は b}} よりも真に小さく、かつそれらの間に別の元が入ることはないことをいう。つまり とは次の3つがすべて成り立つことである：

1.2. 順序集合の例
-----------

実数全体の集合 R}} およびその部分集合は、通常の大小関係により全順序集合となる。しかし、複素数全体の集合 C}} には複素数の乗法と"両立"する全順序は存在しない。単に全順序を入れるだけであれば、直積集合 R × R}} に辞書式順序を定めることができる。
自然数全体の成す集合は整除関係を順序として半順序集合である。
集合の冪集合に対して、包含関係による順序を入れると半順序集合となる。これはもとの集合の元の個数が2個以上であれば全順序でない。例えば mset の冪集合について、例えば mset と mset を考えれば、これらは比較不能であり、全順序ではない。
線形空間の部分空間全体は包含関係で順序付けられた半順序集合である。
半順序集合 P}} に対し、P}} の元の列全体の成す集合は、列 1=//a// = (//asub, 1=//b// = (//bsub に対し、 と定めると半順序集合となる。
集合 X}} と半順序集合 P}} に対し、X}} から P}} への写像全体の成す写像空間は、2つの写像 //f//, //g//}} に対して、//f// ≤ //g//}} を X}} の任意の元 x}} に対して //f// ≤ //g//}} となることとして定義すると、半順序集合になる。
有向非巡回グラフの頂点集合は、到達不可能性によって順序付けられる。
半順序集合における順序関係の向きが //a// < //b// > //c// < //d// …}} というように交互に入れ替わる列をフェンス と呼ぶ。

2. 逆順序、狭義の順序、双対順序
-----------------

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

2.1. 逆順序
--------

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

により定義される。

2.2. 狭義の順序
----------

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

…狭義の逆順序「>}}」も同様に定義される。

狭義の順序「<}}」の対義語として、等しいことも許容する順序「≤}}」のことを広義の順序という。

 式で定義された「<}}」を「≤}}」の反射的簡約 en という。

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

非反射性：¬}};
非対称性：//a// < //b//}} ならば ¬}};
推移性：//a// < //b//}} かつ //b// < //c//}} ならば 以上では広義の順序を定義してから狭義の順序を定義したが、逆に上の三性質を満たすものを狭義の順序として定義し、広義の順序を

…により定義することもできる。この場合、 式で定義された「≤}}」を「<}}」の反射閉包という。「<}}」が前述の3条件を満たせば反射閉包「≤}}」が半順序であることを簡単に示すことができる。

2.3. 双対順序集合
-----------

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

と定義する。すると、「」も P}} 上の順序になっていることが容易に分かる。 を }} の双対順序集合という。

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

3. ハッセ図
-------

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

頂点：P}} の元 //a// ∈ //P//}} から //b// ∈ //P//}} への辺がある ⇔ //a// < //b//}} であり、しかも //a// < //c// < //b//}} を満たす //c// ∈ //P//}} が存在しないこの有向グラフを図示したものをハッセ図という。

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

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

//a// < //b// ⇔ //a//}} から b}} への道があるしたがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。

4. 上界上界、最大、極大、上限、上方集合
---------------------

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

x}} が A}} の上界  であるとは、A}} の任意の元 y}} に対して //y// ≤ //x//}} となること。
x}} が A}} の上限  あるいは最小上界  であるとは、x}} が A}} の上界全体の集合の最小元となること。これは存在すれば一意的に決まり、sup //A//}} あるいは lub //A//}} と表される。
x}} が A}} の最大元  であるとは、x}} は A}} の元であり、かつ x}} は A}} の上界であること。これは存在すれば一意的に決まり、max //A//}} で表される。
x}} が A}} の極大元  であるとは、x}} は A}} の元であり、かつ //y// > //x//}} を満たす //y// ∈ //A//}} が存在しないこと。
x}} が A}} の下界  であるとは、A}} の任意の元 y}} に対して //y// ≥ //x//}} となること。
x}} が A}} の下限  あるいは最大下界  であるとは、x}} が A}} の下界全体の集合の最大元となること。これは存在すれば一意的に決まり、inf //A//}} あるいは glb //A//}} と表される。
x}} が A}} の最小元  であるとは、x}} は A}} の元であり、かつ x}} は A}} の下界であること。これは存在すれば一意的に決まり、min //A//}} で表される。
x}} が A}} の極小元  であるとは、x}} は A}} の元であり、かつ //y// < //x//}} を満たす //y// ∈ //A//}} が存在しないこと。上界および上限の定義において、 x}} が必ずしも A}} の元であるとは限らない、ことには注意が必要である。左閉右開の半開区間 には最大元は存在しないが上界および上限は存在する。

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

さらに A}} が P}} の上方集合であるとは、任意の //a// ∈ //A// }} と //x// > //a// }}  を満たす任意の P}} の元に対し//x// ∈ //A//}} となることをいう。

4.1. 具体例
--------

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

5. 写像と順序
--------

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

5.1. 定義
-------

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

//f//: //S// → //T//}} が順序を保つ写像とは、任意の //x//, //y// ∈ //S//}} に対して
//f//: //S// → //T//}} が順序を逆にするとは、任意の //x//, //y// ∈ //S//}} に対して
上の2つを合わせて単調  写像という。
f}} が順序を反映する  とは、任意の //x//, //y// ∈ //S//}} に対して
f}} が順序埋め込みであるとは、任意の //x//, //y// ∈ //S//}} に対して
f}} が順序同型であるとは、f}} が順序埋め込みな全単射であることをいう。//f//: //S// → //T//}} が順序埋め込みであるとき、S}} は f}} によって T}} に埋め込まれるという。 また順序同型 //f//: //S// → //T//}} が存在するとき、S}} と T}} は順序同型あるいは単に同型であるという。

5.2. 性質
-------

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

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

5.3. 具体例
--------

自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像 //f//: N → //P//}} を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合であるが単射ではないし、順序を反映もしない。少し設定を変えて、各自然数にその素冪の集合を対応させる写像 //g//: N → //P//}} を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではないが終域を g}} の値域 //g//}} に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎な分配束と呼ばれる半順序集合のクラスに対して一般化することができる。

6. 区間
-----

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

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

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

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

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

7. 順序構造と位相構造
------------

7.1. 全順序集合の位相
-------------

7.1.1. 順序位相
-----------

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

全体の集合を準開基とする位相を順序位相  という原理的には半順序集合であっても同様の概念を定義できるが、本稿の英語版をはじめ、誰範囲。例えば、実数全体の集合 を通常の大小関係 ≤ による全順序集合と見ると、その順序位相は通常の距離により定められる位相と同等になる。

全順序集合 //A// の部分集合 //B// には、//B// を全順序集合と見なした時の順序位相と //A// の順序位相から誘導される位相との2つの位相が入る。しかしこの2つの位相は一致するとは限らない。。

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

を考えると、//A// から//B// に誘導される位相では一元集合 mset は明らかに開集合であるが、//B// は順序集合としてみたときはそうではない。実際 //B// は と順序同型だが、//C// の順序位相で mset は開集合ではないので //B// の順序位相でmset は開集合ではない。

7.1.2. 上極限位相、下極限位相
------------------

単に「実数体上の位相」といった場合、前述の順序位相を指すがその他の位相を考えることもできる。

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

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

全体の集合を開基とする位相のことである実数体でなくとも上極限位相と下極限位相を考えることができるが、これも実数体以外に対してこれらの位相を定義した文献が見つけられなかったので、ここでは実数体のみを対象にした。}}。

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

7.1.3. overlapping interval topology
------------------------------------

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

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

7.2. 半順序集合の位相
-------------

7.2.1. 半順序空間
------------

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

//a// < //b//}} を満たす任意の//a//, //b// ∈ //P//}} に対し、//a// の開近傍//U//で上方集合であるものと //b// の開近傍//V// で下方集合であるものが存在することである。 なお、半順序空間と名前の似たposet topologyは別概念であるので注意が必要である。

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

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

//asub かつ任意の //i// に対して //asub ならば //a// ≤ //b//}} である位相構造を持つ半順序集合//P// が半順序空間である必要十分条件は以下を満たすことである：

半順序集合//P// 上の位相構造として、 //a// ≤ //b// } が直積位相に関する閉部分集合になる。2つ半順序空間の間の順序を保つ連続写像のことをdimapという。

7.2.2. 上方位相、下方位相
----------------

順序集合 //P// 上の以下の2つの位相は同一である事が簡単に示せる。以下のいずれか一方の条件を満たす位相を上方位相という。

x &leq; a} for //a// ∈ //P//}} を全て閉集合とする最弱の位相
任意の//a// ∈ //P//}} に対し、一点集合mset の閉包が x &leq; a} と一致する最弱の位相下方位相も同様にして定義できる。

7.2.3. アレクサンドロフ空間
-----------------

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

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

//U// が //P// の開集合 ⇔ //U// が //P// の上方集合により //P// に位相を入れたものはアレクサンドロフ空間になる。

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

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

で定義される前順序のことである。上式では一元集合mset の閉包である。

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

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

7.2.3.1. 実数体における例
-----------------

実数体を前順序集合と見なすことで実数体にアレクサンドロフ位相を入れることができる。アレクサンドロフ位相における実数体上の開集合は以下のもののいずれかになる：

for some //a//
for some //a//
空集合、全体集合

7.2.4. スコット位相
-------------

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

//O// ⊂ //P// は上方集合である
//P// の有向部分集合 //A// で//A// の極限が//O// に入っていれば、//A// の点で//O// に含まれるものが存在する後者の条件は内点概念の点列による特徴づけに類似しており、この条件が「下に閉じた」集合を排除する。

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

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

//P// の任意の有向部分集合//A// に対し、//A// が//P// 内の上限を持てば//f// も//Q// 内の上限を持ち、sup //f//  = //f//  が成立する。スコット連続な関数は順序を保つ。実際、//x// ≥ //y// ⇒ sup{//x// , //y// } = //x// であるので、上述した条件よりsup//f// , //f// }}}が存在し、しかも sup{//f// , //f// } = //f//  = //f//  となる。これは//f//  ≥ //f// }} を意味する。

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

7.3. ストーン双対性
------------

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

8. 直積集合上の順序
-----------

2つの半順序集合の直積集合上の半順序としては次の三種類がある。

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

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

9. 圏としての順序集合
------------

任意の半順序集合は、任意の射集合が高々一つの元からなる圏と見なすことができる。具体的には、射の集合を //x// ≤ //y//}} ならば 1=hom = msetとし、1=∘ = }} と定義する。2つの半順序集合が圏として同値となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏は同型射閉圏いる。

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

10. その他
-------

n}} 個の元からなる集合上の半順序の総数は 1, 1, 3, 19, 219, 4231, …}} 。同型を除いた総数は 1, 1, 2, 5, 16, 63, 318, …}} 。
半順序集合 P}} の全順序集合への埋め込みを線型順序拡大  という。任意の半順序は全順序に拡張することができる。計算機科学において半順序の線型拡張を求めるアルゴリズムは位相ソート en と呼ばれる。

11. 関連項目
--------

反マトロイド: 半順序集合よりも一般の順序付けの族を許すような、集合上の順序付けの一般化
因果集合
有向集合
半束
束 
順序群
準順序 
狭義弱順序: "//a// < //b// または //b// < //a// の何れかが成り立つ" という関係が推移的となるような狭義半順序 "<"
完備半順序 
ツォルンの補題
コンパクト要素

12. 脚注
------

12.1. 注釈
--------

12.2. 出典
--------

13. 参考文献
--------

14. 外部リンク
---------

A001035}}: Number of posets with //n// labeled elements in the OEIS
A000112}}: Number of posets with //n// unlabeled elements in the OEIS