WIIS

順序集合

半順序(半順序集合)の定義と具体例

目次

Mailで保存
Xで共有

半順序関係

集合\(A\)上の二項関係\(R\)が与えられているものとします。つまり、\begin{equation*}R\subset A\times A
\end{equation*}です。特に、集合\(A\)上の二項関係\(R\)が反射律反対称律、そして推移律を満たすことを公理として認める場合には、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:\left( x,x\right) \in R \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left\{ \left[ \left( x,y\right)
\in R\wedge \left( y,x\right) \in R\right] \Rightarrow x=y\right\} \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left\{ \left[ \left( x,y\right)
\in R\wedge \left( y,z\right) \in R\right] \Rightarrow \left( x,z\right) \in
R\right\}
\end{eqnarray*}が成り立つ場合には、このような二項関係\(R\)を半順序(partial order)や順序(order)などと呼びます。半順序を規定する以上の3つの性質(反射律・反対称律・推移律)を総称して順序の公理(axiom of order)と呼びます。

多くの場合、半順序を表す記号として\(\leq \)を採用します。つまり、集合\(A\)上の半順序\(R\)が与えられたとき、任意の\(x,y\in A\)について、\begin{equation*}x\leq y\Leftrightarrow \left( x,y\right) \in R
\end{equation*}を満たすものとして記号\(x\leq y\)の意味を定義するということです。この場合、任意の\(x,y\in A\)について、\begin{equation*}\lnot \left( x\leq y\right) \Leftrightarrow \left( x,y\right) \not\in R
\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 \)が与えられたとき、要素\(x,y\in A\)について\(x\leq y\)が成り立つ場合には、\(x\)\(y\)以下(\(x\) is less than or euqal to \(y\))であるとか、\(y\)\(x\)以上(\(y\) is greater than or eual to \(x\))であるとか、\(x\)\(y\)を超えない(\(x\) is not greaterthan \(y\))などと言います。

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

 

半順序の具体例:実数の大小関係

実数どうしを比較する通常の大小関係\(\leq \)は実数集合\(\mathbb{R} \)上に定義された二項関係です。実際、大小関係\(\leq \)が与えられたとき、任意の実数\(x,y\in \mathbb{R} \)について、以下の関係\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\begin{equation*}R\subset \mathbb{R} \times \mathbb{R} \end{equation*}を定義可能です。つまり、実数\(x,y\)について、\(x\)が\(y\)以下である場合、そしてその場合にのみ\(\left( x,y\right) \in R\)が成り立つものとして\(\mathbb{R} \)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を大小関係\(\leq \)と同一視することにより、大小関係\(\leq \)を\(\mathbb{R} \)上の二項関係とみなすことができます。

実数集合\(\mathbb{R} \)上に定義された大小関係\(\leq \)は\(\mathbb{R} \)上の半順序です。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in \mathbb{R} :x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in \mathbb{R} :\left[ \left( x\leq y\wedge y\leq x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in \mathbb{R} :\left[ \left( x\leq y\wedge y\leq z\right) \Rightarrow x\leq z\right] \end{eqnarray*}が成り立ちます。

命題(大小関係は半順序)
実数集合\(\mathbb{R} \)上に定義された大小関係\(\leq \)は\(\mathbb{R} \)上の半順序である。
証明

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

 

半順序の具体例:集合の包含関係

全体集合\(U\)を任意に選んだ上で、その部分集合どうしの包含関係を判定する状況を想定します。任意の集合\(A,B\in 2^{U}\)について、以下の関係\begin{equation*}\left( A,B\right) \in R\Leftrightarrow A\subset B
\end{equation*}を満たすものとして\(2^{U}\)上の二項関係\begin{equation*}R\subset 2^{U}\times 2^{U}
\end{equation*}を定義します。ただし、\(2^{U}\)は\(U\)のべき集合、すなわち\(U\)のすべての部分集合を要素として持つ集合族です。つまり、\(U\)の部分集合\(A,B\)について、\(A\)が\(B\)の部分集合である場合、そしてその場合にのみ\(\left( A,B\right) \in R\)が成り立つものとして\(2^{U}\)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を包含関係\(\subset \)と同一視することにより、包含関係\(\subset \)を\(2^{U}\)上の二項関係とみなすことができます。

集合\(U\)のべき集合\(2^{U}\)上に定義された包含関係\(\subset \)は\(2^{U}\)上の半順序です。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall A\in 2^{U}:A\subset A \\
&&\left( O_{2}\right) \ \forall A,B\in 2^{U}:\left[ \left( A\subset B\wedge
B\subset A\right) \Rightarrow A=B\right] \\
&&\left( O_{3}\right) \ \forall A,B,C\in 2^{U}:\left[ \left( A\subset
B\wedge B\subset C\right) \Rightarrow A\subset C\right] \end{eqnarray*}が成り立ちます。

命題(包含関係は半順序)
集合\(U\)のべき集合\(2^{U}\)上に定義された包含関係\(\subset \)は\(2^{U}\)上の半順序である。
解答を見る

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

 

半順序の具体例:自然数の整除関係

2つの自然数\(m,n\in \mathbb{N} \)について、\(m\)が\(n\)の倍数(\(n\)が\(m\)の約数)であることを、\begin{equation*}n|m
\end{equation*}と表記するものと定めます。これを整除関係と呼びます。その上で、任意の自然数\(m,n\in \mathbb{N} \)について、以下の関係\begin{equation*}\left( m,n\right) \in R\Leftrightarrow n|m
\end{equation*}を満たすものとして\(\mathbb{N} \)上の二項関係\begin{equation*}R\subset \mathbb{N} \times \mathbb{N} \end{equation*}を定義します。つまり、自然数\(m,n\)について、\(m\)が\(n\)の倍数である場合、そしてその場合にのみ\(\left( m,n\right) \in R\)が成り立つものとして\(\mathbb{N} \)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を整除関係\(|\)と同一視することにより、整除関係\(|\)を\(\mathbb{N} \)上の二項関係とみなすことができます。

自然数集合\(\mathbb{N} \)上に定義された整除関係\(|\)は\(\mathbb{N} \)上の半順序です。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall m\in \mathbb{N} :m|m \\
&&\left( O_{2}\right) \ \forall m,n\in \mathbb{N} :\left[ \left( n|m\wedge m|n\right) \Rightarrow m=n\right] \\
&&\left( O_{3}\right) \ \forall l,m,n\in \mathbb{N} :\left[ \left( n|m\wedge m|l\right) \Rightarrow n|l\right] \end{eqnarray*}が成り立ちます。

命題(整除関係は半順序)
自然数集合\(\mathbb{N} \)上に定義された整除関係\(|\)は\(\mathbb{N} \)上の半順序である。
解答を見る

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

 

半順序の具体例:恒等関係

集合\(A\)が与えられたとき、任意の要素\(x,y\in A\)について、以下の関係\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x=y
\end{equation*}を満たすものとして\(A\)上の二項関係\begin{equation*}R\subset A\times A
\end{equation*}を定義します。このような関係\(R\)を恒等関係(identity relation)と呼びます。つまり、要素\(x,y\)について、\(x\)と\(y\)が等しい場合、そしてその場合にのみ\(\left( x,y\right) \in R\)が成り立つものとして\(A\)上の二項関係\(R\)を定義するということです。この二項関係\(R\)を相等関係\(=\)と同一視することにより、相等関係\(=\)を\(\mathbb{N} \)上の二項関係とみなすことができます。

集合\(A\)上に定義された恒等関係\(=\)は\(A\)上の半順序です。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x=x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x=y\wedge y=x\right)
\Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x=y\wedge
y=z\right) \Rightarrow x=z\right] \end{eqnarray*}が成り立ちます。

命題(恒等関係は半順序)
集合\(A\)上に定義された恒等関係\(=\)は\(A\)上の半順序である。
証明

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

 

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

逆に、集合\(A\)上の二項関係\(R\)が順序の公理を満たさない場合、すなわち\(R\)が反射律、反対称律、そして推移律の中の少なくとも1つを満たさない場合、\(R\)は半順序ではありません。

例(集団への所属関係)
ある学校の生徒からなる集合\(A\)が与えられたとき、任意の学生\(x,y\in A\)について、\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の半順序ではありません(演習問題)。
例(実数の狭義大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、任意の実数\(x,y\in \mathbb{N} \)について、\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x<y
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\(R\)を定義します。この\(R\)は\(\mathbb{R} \)上の半順序ではありません(演習問題)。
例(三角形の相似関係)
平面上のすべての三角形からなる集合\(A\)が与えられたとき、任意の三角形\(x,y\in A\)について、\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x\text{と}y\text{は相似}
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の半順序ではありません(演習問題)。
例(空関係)
集合\(A\)を任意に選びます。空集合は任意の集合の部分集合であるため、\begin{equation*}\phi \subset A\times A
\end{equation*}が成り立ちますが、以上の事実は\(\phi \)が\(A\)上の二項関係であることを意味します。空集合\(\phi \)を二項関係とみなした場合、これを空関係と呼びます。空関係\(\phi \)は\(A\)上の半順序ではありません(演習問題)。
例(全体関係)
集合\(A\)を任意に選びます。このとき、\begin{equation*}A\times A\subset A\times A
\end{equation*}が成り立ちますが、以上の事実は\(A\times A\)が\(A\)上の二項関係であることを意味します。直積\(A\times A\)を二項関係とみなした場合、これを全体関係と呼びます。全体関係\(A\times A\)は\(A\)上の半順序ではありません(演習問題)。

 

演習問題

問題(集団への所属関係)
ある学校の生徒からなる集合\(A\)が与えられたとき、任意の学生\(x,y\in A\)について、\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x\text{は}y\text{と同じ学年}
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の半順序ではないことを示してください。
解答を見る

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

問題(実数の狭義大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、任意の実数\(x,y\in \mathbb{N} \)について、\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x<y
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\(R\)を定義します。ただし、\(<\)は狭義の大小関係であり、\(x<y\)は\(x\)が\(y\)よりも小さいことを意味します。この\(R\)は\(\mathbb{R} \)上の半順序ではないことを示してください。
解答を見る

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

問題(三角形の相等関係)
平面上のすべての三角形からなる集合\(A\)が与えられたとき、任意の三角形\(x,y\in A\)について、\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x\text{と}y\text{は相似}
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の半順序ではないことを示してください。
解答を見る

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

問題(空関係)
集合\(A\)を任意に選びます。空集合は任意の集合の部分集合であるため、\begin{equation*}\phi \subset A\times A
\end{equation*}が成り立ちますが、これは\(\phi \)が\(A\)上の二項関係であることを意味します。空集合\(\phi \)を二項関係とみなした場合、これを空関係と呼びます。空関係\(\phi \)は\(A\)上の半順序ではないことを示してください。
解答を見る

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

問題(全体関係)
集合\(A\)を任意に選びます。このとき、\begin{equation*}A\times A\subset A\times A
\end{equation*}が成り立ちますが、これは直積\(A\times A\)が\(A\)上の二項関係であることを意味します。直積\(A\times A\)を二項関係とみなした場合、これを全体関係と呼びます。全体関係\(A\times A\)は\(A\)上の半順序ではないことを示してください。
解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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