集合論問題集

4 関係

集合 $X$ 上の関係の定義を書け。
-

$X$ 上の関係とは、直積集合 $X × X$ の部分集合のことである。

4.1 順序関係

集合上の関係「」が順序関係であることの定義を書け。
-
集合上の関係「」を以下３つの条件を満たすとき「」を順序関係であるという。
- (反射律) 任意の $x ∈ A$ に対して、 $x ≤ x$ が成り立つ。
- (非対称律) $x, y ∈ A$ に対して、 $x ≤ y$ and $y ≤ x$ ならば $x = y$ が成り立つ。
- (推移律) $x, y, z ∈ A$ に対して、 $x ≤ y$ , $y ≤ z$ ならば $x ≤ z$ が成り立つ。
を順序集合とする。
1. (1) $a ∈ A$ が $(A,≤ )$ の極大元であることの定義を書け。
2. (2) $a ∈ A$ が $(A,≤ )$ の極小元であることの定義を書け。
3. (3) $a ∈ A$ が $(A,≤ )$ の最大元であることの定義を書け。
4. (4) $a ∈ A$ が $(A,≤ )$ の最小元であることの定義を書け。
5. (5) $a ∈ A$ が $X ⊂ A$ の上界であることの定義を書け。
6. (6) $X ⊂ A$ が上に有界であることの定義を書け。
-
1. (1) $b ∈ A$ について、 $a ≤ b$ ならば $a = b$ である。
2. (2) $b ∈ A$ について、 $b ≤ a$ ならば $a = b$ である。
3. (3) 任意の $b ∈ A$ に対して $b ≤ a$ である。
4. (4) 任意の $b ∈ A$ に対して $a ≤ b$ である。
5. (5) 任意の $x ∈ X$ に対して $x ≤ a$ である。
6. (6) $X$ の上界が存在する。
集合について、べき集合を考えたとき、関係「」は順序関係であることを示せ。
-
- 任意の $A ∈ 2X$ に対して、 $A 抂 A$ は成り立つ。
- $A, B ∈ 2X$ に対して、 $A ⊂ B$ かつ $B ⊂ A$ ならば $A = B$ である。
- $A, B, C ∈ 2X$ に対して、 $A ⊂ B$ かつ $B ⊂ C$ ならば、 $A ⊂ C$ である。
以上から、関係「」は順序関係である。
順序集合 $(A,≤ )$ が全順序集合であることの定義を書け。
-

$(A, ≤)$ が順序集合であって、任意の $x, y ∈ A$ に対して $x ≤ y$ または $y ≤ x$ が成り立つとき、 $(A,≤)$ を全順序集合であるという。
全順序集合ではない順序集合の例を一つ答えよ。
-
- $(ℕ,|)$ (自然数全体の集合に “割り切れる” という関係を考えたもの)。
- $(2A,⊂)$ (集合 $A$ の部分集合全体の集合に “含まれる” という関係を考えたもの)。ただし $A$ は二つ以上の要素を持つものとする。
$ℝ$ が (通常の大小関係による順序で) 整列集合ではないことを示せ。
-

$ℝ ⊃ (0, 1)$ に対して、 $(0, 1)$ は最小元をもたない。なぜなら、 $x ∈ (0, 1)$ が最小元だったと仮定すると、任意の $y ∈ (0, 1)$ に対して、 $x ≤ y$ が成り立つ。ここで、 $0 < x$ であるから、 $0 < x∕2 < x < 1$ となり、 $x$ より小さい $(0, 1)$ の元 $x∕2$ が存在する。よって $(0 1)$ に最小元は存在しない。したがって、 $ℝ$ は整列集合ではない。整列集合とは任意の空でない順序部分集合が最小元を持つ集合のことである。
集合とし、 , をその部分集合とする。
1. (1) $B ∩ C$ は $B$ と $C$ の両方に含まれる $A$ の部分集合のうち、 (包含関係に関して) 最大のものであることを示せ。
2. (2) $B ∪ C$ は $B$ と $C$ の両方を含む $A$ の部分集合のうち、 (包含関係に関して) 最小のものであることを示せ。
-
1. (1) $B ∪ C$ が $B$ と $C$ の両方を含む $A$ の部分集合であることは明らかである。最大であることをいうには $U ⊃ B$ かつ $U ⊃ C$ である $A$ の任意の部分集合 $U$ に対して、 $U ⊃ B ∩ C$ を示せばよい。 $x ∈ B ∪C$ とする。このとき $x ∈ B$ または $x ∈ C$ である。 $x ∈ B$ のとき $U ⊃ B$ より、 $x ∈ U$ であり、 $x ∈ C$ のとき $U ⊃ B$ より、 $x$∈ U$ である。よって $x ∈ U$ であり、 $U ⊃ B ∪C$ である。
2. (2) $B ∩ C$ が $B$ と $C$ の両方に含まれる $A$ の部分集合であることは明らかである。最小であることをいうには $U ⊂ B$ かつ $U ⊂ C$ である $A$ の任意の部分集合 $U$ に対して、 $U ⊂ B ∩ C$ を示せばよい。 $x ∈ U$ とする。より、 $x ∈ B$ であり、 $U ⊂ C$ より、 $x ∈ C$ である。よって $x ∈ B ∩C$ であり、 $U ⊂ B ∩ C$ である。
(ベクトル空間とその部分空間についての知識を仮定する。) をベクトル空間とし、 , をその部分空間とする。とおく。
1. (1) $V ∩ W$ , $V + W$ は $U$ の部分空間であることを示せ。
2. (2) $V ∩ W$ は $V$ と $W$ の両方に含まれる $U$ の部分空間のうち、 (包含関係に関して) 最大のものであることを示せ。
3. (3) $V + W$ は $V$ と $W$ の両方を含む $U$ の部分空間のうち、 (包含関係に関して) 最小のものであることを示せ。
-
1. (1) $v,w ∈ V ∩W$ , $α$ をスカラーとすると $v + w,αv ∈ V ∩ W$ は簡単に分かるので $V ∩ W$ は部分空間である。 $V + W$ についても同様である。
2. (2) $V ∩ W$ が $V$ と $W$ の両方に含まれる部分空間であることはすぐに分かる。 $U$ を $V$ と $W$ の両方に含まれる部分空間とすれば、明らかに $U ⊂ V ∩ W$ となるので、 $V ∩W$ はそのような部分空間のうち最大のものである。
3. (3) $V + W$ が $V$ と $W$ の両方を含む部分空間であることはすぐに分かる。 $U$ を $V$ と $W$ の両方を含む部分空間とすれば $U ⊃ V + W$ であることもすぐに分かるので、 $V +W$ はそのような部分空間のうち最小のものである。
一般にである。は一般に部分空間にはならない。
の辞書式順序の定義を書け。またそれが整列順序であることを示せ。
-
に次のように定めた順序を辞書式順序という。 , に対して
1. (1) $a0 < a1$ のとき $(a0,b0) ≤ (a1,b1)$ である、
2. (2) $a0 = a1$ かつ $b0 ≤ b1$ のとき $(a0,b0) ≤ (a1,b1)$ である。
まず、これが順序であることを示す。
- 任意の $(a,b) ∈ ℕ× ℕ$ に対して (2) より $(a,b) ≤ (a,b)$ である。
- $(a,b) ≤ (c,d)$ かつ $(c,d) ≤ (a,b)$ とする。 $(a,b) ≤ (c,d)$ が (1) によるとすると $(c,d) ≤ (a,b)$ は成り立たず矛盾が生じる。 $(c,d) ≤ (a,b)$ が (1) によるとすると $(a,b) ≤ (c,d)$ は成り立たず矛盾が生じる。よって、いずれも (2) によらなければならない。このとき $a = c$ であって、 $b ≤ d$ かつ $d ≤ b$ となるので $b = d$ である。よって $(a,b) = (c,d)$ である。
- $(a,b) ≤ (c,d)$ かつ $(c,d) ≤ (e,f)$ とする。いずれかが (1) によるならば $a < e$ となり、 (1) より $(a,b) ≤ (e,f )$ である。両方が (2) によるとする。このとき $a = e$ であり、 $b ≤ d$ かつ $d ≤ f$ なので $b ≤ f$ である。 (2) により $(a,b) ≤ (e,f)$ である。
以上で、これが順序であることが分かった。この順序が整列順序であることを示す。とおき、その部分集合をとする。さらにとおく。が空でないからも空ではない。はの部分集合で、は整列集合なのでには最小元が存在する。次にとおく。の決め方からは空でないの部分集合で、したがって最小元もつ。このときの決め方からはの最小元である。
最大元ではない極大元をもつ順序集合の例を作れ。
-

(解答例 1)
$S = {a,b,c}$ とし、関係 $≤$ を $≤= {(a,a), (b,b), (c,c), (a,b), (a,c)}$ で定める。すなわち
$a ≤ a, b ≤ b, c ≤ c, a ≤ b, a ≤ c$
であり、その他の組については順序は定まらない。これが順序であることは容易に確かめられる。またこのとき $b$ と $c$ は極大元ではあるが、最大元ではない。
(解答例 2)
$S$ を $|S| ≥ 2$ なる集合とする。また $X = 2S - {S}$ とする。 $X$ は集合の包含関係によって順序集合となる (すなわち $2S$ の順序部分集合である)。このとき、任意の $s ∈ S$ について $S - {s}$ は $X$ の極大元であるが、最大元ではない。 (解答例 1 は、この $S$ として $|S| = 2$ なるものを考えたものと本質的に同じである。)
全順序集合の極大元は最大元であることを示せ。
-

$(A, ≤)$ を全順序集合とし $a$ をその極大元とする。このとき $a$ が最大元であることをいう。 $b ∈ A$ とする。このとき $A$ が全順序集合であることから $a ≤ b$ または $b ≤ a$ である。 $a$ は極大なので $a ≤ b$ ならば $b = a$ である。よってこのときも $b ≤ a$ が成り立つ。したがって、常に $b ≤ a$ が成り立ち、よって $a$ は最大元である。
もちろん「全順序集合の極小元は最小元である」も正しく、同様に証明できる。
順序集合に最大元が存在するならば、それは唯一つであることを示せ。
-

$(A, ≤)$ を順序集合とし $a,b$ をその最大元とする。 $a$ が最大元であるから $b ≤ a$ である。また $b$ が最大元であるから $a ≤ b$ である。したがって $a = b$ である。よって最大元は唯一つである。
最小元についても同様である。
順序集合の最大元は極大元であることを示せ。
-

$(A, ≤)$ を順序集合とし $a$ をその最大元とする。 $b ∈ A$ が $a ≤ b$ を満たすとする。 $a$ が最大であるから $b ≤ a$ である。よって $a = b$ が成り立ち、 $a$ は極大元である。
最小元についても同様である。
順序集合 $(A,≤ )$ に最大元 $a$ が存在するとき、 $A$ の極大元は $a$ のみであることを示せ。
-

$b$ を極大元とする。 $a$ が最大であるから $b ≤ a$ である。が極大元であるから $b = a$ となる。よって $A$ の極大元は $a$ のみである。
最小元、極小元についても同様である。
最大元をもたない全順序集合の例を作れ。
-

$ℕ$ に自然な順序を考えれば、それは全順序集合であり、最大元をもたない。
最小元をもたないが最大元をもつ全順序集合の例を作れ。
-

負の整数全体の集合に自然な順序を考えれば、それは全順序集合であり、最小元をもたないが最大元 $- 1$ をもつ。
$(S,≤ )$ を整列集合とする。 $a,b ∈ S$ , $a ≤ b$ とする。このとき「 $a ≤ c ≤ b$ なる $c ∈ S$ は有限個しかない」というのは正しいかどうかを考え、正しいならば証明し、正しくなければ反例を構成せよ。
-

正しくない。
例えば $ℕ × ℕ$ に辞書式順序を考えれば、それは整列集合である。また $(1,1) ≤ (2,1)$ であるが、任意の $n ∈ N$ に対して $(1,1) ≤ (1,n) ≤ (2,1)$ であるから、このようなものは無限個ある。
$(S,≤ )$ を順序集合とする。 $x,y ∈ S$ に対して「 $x ≤ z$ , $y ≤ z$ なる最小の $z ∈ S$ が存在する」というのは正しいかどうかを考え、正しいならば証明し、正しくなければ反例を構成せよ。 (上の条件は正確には「 $T = {z ∈ S | x ≤ z, y ≤ z}$ が最小元をもつ」ということである。このとき $T$ は ${x,y}$ の上界全体の集合である。)
-

正しくない。
$S = {a,b,c,d}$ とし、関係 $≤$ を $≤= {(a,a), (b,b), (c,c), (d,d), (a,c), (a,d), (b,c), (b,d)}$ で定める。このとき $c,d$ はいずれも条件を満たしているが、この二つに順序がない ( $c ≤ d$ でも $d ≤ c$ でもない) ので、それは最小ではない。
とする。に以下のように関係を定める。に対して「であるとは、あるが存在してとなること」とする。
1. (1) $(S,≼)$ が順序集合であることを示せ。
2. (2) $(S,≼)$ に極大元、極小元、最大元、最小元があるかどうかを考え、存在するならばそれを求めよ。
-
1. (1)
  - $a ∈ S$ に対して $a = a1$ で $1 ∈ S$ であるから $a ≼ a$ である。
  - $a ≼ b$ かつ $b ≼ a$ とする。ある $c,d ∈ S$ が存在して $b = ac$ , $a = bd$ となる。 $a ⁄= 0$ とする。このとき $a = bd = acd$ となるが、 $c,d ∈ S$ より $c = d = 1$ でなくてはならない。よって、このとき $a = b$ である。 $a = 0$ ならば $b = ac = 0$ で、このときも $a = b$ である。
  - $a ≼ b$ かつ $b ≼ c$ とする。ある $d,e ∈ S$ が存在して $b = ad$ , $c = be$ となる。このとき $c = be = ade$ で $de ∈ S$ であるから $a ≼ c$ である。
  以上よりは順序集合である。
2. (2) 任意の $a ∈ S$ に対して $0 = a× 0$ であるから $a ≼ 0$ である。よって $0$ は最大元であり、また極大元でもある。更に極大元は $0$ に限る。
  任意の $a ∈ S$ に対して $a = 1× a$ であるから $1 ≼ a$ である。よって $1$ は最小元であり、また極小元でもある。更に極小元は $1$ に限る。
$ℤ$ に以下のように関係 $≼$ を定める。 $a,b ∈ ℤ$ に対して「 $a ≼ b$ であるとは、ある $c ∈ ℤ$ が存在して $b = ac$ となること」とする。 $(ℤ,≼)$ が順序集合であるかどうかを判定し、その理由も述べよ。
-

順序集合ではない。
なぜならば $1 ≼ - 1$ かつ $- 1 ≼ 1$ であるが $1 ⁄= - 1$ である。
有限な順序集合は極小元をもつことを示せ。
-

$(X, ≤)$ を順序集合とし $|X| < ∞$ とする。 $x,y ∈ X$ に対して $x ≤ y$ かつ $x ⁄= y$ であることを $x < y$ または $y > x$ と書くことにする。
$(X,≤ )$ が極小元を持たないと仮定する。 $x1 ∈ X$ を任意にとる。 $x1$ は極小ではないので $x2 < x1$ となる $x2 ∈ X$ が存在する。これを繰り返せば
$x1 > x2 > x3 > ⋅⋅⋅$
なる無限列を得る。 $i > j$ ( $i,j ∈ ℕ$ ) に対して $xi < xj$ なので $xi ⁄= xj$ である。よって ${xi | i ∈ ℕ }$ は無限集合となる。しかし ${xi | i ∈ ℕ}$ は有限集合 $X$ の部分集合なので、これは矛盾である。
とする。上の順序はいくつあるか答えよ。また全順序はいくつあるか。
-
として、その順序集合としての型を分類すると

(1) $x|y|z$ (2) $xy z$ (3) $x y z$

(4) $x| y | |z$ (5) $x y z$

となる。すなわち
1. (1) ${(x,x),(y,x),(z,x),(y,y),(z,y),(z,z)}$ であり、 $x,y,z$ の選び方で $6$ 通りある。
2. (2) ${(x,x),(y,x),(z,x),(y,y),(z,z)}$ であり、 $x,y,z$ の選び方で $3$ 通りある。
3. (3) ${(x,x),(z,x),(y,y),(z,y),(z,z)}$ であり、 $x,y,z$ の選び方で $3$ 通りある。
4. (4) ${(x,x),(z,x),(y,y),(z,z)}$ であり、 $x,y,z$ の選び方で $6$ 通りある。
5. (5) ${(x,x),(y,y),(z,z)}$ であり、 $x,y,z$ の選び方は $1$ 通りしかない。
よってすべてで個の順序がある。このうち、全順序は (1) のみなので、それは個である。
を写像、を順序集合とする。上の関係を「に対してのとき」として定める。
1. (1) $(X,≤ )$ が順序集合であることと $f$ が単射であることは同値である。これを示せ。
2. (2) $f$ が単射であるとする。 $(Y,≼)$ が全順序集合であるならば $(X, ≤)$ も全順序集合であることを示せ。
3. (3) $f$ が単射であるとする。 $(Y,≼)$ が整列集合であるならば $(X,≤ )$ も整列集合であることを示せ。
-
1. (1) は単射であるとする。
  - 任意の $x ∈ X$ に対して $f(x) ≼ f(x )$ であるから $x ≤ x$ である。
  - $x ≤ y$ , $y ≤ x$ とする。 $f(x) ≼ f(y)$ , $f (y) ≼ f(x )$ であるから $f(x) = f(y)$ である。また $f$ は単射なので $x = y$ である。
  - $x ≤ y$ , $y ≤ z$ とする。 $f(x) ≼ f(y)$ , $f (y) ≼ f(z)$ である。よって $f(x) ≼ f(z)$ となり $x ≤ z$ である。
  以上よりは順序集合である。
  が単射でないとする。で , となるものが存在する。このときよりであり、よりである。よってかつであってもとは限らず、は順序集合ではない。
  を順序集合、をその部分集合とする。のへの埋め込みは単射であるから、この方法でも順序集合になる。これが順序部分集合である。
2. (2) 任意の $′x,x ∈ X$ に対して $′f(x) ≼ f (x )$ または $′f (x ) ≼ f(x)$ が成り立つので $′x ≤ x$ または $′x ≤ x$ となり $(X,≤ )$ は全順序集合である。
3. (3) $A$ を $X$ の空でない部分集合とする。 $f(A )$ は $Y$ の空でない部分集合である。 $Y$ は整列集合なので $f(A )$ は最小元 $y$ をもつ。このとき $y ∈ f(A)$ なので、ある $a ∈ A$ が存在して $f(a) = y$ である。 $a$ が $A$ の最小元であることを示す。 $b ∈ A$ とする。 $f(a)$ が $f(A)$ の最小元であり、 $f(b) ∈ f(A)$ であることから $f(a) ≼ f(b)$ である。よって $a ≤ b$ である。したがって $a$ は $A$ の最小元である。
  空でない部分集合が最小元をもつので $X$ は整列集合である。
$R$ , $R ′$ を集合 $X$ 上の二つの順序とする。 $R ⊂ R ′$ であるとき「 $R$ は $R ′$ よりも弱い順序」、または「 $R′$ は $R$ よりも強い順序」であるということにする。この関係によって $X$ 上の順序全体の集合は順序集合となる。 $X$ 上の最も弱い順序を求めよ。
-

$R0 = {(x,x) | x ∈ X }$ が求めるものである。実際 $R0$ が順序であることはすぐに分かる。また、任意の順序 $R$ について $(x,x) ∈ R$ ( $∀x ∈ X$ ) であるから $R0 ⊂ R$ である。

4.2 同値関係

集合上の関係「」が同値関係であることの定義を書け。
-
以下つの条件が成り立つとき、関係は同値関係であるという。
- (反射律) 任意の $X$ の元 $x$ に対して $x ~ x$ である。
- (対称律) $X$ の元 $x, y$ に対して、 $x ~ y$ ならば $y ~ x$ が成り立つ。
- (推移律) $X$ の元 $x, y, z$ に対して、「 $x ~ y$ かつ $y ~ z$ 」ならば $x ~ z$ が成り立つ。
ある学生の集合を $S$ とする。 $A,B ∈ S$ に対して「同じ趣味をもっているときに $A ~ B$ 」と関係 $~$ を定める (厳密に定義されるわけではないが、関係が定まったとする)。このとき $~$ は同値関係といえるかどうかを考え、その理由も答えよ。
-

同値関係とはいえない。
$A ~ B$ かつ $B ~ C$ とする。 $A$ と $B$ の共通の趣味が、例えば「読書」であり、 $B$ と $C$ の共通の趣味が「音楽鑑賞」であれば、 $A$ と $C$ は必ずしも共通の趣味をもつわけではない。したがって $A ~ C$ とはいえない。
実数成分の次正方行列全体の集合について関係「」を「次正則行列が存在してのとき」と定める。このとき関係「」は同値関係であることを示せ。
-
問 26 の条件をつ確認すればよい。
- $E$ を単位行列とする。任意の $M (n,ℝ)$ の元 $X$ に対して、 $X = XE$ より、 $X ~ X$ である。
- $X ~ Y$ とする。ある正則行列 $P$ が存在して $Y = XP$ となる。このとき $X = Y P- 1$ である。よって $Y ~ X$ となる。
- $X ~ Y$ かつ $Y ~ Z$ とする。ある正則行列 $P$ , $Q$ が存在して $Y = XP$ , $Z = Y Q$ となる。したがって、 $Z = (XP )Q = X (P Q)$ となり $X ~ Z$ である。
以上より、関係は集合上の同値関係である。
実数成分の次正方行列全体の集合について関係「」を「次正則行列が存在してのとき」と定める。このとき関係「」は同値関係であることを示せ。
-
問 26 の条件をつ確認すればよい。
- $E$ を単位行列とする。任意の $M (n,ℝ)$ の元 $X$ に対して、 $X = E -1XE$ より、 $X ~ X$ である。
- $X ~ Y$ とする。ある行列 $P$ が存在して $Y = P-1XP$ となる。このとき $X = (P -1)-1Y(P -1)$ ・ある。よって $Y ~ X$ となる。
- $X ~ Y$ かつ $Y ~ Z$ とする。ある正則行列 $P$ , $Q$ が存在して $Y = P -1XP$ , $Z = Q -1Y Q$ となる。したがって、 $Z = Q-1(P- 1XP )Q = Q -1P- 1XP Q = (P Q)-1X (PQ )$ となり $X ~ Z$ である。
以上より、関係は集合上の同値関係である。
集合の部分集合全体の集合を考える。に対して関係「」を「との間に全単射が存在するとき」と定める。このとき関係「」は上の同値関係であることを示せ。
-
- 任意の $2X$ の元 $A$ に対して、恒等写像は $A$ から $A$ への全単射である。よって $A ~ A$ が成り立つ。
- $A ~ B$ とする。全単射 $f : A → B$ が存在する。このとき逆写像 $f-1 : B → A$ が存在してこれも全単射である。よって $B ~ A$ となる。
- $A ~ B$ かつ $B ~ C$ とする。全単射 $f : A → B$ , $g : B → C$ が存在する。このとき合成写像 $g∘ f : A → C$ も全単射である。よって $A ~ C$ である。
次元ベクトル空間から原点を除いた集合に以下のように関係「」を定める。 , に対して、あるでない実数が存在してのときとする。このときは同値関係であることを示せ。また、このときの同値類を考え、同値類の代表系を一つ求めよ。
-
- $x = 1x$ より $x ~ x$ である。
- $x ~ y$ とする。 $x = αy$ となる $0 ⁄= α ∈ ℝ$ が存在し、このとき $y = α-1x$ なので $y ~ x$ である。
- $x ~ y$ , $y ~ z$ とする。 $x = αy$ , $y = βz$ となる $0 ⁄= α ∈ ℝ$ , $0 ⁄= β ∈ ℝ$ が存在する。このとき $x = αβz$ で $αβ ⁄= 0$ なので $x ~ z$ である。
以上よりは同値関係である。
同値類は、原点を通る一つの直線上の点の集合から原点を除いたものである。
同値類の代表としては、例えば単位球面上の点の集合で、原点に関して対称な二つの点のうち、片方だけを集めたものとなる。具体的にはなどである。
を写像とする。上の関係を「に対してのとき」として定める。このときは同値関係であることを示せ。また、この同値関係によるを含む同値類、および類別を求めよ。
-
- $x ∈ X$ に対して $f(x) = f(x)$ なので $x ~ x$ である。
- $x ~ y$ とする。 $f(x) = f (y)$ なので $f(y) = f(x)$ となり $y ~ x$ である。
- $x ~ y$ , $y ~ z$ とする。 , $f (y) = f(z)$ なので $f(x) = f(z)$ となり $x ~ z$ である。
以上よりは同値関係である。
を含む同値類はである。
類別はである。
の動く範囲をとするととなることもあるので、とする方が好ましい。
1. (1) $ℤ$ について関係「 $~$ 」を「 $x - y = 2a$ なる $a ∈ ℤ$ が存在するとき $x ~ y$ 」と定めるとこれは同値関係であることを示せ。
2. (2) $0, 1$ を含む同値類を求めよ。
3. (3) $ℤ∕ ~$ を求めよ。
-
1. (1)
  - 任意の $ℤ$ の元 $x$ に対して、 $x - x = 0 = 2⋅0$ となる。よって $x ~ x$ である。
  - $x ~ y$ とする。ある整数 $ℓ$ が存在して、 $x - y = 2ℓ$ である。このとき $y - x = - 2ℓ = 2(- ℓ)$ で、 $- ℓ$ は整数だから、 $y ~ x$ である。
  - $x ~ y$ かつ $y ~ z$ とする。ある整数 $k,ℓ$ が存在して $x - y = 2k$ , $y- z = 2ℓ$ となる。このとき $x- z = (x - y)+ (y- z) = 2k - 2ℓ = 2(k- ℓ)$ となって、 $k- ℓ$ は整数だから、 $x ~ z$ である。
2. (2) $C0 = {x | x ~ 0} = {x | x = x- 0 = 2ℓ (ℓ ∈ ℤ)} = (偶数全体の集合 )$ ,
  $C1 = {x | x ~ 1} = {x | x - 1 = 2ℓ (ℓ ∈ ℤ )} = {x | x = 2ℓ+ 1 (ℓ ∈ ℤ)} = (奇数全体の集合 )$ 。
3. (3) $ℤ = C0 ∪C1$ だから、 $(ℤ∕ ~ ) = {C0, C1}$
1. (1) $n ∈ ℕ$ を固定する。 $ℤ ∋ x, y$ に対して、 $x ≡ y (mod n)$ であることの定義を書け。
2. (2) この関係は $ℤ$ 上の同値関係であることを示せ。
3. (3) この同値関係に関して $a ∈ ℤ$ を含む同値類を求めよ。
4. (4) この同値関係の完全代表系を一組求めよ。
5. (5) この同値関係による $ℤ$ の類別を求めよ。
6. (6) $493256823$ を $9$ で割ったときの余りを求めよ。 (集合論とは直接は関係ない。）
7. (7) $2x - 5y = 1$ の整数解を求めよ。 (集合論とは直接は関係ない。）
-
1. (1) $x ≡ y (mod n)$ であるとは、適当な整数 $ℓ$ が存在して、 $x - y = nℓ$ となることである。
2. (2)
  - $x- x = 0 = n ⋅0$ なので $x ≡ x (mod n)$ である。
  - $x ≡ y (mod n)$ とする。ある $ℓ ∈ ℤ$ が存在して $x - y = n ℓ$ である。このとき $y - x = n(- ℓ)$ なので $y ≡ x (mod n)$ である。
  - $x ≡ y (mod n)$ , $y ≡ z (mod n)$ とする。ある $ℓ,ℓ′ ∈ ℤ$ があって $x- y = nℓ$ , $y- z = nℓ′$ である。このとき $x - z = (x - y) + (y - z) = nℓ+ nℓ′ = n(ℓ+ ℓ′)$ なので $x ≡ z (mod n )$ である。
3. (3) ${a +ℓn | ℓ ∈ ℤ}$
4. (4) ${0,1,2,⋅⋅⋅ ,n - 1}$ (完全代表系は一意的ではないので、これ以外にも色々とある。)
5. (5) $⋃ℤ = na=-01{a+ ℓn | ℓ ∈ ℤ}$
6. (6) $10 ≡ 1 (mod 9)$ だから、以下、 $(mod 9)$ で考えると、 $493256823 ≡ 4 + 9+ 3+ 2 +5 + 6+ 8+ 2 + 3 = 9+ (4+ 3 + 2)+ 5+ (4+ 2)+ 8+ (1+ 1)+ 3 ≡ (5+ 4)+ 2+ (8+ 1)+ 1 +3 ≡ 2+ 1 +3 = 6$ つまり、余りは $6$ である。結局 $9$ で割ったときの余りを求めるとき、各位の和から、 $9$ を取り除いていけばよい。（九去法）
7. (7) $2x - 5y = 1$ に対して、 $(mod 5)$ で考えると、 $2x ≡ 1$ だから、 $x = 5k+ 3 (k ∈ ℤ)$ となる。よって、問題の式に代入すると、 $1 = 2(5k + 3)- 5y = 10k + 6- 5y$ より、 $y = 2k+ 1$ である。つまり、 $(x, y) = (5k+ 3, 2k+ 1)$ である。
(線形代数に関する深い知識を仮定する。) 問題 29と同様に $Mn (ℂ)$ に同値関係「 $~$ 」を定義する。このときの同値類はどのようなものかを考察せよ。
-

Jordan 標準形として同じ行列をもつものすべての集合。
を集合、を上の同値関係、をの部分集合とする。をの部分集合と見てとおけばは上の関係である。が上の同値関係であることを示せ。
-
- $y ∈ Y$ とする。 $R$ は同値関係だから $(y,y) ∈ R$ で、 $(y,y) ∈ R ∩ (Y ×Y ) = R ′$ 、すなわち $yR′y$ である。
- $y,z ∈ Y$ とし $yR′z$ とする。 $(y,z) ∈ R′ ⊂ R$ で $R$ は同値関係なので $(z,y) ∈ R$ である。また $y,z ∈ Y$ なので $(z,y) ∈ R ∩ (Y × Y) = R ′$ である。よって $zR ′y$ である。
- $y,z,u ∈ Y$ とし $yR ′z$ かつ $zR′u$ とする。 $(y,z) ∈ R ′ ⊂ R$ , $(z,u) ∈ R′ ⊂ R$ で $R$ は同値関係なので $(y,u) ∈ R$ である。またすなわち $yR′u$ である。
以上よりは上の同値関係である。
を集合とし
$⋃X = X λ, λ ⁄= μ ならば Xλ ∩X μ = ϕ λ∈Λ$
とする。に対して「あるがあってかつとなるときに」として関係を定める。このときは上の同値関係であることを示せ。
-
- $x ∈ X$ とする。 $⋃X = λ∈ΛX λ$ であるから、ある $λ ∈ Λ$ があって $x ∈ X λ$ となり、よって $x ~ x$ である。
- $x ~ y$ とする。ある $λ ∈ Λ$ があって $x,y ∈ X λ$ となり、 $y ~ x$ も成り立つ。
- $x ~ y$ , $y ~ z$ とする。ある $λ,μ ∈ Λ$ があって $x,y ∈ Xλ$ , $y,z ∈ Xμ$ となる。このとき $y ∈ X λ ∩ X μ$ である。 $λ ⁄= μ$ ならば $X λ ∩ X μ = ϕ$ であるから $λ = μ$ である。よって $x,z ∈ X λ$ となり $x ~ z$ である。
以上よりは上の同値関係である。
集合を空でない部分集合の共通部分のない和集合に書くとき、これをの分割という。同値関係による類別は分割である。また、この問題により、任意の分割は同値関係を定めることが分かる。よって、同値関係を与えることと、分割を与えることは本質的に等しい。
$X = {1,2,3,4,5,6}$ とし、 $R = {(1,1),(1,2),(1,3),(3,3),(4,6),(5,5)}$ とする。 $R ⊂ X × X$ である。 $R$ を含む最小の同値関係を求めよ。
-

同値関係を満たすためには以下の表のようにすればよい。

よって求める関係は ${(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3),(4,4),(4,6),(5,5),(6,4),(6,6)}$ である。
同値類が ${1,2,3}$ , ${4,6}$ , ${5}$ であることを読み取り、同じ同値類の任意の 2 元の組からなるものを求めればよい。
$X$ を集合とする。 $R$ は $X$ 上の関係であり、順序関係、かつ同値関係であるとする。 $R$ を求めよ。
-

$(x,y) ∈ R$ とする。このとき $R$ が同値関係であるから $(y,x) ∈ R$ である。また $R$ が順序であるから $(x,y) ∈ R$ かつ $(y,x) ∈ R$ より $x = y$ となる。したがって $R ⊂ {(x,x) ∈ X × X | x ∈ X }$ である。
逆に任意の $x ∈ X$ に対して、 $R$ が同値関係であることから $(x,x ) ∈ R$ である。よって ${(x,x) ∈ X × X | x ∈ X} ⊂ R$ である。
以上より $R = {(x,x) ∈ X ×X | x ∈ X }$ となる。
$X = {1,2,3}$ とする。 $X$ 上の関係はいくつあるかを答えよ。 $X$ 上の同値関係はいくつあるかを答えよ。
-

$X$ 上の関係とは $X × X$ の部分集合である。したがってその数は $2|X ×X| = 29 = 512$ である。 $X$ 上の同値関係は $X$ の同値類への分割 (いくつかの空でない部分集合の共通部分のない和集合への分解) に対応する (問 37参照)。それは

$X =$ {1,2,3}X = {1}∪ {6,3}X = {2}∪ {1,3}X = {3}∪ {1,2}X = {1}∪ {2}∪ {3}$

ですべてであるから、その個数は $5$ である。
実数成分の $n$ 次正方行列全体の集合 $M (n,ℝ )$ について関係「 $~$ 」を「 $n$ 次正則行列 $P$ が存在して $-1B = P AP$ のとき $A ~ B$ 」と定める。このとき関係「 $~$ 」は同値関係である (問 29 参照)。行列 $A$ を含む同値類を $CA$ で表し、同値類全体の集合 $M (n,ℝ )∕ ~$ を考える。写像 $f : (M (n,ℝ )∕ ~) → ℝ$ , $f(CA) = detA$ が矛盾なく定義できることを示せ。
-

$A ~ B$ のとき $detA = detB$ であることを示せばよい。 $A ~ B$ とする。ある正則行列 $P$ があって $B = P -1AP$ である。よって $detB = (det P-1)(det A)(detP ) = (detP)-1(detA)(detP) = detA$ となる。したがって $f$ は矛盾なく定義できる。
を一つ固定する。にで定まる同値関係を考え、を含む同値類を , 同値類の全体の集合をで表す (問 34 参照)。
1. (1) $m, n ∈ ℕ$ とする。 $f : ℤ∕m ℤ → ℤ∕nℤ$ , $f(a+ m ℤ) = a + nℤ$ が矛盾なく定義できるための条件を求めよ。
2. (2) $g : ℤ∕nℤ × ℤ∕nℤ → ℤ ∕nℤ$ , $g(a +n ℤ,b+ nℤ) = (a + b) + nℤ$ は矛盾なく定義できることを示せ。
-
1. (1) 矛盾なく定義できるためには「 $a+ m ℤ = b+ mℤ$ のとき $a + nℤ = b+ nℤ$ 」であればよい。 $m + m ℤ = 0 + mℤ$ であることに注意すれば $n | m$ でなければならない。逆に $n | m$ とする。 $m = nd$ ( $d ∈ ℕ$ ) とする。 $a + mℤ = b+ m ℤ$ とすると、ある $ℓ ∈ ℤ$ があって $a - b = m ℓ = ndℓ$ である。よって $a+ nℤ = b+ nℤ$ である。
  以上より $f$ が矛盾なく定義できるための必要十分条件は $n | m$ である。
2. (2) $a + nℤ = a′ + n ℤ$ かつ $b+ nℤ = b′ + nℤ$ とする。ある $s,t ∈ ℤ$ があって $a- a′ = sn$ , $b- b′ = tn$ である。このとき $(a + b)- (a′ + b′) = (a- a′)+ (b - b′) = sn +tn = (s+ t)n$ となるから $(a+ b)+ nℤ = (a′ + b′)+ nℤ$ となり $f$ は矛盾なく定義される。
を集合、を上の関係とする。
1. (1) $R$ を含む同値関係が存在することを示せ。
2. (2) $R$ を含む順序は存在するとは限らない。 $R$ を含む順序が存在しないような例を作れ。
-
1. (1) $X × X$ は任意の関係を含む同値関係であるから、 $X × X$ が求めるものである。
2. (2) $X = {a,b}$ ( $a ⁄= b$ ) とする。 $R = X × X$ とおくと $R$ を含む関係は $R$ のみである。 $(a,b) ∈ R$ , $(b,a) ∈ R$ で $a ⁄= b$ なので $R$ は順序ではない。よって $R$ を含む順序は存在しない。
$R$ を集合 $X$ 上の関係とする。 $R$ に含まれる順序、および同値関係は存在するとは限らない。それらが存在しないような例を作れ。
-

$X$ は空集合でないとし、 $R$ を空集合とすればよい。 $x 戈 X$ について $(x,x)$ は順序、および同値関係に含まれなくてはならないが、 $R$ がそれを含まないので、任意の部分集合もそれを含まない。
に次のように関係を定める。「に対して、であるとき」
1. (1) $~$ は同値関係であることを示せ。
2. (2) この同値関係に関して $r ∈ ℝ$ を含む同値類を求めよ。
3. (3) この同値関係による完全代表系を一組求めよ。
4. (4) この同値関係による類別を書け。
-
1. (1)
  - 任意の $r ∈ ℝ$ に対して $r- r = 0 ∈ ℤ$ なので $r ~ r$ である。
  - $r ~ s$ とする。 $a = r- s$ とおくと $a ∈ ℤ$ である。このとき $s - r = - a ∈ ℤ$ であるから $s ~ r$ である。
  - $r ~ s$ , $s ~ t$ とする。 $a = r- s$ , $b = s- t$ とおくと $a,b ∈ ℤ$ である。このとき $r- t = (r- s)+ (s- t) = a +b ∈ Z$ となり $r ~ t$ である。
  以上よりは同値関係である。
2. (2) ${r+ a | a ∈ ℤ }$
3. (3) 例えば $[0,1)$ が完全代表系である。 (完全代表系は一意ではないので、これ以外にも色々と考えられる。)
4. (4) $⋃ℝ = r∈[0,1){r+ a | a ∈ ℤ}$
集合上の関係を「に対してとはであること」と定める。
1. (1) $~$ は同値関係であることを示せ。
2. (2) $Q = (ℤ × ℕ)∕ ~$ とおく。また $(a,b)$ を含む同値類を $[a,b]$ と書くことにする。写像 $φ : Q × Q → Q$ , $φ ([a,b],[c,d]) = [ac,bd]$ が矛盾なく定義できることを示せ。
3. (3) (2) と同様の記号を用いる。写像 $ψ : Q × Q → Q$ , $ψ ([a,b],[c,d]) = [ad + bc,bd]$ が矛盾なく定義できることを示せ。
-
1. (1)
  - 任意の $ℤ× ℕ$ の元 $(a,b)$ に対して、 $ab = ab$ であるから、 $a ~ b$ である。
  - $(a,b) ~ (c,d)$ とする。このとき $ad = bc$ である。よって $bc = ad$ であるから、 $(c,d) ~ (a,b)$ である。
  - $(a,b) ~ (c,d)$ , $(c,d) ~ (e,f)$ とする。 $ad = bc$ , $cf = de$ である。よって $adf = bcf = bde$ である。ここで $d ∈ ℕ$ なので $d ⁄= 0$ であり、 $af = be$ となる。したがって $(a,b) ~ (e,f)$ が成り立つ。
  以上から、関係は集合上の同値関係である。
2. (2) $′ ′[a,b] = [a ,b ]$ , $′ ′[c,d] = [c ,d]$ と仮定する。 $′ ′ ′′[ac,bd] = [a c,bd ]$ であることを示せばよい。
  $′ ′[a,b] = [a ,b ]$ より $′ ′ab = a b$ である。 $′ ′[c,d] = [c,d]$ より $′ ′cd = cd$ である。よって $′′ ′′(ac)(bd ) = (ac )(bd)$ が成り立ち $′′ ′ ′[ac,bd] = [ac ,b d]$ である。
3. (3) $[a,b] = [a′,b′]$ , $[c,d] = [c′,d′]$ と仮定する。 $[ad + bc,bd] = [a′d′ + b′c′,b′d′]$ であることを示せばよい。
  $[a,b] = [a′,b′]$ より $ab′ = a′b$ である。 $[c,d] = [c′,d′]$ より $cd′ = c′d$ である。このとき
  $(ad+ bc)b′d′ = ab′dd′ + bb′cd′ = a′bdd′ + bb′c′d = (a′d′ +b′c′)bd$
  であるから $[ad +bc,bd] = [a′d′ + b′c′,b′d′]$ である。
この同値関係による同値類は有理数と一対一に対応している。