部分順序集合
部分順序集合
順序集合\(\left(A,\preceq_{A}\right)\)があり、\(A\)の部分集合を\(B\subseteq A\)とする。
このとき、\(B\)の任意の元\(b_{1},b_{2}\)に対し、\(b_{1}\preceq_{A}b_{2}\Leftrightarrow b_{1}\preceq_{B}b_{2}\)と定めれば順序\(\preceq_{B}\)は\(B\)での順序となる。
故に\(\left(B,\preceq_{B}\right)\)は順序集合となり、\(\left(B,\preceq_{B}\right)\)は\(\left(A,\preceq_{A}\right)\)の部分順序集合という。
順序集合\(\left(A,\preceq_{A}\right)\)があり、\(A\)の部分集合を\(B\subseteq A\)とする。
このとき、\(B\)の任意の元\(b_{1},b_{2}\)に対し、\(b_{1}\preceq_{A}b_{2}\Leftrightarrow b_{1}\preceq_{B}b_{2}\)と定めれば順序\(\preceq_{B}\)は\(B\)での順序となる。
故に\(\left(B,\preceq_{B}\right)\)は順序集合となり、\(\left(B,\preceq_{B}\right)\)は\(\left(A,\preceq_{A}\right)\)の部分順序集合という。
全体集合を整数全体\(\mathbb{Z}\)として、順序を通常の大小関係\(\leq_{\mathbb{Z}}\)ととると\(\left(\mathbb{Z},\leq_{\mathbb{Z}}\right)\)は順序集合となる。
ここで、自然数全体を部分集合\(\mathbb{N}\subseteq\mathbb{Z}\)ととり、任意の\(n_{1},n_{2}\in\mathbb{N}\)に対し、\(n_{1}\leq_{\mathbb{Z}}n_{2}\Rightarrow n_{1}\leq_{\mathbb{N}}n_{2}\)と定める。
こうすると\(\left(\mathbb{N},\leq_{\mathbb{N}}\right)\)は順序集合となり、\(\left(\mathbb{N},\leq_{\mathbb{N}}\right)\)は\(\left(\mathbb{Z},\leq_{\mathbb{Z}}\right)\)の部分順序集合となる。
ここで、自然数全体を部分集合\(\mathbb{N}\subseteq\mathbb{Z}\)ととり、任意の\(n_{1},n_{2}\in\mathbb{N}\)に対し、\(n_{1}\leq_{\mathbb{Z}}n_{2}\Rightarrow n_{1}\leq_{\mathbb{N}}n_{2}\)と定める。
こうすると\(\left(\mathbb{N},\leq_{\mathbb{N}}\right)\)は順序集合となり、\(\left(\mathbb{N},\leq_{\mathbb{N}}\right)\)は\(\left(\mathbb{Z},\leq_{\mathbb{Z}}\right)\)の部分順序集合となる。
\(\left(A,\preceq_{A}\right)\)は順序集合であるので、任意の元\(b_{1},b_{2}\in B\)に対し、\(B\subseteq A\)より\(b_{1},b_{2}\in A\)となる。
\(\left(A,\preceq_{A}\right)\)は順序集合であるので、任意の元\(b_{1},b_{2}\in B\)に対し、\(B\subseteq A\)より\(b_{1},b_{2}\in A\)となる。
\[ \left(P\rightarrow Q\right)\land\left(R\rightarrow S\right)\Rightarrow\left(P\land R\right)\rightarrow\left(Q\land S\right) \] が成り立ち、\(\left(A,\preceq_{A}\right)\)では反対称律を満たすので、
\begin{align*} \top & \Leftrightarrow\left\{ \left(b_{1}\preceq_{A}b_{2}\rightarrow b_{1}\preceq_{B}b_{2}\right)\land\left(b_{2}\preceq_{A}b_{1}\rightarrow b_{2}\preceq_{B}b_{1}\right)\right\} \land\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \\ & \Rightarrow\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\right\} \land\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \\ & \Leftrightarrow\left\{ \lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\lor\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\right\} \land\left\{ \lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\lor b_{1}=b_{2}\right\} \\ & \Leftrightarrow\lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\lor\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\land b_{1}=b_{2}\right\} \\ & \Rightarrow\lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\lor\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \\ & \Leftrightarrow\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \end{align*} となる。
これより、\(\left(A,\preceq_{A}\right)\)で反対称律を満たすなら\(\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\Leftrightarrow\top\)なので、\(\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\rightarrow b_{1}=b_{2}\)が真となり反対称律を満たす。
途中でLK推論を使った。
これより、\(\left(A,\preceq_{A}\right)\)で推移律を満たすなら\(\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\right)\Leftrightarrow\top\)なので、\(\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\right)\rightarrow b_{1}\preceq_{B}b_{3}\)が真となり推移律を満たす。
反射律
\(\top\Leftrightarrow b_{1}\preceq_{A}b_{1}\Leftrightarrow b_{1}\preceq_{B}b_{1}\)より、\(b_{1}\preceq_{B}b_{1}\)が真となるので反射律を満たす。反対称律
\begin{align*} \top & \Leftrightarrow\left\{ \left(b_{1}\preceq_{A}b_{2}\leftrightarrow b_{1}\preceq_{B}b_{2}\right)\land\left(b_{2}\preceq_{A}b_{1}\leftrightarrow b_{2}\preceq_{B}b_{1}\right)\right\} \land\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \\ & \Leftrightarrow\left\{ \left(b_{1}\preceq_{A}b_{2}\leftrightarrow b_{1}\preceq_{B}b_{2}\right)\land\left(b_{2}\preceq_{A}b_{1}\leftrightarrow b_{2}\preceq_{B}b_{1}\right)\right\} \land\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \\ & \Rightarrow\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\rightarrow b_{1}=b_{2} \end{align*}推移律
\begin{align*} \top & \Leftrightarrow\left(b_{1}\preceq_{A}b_{2}\leftrightarrow b_{1}\preceq_{B}b_{2}\right)\land\left(b_{2}\preceq_{A}b_{3}\leftrightarrow b_{2}\preceq_{B}b_{3}\right)\land\left(b_{1}\preceq_{A}b_{3}\leftrightarrow b_{1}\preceq_{B}b_{3}\right)\land\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\rightarrow b_{1}\preceq_{A}b_{3}\right)\\ & \Leftrightarrow\left(b_{1}\preceq_{A}b_{2}\leftrightarrow b_{1}\preceq_{B}b_{2}\right)\land\left(b_{2}\preceq_{A}b_{3}\leftrightarrow b_{2}\preceq_{B}b_{3}\right)\land\left(b_{1}\preceq_{A}b_{3}\leftrightarrow b_{1}\preceq_{B}b_{3}\right)\land\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\rightarrow b_{1}\preceq_{B}b_{3}\right)\\ & \Rightarrow b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\rightarrow b_{1}\preceq_{B}b_{3} \end{align*}-
これらより、\(\left(B,\preceq_{B}\right)\)は反射律・反対称律・推移律を満たすので順序集合となる。おまけ
\(\forall b_{1},b_{2}\in B,b_{1}\preceq_{A}b_{2}\Rightarrow b_{1}\preceq_{B}b_{2}\)として証明してみる。\(\left(A,\preceq_{A}\right)\)は順序集合であるので、任意の元\(b_{1},b_{2}\in B\)に対し、\(B\subseteq A\)より\(b_{1},b_{2}\in A\)となる。
反射律
\(\top\Leftrightarrow b_{1}\preceq_{A}b_{1}\Rightarrow b_{1}\preceq_{B}b_{1}\)より、\(b_{1}\preceq_{B}b_{1}\)が真となるので反射律を満たす。反対称律
LK推論より、\[ \left(P\rightarrow Q\right)\land\left(R\rightarrow S\right)\Rightarrow\left(P\land R\right)\rightarrow\left(Q\land S\right) \] が成り立ち、\(\left(A,\preceq_{A}\right)\)では反対称律を満たすので、
\begin{align*} \top & \Leftrightarrow\left\{ \left(b_{1}\preceq_{A}b_{2}\rightarrow b_{1}\preceq_{B}b_{2}\right)\land\left(b_{2}\preceq_{A}b_{1}\rightarrow b_{2}\preceq_{B}b_{1}\right)\right\} \land\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \\ & \Rightarrow\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\right\} \land\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \\ & \Leftrightarrow\left\{ \lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\lor\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\right\} \land\left\{ \lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\lor b_{1}=b_{2}\right\} \\ & \Leftrightarrow\lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\lor\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\land b_{1}=b_{2}\right\} \\ & \Rightarrow\lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\lor\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \\ & \Leftrightarrow\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\rightarrow\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\rightarrow b_{1}=b_{2}\right\} \end{align*} となる。
これより、\(\left(A,\preceq_{A}\right)\)で反対称律を満たすなら\(\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{1}\right)\Leftrightarrow\top\)なので、\(\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{1}\right)\rightarrow b_{1}=b_{2}\)が真となり反対称律を満たす。
推移律
\begin{align*} \top & \Leftrightarrow\left(b_{1}\preceq_{A}b_{2}\rightarrow b_{1}\preceq_{B}b_{2}\right)\land\left(b_{2}\preceq_{A}b_{3}\rightarrow b_{2}\preceq_{B}b_{3}\right)\land\left(b_{1}\preceq_{A}b_{3}\rightarrow b_{1}\preceq_{B}b_{3}\right)\land\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\rightarrow b_{1}\preceq_{A}b_{3}\right)\\ & \Rightarrow\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\right)\rightarrow\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\right)\right\} \land\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\rightarrow b_{1}\preceq_{A}b_{3}\right)\land\left(b_{1}\preceq_{A}b_{3}\rightarrow b_{1}\preceq_{B}b_{3}\right)\\ & \Rightarrow\left\{ \left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\right)\rightarrow\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\right)\right\} \land\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\rightarrow b_{1}\preceq_{B}b_{3}\right)\\ & \Leftrightarrow\left\{ \lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\right)\lor\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\right)\land b_{1}\preceq_{B}b_{3}\right\} \right\} \\ & \Rightarrow\lnot\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\right)\lor\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\right)\rightarrow b_{1}\preceq_{B}b_{3}\right\} \\ & \Leftrightarrow\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\right)\rightarrow\left\{ \left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\right)\rightarrow b_{1}\preceq_{B}b_{3}\right\} \end{align*} となる。途中でLK推論を使った。
これより、\(\left(A,\preceq_{A}\right)\)で推移律を満たすなら\(\left(b_{1}\preceq_{A}b_{2}\land b_{2}\preceq_{A}b_{3}\right)\Leftrightarrow\top\)なので、\(\left(b_{1}\preceq_{B}b_{2}\land b_{2}\preceq_{B}b_{3}\right)\rightarrow b_{1}\preceq_{B}b_{3}\)が真となり推移律を満たす。
-
これらより、\(\left(B,\preceq_{B}\right)\)は反射律・反対称律・推移律を満たすので順序集合となる。ページ情報
| タイトル | 部分順序集合 |
| URL | https://www.nomuramath.com/sm40bfn3/ |
| SNSボタン |
半順序集合・狭義半順序集合の辞書式順序
\[
\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)
\]
整列集合の比較定理
順序写像・順序単射・順序埋め込み写像の合成写像
順序写像同士の合成写像は順序写像になる。
順序写像・単調写像・順序反映・順序埋め込み・順序同型写像の定義
\[
a\preceq_{X}b\Rightarrow f\left(a\right)\preceq_{Y}f\left(b\right)
\]