順序集合

数学における（半）順序集合（はん-じゅんじょしゅうごう、英: [partially] ordered set, poset）とは整列、序列化、配列、順序付けといった直感的概念を定式化するものである。順序集合は、台となる集合とともに、その集合のある元が別の元よりも大きい・小さい、前にある・後にある、上位である・下位であるなどといったことを指示する二項関係をあわせて考えたものである。

このような序列をあらわす関係は、一般には集合のふたつの元が必ずしも比較可能でない（ある元の対に対して、その順序ではどちらが大きいとも小さいともいえないということが起こり得る）という事実を反映して半順序（はんじゅんじょ、partial order; 偏順序、部分順序）と呼ばれる。どのふたつの元でも比較できるような特別な順序は全順序 (total order) または線型順序 (linear order) と呼ばれる。

（台となる集合が有限集合であるような）有限順序集合は、ふたつの元に順序関係があるかどうかを示したハッセ図を使えば、視覚化したり部分順序構造を再構成したりすることができる。

実生活に近いところで言えば、血統的な子孫であるという関係で人間の集まりを考えたりすることは順序集合の例になっている。実際、あるふたりの人は先祖と子孫の関係にあるかもしれないが、そのような関係を持たない組合せもたくさんある。

定義

集合 A 上の（半）順序（関係） (partial order) とは、反射的 (reflexive) で反対称的 (antisymmetric) かつ推移的 (transitive) な A 上の二項関係すなわち a, b, c を A の任意の元として

反射律: a ≤ a,
推移律: a ≤ b かつ b ≤ c ならば a ≤ c,
反対称律: a ≤ b かつ b ≤ a ならば a = b

が成立するような関係 "≤" のことをいう。

反射律と推移律が成り立つ二項関係は前順序(preorder)と呼ばれる。つまり、半順序は反対称的な前順序と言い表すこともできる。

推移律と反対称律によって、半順序関係においてはいわゆる三竦みが起こらないことが保証される。

半順序 ≤ をもつ集合 A を（半）順序集合 ([partially] ordered set) あるいは簡単にポセット (poset) と呼び、(A, ≤) あるいは紛れのおそれの無い場合は台集合と同じく A で表す。

半順序集合 P のふたつの元 a, b に対し、a ≤ b または b ≤ a のいずれか（あるいは両方）が成り立つとき、a と b は比較可能 (comparable) であるといい、そうでないとき比較不能 (incomparable) であるという。順序集合 (A, ≤) が条件

完全律 (totalness): A の任意の元 a, b について比較可能である

を満たすとき、順序 ≤ は全順序 (total order) または線型順序 (linear order) であるといい、順序集合 A は全順序集合 (totally ordered set) または鎖 (chain) と呼ぶ。また、任意のふたつの元が比較不能であるような半順序集合を反鎖 (anti-chain) という。

全順序集合を単に順序集合といい、全順序でないものを特に半順序集合と呼ぶ流儀もある。

狭義の順序

いくつかの文脈では、上で述べた半順序を広義 (non-strict) の、弱い意味 (weak) の、反射的 (reflexive) な半順序と呼び、代わりに、狭義 (strict) のあるいは非反射的 (irreflexive) な半順序 "<" を、非反射的かつ推移的な、したがって非対称な二項関係として定めることがある。つまり、半順序集合 P における狭義の順序を、a, b, c は P の任意の元として

非反射性: ¬(a < a);
非対称性: a < b ならば ¬(b < a);
推移性: a < b かつ b < c ならば a < c

によって定める。広義の順序と狭義の順序との間には一対一対応が存在する。 "≤" を広義の順序とすると、対応する狭義の順序 "<" は

a<b\iff (a\leq b\land a\neq b)

で与えられる反射的簡約 (reflexive reduction) である。逆に、狭義の半順序 "<" に対応する広義の半順序 "≤" は

a\leq b\iff a<b\lor a=b

で与えられる反射的閉包である。このような対応関係があることは、半順序を表すのに "≤" を用いる理由となっている。

狭義の順序は広義のそれよりも直接的に非循環有向グラフに対応するという点で有用である。任意の狭義半順序は非循環有向グラフであり、非循環有向グラフの推移的閉包は狭義半順序集合、したがってふたたび非循環有向グラフとなる。

例

都道府県の集合に人口の大小で順序を定めると前順序集合になる。特に人口の等しい都道府県が無ければ全順序集合になる。
自然数全体の集合 N、整数全体の集合 Z、有理数全体の集合 Q、実数全体の集合 R は通常の代数的な大小関係によって全順序集合になるが、複素数はそうではない。複素数全体の集合 C に R × R としての辞書式順序を定めたものは全順序集合であるが、この順序は複素数の乗法とは両立しない。
自然数全体の成す集合は整除関係を順序として半順序集合である。
ある集合の冪集合は部分集合の包含関係を順序として半順序集合となる。これは一般には全順序ではない。例えば {1, 2, 3} の冪集合
$\{\emptyset ,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}$
について、たとえば {1, 2} と {2, 3} を考えれば、これらは比較不能である（{1, 2} ≤ {2, 3} でも {2, 3} ≤ {1, 2} でもない）。
ベクトル空間の部分空間全体は包含関係で順序付けられた半順序集合である。
半順序集合 P に対し、P の元の列全体の成す集合は、列 a, b に対し、
$a=(a_{n})_{n\in \mathbb {N} }\leq b=(b_{n})_{n\in \mathbb {N} }\iff a_{n}\leq b_{n}(\forall n\in \mathbb {N} )$
と定めると半順序集合となる。
集合 X と半順序集合 P に対し、X から P への写像全体の成す写像空間は、ふたつの写像 f, g に対して、f ≤ g を X の任意の元 x に対して f(x) ≤ g(x) となることとして定義すると、半順序集合になる。
非循環有向グラフの頂点集合は、到達不可能性によって順序付けられる。
半順序集合における順序関係の向きが a < b > c < d ... というように交互に入れ替わる列をフェンスと呼ぶ。

写像と順序

写像 f: A → B は A の任意の元 a, b について

a ≤ b ならば f(a) ≤ f(b) を満たすとき順序を保つ写像といわれる。

a ≤ b ならば f(a) ≥ f(b) を満たすとき順序を逆にする写像といわれる。

実変数実数値の関数で単調増大なものは順序を保つ写像、単調減少なものは順序を逆にする写像となっていることから、順序を保つ写像と順序を逆にする写像を総称して単調写像ということがある。

順序を保つ写像 f: A → B が全単射であっても、逆写像 f⁻¹ は順序を保つとは限らないが（ただし、A,B が全順序集合のときは f⁻¹ は順序を保つ）、逆写像 f⁻¹ も順序を保つとき、f は 順序同型写像あるいは単に順序同型と呼ばれる。また、A と B は順序同型であるという。

順序同型な 2 つの順序集合は、個々の要素は異なっても順序集合として同じ"形"をしていると言える。そこで、同じ"形"をした順序集合たちにその"形"を表す何かを割り当て、個々の要素の違いを無視した構造のみに注目して順序集合を考察をすることが考えられる。このように各順序集合に割り当てられたものを順序型と呼ぶ。

詳細は「順序型」を参照

直積集合上の順序

ふたつの半順序集合（の台集合）の直積集合上の半順序としては次の三種類が考えられる。

辞書式順序: $(a,b)\leq (c,d)\iff a<c\lor (a=c\land b\leq d)$
積順序: $(a,b)\leq (c,d)\iff a\leq c\land b\leq d$
$(a,b)\leq (c,d)\iff (a<c\land b<d)\lor (a=c\land b=d)$

最後の順序は対応する狭義全順序の直積の反射閉包である。これらの三種類の順序はいずれもふたつよりも多くの半順序集合の直積に対しても同様に定義される。

体上の順序線型空間に対してこれらの構成を適用すれば、結果として得られる順序集合はいずれもふたたび順序線型空間となる。

逆順序・双対順序

半順序関係 "≤" の逆 (inverse, converse, opposite) "≥" とは

x\geq y\iff y\leq x

を満足する関係である。半順序の逆は、反射的、推移的かつ反対称な関係であるから、それ自身が反順序である。半順序集合 (P, ≤) の双対順序集合 (order dual) とは、台集合はもとの半順序集合のそれと同じものとし、もとの半順序の逆を順序関係として入れた半順序集合 (P, ≥) を言う。"≥" に対する非反射的順序 ">" も、"≤" に対する "<" と同様に定義される。

与えられた集合上の四つの関係 "≤", "<", "≥", ">" は、そのうちのいずれでも一つ与えられれば、他の三つはそれから一意的に決定することができる。

一般に、半順序集合のふたつの元 x, y に対して、

x < y,
x = y,
x > y,
x と y は比較不能

という互いに排他的な四つの条件のうち、いずれかひとつだけが成り立つ。全順序集合に対しては、ふたつの元は常に比較可能だから、この最後の条件は無視してよい（このとき、三分法が成り立つという）。

順序集合の極値

順序集合の「最大」や「最小」に関する概念にはいくつかの種類がある。

順序集合の空でない部分集合 A について、A の任意の元 a に対して a ≤ b が成り立つような b を A の上界（じょうかい、upper bound）という。上界が存在するとき、集合 A は上に有界であるという。また、A の任意の元 a に対して b ≤ a が成り立つような b を A の下界（かかい、lower bound）という。下界が存在するとき、集合 A は下に有界であるという。上下に有界であるとき、単に有界である (bounded) という。

A のある元 s に対して、s ≤ a となる A の元 a は常に s = a となるとき、s を極大元（きょくだいげん、 maximal element）という。また、A のある元 s に対して、a ≤ s となる A の元 a は常に s = a となるとき、s を極小元（きょくしょうげん、minimal element）という。

A のある元 m が任意の A の元 a に対して a ≤ m を満たすとき、m を A の最大元（さいだいげん、maximum element）といい、max A と書く。また、A のある元 m が任意の A の元 a に対して m ≤ a を満たすとき、m を A の最小元（さいしょうげん、minimum element）といい、min A と書く。

最大元や最小元は高々一つしかないことが、順序の公理の 3 番目（反対称律）から分かる。最大元は極大元になるが、この逆は正しくない。A はいくつもの異なる極大元を持つかもしれない。

上界の集合の最小元（つまり、最小の上界）のことを、上限（じょうげん、least upper bound, supremum）といい、sup(A) と書く。また、下界の集合の最大元（つまり、最大の下界）のことを、下限（かげん、greatest lower bound, infimum）といい、inf(A) と書く。

A が最大元 M を持てば、M は A の上限になる。また、A が最小元 m を持てば、m は A の下限になる。

自然数の間に順序 a ≤ b を a | b（a は b の約数）で定義する。集合 {a, b} の上界、下界はそれぞれ a と b の公倍数、公約数であり、上限、下限はそれぞれ最小公倍数、最大公約数である。{1, 2, ..., 10} の極大元は 6, 7, 8, 9, 10 であり、最大元は存在しない。最小元は 1 である。
集合 S を S = {m | ある自然数 n が存在して m = 2ⁿ} で定義して上と同じ順序を考えると、これは全順序集合になる。写像 f: S → N を f(2ⁿ) = n で与えると、これは順序同型になる。ただし、値域の自然数の順序には普通の大小関係を考える。
S をある集合とし、そのべき集合 2^S の間に包含関係による順序を考える。A, B を S のある部分集合とすると、{A, B} の上限、下限はそれぞれ A ∪ B、A ∩ B である。
ある環の自明でないイデアル全体の集合に包含関係による順序を考える。極大イデアルはこの集合の極大元である。

整列集合

詳細は「整列集合」を参照

順序集合は、その任意の空でない部分集合が最小元を持つとき整列集合 (well-ordered set) であるという。また、その順序を整列順序 (well-order) という。定義からすぐに「整列集合は全順序集合である」ということが分かる。実際、任意の二つの元 a, b をとってきたとき、その二つの元のなす集合 {a, b} にも最小元があるから、a ≤ b か b ≤ a のどちらかが成り立つ。これは全順序であるということに他ならない。

自然数全体の集合 N は大小関係によって整列集合になる。
普通の大小関係において整数全体の集合 Z、有理数全体の集合 Q、実数全体の集合 R はそうではない。
Z は 0 < -1 < 1 < -2 < 2 < -3 < 3 < … と順序を定めると整列集合になる。
Q や R では（特に R では）、このような簡単な修正ではうまく行かない。

しかし、選択公理を仮定すると、次の整列可能定理 (well-ordering theorem、単に整列定理、ツェルメロの整列定理ともいう）が証明できる。

任意の集合は整列集合となるように順序を定めることができる。

逆に、整列可能定理を仮定して選択公理を証明することもできるので、整列可能定理は選択公理と同値であり、さらにはツォルンの補題などとも同値である。

線型順序拡大

全順序 T が半順序 P の線型拡大（あるいは線型拡張）であるとは、P において x ≤ y であるような二元については T においてもなお x ≤ y となっているときにいう。任意の半順序は全順序に拡張することができる（順序拡大原理^[1]）。

計算機科学において、半順序の線型拡張を求めるアルゴリズムは位相ソート (topological sorting) と呼ばれる。

区間

順序集合 P において、a ≤ b を満たすふたつの元 a, b に対して、それらを端点とする閉区間 [a, b] とは、a ≤ x かつ x ≤ b を満足する元 x 全体の成す集合

[a,b]:=\{x\in P\mid a\leq x\leq b\}

のことをいう。これは少なくともふたつの元 a および b を含む。これに対して、"≤" に対応する狭義の順序関係 "<" を用いれば、開区間 (a, b) が a < x かつ x < b を満たす元 x 全体の成す集合

(a,b):=\{x\in P\mid a<x<b\}

として定まる。半開区間 [a,b) および (a,b] も同様に定義する。しばしば、この定義に言うこれらの区間は a > b の場合には空集合を表すものとして扱うことがある。ただし、開区間 (a, b') はたとえ a < b の場合であっても空集合となりうる。

半順序集合が局所有限であるとは、すべての区間が有限集合であることを言う。たとえば、整数全体の成す集合は通常の大小関係による半順序に関して局所有限である（端点の無い無限区間のようなものは今考えていない）。

順序集合における区間の概念と、区間順序 (interval order) として知られる特定の半順序の類とを混同してはならない。

順序構造と位相構造

全順序集合には次のようにして自然に位相構造が定められる。これを順序位相 (order topology) という。例えば、通常の大小関係 ≤ によって実数全体の集合 R を全順序集合と見ると、その順序位相は通常の距離により定められる位相と同等になる。

(A, ≤) を一般の全順序集合とする。無限半開区間(-∞, b)および(a, +∞)全体を準開基とする位相が定まる。これを A の順序位相という。

P が半順序集合で位相空間の構造をも持つとき、慣習的に {(a, b) ∈ P × P | a ≤ b } が直積位相に関する閉部分集合であるものと仮定する。この仮定の下で、半順序関係は

[(a_{i}\to a)\land (a_{i}\leq b{\text{ for all }}i)]\Rightarrow a\leq b

が成り立つという意味で数列の極限に関してよく振舞う (well-behaved)（Deshpande (1968) を参照）。

圏としての順序集合

任意の半順序集合（および前順序集合）は、任意の射の集合が唯一つの元からなる圏と看做すことができる。詳しく述べれば、射の集合を

{\text{hom}}(x,y)={\begin{cases}{(x,y)}&(x\leq y)\\\emptyset &({\text{otherwise}})\end{cases}}

とし、射の合成を

(y,z)\circ (x,y)=(x,z)

で定めるのである。ふたつの半順序集合が同値であるというのを、それらが同型であることとして定める。半順序集合を圏と見たとき、半順序集合における最小元はいずれも始対象であり、最大元はいずれも終対象である。また、任意の前順序集合はある半順序集合に同値であり、半順序集合の任意の部分圏は同型射について閉じている。

半順序集合からの函手、すなわち半順序圏で添字付けられた図式は、可換図式である。

注記

^ Jech, Thomas (2008) [originally published in 1973]. The Axiom of Choice. Dover Publications. ISBN 0-486-46624-8

参考文献

Jayant V. Deshpande, On Continuity of a Partial Order, Proceedings of the American Mathematical Society, Vol. 19, No. 2, 1968, pp. 383-386
Bernd S. W. Schröder, Ordered Sets: An Introduction (Boston: Birkhäuser, 2003)
Richard P. Stanley, Enumerative Combinatorics, vol.1, Cambridge Studies in Advanced Mathematics 49, Cambridge University Press, ISBN 0-521-66351-2

外部リンク

n 個の元を持つ集合の部分集合の個数を示した数列 A001035 : OEIS

定義