半順序集合と狭義半順序集合の関係

by nomura · 2023年10月6日

半順序集合と狭義半順序集合の関係

(1)

半順序集合$\left(X,\preceq\right)$があるとき、$a\prec b\Leftrightarrow a\preceq b\land a\ne b$と定めると、$\left(X,\prec\right)$は狭義半順序集合となる。

(2)

狭義半順序集合$\left(X,\prec\right)$があるとき、$a\preceq b\Leftrightarrow a\prec b\lor a=b$と定めると、$\left(X,\preceq\right)$は半順序集合となる。

(3)

全順序集合$\left(X,\preceq\right)$があるとき、$a\prec b\Leftrightarrow a\preceq b\land a\ne b$とすると、$\left(X,\prec\right)$は狭義全順序集合となる。

(4)

狭義全順序集合$\left(X,\prec\right)$があるとき、$a\preceq b\Leftrightarrow a\prec b\lor a=b$とすると、$\left(X,\preceq\right)$は全順序集合となる。

(5)

半順序集合$\left(X,\preceq\right)$が完全律を満たさないとき、$a\prec b\Leftrightarrow a\preceq b\land a\ne b$と定めると、$\left(X,\prec\right)$は3分律を満たさない。

(6)

狭義半順序集合$\left(X,\prec\right)$が3分律を満たさないとき、$a\preceq b\Leftrightarrow a\prec b\lor a=b$と定めると、$\left(X,\preceq\right)$は完全律を満たさない。

(1)は狭義半順序集合(非反射律・推移律)を満たすので非対称律も満たす。
なぜなら
\begin{align*} x\prec y\rightarrow\lnot\left(y\prec x\right) & \Leftrightarrow\lnot\left(x\prec y\right)\lor\lnot\left(y\prec x\right)\\ & \Leftrightarrow\lnot\left(x\prec y\land y\prec x\right)\\ & \Leftrightarrow\lnot\left(x\preceq y\land x\ne y\land y\preceq x\land y\ne x\right)\\ & \Leftrightarrow\lnot\left(x=y\land x\ne y\right)\\ & \Leftrightarrow\top \end{align*} となるからである。

(1)

非反射律

\begin{align*} x\prec x & \Leftrightarrow x\preceq x\land x\ne x\\ & \Leftrightarrow x\preceq x\land\bot\\ & \Leftrightarrow\bot \end{align*} となるので、狭義順序$\prec$は非反射律を満たす。

推移律

\begin{align*} x\prec y\land y\prec z & \Leftrightarrow x\preceq y\land x\ne y\land y\preceq z\land y\ne z\\ & \Rightarrow x\preceq y\land y\preceq z\land x\ne z\\ & \Rightarrow x\preceq z\land x\ne z\\ & \Leftrightarrow x\prec z \end{align*} 途中で$x=z$と仮定すると、$x\preceq y\land x\ne y\land y\preceq z\land y\ne z\Rightarrow x\preceq y\land y\preceq z\land x=z\Leftrightarrow x\preceq y\land y\preceq x\land x=z\Leftrightarrow x=y\land x=z$となり、$x\prec y$に矛盾するので$x\ne z$となることを使った。
これより、狭義順序$\prec$は推移律を満たす。

-

これらより、非反射律・推移律を満たすので$\left(X,\prec\right)$は狭義半順序関係を満たす。

(2)

反射律

\begin{align*} x\preceq x & \Leftrightarrow x\prec x\lor x=x\\ & \Leftrightarrow\bot\lor\top\\ & \Leftrightarrow\top \end{align*} となるので半順序$\preceq$は反射律を満たす。

反対称律

\begin{align*} x\preceq y\land y\preceq x & \Leftrightarrow\left(x\prec y\lor x=y\right)\land\left(y\prec x\lor y=x\right)\\ & \Leftrightarrow\left(x\prec y\land y\prec x\right)\lor x=y\\ & \Leftrightarrow x=y \end{align*} となるので半順序$\preceq$は反対称律を満たす。

推移律

\begin{align*} x\preceq y\land y\preceq z & \Leftrightarrow\left(x\prec y\lor x=y\right)\land\left(y\prec z\lor y=z\right)\\ & \Rightarrow\left(x\prec y\land y\prec z\right)\lor\left(x=y\land y=z\right)\\ & \Rightarrow x\prec z\lor x=z\\ & \Leftrightarrow x\preceq z \end{align*} となるので半順序$\preceq$は推移律を満たす。

-

これらより、反射律・反対称律・推移律を満たすので$\left(X,\preceq\right)$は半順序関係を満たす。

(3)

全順序集合$\left(X,\preceq\right)$は半順序関係でもあるので(1)より$\left(X,\prec\right)$は狭義半順序関係(非反射律・推移律)を満たす。
狭義半順序関係であるとき3分律は$a\prec b\lor b\prec a\lor a=b$のみを満たせばよいので、
\begin{align*} a\prec b\lor b\prec a\lor a=b & \Leftrightarrow\left(a\preceq b\land a\ne b\right)\lor\left(b\preceq a\land a\ne b\right)\lor a=b\\ & \Leftrightarrow\left\{ \left(a\preceq b\lor b\preceq a\right)\land\left(a\preceq b\lor a\ne b\right)\land\left(b\preceq a\lor a\ne b\right)\land\left(a\ne b\right)\right\} \lor a=b\\ & \Leftrightarrow\left\{ \left(a\preceq b\lor a\ne b\right)\land\left(b\preceq a\lor a\ne b\right)\land\left(a\ne b\right)\right\} \lor a=b\\ & \Leftrightarrow\left\{ \left(a\preceq b\land b\preceq a\land\bot\right)\lor\left(a\ne b\right)\right\} \lor a=b\\ & \Leftrightarrow\left(a=b\lor a\ne b\right)\lor a=b\\ & \Leftrightarrow\top \end{align*} これより、$\left(X,\prec\right)$は3分律を満たす
従って、$\left(X,\prec\right)$は非反射律・推移律・3分律を満たすので狭義全順序集合となる。

(4)

狭義全順序集合$\left(X,\prec\right)$は狭義半順序関係でもあるので(2)より$\left(X,\preceq\right)$は半順序関係(反射律・反対称律・推移律)を満たす。
このとき、
\begin{align*} a\preceq b\lor b\preceq a & \Leftrightarrow a\prec b\lor a=b\lor b\prec a\lor b=a\\ & \Leftrightarrow a\prec b\lor b\prec a\lor b=a\\ & \Leftrightarrow\top \end{align*} となるので$\left(X,\preceq\right)$は完全律を満たす。
従って、$\left(X,\preceq\right)$は反射律・反対称律・推移律・完全律を満たすので全順序集合となる。

(5)

完全律を満たさないとき、
\begin{align*} a\prec b\lor b\prec a\lor a=b & \Leftrightarrow a\prec b\lor a=b\lor b\prec a\lor a=b\\ & \Leftrightarrow a\preceq b\lor b\preceq a\\ & \Rightarrow\bot \end{align*} となるので3分律を満たさない。
故に題意は成り立つ。

(6)

狭義半順序集合なので3分律を満たさないとき、$a\prec b\lor b\prec a\lor a=b\Leftrightarrow\bot$のみ満たせばいいので、
\begin{align*} a\preceq b\lor b\preceq a & \Leftrightarrow a\prec b\lor a=b\lor b\prec a\lor a=b\\ & \Leftrightarrow a\prec b\lor b\prec a\lor a=b\\ & \Leftrightarrow\bot \end{align*} より、完全律を満たさない。
故に題意は成り立つ。