「順序」はこの項目へ転送されています。その他の用法については「wikt:順序
」をご覧ください。この記事には複数の問題があります。改善やノートページでの議論にご協力ください。
出典は脚注などを用いて記述と関連付けてください。(2019年6月)
独自研究が含まれているおそれがあります。(2019年6月)
順序集合(じゅんじょしゅうごう、英: ordered set)は集合の要素の間に順序が定義された集合。順序とは二項関係であって後述する反射律・推移律などを満たすものであり、数の大小関係などを一般化したものである。
全ての2要素が比較可能(順序が定義されている)ものを特に全順序集合(totally ordered set; toset)という。例えば実数における大小関係は全順序集合である。
また、全順序ではない順序集合の例としては、正の整数全体の集合に整除関係で順序を定めたものや、(2つ以上元を含む)集合の冪集合において、包含関係を順序と見なしたものがある。
後述するように、順序が満たすべき公理の種類により、前順序集合、半順序集合(partially ordered set; poset)、全順序集合がある。多く場合、半順序集合を指して「順序集合」と呼ぶことが多いが、分野によっては前順序集合や全順序集合を指す場合がある。 まず、二項関係について以下の用語を定める。 ここで P は集合であり、「?」を P 上で定義された二項関係とする。 また、「?」が全順序律を満たさない場合(すなわちa ? bでもb ? aないとき、 a と b は比較不能 (incomparable) であると言う。 P を集合とし、? を P 上で定義された二項関係とする。 ? が前順序であるとき (P, ?) を前順序集合という。同様に ? が半順序なら (P, ?) は半順序集合、全順序なら (P, ?) は全順序集合であるという。また集合 P は (P, ?) の台集合 (underlying set) あるいは台 (support) と呼ばれる。紛らわしくなければ ? を省略し、P を(いずれかの意味で)順序集合という。 順序集合 (P, ?) に対し、? を台 P 上の順序関係ともいう。 上では順序を記号 ? で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号 ? と区別するため、順序の記号として ≺ {\displaystyle \prec } や ≪ {\displaystyle \ll } を使うこともある。 全順序を線型順序ともいい、全順序集合を鎖と呼ぶこともある。また半順序集合の部分集合 A で A の任意の異なる2元が比較不能であるものを反鎖
定義
反射律:P の任意の元 a に対し、a ? a が成り立つ。
推移律:P の任意の元 a, b, c に対し、a ? b かつ b ? c ならば a ? c が成り立つ。
反対称律:P の任意の元 a, b に対し、a ? b かつ b ? a ならば a = b が成り立つ。
全順序律:P の任意の元 a, b に対し、a ? b または b ? a が成り立つ。
前順序・半順序・全順序
? が反射律と推移律を満たすとき、? を P 上の前順序(英語版
? が前順序でありさらに反対称律を満たすとき、? を P 上の半順序 (partial order) という。
? が半順序でありさらに全順序律を満たすとき、? を P 上の全順序 (total order) という。
半順序集合の元 a が他の元 b によって被覆される(英語版) (a <: b) とは、a は b よりも真に小さく、かつそれらの間に別の元が入ることはないことをいう。つまり a <: b {\displaystyle a<:b} とは次の3つがすべて成り立つことである: a ≤ b , a ≠ b , ¬ [ ∃ c s.t. a < c < b ] . {\displaystyle a\leq b,\quad a\neq b,\quad \neg [\exists \ c\ {\text{s.t.}}\ a<c<b].}
順序集合の例
実数全体の集合 R およびその部分集合(例えば、自然数全体の集合 N, 整数全体の集合 Z, 有理数全体の集合 Q)は、通常の大小関係により全順序集合となる。しかし、複素数全体の集合 C には複素数の乗法と"両立"する全順序は存在しない(順序体でない)。単に全順序を入れるだけであれば、直積集合 R × R に辞書式順序を定めることができる。
自然数全体の成す集合は整除関係を順序として半順序集合である。
集合の冪集合に対して、包含関係による順序を入れると半順序集合となる。これはもとの集合の元の個数が2個以上であれば全順序でない。例えば {1, 2, 3} の冪集合
{ ∅ , { 1 } , { 2 } , { 3 } , { 1 , 2 } , { 1 , 3 } , { 2 , 3 } , { 1 , 2 , 3 } } {\displaystyle {\bigl \{}\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}{\bigr \}}} について、例えば {1, 2} と {2, 3} を考えれば、これらは比較不能であり({1, 2} ? {2, 3} でも {2, 3} ? {1, 2} でもない)、全順序ではない。