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] \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] \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*}という関係が成り立ちます。

例(集合の包含関係と狭義包含関係)
すべての集合を要素として持つ集合族\(\mathfrak{A}\)上に定義された包含関係\(\subset \)は半順序です。一方、狭義包含関係\(\varsubsetneq \)はそれぞれの\(A,B\in \mathfrak{A}\)に対して、\begin{equation*}A\varsubsetneq B\Leftrightarrow \left( A\subset B\wedge A\not=B\right)
\end{equation*}を満たすものとして定義されるため、先の命題より、\(\varsubsetneq \)は\(\mathfrak{A}\)上の狭義半順序です。加えて、やはり先の命題より、任意の\(A,B\in \mathfrak{A}\)に対して、\begin{equation*}A\subset B\Leftrightarrow \left( A\varsubsetneq B\vee A=B\right)
\end{equation*}という関係が成り立ちます。

 

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

集合\(A\)上の二項関係\(<\)が狭義半順序であるものとします。つまり、\(<\)は非対称律と推移律を満たすということ、具体的には、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow \lnot P\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] \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] \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*}という関係が成り立ちますが、これは\(<\)の定義に他なりません。
例(集合の包含関係と狭義包含関係)
すべての集合を要素として持つ集合族\(\mathfrak{A}\)上に定義された狭義包含関係\(\varsubsetneq \)は\(\mathfrak{A}\)上の狭義半順序です。先に示したように、包含関係\(\subset \)はそれぞれの\(A,B\in \mathfrak{A}\)に対して、\begin{equation*}A\subset B\Leftrightarrow \left( A\varsubsetneq B\vee A=B\right)
\end{equation*}という関係を満たすため、直前の命題より\(\subset \)は\(\mathfrak{A}\)上の半順序です。加えて、やはり直前の命題より、任意の\(A,B\in \mathfrak{A}\)に対して、\begin{equation*}A\varsubsetneq B\Leftrightarrow \left( A\subset B\wedge A\not=B\right)
\end{equation*}と言う関係が成り立ちますが、これは\(\varsubsetneq \)の定義に他なりません。

 

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

以上の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*}を満たすものとして\(A\)上の狭義半順序\(<\)を定義する。その上で、\(x,y\in A\)を任意に選んだとき、以下の真理値表が得られる。ただし、\(1\)は真を表す真理値であり、\(0\)は偽を表す真理値である。

$$\begin{array}{cccccc}\hline
\quad & x\leq y & y\leq x & x=y & x<y & y<x \\ \hline
\left( a\right) & 1 & 1 & 1 & 0 & 0 \\ \hline
\left( b\right) & 1 & 0 & 0 & 1 & 0 \\ \hline
\left( c\right) & 0 & 1 & 0 & 0 & 1 \\ \hline
\left( d\right) & 0 & 0 & 0 & 0 & 0 \\ \hline
\end{array}$$

表:真理値表
証明

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

集合\(A\)上の二項関係\(\leq \)が与えられたとき、2つの要素\(x,y\in A\)を任意に選ぶと、\(x\leq y\)と\(y\leq x\)の真理値表の組み合わせに応じて論理的には上の真理値表にあるような\(\left( a\right) \)から\(\left( d\right) \)までの4通りの場合が起こり得ます。\(\left( a\right) \)は\(x\)と\(y\)が等しい場合、\(\left( b\right) \)は\(x\)が\(y\)より小さい場合、\(\left( c\right) \)は\(y\)が\(x\)より小さい場合に相当する一方で、\(\left( d\right) \)では\(x\)と\(y\)の関係に関する情報が存在せず、この場合にはそもそも\(x\)と\(y\)を比較することができません。

 

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

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

命題(半順序と狭義半順序に関する推移律)
集合\(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

関連知識

半順序
n次元空間上の標準的順序

n次元空間上に定義される標準的順序と呼ばれる二項関係は半順序である一方で全順序ではありません。

大小関係
実数の大小関係

実数の集合 R 上に実数どうしの大小関係を比較する順序を定義した上で、それが全順序としての性質満たすことを公理として定めます。

標準的狭義順序
n次元空間上の標準的狭義順序

n次元空間上に定義される標準的狭義順序と呼ばれる二項関係は狭義順序である一方で狭義全順序ではありません。

狭義大小関係
実数の狭義大小関係

実数の集合 R 上に定義された大小関係を用いて、狭義大小関係と呼ばれる新たな順序を間接的に定義します。狭義大小関係は非対称律、推移律、三分律を満たす狭義全順序です。

半順序
半順序(半順序集合)

反射律、反対称律、推移律を満たす二項関係を半順序や順序などと呼びます。また、半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素以下であると言います。半順序を定義した上で、半順序の具体例を提示します。

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

非対称律と推移律を満たす二項関係を狭義半順序や狭義順序などと呼びます。また、狭義半順序のもとで2つの要素が関係を持つとき、一方の要素は他方の要素より小さいと言います。狭義半順序を定義した上で、狭義半順序の具体例を提示します。

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

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

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

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

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

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

全順序
順序部分集合

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

DISCUSSION

質問とコメント

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

関係