「順序集合」の版間の差分
削除された内容 追加された内容
編集の要約なし |
|||
1行目:
{{保護依頼}}
<q>※「半順序」という訳語が古くから使われているが、近年の数学の発達により、「半(half)」と「部分(partial)」は明確に区別する必要性が出てきた。
比較不能のケースを許容している強調して順序集合の事を'''半順序集合'''（はんじゅんじょしゅうごう、{{lang-en-short|''partially ordered set'', '''poset'''}}）ともいう。一方、半順序集合の中で比較不能のケースがないものを特に'''全順序集合''' ({{en|totally ordered set}}) という。（「半順序」という言葉が「全順序」の対義語ではない事に注意。全順序集合も半順序集合の一種である。）▼
国際的標準に従い、ここでは「半順序」ではなく、「部分順序」を訳語として採用する。
</q>
[[数学]]において'''順序集合'''（じゅんじょしゅうごう、{{lang-en-short|''ordered set''}}）とは
全順序集合の簡単な例は[[整数]]の集合や[[実数]]の集合で、通常の大小比較を順序とみなしたものがある。▼
「順序」の概念が定義された集合の事で、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。
一方、全順序ではない半順序集合の例としては、[[正の整数]]全体の集合に整除関係で順序を入れたものや、（2つ以上元を含む）集合の[[冪集合]]において、包含関係を順序とみなしたものがある。例えば2元集合 {{math|1=''S'' = {{(}}''a'', ''b''{{)}}}} において {{math|{{(}}''a''{{)}}}} と {{math|{{(}}''b''{{)}}}} はいずれも他方を包含していないので ''S'' の冪集合は全順序ではない。▼
ただし順序集合内の２つの元''a''、''b'' に順序関係が定まっている必要はなく、両者が「比較不能」であってもよい。よって''a''、''b'' の関係は「''a'' は''b'' 以上である」、「''b'' は''a'' 以上である」、「''a'' と''b'' は比較不能である」の３通りのいずれかとなる。
実生活に近い例では、「AさんはBさんの子孫である」という事を「A＜B」という大小関係とみなす事で人間全体の集合を半順序集合とみなせる。AさんとBさんはどちらも他方の子孫でない事もありうる（兄弟同士、叔父と甥、赤の他人等）ので、この順序集合は全順序ではない。▼
▲比較不能のケースを許容している強調して順序集合の事を'''
▲一方、全順序ではない
▲実生活に近い例では、「AさんはBさんの子孫である」という事を「A＜B」という大小関係とみなす事で人間全体の集合を
== 定義 ==
全順序集合、
「
=== {{anchors|前順序|部分順序|半順序|全順序|前順序集合|
{{mvar|P}} を集合とし、{{math|≤}} を {{mvar|P}} 上で定義された[[二項関係]] とする。
* {{math|≤}} が反射律と推移律を満たすとき
* 前順序な {{math|≤}} が
* 部分順序な {{math|≤}} が
{{math|≤}} が前順序である
順序集合 {{math|(''P'', ≤)}} に対し、{{math|≤}} を台 {{mvar|P}} 上の'''順序関係'''ともいう。
なお多くの数学の分野では 上では順序を記号 {{math|≤}} で表したが、必ずしもこの記号で表現する必要はない。
実数の大小を表す記号 {{math|≤}} と区別する為、順序の記号として <math>\prec</math> や <math>\ll</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> と定めると部分順序集合となる。
▲* ある[[ベクトル空間]]の部分空間全体は包含関係で順序付けられた半順序集合である。
*
* [[非循環有向グラフ]]の頂点集合は、[[到達不可能性]]によって順序付けられる。
*
== 逆順序、狭義の順序、双対順序 ==
上で述べた順序関係「
=== 逆順序 ===
「大きい、もしくは等しい」事を意味する順序関係は「
: <math>a \ge b \iff b \le a</math>
62 ⟶ 72行目:
=== 狭義の順序 ===
一方、等しい事を許容しない順序は'''狭義の(
: <math>a < b \iff (a \le b \and a \ne b)</math>
狭義の逆順序「
狭義の順序「
(1)
「
以上では広義の順序からスタートして狭義の順序を定義したが、逆に上の三性質を満たすものを狭義の順序として定義し、広義の順序を
: <math>a \le b \iff a < b \or a = b</math>
により定義する事もできる。
この場合、(2) 「 <!--
全順序集合は比較不能であるということが起きないような
-->
=== 双対順序集合 ===
{{math|(''P'' , ≤)}}を順序集合とするとき、''P'' 上の二項関係「<math>
: <math> a \preccurlyeq b \iff b \le a</math>
と定義する（すなわち「<math>
双対順序集合はその定義
==ハッセ図==
[[Image:Hasse diagram of powerset of 3.svg|right|thumb|150px|三元集合 {
: 頂点：
:
この有向グラフを図示したものを'''[[ハッセ図]]'''という。
右に示した図がハッセ図の例である。この図では三元集合 {''x'', ''y'', ''z''}の [[冪集合|部分集合の全体]]を包含関係を順序とする順序集合とみなしたものをハッセ図として表している。
ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。
例えばこの図で {
また[[一元集合]]の族 {{math|{ さらに なお、有限
逆に : {{math|''a'' < ''b''}} ⇔
したがって有限
== {{anchors|上界|下界|上限|下限|最大|最小|極大|極小}}上界、最大、極大、上限、上方集合==
{{mvar|P}} を[[#
このとき上界、最大、極大、上限の概念、およびこれらの[[双対|双対概念]]である下界、最小、極小、下限は以下のように定義される： === 定義 ===
122 ⟶ 140行目:
* {{mvar|x}} が {{mvar|A}} の'''最大元'''（resp. '''最小元'''）: {{mvar|x}} は {{mvar|A}} の元でしかも {{mvar|x}} は {{mvar|A}} の上界（resp. 下界）である
* {{mvar|x}} が {{mvar|A}} の'''極大元'''（resp. '''極小元'''）: {{mvar|x}} は {{mvar|A}} の元でしかも <math>y \gneqq x</math> (resp. <math>y \lneqq x</math>) を満たす {{math|''y'' ∈ ''A''}} が存在しない
* {{mvar|x}} が {{mvar|A}} の'''上限'''（resp. '''下限'''）: {{mvar|x}} は集合
上界および上限の定義において {{mvar|x}} が {{mvar|A}} に必ずしも属さないことには注意が必要である。
極大元の概念と最大元の概念は以下の点で異なる。
まず {{mvar|x}} が {{mvar|A}} の極大元であるとは、{{mvar|A}} の元は「{{mvar|x}} 以下である」か、もしくは「{{mvar|x}} とは大小が比較不能である」かのいずれかである事を意味する。一方 {{mvar|x}} が {{mvar|A}} の最大元であるとは {{mvar|A}} の元は常に {{mvar|x}} 以下である事を意味する（このとき {{mvar|A}} の元は {{mvar|x}} と比較可能である）。したがって最大元は極大元であるが、極大元は必ずしも最大元であるとは限らない。 さらに {{mvar|A}} が {{mvar|P}} の'''{{仮リンク|上方集合|en|upper set}}'''（resp. '''下方集合'''）であるとは、任意の {{math|''a'' ∈ ''A'' }} と {{math|''x'' > ''a'' }} (resp. {{math|''x'' < ''a''}}) を満たす任意の {{mvar|P}} の元に対し{{math|''x'' ∈ ''A'' }} となることをいう。
132 ⟶ 151行目:
===具体例===
{|
|[[File:Hasse diagram of powerset of 3 no greatest or least.svg|thumb|right|x150px|三元集合の冪集合のハッセ図から最大元と最小元を取り除いたもの。この図の一番上の行にある各元がこの
|[[File:Infinite lattice of divisors.svg|thumb|right|x150px|整除性によって順序付けられた非負整数のハッセ図]]
|}
[[正整数]]全体の成す集合を整除関係で順序付ける時、{{math|1}} は任意の正整数を割り切るという意味において {{math|1}} は最小元である。しかしこの
== 写像と順序 ==
142 ⟶ 161行目:
=== 定義 ===
*
*
* 上の2つを合わせて[[単調写像|単調]]
*
*
*
また
=== 性質 ===
上で述べた概念は以下の性質を満たす：
* 順序を反映する写像は単射である。実際
*
* 順序を保つ写像と順序を保つ写像の合成は順序を保つ。 順序を反映する写像と順序を反映する写像の合成も順序を反映する。
164 ⟶ 183行目:
{|
|[[File:Monotonic but nonhomomorphic map between lattices.gif|thumb|right|x150px|順序を保つが順序を反映しない写像 (''f''(''u'')≤''f''(''v'') だが ''u''≤''v'' でない)]]
|[[File:Birkhoff120.svg|thumb|right|x150px| 120 の約数全体の成す
|}
自然数全体が整除関係に関して成す
== 区間 ==
: <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):=\{x\in P\mid a\le x< b\}</math>
: <math>(a,b]:=\{x\in P\mid a < x \le b\}</math>
文献によっては
]''a'', ''b''[ 順序集合における区間の概念と、{{仮リンク|区間順序|en|interval order}}として知られる特定の
== 順序構造と位相構造 ==
===全順序集合の位相===
====順序位相====
228 ⟶ 247行目:
を準開基とする位相である。
===
====
位相構造を持つ
: {{math|''a'' < ''b'' }}を満たす任意の{{math|''a'', ''b'' ∈ ''P'' }}に対し、''a'' の開近傍''U''で上方集合であるものと''b'' の開近傍''V'' で下方集合であるものが存在する事である。
（''P'' の位相構造でこの性質を満たすものは１つとは限らないが、それらを全て
なお、
定義より明らかに
:{{math|''a''<sub>''i''</sub> → ''a'', ''b''<sub>''i''</sub> → ''b''}} かつ任意の ''i'' に対して {{math|''a''<sub>''i''</sub> ≤ ''b''<sub>''i''</sub>}} ならば {{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>
位相構造を持つ
:
２つ
====上方位相、下方位相====
273 ⟶ 292行目:
: <math>x \le y \iff \overline{\{x\}} \subset \overline{\{y\}}</math>
で定義される前順序の事である。上式で<math>\overline{\{x\}}</math>は一元集合{{math| {''x'' } }}の[[閉包 (位相空間論)|閉包]]である。（なお、''P''が[[コルモゴロフ空間|T<sub>0</sub>空間]]であればspecialization preorderは
以上の対応関係により、集合''P'' におけるアレクサンドロフ空間としての構造と''P'' 上の前順序は１対１対応する。
313 ⟶ 332行目:
== 直積集合上の順序 ==
ふたつの
* [[辞書式順序]]: <math>(a, b) \le (c, d) \iff a < c \or (a = c \and b \le d)</math>
* [[積順序]]: <math>(a, b) \le (c, d) \iff a \le c \and b \le d</math>
* <math>(a, b) \le (c, d) \iff (a < c \and b < d) \or (a = c \and b = d)</math>
最後の順序は対応する狭義全順序の[[関係の直積|直積]]の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの
[[可換体|体]]上の[[順序線型空間]]に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれもふたたび順序線型空間となる。
<gallery>
File:Strict product order on pairs of natural numbers.svg|
File:N-Quadrat, gedreht.svg|
File:Lexicographic order on pairs of natural numbers.svg|
</gallery>
== 圏としての順序集合 ==
任意の
== その他 ==
* ('''部分順序関係の総数''')<!-- [[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}}.
*
▲* （'''線型順序拡大'''）半順序集合 {{math|''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}}
348 ⟶ 367行目:
* [[順序群]]
* {{仮リンク|準順序|en|semiorder}} (semiorder)
* {{仮リンク|直並列
* {{仮リンク|狭義弱順序|en|strict weak ordering}}: "''a'' < ''b'' または ''b'' < ''a'' の何れかが成り立つ" という関係が推移的となるような狭義
* [[完備
* [[ツォルンの補題]]
{{colend}}
358 ⟶ 377行目:
== 参考文献 ==
* {{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}}
| |||