WIIS

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

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

目次

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

狭義半順序関係

集合\(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] \end{eqnarray*}がともに成り立つ場合には、このような\(R\)を狭義半順序(strict partial order)や狭義順序(strict order)などと呼びます。要素\(x,y\in A\)を任意に選んだとき、狭義半順序\(R\)のもとで\(x\)と\(y\)が関係を持つ場合には、すなわち\(R\left( x,y\right) \)が成り立つ場合には、\(x\)\(y\)より小さい(\(x\) is less than \(y\))や、\(y\)\(x\)より大きい(\(y\) is greater than \(x\))などと言います。

多くの場合、狭義半順序\(<\)で表記します。つまり、集合\(A\)上の狭義半順序\(R\)が与えられたとき、任意の\(x,y\in A\)について、\begin{equation*}x<y\Leftrightarrow 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] \end{eqnarray*}となります。

集合\(A\)上に狭義半順序\(<\)が定義されているとき、これを狭義半順序集合(strict partially ordered set)や狭義順序集合(strict ordered set)などと呼び、\begin{equation*}\left( A,<\right)
\end{equation*}で表記します。ただし、狭義半順序集合について言及していることが文脈から明らかである場合にはシンプルに\(A\)で表記することもできます。

 

狭義半順序の特徴づけ

復習になりますが、集合\(A\)上の二項関係\(R\)が非対称律を満たすこととは、\begin{equation*}\forall x,y\in A:\left[ R\left( x,y\right) \Rightarrow \lnot R\left(
y,x\right) \right] \end{equation*}が成り立つことを意味し、非反射律を満たすことは、\begin{equation*}
\forall x\in A:\lnot R\left( x,x\right)
\end{equation*}が成り立つことを意味し、反対称律を満たすこととは、\begin{equation*}
\forall x,y\in A:\left[ R\left( x,y\right) \wedge R\left( y,x\right)
\Rightarrow x=y\right] \end{equation*}が成り立つことを意味します。さらに復習ですが、集合\(A\)上の二項関係\(R\)が非対称律を満たすことと、非反射律と反対称律をともに満たすことは必要十分です。以上を踏まえると、狭義半順序を以下のように定義することもできます。

命題(狭義半順序の特徴づけ)
集合\(A\)上の二項関係\(R\)が非反射律、反対称律、そして推移律を満たすことは、すなわち、\begin{eqnarray*}&&\left( a\right) \ \forall x\in A:\lnot R\left( x,x\right) \\
&&\left( b\right) \ \forall x,y\in A:\left[ R\left( x,y\right) \wedge
R\left( y,x\right) \Rightarrow x=y\right] \\
&&\left( c\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] \end{eqnarray*}をすべて満たすことは、\(R\)が狭義半順序であるための必要十分条件である。

 

狭義半順序の具体例

以下が狭義順序の具体例です。

例(実数の狭義大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、任意の\(x,y\in \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x<y
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)は狭義半順序です(演習問題)。
例(集合の狭義包含関係)
すべての集合を要素として持つ集合族\(\mathfrak{A}\)が与えられたとき、それぞれの\(\left( A,B\right) \in \mathfrak{A}\times \mathfrak{A}\)について、\begin{equation*}R\left( A,B\right) \Leftrightarrow A\varsubsetneq B
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(\varsubsetneq \)は狭義の包含関係(真部分集合)を表す記号であり、これは包含関係\(\subset \)を用いて、\begin{equation*}A\varsubsetneq B\Leftrightarrow A\subset B\wedge A\not=B
\end{equation*}として定義されます。\(R\)は狭義半順序です(演習問題)。
例(空関係)
関係\(R\)が集合\(A\)上の空関係であるものとします。つまり、\begin{equation*}R=\phi
\end{equation*}です。\(R\)は狭義半順序です(演習問題)。

 

狭義半順序ではない二項関係の具体例

逆に、集合\(A\)上の二項関係\(R\)が非対称律と反射律の少なくとも一方を満たさない場合、\(R\)は狭義半順序ではありません。

以下は狭義半順序ではない二項関係の例です。

例(親子関係)
ヒトの集合\(A\)が与えられたとき、それぞれの順序対\(\left( x,y\right) \in A\times A\)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\text{は}y\text{の子供}
\end{equation*}を満たすものとして\(R\)を定義します。ヒト\(x,y,z\in A\)を任意に選んだとき、\(x\)が\(y\)の子供であるとともに\(y\)が\(z\)の子供であるとき\(x\)は\(z\)の子供ではありません。したがって\(R\)は推移律を満たしません。したがって\(R\)は狭義半順序ではありません。
例(実数の相等関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして\(R\)を定義します。\(x=y\)を満たす実数\(x,y\in \mathbb{R} \)について、\begin{equation*}x=y\wedge y=x
\end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではありません。
例(実数の非相等関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\not=y
\end{equation*}を満たすものとして\(R\)を定義します。\(1,2\in \mathbb{R} \)に注目したとき、\begin{equation*}1\not=2\wedge 2\not=1\wedge 1=1
\end{equation*}が成り立つため\(R\)は推移性を満たしません。したがって\(R\)は狭義半順序ではありません。
例(実数の大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(R\)を定義します。\(x=y\)を満たす実数\(x,y\in \mathbb{R} \)について、\begin{equation*}x\leq y\wedge y\leq x
\end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではありません。
例(集合の包含関係)
すべての集合を要素として持つ集合族\(\mathfrak{A}\)が与えられたとき、それぞれの\(\left( A,B\right) \in \mathfrak{A}\times \mathfrak{A}\)について、\begin{equation*}R\left( A,B\right) \Leftrightarrow A\subset B
\end{equation*}を満たすものとして\(R\)を定義します。\(A=B\)を満たす集合\(A,B\in \mathfrak{A}\)について、\begin{equation*}A\subset B\wedge B\subset A
\end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではありません。
例(恒等関係)
集合\(A\)上の恒等関係\(\Delta_{A}\)は反対称律を満たします。実際、\(x=y\)を満たす要素\(x,y\in A\)について、恒等関係の定義より、\begin{equation*}\left( x,y\right) \in \Delta _{A}\wedge \left( y,x\right) \in \Delta _{A}
\end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではありません。
例(全体関係)
関係\(R\)が集合\(A\)上の全体関係であるものとします。つまり、\begin{equation*}R=A\times A
\end{equation*}です。このとき、\begin{equation*}
\exists x,y\in A:\left[ \left( x,y\right) \in A\times A\wedge \left(
y,x\right) \in A\times A\right] \end{equation*}が成り立つため\(R\)は非対称律を満たしません。したがって\(R\)は狭義半順序ではありません。

 

演習問題

問題(実数の狭義大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{R} \times \mathbb{R} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x<y
\end{equation*}を満たすものとして\(R\)を定義します。\(R\)が狭義半順序であることを示してください。
証明

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

問題(集合の狭義包含関係)
すべての集合を要素として持つ集合族\(\mathfrak{A}\)が与えられたとき、それぞれの\(\left( A,B\right) \in \mathfrak{A}\times \mathfrak{A}\)について、\begin{equation*}R\left( A,B\right) \Leftrightarrow A\varsubsetneq B
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(\varsubsetneq \)は狭義の包含関係(真部分集合)を表す記号であり、これは包含関係\(\subset \)を用いて、\begin{equation*}A\varsubsetneq B\Leftrightarrow A\subset B\wedge A\not=B
\end{equation*}として定義されます。\(R\)は狭義半順序であることを示してください。
証明

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

問題(空関係)
関係\(R\)が集合\(A\)上の空関係であるものとします。つまり、\begin{equation*}R=\phi
\end{equation*}です。\(R\)が狭義半順序であることを示してください。
証明

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

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

関連知識

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

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

大小関係
実数の大小関係

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

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

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

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

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

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

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

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

半順序から狭義半順序を生成する方法や、逆に、狭義半順序から半順序を生成する方法を解説するとともに、両者の間に成立する関係を紹介します。

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

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

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

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

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

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

全順序
順序部分集合

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

DISCUSSION

質問とコメント

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

関係