半順序部分集合
半順序集合\(\left( A,\leq \right) \)が与えられているものとします。つまり、\(\leq \)は集合\(A\)上の二項関係であり、反射律と反対称律と推移律を満たすということ、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq
x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq
z\right) \Rightarrow x\leq z\right]
\end{eqnarray*}が成り立つということです。
集合\(A\)の非空な部分集合\(X\)を選んだ上でその要素\(x,y\in X\)を任意に選んだとき、\(X\subset A\)ゆえに\(x,y\in A\)であるため、\(A\)上の半順序\(\leq \)のもとで\(x\leq y\)が成り立つか判定できます。そこで、任意の\(x,y\in X\)に対して、\begin{equation*}x\leq _{X}y\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(X\)上の二項関係\(\leq _{X}\)を新たに定義します。つまり、集合\(X\)の2つの要素\(x,y\)を任意に選んだとき、もとの集合\(A\)上に定義された半順序\(\leq \)のもとで\(x\leq y\)が成り立つ場合、そしてその場合にのみ新たな二項関係\(\leq _{X}\)のもとで\(x\leq_{X}y\)が成り立つものと定義するということです。
以上のように定義された\(X\)上の二項関係\(\leq _{X}\)を、もとの集合\(A\)上に定義された半順序\(\leq \)を\(X\)に制限した半順序（restriction）と呼びます。その名の通り\(\leq _{X}\)は\(X\)上の半順序になることが保証されます。つまり、反射律と反対称律と推移律を満たすということ、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in X:x\leq _{X}x \\
&&\left( O_{2}\right) \ \forall x,y\in X:\left( x\leq _{X}y\wedge y\leq
_{X}x\Rightarrow x=y\right) \\
&&\left( O_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\leq _{X}y\wedge
y\leq _{X}z\right) \Rightarrow x\leq _{X}z\right]
\end{eqnarray*}が成り立つということです。
\end{equation*}を満たすものとして\(X\)上の二項関係\(\leq _{X}\)を定義した場合、\(\leq _{X}\)は\(X\)上の半順序になる。すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in X:x\leq _{X}x \\
&&\left( O_{2}\right) \ \forall x,y\in X:\left( x\leq _{X}y\wedge y\leq
_{X}x\Rightarrow x=y\right) \\
&&\left( O_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\leq _{X}y\wedge
y\leq _{X}z\right) \Rightarrow x\leq _{X}z\right] \end{eqnarray*}が成り立つ。
半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が与えられたとき、上の命題より、\(A\)上の半順序\(\leq \)を\(X\)に制限することにより得られる\(X\)上の二項関係\(\leq _{X}\)は半順序であるため、\begin{equation*}\left( X,\leq _{X}\right)
\end{equation*}もまた半順序集合になります。そこで、これを\(\left( A,\leq \right) \)の半順序部分集合（partial ordered subset）や順序部分集合（ordered subset）などと呼びます。
多くの場合、半順序集合\(A\)上の半順序を部分集合\(X\subset A\)に制限することにより得られる半順序\(\leq _{X}\)を、制限する以前の半順序と同様の記号\(\leq \)で表記します。この場合、\(\left(A,\leq \right) \)の半順序部分集合を、\begin{equation*}\left( X,\leq \right)
\end{equation*}と表記できます。また、半順序部分集合について言及していることが文脈から明らかである場合、これをシンプルに、\begin{equation*}
X
\end{equation*}と表記できます。
\end{equation*}は半順序集合です。有理数集合\(\mathbb{Q} \)は\(\mathbb{R} \)の非空な部分集合であるため、任意の\(x,y\in \mathbb{Q} \)に対して、\begin{equation*}x\leq _{\mathbb{Q} }y\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(\mathbb{Q} \)上の二項関係\(\leq _{\mathbb{Q} }\)を定義すれば、これは\(\mathbb{Q} \)上の半順序になります。したがって、\begin{equation*}\left( \mathbb{Q} ,\leq _{\mathbb{Q} }\right)
\end{equation*}は半順序集合です。同様の理由により、整数集合\(\mathbb{Z} \)に関して、\begin{equation*}\left( \mathbb{Z} ,\leq _{\mathbb{Z} }\right)
\end{equation*}は半順序集合であり、自然数集合\(\mathbb{N} \)に関して、\begin{equation*}\left( \mathbb{N} ,\leq _{\mathbb{N} }\right)
\end{equation*}は半順序集合です。
\end{equation*}は半順序集合です。非空の集合族\(\mathfrak{A}\subset 2^{U}\)を選んだとき、任意の集合\(A,B\in \mathfrak{A}\)に対して、\begin{equation*}A\subset _{\mathfrak{A}}B\Leftrightarrow A\subset B
\end{equation*}を満たすものとして\(\mathfrak{A}\)上の二項関係\(\subset _{\mathfrak{A}}\)を定義すれば、これは\(\subset _{\mathfrak{A}}\)上の半順序になります。したがって、\begin{equation*}\left( \mathfrak{A},\subset _{\mathfrak{A}}\right)
\end{equation*}は半順序集合です。
\end{equation*}は半順序集合です。奇数であるような自然数からなる集合\(O\)は\(\mathbb{N} \)の非空な部分集合であるため、任意の\(x,y\in O\)に対して、\begin{eqnarray*}x|_{O}y &\Leftrightarrow &x|y \\
&\Leftrightarrow &y\text{が}x\text{の倍数}
\end{eqnarray*}を満たすものとして\(O\)上の二項関係\(|_{O}\)を定義すれば、これは\(O\)上の半順序になります。したがって、\begin{equation*}\left( O,|_{O}\right)
\end{equation*}は半順序集合です。同様の理由により、偶数であるような自然数からなる集合\(E\)について、\begin{equation*}\left( E,|_{E}\right)
\end{equation*}は半順序集合です。
全順序部分集合
全順序集合についても同様の議論が成立します。具体的には以下の通りです。
全順序集合\(\left( A,\leq \right) \)が与えられているものとします。つまり、\(\leq \)は集合\(A\)上の二項関係であり、反射律と反対称律と推移律と完備律を満たすということ、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq
x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq
z\right) \Rightarrow x\leq z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in A:x\leq y\vee y\leq x
\end{eqnarray*}が成り立つということです。
集合\(A\)の非空な部分集合\(X\)を選んだ上でその要素\(x,y\in X\)を任意に選んだとき、\(X\subset A\)ゆえに\(x,y\in A\)であるため、\(A\)上の全順序\(\leq \)のもとで\(x\leq y\)が成り立つか判定できます。そこで、任意の\(x,y\in X\)に対して、\begin{equation*}x\leq _{X}y\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(X\)上の二項関係\(\leq _{X}\)を新たに定義します。つまり、集合\(X\)の2つの要素\(x,y\)を任意に選んだとき、もとの集合\(A\)上に定義された全順序\(\leq \)のもとで\(x\leq y\)が成り立つ場合、そしてその場合にのみ新たな二項関係\(\leq _{X}\)のもとで\(x\leq_{X}y\)が成り立つものと定義するということです。
以上のように定義された\(X\)上の二項関係\(\leq _{X}\)を、もとの集合\(A\)上に定義された全順序\(\leq \)を\(X\)に制限した全順序（restriction）と呼びます。その名の通り\(\leq _{X}\)は\(X\)上の全順序になることが保証されます。つまり、反射律と反対称律と推移律と完備律を満たすということ、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in X:x\leq _{X}x \\
&&\left( O_{2}\right) \ \forall x,y\in X:\left( x\leq _{X}y\wedge y\leq
_{X}x\Rightarrow x=y\right) \\
&&\left( O_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\leq _{X}y\wedge
y\leq _{X}z\right) \Rightarrow x\leq _{X}z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in X:x\leq _{X}y\vee y\leq _{X}x
\end{eqnarray*}が成り立つということです。
\end{equation*}を満たすものとして\(X\)上の二項関係\(\leq _{X}\)を定義した場合、\(\leq _{X}\)は\(X\)上の全順序になる。すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in X:x\leq _{X}x \\
&&\left( O_{2}\right) \ \forall x,y\in X:\left( x\leq _{X}y\wedge y\leq
_{X}x\Rightarrow x=y\right) \\
&&\left( O_{3}\right) \ \forall x,y,z\in X:\left[ \left( x\leq _{X}y\wedge
y\leq _{X}z\right) \Rightarrow x\leq _{X}z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in X:x\leq _{X}y\vee y\leq _{X}x
\end{eqnarray*}が成り立つ。
全順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が与えられたとき、上の命題より、\(A\)上の全順序\(\leq \)を\(X\)に制限することにより得られる\(X\)上の二項関係\(\leq _{X}\)は半順序であるため、\begin{equation*}\left( X,\leq _{X}\right)
\end{equation*}もまた半順序集合になります。そこで、これを\(\left( A,\leq \right) \)の半順序部分集合（partial ordered subset）や順序部分集合（ordered subset）などと呼びます。
多くの場合、全順序集合\(A\)上の全順序を部分集合\(X\subset A\)に制限することにより得られる全順序\(\leq _{X}\)を、制限する以前の全順序と同様の記号\(\leq \)で表記します。この場合、\(\left(A,\leq \right) \)の全順序部分集合を、\begin{equation*}\left( X,\leq \right)
\end{equation*}と表記できます。また、全順序部分集合について言及していることが文脈から明らかである場合、これをシンプルに、\begin{equation*}
X
\end{equation*}と表記できます。
\end{equation*}は全順序集合です。有理数集合\(\mathbb{Q} \)は\(\mathbb{R} \)の非空な部分集合であるため、任意の\(x,y\in \mathbb{Q} \)に対して、\begin{equation*}x\leq _{\mathbb{Q} }y\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(\mathbb{Q} \)上の二項関係\(\leq _{\mathbb{Q} }\)を定義すれば、これは\(\mathbb{Q} \)上の全順序になります。したがって、\begin{equation*}\left( \mathbb{Q} ,\leq _{\mathbb{Q} }\right)
\end{equation*}は全順序集合です。同様の理由により、整数集合\(\mathbb{Z} \)に関して、\begin{equation*}\left( \mathbb{Z} ,\leq _{\mathbb{Z} }\right)
\end{equation*}は全順序集合であり、自然数集合\(\mathbb{N} \)に関して、\begin{equation*}\left( \mathbb{N} ,\leq _{\mathbb{N} }\right)
\end{equation*}は全順序集合です。
半順序集合の部分集合であるような全順序集合
半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)が与えられたとき、先の命題より、\(\left( X,\leq _{X}\right) \)もまた半順序集合になります。その一方で、\(A\)上の半順序\(\leq \)は完備律を満たすとは限らないため、\(\leq \)の\(X\)への制限\(\leq _{X}\)もまた完備律を満たすとは限らず、したがって\(\left( X,\leq_{X}\right) \)は全順序集合になるとは限りません。
その一方で、半順序集合\(\left( A,\leq \right) \)の非空な部分集合\(X\)を適切な形で選ぶことにより、全順序集合\(\left( X,\leq _{X}\right) \)をとり出せるケースも存在します。以下の例より明らかです。
\end{equation*}は半順序集合です。その一方で、自然数\(2,3\in \mathbb{N} \)に注目した場合、\(2\)は\(3\)の倍数ではなく、\(3\)は\(2\)の倍数ではないため、\(|\)は完備律を満たさず、したがって\(\left( \mathbb{N} ,|\right) \)は全順序集合ではありません。\(\mathbb{N} \)の非空な部分集合\begin{equation*}X=\left\{ 3,9,27,81\right\}
\end{equation*}に注目すると、先の命題より、\(|\)の\(X\)への制限\(|_{X}\)は半順序です。加えて、\(X\)の要素\(3,9,27,81\)はいずれも\(3\)の倍数であるため、\(X\)から2つの要素を任意に選んだとき、一方は他方の倍数です。つまり、\(x,y\in X\)を任意に選んだとき、\begin{equation*}x|_{X}y\vee y|_{X}x
\end{equation*}が成り立つため、\(|_{X}\)は完備律を満たします。以上より、\begin{equation*}\left( X,|_{X}\right)
\end{equation*}は全順序集合であることが明らかになりました。
実は、半順序集合が任意に与えられたとき、全順序部分集合を常にとることができます。
演習問題
\end{equation*}を満たすことを示してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】