順序集合

テンプレート:Redirect テンプレート:複数の問題 順序集合（じゅんじょしゅうごう、テンプレート:Lang-en-short）は集合の要素の間に順序が定義された集合。順序とは二項関係であって後述する反射律・推移律などを満たすものであり、数の大小関係などを一般化したものである。

全ての2要素が比較可能（順序が定義されている）ものを特に全順序集合（テンプレート:En）という。例えば実数における大小関係は全順序集合である。

また、全順序ではない順序集合の例としては、正の整数全体の集合に整除関係で順序を定めたものや、（2つ以上元を含む）集合の冪集合において、包含関係を順序と見なしたものがある。

後述するように、順序が満たすべき公理の種類により、前順序集合、半順序集合（テンプレート:En）、全順序集合がある。多く場合、半順序集合を指して「順序集合」と呼ぶことが多いが、分野によっては前順序集合や全順序集合を指す場合がある。

定義

まず、二項関係について以下の用語を定める。

ここでテンプレート:Mvar は集合であり、「テンプレート:Math」をテンプレート:Mvar 上で定義された二項関係とする。

反射律：テンプレート:Mvar の任意の元テンプレート:Mvar に対し、テンプレート:Math が成り立つ。
推移律：テンプレート:Mvar の任意の元テンプレート:Mvar, テンプレート:Mvar, テンプレート:Mvar に対し、テンプレート:Math かつテンプレート:Math ならばテンプレート:Math が成り立つ。
反対称律：テンプレート:Mvar の任意の元テンプレート:Math2 に対し、テンプレート:Math かつテンプレート:Math ならばテンプレート:Math が成り立つ。
全順序律：テンプレート:Mvar の任意の元テンプレート:Math2 に対し、テンプレート:Math2 またはテンプレート:Math2 が成り立つ。

また、「テンプレート:Math」が全順序律を満たさない場合（すなわちテンプレート:Math2でもテンプレート:Math2ないとき、テンプレート:Mvar とテンプレート:Mvar は比較不能 (incomparable) であると言う。

テンプレート:Anchors前順序・半順序・全順序

テンプレート:Mvar を集合とし、テンプレート:Math をテンプレート:Mvar 上で定義された二項関係とする。

テンプレート:Math が反射律と推移律を満たすとき、テンプレート:Math をテンプレート:Mvar 上のテンプレート:仮リンク (テンプレート:En) または擬順序 (テンプレート:En) という。
テンプレート:Math が前順序でありさらに反対称律を満たすとき、テンプレート:Math をテンプレート:Mvar 上の半順序 (テンプレート:En) という。
テンプレート:Math が半順序でありさらに全順序律を満たすとき、テンプレート:Math をテンプレート:Mvar 上の全順序 (テンプレート:En) という。

テンプレート:Math が前順序であるときテンプレート:Math を前順序集合という。同様にテンプレート:Math が半順序ならテンプレート:Math は半順序集合、全順序ならテンプレート:Math は全順序集合であるという。また集合テンプレート:Mvar はテンプレート:Math の台集合 (テンプレート:En) あるいは台テンプレート:En と呼ばれる。紛らわしくなければテンプレート:Math を省略し、テンプレート:Mvar を（いずれかの意味で）順序集合という。

順序集合テンプレート:Math に対し、テンプレート:Math を台テンプレート:Mvar 上の順序関係ともいう。

上では順序を記号テンプレート:Math で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号テンプレート:Math と区別するため、順序の記号として $≺$ や $≪$ を使うこともある。

全順序を線型順序ともいい、全順序集合を鎖と呼ぶこともある。また半順序集合の部分集合テンプレート:Mvar でテンプレート:Mvar の任意の異なる2元が比較不能であるものをテンプレート:仮リンクという。テンプレート:要出典が部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。

半順序集合の元テンプレート:Mvar が他の元テンプレート:Mvar によってテンプレート:仮リンク (テンプレート:Math) とは、テンプレート:Mvar はテンプレート:Mvar よりも真に小さく、かつそれらの間に別の元が入ることはないことをいう。つまり $a < : b$ とは次の3つがすべて成り立つことである： $a \leq b, a \neq b, \neg [\exists c s.t. a < c < b] .$

順序集合の例

実数全体の集合テンプレート:Mathbf およびその部分集合（例えば、自然数全体の集合テンプレート:Mathbf, 整数全体の集合テンプレート:Mathbf, 有理数全体の集合テンプレート:Mathbf）は、通常の大小関係により全順序集合となる。しかし、複素数全体の集合テンプレート:Mathbf には複素数の乗法と"両立"する全順序は存在しない（順序体でない）。単に全順序を入れるだけであれば、直積集合テンプレート:Math に辞書式順序を定めることができる。
自然数全体の成す集合は整除関係を順序として半順序集合である。
集合の冪集合に対して、包含関係による順序を入れると半順序集合となる。これはもとの集合の元の個数が2個以上であれば全順序でない。例えばテンプレート:Math の冪集合

{\emptyset, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}

について、例えばテンプレート:Math とテンプレート:Math を考えれば、これらは比較不能であり（テンプレート:Mathでもテンプレート:Math2でもない）、全順序ではない。

線形空間の部分空間全体は包含関係で順序付けられた半順序集合である。
半順序集合テンプレート:Mvar に対し、テンプレート:Mvar の元の（自然数で添え字付けられた）列全体の成す集合は、列テンプレート:Math, テンプレート:Math に対し、
$a \leq b ⟺ a_{n} \leq b_{n} (\forall n \in ℕ)$
と定めると半順序集合となる。
集合テンプレート:Mvar と半順序集合テンプレート:Mvar に対し、テンプレート:Mvar からテンプレート:Mvar への写像全体の成すテンプレート:仮リンクは、2つの写像テンプレート:Math2 に対して、テンプレート:Math をテンプレート:Mvar の任意の元テンプレート:Mvar に対してテンプレート:Math となることとして定義すると、半順序集合になる。
有向非巡回グラフの頂点集合は、到達不可能性によって順序付けられる。
半順序集合における順序関係の向きがテンプレート:Math2 というように交互に入れ替わる列をテンプレート:仮リンクと呼ぶ。

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

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

逆順序

「大きい、もしくは等しい」ことを意味する順序関係は「テンプレート:Math」の逆順序と呼ばれ、

a \geq b ⟺ b \leq a

により定義される。

狭義の順序

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

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

…(1)

狭義の逆順序「テンプレート:Math」も同様に定義される。

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

(1) 式で定義された「テンプレート:Math」を「テンプレート:Math」の反射的簡約 テンプレート:Lang という。

「テンプレート:Math」が半順序であるとき、その反射的簡約「テンプレート:Math」は任意のテンプレート:Math2 に対して以下を満たす：

非反射性：テンプレート:Math;
非対称性：テンプレート:Math ならばテンプレート:Math; （非反射性と推移性から従う）
推移性：テンプレート:Math かつテンプレート:Math ならばテンプレート:Math

以上では広義の順序を定義してから狭義の順序を定義したが、逆に上の三性質（非対称性は非反射性と推移性より得られるので条件としては不要）を満たすものを狭義の順序として定義し、広義の順序を

a \leq b ⟺ a < b \lor a = b

…(2)

により定義することもできる。この場合、(2) 式で定義された「テンプレート:Math」を「テンプレート:Math」のテンプレート:仮リンクという。「テンプレート:Math」が前述の3条件を満たせば反射閉包「テンプレート:Math」が半順序であることを簡単に示すことができる。

双対順序集合

テンプレート:Math を順序集合とするとき、P 上の二項関係「 $≼$ 」を

a ≼ b ⟺ b \leq a

と定義する（すなわち「 $≼$ 」は「テンプレート:Math」の逆順序を順序と見なしたものである）。すると、「 $≼$ 」もテンプレート:Mvar 上の順序になっていることが容易に分かる。 $(P, ≼)$ をテンプレート:Math の双対順序集合という。

双対順序集合はその定義 $(P, ≼)$ よりもとの順序集合テンプレート:Math とは"大小が逆転"している。したがってテンプレート:Math における上限、極大元、最大元（定義は後述）は $(P, ≼)$ ではそれぞれ下限、極小元、最小元に対応している。

ハッセ図

テンプレート:Mvar を有限集合とし、「テンプレート:Math」をテンプレート:Mvar 上の狭義の半順序とするとき、以下のようにしてテンプレート:Mvar を自然に単純有向グラフと見なせる：

頂点：テンプレート:Mvar の元

テンプレート:Math からテンプレート:Math への辺があるテンプレート:Math であり、しかもテンプレート:Math を満たすテンプレート:Math が存在しない

（すなわちテンプレート:Mvar はテンプレート:Mvar を被覆している）

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

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

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

テンプレート:Math からテンプレート:Mvar への道がある

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

テンプレート:Anchors上界、最大、極大、上限、上方集合

テンプレート:Mvar を半順序集合とし、テンプレート:Mvar をその部分集合とし、テンプレート:Mvar をテンプレート:Mvar の元とする。このとき上界、上限、最大、極大の概念、およびこれらの双対概念である下界（かかい）、下限、最小、極小は以下のように定義される^[1]：

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

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

上界および上限の定義において、テンプレート:Mvar が必ずしもテンプレート:Mvar の元であるとは限らない、ことには注意が必要である。左閉右開の半開区間 $[a, b)$ には最大元は存在しないが上界および上限は存在する（つまり、テンプレート:Mvar）。

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

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

具体例

正整数全体の成す集合を整除関係で順序付けるとき、テンプレート:Math は任意の正整数を割り切るという意味においてテンプレート:Math は最小元である。しかしこの半順序集合には最大元は存在しない（任意の正整数の倍数としてのテンプレート:Math を追加して考えたとするならば、それが最大元になる）。この半順序集合には極大元も存在しない。実際、任意の元テンプレート:Mvar はそれとは異なる。例えばテンプレート:Math を割り切るからテンプレート:Mvar は極大ではありえない。この半順序集合から最小元であるテンプレート:Math を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の素数をとることができる。この半順序に関してテンプレート:Math は部分集合テンプレート:Math の上界（上限ではない）を与えるが、テンプレート:Math は除かれているので下界は持たない。他方、[[2の冪|テンプレート:Math の冪]]全体の成す部分集合に対してテンプレート:Math はその下界（これは下限でもある）を与えるが、上界は存在しない。

写像と順序

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

定義

テンプレート:Math2 を順序集合とし、テンプレート:Math を写像とする。このとき

テンプレート:Math がテンプレート:仮リンク(order-preserving)（同調 (isotone) とも）とは、

任意のテンプレート:Math2 に対してテンプレート:Math

テンプレート:Math が順序を逆にする（テンプレート:仮リンク）とは、

任意のテンプレート:Math2 に対してテンプレート:Math

上の2つを合わせて単調 (monotone) 写像という。
テンプレート:Mvar が順序を反映する (order-reflecting) とは、

任意のテンプレート:Math2 に対してテンプレート:Math

テンプレート:Mvar がテンプレート:仮リンクであるとは、

任意のテンプレート:Math2 に対してテンプレート:Math

テンプレート:Mvar がテンプレート:仮リンクであるとは、テンプレート:Mvar が順序埋め込みな全単射であることをいう。

テンプレート:Math が順序埋め込みであるとき、テンプレート:Mvar はテンプレート:Mvar によってテンプレート:Mvar に（順序集合として）埋め込まれるという。また順序同型テンプレート:Math が存在するとき、テンプレート:Mvar とテンプレート:Mvar は順序同型あるいは単に同型であるという。

性質

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

順序を反映する写像は単射である。実際テンプレート:Math かつテンプレート:Math かつテンプレート:Math である。
テンプレート:Mvar が順序埋め込みである必要十分条件はテンプレート:Mvar が順序を保存し、しかも順序を反映することである。また全単射テンプレート:Math とその逆関数テンプレート:Math が順序同型ならテンプレート:Mvar, テンプレート:Math は順序同型である。
順序を保つ写像と順序を保つ写像の合成は順序を保つ。順序を反映する写像と順序を反映する写像の合成も順序を反映する。

具体例

テンプレート:Math2 の約数全体の成す半順序集合（整除関係で順序を入れる）とテンプレート:Math2 の整除関係で閉じた部分集合族（包含関係で順序を入れる）との間の順序同型

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

区間

テンプレート:Mvar を順序集合とし、テンプレート:Math2 をテンプレート:Mvar の元とするとき、閉区間 テンプレート:Math と開区間 テンプレート:Math を以下のように定義する：

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

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

さらにテンプレート:Math およびテンプレート:Math を以下のように定義し、半開区間と呼ぶ：

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

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

文献によってはテンプレート:Math, テンプレート:Math, テンプレート:Math のことをテンプレート:Math, テンプレート:Math, テンプレート:Math と表す場合もある。

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

順序集合における区間の概念と、テンプレート:仮リンクとして知られる特定の半順序の類いとを混同してはならない。

順序構造と位相構造

テンプレート:内容過剰

全順序集合の位相

順序位相

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

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

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

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

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

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

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

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

上極限位相、下極限位相

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

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

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

全体の集合を開基とする位相のことであり、同様に $ℝ$ 上のテンプレート:仮リンクとは逆向きの半開区間

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

全体の集合を開基とする位相のことであるテンプレート:Efn2。

実数体に下極限位相を入れた空間はしばし $ℝ_{ℓ}$ と書かれ、ゾルゲンフライ直線と呼ばれる。またゾルゲンフライ直線2つの直積 $ℝ_{ℓ} \times ℝ_{ℓ}$ はテンプレート:仮リンクと呼ばれる。

overlapping interval topology

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

[- 1, a)

for

0 < a

(b, 1]

for

b < 0

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

半順序集合の位相

半順序空間

位相構造を持つ半順序集合P で以下の性質を満たすものをテンプレート:仮リンクという：

テンプレート:Math を満たす任意のテンプレート:Math に対し、a の開近傍Uで上方集合であるものと b の開近傍V で下方集合であるものが存在することである。

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

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

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

テンプレート:Math かつ任意の i に対してテンプレート:Math ならばテンプレート:Math である^[2]

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

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

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

上方位相、下方位相

順序集合 P 上の以下の2つの位相は同一である事が簡単に示せる。以下のいずれか一方（したがって両方）の条件を満たす位相をテンプレート:仮リンクという。

{x ∈ P | x ≤ a} for テンプレート:Math を全て閉集合とする最弱の位相
任意のテンプレート:Math に対し、一点集合テンプレート:Math の閉包が{x ∈ P | x ≤ a} と一致する最弱の位相

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

アレクサンドロフ空間

位相空間 P がテンプレート:仮リンクであるとは、P 上の（有限または無限個の）任意の開集合の共通部分が必ず開集合になることである。

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

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

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

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

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

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

で定義される前順序のことである。上式で $\overline{{x}}$ は一元集合テンプレート:Math の閉包である。（なお、P が[[コルモゴロフ空間|Tテンプレート:Sub空間]]であればspecialization preorder は半順序であることが知られている。）

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

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

実数体における例

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

$(a, \infty)$ for some a
$[a, \infty)$ for some a
空集合 $\emptyset$ 、全体集合 $ℝ$

スコット位相

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

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

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

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

$(a, \infty)$ for some a
空集合 $\emptyset$ 、全体集合 $ℝ$

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

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

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

なお、スコット位相と下方位相のいずれよりも強い位相構造の中で最弱のものをテンプレート:仮リンクという。

ストーン双対性

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

直積集合上の順序

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

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

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

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

テンプレート:Math 上の直積狭義順序の反射閉包
テンプレート:Math 上の積順序
テンプレート:Math 上の辞書式順序

圏としての順序集合

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

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

その他

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

脚注

テンプレート:脚注ヘルプ

注釈

テンプレート:Notelist2

出典

テンプレート:Reflist

参考文献

テンプレート:No footnotes

外部リンク

テンプレート:Commons

テンプレート:OEIS: Number of posets with n labeled elements in the OEIS
テンプレート:OEIS: Number of posets with n unlabeled elements in the OEIS

[1] テンプレート:Cite web

[ward-1954-2] テンプレート:Cite journal

[3] テンプレート:Cite book

[1]

[2]

[3]

順序集合

目次