「順序」はこの項目へ転送されています。その他の用法については「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].} 上で述べた順序関係「?」は直観的には左辺が右辺「よりも小さい、もしくは等しい」ことを意味しているが、逆に左辺が右辺「よりも大きい、もしくは等しい」順序関係や等しいことを許容しない順序関係を考えることもできる。 「大きい、もしくは等しい」ことを意味する順序関係は「?」の逆順序と呼ばれ、 a ≥ b ⟺ b ≤ a {\displaystyle a\geq b\iff b\leq a} により定義される。 一方、等しいことを許容しない順序は狭義の（半）順序と呼ばれ、以下のように定義される： a < b ⟺ ( a ≤ b ∧ a ≠ b ) {\displaystyle a<b\iff (a\leq b\land a\neq b)} …(1) 狭義の逆順序「>」も同様に定義される。 狭義の順序「<」の対義語として、等しいことも許容する順序「?」のことを広義の（半）順序（もしくは弱い意味 (weak) の（半）順序、反射的 (reflexive) な(半)順序）という。 (1) 式で定義された「<」を「?」の反射的簡約 (reflexive reduction) という。 「?」が半順序であるとき、その反射的簡約「<」は任意の a, b, c ∈ P に対して以下を満たす： 以上では広義の順序を定義してから狭義の順序を定義したが、逆に上の三性質（非対称性は非反射性と推移性より得られるので条件としては不要）を満たすものを狭義の順序として定義し、広義の順序を a ≤ b ⟺ a < b ∨ a = b {\displaystyle a\leq b\iff a<b\lor a=b} …(2) により定義することもできる。この場合、(2) 式で定義された「?」を「<」の反射閉包 (P, ?) を順序集合とするとき、P 上の二項関係「 ≼ {\displaystyle \preccurlyeq } 」を a ≼ b ⟺ b ≤ a {\displaystyle a\preccurlyeq b\iff b\leq a} と定義する（すなわち「 ≼ {\displaystyle \preccurlyeq } 」は「?」の逆順序を順序と見なしたものである）。すると、「 ≼ {\displaystyle \preccurlyeq } 」も P 上の順序になっていることが容易に分かる。 ( P , ≼ ) {\displaystyle (P,\preccurlyeq )} を (P, ?) の双対順序集合という。
順序集合の例
実数全体の集合 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} でもない）、全順序ではない。
線形空間の部分空間全体は包含関係で順序付けられた半順序集合である。
半順序集合 P に対し、P の元の（自然数で添え字付けられた）列全体の成す集合は、列 a = (an)n∈N, b = (bn)n∈N に対し、 a ≤ b ⟺ a n ≤ b n ( ∀ n ∈ N ) {\displaystyle a\leq b\iff a_{n}\leq b_{n}\;(\forall n\in \mathbb {N} )} と定めると半順序集合となる。
集合 X と半順序集合 P に対し、X から P への写像全体の成す写像空間（英語版）は、2つの写像 f, g に対して、f ? g を X の任意の元 x に対して f(x) ? g(x) となることとして定義すると、半順序集合になる。
有向非巡回グラフの頂点集合は、到達不可能性によって順序付けられる。
半順序集合における順序関係の向きが a < b > c < d … というように交互に入れ替わる列をフェンス（英語版）と呼ぶ。
逆順序、狭義の順序、双対順序
逆順序
狭義の順序
非反射性：¬(a < a);
非対称性：a < b ならば ¬(b < a); （非反射性と推移性から従う）
推移性：a < b かつ b < c ならば a < c
双対順序集合
