順序集合のソースを表示

{{redirect|順序|その他|wikt:順序}}
{{複数の問題
|独自研究 = 2019-06
|参照方法 = 2019-06
}}
'''順序集合'''（じゅんじょしゅうごう、{{Lang-en-short|ordered set}}）は集合の要素の間に順序が定義された[[集合]]。順序とは[[二項関係]]であって後述する反射律・推移律などを満たすものであり、数の大小関係などを一般化したものである。

全ての2要素が比較可能（順序が定義されている）ものを特に'''全順序集合'''（{{en|totally ordered set; toset}}）という。例えば[[実数]]における大小関係は全順序集合である。

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

後述するように、順序が満たすべき公理の種類により、'''前順序集合'''、'''半順序集合'''（{{en|partially ordered set; poset}}）、'''全順序集合'''がある。多く場合、半順序集合を指して「順序集合」と呼ぶことが多いが、分野によっては前順序集合や全順序集合を指す場合がある。

== 定義 ==

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

ここで {{mvar|P}} は集合であり、「{{math|≤}}」を {{mvar|P}} 上で定義された[[二項関係]]とする。

*[[反射関係|'''反射律''']]：{{mvar|P}} の任意の元 {{mvar|a}} に対し、{{math|''a'' ≤ ''a''}} が成り立つ。
*[[推移関係|'''推移律''']]：{{mvar|P}} の任意の元 {{mvar|a}}, {{mvar|b}}, {{mvar|c}} に対し、{{math|''a'' ≤ ''b''}} かつ {{math|''b'' ≤ ''c''}} ならば {{math|''a'' ≤ ''c''}} が成り立つ。
*'''反対称律'''：{{mvar|P}} の任意の元 {{math2|''a'', ''b''}} に対し、{{math|''a'' ≤ ''b''}} かつ {{math|''b'' ≤ ''a''}} ならば {{math|''a'' {{=}} ''b''}} が成り立つ。
*'''全順序律'''：{{mvar|P}} の任意の元 {{math2|''a'', ''b''}} に対し、{{math2|''a'' ≤ ''b''}} または {{math2|''b'' ≤ ''a''}} が成り立つ。

また、「{{math|≤}}」が全順序律を満たさない場合（すなわち{{math2|''a'' ≤ ''b''}}でも{{math2|''b'' ≤ ''a''}}ないとき、 {{mvar|a}} と {{mvar|b}} は'''比較不能''' (incomparable) であると言う。

=== {{anchors|前順序|半順序|全順序|前順序集合|半順序集合|全順序集合}}前順序・半順序・全順序 ===

{{mvar|P}} を集合とし、{{math|≤}} を {{mvar|P}} 上で定義された[[二項関係]]とする。
* {{math|≤}} が反射律と推移律を満たすとき、{{math|≤}} を {{mvar|P}} 上の'''{{仮リンク|前順序|en|Preorder|redirect=1}}''' ({{en|preorder}}) または'''擬順序''' ({{en|quasiorder}}) という。
* {{math|≤}} が前順序でありさらに反対称律を満たすとき、{{math|≤}} を {{mvar|P}} 上の'''半順序''' ({{en|partial order}}) という。
* {{math|≤}} が半順序でありさらに全順序律を満たすとき、{{math|≤}} を {{mvar|P}} 上の'''[[全順序]]'''  ({{en|total order}}) という。

{{math|≤}} が前順序であるとき {{math|(''P'', ≤)}} を'''前順序集合'''という。同様に {{math|≤}} が半順序なら {{math|(''P'', ≤)}} は'''半順序集合'''、全順序なら {{math|(''P'', ≤)}} は'''全順序集合'''であるという。また集合 {{mvar|P}} は {{math|(''P'', ≤)}} の'''[[数学的構造#定義|台集合]]''' ({{en|underlying set}}) あるいは'''台''' {{en|(support)}} と呼ばれる。紛らわしくなければ {{math|≤}} を省略し、{{mvar|P}} を（いずれかの意味で）順序集合という。

順序集合 {{math|(''P'', ≤)}} に対し、{{math|≤}} を台 {{mvar|P}} 上の'''順序関係'''ともいう。

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

全順序を'''線型順序'''ともいい、全順序集合を'''鎖'''と呼ぶこともある。また半順序集合の部分集合 {{mvar|A}} で {{mvar|A}} の任意の異なる2元が比較不能であるものを'''{{仮リンク|反鎖|en|Anti-chain}}'''という。{{要出典|半順序集合のことを部分順序集合と呼ぶこともある|date=2016-01}}が部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。

半順序集合の元 {{mvar|a}} が他の元 {{mvar|b}} によって{{仮リンク|被覆関係|en|Covering relation|label='''被覆される'''}} ({{math|''a'' <: ''b''}}) とは、{{mvar|a}} は {{mvar|b}} よりも'''真に小さく'''、かつそれらの間に別の元が入ることはないことをいう。つまり <math>a <: b</math> とは次の3つがすべて成り立つことである：<math>a \le b,\quad a \neq b,\quad \neg[\exists\ c\ \text{s.t.}\ a<c<b].</math>

=== 順序集合の例 ===
* [[実数]]全体の集合 {{mathbf|R}} およびその部分集合（例えば、[[自然数]]全体の集合 {{mathbf|N}}, [[整数]]全体の集合 {{mathbf|Z}}, [[有理数]]全体の集合 {{mathbf|Q}}）は、通常の大小関係により全順序集合となる。しかし、[[複素数]]全体の集合 {{mathbf|C}} には複素数の乗法と"両立"する全順序は存在しない（[[順序体]]でない）。単に全順序を入れるだけであれば、[[直積集合]] {{math|'''R''' × '''R'''}} に[[辞書式順序]]を定めることができる。
* [[自然数]]全体の成す集合は[[整除関係]]を順序として半順序集合である。
* 集合の[[冪集合]]に対して、包含関係による順序を入れると半順序集合となる。これはもとの集合の元の個数が2個以上であれば全順序でない。例えば {{math|{{mset|1, 2, 3}}}} の冪集合
::<math>\bigl\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\bigr\}</math>
:について、例えば {{math|{{mset|1, 2}}}} と {{math|{{mset|2, 3}}}} を考えれば、これらは比較不能であり（{{math|{1, 2} ≤ {2, 3} }}でも {{math2|{2, 3} ≤ {1, 2} }}でもない）、全順序ではない。
* [[ベクトル空間|線形空間]]の部分空間全体は包含関係で順序付けられた半順序集合である。
* 半順序集合 {{mvar|P}} に対し、{{mvar|P}} の元の（自然数で添え字付けられた）列全体の成す集合は、列 {{math|1=''a'' = (''a{{sub|n}}''){{sub|''n''∈'''N'''}}}}, {{math|1=''b'' = (''b{{sub|n}}''){{sub|''n''∈'''N'''}}}} に対し、<div style="margin:1ex auto 1ex 2em"><math>a\le b \iff a_n \le b_n \;(\forall n \in \mathbb{N})</math></div> と定めると半順序集合となる。
* 集合 {{mvar|X}} と半順序集合 {{mvar|P}} に対し、{{mvar|X}} から {{mvar|P}} への写像全体の成す{{仮リンク|写像空間|en|function space}}は、2つの写像 {{math2|''f'', ''g''}} に対して、{{math|''f'' ≤ ''g''}} を {{mvar|X}} の任意の元 {{mvar|x}} に対して {{math|''f''(''x'') ≤ ''g''(''x'')}} となることとして定義すると、半順序集合になる。
* [[有向非巡回グラフ]]の頂点集合は、[[到達不可能性]]によって順序付けられる。
* 半順序集合における順序関係の向きが {{math2|''a'' < ''b'' > ''c'' < ''d'' …}} というように交互に入れ替わる列を{{仮リンク|フェンス (数学)|label=フェンス|en|Fence (mathematics)}}と呼ぶ。

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

=== 逆順序 ===
「大きい、もしくは等しい」ことを意味する順序関係は「{{math|≤}}」の'''逆順序'''と呼ばれ、
: <math>a \ge b \iff b \le a</math>
により定義される。

=== 狭義の順序 ===
一方、等しいことを許容しない順序は'''狭義の（半）順序'''と呼ばれ、以下のように定義される：
: <math>a < b \iff (a \le b \land a \ne b)</math> …(1)
狭義の逆順序「{{math|>}}」も同様に定義される。

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

(1) 式で定義された「{{math|<}}」を「{{math|≤}}」の'''反射的簡約''' {{lang|en|(reflexive reduction)}} という。

「{{math|≤}}」が半順序であるとき、その反射的簡約「{{math|<}}」は任意の {{math2|''a'', ''b'', ''c'' ∈ ''P''}} に対して以下を満たす：
*非反射性：{{math|¬(''a'' < ''a'')}};
*非対称性：{{math|''a'' < ''b''}} ならば {{math|¬(''b'' < ''a'')}}; （非反射性と推移性から従う）
*推移性：{{math|''a'' < ''b''}} かつ {{math|''b'' < ''c''}} ならば {{math|''a'' < ''c''}}

以上では広義の順序を定義してから狭義の順序を定義したが、逆に上の三性質（非対称性は非反射性と推移性より得られるので条件としては不要）を満たすものを狭義の順序として定義し、広義の順序を
: <math>a \le b \iff a < b \lor a = b</math> …(2)
により定義することもできる。この場合、(2) 式で定義された「{{math|≤}}」を「{{math|<}}」の{{仮リンク|反射閉包|en|Binary relation#Operations on binary relations}}という。「{{math|<}}」が前述の3条件を満たせば反射閉包「{{math|≤}}」が半順序であることを簡単に示すことができる。

=== 双対順序集合 ===
{{math|(''P'', ≤)}} を順序集合とするとき、''P'' 上の二項関係「<math>\preccurlyeq</math>」を
: <math>a \preccurlyeq b \iff b \le a</math>
と定義する（すなわち「<math>\preccurlyeq</math>」は「{{math|≤}}」の逆順序を順序と見なしたものである）。すると、「<math>\preccurlyeq</math>」も {{mvar|P}} 上の順序になっていることが容易に分かる。<math>(P,\preccurlyeq)</math> を {{math|(''P'', ≤)}} の'''双対順序集合'''という。

双対順序集合はその定義 <math>(P,\preccurlyeq)</math> よりもとの順序集合 {{math|(''P'', ≤)}} とは"大小が逆転"している。したがって {{math|(''P'', ≤)}} における上限、極大元、最大元（定義は後述）は <math>(P,\preccurlyeq)</math> ではそれぞれ下限、極小元、最小元に対応している。

== ハッセ図 ==
[[画像:Hasse diagram of powerset of 3.svg|150px|thumb|三元集合 {{math|{{mset|''x'', ''y'', ''z''}}}} の[[冪集合|部分集合の全体]]を包含関係を順序とする順序集合と見たときの[[ハッセ図]]]]
{{mvar|P}} を有限集合とし、「{{math|<}}」を {{mvar|P}} 上の狭義の半順序とするとき、以下のようにして {{mvar|P}} を自然に[[グラフ理論|単純有向グラフ]]と見なせる：

: 頂点：{{mvar|P}} の元
: {{math|''a'' ∈ ''P''}} から {{math|''b'' ∈ ''P''}} への辺がある {{math|⇔ ''a'' < ''b''}} であり、しかも {{math|''a'' < ''c'' < ''b''}} を満たす {{math|''c'' ∈ ''P''}} が存在しない
:（すなわち {{mvar|b}} は {{mvar|a}} を被覆している）

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

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

なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に {{math|(''V'', ''E'')}} を閉路を持たない有限な単純有向グラフとすると、{{mvar|V}} 上に以下の順序を入れることで {{mvar|V}} を半順序集合と見なせる：
: {{math|''a'' < ''b'' ⇔ ''a''}} から {{mvar|b}} への道がある
したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。

== {{anchors|上界|下界|上限|下限|最大|最小|極大|極小}}上界、最大、極大、上限、上方集合 ==
{{mvar|P}} を[[#半順序集合|半順序集合]]とし、{{mvar|A}} をその[[部分集合]]とし、{{mvar|x}} を {{mvar|P}} の[[元 (数学)|元]]とする。このとき上界、上限、最大、極大の概念、およびこれらの[[双対]]概念である下界（かかい）、下限、最小、極小は以下のように定義される<ref>{{Cite web|和書|url=http://math.shinshu-u.ac.jp/~hanaki/edu/set/set20210122.pdf |title=集合論 信州大学理学部数学科 講義ノート 2020 年度後期 (2021/01/22) |author=花木 章秀 |date=2021-01-22 |accessdate=2022-03-17}}</ref>：

* {{mvar|x}} が {{mvar|A}} の'''上界''' ({{lang|en|upper bound}}) であるとは、{{mvar|A}} の任意の元 {{mvar|y}} に対して {{math|''y'' ≤ ''x''}} となること。
* {{mvar|x}} が {{mvar|A}} の'''上限''' ({{lang|en|supremum}}) あるいは'''最小上界''' ({{lang|en|least upper bound}}) であるとは、{{mvar|x}} が {{mvar|A}} の上界全体の集合の最小元となること。これは存在すれば一意的に決まり、{{math|sup ''A''}} あるいは {{math|lub ''A''}} と表される。
* {{mvar|x}} が {{mvar|A}} の'''最大元''' ({{lang|en|maximum element}}) であるとは、{{mvar|x}} は {{mvar|A}} の元であり、かつ {{mvar|x}} は {{mvar|A}} の上界であること。これは存在すれば一意的に決まり、{{math|max ''A''}} で表される。
* {{mvar|x}} が {{mvar|A}} の'''極大元''' ({{lang|en|maximal element}}) であるとは、{{mvar|x}} は {{mvar|A}} の元であり、かつ {{math|''y'' > ''x''}} を満たす {{math|''y'' ∈ ''A''}} が存在しないこと。

* {{mvar|x}} が {{mvar|A}} の'''下界''' ({{lang|en|lower bound}}) であるとは、{{mvar|A}} の任意の元 {{mvar|y}} に対して {{math|''y'' ≥ ''x''}} となること。
* {{mvar|x}} が {{mvar|A}} の'''下限''' ({{lang|en|infimum}}) あるいは'''最大下界''' ({{lang|en|greatest lower bound}}) であるとは、{{mvar|x}} が {{mvar|A}} の下界全体の集合の最大元となること。これは存在すれば一意的に決まり、{{math|inf ''A''}} あるいは {{math|glb ''A''}} と表される。
* {{mvar|x}} が {{mvar|A}} の'''最小元''' ({{lang|en|minimum element}}) であるとは、{{mvar|x}} は {{mvar|A}} の元であり、かつ {{mvar|x}} は {{mvar|A}} の下界であること。これは存在すれば一意的に決まり、{{math|min ''A''}} で表される。
* {{mvar|x}} が {{mvar|A}} の'''極小元''' ({{lang|en|minimal element}}) であるとは、{{mvar|x}} は {{mvar|A}} の元であり、かつ {{math|''y'' < ''x''}} を満たす {{math|''y'' ∈ ''A''}} が存在しないこと。

上界および上限の定義において、 {{mvar|x}} が必ずしも {{mvar|A}} の元であるとは限らない、ことには注意が必要である。左閉右開の半開区間 <math>[a, b)</math> には最大元は存在しないが上界および上限は存在する（つまり、 {{mvar|b}}）。

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

さらに {{mvar|A}} が {{mvar|P}} の'''[[上方集合]]'''（resp. '''下方集合'''）であるとは、任意の {{math|''a'' ∈ ''A'' }} と {{math|''x'' > ''a'' }} (resp. {{math|''x'' < ''a''}}) を満たす任意の {{mvar|P}} の元に対し{{math|''x'' ∈ ''A''}} となることをいう。

=== 具体例 ===
{|
|[[画像:Hasse diagram of powerset of 3 no greatest or least.svg|x150px|thumb|三元集合の冪集合のハッセ図から最大元と最小元を取り除いたもの。この図の一番上の行にある各元がこの半順序の極大元であり、一番下の行の各元は極小元である。最大元と最小元はない。集合 {x, y} は元の族 {{x}, {y}} に対する上界を与える。]]
|[[画像:Infinite lattice of divisors.svg|x150px|thumb|整除性によって順序付けられた非負整数のハッセ図]]
|}
[[正整数]]全体の成す集合を整除関係で順序付けるとき、{{math|1}} は任意の正整数を割り切るという意味において {{math|1}} は最小元である。しかしこの半順序集合には最大元は存在しない（任意の正整数の倍数としての {{math|0}} を追加して考えたとするならば、それが最大元になる）。この半順序集合には極大元も存在しない。実際、任意の元 {{mvar|g}} はそれとは異なる。例えば {{math|2''g''}} を割り切るから {{mvar|g}} は極大ではありえない。この半順序集合から最小元である {{math|1}} を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の[[素数]]をとることができる。この半順序に関して {{math|60}} は部分集合 {{math|{{mset|2, 3, 5, 10}}}} の上界（上限ではない）を与えるが、{{math|1}} は除かれているので下界は持たない。他方、[[2の冪|{{math|2}} の冪]]全体の成す部分集合に対して {{math|2}} はその下界（これは下限でもある）を与えるが、上界は存在しない。

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

=== 定義 ===
{{math2|''S'', ''T''}} を順序集合とし、{{math|''f'': ''S'' → ''T''}} を写像とする。このとき
* {{math|''f'': ''S'' → ''T''}} が{{仮リンク|順序を保つ写像|label='''順序を保つ'''|en|order-preserving}}(order-preserving)（'''同調''' (''isotone'') とも）とは、
::任意の {{math2|''x'', ''y'' ∈ ''S''}} に対して {{math|''x'' ≤ ''y'' ⇒ ''f''(''x'') ≤ ''f'' (''y'')}}
* {{math|''f'': ''S'' → ''T''}} が'''順序を逆にする'''（{{仮リンク|order-reversing|en|order-reversing<!-- リダイレクト先の「[[:en:Monotonic function]]」は、[[:ja:単調写像]] とリンク -->}}）とは、
::任意の {{math2|''x'', ''y'' ∈ ''S''}} に対して {{math|''x'' ≤ ''y'' ⇒ ''f'' (''x'') ≥ ''f'' (''y'')}}
* 上の2つを合わせて[[単調写像|単調]] (''monotone'') 写像という。
* {{mvar|f}} が'''順序を反映する''' (''order-reflecting'') とは、
::任意の {{math2|''x'', ''y'' ∈ ''S''}} に対して {{math|''f'' (''x'') ≤ ''f'' (''y'') ⇒ ''x'' ≤ ''y''}}
* {{mvar|f}} が'''{{仮リンク|順序埋め込み|en|order-embedding}}'''であるとは、
::任意の {{math2|''x'', ''y'' ∈ ''S''}} に対して {{math|''x'' ≤ ''y'' ⇔ ''f'' (''x'') ≤ ''f'' (''y'')}}
* {{mvar|f}} が'''{{仮リンク|順序同型|en|order isomorphism|label=順序同型写像}}'''であるとは、{{mvar|f}} が順序埋め込みな全単射であることをいう。

{{math|''f'': ''S'' → ''T''}} が順序埋め込みであるとき、{{mvar|S}} は {{mvar|f}} によって {{mvar|T}} に（順序集合として）'''埋め込まれる'''という。
また順序同型 {{math|''f'': ''S'' → ''T''}} が存在するとき、{{mvar|S}} と {{mvar|T}} は'''順序同型'''あるいは単に'''同型'''であるという。

=== 性質 ===
上で述べた概念は以下の性質を満たす：
* 順序を反映する写像は単射である。実際 {{math|1=''f''(''x'') = ''f''(''y'') ⇒''f''(''x'') ≤ ''f''(''y'')}} かつ {{math|''f''(''x'') ≥ ''f''(''y'') ⇒ ''x'' ≤ ''y''}} かつ {{math|1=''x'' ≥ ''y'' ⇒ ''x'' = ''y''}} である。
* {{mvar|f}} が順序埋め込みである必要十分条件は {{mvar|f}} が順序を保存し、しかも順序を反映することである。また全単射 {{math|''f'': ''S'' → ''T''}} とその逆関数 {{math|''f''{{sup|&minus;1}}: ''T'' → ''S''}} が順序同型なら {{mvar|f}}, {{math|''f''{{sup|&minus;1}}}} は順序同型である。 
* 順序を保つ写像と順序を保つ写像の合成は順序を保つ。順序を反映する写像と順序を反映する写像の合成も順序を反映する。
 
=== 具体例 ===
{|
|[[画像:Monotonic but nonhomomorphic map between lattices.gif|x150px|thumb|順序を保つが順序を反映しない写像<br />{{math2|(''f''(''u'') ≤ ''f''(''v'')}} だが {{math2|''u'' ≤ ''v''}} でない)]]
|[[画像:Birkhoff120.svg|x150px|thumb|{{math2|120}} の[[約数]]全体の成す半順序集合（整除関係で順序を入れる）と {{math2|{{mset|2, 3, 4, 5, 8}}}} の整除関係で閉じた部分集合族（包含関係で順序を入れる）との間の順序同型]]
|}
自然数全体が整除関係に関して成す半順序集合から、その[[冪集合]]が包含関係に関して成す半順序集合への写像 {{math|''f'': '''N''' → ''P''('''N''')}} を各自然数にその[[素因数]]全体の成す集合を対応させることにより定まる。これは順序を保つ集合である（すなわち、{{mvar|x}} が {{mvar|y}} を割るならば {{mvar|x}} の各素因数は {{mvar|y}} の素因数にもなる）が単射ではない（例えば {{math|12}} も {{math|6}} もこの写像で {{math|{{mset|2, 3}}}} に写る）し、順序を反映もしない（例えば {{math|12}} は {{math|6}} を割らない）。少し設定を変えて、各自然数にその[[素冪|素冪因子]]の集合を対応させる写像 {{math|''g'': '''N''' → ''P''('''N''')}} を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない（実際、たとえば[[単集合]] {{math|{{mset|4}}}} に移る数は無い）が[[終域]]を {{mvar|g}} の[[値域]] {{math|''g''('''N''')}} に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎な{{仮リンク|分配束|en|distributive lattice}}と呼ばれる半順序集合のクラスに対して一般化することができる（{{仮リンク|バーコフの表現定理|en|Birkhoff's representation theorem}}の項を参照）。

== 区間 ==
{{mvar|P}} を順序集合とし、{{math2|''a'', ''b''}} を {{mvar|P}} の元とするとき、'''[[閉区間]]''' {{math|[''a'', ''b'']}} と'''[[開区間]]''' {{math|(''a'', ''b'')}} を以下のように定義する：
: <math>[a,b]:=\{x\in P\mid a\le x\le b\}</math> 
: <math>(a,b):=\{x\in P\mid a < x < b\}</math> 
さらに {{math|[''a'', ''b'')}} および {{math|(''a'', ''b'']}} を以下のように定義し、'''[[半開区間]]'''と呼ぶ：
: <math>[a,b):=\{x\in P\mid a\le x< b\}</math> 
: <math>(a,b]:=\{x\in P\mid a < x \le b\}</math> 
文献によっては {{math|(''a'', ''b'')}}, {{math|[''a'', ''b'')}}, {{math|(''a'', ''b'']}} のことを {{math|]''a'', ''b''[}}, {{math|[''a'', ''b''[}}, {{math|]''a'', ''b'']}} と表す場合もある。

半順序集合が{{仮リンク|局所有限半順序集合|label=局所有限|en|Locally finite poset}}であるとは、全ての区間が有限集合であることをいう。例えば、[[整数]]全体の成す集合は通常の大小関係による半順序に関して局所有限である（端点の無い無限区間のようなものは今考えていない）。

順序集合における区間の概念と、{{仮リンク|区間順序|en|interval order}}として知られる特定の半順序の類いとを混同してはならない。

== 順序構造と位相構造 ==
{{内容過剰|section=1|date=2016-01}}
=== 全順序集合の位相 ===
==== 順序位相 ====
全順序集合 ''A'' に対し、無限半開区間
: <math>(-\infty,b)=\{x \in A \mid x< b\}</math>
: <math>(a,\infty)=\{x \in A \mid a< x\}</math>
全体の集合を[[準開基]]とする位相を'''順序位相''' ([[:en:order topology|order topology]]) という{{Efn2|原理的には半順序集合であっても同様の概念を定義できるが、本稿の英語版をはじめ、{{誰範囲|筆者|date=2019-06}}が調べた範囲{{Full citation needed|date=2019-06}}では全順序集合に対してのみ order topology を定義しているため、ここでは全順序のみに話を限定した。}}。例えば、実数全体の集合 <math>\mathbb{R}</math> を通常の大小関係 ≤ による全順序集合と見ると、その順序位相は通常の[[距離空間|距離]]により定められる位相と同等になる。

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

例えば ''A'' を実数全体の集合とし、''A'' の部分集合
: <math>B=\{x\mid 0<x<1\}\cup \{2\}</math>
を考えると、''A'' から''B'' に誘導される位相では一元集合 {{math|{{mset|2}}}} は明らかに開集合であるが、''B'' は順序集合としてみたときはそうではない。実際 ''B'' は（2を1に移す写像により）<math>C=\{x\mid 0<x\le 1\}</math> と順序同型だが、''C'' の順序位相で {{math|{{mset|1}}}} は開集合ではないので ''B'' の順序位相で{{math|{{mset|2}}}} は開集合ではない。

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

実数体 <math>\mathbb{R}</math> 上の'''上極限位相'''とは
: <math>(a,b] = \{x\in\mathbb{R}~:~a<x \le b \}</math>
全体の集合を[[位相空間#位相の比較、生成|開基]]とする位相のことであり、同様に <math>\mathbb{R}</math> 上の'''{{仮リンク|下極限位相|en|lower limit topology}}'''とは逆向きの半開区間
: <math>[a,b) = \{x\in\mathbb{R}~:~a \le x < b \}</math>
全体の集合を[[位相空間#位相の比較、生成|開基]]とする位相のことである{{Efn2|実数体でなくとも上極限位相と下極限位相を考えることができるが、これも実数体以外に対してこれらの位相を定義した文献が見つけられなかったので、ここでは実数体のみを対象にした。}}。

実数体に下極限位相を入れた空間はしばし <math>\mathbb{R}_{\ell}</math> と書かれ、'''ゾルゲンフライ直線'''と呼ばれる。またゾルゲンフライ直線2つの直積 <math>\mathbb{R}_{\ell}\times\mathbb{R}_{\ell}</math> は'''{{仮リンク|ゾルゲンフライ平面|en|Sorgenfrey plane}}'''と呼ばれる。

==== overlapping interval topology ====
区間 [-1,1] 上の '''[[:en:overlapping interval topology|overlapping interval topology]]''' とは
: <math>[-1,a)</math> for <math>0<a</math>
: <math>(b,1]</math> for <math>b<0</math>
を準開基とする位相である。

=== 半順序集合の位相 ===
==== 半順序空間 ====
位相構造を持つ半順序集合''P'' で以下の性質を満たすものを'''{{仮リンク|半順序空間|en|partially ordered space}}'''という：
: {{math|''a'' < ''b''}} を満たす任意の{{math|''a'', ''b'' ∈ ''P''}} に対し、''a'' の開近傍''U''で上方集合であるものと ''b'' の開近傍''V'' で下方集合であるものが存在することである。

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

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

半順序空間では以下が成立する：
:{{math|''a{{sub|i}}'' → ''a'', ''b{{sub|i}}'' → ''b''}} かつ任意の ''i'' に対して {{math|''a{{sub|i}}'' ≤ ''b{{sub|i}}''}} ならば {{math|''a'' ≤ ''b''}} である<ref name="ward-1954">{{Cite journal |first=L. E. Jr |last=Ward |title=Partially Ordered Topological Spaces |journal=Proceedings of the American Mathematical Society|volume=5 |year=1954 |pages=144-161 |issue=1 |doi=10.1090/S0002-9939-1954-0063016-5}}</ref>

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

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

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

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

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

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

ここで位相空間 ''P'' の'''specialization preorder'''とは
: <math>x \le y \iff \overline{\{x\}} \subset \overline{\{y\}}</math>
で定義される前順序のことである。上式で<math>\overline{\{x\}}</math>は一元集合{{math|{{mset|''x''}}}} の[[閉包 (位相空間論)|閉包]]である。（なお、''P'' が[[コルモゴロフ空間|T{{sub|0}}空間]]であればspecialization preorder は半順序であることが知られている。）

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

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

===== 実数体における例 =====
実数体（に通常の順序をいれたもの）を前順序集合と見なすことで実数体にアレクサンドロフ位相を入れることができる。アレクサンドロフ位相における実数体上の開集合（すなわち上方集合）は以下のもののいずれかになる：
* <math>(a,\infty)</math> for some ''a'' 
* <math>[a, \infty)</math> for some ''a''
* 空集合<math>\emptyset</math>、全体集合<math>\mathbb{R}</math>

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

よって実数体にスコット位相を入れた際、実数体上の開集合は以下のもののいずれかになる：
* <math>(a,\infty)</math> for some ''a'' 
* 空集合 <math>\emptyset</math>、全体集合 <math>\mathbb{R}</math>
スコット位相を入れた順序集合を'''スコット空間'''といい、スコット空間からスコット空間への連続写像を'''[[スコット連続]]''' ([[:en:Scott continuity|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'' )}}}が存在し、しかも sup{''f'' (''x'' ), ''f'' (''y'' )} = ''f'' (sup{''x'' , ''y'' }) = ''f'' (''x'' ) となる。これは{{math|''f'' (''x'' ) ≥ ''f'' (''y'' )}} を意味する。

なお、スコット位相と下方位相のいずれよりも強い位相構造の中で最弱のものを'''{{仮リンク|ローソン位相|en|Lawson topology}}'''という。

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

== 直積集合上の順序 ==
2つの半順序集合（の台集合）の[[直積集合]]上の半順序としては次の三種類がある。
* [[辞書式順序]]：<math>(a, b) \le (c, d) \iff a < c \lor (a = c \land b \le d)</math>
* [[積順序]]：<math>(a, b) \le (c, d) \iff a \le c \land b \le d</math> 
* <math>(a, b) \le (c, d) \iff (a < c \land b < d) \lor (a = c \land b = d)</math> 
最後の順序は対応する狭義全順序の[[関係の直積|直積]]の反射閉包である。これらの三種類の半順序は、いずれも3個以上の半順序集合の直積に対しても同様に定義される。

[[可換体|体]]上の[[順序線型空間]]に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれも再び順序線型空間となる。
<gallery>
Strict product order on pairs of natural numbers.svg|{{math|'''N''' × '''N'''}} 上の直積狭義順序の反射閉包
N-Quadrat, gedreht.svg| {{math|'''N''' × '''N'''}} 上の積順序
Lexicographic order on pairs of natural numbers.svg| {{math|'''N''' × '''N'''}} 上の辞書式順序
</gallery>

== 圏としての順序集合 ==
任意の半順序集合（および前順序集合）は、任意の射集合が高々一つの元からなる[[圏 (数学)|圏]]と見なすことができる。具体的には、射の集合を {{math|''x'' ≤ ''y''}} ならば {{math|1=hom(''x'', ''y'') = {{mset|(''x'', ''y'')}}}}（それ以外の場合は空集合）とし、{{math|1=(''y'', ''z'')∘(''x'', ''y'') = (''x'', ''z'')}} と定義する。2つの半順序集合が[[圏同値|圏として同値]]となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは[[始対象]]であり、最大元が存在すればそれは[[終対象]]となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏は{{仮リンク|同型射閉圏|label=同型射について閉じて|en|isomorphism-closed}}いる。

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

== その他 ==<!--
[[画像:poset6.jpg|250px|thumb|Partially ordered set of [[power set|set of all subsets]] of a six-element set {a, b, c, d, e, f}, ordered by the subset relation.]]-->
* （'''半順序関係の総数'''）{{mvar|n}} 個の元からなる集合上の半順序の総数（狭義半順序の総数も同じ）は {{math2|1, 1, 3, 19, 219, 4231, …}} （{{OEIS|A001035}}）。<!-- {{Number of relations}} -->[[違いを除いて|同型を除いた]]総数は {{math2|1, 1, 2, 5, 16, 63, 318, …}} （{{OEIS|A000112}}）。
* （'''線型順序拡大'''）半順序集合 {{mvar|P}} の全順序集合への埋め込みを'''{{仮リンク|線型順序拡大|en|linear extension}}''' (linear extension) という。任意の半順序は全順序に拡張することができる（{{仮リンク|順序拡大原理|en|order-extension principle}}<ref>{{Cite book |last=Jech |first=Thomas |title=The Axiom of Choice |year=2008 |origyear=originally published in 1973 |publisher=[[Dover Publications]] |isbn=0-486-46624-8}}</ref>）。[[計算機科学]]において（[[有向非循環グラフ]]の{{仮リンク|到達可能性|en|reachability}}順序として表現される）半順序の線型拡張を求めるアルゴリズムは[[位相ソート]] {{lang|en|(topological sorting)}} と呼ばれる。

== 関連項目 ==
{{colbegin|3}}
* {{仮リンク|反マトロイド|en|antimatroid}}: 半順序集合よりも一般の順序付けの族を許すような、集合上の順序付けの一般化
* [[因果集合]]
* {{仮リンク|比較可能グラフ|en|comparability graph}}
* [[有向集合]]
* {{仮リンク|次数付き順序集合|en|graded poset}}
* [[半束]]
* [[束 (束論)]]
* [[順序群]]
* {{仮リンク|準順序|en|semiorder}} (semiorder)
* {{仮リンク|直並列半順序|en|series-parallel partial order}}
* {{仮リンク|狭義弱順序|en|strict weak ordering}}: "''a'' < ''b'' または ''b'' < ''a'' の何れかが成り立つ" という関係が推移的となるような狭義半順序 "<"
* [[完備半順序]] (cpo)
* [[ツォルンの補題]]
* [[コンパクト要素]]
{{colend}}

== 脚注 ==
{{脚注ヘルプ}}

=== 注釈 ===
{{Notelist2}}

=== 出典 ===
{{Reflist}}

== 参考文献 ==
{{No footnotes|date=2016-01|section=1}}
* {{Cite book|和書 |author=松坂和夫|authorlink=松坂和夫 |date=1968-06-10 |title=集合・位相入門 |publisher=[[岩波書店]] |isbn=4-00-005424-4 |ref=harv}}
* {{Cite book|和書 |author=斎藤正彦|authorlink=斎藤正彦 |date=2002-08-01 |title=数学の基礎　集合・数・位相 |series=基礎数学14 |publisher=[[東京大学出版会]] |isbn=978-4-13-062909-6 |ref=harv}}
* {{Cite journal |first=Jayant V. |last=Deshpande |title=On Continuity of a Partial Order |journal=Proceedings of the American Mathematical Society |volume=19 |year=1968 |pages=383-386 |issue=2 |doi=10.1090/S0002-9939-1968-0236071-7 |postscript=.}}
* {{Cite book |first=Bernd S. W. |last=Schröder |title=Ordered Sets:  An Introduction |publisher=Birkhäuser, Boston|year=2003}}
* {{Cite book |first=Richard P.|last=Stanley |authorlink=Richard P. Stanley |title=Enumerative Combinatorics 1 |series=Cambridge Studies in Advanced Mathematics |volume=49 |publisher=Cambridge University Press |isbn=0-521-66351-2}}

== 外部リンク ==
{{Commons|Hasse diagram|Hasse diagram}}
* {{OEIS|A001035}}: Number of posets with ''n'' labeled elements in the [[On-Line Encyclopedia of Integer Sequences|OEIS]]
* {{OEIS|A000112}}: Number of posets with ''n'' unlabeled elements in the OEIS

{{DEFAULTSORT:しゆんしよしゆうこう}}
[[Category:順序構造|*]]
[[Category:数学に関する記事]]