順序集合
概要
順序集合（ordered set）とは、集合 $P$ と、その上の反射律・反対称律・推移律を満たす二項関係 $\leq$ の組 $(P,\leq)$ のことであり、半順序集合とも呼ばれる。実数の大小関係のように任意の二元が比較できることは要求されず、集合の包含関係や正の整数の整除関係のように、どちらとも比較できない二元の組があってもよい。順序の強さに応じて前順序・順序（半順序）・全順序・整列順序という階層があり、順序集合の中では最大元と極大元、上界と上限が区別される。直積順序・双対順序・部分集合への制限によって新しい順序集合が作れ、束・順序数・Zorn の補題など順序を土台とする理論全体の出発点となる。
定義
集合 $P$ とその上の二項関係 $\leq\ \subset P\times P$ の組 $(P,\leq)$ が順序集合（ordered set）であるとは、$\leq$ が次の三条件を満たすことをいう。
- 反射律（reflexivity）：任意の $x\in P$ に対して $x\leq x$。
- 反対称律（antisymmetry）：$x\leq y$ かつ $y\leq x$ ならば $x=y$。
- 推移律（transitivity）：$x\leq y$ かつ $y\leq z$ ならば $x\leq z$。
このとき $\leq$ を $P$ 上の順序（order）または半順序（partial order）といい、三条件をあわせて順序の公理という。順序集合を半順序集合（partially ordered set, poset）とも呼ぶ。文脈から $\leq$ が明らかなときは、組 $(P,\leq)$ を台集合 $P$ だけで表す。$x\leq y$ を「$x$ は $y$ 以下である」と読み、$y\geq x$ は $x\leq y$ の別の書き方とする。
「順序集合」と「半順序集合」は同じ構造を指す二つの名前である。本記事は順序の公理・用語の整理・基本的な例と構成を扱い、半順序集合を対象とする圏や有限順序集合とHasse図の対応など、より進んだ性質は 半順序集合 が扱う。
$(P,\leq)$ を順序集合とする。
- $x,y\in P$ に対し、$x< y$ を「$x\leq y$ かつ $x\neq y$」で定め、$<$ を $\leq$ に付随する狭義順序（strict order）という。$y>x$ は $x< y$ の別の書き方とする。
- $x,y\in P$ が比較可能（comparable）であるとは、$x\leq y$ または $y\leq x$ が成り立つことをいう。比較可能でないとき $x,y$ は比較不能（incomparable）であるといい、$x\parallel y$ と書く。
- 部分集合 $C\subset P$ の任意の二元が比較可能であるとき $C$ を鎖（chain）といい、相異なる任意の二元が比較不能であるとき $C$ を反鎖（antichain）という。
集合 $P$ 上の二項関係 $\leq$ について、次の言葉を用いる。
$(P,\leq)$ を順序集合、$A\subset P$ を部分集合とする。
- $g\in A$ が $A$ の最大元（greatest element）であるとは、任意の $a\in A$ に対して $a\leq g$ が成り立つことをいう。$m\in A$ が $A$ の最小元（least element）であるとは、任意の $a\in A$ に対して $m\leq a$ が成り立つことをいう。
- $m\in A$ が $A$ の極大元（maximal element）であるとは、$m< a$ となる $a\in A$ が存在しないこと、すなわち「$a\in A$ かつ $m\leq a$ ならば $m=a$」が成り立つことをいう。同様に、$a< m$ となる $a\in A$ が存在しないとき $m$ を極小元（minimal element）という。
- $u\in P$ が $A$ の上界（upper bound）であるとは、任意の $a\in A$ に対して $a\leq u$ が成り立つことをいう。$A$ の上界全体の集合に最小元が存在するとき、それを $A$ の上限（supremum, least upper bound）といい $\sup A$ と書く。上界・上限の $\leq$ の向きを逆にしたものを下界（lower bound）・下限（infimum, greatest lower bound）といい、下限を $\inf A$ と書く。
最大元は $A$ に属することが要求されるが、上界は $A$ に属さなくてよい。$A$ が最大元 $g$ を持てば $g$ は $A$ の上界であり、$g=\sup A$ である。逆に $\sup A$ が存在しても $A$ に属するとは限らない。
直感
「大きい・小さい」「含む・含まれる」「割り切る・割り切れる」はどれも二つの対象を比較する操作だが、実数の大小関係と違って、集合の包含関係や整数の整除関係では、どちらとも比較できない二元の組が存在しうる。順序集合は、このような「比較できてもできなくてもよい」比較の枠組みを、反射律・反対称律・推移律の三条件だけで公理化したものである。「一列に並ぶ部分」と「枝分かれして比較できない部分」が共存してよく、比較不能な組が一つもない場合が全順序である。順序集合において「一番大きい元」という素朴な言葉は、全体と比較できる最大元と、自分より上がないだけの極大元とに分かれ、また集合の外にある上界・上限とも区別される。
例と反例
自然数全体 $\mathbb{N}$、整数全体 $\mathbb{Z}$、有理数全体 $\mathbb{Q}$、実数全体 $\mathbb{R}$ に通常の大小関係 $\leq$ を入れると、いずれも順序集合である。しかも任意の二元が比較可能なので全順序集合である。$\mathbb{N}$ の任意の空でない部分集合は最小元を持つので $\mathbb{N}$ は整列集合だが、$\mathbb{Z}$ は最小元を持たない（任意の $n\in\mathbb{Z}$ に対し $n-1< n$）ので整列集合ではない。
集合 $X$ の冪集合 $\mathcal{P}(X)$ 上で、包含関係 $\subset$（等号を許す）を $\leq$ とすると $(\mathcal{P}(X),\subset)$ は順序集合である。反射律 $A\subset A$、反対称律「$A\subset B$ かつ $B\subset A$ ならば $A=B$」（集合の外延性の公理）、推移律「$A\subset B$ かつ $B\subset C$ ならば $A\subset C$」はいずれも包含関係の基本性質である。$X=\{1,2\}$ のとき $\{1\}$ と $\{2\}$ はどちらも他方の部分集合ではなく比較不能なので、$|X|\geq 2$ なら $\mathcal{P}(X)$ は全順序集合ではない。
$\mathcal{P}(X)$ の任意の部分集合族 $\mathcal{A}\subset\mathcal{P}(X)$ は上限 $\sup\mathcal{A}=\bigcup\mathcal{A}$ と下限 $\inf\mathcal{A}=\bigcap\mathcal{A}$（$\mathcal{A}=\emptyset$ のときは $\bigcap\emptyset:=X$）を持つ。実際、$\bigcup\mathcal{A}$ は各 $A\in\mathcal{A}$ を含むので上界であり、任意の上界 $U$ は各 $A\in\mathcal{A}$ を含むので $\bigcup\mathcal{A}\subset U$ である。下限も同様である。
正の整数全体 $\mathbb{Z}_{>0}$ 上で、$a\leq b$ を $a\mid b$（$a$ が $b$ を割り切る、すなわち $b=ac$ となる $c\in\mathbb{Z}_{>0}$ が存在する）で定めると $(\mathbb{Z}_{>0},\mid)$ は順序集合である。反射律は $a=a\cdot 1$ から従う。反対称律：$b=ac$ かつ $a=bd$ なら $a=acd$ であり、$a>0$ より $cd=1$、正の整数なので $c=d=1$、よって $a=b$。推移律：$a\mid b$ かつ $b\mid d$、すなわち $b=ac$、$d=bc'$ なら $d=a(cc')$ であり $a\mid d$。$2$ と $3$ はどちらも他方を割り切らないので比較不能であり、全順序ではない。二元 $a,b$ の上限は最小公倍数、下限は最大公約数である。
$0$ を含む $\mathbb{N}$ 上でも整除関係 $a\mid b$（$b=ac$ となる $c\in\mathbb{N}$ が存在する）は順序である。$0\mid b$ は $b=0$ のときに限り成り立ち、任意の $a$ について $a\mid 0$ なので、$0$ は $(\mathbb{N},\mid)$ の最大元、$1$ は最小元である。
$A=\{2,3,4,5,6\}$ に整除関係を入れる。$4,5,6$ はそれぞれ、自分の真の倍数が $A$ にないので極大元である。一方、$A$ の全ての元から割り切られる $A$ の元は存在しないので、最大元は存在しない。極大元は三つあるが、最大元は一つもない。
$A$ に $60$ を加えた $A'=\{2,3,4,5,6,60\}$ では、$60$ は $2,3,4,5,6$ すべての倍数なので $A'$ の最大元であり、唯一の極大元でもある。
もう一つの例として、$X=\{1,2\}$ とし、$\mathcal{P}(X)\setminus\{X\}=\{\emptyset,\{1\},\{2\}\}$ を包含関係で順序集合とみると、$\{1\}$ と $\{2\}$ はいずれも極大元であり、最大元は存在しない。$\{1\},\{2\}$ の上界は $\mathcal{P}(X)\setminus\{X\}$ の中には存在しないが、$\mathcal{P}(X)$ の中では $X$ が唯一の上界かつ上限である。
四元集合 $P=\{a,b,c,d\}$ 上に、$a\leq c$、$a\leq d$、$b\leq c$、$b\leq d$ と、反射律が要求する $x\leq x$ だけを成り立たせる関係を入れる。この関係は順序である（反対称律は相異なる元の間に双方向の関係がないことから、推移律は $x\leq y\leq z$ で $x\neq y$、$y\neq z$ となる組が存在しないことから従う）。部分集合 $A=\{a,b\}$ の上界は $c$ と $d$ の二つだが、$c\parallel d$ なので上界全体 $\{c,d\}$ に最小元はなく、$\sup A$ は存在しない。上界の存在と上限の存在は別の条件である。
次の各関係は、順序の三条件のうち二つを満たし、残りの一つを満たさない。したがってどれも順序ではなく、三条件のどれも他の二つから従わない。
- 反射律を満たさない：$\mathbb{R}$ 上の通常の狭義大小関係 $<$。推移律を満たし、反対称律は「$x< y$ かつ $y< x$」が決して成り立たないので空虚に満たすが、$x< x$ は成り立たない。
- 反対称律を満たさない：整数全体 $\mathbb{Z}$ 上の整除関係 $a\mid b$（$b=ac$ となる $c\in\mathbb{Z}$ が存在する）。反射律と推移律を満たすので前順序だが、$2\mid -2$ かつ $-2\mid 2$ でありながら $2\neq -2$ である。反対称律が破れる前順序は、正の整数に制限すれば順序になる（ex-ordered-set-divisibility）。
- 推移律を満たさない：集合 $\{\text{グー},\text{チョキ},\text{パー}\}$ 上で「$x$ は $y$ に勝つか等しい」と定めた関係。反射律を満たし、相異なる二元の間の関係は一方向しかないので反対称律も満たすが、グーはチョキに勝ち、チョキはパーに勝つのに、グーはパーに勝たない。「循環する比較」は順序の枠組みでは表せない。
性質
$(P,\leq)$ を順序集合とし、$<$ をその狭義順序とする。このとき $<$ は次の二条件を満たす。
- 非反射律：任意の $x\in P$ に対して $x< x$ は成り立たない。
- 推移律：$x< y$ かつ $y< z$ ならば $x< z$。
逆に、集合 $P$ 上の二項関係 $\prec$ が非反射律と推移律を満たすとき、$x\leq y$ を「$x\prec y$ または $x=y$」で定めると $\leq$ は $P$ 上の順序であり、$\leq$ の狭義順序は $\prec$ に一致する。また、$\leq$ の狭義順序 $<$ から同じ方法で作った関係は $\leq$ に戻る。
$<$ が非反射律を満たすこと：$x< x$ は $x\leq x$ かつ $x\neq x$ を意味するが、$x\neq x$ は偽である。推移律：$x< y$ かつ $y< z$ とすると $x\leq y$、$y\leq z$、$x\neq y$、$y\neq z$ であり、$\leq$ の推移律から $x\leq z$ である。もし $x=z$ なら $x\leq y$ かつ $y\leq z=x$ となり、反対称律から $x=y$ となって $x\neq y$ に反する。よって $x\neq z$、すなわち $x< z$ である。
逆に、非反射律と推移律を満たす $\prec$ から $\leq$ を定める。反射律は定義の「$x=y$」の場合から従う。反対称律：$x\leq y$ かつ $y\leq x$ とする。$x\prec y$ かつ $y\prec x$ なら推移律から $x\prec x$ となり非反射律に反するので、少なくとも一方は「$=$」の場合であり、いずれにせよ $x=y$ である。推移律：$x\leq y$ かつ $y\leq z$ とする。$x=y$ または $y=z$ なら直ちに $x\leq z$ である。$x\prec y$ かつ $y\prec z$ なら $\prec$ の推移律から $x\prec z$、よって $x\leq z$ である。
$\leq$ の狭義順序が $\prec$ に一致すること：「$x\leq y$ かつ $x\neq y$」は「（$x\prec y$ または $x=y$）かつ $x\neq y$」であり、これは $x\prec y$ と同値である（$x\prec y$ なら非反射律から $x\neq y$）。最後に、順序 $\leq$ の狭義順序 $<$ から「$x< y$ または $x=y$」で作った関係は、「（$x\leq y$ かつ $x\neq y$）または $x=y$」であり、反射律により $x\leq y$ と同値である。$\square$
$(P,\leq)$ を順序集合、$S\subset P$ とする。$\leq$ を $S\times S$ に制限した関係 $\leq_S:=\leq\cap(S\times S)$ は $S$ 上の順序である。これを $S$ 上の誘導順序（induced order）といい、$(S,\leq_S)$ を $(P,\leq)$ の順序部分集合（部分集合 $S$ に誘導順序を入れたもの）という。
反射律・反対称律・推移律はいずれも「任意の $x,y,z\in P$ について」成り立つ条件であり、$S$ の元は $P$ の元でもあるから、$x,y,z\in S$ に限っても成り立つ。制限された関係 $\leq_S$ において $x\leq_S y$ は $x\leq y$ と同じ意味なので、三条件は $\leq_S$ についてそのまま成り立つ。$\square$
反射律：$p\leq_P p$ かつ $q\leq_Q q$ なので $(p,q)\leq(p,q)$。反対称律：$(p,q)\leq(p',q')$ かつ $(p',q')\leq(p,q)$ なら、$p\leq_P p'$ かつ $p'\leq_P p$ から $p=p'$、同様に $q=q'$、よって $(p,q)=(p',q')$。推移律：$(p,q)\leq(p',q')$ かつ $(p',q')\leq(p'',q'')$ なら、$p\leq_P p'\leq_P p''$ から $p\leq_P p''$、同様に $q\leq_Q q''$、よって $(p,q)\leq(p'',q'')$。
全順序にならない例：$\mathbb{N}\times\mathbb{N}$ に直積順序を入れると、$(1,0)\leq(0,1)$ には $1\leq0$ が、$(0,1)\leq(1,0)$ にも $1\leq0$ が必要で、どちらも成り立たないため、$(1,0)$ と $(0,1)$ は比較不能である。$\square$
$(P,\leq)$ を順序集合とする。$x\leq^{\mathrm{op}}y$ を $y\leq x$ で定めると、$\leq^{\mathrm{op}}$ も $P$ 上の順序である。$(P,\leq^{\mathrm{op}})$ を $(P,\leq)$ の双対順序集合（dual ordered set）といい $P^{\mathrm{op}}$ と書く。$A\subset P$ に対し、$A$ の $P^{\mathrm{op}}$ における最大元・極大元・上界・上限は、それぞれ $P$ における最小元・極小元・下界・下限である。
反射律：$x\leq x$ より $x\leq^{\mathrm{op}}x$。反対称律：$x\leq^{\mathrm{op}}y$ かつ $y\leq^{\mathrm{op}}x$ なら $y\leq x$ かつ $x\leq y$ であり、$\leq$ の反対称律から $x=y$。推移律：$x\leq^{\mathrm{op}}y$ かつ $y\leq^{\mathrm{op}}z$ なら $y\leq x$ かつ $z\leq y$ であり、$\leq$ の推移律から $z\leq x$、すなわち $x\leq^{\mathrm{op}}z$。
最後の主張は定義を書き換えるだけである。たとえば $g\in A$ が $P^{\mathrm{op}}$ における $A$ の最大元であるとは、任意の $a\in A$ に対し $a\leq^{\mathrm{op}}g$、すなわち $g\leq a$ が成り立つことであり、これは $g$ が $P$ における $A$ の最小元であることにほかならない。極大元・上界・上限についても同様である。$\square$
$(P,\leq)$ を順序集合、$A\subset P$ とする。
- $A$ の最大元は、存在すればただ一つである。同様に、最小元・上限・下限も存在すればただ一つである。
- $A$ の最大元は $A$ の極大元であり、しかも $A$ の唯一の極大元である。
- $(P,\leq)$ が全順序集合ならば、$A$ の極大元は $A$ の最大元である。したがって全順序集合では極大元と最大元は一致する。
- $g,g'$ がともに $A$ の最大元とする。$g'$ が最大元なので $g\leq g'$、$g$ が最大元なので $g'\leq g$、反対称律から $g=g'$。最小元については双対順序を考えれば同じ議論である。上限は上界全体の集合の最小元、下限は下界全体の集合の最大元なので、それぞれ一意である。
- $g$ を $A$ の最大元とする。$a\in A$ かつ $g\leq a$ なら、$a\leq g$ とあわせて反対称律から $g=a$ なので、$g$ は極大元である。$m$ を $A$ の任意の極大元とすると、$g$ が最大元なので $m\leq g$ であり、$m$ が極大元なので $m=g$ である。
- $m$ を $A$ の極大元とし、$a\in A$ を任意にとる。全順序なので $a\leq m$ または $m\leq a$ である。後者なら極大性から $m=a$、よって $a\leq m$ である。いずれにせよ $a\leq m$ となり、$m$ は最大元である。$\square$
補足
def-ordered-set-hierarchy の用語を、課される条件と代表例で整理する。上の行ほど条件が弱く、各行の構造は下の行の構造を特別な場合として含む。
| 名称 | 条件 | 代表例 | 満たさない例 |
|---|---|---|---|
| 前順序 | 反射律・推移律 | $\mathbb{Z}$ 上の整除関係 | じゃんけんの勝敗（推移律が破れる） |
| 順序（半順序） | 前順序・反対称律 | $\mathcal{P}(X)$ の包含関係 | $\mathbb{Z}$ 上の整除関係（反対称律が破れる） |
| 全順序 | 順序・任意の二元が比較可能 | $\mathbb{Z}$、$\mathbb{R}$ の大小関係 | $\mathcal{P}(\{1,2\})$ の包含関係 |
| 整列順序 | 全順序・空でない部分集合が最小元を持つ | $\mathbb{N}$ の大小関係 | $\mathbb{Z}$ の大小関係 |
各段階の詳しい性質は 前順序、全順序、整列順序 が扱う。反対称律を要求しない、空でない前順序集合であって任意の二元が共通の上界を持つものが有向集合であり、任意の二元が上限と下限を持つ順序集合が束である。
集合論寄りの文献（End77 Chapter 7、Jec03 Chapter 2）では、反射的な $\leq$ ではなく、非反射律と推移律を満たす狭義順序 $<$ を先に定義し、そこから $\leq$ を導く流儀を採ることが多い。prop-ordered-set-strict-characterization が示すように二つの流儀は同じ情報を与えるので、どちらを出発点にしても本記事の内容はそのまま成り立つ。
順序集合の言葉で述べられる基本定理として次がある。いずれも本記事では主張の紹介にとどめ、証明はそれぞれの記事と文献に委ねる。
- Zornの補題：順序集合 $(P,\leq)$ の任意の鎖が $P$ に上界を持つならば、$P$ は極大元を持つ。選択公理と同値であり、ベクトル空間の基底（基底(ベクトル空間)）の存在や極大イデアルの存在の証明に使われる（Jec03 Chapter 5）。
- 整列可能定理：任意の集合上に整列順序が存在する。これも選択公理と同値である（Jec03 Chapter 5）。
- Knaster–Tarskiの定理：完備束（任意の部分集合が上限と下限を持つ順序集合）上の単調写像 $f$（$x\leq y$ ならば $f(x)\leq f(y)$）は不動点を持ち、不動点全体も完備束をなす（DP02 Chapter 2）。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
