順序集合
数学において順序集合（じゅんじょしゅうごう、）とは「順序」の概念が定義された集合の事で、「順序」とは大小、高低、長短等の序列に関わる概念を抽象化したものである。ただし、順序集合内の2つの元 , に順序関係が定まっている（「比較可能」である）必要はなく、両者が「比較不能」であってもよい。
比較不能のケースを許容していることを強調して順序集合の事を半順序集合（はんじゅんじょしゅうごう、）ともいう。一方、半順序集合の中で比較不能のケースがないものを特に全順序集合 () という。（「半順序」という言葉が「全順序」の対義語ではない事に注意。全順序集合も半順序集合の一種である。）
全順序集合の簡単な例は整数の集合や実数の集合で、通常の大小比較を順序とみなしたものがある。
一方、全順序ではない半順序集合の例としては、正の整数全体の集合に整除関係で順序を入れたものや、（2つ以上元を含む）集合の冪集合において、包含関係を順序とみなしたものがある。例えば2元集合 において と はいずれも他方を包含していないので "S" の冪集合は全順序ではない。
実生活に近い例では、「AさんはBさんの子孫である」という事を「A＜B」という大小関係とみなす事で人間全体の集合を半順序集合とみなせる。AさんとBさんはどちらも他方の子孫でない事もありうる（兄弟同士、叔父と甥、赤の他人等）ので、この順序集合は全順序ではない。
全順序集合、半順序集合、およびこれらよりさらに弱い概念である前順序集合の定義を述べる為にまず以下の性質を考える。ここで は集合であり、「」を 上で定義された二項関係とする。「」が全順序律を満たさない場合、「」でも「」でもないケースがある。このようなケースにあるとき と は比較不能 (incomparable) であるという。
を集合とし、 を 上で定義された二項関係 とする。
順序集合 に対し、 を台 上の順序関係ともいう。なお多くの数学の分野では半順序集合を主に扱うので、単に順序あるいは順序集合といった場合はそれぞれ半順序、半順序集合を意味する場合が多いが、分野によっては、主な対象が半順序集合でなく前順序集合や全順序集合である場合があり、そのような分野では前順序集合や全順序集合の意味で「順序集合」という言葉が用いられることがあるので注意が必要である。
上では順序を記号 で表したが、必ずしもこの記号で表現する必要はない。実数の大小を表す記号 と区別する為、順序の記号として formula_1 や formula_2 を使うこともある。
全順序の事を線型順序ともいい、全順序集合のことを鎖と呼ぶこともある。また半順序集合の部分集合 で の任意の相異なる二元が比較不能であるものをという。が部分順序集合は順序集合の部分集合に自然な順序を入れたものも指す。
半順序集合の元 が他の元 によって () とは、 は よりも真に小さく、かつそれらの間に別の元が入ることはないことをいう. つまり formula_3 とは次の３つがすべて成り立つことである： formula_4
上で述べた順序関係「」は直観的には左辺が右辺「よりも小さい、もしくは等しい」事を意味しているが、逆に左辺が右辺「よりも大きい、もしくは等しい」順序関係や等しい事を許容しない順序関係を考える事もできる。
「大きい、もしくは等しい」事を意味する順序関係は「」の逆順序と呼ばれ、
により定義される。
一方、等しい事を許容しない順序は狭義の(半)順序と呼ばれ、以下のように定義される：
狭義の逆順序「」も同様に定義される。
狭義の順序「」の対義語として、等しい事も許容する順序「」の事を広義の(半)順序（もしくは弱い意味 の(半)順序、反射的 な(半)順序）という。
(1) 式で定義された「」を「」の反射的簡約 という。
「」が半順序であるとき、その反射的簡約「」は任意の に対して以下を満たす：以上では広義の順序からスタートして狭義の順序を定義したが、逆に上の三性質（非対称性は非反射性と推移性より得られるので条件としては不要）を満たすものを狭義の順序として定義し、広義の順序を
により定義する事もできる。この場合、(2) 式で定義された「」を「」のという。「」が前述の3条件を満たせば反射閉包「」が半順序である事を簡単に示す事ができる。
を順序集合とするとき、"P" 上の二項関係「formula_8」を
と定義する（すなわち「formula_8」は「」の逆順序を順序とみなしたものである）。すると、「formula_8」も 上の順序になっている事が容易に分かる。formula_12 を の双対順序集合という。
双対順序集合はその定義 formula_12 よりもとの順序集合 とは"大小が逆転"している。したがって における上限、極大元、最大元（定義は後述）は formula_12 ではそれぞれ下限、極小元、最小元に対応している。
を有限集合とし、「」を 上の狭義の半順序とするとき、以下のようにして を自然に単純有向グラフとみなせる：
この有向グラフを図示したものをハッセ図という。
ハッセ図を用いると、順序関係に関する基本的な概念が図示できる。
例えばこの図で と は比較可能だが、 と は比較不能である。また一元集合の族 は反鎖である。さらに は によって被覆されるが、 には被覆されない。
なお、有限半順序集合から前述の方法で作ったグラフは閉路を持たない。逆に を閉路を持たない有限な単純有向グラフとすると、 上に以下の順序を入れる事で を半順序集合とみなせる：
したがって有限半順序集合は閉路を持たない有限な単純有向グラフと自然に同一視できる。
を半順序集合とし、 をその部分集合とし、 を の元とする。このとき上界、最大、極大、上限の概念、およびこれらの双対概念である下界、最小、極小、下限は以下のように定義される：上界および上限の定義において、 が に必ずしも属しているとは限らない、ことには注意が必要である。
極大元の概念と最大元の概念は以下の点で異なる。まず が の極大元であるとは、 の元は「 以下である」か、もしくは「 とは大小が比較不能である」かのいずれかである事を意味する。一方 が の最大元であるとは の元は常に 以下である事を意味する（このとき は の任意の元と比較が可能である）。したがって最大元は必ず極大元であるが、極大元は必ずしも最大元であるとは限らない。
さらに が の（resp. 下方集合）であるとは、任意の と (resp. ) を満たす任意の の元に対し となることをいう。
正整数全体の成す集合を整除関係で順序付ける時、 は任意の正整数を割り切るという意味において は最小元である。しかしこの半順序集合には最大元は存在しない（任意の正整数の倍数としての を追加して考えたとするならば、それが最大元になる）。この半順序集合には極大元も存在しない。実際、任意の元 はそれとは異なる例えば を割り切るから は極大ではありえない。この半順序集合から最小元である を除いて、順序はそのまま整除関係によって入れるならば、最小元は無くなるが、極小元として任意の素数をとることができる。この半順序に関して は部分集合 の上界（上限ではない）を与えるが、 は除かれているので下界は持たない。他方、の冪全体の成す部分集合に対して はその下界（これは下限でもある）を与えるが、上界は存在しない。
順序に関する写像の概念に以下のものがある：
, を順序集合とし、 を写像とする。このときまた順序同型 が存在するとき、 と は順序同型あるいは単に同型であるという。
上で述べた概念は以下の性質を満たす：
自然数全体が整除関係に関して成す半順序集合から、その冪集合が包含関係に関して成す半順序集合への写像 を各自然数にその素因数全体の成す集合を対応させることにより定まる。これは順序を保つ集合である（すなわち、 が を割るならば の各素因数は の素因数にもなる）が単射ではない（例えば も もこの写像で に写る）し、順序を反映もしない（例えば は を割らない）。少し設定を変えて、各自然数にそのの集合を対応させる写像 を考えれば、これは順序を保ち、かつ順序を反映するから、従って順序埋め込みになる。一方、これは順序同型ではない（実際、たとえば単元集合 に写る数は無い）が終域を の値域 に変更すれば順序同型にすることができる。このような冪集合の中への順序同型の構成は、より広汎なと呼ばれる半順序集合のクラスに対して一般化することができる（の項を参照）。
を順序集合とし、, を の元とするとき、閉区間 と開区間 を以下のように定義する：
さらに および を以下のように定義し、半開区間と呼ぶ：
文献によっては , , のことを , , と表す場合もある。
半順序集合がであるとは、すべての区間が有限集合であることを言う。たとえば、整数全体の成す集合は通常の大小関係による半順序に関して局所有限である（端点の無い無限区間のようなものは今考えていない）。
順序集合における区間の概念と、として知られる特定の半順序の類いとを混同してはならない。
全順序集合"A" に対し、無限半開区間
全体の集合を準開基とする位相を順序位相()という。例えば、通常の大小関係 ≤ によって実数全体の集合formula_21を全順序集合と見ると、その順序位相は通常の距離により定められる位相と同等になる。
全順序集合"A"の部分集合"B" には、"B" を全順序集合とみなした時の順序位相と "A" の順序位相から誘導される位相との２つの位相が入る。しかしこの２つの位相は一致するとは限らない。（"B"の順序位相における開集合は誘導位相でも開集合であるが逆は一般には成り立たない）。
例えば"A" を実数全体の集合とし、"A" の部分集合
を考えると、"A" から"B" に誘導される位相では一元集合 は明らかに開集合であるが、"B" は順序集合としてみたときはそうではない。実際"B" は(2を1に移す写像により)formula_23と順序同型だが、"C" の順序位相で は開集合ではないので"B" の順序位相で は開集合ではない。
単に「実数体上の位相」といった場合、前述の順序位相を指すがその他の位相を考える事も（主に反例として用いる為に）できる。
実数体formula_21上の上極限位相とは
全体の集合を開基とする位相の事であり、同様にformula_21上のとは逆向きの半開区間
全体の集合を開基とする位相の事である。
実数体に下限位相を入れた空間はしばしformula_28と書かれ、ゾルゲンフライ直線と呼ばれる。またゾルゲンフライ直線２つの直積formula_29はと呼ばれる。
区間[-1,1]上のとは
を準開基とする位相である。
位相構造を持つ半順序集合"P" で以下の性質を満たすものをという：
（"P" の位相構造でこの性質を満たすものは１つとは限らないが、それらを全て半順序空間という。）
なお、半順序空間と名前の似たは別概念であるので注意が必要である。
定義より明らかに半順序空間は常にハウスドルフ性を満たす。
半順序空間では以下が成立する：
位相構造を持つ半順序集合"P" が半順序空間である必要十分条件は以下を満たす事である：
２つ半順序空間の間の順序を保つ連続写像の事をdimapという。
順序集合"P" 上の以下の２つの位相は同一である事が簡単に示せる。以下のいずれか一方（したがって両方）の条件を満たす位相をという。下方位相も同様にして定義できる。
位相空間"P" がであるとは、"P"上の（有限または無限個の）任意の開集合の共通部分が必ず開集合になる事を言う。
アレクサンドロフ空間は前順序集合と自然に１対１対応している事が知られている。
実際任意の前順序集合"P" に対し、
により"P" に位相を入れたものはアレクサンドロフ空間になる。（この位相を"P" のアレクサンドロフ位相という。）
逆に任意のアレクサンドロフ空間"P" に対し"P" 上の「」を前順序とする事で"P" を前順序集合とみなす事ができる。
ここで位相空間"P" のspecialization preorderとは
で定義される前順序の事である。上式でformula_35は一元集合の閉包である。（なお、"P"がT空間であればspecialization preorderは半順序である事が知られている。）
以上の対応関係により、集合"P" におけるアレクサンドロフ空間としての構造と"P" 上の前順序は１対１対応する。
specialization preorderはアレクサンドロフ空間でなくとも定義可能であるが、アレクサンドロフ空間でない位相空間上ではspecialization preorderに対して上方集合でない開集合も存在する。（なおこの場合でも開集合は常に上方集合である）。したがって前述したような、上方集合を開集合とする位相を考えても元の位相は復元できない。
実数体（に通常の順序をいれたもの）を前順序集合とみなす事で実数体にアレクサンドロフ位相を入れる事ができる。アレクサンドロフ位相における実数体上の開集合（すなわち上方集合）は以下のもののいずれかになる：上で述べたようにアレクサンドロフ位相はformula_37のような「下に閉じた」集合すらも開集合とみなしてしまう。アレクサンドロフ位相からこのような不自然さを取り除いたのがスコット位相である。
順序集合"P" 上のスコット位相()とは、以下の２条件を満たす"P" の部分集合"O" 全体の集合を開集合族とする位相である：後者の条件は内点概念の点列による特徴づけ（"O" の内点"x" に収束する点列は"O" と共通部分を持つ）に類似しているおり、この条件が「下に閉じた」集合を排除する。
よって実数体にスコット位相を入れた際、実数体上の開集合は以下のもののいずれかになる：スコット位相を入れた順序集合をスコット空間といい、スコット空間からスコット空間への連続写像をスコット連続()という。順序集合"P" から順序集合"Q" への写像"f" がスコット連続である必要十分条件は以下の性質が成り立つ事である事が知られている：スコット連続な関数は順序を保つ。実際、"x" ≥ "y" ⇒ sup{"x" , "y" } = "x" であるので、上述した条件より}が存在し、しかもsup{"f" ("x" ), "f" ("y" )} = "f" (sup{"x" , "y" }) = "f" ("x" )となる。これはを意味する。
なお、スコット位相と下方位相のいずれよりも強い位相構造の中で最弱のものをという。
位相空間の開集合全体の集合は包含関係により順序集合とみなせる。位相空間が「sober性」という弱い性質を満たす時はこの順序構造のみで位相空間の構造が特徴づけられる事が知られている（ストーンの双対性定理）。
したがってsober性を満たす空間に話を限定すれば、点集合論に頼らなくても順序構造のみで位相空間論を展開できる（ポイントレス位相空間論）。
ふたつの半順序集合（の台集合）の直積集合上の半順序としては次の三種類が考えられる。
最後の順序は対応する狭義全順序の直積の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの半順序集合の直積に対しても同様に定義される。
体上の順序線型空間に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれもふたたび順序線型空間となる。
任意の半順序集合（および前順序集合）は、任意の射集合が高々一つの元からなる圏と看做すことができる。具体的には、射の集合を ならば （それ以外の場合は空集合）とし、 と定義する。二つの半順序集合が圏として同値となるのは、それらが順序集合として同型であるときであり、かつその時に限る。半順序集合に最小元が存在すればそれは始対象であり、最大元が存在すればそれは終対象となる。また、任意の前順序集合はある半順序集合に圏同値であり、半順序集合の任意の部分圏はいる。
半順序集合からの函手、すなわち半順序圏で添字付けられた図式は、可換図式である。