📂集合論

부분순서 집합

定義 ¹

1. 集合 $A$ においての 関係 $\le$ が反射的、推移的、反対称的であるならば、$\le$ を 部分順序^{partial order} とし、$(A,\le)$ を 部分順序集合^{partial ordered set} と呼ぶ。つまり、$A$ が部分順序集合であるということは、すべての要素 $a,b,c \in A$ に対して次が満たされることを指す： $$\begin{align*} a \le a & \text{ (reflexivity) } \\ a \le b \land b \le c \implies a \le c & \text{ (transitivity) } \\ a \le b \land b \le a \implies a = b & \text{ (antisymmetry) } \end{align*}$$
2. 部分順序集合 $(A, \le)$ が与えられているとき、すべての $a,b \in A$ に対し $a \le b$ または $b \le a$ なら、$\le$ を $A$ における 全順序^{total order}、$(A,\le)$ を 全順序集合^{totally ordered set} とする。

説明

部分順序（集合）は反順序（集合）とも翻訳される。部分順序の表記としては $\preceq$^\preceq も使用される。

定義での $\le$ は単に記号であり、必ずしも大小を比較する不等号である必要はない。当然、不等号や包含関係は部分順序になり得るが、その逆は成り立たない。一例として、アルファベットでは a の次は b であり、単に記号を用いれば $a \le b$ として表示しても問題ない。実際、コンピュータサイエンスでは a はアスキーコード $0000001_{(2)}$ に対応し、b はアスキーコード $00000010_{(2)}$ に対応しており、これらの2進数の大小関係で文字間の順序も示せる。

実のところ、全順序集合は義務教育を受けた人なら馴染み深く思い出せるものであり、むしろそれ以外の集合はすぐには思い浮かばないかもしれない。全順序集合の良い例としては、自然数 の集合 $\mathbb{N}$ であり、これは 整数 の集合 $\mathbb{Z}$、有理数の集合 $\mathbb{Q}$、実数 の集合 $\mathbb{R}$ とも同様である。しかし一歩進んで 複素数 $\mathbb{C}$ になると、自然な順序は特には定義されていない。

全順序を定義する前に部分順序を定義することは、数学的に非常に自然であるからだ。次のような5つの集合 $$\begin{align*} A &= \left\{ 1 \right\} \\ B &= \left\{ 1,2 \right\} \\ C &= \left\{ 1,3 \right\} \\ D &= \left\{ 1,2,3 \right\}\\ E &= \left\{ 1,2,4 \right\} \end{align*}$$ について 集合の包含関係 を考えてみると、次のことが成り立つと確認できる。 $$A \subset B \subset D \\ A \subset B \subset E \\ A \subset C \subset D$$ 図から見ると、この複雑な形状を一目で確認できる。

または他の例として、次のような6つの集合について見ると、 $$\begin{align*} A^{\prime} &= \left\{ 1 \right\} \\ B^{\prime} &= \left\{ 1,2 \right\} \\ C^{\prime} &= \left\{ 1,3 \right\} \\ D^{\prime} &= \left\{ 1,2,4 \right\}\\ E^{\prime} &= \left\{ 5 \right\}\\ F^{\prime} &= \left\{ 2, 5 \right\} \end{align*}$$ $$A^{\prime} \subset B^{\prime} \subset D^{\prime} \\ A^{\prime} \subset C^{\prime} \\ E^{\prime} \subset F^{\prime}$$ 図では次のようになる。

実際、このような非線形的形式は日常においてもよく見られるような自然な関係を表している。改めて考えてみると、むしろ全てが線形的に連鎖している関係がおかしいかもしれない。さらには フォン・ノイマンの構成法 による『直感的』という表現からも少し距離のある自然数の集合 $\mathbb{N}$ にさえそうである。なので全順序は単に部分順序が集合全体で線形的に定義される関係として話す方が便利であるかもしれない。