集合.11　二項関係.1　順序

ホーム
大学数学, 集合と位相
集合.11　二項関係.1　順序

2018.06.15

二項関係

今回からは二項関係というものを考えていきます。二項関係というと聞き慣れないかもしれませんが、要するに名前の通り２つの項の関係です。恒等関係（＝で結ばれる関係）とか、合同関係（≡で結ばれる関係）とかが代表的な二項関係ですね。

一般的には、次のような小難しい定義になります。

◆定義

$X,Y$ を集合とし、 $X \times Y$ の部分集合 $G(R)$ とする。三つ組 $(X,Y,G(R))$ を $X$ と $Y$ との二項関係 $R$ という。 $(x,y) \in X \times Y$ について、 $(x,y) \in G(R)$ であるとき、 $x$ と $y$ は $R$ 関係を持つといい、 $xRy$ などと書く。特に、 $X =Y$ のとき、 $X$ 上の二項関係という。

というのが二項関係の最も一般的な定義ですが、こんな一般的なことは結構どうでもいいです。

実際によく使われる２種類の二項関係を押さえておけば大体OKです。それが順序と同値関係です。

同値関係は次回やるとして、今回は順序について見ていきましょう。

順序

順序というのは、その名の通り順序を表す関係を一般的に定義したものです。順序というものが満たすべき性質をまとめて定義としています。次のようになります。

◆定義

集合 $X$ 上に定義された二項関係 $\leq$ が順序(あるいは順序関係)であるとは、次を満たすことを言う。

・反射律　 $\forall x \in X,x \leq x$
・推移律　 $\forall x,y,z \in X , ( (x \leq y) \land (y \leq z)) \Rightarrow (x \leq z)$
・反対称律　 $\forall x,y \in X , ( (x \leq y) \land (y \leq x)) \Rightarrow (x = y)$

順序が定義された集合のことを順序集合という。

さらに上記３つの条件に加えて次を満たすとき、全順序という。

・全順序律　 $\forall x,y \in X , (x \leq y) \lor (y \leq x)$

全順序が定義された集合のことを全順序集合という。全順序でない順序を半順序とも言う。

記号の由来にもなっている普通の実数での大小関係 $\leq$ を考えてみると、順序の典型例となっています。（自分で確かめてみて下さい。結構当たり前のことを言っています）

いくつか例を見ていきましょう。

◇例

$\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ は通常の大小関係 $\leq$ によって順序集合となります。しかもこれは全順序です。

一方で、 $\mathbb{C}$ は通常の大小関係というものを定めることができないため、このやり方では順序集合にはできません。

$\mathbb{C}$ に全順序を入れるためには、例えば次のような辞書式順序を考えます。

$x_1+y_1i \leq x_2+y_2i \overset{\mathrm{def}}{\Leftrightarrow} (x_1 < x_2) \lor ((x_1 = x_2) \land (y_1 \leq y_2))$

この種の順序は、あたかも辞書を引くかのように手前から順序を参照しているので、辞書式順序と言われています。

実際にこれが全順序であることを、一つ一つの定義に立ち戻って示してみましょう。

・反射律
$\forall x+yi \in \mathbb{C}$ とすると、
$x=x$ かつ $y=y$ なので、上の辞書式順序の定義より、
$x+yi \leq x+yi$
です。

・推移律
$\forall x_1+y_1i,x_2+y_2i,x_3+y_3i \in \mathbb{C}$ とし、 $x_1+y_1i \leq x_2+y_2i$ かつ $x_2+y_2i \leq x_3+y_3i$ が成り立っているとします。すると、上の辞書式順序の定義から、

$((x_1 < x_2) \lor ((x_1 = x_2) \land (y_1 \leq y_2))) \land ((x_2 < x_3) \lor ((x_2 = x_3) \land (y_2 \leq y_3)))$

が成り立ちます。ここから、

$(x_1 < x_3) \lor ((x_1 = x_3) \land (y_1 \leq y_3))$

を示せば、上の辞書式順序の定義から、

$x_1+y_1i \leq x_3+y_3i$

が言えます。

では、示しましょう。論理式の演算を行います。（演算のしかたは論理記号　その５を参考）

多少見やすくするために、

$A \colon x_1 < x_2$
$B \colon x_1 = x_2$
$C \colon y_1 \leq y_2$
$D \colon x_2 < x_3$
$E \colon x_2 = x_3$
$F \colon y_2 \leq y_3$

で表すと、

$((x_1 < x_2) \lor ((x_1 = x_2) \land (y_1 \leq y_2))) \land ((x_2 < x_3) \lor ((x_2 = x_3) \land (y_2 \leq y_3)))$

は、

$(A \lor ( B \land C) ) \land ( D \lor ( E \land F))$

と書けます。ここから、

$(A \lor ( B \land C) ) \land ( D \lor ( E \land F))$
$\Leftrightarrow}$
$(A \land ( D \lor ( E \land F)) ) \lor (( B \land C) \land ( D \lor ( E \land F)))$
$\Leftrightarrow}$
$(A \land D) \lor ( A \land E \land F) \lor ( B \land C \land D) \lor (B \land C \land E \land F)$
$\Rightarrow}$
$(A \land D) \lor (B \land C \land E \land F)$

$A,B,C,D,E,F$ を代入して、

$((x_1 < x_2) \land (x_2 < x_3)) \lor ((x_1 = x_2) \land (y_1 \leq y_2) \land (x_2 = x_3) \land (y_2 \leq y_3))$
$\Rightarrow}$
$(x_1 < x_3) \lor ((x_1 = x_3) \land (y_1 \leq y_3))$

したがって、推移律は成立します。

・反対称律
$\forall x_1+y_1i,x_2+y_2i \in \mathbb{C}$ とし、 $x_1+y_1i \leq x_2+y_2i$ かつ $x_2+y_2i \leq x_1+y_1i$ が成り立っているとします。すると、上の辞書式順序の定義から、

$((x_1 < x_2) \lor ((x_1 = x_2) \land (y_1 \leq y_2))) \land ((x_2 < x_1) \lor ((x_2 = x_1) \land (y_2 \leq y_1)))$

が成り立ちます。ここから、

$x_1+y_1i=x_2+y_2i$

を示しましょう。

やはり、見やすくするために、

$A \colon x_1 < x_2$
$B \colon x_1 = x_2$
$C \colon y_1 \leq y_2$
$D \colon x_2 < x_1$
$E \colon x_2 = x_1$
$F \colon y_2 \leq y_1$

とします。すると、

$((x_1 < x_2) \lor ((x_1 = x_2) \land (y_1 \leq y_2))) \land ((x_2 < x_1) \lor ((x_2 = x_1) \land (y_2 \leq y_1)))$

は、

$(A \lor ( B \land C) ) \land ( D \lor ( E \land F))$

と書けます。推移律のときと同様に論理式を変形して、

$(A \lor ( B \land C) ) \land ( D \lor ( E \land F))$
$\Rightarrow}$
$(A \land D) \lor (B \land C \land E \land F)$

$A,B,C,D,E,F$ を代入して、

$((x_1 < x_2) \land (x_2 < x_1)) \lor ((x_1 = x_2) \land (y_1 \leq y_2) \land (x_2 = x_1) \land (y_2 \leq y_1))$

ここで、 $(x_1 < x_2) \land (x_2 < x_1)$ は成り立たないので、結局、

$((x_1 < x_2) \land (x_2 < x_1)) \lor ((x_1 = x_2) \land (y_1 \leq y_2) \land (x_2 = x_1) \land (y_2 \leq y_1))$
$\Leftrightarrow}$
$(x_1 = x_2) \land (y_1 \leq y_2) \land (x_2 = x_1) \land (y_2 \leq y_1)$
$\Leftrightarrow}$
$(x_1 = x_2) \land (y_1 = y_2)$

したがって、 $x_1+y_1i=x_2+y_2i$ が成り立つので、示されました。

・全順序律
$\forall x_1+y_1i,x_2+y_2i \in \mathbb{C}$ とし、 $x_1+y_1i \leq x_2+y_2i$ または $x_2+y_2i \leq x_1+y_1i$ が成り立つことを示します。すなわち、

$((x_1 < x_2) \lor ((x_1 = x_2) \land (y_1 \leq y_2))) \lor ((x_2 < x_1) \lor ((x_2 = x_1) \land (y_2 \leq y_1)))$

を示します。

論理式の変形を行い、示すべき命題を同値変形で簡単にしていきましょう。

ここでも、

$A \colon x_1 < x_2$
$B \colon x_1 = x_2$
$C \colon y_1 \leq y_2$
$D \colon x_2 < x_1$
$E \colon x_2 = x_1$
$F \colon y_2 \leq y_1$

とします。すると、

$((x_1 < x_2) \lor ((x_1 = x_2) \land (y_1 \leq y_2))) \lor ((x_2 < x_1) \lor ((x_2 = x_1) \land (y_2 \leq y_1)))$

は

$(A \lor ( B \land C) ) \lor( D \lor ( E \land F))$

と書けます。ここから（ $B=E$ に注意して）、

$(A \lor ( B \land C) ) \lor ( D \lor ( E \land F))$
$\Leftrightarrow}$
$(A \lor D) \lor ( B \land C) \lor ( E \land F)$
$\Leftrightarrow}$
$(A \lor D) \lor ( B \land C) \lor ( B \land F)$
$\Leftrightarrow}$
$(A \lor D) \lor ( B \land (C \lor F))$
$\Leftrightarrow}$
$(A \lor D \lor B) \land (A \lor D \lor C \lor F)$

$A,B,C,D,F$ を代入して、

$((x_1 < x_2) \lor (x_2 < x_1) \lor (x_1 = x_2)) \land ((x_1 < x_2) \lor (x_2 < x_1) \lor (y_1 \leq y_2) \lor (y_2 \leq y_1))$

ここで、 $(x_1 < x_2) \lor (x_2 < x_1) \lor (x_1 = x_2)$ と $(y_1 \leq y_2) \lor (y_2 \leq y_1)$ は常に成り立つことから、この式は常に成り立ちます。

よって、示されました。

ところで、 $\mathbb{C}$ への全順序の入れ方は一つとは限りません。例えば、複素数平面上からの距離の大小で順序付けすると、これは全順序となります。式で書くと、

$\forall x_1+y_1i,x_2+y_2i \in \mathbb{C}$ について、
$x_1+y_1i \leq x_2+y_2i \overset{\mathrm{def}}{\Leftrightarrow} \sqrt{x_1^2+y_1^2} \leq \sqrt{x_2^2+y_2^2}$

実数の大小関係が全順序であることから、この順序が全順序であることが従います。

このように、 $\mathbb{C}$ に全順序を入れる方法は色々あるのですが、いかなる全順序を持ってきたとしても、 $\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R}$ における通常の大小関係が持っている次の性質

$\forall a,b,c,a \leq b \Rightarrow a+c \leq b+c$ 　… 条件１
$\forall a,b \geq 0 \Rightarrow ab \geq 0$ 　… 条件２

は満たさないということが知られています。

実際、もし $\mathbb{C}$ に全順序 $\leq$ が入っているとすると、 $i \geq 0$ か $i \leq 0$ が成り立ちます。

$i \geq 0$ のとき、条件２より $i^2 = -1 \geq 0$ となります。
ここで、 $\leq$ は全順序なので、 $0 \leq 1$ か $0 \geq 1$ が成り立ちます。
$0 \leq 1$ と仮定すれば、条件１より $-1 = 0-1 \leq 1-1=0$ となり、反対称律から $-1=0$ となり矛盾。
$0 \geq 1$ と仮定すれば、 $-1 \geq 0$ より条件２から $1=-1 \times -1 \geq 0$ となり、反対称律から $1=0$ となり矛盾。

$i \leq 0$ のとき、条件１より $0 = i- i \leq 0-i=-i$ となり、条件２より $0 \leq (-i)^2=-1$ となります。
あとは $i \geq 0$ のときと同様にして矛盾が導けます。

したがって、条件１、２を満たすような $\mathbb{C}$ の全順序は存在しません。

◇例２

集合 $X$ のべき集合 $2^{X}$ 上に包含関係 $\subset$ によって順序を導入します。これは順序（半順序）ですが全順序ではありません。

・反射律
$\forall A \subset X, A \subset A$

・推移律
$\forall A,B,C \subset X, ((A \subset B) \land ( B \subset C)) \Rightarrow (A \subset C )$

・反対称律
$\forall A,B \subset X, ((A \subset B) \land ( B \subset A)) \Rightarrow (A=B)$

を満たすことは簡単なので自分自身で確かめてみて下さい。

全順序律については、簡単な反例があります。

$X = \{ 1,2 \}$ とすると、 $2^{X} = \{ \emptyset , \{ 1 \},\{ 2 \},\{ 1,2 \} \}$ となりますが、ここで、 $\{ 1 \}$ と $\{ 2 \}$ は $\{ 1 \} \not \subset \{ 2 \}$ かつ $\{ 2 \} \not \subset \{ 1 \}$ です。