論理と集合要約 NO.13

第 13 回目の主題 : 写像は定義域の元を類別する。

定義 13.1. (再) 集合 X の部分集合の族 {C_{λ}}_{λ∈Λ} が X のクラス分け (分割とも言う) であるとは、つぎのことが成り立つときに言う。

(1) ⋃_{λ∈Λ} C_{λ} = X.

(2) λ_{1}, λ_{2} ∈ Λ , λ_{1} ≠ λ_{2} ならば C_{λ_{1}} ∩ C_{λ_{2}} = ∅.

定義 13.2. (再) X の 2 つの元 x, y にたいして、 x ∼ y か、そうでない (x ≁ y) かがきちんと定まっていて、次の性質を持つとき、 ∼ のことを X 上の同値関係という。

(1) ∀x ∈ X∀y ∈ X∀z ∈ X ( 「x ∼ y and y ∼ z」 ⟹ x ∼ z).

(2) ∀x ∈ X (x ∼ x).

(3) ∀x ∈ X∀y ∈ X (x ∼ y ⟹ y ∼ x).

「同値関係」と、論理で言うところの「同値」とは (遠縁の親戚ぐらいにはあたるが)、別物である。よく区別すること。

問題 13.1. (再) X のクラス分け {C_{λ}}_{λ∈Λ} が与えられたとき、 x ∼ x′ であることを

∃λ(x ∈ C_{λ} and x′ ∈ C_{λ})

か否かで判定すれば、この ∼ は同値関係であることを示しなさい。

問題 13.2. (再) X に同値関係 ∼ が与えられているとする。 x ∈ X に対して、

C_{x} = {x′ ∈ X; x′ ∼ x}

とおくとき、次のことを示しなさい。

(1) x ∈ C_{x}. とくに、 ⋃_{x∈X} C_{x} = X.

(2) x′ ∈ C_{x} ⟹ x ∈ C_{x′}.

(3) C_{x} ∩ C_{x′} ≠ ∅ ⇔ x ∼ x′ ⇔ C_{x} = C_{x′}.

先ほどと同様に、 C_{x} のなかから重複するものを省くことにより、 X のクラス分けを得ることができる。容易に分かるように、上記 2 問題の操作は互いに逆になっている。すなわち、\underline{クラス分けを与えることとと同値関係を与えることは本質的に同じ事である。}

定義 13.3. 集合 X に同値関係 ∼ が与えられているとき、問題 13.2 で見たように X に次のようなクラス分けが定まるのであった。

x_{1} ∈ X と x_{2} ∈ X とが同じクラス⇔x_{1} ∼ x_{2}.

このクラス分けによるクラスの全体を X/ ∼ とよび、 X の ∼ による商集合とよぶ。

問題 13.3. (再) 写像 f : X → Y が与えられているとき、 x ∼_{f} x′ か否かの判定を f(x) = f(x′) か否かでするとき、すなわち、

x ∼_{f} x′ ⇔ f(x) = f(x′)

と定めるとき、 ∼_{f} は X の同値関係であることを定義に従って示しなさい。

上の問題の ∼_{f} を以下でも流用する。

問題 13.4. (再) f : ℤ → ℤ を f(n) = n^{2} で定義するとき、 (1) 1 ∼_{f} n となるような n ∈ ℤ をすべて求めなさい。

(2) ℤ の ∼_{f} に関するクラス分けの表を書きなさい。

問題 13.5. (再) f : ℝ^{2} ∋ (x, y) ↦ x ∈ ℝ に対して、 (1) (1, 0) ∼_{f} (1, 5) であることを示しなさい。

(2) (1, 0) ≁_{f} (2, 5) であることを示しなさい。

(3) (1, 0) ∼_{f} (a, b) となるような (a, b) ∈ ℝ^{2} をすべて求めなさい。問題 13.6. (再) f : ℝ^{2} ∋ (x, y) ↦ x^{2} + y^{2} ∈ ℝ に対して、

(1) (1, 0) ∼_{f} (0, −1) であることを示しなさい。

(2) (1, 0) ≁_{f} (2, 5) であることを示しなさい。

(3) (1, 0) ∼_{f} (a, b) となるような (a, b) ∈ ℝ^{2} をすべて求めなさい。

問題 13.7. f : ℝ ∋ t ↦ (cos(t), sin(t)) ∈ ℝ に対して、 (1) 0 ∼_{f} 2π であることを示しなさい。

(2) 0 ≁_{f} π であることを示しなさい。

(3) 0 ∼_{f} a となるような a ∈ ℝ をすべて求めなさい。

(4) a ∼_{f} b となるための a, b ∈ ℝ の条件はなんだろうか。

問題 13.8. X = (平仮名の全体のなす集合), y = (アルファベット小文字全体のなす集合) , f : X → Y を x ∈ X に対して、 x をローマ字小文字表記 (ヘボン式) した時の最後の文字に写すことにより定める。このとき、

(1) あなたの自由に選んだ平仮名5文字 x_{1}, x_{2}, x_{3}, x_{4}, x_{5} について、 f(x_{1}), f(x_{2}), f(x_{3}), f(x_{4}), f(x_{5}) を求めなさい。

(2) 「あ ∼_{f} た」であることを示しなさい。

(3) 「い ≁_{f} た」であることを示しなさい。

(4) ∼_{f} に関して同じクラスであるための条件を簡潔に述べなさい。

(5) 商集合 X/ ∼_{f} の元の個数 #(X/ ∼_{f}) はいくつか。

問題 13.9. X = ℤ_{>0}, Y = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} とし、 f : X → Y を、 f(x) = (x を 10 で割った余り)で定義する。このとき、

(1) あなたの自由に選んだ正の整数 x_{1}, x_{2}, x_{3}, x_{4}, x_{5} について、 f(x_{1}), f(x_{2}), f(x_{3}), f(x_{4}), f(x_{5}) を求めなさい。

(2) 75 ∼_{f} 55 であることを示しなさい。

(3) 85 ≁_{f} 1018 であることを示しなさい。

(4) ∼_{f} に関して同じクラスであるための条件を 10 進数による表記をもちいて簡潔に述べなさい。

(5) x ∼_{f} y と x − y ∈ 10ℤ は同値であることを示しなさい。

(6) 商集合 X/ ∼_{f} の元の個数 #(X/ ∼_{f}) はいくつか。