「順序」はこの項目へ転送されています。その他の用法については「wikt:順序」をご覧ください。
.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%;font-size:90%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}html.client-js body.skin-minerva .mw-parser-output .mbox-text-span{margin-left:23px!important}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}

この記事には複数の問題があります。改善やノートページでの議論にご協力ください。

出典は脚注などを用いて記述と関連付けてください。（2019年6月）


独自研究が含まれているおそれがあります。（2019年6月）

順序集合（じゅんじょしゅうごう、英: ordered set）は集合の要素の間に順序が定義された集合。順序とは二項関係であって後述する反射律・推移律などを満たすものであり、数の大小関係などを一般化したものである。

全ての2要素が比較可能（順序が定義されている）ものを特に全順序集合（totally ordered set; toset）という。例えば実数における大小関係は全順序集合である。

また、全順序ではない順序集合の例としては、正の整数全体の集合に整除関係で順序を定めたものや、（2つ以上元を含む）集合の冪集合において、包含関係を順序と見なしたものがある。

後述するように、順序が満たすべき公理の種類により、前順序集合、半順序集合（partially ordered set; poset）、全順序集合がある。多く場合、半順序集合を指して「順序集合」と呼ぶことが多いが、分野によっては前順序集合や全順序集合を指す場合がある。
定義

まず、二項関係について以下の用語を定める。

ここで P は集合であり、「?」を P 上で定義された二項関係とする。

反射律：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 が成り立つ。

また、「?」が全順序律を満たさない場合（すなわちa ? bでもb ? aないとき、 a と b は比較不能 (incomparable) であると言う。
前順序・半順序・全順序

P を集合とし、? を P 上で定義された二項関係とする。

? が反射律と推移律を満たすとき、? を P 上の前順序（英語版） (preorder) または擬順序 (quasiorder) という。

? が前順序でありさらに反対称律を満たすとき、? を P 上の半順序 (partial order) という。

? が半順序でありさらに全順序律を満たすとき、? を P 上の全順序 (total order) という。

? が前順序であるとき (P, ?) を前順序集合という。同様に ? が半順序なら (P, ?) は半順序集合、全順序なら (P, ?) は全順序集合であるという。また集合 P は (P, ?) の台集合 (underlying set) あるいは台 (support) と呼ばれる。紛らわしくなければ ? を省略し、P を（いずれかの意味で）順序集合という。

順序集合 (P, ?) に対し、? を台 P 上の順序関係ともいう。

上では順序を記号 ? で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号 ? と区別するため、順序の記号として ≺ {\displaystyle \prec } や ≪ {\displaystyle \ll } を使うこともある。

全順序を線型順序ともいい、全順序集合を鎖と呼ぶこともある。また半順序集合の部分集合 A で A の任意の異なる2元が比較不能であるものを反鎖（英語版）という。@media screen{.mw-parser-output .fix-domain{border-bottom:dashed 1px}}半順序集合のことを部分順序集合と呼ぶこともある[要出典]が部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。

半順序集合の元 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} でもない）、全順序ではない。