論理と集合要約 NO.13

写像 f があると定義域の集合は f の値によってクラス分けされるのでした。

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

第 13 回目の主題 : クラス分けと同値関係

集合 X をクラス分けする際、「クラス分けの表」を書くのは面倒である。ほかの有力な手段として、「同値関係」を導入する方法がある。

問題 13.1. X = {1, 2, 3, …, 31}, Y = {0, 1, 2, …, 6}, f : X → Y を f(x) =(x を 7 で割った余り) で定義するとき、

(1) X の f に関するクラス分けの表を書きなさい。

(2) 1 と同じクラスになる X の元をすべて書きなさい。

(3) 2 と同じクラスになる X の元をすべて書きなさい。

一般に、集合 X にクラス分けが定まっているとき、 x ∈ X と同じクラスの元全体の集

合を [x] とか x̄ と書く。 (クラス分けがいろいろ出てきて区別が必要なときには、その都度 [x]_{1} とか添

字をつけて区別するのが良かろう) 字面だけみると、面白いことが起こる。例えば、上の例では

[1] = [8](= [15])

等々。

クラスは、元来は集合であるが、これを一つの元と改めて思い直すことにより、 X の \underline{クラス全体の集合}を考えることができる。これを X のこのクラス分けに関する商集合といい、 X/(クラス分け) と書く。上の例では、

X/(クラス分け) = {[0], [1], [2], [3], [4], [5], [6]}.

問題 13.2. 有限集合 X = {1, 2, 3, …, 15} をいくつかの黒い線分で結ぶ。 (ウラ面参照。 ) このとき、 X の点を「黒い線づたいにつなげるか否か」でクラス分けすることができる。このクラス分けの表を書き、 X/(クラス分け)の元の個数を書きなさい。

上の問題のように、「同じクラスか否か」のほうが先に分かっていれば、それをもとにクラス分けができる。これが同値関係の考え方である。

問題 13.3. X = {−10, −9, −8, …, 8, 9, 10} (絶対値が 10 以下の整数) とする。このとき、

(1) |x| = |y| のとき (のみ) x と y が同じクラス、と決めることにより、 X をクラス分けしその表を書け。

(2) x − y が 3 の倍数のとき (のみ) x と y が同じクラス、と決めることにより、 X をクラス分けしその表を書け。

(3) x − y が 5 の倍数のとき (のみ) x と y が同じクラス、と決めることにより、 X をクラス分けしその表を書け。

(4) x ≥ y のとき (のみ) x と y が同じクラス、と決めることにより、 X をクラス分けできるだろうか。

(5) xy ≥ 0 のとき (のみ) x と y が同じクラス、と決めることにより、 X をクラス分けできるだろうか。

(6) xy > 0 のとき (のみ) x と y が同じクラス、と決めることにより、 X をクラス分けできるだろうか。

上で、 x と y が同じクラス、といちいち書くのは面倒である。そこで、 x ∼ y や x ≡ y のような記号を用いて書くことが多い。いずれにしても、\underline{勝手な規則で}\underline{「同じクラス」}\underline{を定めようとしても}、 \underline{うまく行かない。}

うまく行くために必要な事柄を集めたのが、同値関係である。定義 13.1. ∼ が集合 X の同値関係であるとは、次のことを満たすときにいう。

(0) 任意の a, b ∈ X に対して、 a ∼ b か、そうでないかがはっきりと決まっている。 (1) (推移律) a, b, c ∈ X が、 a ∼ b, b ∼ c を満たせば、 a ∼ c も成り立っている。

(2) (反射律) 任意の a ∈ X に対して、 a ∼ a が成り立っている。

(3) (対称律) a, b ∈ X が、 a ∼ b を満たせば、 b ∼ a も成り立っている。

同値関係は、同じクラスかどうかの判定のルールがきちんと機能するためのルール ( 「ルールのルール」 ) である。

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .