4.2 同値関係と同値類

4.2.1 同値関係

反射的，対称的かつ推移的である関係を同値関係(equivalence relation)とよぶ． 等号$=$はこの３条件をみたすから同値関係である．また，三角形の合同関係も同値関係である． しかし，実数の大小関係$<$は対称的ではないので同値関係ではない．

例題 4.3   $f:A\longrightarrow B\strut$とする．このとき， $x\sim x' \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut f(x)=f(x')\strut$とすると， $\sim$は$A$上の同値関係であることを示せ．

解： $\sim$が同値関係の条件R1,R2,R3をみたすことを示す．

R1: $f(x)=f(x)\strut$より$x\sim x$である．

R2: $x\sim x'\strut$とする．このとき， $f(x)=f(x')\strut$より， $f(x')=f(x)\strut$であるから $x'\sim x\strut$ となる．

R3: $x\sim x',x'\sim x''\strut$とする．このとき， $f(x)=f(x') \wedge f(x')=f(x'')\strut$より， $f(x)=f(x'')\strut$であるから $x\sim x''\strut$ となる． $\Box$

例題 4.4   正の整数$m$に対し，

$x\sim_m y \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut x-y\strut$ は$m$で割り切れる $\Leftrightarrow \exists k\in \mathbb{Z}[mk = x-y]\strut$

と定義すると，$\sim_m$は $\mathbb{Z}$ 上の同値関係であることを示せ．

解： $\sim_m$が同値関係の条件R1,R2,R3をみたすことを示す．

R1: $x\in \mathbb{Z}\strut$を任意の整数とする．このとき，$x-x=0$より，$x-x$は$m$で割り切れるから， $x\sim x$である．

R2: $x,y\in \mathbb{Z}\strut$を $x\sim_m y\strut$をみたす任意の整数とする．$x-y\strut$が$m$で割り切れるから， $x-y\strut$を$m$で割ったときの商を$c$とすると， $x-y=cm\strut$である．このとき， $y-x=-(x-y)=-cm=(-c)m\strut$であるから， $y-x\strut$も$m$で割り切れる．よって， $y\sim_m x\strut$である．

R3: $x,y,z\in \mathbb{Z}\strut$を $x\sim_m y\strut$かつ $y\sim_m z\strut$をみたす任意の整数とする．(2)と同様に， $x-y\strut$を$m$で割ったときの商を$c$，$y-z\strut$を$m$で割ったときの商を$d$とすると， $x-y=cm, y-z=dm\strut$である． このとき， $x-z=(x-y)+(y-z)=cm + dm=(c+d)m\strut$より，$x-z$も$m$で割り切れる．よって，$x\sim_m z$である．

従って，$\sim_m$は条件R1,R2,R3をみたすから同値関係である． $\Box$

問題 4.5   $x$を $m( \ne 0)\strut$で割ったときの余りを $x {\mathrm {mod}} m$で表す．このとき，

$$x\sim_5 y \Leftrightarrow x {\mathrm {mod}} 5=y {\mathrm {mod}} 5\strut$$

を示せ．

問題 4.6   $\mathbb{Q}\strut \times \mathbb{Q}\strut \strut$において，関係$\sim$を

$$(p,q)\sim (r,s) \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut p-q=r-s\strut$$

により定める．$\sim$は同値関係であることを示せ．

問題 4.7   $\mathbb{Q}\strut ^+:=\{q\in \mathbb{Q}\strut \bigm \vert q > 0\}\strut$とする． $\mathbb{Q}\strut ^+ \times \mathbb{Q}\strut ^+\strut$において，関係$\sim$を

$$(p,q)\sim (r,s) \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut ps=qr\strut$$

により定める．$\sim$は同値関係であることを示せ．

問題 4.8   $\mathbb{Q}\strut \times \mathbb{Q}\strut \strut$において，関係$\sim$を

$(p,q)\sim (r,s) \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut (p,q)=t(r,s)$ となる$0\strut$でない有理数$t$が存在する

により定める．$\sim$は同値関係であることを示せ．

問題 4.9   ${\cal F}\strut$を実数列全体の集合とする． ${\cal F}\strut$上の関係$\sim$を次のように定義する．

$\{a_n\}\strut\sim \{b_n\}\strut\stackrel{\mathrm{def}}{ \Leftrightarrow }\strut$ある番号$N$が存在して， $n\geq N$となる任意の$n$に対し， $a_n= b_n\strut$である．

$\sim$は同値関係であることを示せ．

問題 4.10   $f:A\xrightarrow[onto]{1-1} A\strut$に対し， $f^0:=Id_A, f^n:=\overbrace{f\circ f\circ \cdots \circ f}^{n}, f^{-n}:=\overbrace{f^{-1}\circ f^{-1}\circ \cdots \circ f^{-1}}^n\strut$とする．

$$a\sim b \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut a=f^k(b)$$    for some $$k\in \mathbb{Z}\strut$$

とすると$\sim$は同値関係であることを示せ．

問題 4.11   $M_n(\mathbb{R})\strut$を実数上の$n$次正方行列全体とする． $M_n(\mathbb{R})\strut$上の関係$\sim$を次のように定義する．

$A\sim B\stackrel{\mathrm{def}}{ \Leftrightarrow }\strut B=P^{-1}AP\strut$をみたす正則な$n$次行列$P$が存在する．

$\sim$は同値関係であることを示せ．

問題 4.12   $\mathbb{R}$から $\mathbb{R}$への関数全体の集合 $\mathbb{R}\longrightarrow \mathbb{R}$ 上で以下の関係を考える．これらはそれぞれ同値関係であるかどうか調べよ．

1. $f,g \in \mathbb{R}\longrightarrow \mathbb{R}\strut$に対し，
   $$fRg\stackrel{\mathrm{def}}{ \Leftrightarrow }\strut \exists r \in \mathbb{R}[ f(r)=g(r)]\strut$$

2. $f,g \in \mathbb{R}\longrightarrow \mathbb{R}\strut$に対し，
   $$fSg\stackrel{\mathrm{def}}{ \Leftrightarrow }\strut \forall r \in \mathbb{R}[ f(r)=g(r)]\strut$$

4.2.2 同値類

$\sim$を$A$上の同値関係とする．任意の$a\in A$に対し，$a$と同値な関係にある$A$の元全体を $[a]_{\sim}\strut$で表すことにする．すなわち，

$$[a]_{\sim}:=\{b \in A \bigm \vert a\sim b\}\strut$$

とおく．文脈から考えている同値関係が明らかなときは，単に$[a]\strut$で表すことにする． $[a]\strut$の形の集合を同値類(equivalence class)とよび，$a$をその同値類の代表元 とよぶ． 代表元の取り方は，一意的には決まらない²⁰．$a\sim b$のとき，$a$を代表元として表していた同値類$[a]\strut$を，表現を変えて$b$を代表元とする同値類$[b]\strut$で置き換えることを，“代表元の置き換え”あるいは“代表元の取り換え”とよぶ．

例 4.13  

例題4.4において$m=5$とする．このとき，$0\strut$を代表元とする $\sim_5\strut$による同値類$[0]\strut$は 問題4.5より，$5$で割り切れる整数全体の集合になる．

問題 4.14   上の例において，同値類$[3]\strut$はどのような集合か述べよ．

定理 4.15   $\sim$を$A$上の同値関係とするとき，次のことが成り立つ．

1. $\forall a,a' \in A(a\sim a' \rightarrow [a]=[a'] )\strut$
2. $\forall a,a' \in A (a\sim\!\!\!\!\!/ a' \rightarrow [a]\cap [a']=\varnothing )\strut$
3. $$\bigcup_{a \in A}[a]=A\strut$$

証明： 1: $a\sim a'\strut$とする．このとき， $x \in [a] \Leftrightarrow a \sim x \Leftrightarrow a'\sim x \Leftrightarrow x \in [a']\strut$である． よって， $[a]=[a']\strut$である．

2: 対偶を示す． $[a]\cap [a']\ne\varnothing\strut$とすると， $x \in [a]\cap [a']\strut$である$x$が存在する．このとき， $a\sim x \wedge a'\sim x\strut$であるから $a\sim a'\strut$となる．

3: 任意の$a\in A$に対し， $[a]\subseteq A\strut$であるから，定理3.5より $$\bigcup_{a \in A}[a]\subseteq A\strut$$ は明らか． $A \subseteq \displaystyle \bigcup_{a \in A}[a]\strut$を示す．$x\in A$とする． $x \in [x]\strut$であり，また 命題3.4より $[x]\subseteq\displaystyle \bigcup_{a \in A}[a]\strut$であるから， $x \in \displaystyle \bigcup_{a \in A}[a]\strut$である． $\Box$

定理4.15より相異なる$[a]\strut$を集めると，$A$を互いに共通部分のない部分集合で分割することになる．

例 4.16  

$\mathbb{R}$ 上で定義された微分可能な関数の全体を ${\cal F}\strut$とする． ${\cal F}\strut$上の関係$\sim$を

$$f\sim g \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut f'=g'\strut$$

により定義する（ただし、$f',g'$はそれぞれ$f,g\strut$の導関数とする）と，$\sim$は同値関係であり，$[f]\strut$は$f'\strut$の原始関数全体である．

問題 4.17   自然数$m$に対し，集合 $A(m)\strut$を$m$の素因数の集合とする． $\mathbb{N}$ 上の関係$\sim$を $m\sim n \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut A(m)=A(n)\strut$により定義する． 但し， $A(1)=\{1\}\strut$とする．次の問に答えよ．

1. $\sim$は同値関係であることを示せ．
2. $2$を代表元とする同値類はどのような集合であるか．

問題 4.18   自然数$m$に対し， $N(m)\strut$を$m$の約数の個数とする． $\mathbb{N}$ 上の関係$\sim$を $m\sim n \stackrel{\mathrm{def}}{ \Leftrightarrow }\strut N(m)=N(n)\strut$

により定義する．このとき，次の問に答えよ．

1. $\sim$は同値関係であることを示せ．
2. $3$を代表元とする同値類はどのような集合であるか．