半順序集合・狭義半順序集合の辞書式順序
半順序集合・狭義半順序集合の辞書式順序
このとき直積集合\(X\times Y\)上の2項関係\(\preceq\)を
\[ \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right) \] とする。
ここで、\(x_{1}\prec_{X}x_{2}\Leftrightarrow x_{1}\preceq_{X}x_{2}\land x_{1}\ne x_{2}\)である。
この2項関係を辞書式順序といい、\(\left(X\times Y,\preceq\right)\)は半順序集合となる。
\(\left(X,\preceq_{X}\right),\left(Y,\preceq_{Y}\right)\)を全順序集合とすると辞書式順序\(\preceq\)は全順序集合\(\left(X\times Y,\preceq\right)\)となる。
辞書式順序の半順序集合\(\left(X\times Y,\preceq\right)\)が与えられたとき、辞書式順序の狭義半順序集合\(\left(X\times Y,\prec\right)\)を
\[ \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1},y_{1}\right)\ne\left(x_{2},y_{2}\right) \] とする。
ここで\(\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\)は(1)と同じ定義とする。
このとき直積集合\(X\times Y\)上の2項関係\(\prec\)は
\[ \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\prec_{Y}y_{2}\right) \] となる。
この2項関係\(\prec\)を辞書式順序といい、\(\left(X\times Y,\prec\right)\)は狭義半順序集合となる。
\(\left(X,\preceq_{X}\right),\left(Y,\preceq_{Y}\right)\)を狭義全順序集合とすると辞書式順序\(\prec\)は狭義全順序集合\(\left(X\times Y,\prec\right)\)となる。
(1)半順序集合
\(\left(X,\preceq_{X}\right),\left(Y,\preceq_{Y}\right)\)を半順序集合とする。このとき直積集合\(X\times Y\)上の2項関係\(\preceq\)を
\[ \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right) \] とする。
ここで、\(x_{1}\prec_{X}x_{2}\Leftrightarrow x_{1}\preceq_{X}x_{2}\land x_{1}\ne x_{2}\)である。
この2項関係を辞書式順序といい、\(\left(X\times Y,\preceq\right)\)は半順序集合となる。
\(\left(X,\preceq_{X}\right),\left(Y,\preceq_{Y}\right)\)を全順序集合とすると辞書式順序\(\preceq\)は全順序集合\(\left(X\times Y,\preceq\right)\)となる。
(2)狭義半順序集合
\(\left(X,\prec_{X}\right),\left(Y,\prec_{Y}\right)\)を狭義半順序集合とする。辞書式順序の半順序集合\(\left(X\times Y,\preceq\right)\)が与えられたとき、辞書式順序の狭義半順序集合\(\left(X\times Y,\prec\right)\)を
\[ \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1},y_{1}\right)\ne\left(x_{2},y_{2}\right) \] とする。
ここで\(\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\)は(1)と同じ定義とする。
このとき直積集合\(X\times Y\)上の2項関係\(\prec\)は
\[ \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\prec_{Y}y_{2}\right) \] となる。
この2項関係\(\prec\)を辞書式順序といい、\(\left(X\times Y,\prec\right)\)は狭義半順序集合となる。
\(\left(X,\preceq_{X}\right),\left(Y,\preceq_{Y}\right)\)を狭義全順序集合とすると辞書式順序\(\prec\)は狭義全順序集合\(\left(X\times Y,\prec\right)\)となる。
半順序集合\(\left(X\times Y,\preceq\right)\)で
\[ \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1},y_{1}\right)\ne\left(x_{2},y_{2}\right) \] と定義すると、
\[ \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right) \] が成り立ち、\(\left(X\times Y,\prec\right)\)は狭義半順序集合となる。
狭義半順序集合\(\left(X\times Y,\prec\right)\)で
\[ \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right) \] と定義すると、
\[ \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1},y_{1}\right)\ne\left(x_{2},y_{2}\right) \] が成り立ち、\(\left(X\times Y,\preceq\right)\)は半順序集合となる。
\[ \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1},y_{1}\right)\ne\left(x_{2},y_{2}\right) \] と定義すると、
\[ \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right) \] が成り立ち、\(\left(X\times Y,\prec\right)\)は狭義半順序集合となる。
狭義半順序集合\(\left(X\times Y,\prec\right)\)で
\[ \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right) \] と定義すると、
\[ \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1},y_{1}\right)\ne\left(x_{2},y_{2}\right) \] が成り立ち、\(\left(X\times Y,\preceq\right)\)は半順序集合となる。
(1)
反射律
\begin{align*} \left(x_{1},y_{1}\right)\preceq\left(x_{1},y_{1}\right) & \Leftrightarrow x_{1}\prec_{X}x_{1}\lor\left(x_{1}=x_{1}\land y_{1}\preceq_{Y}y_{1}\right)\\ & \Leftrightarrow\top \end{align*} となるので反射律を満たす。反対称律
\begin{align*} \left\{ \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{2},y_{2}\right)\preceq\left(x_{1},y_{1}\right)\right\} & \Leftrightarrow\left\{ x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right)\right\} \land\left\{ x_{2}\prec_{X}x_{1}\lor\left(x_{2}=x_{1}\land y_{2}\preceq_{Y}y_{1}\right)\right\} \\ & \Leftrightarrow\left(x_{1}\prec_{X}x_{2}\land x_{2}\prec_{X}x_{1}\right)\lor\left(x_{1}\prec_{X}x_{2}\land x_{2}=x_{1}\land y_{2}\preceq_{Y}y_{1}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land x_{2}\prec_{X}x_{1}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land x_{2}=x_{1}\land y_{2}\preceq_{Y}y_{1}\right)\\ & \Leftrightarrow\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land y_{2}\preceq_{Y}y_{1}\right)\\ & \Leftrightarrow\left(x_{1}=x_{2}\land y_{1}=y_{2}\right)\\ & \Leftrightarrow\left(x_{1},y_{1}\right)=\left(x_{2},y_{2}\right) \end{align*} となるので反対称律を満たす。推移律
\begin{align*} \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{2},y_{2}\right)\preceq\left(x_{3},y_{3}\right) & \Leftrightarrow\left\{ x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right)\right\} \land\left\{ x_{2}\prec_{X}x_{3}\lor\left(x_{2}=x_{3}\land y_{2}\preceq_{Y}y_{3}\right)\right\} \\ & \Leftrightarrow\left(x_{1}\prec_{X}x_{2}\land x_{2}\prec_{X}x_{3}\right)\lor\left(x_{1}\prec_{X}x_{2}\land x_{2}=x_{3}\land y_{2}\preceq_{Y}y_{3}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land x_{2}\prec_{X}x_{3}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land x_{2}=x_{3}\land y_{2}\preceq_{Y}y_{3}\right)\\ & \Rightarrow\left(x_{1}\prec_{X}x_{3}\right)\lor\left(x_{1}\prec_{X}x_{2}\land x_{2}=x_{3}\land y_{2}\preceq_{Y}y_{3}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land x_{2}\prec_{X}x_{3}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{3}\land x_{2}=x_{3}\right)\\ & \Leftrightarrow\left(x_{1}\prec_{X}x_{3}\right)\lor\left(x_{1}\prec_{X}x_{3}\land x_{2}=x_{3}\land y_{2}\preceq_{Y}y_{3}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land x_{1}\prec_{X}x_{3}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{3}\land x_{2}=x_{3}\right)\\ & \Leftrightarrow\left\{ \left(x_{1}\prec_{X}x_{3}\right)\land\left\{ \top\lor\left(x_{2}=x_{3}\land y_{2}\preceq_{Y}y_{3}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right)\right\} \right\} \lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{3}\land x_{2}=x_{3}\right)\\ & \Leftrightarrow\left(x_{1}\prec_{X}x_{3}\right)\lor\left(x_{1}=x_{3}\land x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{3}\right)\\ & \Rightarrow\left(x_{1}\prec_{X}x_{3}\right)\lor\left(x_{1}=x_{3}\land y_{1}\preceq_{Y}y_{3}\right)\\ & \Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{3},y_{3}\right) \end{align*} となるので推移律を満たす。-
これらより、反射律・反対称律・推移律を満たすのでこの辞書式順序の2項関係は半順序集合となる。また\(\left(X,\preceq_{X}\right),\left(Y,\preceq_{Y}\right)\)が全順序集合の場合は、
\begin{align*} \left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\lor\left(x_{2},y_{2}\right)\preceq\left(x_{1},y_{1}\right) & \Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right)\lor x_{2}\prec_{X}x_{1}\lor\left(x_{2}=x_{1}\land y_{2}\preceq_{Y}y_{1}\right)\\ & \Leftrightarrow x_{1}\prec_{X}x_{2}\lor x_{2}\prec_{X}x_{1}\lor\left\{ x_{1}=x_{2}\land\left(y_{1}\preceq_{Y}y_{2}\lor y_{2}\preceq_{Y}y_{1}\right)\right\} \\ & \Leftrightarrow x_{1}\prec_{X}x_{2}\lor x_{2}\prec_{X}x_{1}\lor x_{1}=x_{2}\\ & \Leftrightarrow x_{1}\prec_{X}x_{2}\lor x_{1}=x_{2}\lor x_{2}\prec_{X}x_{1}\lor x_{1}=x_{2}\\ & \Leftrightarrow x_{1}\preceq_{X}x_{2}\lor x_{2}\preceq_{X}x_{1}\\ & \Leftrightarrow\top \end{align*} となるので\(\left(X\times Y,\preceq\right)\)は完全律を満たし全順序集合となる。
(2)
\begin{align*} \left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right) & \Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1},y_{1}\right)\ne\left(x_{2},y_{2}\right)\\ & \Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1}\ne x_{2}\lor y_{1}\ne y_{2}\right)\\ & \Leftrightarrow\left\{ x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right)\right\} \land\left(x_{1}\ne x_{2}\lor y_{1}\ne y_{2}\right)\\ & \Leftrightarrow\left\{ \left(x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right)\right)\land x_{1}\ne x_{2}\right\} \lor\left\{ \left(x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\right)\right)\land y_{1}\ne y_{2}\right\} \\ & \Leftrightarrow\left(x_{1}\prec_{X}x_{2}\land x_{1}\ne x_{2}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land x_{1}\ne x_{2}\right)\lor\left(x_{1}\prec_{X}x_{2}\land y_{1}\ne y_{2}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land y_{1}\ne y_{2}\right)\\ & \Leftrightarrow\left(x_{1}\prec_{X}x_{2}\land x_{1}\ne x_{2}\right)\lor\left(x_{1}\prec_{X}x_{2}\land y_{1}\ne y_{2}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land y_{1}\ne y_{2}\right)\\ & \Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}\prec_{X}x_{2}\land y_{1}\ne y_{2}\right)\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land y_{1}\ne y_{2}\right)\\ & \Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\preceq_{Y}y_{2}\land y_{1}\ne y_{2}\right)\\ & \Leftrightarrow x_{1}\prec x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\prec_{Y}y_{2}\right) \end{align*} これより\(X\times Y\)上の2項関係\(\prec\)は\(\left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow x_{1}\prec_{X}x_{2}\lor\left(x_{1}=x_{2}\land y_{1}\prec_{Y}y_{2}\right)\)となる。(1)より\(X\times Y\)上の2項関係\(\preceq\)は半順序関係を満たし、2項関係\(\prec\)を\(\left(x_{1},y_{1}\right)\prec\left(x_{2},y_{2}\right)\Leftrightarrow\left(x_{1},y_{1}\right)\preceq\left(x_{2},y_{2}\right)\land\left(x_{1},y_{1}\right)\ne\left(x_{2},y_{2}\right)\)で定めているので\(X\times Y\)上の2項関係\(\prec\)は狭義半順序関係を満たす。
故に\(\left(X\times Y,\prec\right)\)は狭義半順序集合となる。
また、\(\left(X\times Y,\preceq\right)\)が全順序集合であるならば、\(\prec\)の定め方より、\(\left(X\times Y,\prec\right)\)は狭義全順序集合となる。
ページ情報
| タイトル | 半順序集合・狭義半順序集合の辞書式順序 |
| URL | https://www.nomuramath.com/n50i2pzz/ |
| SNSボタン |
順序写像・順序単射・順序埋め込み写像の合成写像
順序写像同士の合成写像は順序写像になる。
集合族の有限性・鎖・帰納的順序集合の定義
\[
A\in\mathcal{A}\Leftrightarrow\forall B\subseteq A,\left|B\right|<\infty\rightarrow B\in\mathcal{A}
\]
順序同型は同値関係
順序同型は同値関係(反射律・対称律・推移律)を満たす。
整列可能定理
任意の集合は適当な順序を定めることによって整列集合にできる。