半順序集合と狭義半順序集合の関係
半順序集合と狭義半順序集合の関係
(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*} となるからである。
なぜなら
\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*} より、完全律を満たさない。
故に題意は成り立つ。
ページ情報
タイトル | 半順序集合と狭義半順序集合の関係 |
URL | https://www.nomuramath.com/bdaq9sug/ |
SNSボタン |
半順序関係と狭義半順序関係
\[
x\prec y\Leftrightarrow x\preceq y\land x\ne y
\]
順序を反映する写像(順序単射)ならば単射
テューキーの補題
有限性をもつ空でない集合族$\mathcal{A}$に対し、包含関係を順序とする半順序集合$\left(\mathcal{A},\subseteq\right)$に極大元が存在する。
超限帰納法
\[
P\left(\min X\right)\land\forall x\in X,\left(\forall a\prec x,P\left(a\right)\right)\rightarrow P\left(x\right)\Rightarrow\forall x\in X,P\left(x\right)
\]