順序集合

数学において順序集合（じゅんじょしゅうごう、テンプレート:Lang-en-short）とは 「順序」の概念が定義された集合の事で、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。

ただし順序集合内の２つの元a、b に順序関係が定まっている必要はなく、両者が「比較不能」であってもよい。よってa、b の関係は「a はb 以上である」、「b はa 以上である」、「a とb は比較不能である」の３通りのいずれかとなる。

順序集合で特に「比較不能」のケースを許容しないものを全順序集合(totally ordered set)という。全順序集合であれば比較不能のケースはないので集合内の元を小さい方から順番に一列に（すなわち線形に）並べる事ができる。この為全順序集合の事を線型順序集合ともいう。

順序集合は必ずしも全順序とは限らないので、この事を強調して順序集合の事を半順序集合（はんじゅんじょしゅうごう、テンプレート:Lang-en-short）ともいう。（「半順序」という言葉が「全順序」の対義語ではない事に注意。全順序集合も半順序集合の一種である）。

全順序集合の簡単な例は整数の集合や実数の集合で、通常の大小比較を順序とみなしたものがある。 一方、全順序ではない半順序集合の例としては(2つ以上元を含む)集合の冪集合で、包含関係を順序とみなしたものがある。例えば3元集合P ={a,b,c}において{a,b}と{b,c}はいずれも他方を包含していないのでP の冪集合は全順序ではない。実生活に近い例では、「AさんはBさんの子孫である」という事を「A＜B」という大小関係とみなす事で人間全体の集合を半順序集合とみなせる。AさんとBさんはどちらも他方の子孫でない事もありうる（兄弟同士、叔父と甥、赤の他人等）ので、この順序集合は全順序ではない。

定義

全順序集合、半順序集合、およびこれらよりさらに弱い概念である前順序集合の定義を述べる為にまず以下の性質を考える。ここでP は集合であり、「≤」をP 上で定義された二項関係 である。

反射律 

∀a ∈ P ： a ≤ a,

推移律 

∀a , b , c ∈ P ： a ≤ b かつ b ≤ c ⇒ a ≤ c,

反対称律 

∀a , b ∈ P ： a ≤ b かつ b ≤ a ⇒a = b

全順序律 

∀a , b ∈ P ： a ≤ b もしくは b ≤ a である。

「≤」が全順序律を満たさない場合、「a ≤ b」でも「b ≤ a」でもないケースがある。このような第三のケースにあるときa とbは比較不能であるという。したがって全順序律は、a とbが比較不能である事はない、と言い換える事ができる。

前順序・半順序・全順序

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

• 「≤」が反射律と推移律を満たせすとき「≤」をP 上の前順序という。
• 前順序な「≤」が反対称律をも満たすとき「≤」をP 上の半順序という。
• 半順序な「≤」が全順序律をも満たせとき「≤」をP 上の全順序という。

「≤」が前順序、半順序、全順序であるとき組(P, ≤)をそれぞれ前順序集合、半順序集合、全順序集合といい、P を(P, ≤)の台 (support)という。紛れがなければ「≤」を省略し、P の事を(前、半、もしくは全)順序集合という。 |}

(前、半、もしくは全)順序集合(P, ≤)に対し、「≤」の事をP 上の順序関係 ともいう。 なお数学では単に順序あるいは順序集合といった場合はそれぞれ半順序、半順序集合を意味するが、主な研究対象が（前もしくは全）順序集合であるような分野では（前もしくは全）順序集合の意味で「順序集合」を使うことがあるので注意が必要である。

上では順序を記号「≤」で表したが、必ずしもこの記号で表現する必要はない。 整数の大小を表す記号「≤」と区別する為、順序の記号として「<math>\prec</math>」や「<math>\ll</math>」を使う事もある。

全順序の事を線型順序ともいい、全順序集合のことを鎖と呼ぶこともある。また半順序集合の部分集合A でA の任意の相異なる二元が比較不能であるものをテンプレート:仮リンクという。

半順序集合の元 a が他の元 b によってテンプレート:仮リンク テンプレート:Math とは、a は b よりも真に小さく、かつそれらの間に別の元が入ることは無いこと（後述する狭義の記号を使って書けば テンプレート:Math かつ任意の テンプレート:Math に対して テンプレート:Math が偽となること）をいう。

逆順序と狭義の順序

上で述べた順序関係「≤」は直観的には左辺が右辺よりも「小さい、もしくは等しい」事を意味しているが、逆に左辺が右辺よりも「大きい、もしくは等しい」順序関係や等しい事を許容しない順序関係を考える事もできる。

「大きい、もしくは等しい」事を意味する順序関係は「≤」の逆順序と呼ばれ、

<math>a \ge b \iff b \le a</math>

により定義される。

また等しい事を許容しない順序は狭義の(半)順序と呼ばれ、以下のように定義される：

<math>a < b \iff (a \le b \and a \ne b)</math> ...(1)

狭義の逆順序「>」も自然に定義される。

狭義の順序「<」の対義語として、等しい事も許容する順序「≤」の事を広義の(半)順序（もしくは弱い意味 (weak) の(半)順序、反射的 (reflexive) な(半)順序）という。

(1)式で定義された「<」を「≤」の反射的簡約 (reflexive reduction) という。

「≤」が半順序であるとき、その反射的簡約「<」は任意のa, b, c ∈ P に対して以下を満たす：

狭義の順序の性質

非反射性 

¬(a < a);

非対称性 

a < b ならば ¬(b < a);

推移性 

a < b かつ b < c ならば a < c

以上では広義の順序からスタートして狭義の順序を定義したが、逆に上の三性質を満たすものを狭義の順序として定義し、広義の順序を

<math>a \le b \iff a < b \or a = b</math> ...(2)

により定義する事もできる。 この場合、(2)式で定義された「≤」を「<」のテンプレート:仮リンクという。 「<」が前述の３条件を満たせば反射閉包「≤」が半順序である事を簡単に示す事ができる。

順序集合の例

• 自然数全体の集合 N、整数全体の集合 Z、有理数全体の集合 Q、実数全体の集合 R は通常の代数的な大小関係によって全順序集合になるが、複素数はそうではない。複素数全体の集合 C に R × R としての辞書式順序を定めたものは全順序集合であるが、この順序は複素数の乗法とは両立しない。
• 自然数全体の成す集合は整除関係を順序として半順序集合である。
• ある集合の冪集合は部分集合の包含関係を順序として半順序集合となる。これは一般には全順序ではない。例えば {1, 2, 3} の冪集合
  <math>

\{\emptyset, \{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}</math>