「順序集合」の版間の差分

比較不能のケースを許容している強調して順序集合の事を'''部分半順序集合'''（ぶぶはんじゅんじょしゅうごう、{{lang-en-short|''partially ordered set'', '''poset'''}}）ともいう。一方、部分半順序集合の中で比較不能のケースがないものを特に'''全順序集合'''(totally ordered set)という。（「部分半順序」という言葉が「全順序」の対義語ではない事に注意。全順序集合も部分半順序集合の一種である）。

一方、全順序ではない部分半順序集合の例としては(2つ以上元を含む)集合の冪集合で、包含関係を順序とみなしたものがある。例えば3元集合''P'' ={a,b,c}において{a,b}と{b,c}はいずれも他方を包含していないので''P'' の冪集合は全順序ではない。

実生活に近い例では、「AさんはBさんの子孫である」という事を「A＜B」という大小関係とみなす事で人間全体の集合を部分半順序集合とみなせる。AさんとBさんはどちらも他方の子孫でない事もありうる（兄弟同士、叔父と甥、赤の他人等）ので、この順序集合は全順序ではない。

全順序集合、部分半順序集合、およびこれらよりさらに弱い概念である前順序集合の定義を述べる為にまず以下の性質を考える。ここで''P'' は集合であり、「≤」を''P'' 上で定義された[[二項関係]] である。

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

* 前順序な {{math|≤}} が反対称律をも満たすとき {{math|≤}} を {{mvar|P}} 上の'''部分半順序'''という。

* 部分半順序な {{math|≤}} が全順序律をも満たすとき {{math|≤}} を {{mvar|P}} 上の'''全順序'''という。

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

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

全順序の事を'''線型順序'''ともいい、'''全順序集合'''のことを'''鎖'''と呼ぶこともある。また部分半順序集合の部分集合 {{mvar|A}} で {{mvar|A}} の任意の相異なる二元が比較不能であるものを'''{{仮リンク|反鎖|en|Anti-chain}}'''という。

部分半順序集合の元 {{mvar|a}} が他の元 {{mvar|b}} によって{{仮リンク|被覆関係|en|Covering relation|label='''被覆される'''}} {{math|''a'' <: ''b''}} とは、{{mvar|a}} は {{mvar|b}} よりも'''真に小さく'''、かつそれらの間に別の元が入ることはないこと（後述する狭義の記号を使って書けば {{math|''a'' < ''b''}} かつ任意の {{mvar|c}} に対して {{math|''a'' < ''c'' < ''b''}} が偽となること）をいう。

* [[自然数]]全体の成す集合は整除関係を順序として部分半順序集合である。

* ある集合の[[冪集合]]は部分集合の包含関係を順序として部分半順序集合となる。これは一般には全順序ではない。例えば {1, 2, 3} の冪集合<div style="margin:1ex auto 1ex 2em"><math>

* [[ベクトル空間]]の部分空間全体は包含関係で順序付けられた部分半順序集合である。

* 部分半順序集合 ''P'' に対し、''P'' の元の列全体の成す集合は、列 ''a'', ''b'' に対し、<div style="margin: 1ex auto 1ex 2em"><math>a=(a_n)_{n\in\mathbb{N}} \le b=(b_n)_{n\in\mathbb{N}} \iff a_n \le b_n (\forall n \in \mathbb{N})</math></div> と定めると部分半順序集合となる。

* 集合 ''X'' と部分半順序集合 ''P'' に対し、''X'' から ''P'' への写像全体の成す[[写像空間]]は、ふたつの写像 ''f'', ''g'' に対して、''f'' &le; ''g'' を ''X'' の任意の元 ''x'' に対して ''f''(''x'') &le; ''g''(''x'') となることとして定義すると、部分半順序集合になる。

* 部分半順序集合における順序関係の向きが ''a'' &lt; ''b'' &gt; ''c'' &lt; ''d'' ... というように交互に入れ替わる列を[[フェンス (数学)|フェンス]]と呼ぶ。

一方、等しい事を許容しない順序は'''狭義の(部分半)順序'''と呼ばれ、以下のように定義される：

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

「&le;」が部分半順序であるとき、その反射的簡約「&lt;」は任意の''a'', ''b'', ''c'' &isin; ''P'' に対して以下を満たす：

「&lt;」が前述の３条件を満たせば反射閉包「&le;」が部分半順序である事を簡単に示す事ができる。

全順序集合は比較不能であるということが起きないような部分半順序集合を言い、従って任意の二元は比較可能であり、このとき{{仮リンク|三分法 (数学)|label=三分律|en|Trichotomy (mathematics)}}が成り立つという。

''P'' を有限集合とし、「&lt;」を''P'' 上の狭義の部分半順序とするとき、以下のようにして''P'' を自然に[[グラフ理論|単純有向グラフ]]とみなせる：

なお、有限部分半順序集合から前述の方法で作ったグラフは閉路を持たない。

逆に{{math|(''V'' , ''E'' )}}を閉路を持たない有限な単純有向グラフとすると、''V'' 上に以下の順序を入れる事で''V'' を部分半順序集合とみなせる：

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

{{mvar|P}} を[[#部分半順序集合|部分半順序集合]]とし、{{mvar|A}} をその[[部分集合]]とし、{{mvar|x}} を {{mvar|P}} の[[元 (数学)|元]]とする。

|[[File:Hasse diagram of powerset of 3 no greatest or least.svg|thumb|right|x150px|三元集合の冪集合のハッセ図から最大元と最小元を取り除いたもの。この図の一番上の行にある各元がこの部分半順序の極大元であり、一番下の行の各元は極小元である。最大元と最小元はない。集合 {x, y} は元の族 {{x}, {y}} に対する上界を与える。]]

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

|[[File:Birkhoff120.svg|thumb|right|x150px| 120 の約数全体の成す部分半順序集合（整除関係で順序を入れる）と {2,3,4,5,8} の整除関係で閉じた部分集合族（包含関係で順序を入れる）との間の順序同型]]

自然数全体が整除関係に関して成す部分半順序集合から、その[[冪集合]]が包含関係に関して成す部分半順序集合への写像 ''f'': ℕ → ℙ(ℕ) を各自然数にその[[素因数]]全体の成す集合を対応させることにより定まる。これは順序を保つ集合である（すなわち、''x'' が ''y'' を割るならば ''x'' の各素因数は ''y'' の素因数にもなる）が単射ではない（例えば 12 も 6 もこの写像で {2,3} に写る）し、順序を反映もしない（例えば 12 は 6 を割らない）。少し設定を変えて、各自然数にその{{仮リンク|素冪|en|prime power|label=素冪因子}}の集合を対応させる写像 ''g'': ℕ → ℙ(ℕ) を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない（実際、たとえば単元集合 {4} に写る数は無い）が[[終域]]を ''g'' の[[値域]] ''g''(ℕ) に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎な{{仮リンク|分配束|en|distributive lattice}}と呼ばれる部分半順序集合のクラスに対して一般化することができる（{{仮リンク|バーコフの表現定理|en|Birkhoff's representation theorem}}の項を参照）。

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

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

===部分半順序集合の位相===

====部分半順序空間====

位相構造を持つ部分半順序集合''P'' で以下の性質を満たすものを'''{{仮リンク|部分半順序空間|en|partially ordered space}}'''という：

（''P'' の位相構造でこの性質を満たすものは１つとは限らないが、それらを全て部分半順序空間という。）

なお、部分半順序空間と名前の似た{{仮リンク|poset topology|en|poset topology}}は別概念であるので注意が必要である。

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

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

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

: 部分半順序集合''P'' 上の位相構造として、{(''a'', ''b'') &isin; ''P'' &times; ''P'' | ''a'' &le; ''b'' } が[[直積位相]]に関する[[閉集合|閉部分集合]]になる。

２つ部分半順序空間の間の順序を保つ連続写像の事を'''dimap'''という。

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

ふたつの部分半順序集合（の台集合）の[[直積集合]]上の部分半順序としては次の三種類が考えられる。

最後の順序は対応する狭義全順序の[[関係の直積|直積]]の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの部分半順序集合の直積に対しても同様に定義される。

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

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

* ('''部分半順序関係の総数''')<!-- [[Image:poset6.jpg|right|thumb|250px| 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.]]-->''n'' 個の元からなる集合上の部分半順序の総数（狭義部分半順序の総数も同じ）は {{OEIS|A001035}} <!-- {{Number of relations}} -->[[違いを除いて|同型を除いた]]総数は 1, 1, 2, 5, 16, 63, 318, … {{OEIS|A000112}}.

* ('''線型順序拡大''')部分半順序集合''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)}} と呼ばれる。

* {{仮リンク|反マトロイド|en|antimatroid}}: 部分半順序集合よりも一般の順序付けの族を許すような、集合上の順序付けの一般化

* {{仮リンク|直並列部分半順序|en|series-parallel partial order}}

* {{仮リンク|狭義弱順序|en|strict weak ordering}}: "''a'' < ''b'' または ''b'' < ''a'' の何れかが成り立つ" という関係が推移的となるような狭義部分半順序 "<"

* [[完備部分半順序]] (cpo)