「順序集合」の版間の差分
削除された内容 追加された内容
221.190.232.151 (会話) による ID:58307842 の版を取り消し OR |
|||
1行目:
<q>※「半順序」という訳語が古くから使われているが、近年の数学の発達により、「半(half)」と「部分(partial)」は明確に区別する必要性が出てきた。
[[数学]]において'''順序集合'''(じゅんじょしゅうごう、{{lang-en-short|''ordered set''}})とは「順序」の概念が定義された集合の事で、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。▼
国際的標準に従い、ここでは「半順序」ではなく、「部分順序」を訳語として採用する。
</q>
[[数学]]において'''順序集合'''(じゅんじょしゅうごう、{{lang-en-short|''ordered set''}})とは
▲
ただし順序集合内の2つの元''a''、''b'' に順序関係が定まっている必要はなく、両者が「比較不能」であってもよい。よって''a''、''b'' の関係は「''a'' は''b'' 以上である」、「''b'' は''a'' 以上である」、「''a'' と''b'' は比較不能である」の3通りのいずれかとなる。
比較不能のケースを許容している強調して順序集合の事を'''
全順序集合の簡単な例は整数の集合や実数の集合で、通常の大小比較を順序とみなしたものがある。
一方、全順序ではない
実生活に近い例では、「AさんはBさんの子孫である」という事を「A<B」という大小関係とみなす事で人間全体の集合を
== 定義 ==
全順序集合、
; [[反射関係|反射律]] : <math>\forall a \in P : a \le a</math>
21 ⟶ 27行目:
「≤」が全順序律を満たさない場合、「''a'' ≤ ''b''」でも「''b'' ≤ ''a''」でもないケースがある。このような第三のケースにあるとき''a'' と''b''は'''比較不能'''であるという。
=== {{anchors|前順序|部分順序|半順序|全順序|前順序集合|
{{mvar|P}} を集合とし、{{math|≤}} を {{mvar|P}} 上で定義された[[二項関係]] とする。
* {{math|≤}} が反射律と推移律を満たすとき {{math|≤}} を {{mvar|P}} 上の'''前順序'''という。
* 前順序な {{math|≤}} が反対称律をも満たすとき {{math|≤}} を {{mvar|P}} 上の'''
*
{{math|≤}} が前順序である {{math|(''P'', ≤)}} を'''前順序集合'''という。同様に {{math|≤}} が
順序集合 {{math|(''P'', ≤)}} に対し、{{math|≤}} を台 {{mvar|P}} 上の'''順序関係'''ともいう。
なお多くの数学の分野では
上では順序を記号 {{math|≤}} で表したが、必ずしもこの記号で表現する必要はない。
実数の大小を表す記号 {{math|≤}} と区別する為、順序の記号として <math>\prec</math> や <math>\ll</math> を使うこともある。
全順序の事を'''線型順序'''ともいい、'''全順序集合'''のことを'''鎖'''と呼ぶこともある。また
=== 順序集合の例 ===
* [[自然数]]全体の集合 '''N'''、[[整数]]全体の集合 '''Z'''、[[有理数]]全体の集合 '''Q'''、[[実数]]全体の集合 '''R''' は通常の代数的な大小関係によって全順序集合になるが、[[複素数]]はそうではない。複素数全体の集合 '''C''' に '''R''' × '''R''' としての[[辞書式順序]]を定めたものは全順序集合であるが、この順序は複素数の乗法とは両立しない。
* [[自然数]]全体の成す集合は整除関係を順序として
* ある集合の[[冪集合]]は部分集合の包含関係を順序として
\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}</math></div> について、たとえば {1, 2} と {2, 3} を考えれば、これらは比較不能である({1, 2} ≤ {2, 3} でも {2, 3} ≤ {1, 2} でもない)。
* [[ベクトル空間]]の部分空間全体は包含関係で順序付けられた
*
* 集合 ''X'' と
* [[非循環有向グラフ]]の頂点集合は、[[到達不可能性]]によって順序付けられる。
*
== 逆順序、狭義の順序、双対順序 ==
64 ⟶ 70行目:
=== 狭義の順序 ===
一方、等しい事を許容しない順序は'''狭義の(
: <math>a < b \iff (a \le b \and a \ne b)</math> ...(1)
70 ⟶ 76行目:
狭義の逆順序「>」も自然に定義される。
狭義の順序「<」の対義語として、等しい事も許容する順序「≤」の事を'''広義の(
(1)式で定義された「<」を「≤」の'''反射的簡約''' {{lang|en|(reflexive reduction)}} という。
「≤」が
; 非反射性 : ¬(''a'' < ''a'');
86 ⟶ 92行目:
により定義する事もできる。
この場合、(2)式で定義された「≤」を「<」の{{仮リンク|反射閉包|en|Binary relation#Operations on binary relations}}という。
「<」が前述の3条件を満たせば反射閉包「≤」が
<!--
全順序集合は比較不能であるということが起きないような
-->
103 ⟶ 109行目:
[[Image:Hasse diagram of powerset of 3.svg|right|thumb|150px|三元集合 {''x'', ''y'', ''z''} の[[冪集合|部分集合の全体]]を包含関係を順序とする順序集合とみたときの[[ハッセ図]]]]
''P'' を有限集合とし、「<」を''P'' 上の狭義の
: 頂点:''P''の元
117 ⟶ 123行目:
さらに{''x''} は {''x'',''z''} によって被覆されるが、{''x'',''y'',''z''} には被覆されない。
なお、有限
逆に{{math|(''V'' , ''E'' )}}を閉路を持たない有限な単純有向グラフとすると、''V'' 上に以下の順序を入れる事で''V'' を
: {{math|''a'' < ''b''}} ⇔ ''a'' から''b'' への道がある
したがって有限
== {{anchors|上界|下界|上限|下限|最大|最小|極大|極小}}上界、最大、極大、上限、上方集合==
{{mvar|P}} を[[#
このとき上界、最大、極大、上限の概念、およびこれらの[[双対|双対概念]]である下界、最小、極小、下限は以下のように定義される:
143 ⟶ 149行目:
===具体例===
{|
|[[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}} は最小元である。しかしこの
== 写像と順序 ==
175 ⟶ 181行目:
{|
|[[File:Monotonic but nonhomomorphic map between lattices.gif|thumb|right|x150px|順序を保つが順序を反映しない写像 (''f''(''u'')≤''f''(''v'') だが ''u''≤''v'' でない)]]
|[[File:Birkhoff120.svg|thumb|right|x150px| 120 の約数全体の成す
|}
自然数全体が整除関係に関して成す
== 区間 ==
194 ⟶ 200行目:
]''a'', ''b''[、[''a'',''b''[、 ]''a'',''b''] と表す場合もある。
順序集合における区間の概念と、{{仮リンク|区間順序|en|interval order}}として知られる特定の
== 順序構造と位相構造 ==
239 ⟶ 245行目:
を準開基とする位相である。
===
====
位相構造を持つ
: {{math|''a'' < ''b'' }}を満たす任意の{{math|''a'', ''b'' ∈ ''P'' }}に対し、''a'' の開近傍''U''で上方集合であるものと''b'' の開近傍''V'' で下方集合であるものが存在する事である。
(''P'' の位相構造でこの性質を満たすものは1つとは限らないが、それらを全て
なお、
定義より明らかに
:{{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>
位相構造を持つ
:
2つ
====上方位相、下方位相====
284 ⟶ 290行目:
: <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'' 上の前順序は1対1対応する。
324 ⟶ 330行目:
== 直積集合上の順序 ==
ふたつの
* [[辞書式順序]]: <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>
最後の順序は対応する狭義全順序の[[関係の直積|直積]]の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの
[[可換体|体]]上の[[順序線型空間]]に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれもふたたび順序線型空間となる。
339 ⟶ 345行目:
== 圏としての順序集合 ==
任意の
== その他 ==
* ('''
* ('''線型順序拡大''')
== 関連項目 ==
{{colbegin|3}}
* {{仮リンク|反マトロイド|en|antimatroid}}:
* [[因果集合]]
* {{仮リンク|比較可能グラフ|en|comparability graph}}
358 ⟶ 365行目:
* [[順序群]]
* {{仮リンク|準順序|en|semiorder}} (semiorder)
* {{仮リンク|直並列
* {{仮リンク|狭義弱順序|en|strict weak ordering}}: "''a'' < ''b'' または ''b'' < ''a'' の何れかが成り立つ" という関係が推移的となるような狭義
* [[完備
* [[ツォルンの補題]]
{{colend}}
368 ⟶ 375行目:
== 参考文献 ==
* {{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}}
|