WIIS

順序集合

全順序と狭義全順序の関係

目次

Mailで保存
Xで共有

全順序と狭義全順序(復習)

集合\(A\)上の二項関係\(R\)が与えられているものとします。つまり、\begin{equation*}R\subset A\times A
\end{equation*}であるとともに、任意の\(x,y\in A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow \left( x,y\right) \in R
\end{equation*}を満たすものとして記号\(R\left( x,y\right) \)の意味を定義するということです。このとき、\begin{equation*}\lnot R\left( x,y\right) \Leftrightarrow \left( x,y\right) \not\in R
\end{equation*}という関係もまた成立することに注意してください。

集合\(A\)上の二項関係\(R\)が半順序であることとは、\(R\)が反射律と反対称律と推移律と完備律を満たすことを意味します。つまり、以下の4つの条件\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:R\left( x,x\right) \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,x\right) \right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,z\right) \right) \Rightarrow R\left( x,z\right) \right] \\
&&\left( O_{4}\right) \ \forall x,y\in A:R\left( x,y\right) \vee R\left(
y,x\right)
\end{eqnarray*}が成り立つことを認める場合、\(R\)を全順序と呼びます。多くの場合、全順序を表す記号として\(\leq \)を採用します。つまり、集合\(A\)上の全順序\(R\)が与えられたとき、任意の\(x,y\in A\)について、\begin{equation*}x\leq y\Leftrightarrow R\left( x,y\right)
\end{equation*}を満たすものとして記号\(x\leq y\)の意味を定義するということです。この場合、\begin{equation*}\lnot \left( x\leq y\right) \Leftrightarrow \lnot R\left( x,y\right)
\end{equation*}という関係もまた成立します。全順序を表す記号\(\leq \)を用いて反射律と反対称律と推移律と完備律を改めて表現すると、\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\)上の二項関係\(R\)が狭義全順序であることとは、\(R\)が非対称律と推移律と三分律を満たすことを意味します。つまり、以下の3つの条件\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ R\left( x,y\right)
\Rightarrow \lnot R\left( y,x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,z\right) \right) \Rightarrow R\left( x,z\right) \right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:R\left( x,y\right) ,R\left(
y,x\right) ,x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}が成り立つことを認める場合、\(R\)を狭義全順序と呼びます。多くの場合、狭義全順序を表す記号として\(<\)を採用します。つまり、集合\(A\)上の狭義全順序\(R\)が与えられたとき、任意の\(x,y\in A\)について、\begin{equation*}x<y\Leftrightarrow R\left( x,y\right)
\end{equation*}を満たすものとして記号\(x<y\)の意味を定義するということです。この場合、\begin{equation*}\lnot \left( x<y\right) \Leftrightarrow \lnot R\left( x,y\right)
\end{equation*}という関係もまた成立します。狭義全順序を表す記号\(<\)を用いて非対称律と推移律と三分律を改めて表現すると、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow \lnot \left(
y<x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge
y<z\right) \Rightarrow x<z\right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:x<y,y<x,x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}となります。

全順序と狭義全順序の間には深い関係があります。具体的には、集合\(A\)の全順序が与えられれば、それを用いて集合\(A\)上の狭義全順序を生成することができます。逆に、集合\(A\)の狭義全順序が与えられれば、それを用いて集合\(A\)上の全順序を生成することができます。順番に解説します。

 

全順序から生成される狭義全順序

集合\(A\)上の全順序\(\leq \)を任意に選びます。つまり、\(\leq \)は反射律と反対称律、推移律に加えて完備律を満たすということ、具体的には、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left( x\leq y\wedge y\leq
x\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:\left( x\leq y\vee y\leq x\right)
\end{eqnarray*}が成り立つということです。このとき、任意の\(x,y\in A\)に対して、\begin{equation}R\left( x,y\right) \Leftrightarrow \left( x\leq y\wedge x\not=y\right)
\quad \cdots (1)
\end{equation}を満たすものとして\(A\)上の二項関係\(R\)を新たに定義します。つまり、2つの要素\(x,y\in A\)を任意に選んだとき、全順序\(\leq \)のもとで\(x\leq y\)と\(x\not=y\)が成り立つ場合、そしてその場合にのみ新たな二項関係\(R\)のもとで\(R\left( x,y\right) \)が成り立つものと定義するということです。この場合、\begin{eqnarray*}\lnot R\left( x,y\right) &\Leftrightarrow &\lnot \left( x\leq y\wedge
x\not=y\right) \quad \because \left( 1\right) \\
&\Leftrightarrow &\lnot \left( x\leq y\right) \vee \lnot \left(
x\not=y\right) \quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot \left( x\leq y\right) \vee x=y
\end{eqnarray*}すなわち、\begin{equation*}
\lnot R\left( x,y\right) \Leftrightarrow \lnot \left( x\leq y\right) \vee x=y
\end{equation*}もまた成り立ちます。つまり、2つの要素\(x,y\in A\)を任意に選んだとき、半順序\(\leq \)のもとで\(\lnot \left( x\leq y\right) \)または\(x=y\)の少なくとも一方が成り立つ場合、そしてその場合にのみ新たな二項関係\(R\)のもとで\(\lnot R\left( x,y\right) \)が成り立ちます(\(R\left( x,y\right) \)が成り立たない)。

集合\(A\)上の全順序\(\leq \)を用いて新たな二項関係\(R\)を上のように定義した場合、この新たな二項関係\(R\)は集合\(A\)上の狭義全順序になることが保証されます。つまり、\(R\)は非対称律と推移律と三分律を満たすことが示されるということです。具体的には、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ R\left( x,y\right)
\Rightarrow \lnot R\left( y,x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,z\right) \right) \Rightarrow R\left( x,z\right) \right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:R\left( x,y\right) ,R\left(
y,x\right) ,x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}がすべて成り立つということです。

命題(全順序から生成される狭義全順序)
集合\(A\)上の全順序\(\leq \)が与えられたとき、そこから、任意の\(x,y\in A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow \left( x\leq y\wedge x\not=y\right)
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義した場合、\(R\)は狭義全順序になる。すなわち、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ R\left( x,y\right)
\Rightarrow \lnot R\left( y,x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,z\right) \right) \Rightarrow R\left( x,z\right) \right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:R\left( x,y\right) ,R\left(
y,x\right) ,x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}が成り立つ。加えて、任意の\(x,y\in A\)に対して、\begin{equation*}x\leq y\Leftrightarrow R\left( x,y\right) \vee x=y
\end{equation*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(実数の大小関係と狭義大小関係)
すべての実数からなる集合\(\mathbb{R} \)上に定義された大小関係\(\leq \)が与えられたとき、狭義の大小関係\(<\)は、任意の実数\(x,y\in \mathbb{R} \)に対して、\begin{equation*}x<y\Leftrightarrow \left( x\leq y\wedge x\not=y\right)
\end{equation*}を満たすものとして定義されます。つまり、2つの実数\(x,y\)について、\(x\leq y\)と\(x\not=y\)がともに成り立つ場合、そしてその場合にのみ\(x<y\)が成り立つものとして\(x<y\)の意味を定義するということです。大小関係\(\leq \)は\(\mathbb{R} \)上の全順序であるため、先の命題より、狭義大小関係\(<\)は\(\mathbb{R} \)上の狭義全順序であることが保証されます。つまり、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow \lnot \left(
y<x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge
y<z\right) \Rightarrow x<z\right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:x<y,y<x,x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}が成り立つということです。

 

狭義全順序から生成される全順序

全順序が与えられればそれを用いることにより狭義全順序を生成できることが明らかになりました。それとは逆に、狭義全順序から全順序を生成することもできます。具体的には以下の通りです。

集合\(A\)上の狭義全順序\(<\)を任意に選びます。つまり、\(<\)は非対称律と推移律と三分律を満たすということ、具体的には、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow \lnot \left(
y<x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge
y<z\right) \Rightarrow x<z\right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:x<y,y<x,x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}が成り立つということです。このとき、任意の\(x,y\in A\)に対して、\begin{equation}R\left( x,y\right) \Leftrightarrow \left( x<y\vee x=y\right) \quad \cdots (1)
\end{equation}を満たすものとして\(A\)上の二項関係\(R\)を新たに定義します。つまり、2つの要素\(x,y\in A\)を任意に選んだとき、狭義全順序\(<\)のもとで\(x<y\)または\(x=y\)の少なくとも一方が成り立つ場合、そしてその場合にのみ新たな二項関係\(R\)のもとで\(R\left( x,y\right) \)が成り立つものと定義するということです。この場合、\begin{eqnarray*}\lnot R\left( x,y\right) &\Leftrightarrow &\lnot \left( x<y\vee x=y\right)
\quad \because \left( 1\right) \\
&\Leftrightarrow &\lnot \left( x<y\right) \wedge \lnot \left( x=y\right)
\quad \because \text{ド・モルガンの法則} \\
&\Leftrightarrow &\lnot \left( x<y\right) \wedge x\not=y
\end{eqnarray*}すなわち、\begin{equation*}
\lnot R\left( x,y\right) \Leftrightarrow \lnot \left( x<y\right) \wedge
x\not=y
\end{equation*}もまた成り立ちます。つまり、2つの要素\(x,y\in A\)を任意に選んだとき、狭義全順序\(<\)のもとで\(\lnot \left( x<y\right) \)と\(x\not=y\)がともに成り立つ場合、そしてその場合にのみ新たな二項関係\(R\)のもとで\(\lnot R\left( x,y\right) \)が成り立ちます(\(R\left( x,y\right) \)が成り立たない)。

集合\(A\)上の狭義全順序\(<\)を用いて新たな二項関係\(R\)を上のように定義した場合、この新たな二項関係\(R\)は集合\(A\)上の全順序になることが保証されます。つまり、\(R\)は反射律と反対称律と推移律に加えて完備律を満たすことが示されるということです。具体的には、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:R\left( x,x\right) \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,x\right) \right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,z\right) \right) \Rightarrow R\left( x,z\right) \right] \\
&&\left( O_{4}\right) \ \forall x,y\in A:R\left( x,y\right) \vee R\left(
y,x\right)
\end{eqnarray*}がすべて成り立つということです。

命題(狭義全順序から生成される全順序)
集合\(A\)上の狭義全順序\(<\)が与えられたとき、そこから、任意の\(x,y\in A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow \left( x<y\vee x=y\right)
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義した場合、\(R\)は全順序になる。すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:R\left( x,x\right) \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,x\right) \right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( R\left( x,y\right)
\wedge R\left( y,z\right) \right) \Rightarrow R\left( x,z\right) \right] \\
&&\left( O_{4}\right) \ \forall x,y\in A:R\left( x,y\right) \vee R\left(
y,x\right)
\end{eqnarray*}が成り立つ。加えて、任意の\(x,y\in A\)に対して、\begin{equation*}x<y\Leftrightarrow \left( R\left( x,y\right) \wedge x\not=y\right)
\end{equation*}という関係が成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

例(実数の大小関係と狭義大小関係)
すべての実数からなる集合\(\mathbb{R} \)上に定義された狭義大小関係\(<\)が与えられたとき、大小関係\(\leq \)は、任意の実数\(x,y\in \mathbb{R} \)に対して、\begin{equation*}x\leq y\Leftrightarrow \left( x<y\vee x\not=y\right)
\end{equation*}を満たすものとして定義されます。つまり、2つの実数\(x,y\)について、\(x\leq y\)または\(x\not=y\)の少なくとも一方が成り立つ場合、そしてその場合にのみ\(x\leq y\)が成り立つものとして\(x\leq y\)の意味を定義するということです。狭義大小関係\(<\)は\(\mathbb{R} \)上の狭義全順序であるため、先の命題より、大小関係\(<\)は\(\mathbb{R} \)上の全順序であることが保証されます。つまり、\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\wedge y\leq x
\end{eqnarray*}が成り立つということです。

 

全順序と狭義全順序の関係

以上の2つの命題より、集合\(A\)上の全順序\(\leq \)から狭義全順序\(<\)を生成したり、逆に、狭義全順序\(<\)から全順序\(\leq \)を生成できることが明らかになりました。したがって、全順序や狭義全順序について考える際には、どちらを先に定義しても問題はありません。多くの場合、全順序\(\leq \)を先に定義し、そこから間接的に狭義全順序\(<\)を定義するアプローチを採用します。つまり、集合\(A\)上の全順序\(\leq \)が与えられたとき、そこから、任意の\(x,y\in A\)に対して、\begin{equation*}x<y\Leftrightarrow \left[ x\leq y\wedge x\not=y\right] \end{equation*}を満たすものとして狭義全順序\(<\)を定義するということです。このとき、両者の間には、任意の\(x,y\in A\)について、\begin{equation*}x\leq y\Leftrightarrow \left[ x<y\vee x=y\right] \end{equation*}という関係もまた成り立ちます。

 

全順序と狭義全順序に関する推移律

全順序や狭義全順序はそれぞれ推移律を満たしますが、両者の間にも以下が成り立ちます。

命題(全順序と狭義全順序に関する推移律)
集合\(A\)上の全順序\(\leq \)が与えられたとき、任意の\(x,y\in A\)に対して、\begin{equation*}x<y\Leftrightarrow x\leq y\wedge x\not=y
\end{equation*}を満たすものとして定義される\(A\)上の二項関係\(<\)は狭義全順序である。このとき、\begin{eqnarray*}&&\left( a\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge
y<z\right) \Rightarrow x<z\right] \\
&&\left( b\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge y\leq
z\right) \Rightarrow x<z\right] \end{eqnarray*}がともに成り立つ。

証明

プレミアム会員専用コンテンツです
ログイン】【会員登録

関連知識

Mailで保存
Xで共有

質問とコメント

プレミアム会員専用コンテンツです

会員登録

有料のプレミアム会員であれば、質問やコメントの投稿と閲覧、プレミアムコンテンツ(命題の証明や演習問題とその解答)へのアクセスなどが可能になります。

ワイズのユーザーは年齢・性別・学歴・社会的立場などとは関係なく「学ぶ人」として対等であり、お互いを人格として尊重することが求められます。ユーザーが快適かつ安心して「学ぶ」ことに集中できる環境を整備するため、広告やスパム投稿、他のユーザーを貶めたり威圧する発言、学んでいる内容とは関係のない不毛な議論などはブロックすることになっています。詳細はガイドラインをご覧ください。

誤字脱字、リンク切れ、内容の誤りを発見した場合にはコメントに投稿するのではなく、以下のフォームからご連絡をお願い致します。

プレミアム会員専用コンテンツです
ログイン】【会員登録