数学: 順序の例: ていへんかけるたかさわるに

数学: 順序の例

定義.$X$ を集合とし, $\le$ を $X$ 上の 2 項関係とする. $a, b, c$ を $X$ の任意の元とする.
I. $\le$ が以下を満たすとき 前順序 (preorder)と呼ぶ:
(i) $a \le a$ (反射率);
(ii) $a \le b$ かつ $b \le c$ ならば $a \le c$ (推移律).

II. $\le$ が以下を満たすとき 半順序 (partial order)と呼ぶ.
(i) $a \le a$ (反射率);
(ii) $a \le b$ かつ $b \le c$ ならば $a \le c$ (推移律);
(iii) $a \le b$ かつ $b \le a$ ならば $a = b$ (反対称律).

III. $\le$ が以下を満たすとき 全順序 (total order)と呼ぶ:
(i) $a \le a$ (反射率);
(ii) $a \le b$ かつ $b \le c$ ならば $a \le c$ (推移律);
(iii) $a \le b$ かつ $b \le a$ ならば $a = b$ (反対称律);
(iv) $a \le b$ または $b \le a$ (完全律).

※: Wikipedia より引用.

$P$ を整数全体の集合 $\mathbb{Z}$ の有限部分集合を元とする集合とする. つまり
\begin{equation*}
P = \left\{\, x \mid x \subset \mathbb{Z},\, x \,\text{は有限集合} \,\right\}
\end{equation*}
$P$ にいろいろな順序を入れてどのような順序集合になるかを見てみた.

(1) $x, y \in P$ に対して $x \subset y$ ならば $x \le_1 y$ と表わす. $\le_1$ は前順序であり半順序であるが, 完全律を満たさないので全順序ではない.
(2) $x, y \in P$ に対して単射 $x \hookrightarrow y$ が存在するならば $x \le_2 y$ と表わす. $\le_2$ は前順序であり完全律を満たすが反対称律を満たさないので半順序ではなく, よって全順序でもない.
(3) 有限集合 $x \in P$ の要素の数を $\mathrm{card}(x)$ で表わすことにする. $x, y \in P$ に対して $\mathrm{card}(x) \le \mathrm{card}(y)$ のとき $x \le_3 y$ と表わす. $\le_3$ は前順序であり完全律を満たすが反対称律を満たさないので半順序ではなく, よって全順序でもない.
(4) $\mathrm{card}(x)$ の値は非負整数となる. ここで $x$ に対して
\begin{equation*}
m(x) = \begin{cases}
\tan\left(\dfrac{\mathrm{card}(x)\cdot\pi}{4}\right) & (\mathrm{card}(x) \neq 4n+2 \,(n=0,1,2,...)), \\
\text{不定} & (\mathrm{card}(x) = 4n+2 \,(n=0,1,2,...))
\end{cases}
\end{equation*}
と定義する. $x, y \in P$ に対して $m(x)$, $m(y)$ が共に不定でなく, かつ $m(x) \le m(y)$ のとき $x \le_4 y$ と表わす. $x \in P$ に対して $m(x)$ が不定のとき $x \le_4 x$ と表わす. $\le_4$ は前順序だが反対称律と完全律を満たさないので半順序でも全順序でもない.
(5) 素数を小さな方から順に並べて数列 $\left\{\, p_i \,\right\} \,(i=1,2,...)$ を作る. $p_1=2,\, p_2=3,\, p_3=5,\, p_4=7,...$ である. $x \in P$ に対して, $x$ の元を小さい方から順に並べた結果を
\begin{equation*}
x = \left\{\, a_1, a_2, a_3,..., a_n \,\right\} \quad (n = \mathrm{card}(x))
\end{equation*}
とし, これを用いて
\begin{equation*}
m(x) = {p_1}^{a_1}{p_2}^{a_2}\cdots{p_n}^{a_n}
\end{equation*}
と定義する. $x, y \in P$ に対して, $m(x) \le m(y)$ のとき, $x \le_5 y$ と表わす. $\le_5$ は全順序である.