WIIS

教材一覧
教材一覧
教材検索
RELATION

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

目次

Share on twitter
Twitterで共有
Share on email
メールで共有

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

集合\(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*}x<y\Leftrightarrow \left( x\leq y\wedge x\not=y\right)
\end{equation*}を満たすものとして\(A\)上の二項関係\(<\)を定義します。つまり、\(x\)が\(y\)以下であるとともに\(x\)が\(y\)と異なる場合、そしてその場合にのみ\(<\)のもとで\(x\)と\(y\)が関係を持つものとして\(<\)を定義するということです。以上のように定義される\(<\)は狭義全順序になります。つまり、\(<\)は非対称律推移律に加えて三分律を満たすということ、具体的には、\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\)上の全順序\(\leq \)が与えられたとき、そこから、任意の\(x,y\in A\)に対して、\begin{equation*}x<y\Leftrightarrow \left( x\leq y\wedge x\not=y\right)
\end{equation*}を満たすものとして定義される\(A\)上の二項関係\(<\)は狭義全順序であるとともに、任意の\(x,y\in A\)に対して、\begin{equation*}x\leq y\Leftrightarrow \left( x<y\vee x=y\right)
\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*}を満たすものとして定義されるため、先の命題より、\(<\)は\(\mathbb{R} \)上の狭義全順序です。加えて、やはり先の命題より、任意の\(x,y\in \mathbb{R} \)に対して、\begin{equation*}x\leq y\Leftrightarrow \left( x<y\vee x=y\right)
\end{equation*}という関係が成り立ちます。

 

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

集合\(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*}x\leq y\Leftrightarrow \left[ x<y\vee x=y\right] \end{equation*}を満たすものとして\(A\)上の二項関係\(\leq \)を定義します。つまり、\(x\)が\(y\)より小さいか、または\(x\)と\(y\)が一致するか、その少なくとも一方が成り立つ場合、そしてその場合にのみ\(\leq \)のもとで\(x\)と\(y\)が関係を持つものとして\(\leq \)を定義するということです。以上のように定義される\(\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*}が成り立つということです。

命題(狭義全順序から生成される全順序)
集合\(A\)上の狭義全順序\(<\)が与えられたとき、そこから、任意の\(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 \left( x\leq y\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=y\right)
\end{equation*}という関係を満たすため、直前の命題より\(\leq \)は\(\mathbb{R} \)上の全順序です。加えて、やはり直前の命題より、任意の\(x,y\in \mathbb{R} \)に対して、\begin{equation*}x<y\Leftrightarrow \left( x\leq y\wedge x\not=y\right)
\end{equation*}という関係が成り立ちますが、これは\(<\)の定義に他なりません。

 

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

以上の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 \left[ x\leq y\wedge x\not=y\right] \end{equation*}を満たすものとして\(X\)上の狭義全順序\(<\)を定義する。このとき、\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*}がともに成り立つ。

証明

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

Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

全順序
集合の濃度の大小関係

集合Aから集合Bへの単射が存在する場合、Aの濃度はBの濃度以下であると言います。集合の大小関係を二項関係と解釈したとき、これは反射律・反対称律・推移律・完備律を満たす全順序関係です。

全順序
全順序(全順序集合)

反射律、反対称律、推移律、完備律を満たす二項関係、すなわち完備律を満たす半順序を全順序や線型順序などと呼びます。全順序を定義した上で、全順序の具体例を提示します。

狭義全順序
狭義全順序(狭義全順序集合)

非対称律、推移律、三分律を満たす二項関係、すなわち三分律を満たす狭義半順序を狭義全順序や狭義線型順序などと呼びます。狭義全順序を定義した上で、その具体例を提示します。

ハッセ図
ハッセ図(有向グラフと順序)

有向グラフを用いることにより半順序集合を視覚的に表現できます。加えて、半順序の性質を利用することにより、有向グラフを簡略化したハッセ図と呼ばれる図を得ることができます。

全順序
順序部分集合

順序集合A上に定義されている順序のもとで、Aの非空な部分集合Xが順序集合になっている場合、XをAの順序部分集合と呼びます。

全順序
整列順序関係(整列集合)

全順序集合の任意の非空な部分集合が最小限を持つ場合、このような全順序集合を整列集合と呼びます。また、整列集合上に定義された全順序を整列関係と呼びます。

DISCUSSION

質問とコメント

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

関係