WIIS

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

半順序(半順序集合)

目次

< 前のページ
Share on twitter
Twitterで共有
Share on email
メールで共有

半順序関係

集合\(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[ R\left( x,y\right) \wedge
R\left( y,x\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] \end{eqnarray*}が成り立つ場合には、このような\(R\)を半順序(partial order)や順序(order)などと呼びます。半順序を規定する以上の3つの性質(反射律・反対称律・推移律)を総称して順序の公理(axiom of order)と呼びます。また、要素\(x,y\in A\)を任意に選んだとき、半順序\(R\)のもとで\(x\)と\(y\)が関係を持つ場合には、すなわち\(R\left( x,y\right) \)が成り立つ場合には、\(x\)\(y\)以下(\(x\) is less than or euqal to \(y\))、\(y\)\(x\)以上(\(y\) is greater than oreual to \(x\))、または\(x\)\(y\)を超えない(\(x\) is not greater than \(y\))などと言います。

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

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

 

半順序の具体例

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

例(実数の大小関係)
すべての実数からなる集合\(\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\)を定義します。\(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\)を定義します。\(R\)は半順序です(演習問題)。
例(自然数の整除関係)
すべての自然数からなる集合\(\mathbb{N} \)が与えられたとき、それぞれの順序対\(\left(x,y\right) \in \mathbb{N} \times \mathbb{N} \)に対して、\begin{equation*}R\left( x,y\right) \Leftrightarrow x|y
\end{equation*}を満たすものとして\(R\)を定義します。ただし、\(x|y\)は\(y\)が\(x\)の倍数であることを表します。\(R\)は半順序です(演習問題)。
例(恒等関係)
集合\(A\)上の恒等関係\(\Delta_{A}\)は、任意の\(\left( x,y\right) \in A\times A\)について、\begin{equation*}\Delta _{A}\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして定義されます。\(\Delta _{A}\)は半順序です(演習問題)。

 

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

逆に、集合\(A\)上の二項関係\(R\)が反射律、反対称律、そして推移律の中の少なくとも1つを満たさない場合、\(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\)を定義します。同じ学年に属する異なる2人の学生\(x,y\in A\)に注目したとき、\(x\)と\(y\)が同じ学年で、\(y\)と\(x\)が同じ学年である一方で、\(x\)と\(y\)は異なる学生であるため\(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\in \mathbb{R} \)を任意に選んだとき、\(x<x\)すなわち\(R\left( x,y\right) \)は成り立たないため\(R\)は反射律を満たしません。したがって\(R\)は半順序ではありません。
例(空関係)
関係\(R\)が集合\(A\)上の空関係であるものとします。つまり、\begin{equation*}R=\phi
\end{equation*}です。\(x\in A\)を任意に選んだとき、\begin{equation*}\left( x,x\right) \not\in \phi
\end{equation*}が成り立つため\(R\)は反射律を満たしません。したがって\(R\)は半順序ではありません。
例(全体関係)
関係\(R\)が集合\(A\)上の全体関係であるものとします。つまり、\begin{equation*}R=A\times A
\end{equation*}です。異なる2つの要素\(x,y\in A\)を任意に選んだとき、\begin{equation*}\left[ \left( x,y\right) \in A\times A\wedge \left( y,x\right) \in A\times A\right] \Rightarrow x=y
\end{equation*}は偽であるため\(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\)を定義します。相似だが辺の長さが異なる2つの三角形\(x,y\in A\)に注目したとき、\(x\)と\(y\)が相似で、\(y\)と\(x\)が相似である一方で、\(x\)と\(y\)は異なる三角形であるため\(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\)を定義します。\(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\)を定義します。\(R\)が半順序であることを示してください。
証明

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

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

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

問題(恒等関係)
集合\(A\)上の恒等関係\(\Delta_{A}\)は、任意の\(\left( x,y\right) \in A\times A\)について、\begin{equation*}\Delta _{A}\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして定義されます。\(\Delta _{A}\)が半順序であることを示してください。
解答を見る

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

< 前のページ
Share on twitter
Twitterで共有
Share on email
メールで共有
RELATED KNOWLEDGE

関連知識

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

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

大小関係
実数の大小関係

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

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

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

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

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

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

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

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

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

全順序
順序部分集合

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

DISCUSSION

質問とコメント

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

関係