順序集合

数学において順序集合（じゅんじょしゅうごう、）とは、大小関係や血縁関係のような順序が定義された集合のことである。順序は一般に二項関係として定義されるが、その順序集合の任意の2つの元に対して必ず定まるとは限らない。
比較不能の場合を許容する順序集合として典型的なのは後述する半順序集合（）である。特に、半順序集合で全ての2元が比較可能であるものを全順序集合（）という。
全順序の最も簡単な例は、実数における大小関係である。
一方、全順序ではない半順序集合の例としては、正の整数全体の集合に整除関係で順序を入れたものや、（2つ以上元を含む）集合の冪集合において、包含関係を順序と見なしたものがある。例えば2元集合 において と はいずれも他方を包含していないので の冪集合は全順序ではない。
定義.
前順序、半順序、全順序を順に定義するために、まず以下の性質を考える。ここで は集合であり、「」を 上で定義された二項関係とする。
「」が全順序律を満たさない場合、「」でも「」でもないときがある。このとき と は比較不能 (incomparable) であるという。
前順序・半順序・全順序.
 を集合とし、 を 上で定義された二項関係とする。
 が前順序であるとき を前順序集合という。同様に が半順序なら は半順序集合、全順序なら は全順序集合という。また集合 は の台集合 () あるいは台 と呼ばれる。紛れがなければ を省略し、 を（いずれかの意味で）順序集合という。
順序集合 に対し、 を台 上の順序関係ともいう。なお多くの数学の分野では半順序集合を主に扱うので、単に順序あるいは順序集合といった場合はそれぞれ半順序、半順序集合を意味する場合が多いが、分野によっては、主な対象が半順序集合でなく前順序集合や全順序集合である場合があり、そのような分野では前順序集合や全順序集合の意味で「順序集合」という言葉が用いられることがあるので注意が必要である。
上では順序を記号 で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号 と区別するため、順序の記号として formula_1 や formula_2 を使うこともある。
全順序を線型順序ともいい、全順序集合を鎖と呼ぶこともある。また半順序集合の部分集合 で の任意の異なる2元が比較不能であるものをという。が部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。
半順序集合の元 が他の元 によって () とは、 は よりも真に小さく、かつそれらの間に別の元が入ることはないことをいう。つまり formula_3 とは次の3つがすべて成り立つことである：formula_4
逆順序、狭義の順序、双対順序.
上で述べた順序関係「」は直観的には左辺が右辺「よりも小さい、もしくは等しい」ことを意味しているが、逆に左辺が右辺「よりも大きい、もしくは等しい」順序関係や等しいことを許容しない順序関係を考えることもできる。
逆順序.
「大きい、もしくは等しい」ことを意味する順序関係は「」の逆順序と呼ばれ、
により定義される。
狭義の順序.
一方、等しいことを許容しない順序は狭義の（半）順序と呼ばれ、以下のように定義される：
狭義の逆順序「」も同様に定義される。
狭義の順序「」の対義語として、等しいことも許容する順序「」のことを広義の（半）順序（もしくは弱い意味 の（半）順序、反射的 な(半)順序）という。
(1) 式で定義された「」を「」の反射的簡約 という。
「」が半順序であるとき、その反射的簡約「」は任意の に対して以下を満たす：
以上では広義の順序を定義してから狭義の順序を定義したが、逆に上の三性質（非対称性は非反射性と推移性より得られるので条件としては不要）を満たすものを狭義の順序として定義し、広義の順序を
により定義することもできる。この場合、(2) 式で定義された「」を「」のという。「」が前述の3条件を満たせば反射閉包「」が半順序であることを簡単に示すことができる。
双対順序集合.
 を順序集合とするとき、"P" 上の二項関係「formula_9」を
と定義する（すなわち「formula_9」は「」の逆順序を順序と見なしたものである）。すると、「formula_9」も 上の順序になっていることが容易に分かる。formula_13 を の双対順序集合という。
双対順序集合はその定義 formula_13 よりもとの順序集合 とは"大小が逆転"している。したがって における上限、極大元、最大元（定義は後述）は formula_13 ではそれぞれ下限、極小元、最小元に対応している。
ハッセ図.
 を有限集合とし、「」を 上の狭義の半順序とするとき、以下のようにして を自然に単純有向グラフと見なせる：
この有向グラフを図示したものをハッセ図という。
ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。例えばこの図で と は比較可能だが、 と は比較不能である。また単集合の族 は反鎖である。さらに は によって被覆されるが、 には被覆されない。
なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に を閉路を持たない有限な単純有向グラフとすると、 上に以下の順序を入れることで を半順序集合と見なせる：
したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。
上界、最大、極大、上限、上方集合.
 を半順序集合とし、 をその部分集合とし、 を の元とする。このとき上界、上限、最大、極大の概念、およびこれらの双対概念である下界（かかい）、下限、最小、極小は以下のように定義される：
上界および上限の定義において、 が必ずしも の元であるとは限らない、ことには注意が必要である。左閉右開の半開区間 formula_16 には最大元は存在しないが上界および上限は存在する（つまり、 ）。
極大元の概念と最大元の概念は以下の点で異なる。まず が の極大元であるとは、 の元は「 以下である」か、もしくは「 とは大小が比較不能である」かのいずれかである事を意味する。一方 が の最大元であるとは の元は常に 以下である事を意味する（このとき は の任意の元と比較が可能である）。したがって最大元は必ず極大元であるが、極大元は必ずしも最大元であるとは限らない（下の具体例参照）。全順序集合においては必ず極大元は最大元に一致する。
さらに が の（resp. 下方集合）であるとは、任意の と (resp. ) を満たす任意の の元に対し となることをいう。
具体例.
正整数全体の成す集合を整除関係で順序付けるとき、 は任意の正整数を割り切るという意味において は最小元である。しかしこの半順序集合には最大元は存在しない（任意の正整数の倍数としての を追加して考えたとするならば、それが最大元になる）。この半順序集合には極大元も存在しない。実際、任意の元 はそれとは異なる。例えば を割り切るから は極大ではありえない。この半順序集合から最小元である を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の素数をとることができる。この半順序に関して は部分集合 の上界（上限ではない）を与えるが、 は除かれているので下界は持たない。他方、の冪全体の成す部分集合に対して はその下界（これは下限でもある）を与えるが、上界は存在しない。
写像と順序.
順序に関する写像の概念に以下のものがある：
定義.
 を順序集合とし、 を写像とする。このとき
 が順序埋め込みであるとき、 は によって に（順序集合として）埋め込まれるという。
また順序同型 が存在するとき、 と は順序同型あるいは単に同型であるという。
性質.
上で述べた概念は以下の性質を満たす：
具体例.
自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像 を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合である（すなわち、 が を割るならば の各素因数は の素因数にもなる）が単射ではない（例えば も もこの写像で に写る）し、順序を反映もしない（例えば は を割らない）。少し設定を変えて、各自然数にそのの集合を対応させる写像 を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない（実際、たとえば単集合 に移る数は無い）が終域を の値域 に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎なと呼ばれる半順序集合のクラスに対して一般化することができる（の項を参照）。
区間.
 を順序集合とし、 を の元とするとき、閉区間 と開区間 を以下のように定義する：
さらに および を以下のように定義し、半開区間と呼ぶ：
文献によっては , , のことを , , と表す場合もある。
半順序集合がであるとは、全ての区間が有限集合であることをいう。例えば、整数全体の成す集合は通常の大小関係による半順序に関して局所有限である（端点の無い無限区間のようなものは今考えていない）。
順序集合における区間の概念と、として知られる特定の半順序の類いとを混同してはならない。
順序構造と位相構造.
全順序集合の位相.
順序位相.
全順序集合 "A" に対し、無限半開区間
全体の集合を準開基とする位相を順序位相 () という。例えば、実数全体の集合 formula_23 を通常の大小関係 ≤ による全順序集合と見ると、その順序位相は通常の距離により定められる位相と同等になる。
全順序集合 "A" の部分集合 "B" には、"B" を全順序集合と見なした時の順序位相と "A" の順序位相から誘導される位相との2つの位相が入る。しかしこの2つの位相は一致するとは限らない。（"B" の順序位相における開集合は誘導位相でも開集合であるが逆は一般には成り立たない）。
例えば "A" を実数全体の集合とし、"A" の部分集合
を考えると、"A" から"B" に誘導される位相では一元集合 は明らかに開集合であるが、"B" は順序集合としてみたときはそうではない。実際 "B" は（2を1に移す写像により）formula_25 と順序同型だが、"C" の順序位相で は開集合ではないので "B" の順序位相で は開集合ではない。
上極限位相、下極限位相.
単に「実数体上の位相」といった場合、前述の順序位相を指すがその他の位相を考えることも（主に反例として用いるために）できる。
実数体 formula_23 上の上極限位相とは
全体の集合を開基とする位相のことであり、同様に formula_23 上のとは逆向きの半開区間
全体の集合を開基とする位相のことである。
実数体に下極限位相を入れた空間はしばし formula_30 と書かれ、ゾルゲンフライ直線と呼ばれる。またゾルゲンフライ直線2つの直積 formula_31 はと呼ばれる。
overlapping interval topology.
区間 [-1,1] 上の とは
を準開基とする位相である。
半順序集合の位相.
半順序空間.
位相構造を持つ半順序集合"P" で以下の性質を満たすものをという：
（"P" の位相構造でこの性質を満たすものは1つとは限らないが、それらを全て半順序空間という。）
なお、半順序空間と名前の似たは別概念であるので注意が必要である。
定義より明らかに半順序空間は常にハウスドルフ性を満たす。
半順序空間では以下が成立する：
位相構造を持つ半順序集合"P" が半順序空間である必要十分条件は以下を満たすことである：
2つ半順序空間の間の順序を保つ連続写像のことをdimapという。
上方位相、下方位相.
順序集合 "P" 上の以下の2つの位相は同一である事が簡単に示せる。以下のいずれか一方（したがって両方）の条件を満たす位相をという。
下方位相も同様にして定義できる。
アレクサンドロフ空間.
位相空間 "P" がであるとは、"P" 上の（有限または無限個の）任意の開集合の共通部分が必ず開集合になることである。
アレクサンドロフ空間は前順序集合と自然に1対1対応していることが知られている。
実際任意の前順序集合 "P" に対し、
により "P" に位相を入れたものはアレクサンドロフ空間になる。（この位相を "P" のアレクサンドロフ位相という。）
逆に任意のアレクサンドロフ空間 "P" に対し "P" 上の「」を前順序とすることで "P" を前順序集合と見なすことができる。
ここで位相空間 "P" のspecialization preorderとは
で定義される前順序のことである。上式でformula_36は一元集合 の閉包である。（なお、"P" がT空間であればspecialization preorder は半順序であることが知られている。）
以上の対応関係により、集合"P" におけるアレクサンドロフ空間としての構造と"P" 上の前順序は1対1対応する。
specialization preorderはアレクサンドロフ空間でなくとも定義可能であるが、アレクサンドロフ空間でない位相空間上ではspecialization preorderに対して上方集合でない開集合も存在する。（なおこの場合でも開集合は常に上方集合である）。したがって前述したような、上方集合を開集合とする位相を考えても元の位相は復元できない。
実数体における例.
実数体（に通常の順序をいれたもの）を前順序集合と見なすことで実数体にアレクサンドロフ位相を入れることができる。アレクサンドロフ位相における実数体上の開集合（すなわち上方集合）は以下のもののいずれかになる：
スコット位相.
上で述べたようにアレクサンドロフ位相は formula_38 のような「下に閉じた」集合すらも開集合と見なしてしまう。アレクサンドロフ位相からこのような不自然さを取り除いたのがスコット位相である。順序集合 "P" 上のスコット位相 () とは、以下の2条件を満たす "P" の部分集合 "O" 全体の集合を開集合族とする位相である：
後者の条件は内点概念の点列による特徴づけ（"O" の内点"x" に収束する点列は"O" と共通部分を持つ）に類似しており、この条件が「下に閉じた」集合を排除する。
よって実数体にスコット位相を入れた際、実数体上の開集合は以下のもののいずれかになる：
スコット位相を入れた順序集合をスコット空間といい、スコット空間からスコット空間への連続写像をスコット連続 () という。順序集合 "P" から順序集合"Q" への写像 "f" がスコット連続である必要十分条件は以下の性質が成り立つことであることが知られている：
スコット連続な関数は順序を保つ。実際、"x" ≥ "y" ⇒ sup{"x" , "y" } = "x" であるので、上述した条件より}が存在し、しかも sup{"f" ("x" ), "f" ("y" )} = "f" (sup{"x" , "y" }) = "f" ("x" ) となる。これは を意味する。
なお、スコット位相と下方位相のいずれよりも強い位相構造の中で最弱のものをという。
ストーン双対性.
位相空間の開集合全体の集合は包含関係により順序集合と見なせる。位相空間が「sober性」という弱い性質を満たす時はこの順序構造のみで位相空間の構造が特徴づけられることが知られている（ストーンの双対性定理）。したがってsober性を満たす空間に話を限定すれば、点集合論に頼らなくても順序構造のみで位相空間論を展開できる（ポイントレス位相空間論）。
直積集合上の順序.
2つの半順序集合（の台集合）の直積集合上の半順序としては次の三種類がある。
最後の順序は対応する狭義全順序の直積の反射閉包である。これらの三種類の半順序は、いずれも3個以上の半順序集合の直積に対しても同様に定義される。
体上の順序線型空間に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれも再び順序線型空間となる。
圏としての順序集合.
任意の半順序集合（および前順序集合）は、任意の射集合が高々一つの元からなる圏と見なすことができる。具体的には、射の集合を ならば （それ以外の場合は空集合）とし、 と定義する。2つの半順序集合が圏として同値となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏はいる。
半順序集合からの函手、すなわち半順序圏で添字付けられた図式は、可換図式である。