WIIS

順序集合

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

目次

Mailで保存
Xで共有

狭義半順序関係

集合\(A\)上の二項関係\(R\)が与えられているものとします。つまり、\begin{equation*}R\subset A\times A
\end{equation*}です。特に、集合\(A\)上の二項関係\(R\)が非対称律推移律を満たすことを公理として認める場合には、すなわち、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ \left( x,y\right) \in
R\Rightarrow \left( y,x\right) \not\in R\right] \\
&&\left( S_{2}\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\)を狭義半順序(strict partial order)や狭義順序(strict order)などと呼びます。狭義半順序を規定する以上の2つの性質(非対称律・推移律)を総称して狭義順序の公理(axiom of strict order)と呼びます。

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

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

 

狭義半順序の特徴づけ

集合\(A\)上の二項関係\(R\)が非対称律を満たすこととは、\begin{equation*}\forall x,y\in A:\left[ \left( x,y\right) \in R\Rightarrow \left( y,x\right)
\not\in R\right] \end{equation*}が成り立つことを意味し、非反射律を満たすことは、\begin{equation*}
\forall x\in A:\left( x,x\right) \not\in R
\end{equation*}が成り立つことを意味し、反対称律を満たすこととは、\begin{equation*}
\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\}
\end{equation*}が成り立つことを意味します。

集合\(A\)上の二項関係\(R\)が非対称律を満たすことと、\(R\)が非反射律と反対称律をともに満たすことは必要十分です。以上を踏まえると、狭義半順序を以下のように定義することもできます。

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

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

狭義半順序の記号\(<\)を用いて上の命題の主張を表現すると、狭義順序の公理は、\begin{eqnarray*}&&\left( a\right) \ \forall x\in A:\lnot \left( x<x\right) \\
&&\left( b\right) \ \forall x,y\in A:\left[ \left( x<y\wedge y<x\right)
\Rightarrow x=y\right] \\
&&\left( c\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge y<z\right)
\Rightarrow x<z\right] \end{eqnarray*}と必要十分であるということになります。

 

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

実数どうしを比較する通常の狭義大小関係\(<\)は実数集合\(\mathbb{R} \)上に定義された二項関係です。実際、狭義大小関係\(<\)が与えられたとき、任意の実数\(x,y\in \mathbb{R} \)について、以下の関係\begin{equation*}\left( x,y\right) \in R\Leftrightarrow x<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\)を狭義大小関係\(<\)と同一視することにより、狭義大小関係\(<\)を\(\mathbb{R} \)上の二項関係とみなすことができます。

実数集合\(\mathbb{R} \)上に定義された狭義大小関係\(<\)は\(\mathbb{R} \)上の狭義半順序です。つまり、\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*}が成り立ちます。

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

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

 

狭義半順序の具体例:狭義の包含関係

2つの集合\(A,B\)について、\(A\)が\(B\)の部分集合である一方で\(A\)は\(B\)とは異なる集合である場合、すなわち、\begin{equation*}A\subset B\wedge A\not=B
\end{equation*}が成り立つ場合、\(A\)を\(B\)の真部分集合と呼びます。その上で、\(A\)が\(B\)の真部分集合であることを、\begin{equation*}A\varsubsetneq B
\end{equation*}で表記します。これを狭義包含関係と呼びます。

全体集合\(U\)を任意に選んだ上で、その部分集合どうしの狭義包含関係(真部分集合)を判定する状況を想定します。任意の集合\(A,B\in 2^{U}\)について、以下の関係\begin{equation*}\left( A,B\right) \in R\Leftrightarrow A\varsubsetneq 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\)を狭義包含関係\(\varsubsetneq \)と同一視することにより、狭義包含関係\(\varsubsetneq \)を\(2^{U}\)上の二項関係とみなすことができます。

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

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

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

 

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

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

例(親子関係)
すべての人間からなる集合\(A\)が与えられたとき、任意の人間\(x,y\in A\)について、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\text{は}y\text{の子供}
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の狭義半順序ではありません(演習問題)。
例(実数の相等関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、任意の実数\(x,y\in \mathbb{R} \)について、\begin{equation*}R\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\(R\)を定義します。この\(R\)は\(\mathbb{R} \)上の狭義半順序ではありません(演習問題)。
例(実数の非相等関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、任意の実数\(x,y\in \mathbb{R} \)について、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\not=y
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\(R\)を定義します。この\(R\)は\(\mathbb{R} \)上の狭義半順序ではありません(演習問題)。
例(実数の大小関係)
すべての実数からなる集合\(\mathbb{R} \)が与えられたとき、任意の実数\(x,y\in \mathbb{R} \)について、\begin{equation*}R\left( x,y\right) \Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(\mathbb{R} \)上の二項関係\(R\)を定義します。この\(R\)は\(\mathbb{R} \)上の狭義半順序ではありません(演習問題)。
例(集合の包含関係)
集合\(U\)のベキ集合\(2^{U}\)が与えられたとき、任意の集合\(A,B\in 2^{U}\)について、\begin{equation*}R\left( A,B\right) \Leftrightarrow A\subset B
\end{equation*}を満たすものとして\(2^{U}\)上の二項関係\(R\)を定義します。この\(R\)は\(2^{U}\)上の狭義半順序ではありません(演習問題)。
例(恒等関係)
集合\(A\)が与えられたとき、任意の\(x,y\in A\)について、\begin{equation*}R\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(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\)を任意に選びます。このとき、\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*}R\left( x,y\right) \Leftrightarrow x\text{は}y\text{の子供}
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(A\)上の狭義半順序ではないことを示してください。
解答を見る

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

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

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

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

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

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

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

問題(集合の包含関係)
集合\(U\)のベキ集合\(2^{U}\)が与えられたとき、任意の集合\(A,B\in 2^{U}\)について、\begin{equation*}R\left( A,B\right) \Leftrightarrow A\subset B
\end{equation*}を満たすものとして\(2^{U}\)上の二項関係\(R\)を定義します。この\(R\)は\(2^{U}\)上の狭義半順序ではないことを示してください。
解答を見る

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

問題(恒等関係)
集合\(A\)が与えられたとき、任意の\(x,y\in A\)について、\begin{equation*}R\left( x,y\right) \Leftrightarrow x=y
\end{equation*}を満たすものとして\(A\)上の二項関係\(R\)を定義します。この\(R\)は\(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\)を任意に選びます。空集合は任意の集合の部分集合であるため、\begin{equation*}\phi \subset A\times A
\end{equation*}が成り立ちますが、以上の事実は\(\phi \)が\(A\)上の二項関係であることを意味します。空集合\(\phi \)を二項関係とみなした場合、これを空関係と呼びます。空関係\(\phi \)は\(A\)上の半順序であることを示してください。
解答を見る

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

関連知識

Mailで保存
Xで共有

質問とコメント

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

会員登録

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

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

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

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