大学数学

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

二項関係

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

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


◆定義

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


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

実際によく使われる2種類の二項関係を押さえておけば大体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)

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

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

全順序律 \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

が言えます。

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

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

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 … 条件1
\forall a,b \geq 0 \Rightarrow ab \geq 0 … 条件2

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

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

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

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

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



◇例2

集合 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 \} です。



◇例3

集合 X から \mathbb{R} への関数全体の集合 Map(X,\mathbb{R}) を考えます。Map(X,\mathbb{R}) には次のようにして順序が導入できます。

\forall  f,g \in Map(X,\mathbb{R}) について、
f \leq g \overset{\mathrm{def}}{\Leftrightarrow} \forall x \in X, f(x) \leq g(x)

これは順序(半順序)ですが全順序ではありません。

反射律
\forall f \in Map(X,\mathbb{R}), f \leq f

推移律
\forall f,g,h \in Map(X,\mathbb{R}), ((f \leq g) \land ( g \leq h)) \Rightarrow ( f \leq h)

反対称律
\forall f,g \in Map(X,\mathbb{R}),((f \leq g) \land ( g \leq f)) \Rightarrow ( f=g)

は、\mathbb{R} において反射律、推移律、反対称律が成り立つことから、上の定義に立ち返って考えれば成り立つことがわかります。

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

X = \{ 1,2 \} として、f(1)=1,f(2)=2 で定義される関数 f と、g(1)=2,g(2)=1 で定義される関数 g について、f \not \leq g かつ g \not \leq f です。


 

集合 その11へ>

<集合 その9へ

記事一覧(大学数学)に戻る

関連記事

  1. 大学数学

    集合.20 選択公理

    選択公理実は今までも暗に使っていたのですが、次のことは公理とみ…

  2. 大学数学

    写像.7 全射の性質

    全射の性質全射であることを同値な条件で言い替えることで特徴付け…

  3. 大学数学

    写像.13 集合の準同型定理、引き起こされる写像

    集合の準同型定理Prop.SetTop.3.12.1.を応用す…

  4. 大学数学

    論理記号.1 よく使う論理記号一覧、命題

    論理記号とは~数学を記述する上での基本言語~数学においてよく使…

  5. 大学数学

    大学数学概説.5 大学3、4年生レベルの科目(解析)

    ルベーグ積分大学1、2年生でやってきた積分はリーマン積分と言い…

  6. 大学数学

    大学数学概説.4 大学3、4年生レベルの科目(幾何)

    多様体現代幾何学の中心的な対象である多様体について学びます。…

コメント

  1. この記事へのコメントはありません。

  1. この記事へのトラックバックはありません。

アーカイブ

  1. 大学数学

    写像.4 逆写像
  2. 大学数学

    集合.12 二項関係.2 同値関係
  3. 大学数学

    大学数学概説.4 大学3、4年生レベルの科目(幾何)
  4. 大学数学

    集合.14 商集合
  5. 大学数学

    集合.6 共通集合と和集合(一般の場合)
PAGE TOP
error: Content is protected !!