半順序

同義語：partial order部分順序

概要

定義

半順序の定義

集合 $P$ 上の二項関係 $R\subset P\times P$ が $P$ 上の半順序（partial order）であるとは、$(x,y)\in R$ を $x\leq y$ と書くとき、次の三条件を満たすことをいう。

反射律（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$。
半順序を単に順序（order）、あるいは全順序と対比して部分順序ということもある。半順序 $\leq$ を備えた集合の組 $(P,\leq)$ を半順序集合または順序集合という。本記事は関係 $\leq$ そのものを主題とし、組 $(P,\leq)$ の構造（最大元と極大元、上界と上限、Hasse図など）は順序集合・半順序集合が扱う。

狭義半順序の定義

集合 $P$ 上の二項関係 $S\subset P\times P$ が $P$ 上の狭義半順序（strict partial order）であるとは、$(x,y)\in S$ を $x< y$ と書くとき、次の二条件を満たすことをいう。

非反射律（irreflexivity）：任意の $x\in P$ に対して $x< x$ は成り立たない。
推移律：$x< y$ かつ $y< z$ ならば $x< z$。
半順序 $\leq$ に対し、$x< y$ を「$x\leq y$ かつ $x\neq y$」で定めた関係を $\leq$ に付随する狭義半順序（狭義順序）という。この名称が正当であること、および逆に狭義半順序から半順序が一意に復元されることは prop-partial-order-strict-bijection で証明する。

近接する関係の名称

集合 $P$ 上の二項関係 $\leq$ について、次の言葉を用いる。

反射律と推移律を満たす（反対称律は要求しない）とき、$\leq$ を前順序（preorder）という。
半順序であって、さらに任意の $x,y\in P$ について $x\leq y$ または $y\leq x$ が成り立つとき、$\leq$ を全順序（total order）という。$x\leq y$ も $y\leq x$ も成り立たない二元 $x,y$ を比較不能（incomparable）という。
したがって、全順序は半順序であり、半順序は前順序である。逆の含意はいずれも成り立たない（rem-partial-order-counterexamples）。

関係の演算

集合 $P$ 上の二項関係 $R,S\subset P\times P$ に対して、次の記号を用いる。

対角集合 $\Delta_P:=\{(x,x)\mid x\in P\}$。これは $P$ 上の等号を関係とみたものである。
逆関係 $R^{-1}:=\{(y,x)\mid (x,y)\in R\}$。
合成 $S\circ R:=\{(x,z)\mid \text{ある }y\in P\text{ について }(x,y)\in R\text{ かつ }(y,z)\in S\}$。
部分集合 $A\subset P$ への制限 $R|_A:=R\cap(A\times A)$。
集合 $Q$ 上の二項関係 $T$ との直積 $R\times T$ を、直積 $P\times Q$ 上の関係 $\{((p,q),(p',q'))\mid (p,p')\in R\text{ かつ }(q,q')\in T\}$ とする。

直感

「大きい・小さい」「含む・含まれる」「割り切る・割り切れる」「前に済ませておく必要がある」は、どれも二つのものを比べる言い方である。半順序は、こうした比較のうち「自分は自分と比べられる」「互いに相手以下なら同じもの」「比較を二段つなげられる」という三つの性質だけを取り出して公理化した関係である。実数の大小と違って、どちらとも言えない二元の組があってよい。この「比べられない組があってよい」ことを表すのが「半」（partial）という接頭語であり、比較不能な組が一つもない半順序が全順序である。前順序は「互いに相手以下でも同じものとは限らない」ことまで許した関係であり、半順序は前順序と全順序のあいだに位置する。

例と反例

集合の包含による半順序

集合族 $\mathcal{F}$（たとえば集合 $X$ の冪集合 $\mathcal{P}(X)$）の上で、包含関係 $A\leq B:\iff A\subset B$ は半順序である。反射律 $A\subset A$ は明らかであり、反対称律「$A\subset B$ かつ $B\subset A$ ならば $A=B$」は集合の相等の定義（外延性の公理）そのものであり、推移律「$A\subset B$ かつ $B\subset C$ ならば $A\subset C$」は $x\in A\Rightarrow x\in B\Rightarrow x\in C$ から従う。$X=\{1,2\}$ のとき $\{1\}$ と $\{2\}$ は比較不能なので、この半順序は一般に全順序ではない。任意の半順序が包含関係の制限として実現できることは prop-partial-order-embedding で示す。

正の整数の整除による半順序

正の整数全体 $\mathbb{Z}_{>0}$ の上で、整除関係 $a\leq b:\iff a\mid b$（$b=ac$ となる $c\in\mathbb{Z}_{>0}$ が存在する）は半順序である。反射律は $a=a\cdot1$ から、推移律は $b=ac$、$d=bc'$ ならば $d=a(cc')$ から従う。反対称律は、$b=ac$ かつ $a=bd$ ならば $a=acd$、$a>0$ より $cd=1$、正の整数なので $c=d=1$、よって $a=b$ となることによる。$2$ と $3$ は比較不能である。整除関係を整数全体 $\mathbb{Z}$ に広げると反対称律が破れる（rem-partial-order-counterexamples）。

座標ごとの順序

実数の組全体 $\mathbb{R}^n$ の上で、$(x_1,\ldots,x_n)\leq(y_1,\ldots,y_n):\iff$ すべての $i$ について $x_i\leq y_i$ と定めた関係（座標ごとの順序、直積順序）は半順序である。三条件はいずれも各座標で $\mathbb{R}$ の大小関係の対応する条件を用いれば従う。たとえば反対称律は、$x\leq y$ かつ $y\leq x$ なら各 $i$ で $x_i\leq y_i$ かつ $y_i\leq x_i$、よって $x_i=y_i$ となることによる。$n\geq2$ のとき $(1,0)$ と $(0,1)$ は比較不能なので全順序ではない。一般の直積は prop-partial-order-constructions で扱う。

部分写像の拡大関係

集合 $X$ から集合 $Y$ への部分写像とは、$X$ の部分集合 $D$（定義域）から $Y$ への写像 $f\colon D\to Y$ のことである。部分写像 $f\colon D\to Y$、$g\colon E\to Y$ について、$g$ が $f$ の拡大（extension）である（$f$ は $g$ の制限である）とは、$D\subset E$ かつ任意の $x\in D$ に対して $g(x)=f(x)$ が成り立つことをいい、$f\leq g$ と書く。$X$ から $Y$ への部分写像全体の上で、この拡大関係は半順序である。
実際、写像を関数のグラフ $\{(x,f(x))\mid x\in D\}\subset X\times Y$ と同一視すると、$f\leq g$ は $f$ のグラフが $g$ のグラフに含まれることと同値である。$f$ のグラフが $g$ のグラフに含まれれば、$x\in D$ に対し $(x,f(x))$ が $g$ のグラフに属するので $x\in E$ かつ $g(x)=f(x)$ であり、逆も明らかである。したがって拡大関係は、$X\times Y$ の部分集合全体の包含関係（ex-partial-order-inclusion）を部分写像のグラフ全体に制限したものであり、prop-partial-order-constructions により半順序である。空写像は最小の元であり、$D\cap E$ 上で値が食い違えば二つの部分写像は比較不能である。この半順序は、Zornの補題によって写像を極大に拡大する議論（たとえば線形写像や体の同型の拡大）で用いられる。

反例：各公理を一つずつ破る関係

次の各関係は、半順序の三条件のうち二つを満たし、残りの一つを満たさない。したがってどの条件も他の二つから従わず、どれを落としても半順序にならない。

反射律を満たさない：集合 $X$ の冪集合 $\mathcal{P}(X)$ 上の真包含（$A$ が $B$ の真部分集合である関係）$A\subsetneq B$。推移律を満たし、「$A\subsetneq B$ かつ $B\subsetneq A$」は決して成り立たないので反対称律は空虚に満たすが、$A\subsetneq A$ は成り立たない。これは狭義半順序の例である。
反対称律を満たさない：整数全体 $\mathbb{Z}$ 上の関係 $x\leq y:\iff|x|\leq|y|$。反射律と推移律を満たすので前順序だが、$|2|\leq|-2|$ かつ $|-2|\leq|2|$ でありながら $2\neq-2$ である。同様に、$\mathbb{Z}$ 上の整除関係 $a\mid b$（$b=ac$ となる $c\in\mathbb{Z}$ が存在する）も前順序だが、$2\mid-2$ かつ $-2\mid2$ なので反対称律を満たさない。前順序を半順序に直す標準的な方法は prop-partial-order-preorder-quotient で与える。
推移律を満たさない：実数全体 $\mathbb{R}$ 上の関係 $x\leq' y:\iff x\leq y\leq x+1$（「$y$ は $x$ 以上で、$x$ から高々 $1$ しか離れていない」）。反射律を満たし、$x\leq'y$ かつ $y\leq'x$ なら $x\leq y\leq x$ より $x=y$ なので反対称律も満たすが、$0\leq'1$、$1\leq'2$ であるのに $0\leq'2$ ではない。
次の関係は、上の含意の逆が成り立たないことを示す。
前順序だが半順序でない：2 の関係。含意「前順序 $\Rightarrow$ 半順序」は成り立たない。
半順序だが全順序でない：ex-partial-order-inclusion の $\mathcal{P}(\{1,2\})$ 上の包含関係。含意「半順序 $\Rightarrow$ 全順序」は成り立たない。
二つの半順序の合併は半順序とは限らない：二元集合 $\{a,b\}$ 上の半順序 $R_1=\Delta\cup\{(a,b)\}$ と $R_2=\Delta\cup\{(b,a)\}$ の合併 $R_1\cup R_2$ は $(a,b)$ と $(b,a)$ を含み $a\neq b$ なので反対称律を満たさない。また三元集合 $\{a,b,c\}$ 上の $\Delta\cup\{(a,b)\}$ と $\Delta\cup\{(b,c)\}$ の合併は $(a,c)$ を含まないので推移律を満たさない。共通部分については prop-partial-order-constructions を参照。

性質

関係の演算による三条件の言い換え

集合 $P$ 上の二項関係 $R$ について次が成り立つ。

$R$ が反射律を満たすことと $\Delta_P\subset R$ は同値である。
$R$ が反対称律を満たすことと $R\cap R^{-1}\subset\Delta_P$ は同値である。
$R$ が推移律を満たすことと $R\circ R\subset R$ は同値である。
したがって $R$ が半順序であることは、$\Delta_P\subset R$、$R\cap R^{-1}\subset\Delta_P$、$R\circ R\subset R$ の三つの包含が成り立つことと同値である。また $R$ が狭義半順序であることは、$R\cap\Delta_P=\emptyset$ かつ $R\circ R\subset R$ と同値である。

$\Delta_P\subset R$ は「任意の $x\in P$ について $(x,x)\in R$」の言い換えである。
$(x,y)\in R\cap R^{-1}$ は「$(x,y)\in R$ かつ $(y,x)\in R$」、すなわち $x\leq y$ かつ $y\leq x$ と同値であり、$(x,y)\in\Delta_P$ は $x=y$ と同値である。よって $R\cap R^{-1}\subset\Delta_P$ は反対称律の言い換えである。
$(x,z)\in R\circ R$ は「ある $y$ について $x\leq y$ かつ $y\leq z$」と同値なので、$R\circ R\subset R$ は「$x\leq y$ かつ $y\leq z$ ならば $x\leq z$」の言い換えである。
最後の主張は、非反射律「任意の $x$ について $(x,x)\notin R$」が $R\cap\Delta_P=\emptyset$ の言い換えであることによる。$\square$

狭義半順序との一対一対応

集合 $P$ を固定する。$P$ 上の半順序 $R$ に対して $R^{\circ}:=R\setminus\Delta_P$ とおき、$P$ 上の狭義半順序 $S$ に対して $\overline{S}:=S\cup\Delta_P$ とおく。このとき次が成り立つ。

$R$ が半順序ならば $R^{\circ}$ は狭義半順序であり、$(x,y)\in R^{\circ}$ は「$x\leq y$ かつ $x\neq y$」と同値である。
$S$ が狭義半順序ならば $\overline{S}$ は半順序である。
$\overline{R^{\circ}}=R$ かつ $(\overline{S})^{\circ}=S$。したがって $R\mapsto R^{\circ}$ と $S\mapsto\overline{S}$ は、$P$ 上の半順序全体の集合と $P$ 上の狭義半順序全体の集合との間の互いに逆な全単射である。
狭義半順序 $S$ は非対称律（asymmetry）を満たす：$x< y$ ならば $y< x$ は成り立たない。

$R^{\circ}\cap\Delta_P=\emptyset$ は定義から明らかであり、$(x,y)\in R^{\circ}$ が「$x\leq y$ かつ $x\neq y$」と同値であることも定義そのものである。推移律：$(x,y),(y,z)\in R^{\circ}$ とすると $x\leq y\leq z$ より $x\leq z$ である。もし $x=z$ なら $x\leq y$ かつ $y\leq x$ となり、反対称律から $x=y$ となって $(x,y)\in R^{\circ}$ に反する。よって $x\neq z$、すなわち $(x,z)\in R^{\circ}$ である。
$\Delta_P\subset\overline{S}$ は定義から明らかである。反対称律：$(x,y),(y,x)\in\overline{S}$ かつ $x\neq y$ と仮定すると、$(x,y),(y,x)\notin\Delta_P$ なので $(x,y),(y,x)\in S$ であり、$S$ の推移律から $(x,x)\in S$ となって非反射律に反する。よって $x=y$ である。推移律：$(x,y),(y,z)\in\overline{S}$ とする。$x=y$ または $y=z$ なら $(x,z)$ は $(y,z)$ または $(x,y)$ に等しく $\overline{S}$ に属する。そうでなければ $(x,y),(y,z)\in S$ であり、$S$ の推移律から $(x,z)\in S\subset\overline{S}$ である。
$R$ が半順序なら $\Delta_P\subset R$ なので $\overline{R^{\circ}}=(R\setminus\Delta_P)\cup\Delta_P=R$ である。$S$ が狭義半順序なら $S\cap\Delta_P=\emptyset$ なので $(\overline{S})^{\circ}=(S\cup\Delta_P)\setminus\Delta_P=S$ である。1・2 とあわせて、二つの写像は互いに逆である。
$x< y$ かつ $y< x$ なら推移律から $x< x$ となり、非反射律に反する。$\square$

この命題により、半順序 $\leq$ と狭義半順序 $<$ は同じ情報を持ち、どちらを出発点にとってもよい。順序集合では同じ対応を元ごとの言葉で述べている。

前順序から半順序を作る商

$\lesssim$ を集合 $P$ 上の前順序とし、$x\sim y:\iff x\lesssim y$ かつ $y\lesssim x$ と定める。このとき次が成り立つ。

$\sim$ は $P$ 上の同値関係である。
商集合 $P/{\sim}$ 上で、$[x]\leq[y]:\iff x\lesssim y$ は代表元の取り方によらずに定まり、$P/{\sim}$ 上の半順序である。
$\lesssim$ 自身が半順序であることと、$\sim$ が等号に一致する（$x\sim y$ ならば $x=y$）こととは同値である。

反射律 $x\sim x$ は $\lesssim$ の反射律から従う。対称律は定義が $x,y$ について対称なので明らかである。推移律：$x\sim y$ かつ $y\sim z$ なら $x\lesssim y\lesssim z$ と $z\lesssim y\lesssim x$ から、$\lesssim$ の推移律により $x\lesssim z$ かつ $z\lesssim x$ である。
代表元によらないこと：$x\sim x'$、$y\sim y'$ かつ $x\lesssim y$ とする。$x'\lesssim x\lesssim y\lesssim y'$ より $x'\lesssim y'$ である。逆向きも同様なので、$x\lesssim y$ と $x'\lesssim y'$ は同値である。反射律：$x\lesssim x$ より $[x]\leq[x]$。推移律：$[x]\leq[y]\leq[z]$ なら $x\lesssim y\lesssim z$ より $x\lesssim z$、すなわち $[x]\leq[z]$。反対称律：$[x]\leq[y]$ かつ $[y]\leq[x]$ なら $x\lesssim y$ かつ $y\lesssim x$、すなわち $x\sim y$ であり、$[x]=[y]$ である。
$\lesssim$ が反対称律を満たすことは、「$x\lesssim y$ かつ $y\lesssim x$ ならば $x=y$」、すなわち「$x\sim y$ ならば $x=y$」と同じ主張である。$\square$

半順序から半順序を作る操作

$R$ を集合 $P$ 上の半順序、$T$ を集合 $Q$ 上の半順序とする。

逆関係 $R^{-1}$ は $P$ 上の半順序である（双対順序）。
任意の部分集合 $A\subset P$ について、制限 $R|_A$ は $A$ 上の半順序である（誘導順序）。
$P$ 上の半順序からなる空でない族 $\{R_i\}_{i\in I}$ の共通部分 $\bigcap_{i\in I}R_i$ は $P$ 上の半順序である。
直積 $R\times T$ は $P\times Q$ 上の半順序である（直積順序）。
同じ主張は、$R$ と $T$ を狭義半順序に置き換えても成り立つ。

(1)(2)(4) は順序集合の記事が元ごとの言葉で証明している。ここでは関係演算による別証明を与える。

prop-partial-order-relational の三つの包含を確かめる。
(1) $\Delta_P^{-1}=\Delta_P$ なので $\Delta_P\subset R$ から $\Delta_P\subset R^{-1}$。$(R^{-1})^{-1}=R$ より $R^{-1}\cap(R^{-1})^{-1}=R^{-1}\cap R=(R\cap R^{-1})^{-1}\subset\Delta_P^{-1}=\Delta_P$。$(x,z)\in R^{-1}\circ R^{-1}$ なら、ある $y$ について $(x,y),(y,z)\in R^{-1}$、すなわち $(z,y),(y,x)\in R$ なので $(z,x)\in R$、よって $(x,z)\in R^{-1}$。
(2) $\Delta_A=\Delta_P\cap(A\times A)\subset R\cap(A\times A)=R|_A$。$R|_A\cap(R|_A)^{-1}\subset R\cap R^{-1}\subset\Delta_P$ であり、左辺は $A\times A$ に含まれるので $\Delta_A$ に含まれる。$(x,z)\in R|_A\circ R|_A$ なら $x,z\in A$ で $(x,z)\in R\circ R\subset R$、よって $(x,z)\in R|_A$。
(3) $R':=\bigcap_{i\in I}R_i$ とおく。各 $i$ について $\Delta_P\subset R_i$ なので $\Delta_P\subset R'$。$I\neq\emptyset$ なので $i\in I$ を一つとると $R'\cap R'^{-1}\subset R_i\cap R_i^{-1}\subset\Delta_P$。$(x,z)\in R'\circ R'$ なら、ある $y$ について $(x,y),(y,z)\in R'$ であり、各 $i$ について $(x,y),(y,z)\in R_i$ なので $(x,z)\in R_i$、よって $(x,z)\in R'$。
(4) $\Delta_{P\times Q}\subset R\times T$ は $\Delta_P\subset R$、$\Delta_Q\subset T$ から従う。$((p,q),(p',q'))$ が $R\times T$ とその逆関係の両方に属すれば $(p,p'),(p',p)\in R$ かつ $(q,q'),(q',q)\in T$ なので $p=p'$、$q=q'$ である。$((p,q),(p'',q''))\in(R\times T)\circ(R\times T)$ なら、ある $(p',q')$ について $(p,p'),(p',p'')\in R$ かつ $(q,q'),(q',q'')\in T$ なので $(p,p'')\in R$、$(q,q'')\in T$ である。
狭義半順序の場合は、$\Delta\subset R$ の代わりに $R\cap\Delta=\emptyset$ を確かめればよく、(1) は $\Delta_P^{-1}=\Delta_P$ から、(2)・(3) は $R|_A\subset R$、$R'\subset R_i$ から、(4) は $((p,q),(p,q))\in R\times T$ なら $(p,p)\in R$ となることから従う。推移律の確認は上と同じである。$\square$

包含関係への埋め込み

$\leq$ を集合 $P$ 上の半順序とし、$x\in P$ に対して $\downarrow x:=\{y\in P\mid y\leq x\}$ とおく。このとき任意の $x,y\in P$ について
$$ x\leq y\iff\ \downarrow x\subset\ \downarrow y $$
が成り立ち、写像 $x\mapsto\ \downarrow x$ は単射である。したがって、任意の半順序は、ある集合の族の上の包含関係と（順序同型で）同一視できる。

$x\leq y$ とし、$z\in\downarrow x$ とすると $z\leq x\leq y$ より $z\leq y$、すなわち $z\in\downarrow y$ である。逆に $\downarrow x\subset\downarrow y$ とすると、反射律から $x\in\downarrow x$ なので $x\in\downarrow y$、すなわち $x\leq y$ である。単射性：$\downarrow x=\downarrow y$ なら $x\leq y$ かつ $y\leq x$ なので反対称律から $x=y$ である。最後の主張は、$\mathcal{F}:=\{\downarrow x\mid x\in P\}$ 上の包含関係が ex-partial-order-inclusion により半順序であり、$x\mapsto\downarrow x$ が $P$ から $\mathcal{F}$ への全単射で、$x\leq y$ と $\downarrow x\subset\downarrow y$ が同値であることによる。$\square$

補足

「順序」「半順序」「半順序集合」の呼び分け

反射律・反対称律・推移律を満たす関係を、全順序と対比する文脈では「半順序」、紛れがなければ単に「順序」と呼ぶ文献が多い（DP02 Chapter 1、Mat68 第3章）。一方で「順序」を全順序の意味に限って用いる文献もあるので、初出の定義を確認する必要がある。本サイトでは、関係そのものを「半順序」または「順序」、それを備えた組 $(P,\leq)$ を「順序集合」または「半順序集合」と呼び、全順序であることは別に明示する。集合論の文献（Jec03 Chapter 2、End77 Chapter 7）では狭義半順序 $<$ を先に定義する流儀が多く、prop-partial-order-strict-bijection により両者は同じ情報を与える。

半順序集合の構造に関する事項の所在

半順序を備えた集合 $(P,\leq)$ に関する次の事項は、本記事では扱わず他の記事に委ねる。最大元・最小元・極大元・極小元・上界・上限の定義と、最大元は一意だが極大元は複数ありうること（たとえば $\{2,3,4,6\}$ に整除関係を入れると $4$ と $6$ が極大元で最大元はない）は順序集合が扱う。有限な半順序集合をHasse図で描けること、および半順序集合と単調写像のなす圏は半順序集合が扱う。$P$ の部分集合で任意の二元が比較可能なものを鎖、相異なる任意の二元が比較不能なものを反鎖といい、任意の鎖が上界を持つ半順序集合には極大元が存在するという Zornの補題は選択公理と同値である（Jec03 Chapter 5）。有限半順序集合を鎖に分割するのに必要な最小個数が反鎖の最大の大きさに等しいというDilworthの定理は Dil50 による（証明は Dil50 に譲る）。

計算機科学での使われ方

作業の依存関係「$A$ が終わらないと $B$ を始められない」は、$A\leq B$ と読めば（自分自身との関係を加えて）半順序である。並行して実行できる作業の組が比較不能な組に対応し、依存を壊さずに作業を一列に並べ直す操作が位相的整列である。半順序を全順序に拡大できることの一般形（順序拡大定理）は全順序が扱う。