順序集合
Contents
順序集合
順序集合 (英：ordered set) とは、順序的構造が与えられた集合のこと。二項関係に複数の規則を加えることで順序の概念が与えられる。また各規則の有無により次表のように順序的構造が定義される。順序の概念が与えられた二項関係は順序関係 (英：order relation) と呼ばれ、しばしば $\preccurlyeq$ で表される。
| 順序集合 | 反射性 | 推移性 | 反対称性 | 比較可能性 |
|---|---|---|---|---|
| 前順序集合 | ◯ | ◯ | - | - |
| 半順序集合 | ◯ | ◯ | ◯ | - |
| 全順序集合 | ◯ | ◯ | ◯ | ◯ |
前順序集合
前順序集合 (英：preordered set) とは、下記の性質を満たす数学的構造 $(U,\preccurlyeq)$ のこと。前順序集合の順序関係を前順序 (英：preorder) と呼ぶ。
\[ \begin{aligned} \text{(OA1)} &: \forall a \in U, ~ a\preccurlyeq a \cr \text{(OA2)} &: \forall a,b,c \in U, ~ a\preccurlyeq b\land b\preccurlyeq c \rArr a\preccurlyeq c \end{aligned} \]
- $\text{(OA1)}$ - 反射性 (英：reflexivity)
ある元 $a$ に関係 $R$ が定められているとき、$aRa$ であるという性質。 - $\text{(OA2)}$ - 推移性 (英：transitivity)
ある元 $a,b,c$ に関係 $R$ が定められているとき、$aRb$ かつ $bRc$ ならば $aRc$ であるという性質。
半順序集合
半順序集合 (英：partially ordered set) とは、下記の性質を満たす前順序集合 $(U,\preccurlyeq)$ のこと。半順序集合の順序関係を半順序 (英：partially order) と呼ぶ。
\[ \begin{aligned} \text{(OA3)} &: \forall a,b \in U, ~ a\preccurlyeq b \land b\preccurlyeq a \rArr a = b \end{aligned} \]
- $\text{(OA3)}$ - 反対称性 (英：antisymmetry)
ある元 $a,b$ に関係 $R$ が定められているとき、$aRb$ かつ $bRa$ ならば $a$ と $b$ が等しいという性質。
全順序集合
全順序集合 (英：totally ordered set) とは、下記の性質を満たす半順序集合 $(U,\preccurlyeq)$ のこと。全順序集合の順序関係を全順序 (英：total order) と呼ぶ。
\[ \begin{aligned} \text{(OA4)} &: \forall a,b\in U, ~ a\preccurlyeq b \lor b\preccurlyeq a \end{aligned} \]
- $\text{(OA4)}$ - 比較可能性 (英：comparability)
集合 $U$ の全ての元の間で関係 $R$ が成り立つという規則。
整列集合
整列集合 (英：well-ordered set) とは、最小元を持つ全順序集合 $(U,\preccurlyeq)$ のこと。このとき整列集合の順序関係を整列順序 (英：well-order) という。