前順序
概要
前順序（preorder）とは、集合上の二項関係 $\lesssim$ であって、反射律（$x\lesssim x$）と推移律（$x\lesssim y$ かつ $y\lesssim z$ ならば $x\lesssim z$）を満たすもののことであり、擬順序ともいう。半順序と違って反対称律を要求しないので、整数全体の整除（$2\mid-2$ かつ $-2\mid2$）や年齢による比較のように、互いに相手以下である相異なる元があってよい。互いに相手以下である元を同一視すると半順序が得られ、有向グラフの到達可能性や位相空間の特殊化の前順序もその例である。有限集合の上では、前順序と位相は上方集合を開集合とする対応によって一対一に対応し、半順序は $T_0$ である位相に対応する。
整数どうしを「割り切るかどうか」で比べてみる。$2$ は $6$ を割り切り、$6$ は $12$ を割り切るので、$2$ は $12$ を割り切る。どの整数も自分自身を割り切る。このように「自分と比べられる」「比較を 2 段つなげられる」という 2 つの性質はもつが、$2$ は $-2$ を割り切り、$-2$ も $2$ を割り切るのに $2\neq-2$ である。「互いに相手以下なら同じもの」という性質（反対称律）が欠けているのである。人を年齢で比べるときも同じで、同い年の別人は互いに「相手以下」になる。このように、反射律と推移律だけを満たす比べ方を 前順序 という。互いに相手以下である元をひとまとめにすると、ふつうの半順序が得られる。整数の整除なら $a$ と $-a$ を同一視して、$0$ 以上の整数の整除の半順序になる。3 個の元からなる集合の上の前順序をすべて書き出すと $29$ 個あり、そのうち半順序は $19$ 個である。この $29$ と $19$ は、3 点集合の上の位相空間の位相の個数と、そのうち $T_0$ であるものの個数に一致する（thm-preorder-alexandrov）。
定義
集合 $P$ 上の二項関係 $\lesssim$ が $P$ 上の 前順序（preorder）であるとは、次の 2 条件を満たすことをいう。
- 反射律：任意の $x\in P$ について $x\lesssim x$。
- 推移律：$x\lesssim y$ かつ $y\lesssim z$ ならば $x\lesssim z$。
前順序を 擬順序（quasi-order）ともいう。前順序 $\lesssim$ を備えた集合の組 $(P,\lesssim)$ を 前順序集合 という。前順序 $\lesssim$ について、
- $x\lesssim y$ かつ $y\lesssim x$ であることを $x\sim y$ と書き、$x$ と $y$ は 同値 であるという。
- $x\lesssim y$ であって $y\lesssim x$ でないことを $x< y$ と書き、$\lesssim$ の 狭義部分 という。
反対称律（$x\lesssim y$ かつ $y\lesssim x$ ならば $x=y$）も満たす前順序が半順序である（半順序 の記事の定義「近接する関係の名称」）。前順序では $x\sim y$ でも $x=y$ とは限らない。狭義部分 $<$ を「$x\lesssim y$ かつ $x\neq y$」で定めないのはこのためである（prop-preorder-strict）。
$P$ 上の前順序 $\lesssim$ が 全前順序（total preorder）であるとは、任意の $x,y\in P$ について $x\lesssim y$ または $y\lesssim x$ が成り立つことをいう。
直感
前順序は「どちらが上か」を比べる関係のうち、同点を許すものである。順位表では勝ち点が同じチームが並ぶことがあり、同じ勝ち点のチームは互いに「相手以上」だが同じチームではない。半順序は同点を許さない（同点なら同じもの）比べ方であり、前順序から半順序へ移るには同点の元をひとまとめにすればよい（prop-preorder-quotient-universal）。逆に言えば、前順序は「半順序に、各点の上に同点の元の集まりを載せたもの」とみなせる。有向グラフの「たどり着けるか」、位相空間の点の「どちらが他方の閉包に入るか」のように、比べ方が自然に定まるが同点が避けられない場面で前順序が現れる。
例と反例
整数全体 $\mathbb{Z}$ 上で、$a\mid b$（$b=ac$ となる $c\in\mathbb{Z}$ が存在する）は前順序である。反射律は $a=a\cdot1$ から、推移律は $b=ac$、$d=bc'$ ならば $d=a(cc')$ から従う。$a\sim b$ となるのは $b=\pm a$ のときに限る。実際 $a\mid b$ かつ $b\mid a$ とする。$a=0$ なら $b=0\cdot c=0$ である。$a\neq0$ なら $b=ac$、$a=bd$ から $a=acd$、$cd=1$ となり、$c=\pm1$ である。したがって同値類は $\{a,-a\}$ であり、各類を $|a|$ で代表させると、同値類の集合は $0$ 以上の整数の整除の半順序と同じものになる。この半順序では $0$ が最大である（どの $a$ も $a\mid0$）。
ex-preorder-divisibility の $\mathbb{Z}$ 上の整除は、$2\mid-2$ かつ $-2\mid2$ なのに $2\neq-2$ なので、反対称律を満たさない。満たす性質：反射律と推移律（前順序である）。満たさない性質：反対称律。破る含意：「前順序 $\Rightarrow$ 半順序」は成り立たない。同じ型の反例に、半順序集合 の記事の注意「反例：前順序だが半順序集合でない例（年齢による前順序）」がある。
集合 $X$ から全順序集合 $(T,\leq)$ への写像 $f\colon X\to T$ があるとき、$x\lesssim_f y:\iff f(x)\leq f(y)$ と定めると、$\lesssim_f$ は $X$ 上の全前順序である。反射律・推移律・任意の 2 元の比較可能性は、$T$ の $\leq$ の対応する性質から従う。$x\sim y$ は $f(x)=f(y)$ と同値である。
- 人の集合で $f$ を年齢とする。同い年の人どうしが同値になる。
- 文字列の集合で $f$ を長さとすると、「長さが以下である」という全前順序になる。$\mathtt{01}$ と $\mathtt{10}$ は長さが等しいので同値だが、異なる文字列である（Zac25 Example 2.18、p. 22）。
- 順位表で $f$ を勝ち点とする。同じ勝ち点のチームは同値である。
逆に、どの全前順序もこの形で得られる（prop-preorder-total）。
有向グラフ $D=(V,A)$ で、$u$ から $v$ への有向歩道があること（$v$ が $u$ から到達可能であること、有向グラフ の記事の定義「到達可能性と強連結性」）を $u\rightsquigarrow v$ と書くと、$\rightsquigarrow$ は $V$ 上の前順序である。長さ $0$ の有向歩道が反射律を、有向歩道をつなぐことが推移律を与える。$u\sim v$ は「行き来できる」ことであり、同値類は強連結成分である。$\rightsquigarrow$ は有向辺の関係 $A$ を含む最小の前順序でもある（prop-preorder-closure）。有向辺 $(1,2),(2,1),(2,3)$ をもつ 3 頂点の有向グラフでは、$1\sim2$ で、$\{1,2\}$ と $\{3\}$ が同値類になり、$\{1,2\}$ の元から $3$ へは行けるが戻れない。
集合の族 $\mathcal{S}$ の上で、$A\preceq B$ を「$A$ から $B$ への単射が存在する」と定める。恒等写像は単射なので反射律が、単射の合成は単射なので推移律が成り立ち、$\preceq$ は前順序である。反対称律は成り立たない。$\{1\}\preceq\{2\}$ かつ $\{2\}\preceq\{1\}$ だが $\{1\}\neq\{2\}$ である。$A\sim B$（互いに単射がある）が「$A$ から $B$ への全単射がある」と同値であることは Cantor–Bernsteinの定理 であり（Zac25 Theorem 4.25、p. 66。同書はこの定理を証明なしで述べている）、これにより同値類の集合の上の半順序が「濃度の大小」になる。
位相空間 $X$ の点について、$x\preceq y:\iff x\in\overline{\{y\}}$（$x$ が $\{y\}$ の閉包に属する）と定めた関係を 特殊化の前順序 という。$x\in\overline{\{x\}}$ から反射律が従う。$x\in\overline{\{y\}}$ かつ $y\in\overline{\{z\}}$ なら、$\overline{\{z\}}$ は $y$ を含む閉集合なので $\overline{\{y\}}\subset\overline{\{z\}}$ であり、$x\in\overline{\{z\}}$ となって推移律が従う。閉包の定義から、$x\preceq y$ は「$x$ を含むどの開集合も $y$ を含む」と同値である。T1空間 の記事の注意「特殊化の前順序と $T_0$・$T_1$」が示すとおり、この前順序が等号だけであることは $X$ が $T_1$ であることと同値である。2 点 $\{0,1\}$ に開集合 $\emptyset,\{1\},\{0,1\}$ を入れた Sierpinski空間 では $0\preceq1$ であり、$1\preceq0$ でない。
ほかにも、位相空間の被覆の細分の関係（細分 の記事の命題「細分の関係は前順序」）や、時空の因果的順序（同記事の命題「因果的順序は前順序である」）が前順序の例である。どちらも反対称律は一般に成り立たない。
実数全体 $\mathbb{R}$ 上の関係 $x\approx y:\iff|x-y|\le1$（「差が $1$ 以下」）は反射律を満たすが、$0\approx1$、$1\approx2$ なのに $0\approx2$ でないので推移律を満たさず、前順序でない。満たす性質：反射律。満たさない性質：推移律。「近い」を 2 回つないでも「近い」とは限らないので、「近さ」の関係は一般に前順序にならない。この関係を含む最小の前順序は $\mathbb{R}\times\mathbb{R}$ 全体（どの 2 点も差 $1$ 以下の点を順につないで結べる）であり、prop-preorder-closure で閉包をとると区別がすべて失われる。
性質
半順序への商
$(P,\lesssim)$ を前順序集合とする。
1 は 半順序 の記事の命題「前順序から半順序を作る商」である。
2：$[x]\leq[y]$ の定義が $x\lesssim y$ そのものなので、$x\lesssim y\iff q(x)\leq q(y)$ であり、特に $q$ は単調である。
3：一意性：$\bar f\circ q=f$ なら $\bar f([x])=f(x)$ でなければならないので、$\bar f$ は $f$ で決まる。存在：$\bar f([x]):=f(x)$ と定める。$x\sim x'$ なら $x\lesssim x'$ かつ $x'\lesssim x$ なので、$f$ の単調性から $f(x)\leq_Q f(x')$ かつ $f(x')\leq_Q f(x)$ であり、$\leq_Q$ の反対称律により $f(x)=f(x')$ である。したがって $\bar f$ は代表元によらずに定まる。$[x]\leq[y]$ なら $x\lesssim y$ なので $\bar f([x])=f(x)\leq_Q f(y)=\bar f([y])$ であり、$\bar f$ は単調である。$\square$
3 の $Q$ が半順序集合であることは欠かせない。$Q$ が前順序集合なら、同値な 2 元を $Q$ の同値な別々の元へ送る単調写像は $q$ を通して分解できない。たとえば $P=Q=\{a,b\}$ にすべての組を関係とする前順序（どの 2 元も同値）を入れ、$f$ を恒等写像とすると、$P/{\sim}$ は 1 点なので $\bar f$ の値は 1 つしかなく、$f(a)\neq f(b)$ を実現できない。
前順序 $\lesssim$ の狭義部分 $<$（$x\lesssim y$ であって $y\lesssim x$ でない）は、非反射的かつ推移的であり、$x< y\iff[x]<[y]$（$P/{\sim}$ の半順序の狭義部分）を満たす。一方、関係「$x\lesssim y$ かつ $x\neq y$」は、$\lesssim$ が半順序でなければ推移的とは限らない。
$x< x$ なら $x\lesssim x$ でないことになり反射律に反するので、$<$ は非反射的である。$x< y$、$y< z$ とすると $x\lesssim z$ である。もし $z\lesssim x$ なら $y\lesssim z\lesssim x$ から $y\lesssim x$ となり、$x< y$ に反する。よって $x< z$ である。$[x]<[y]$ は「$[x]\leq[y]$ かつ $[x]\neq[y]$」、すなわち「$x\lesssim y$ かつ $x\not\sim y$」であり、$x\lesssim y$ のもとで $x\not\sim y$ は「$y\lesssim x$ でない」と同値なので、$x< y$ と同値である。
後半：$\{a,b\}$（$a\neq b$）上のすべての組を関係とする前順序では、$a\lesssim b$ かつ $a\neq b$、$b\lesssim a$ かつ $b\neq a$ だが、「$a\lesssim a$ かつ $a\neq a$」は成り立たないので、この関係は推移的でない。$\square$
前順序集合 $(P,\lesssim)$ について、次は同値である。
- $\lesssim$ は全前順序である。
- $P/{\sim}$ の半順序は全順序である。
- ある全順序集合 $(T,\leq)$ と写像 $f\colon P\to T$ があって、任意の $x,y$ で $x\lesssim y\iff f(x)\leq f(y)$ となる。
1 ⇒ 2：$[x],[y]$ について $x\lesssim y$ または $y\lesssim x$ なので $[x]\leq[y]$ または $[y]\leq[x]$ である。2 ⇒ 3：$T:=P/{\sim}$、$f:=q$ とすればよい（prop-preorder-quotient-universal の 2）。3 ⇒ 1：$f(x)\leq f(y)$ または $f(y)\leq f(x)$ なので $x\lesssim y$ または $y\lesssim x$ である。$\square$
関係から前順序を作る
$R$ を集合 $X$ 上の二項関係とする。$x\,R^{*}\,y$ を「$n\ge0$ と $x_0,x_1,\dots,x_n\in X$ があって、$x_0=x$、$x_n=y$、各 $i=1,\dots,n$ で $x_{i-1}\,R\,x_i$」と定める（$n=0$ のときは $x=y$）。このとき $R^{*}$ は $R$ を含む前順序であり、$R$ を含む任意の前順序 $\lesssim$ について $R^{*}\subset\lesssim$ である。すなわち $R^{*}$ は $R$ を含む最小の前順序（反射推移閉包）である。
$n=0$ の鎖により $x\,R^{*}\,x$ であり、$n=1$ の鎖により $R\subset R^{*}$ である。$x\,R^{*}\,y$ を与える鎖 $x=x_0,\dots,x_n=y$ と $y\,R^{*}\,z$ を与える鎖 $y=y_0,\dots,y_m=z$ をつないだ $x_0,\dots,x_n=y_0,y_1,\dots,y_m$ は $x$ から $z$ への長さ $n+m$ の鎖なので、$x\,R^{*}\,z$ である。よって $R^{*}$ は前順序である。
$\lesssim$ を $R$ を含む前順序とし、$x\,R^{*}\,y$ を長さ $n$ の鎖で与える。$n$ に関する数学的帰納法で $x\lesssim y$ を示す。$n=0$ なら $x=y$ で反射律による。$n\ge1$ なら、長さ $n-1$ の鎖 $x_0,\dots,x_{n-1}$ により帰納法の仮定から $x\lesssim x_{n-1}$ であり、$x_{n-1}\,R\,y$ から $x_{n-1}\lesssim y$ なので、推移律により $x\lesssim y$ である。$\square$
ex-preorder-reachability の到達可能性 $\rightsquigarrow$ は、有向辺の関係 $A$ の反射推移閉包 $A^{*}$ そのものである（鎖 $x_0,\dots,x_n$ が有向歩道にあたる）。前順序を与えるには、生成する関係 $R$ だけを与えればよい。有限集合の上なら、$R$ を有向グラフとして描いて到達可能性を読めば $R^{*}$ が分かる。
位相との対応
前順序集合 $(X,\lesssim)$ の部分集合 $U$ が 上方集合（上方集合）であるとは、$x\in U$ かつ $x\lesssim y$ ならば $y\in U$ となることをいう。$x\in X$ について $\uparrow x:=\{y\in X\mid x\lesssim y\}$ とおく。
$X$ を集合とする。
- $X$ 上の前順序 $\lesssim$ について、上方集合全体 $\tau_{\lesssim}$ は $X$ 上の位相であり、任意個の共通部分でも閉じている。この位相の特殊化の前順序（ex-preorder-specialization）は $\lesssim$ に一致する。
- $X$ が有限集合なら、$X$ 上の任意の位相 $\tau$ は、その特殊化の前順序 $\preceq_\tau$ の上方集合全体に一致する：$\tau=\tau_{\preceq_\tau}$。
- したがって $X$ が有限なら、$\lesssim\ \mapsto\tau_{\lesssim}$ と $\tau\mapsto\ \preceq_\tau$ は、$X$ 上の前順序全体と $X$ 上の位相全体の間の互いに逆な全単射である。この対応で、半順序は $T_0$ である位相（相異なる 2 点について、一方だけを含む開集合があるもの）に対応する。
位相 $\tau_{\lesssim}$ を $\lesssim$ の Alexandrov位相 という。
1：上方集合の族 $\{U_\lambda\}$ について、$x\in\bigcup U_\lambda$（または $x\in\bigcap U_\lambda$）かつ $x\lesssim y$ なら、$x$ を含む各 $U_\lambda$（または全部の $U_\lambda$）が $y$ を含むので、和集合も共通部分も上方集合である。$\emptyset$ と $X$ は上方集合なので、$\tau_{\lesssim}$ は位相である。推移律により $\uparrow x$ は上方集合であり、反射律により $x\in\uparrow x$ である。$x$ を含む上方集合は $\uparrow x$ を含むので、$\uparrow x$ は $x$ を含む最小の開集合である。特殊化の前順序 $\preceq$ について、$x\preceq y$ は「$x$ を含むどの開集合も $y$ を含む」ことであり、最小の開集合 $\uparrow x$ を考えれば、これは $y\in\uparrow x$、すなわち $x\lesssim y$ と同値である。
2：$U\in\tau$、$x\in U$、$x\preceq_\tau y$ とすると、$x$ を含む開集合 $U$ は $y$ を含むので、$U$ は上方集合である。逆に $A$ を $\preceq_\tau$ の上方集合とする。$X$ が有限なので $\tau$ も有限であり、$x$ を含む開集合全体の共通部分 $U_x$ は有限個の開集合の共通部分として開集合である。$y\in U_x$ は「$x$ を含むどの開集合も $y$ を含む」、すなわち $x\preceq_\tau y$ と同値なので、$U_x=\uparrow x$ である。$A$ は上方集合なので $x\in A$ なら $U_x\subset A$ であり、$A=\bigcup_{x\in A}U_x$ は開集合である。
3：1 により $\preceq_{\tau_{\lesssim}}=\lesssim$、2 により $\tau_{\preceq_\tau}=\tau$ なので、2 つの写像は互いに逆である。最後の主張：$x\preceq_\tau y$ かつ $y\preceq_\tau x$ は「$x$ を含む開集合はすべて $y$ を含み、$y$ を含む開集合はすべて $x$ を含む」、すなわち「$x,y$ の一方だけを含む開集合がない」ことである。よって $\preceq_\tau$ が反対称律を満たすことは、$\tau$ が $T_0$ であることと同値である。$\square$
この定理により、3 点集合の上の位相の個数は 3 点集合の上の前順序の個数 $29$ に等しく、$T_0$ である位相の個数は半順序の個数 $19$ に等しい（4 点集合ではそれぞれ $355$ と $219$）。有限な位相空間は、有限な前順序集合と同じ情報をもつ。Sierpinski空間 の記事の補足も同じ見方を述べている。
$\mathbb{R}$ にふつうの位相を入れると、1 点集合は閉集合なので $\overline{\{y\}}=\{y\}$ であり、特殊化の前順序は等号だけである。等号の上方集合はすべての部分集合なので、$\tau_{\preceq}$ は離散位相であり、ふつうの位相（$\{0\}$ は開集合でない）と異なる。ふつうの位相と離散位相は同じ特殊化の前順序（等号）をもつので、無限集合の上では $\tau\mapsto\ \preceq_\tau$ は単射でない。満たす性質：$\tau$ は位相である。満たさない性質：$\tau=\tau_{\preceq_\tau}$。破る含意：thm-preorder-alexandrov の 2 は「有限」の仮定を外すと成り立たない。証明で有限性を使ったのは、$x$ を含む開集合全体の共通部分が開集合になるところである。
- 位相空間の間の連続写像 $f\colon X\to Y$ は、特殊化の前順序について単調である。
- $X,Y$ に前順序 $\lesssim_X,\lesssim_Y$ の Alexandrov 位相を入れる（$X,Y$ は無限でもよい）。写像 $f\colon X\to Y$ が連続であることと、$f$ が $\lesssim_X,\lesssim_Y$ について単調であることは同値である。
1：$x\in\overline{\{y\}}$ とする。$f$ は連続なので $f^{-1}\bigl(\overline{\{f(y)\}}\bigr)$ は $y$ を含む閉集合であり、$\overline{\{y\}}$ を含む。よって $f(x)\in\overline{\{f(y)\}}$ である。
2：thm-preorder-alexandrov の 1 により、Alexandrov 位相の特殊化の前順序はもとの前順序なので、1 から「連続 ⇒ 単調」が従う。逆に $f$ が単調で $V\subset Y$ が上方集合なら、$x\in f^{-1}(V)$、$x\lesssim_X x'$ のとき $f(x)\lesssim_Y f(x')$ なので $f(x')\in V$ であり、$f^{-1}(V)$ は上方集合、すなわち開集合である。$\square$
補足
前順序集合 $(P,\lesssim)$ は、$x\lesssim y$ のときだけ $x$ から $y$ への射をちょうど 1 本置いた圏とみなせる。反射律が恒等射を、推移律が射の合成を与える（圏 の記事の例「前順序」）。逆に、どの 2 対象の間にも射が高々 1 本しかない圏は、「射がある」という関係によって対象の上の前順序を定める。この見方で、単調写像は関手にあたり（射の有無を保つことが単調性そのもの）、同値な元は圏の中で同型な対象にあたる。prop-preorder-quotient-universal の商 $P/{\sim}$ は、同型な対象を 1 つにまとめる操作である。
反射律と推移律を満たす関係を preorder と呼ぶ定義は Zac25 Definition 2.14（p. 22）にあり、同書は続けて反対称律を加えたものを partial order、さらに任意の 2 元が比較できるものを total order と呼んでいる。日本語では前順序のほか擬順序ともいう。強制法では、最大元をもつ擬順序を強制概念と呼ぶ（強制概念）。前順序の記号には $\lesssim$ や $\preceq$ がよく使われ、半順序の $\leq$ と区別することが多い。空でない前順序集合で、任意の 2 元が共通の上界をもつものが有向集合であり、極限やネットの添字に使われる。用語と記号は文献によって揺れるので、初出の定義を確かめる必要がある。
関連項目
- 前提: 二項関係, 半順序, 同値関係, 位相空間
- 比較: 全順序, 半順序集合, 有向集合
- 直後に読む: 有向グラフ, T1空間, Sierpinski空間
- 発展: 圏, Alexandrov位相, Cantor–Bernsteinの定理
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
