2016年1月19日 (火) 03:24時点における版編集 221.187.153.196 (会話) →‎その他 ← 古い編集		2016年1月19日 (火) 03:31時点における版編集取り消し 221.187.153.196 (会話) 編集の要約なし新しい編集 →
1行目: <q>※半順序という単語が古くから使われているが、近年の数学の発達により、「半(half)」と「部分(partial)」は明確に区別する必要性がある。国際的標準に従い、ここでは「半順序」ではなく、「部分順序」を採用する。 </q> [[数学]]において'''順序集合'''（じゅんじょしゅうごう、{{lang-en-short\|''ordered set''}}）とは「順序」の概念が定義された集合の事で、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。ただし順序集合内の２つの元''a''、''b'' に順序関係が定まっている必要はなく、両者が「比較不能」であってもよい。よって''a''、''b'' の関係は「''a'' は''b'' 以上である」、「''b'' は''a'' 以上である」、「''a'' と''b'' は比較不能である」の３通りのいずれかとなる。比較不能のケースを許容している強調して順序集合の事を'''半部分順序集合'''（はんじゅんじょしゅうごう、{{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さんはどちらも他方の子孫でない事もありうる（兄弟同士、叔父と甥、赤の他人等）ので、この順序集合は全順序ではない。 == 定義 == 195 ⟶ 200行目: ]''a'', ''b''[、[''a'',''b''[、 ]''a'',''b''] と表す場合もある。半部分順序集合が{{仮リンク\|局所有限半部分順序集合\|label=局所有限\|en\|Locally finite poset}}であるとは、すべての区間が有限集合であることを言う。たとえば、[[整数]]全体の成す集合は通常の大小関係による半部分順序に関して局所有限である（端点の無い無限区間のようなものは今考えていない）。順序集合における区間の概念と、{{仮リンク\|区間順序\|en\|interval order}}として知られる特定の半部分順序の類いとを混同してはならない。 == 順序構造と位相構造 == 330 ⟶ 335行目: * <math>(a, b) \le (c, d) \iff (a < c \and b < d) \or (a = c \and b = d)</math> 最後の順序は対応する狭義全順序の[[関係の直積\|直積]]の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの半部分順序集合の直積に対しても同様に定義される。 [[可換体\|体]]上の[[順序線型空間]]に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれもふたたび順序線型空間となる。 346 ⟶ 351行目: == その他 == * ('''部分順序関係の総数''')<!-- [[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)}} と呼ばれる。　 == 関連項目 == {{colbegin\|3}} * {{仮リンク\|反マトロイド\|en\|antimatroid}}: 半部分順序集合よりも一般の順序付けの族を許すような、集合上の順序付けの一般化 * [[因果集合]] * {{仮リンク\|比較可能グラフ\|en\|comparability graph}} 360 ⟶ 365行目: * [[順序群]] * {{仮リンク\|準順序\|en\|semiorder}} (semiorder) * {{仮リンク\|直並列半部分順序\|en\|series-parallel partial order}} * {{仮リンク\|狭義弱順序\|en\|strict weak ordering}}: "''a'' < ''b'' または ''b'' < ''a'' の何れかが成り立つ" という関係が推移的となるような狭義半順序 "<" * [[完備半部分順序]] (cpo) * [[ツォルンの補題]] {{colend}}

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