全順序・半順序・擬順序

概要

　数学では様々な順序を考えることがあります. 一番簡単な例で言うと実数の全体 $\mathbb{R}$ において, $x,y\in \mathbb{R}$に対し$y-x\geq 0$ を $x\leq y$と定義して順序集合$(\mathbb{R},\leq)$を考えることが多いです. 実数だけではなく, 例えばグラフ理論でも順序を考えたりすることがあります.
　本記事では, 順序の公理について述べ, 全順序・半順序・擬順序について一気に述べたのちに例を幾つか挙げたいと思います.

解説単語 : 擬順序(前順序), 半順序, 全順序

順序の定義

　集合 $E$ (有限でも無限でもよい) に対し, $R: E\times E \to \{0,1\}$ を 関係 と呼びます. 特に, $R(x,y)=1$となるときは $x R y$と書くことがあります. 例えば $E=\mathbb{R}$, 関係$R$ として 「$\leq$」 を考えるとこれは大小関係を表す関係になっています. また, 「$=$」 という関係も考えることが出来ます. これは等号の関係です. このように見ると, 関係というのは非常に抽象的なもので, 表現力が非常に高いものだということが分かると思います.

　関係 $R$ が, 集合 $E$ に対していわゆる「順序」を付与するような関係である(即ち大小関係を決定するような関係である)ならば, そのことを強調するために $R$を順序と呼び, $\leq$ などと記述します. そして組 $(E, \leq)$ のことを 順序集合と呼びます.

　順序 $\leq$ として, 次の性質を満たすものを考えましょう:

1. 任意の $a \in E$ に対して $a \leq a$ (反射律)
2. $a,b,c \in E$ が, $a\leq b$, $b \leq c$ ならば $a \leq c$である (推移律)
3. $a,b \in E$ が $a \leq b$, $b \leq a$ ならば $a=b$ である (反対称律)
4. 任意の $a,b\in E$ に対して $a \leq b$ もしくは $b \leq a$ のどちらかが必ず成り立つ (全順序律)

　例えば 実数における通常の順序を考えると1～4の全てを満たしていることが用意に分かります. このように, これら全ての条件を満たすような順序 $\leq$ を特に 全順序 (totally order) と呼び, 全順序$\leq$ に対して $(E, \leq)$ を 全順序集合 (partially ordered set) と呼びます. また, 1~3を満たすものは 半順序 (partially order) と呼び, 1と2を満たすものは 擬順序 (quasi order) と呼ばれます.

　まとめると

• 全順序 : 1~4 を満たす
• 半順序 : 1~3 を満たす
• 擬順序 : 1~2 を満たす

です. 注意されたいのは, 全順序は半順序でもあり, 擬順序でもあるということです. 

　さて, これらの三つの順序の概念について, 幾つかの例を挙げながら見ていきましょう.

例(i). 集合の包含関係

　$U$を空でない集合とし, $E=2^U$ としましょう. 即ち $E$ は$U$の部分集合族です. このとき, $A, B\in E$ はそれぞれ$U$の部分集合となっています. そして $A \subseteq B$ ならば $A \leq B$ と定義しましょう. さて, $(E,\leq )$ はどんな順序集合になっているでしょうか？

　例として $U=\{1,2,3,4,5\}$ としてみます. $A = \{1,2,3\},\,B=\{1,2,3,4\}$ のときは $A \leq B$ となりますが, $A=\{1,2,3\},\,B=\{2,3,4\}$のときは $A\leq B$ でも $B \leq A$ でもありません. 順序の公理のうち, 4だけが満たされないので, この順序は半順序となります. ちなみに $A \leq B$ でも $B \leq A$ でもない組$(A,B)$ のことを 比較不能対 と呼びます.

例(ii). ビッグオー

　$E$ として, 自然数から正実数への関数の全体 としましょう. すなわち $E := \mathbb{N}^{\mathbb{R}_{>}}$ とします. そして, $f, g\in E$ に対して, $f(n)=O(g(n))$ のときに $f\leq g$ と定義します.

　即ち, ある $m \in \mathbb{N}$ 及び 定数 $c>0$ が存在して, 任意の $n \geq m$ に対して $f(n) \leq c \cdot g(n)$ が成り立つ, というときに $f \leq g$ と書くのです.

　オーダーによって定められたこの関係$\leq$ は,

1. $f(n) = O(f(n))$ より, $f \leq f$ (反射律)
2. $f(n) = O(g(n)),\,g(n)=O(h(n))$ ならば, それぞれの定数を$m_1,c_1,m_2,c_2$ としたときに $m=max(m_1,m_2)$, $c=c_1 \cdot c_2$ ととれば, 任意の $n \geq m$ に対し $f(n) \leq c_1 \cdot g(n) \leq c_1 c_2 \cdot h(n)$ となるので, $f \leq h$ (推移律)

　となるので, 擬順序となっています. 更に, $f(n)=n^2,\,g(n)=n^2+1$ と定義すると, $f \neq g$ でありしかも $f \leq g$ かつ $g \leq f$ となっているため, 条件3を満たしません. 即ちこれは 擬順序だが半順序でない例 になっているわけです.

例(iii). 確率変数

　確率空間 $(\Omega,\,\mathcal{F},\,P)$ 上の二つの確率変数 $X,Y:\Omega \to \mathbb{R}$ が

任意の $x \in \mathbb{R}$ に対して $\mathrm{Pr}(X \geq x) \leq \mathrm{Pr}(Y \geq x)$

を満たすとき, $X \leq Y$ と定義します. (ちなみにこのとき $Y$ は $X$ を支配する (dominate) と言います)

　気持ちとしては 「$X\geq x$ となる確率よりも $Y \geq x$ となる確率の方が高い」ということなので, 「$X$ よりも $Y$ の方が 大きい値をとりやすい」ということになります. 例えば「表の出る確率が0.5 のコインを $n$ 回投げて, 表が出た回数」を $X$, 「表の出る確率が 0.7 のコインを $n$ 回投げて, 表が出た回数」を $Y$ とすると, 明らかに$Y$のコインの方が表が出やすいので, 直感的には $X \leq Y$ な気がしてきます. (実際にこれは確率論で使われる「カップリング」と呼ばれるテクニックを用いて鮮やかに示すことが出来ます)

1. $\mathrm{Pr}(X \geq x) = \mathrm{Pr}(X \geq x)$ なので, $X \leq X$.
2. 任意の$x,y\in \mathbb{R}$ に対して, $\mathrm{Pr}(X \geq x) \leq \mathrm{Pr}(Y \geq x)$, $\mathrm{Pr}(X \geq y) \geq \mathrm{Pr}(Y \geq y)$ ならば, 任意の$z \in \mathbb{R}$に対して $\mathrm{Pr}(X \geq z) \leq \mathrm{Pr}(Y \geq z) \leq \mathrm{Pr}(Z \geq z)$ となるので, 推移律も成り立ちます.

　一方で, 例えば「確率0.5で表が出るコインを $2n$ 回投げたとき, 前半の$n$回の中で表が出た回数を $X$, 後半の$n$回の中で表が出た回数を $Y$」としてみると, $X$と$Y$は同じ分布に従うので$X \leq Y$かつ$Y \leq X$なのですが, 確率変数としては異なるので, $X \neq Y$です(*).

(*): 「確率変数として異なる」という部分を細かく議論します. 確率変数とは $\Omega$ から 実数 への$\mathcal{F}$-可測写像なので, $X=Y$ ということは 任意の $\omega \in \Omega$ に対して$X(\omega)=Y(\omega)$ ということを意味しています. 今回のコイントスの例では標本集合$\Omega$を $\Omega = \{0,1\}^{2n}$ として, σ-集合体を $\mathcal{F}=2^{\Omega}$ として, 確率測度$P$を$\Omega$上の一様分布とします. (つまり任意の $\omega \in \Omega$ に対し $P(\omega)=1/2^{2n}$). そして $\omega = \{\omega_1,\omega_2,\ldots,\omega_{2n}\}\in \{0,1\}^{2n}$ に対して, $X(\omega)=\omega_1+\omega_2+\cdots+\omega_n$, $Y(\omega)=\omega_{n+1}+\omega_{n+2}+\cdots+\omega_{2n}$ と定義します. すると $X, Y$ はコイントスの例と同じ分布に従うような確率変数となっていて, 明らかに $X\neq Y$ となっています.

例(iv). 有向グラフ

　有向グラフ $G$ 上の 2頂点 $a,b$ で, $b$ から $a$ への有向パスが存在するとき, $a \leq b$ と定義します. 

1. $a$ から $a$ へは長さ0のパスがあると見なすので, $a \leq a$ です.
2. $a \leq b,\,b \leq c$ ならば, $c$ から $b$ をつたって $a$ にいたるパスがあるので, $a \leq c$ となります.

　従ってこの順序関係は 擬順序 となります. 更に, $G$ が DAG の場合は条件3も満たすので, 半順序となります. 更に$G$のトポロジカル順序が一意の場合は, 条件4も満たすので全順序となります.