同値関係と同値類

以前の記事で二項関係を定義したが、その中でも特別な性質を満たすものを同値関係とよぶ。この同値関係は自然数を元に整数などを定義する際に重要となるので、ここで定義してその性質に触れておく。

同値関係

同値関係とは二項関係の一種である。その中でも「2つのモノはある意味で同じと言える」という関係となるものが同値関係である。この説明だけでは大ざっぱすぎて定義にならないので、定義としては以下を与える。

定義$R\subset x\times x$ を二項関係とする。任意の $a$, $b$, $c$ について

  • (反射律) $aRa$
  • (対称律) $aRb$ であれば $bRa$
  • (推移律) $aRb$, $bRc$ であれば $aRc$
のいずれも成立するとき、$R$ は $x$ 上の同値関係である。

これで、$R$ が同値関係なら「ある意味で同じ」という関係を表すようになっている。例として「偶奇という点で同じ」ことを表す同値関係を定義しよう。その場合たとえば\[M=\{\langle x,y\rangle \in \omega\times\omega \mid \exists z\exists w[x+2z=y+2w]\} \]と定義すればよい (注: 引き算を使えばもっと楽に定義できるが、この記事シリーズでは自然数の引き算を定義していないので、加法と乗法のみで表現した)。この定義の下では $xMy$ であることと、$x+2z=y+2w$ を満たす自然数 $z$, $w$ が存在すること ($x$ と $y$ が2の倍数加算の違いを除いて一致すること) が一致する。

定理上で定義した関係 $M$ は同値関係である。

(証明) 同値関係の定義に則って確かめる。まず $aMa$ を示す。$a+2\cdot 0=a+2\cdot 0$ より、$a+2z=a+2w$ の自然数解 $z$, $w$ が存在するので $aMa$。

次に $aMb$ を仮定して $bMa$ を導く。$aMb$ より、ある自然数 $z$, $w$ が $a+2z=b+2w$ を満たす。このとき $b+2w=a+2z$ であるので $bMa$。

最後に $aMb$, $bMc$ から $aMc$ を導く。$aMb$, $bMc$ より、ある自然数 $z$, $w$, $z'$, $w'$ が $a+2z=b+2w$, $b+2z'=c+2w'$ の双方を満す。このとき\begin{eqnarray}a+2(z+z') &=& a+2z+2z'\\&=&b+2w+2z' \\&=& b+2z'+2w\\&=&c+2w'+2w\\&=&c+2(w'+w)\end{eqnarray}より $aMc$。

$M$ の定義文の中の 2 の部分を他の非零自然数 $n$ に変えることで「$n$ で割った時の余りという点で同じ」ことを表す関係も作れる。自然数同士のそのような関係は $n$ を法とする合同関係と呼ばれる。2 の部分を 0 にすると、$aMb$ と $a=b$ が一致するので、通常の「等しい・同じ」を表す関係になる。

同値類

同値類は同値関係 $R$ によって同じと見なされるモノだけがすべて属する集合である。例えば上で例示した $\omega$ 上の同値関係 $M$ の同値類を考えると\begin{eqnarray}M_o&=&\{1,3,5,7,9,\dots\}\\M_e&=&\{0,2,4,6,8,\dots\}\end{eqnarray}という二つの同値類がある。たとえば $1M3$ だから 1 と 3 は同じ同値類に属し、$2M3$ ではないから 2 と 3 は異なる同値類に属する。

同値類は、それに属する1つの元を用いて表すことができる。$R$ を $x$ 上の同値関係としたとき、「$a$ と同値なモノがすべて属し、そうでないモノは属さない集合」である\[\{y\in x \mid yRa\}\]は $a$ の同値類と呼ばれ、$[a]$ や $[a]_R$ と書く。例えば上の $M_o$ は「1が属する同値類」という意味で $[1]$ とも表現する。1が属する同値類と3が属する同値類は同じ $M_o$ を指しているので $[1]=[3]$ である。この例の 1 や 3 のように同値類に属するモノのうち同値類の表現に使われたモノをその同値類の代表元とよぶ。原則としてどのモノを代表元に選んでもよい。

同値類について成立することを述べておく。

補題$R$ を $x$ 上の同値関係とする。$a,b\in x$ であるとき、

  1. $a\in [b]$
  2. $aRb$
  3. $[a]=[b]$
はみな一致する。すなわち、3つのうちどれかが成立するならすべて成立し、1つでも成立しないならすべて成立しない。

(証明) 『1 ならば 2』『2 ならば 3』『3 ならば 1』の三つを示せばよい。まずは『1 ならば 2』を示す。$a\in[b]$ であるとき、同値類 $[b]$ の定義より $aRb$。

次に『2 ならば 3』を示す。$aRb$ とし、$[a]$ に属するモノはすべて $[b]$ に属し、その逆も成立することを示す。$c\in[a]$ とすると $cRa$ であるので同値関係の推移性より $cRb$ であり、同値類 $[b]$ の定義より $c\in[b]$。また同値関係の対称性より $bRa$ なので $c\in[b]$ とすると同様に $c\in[a]$。以上から外延性の公理より $[a]=[b]$。

最後に『3 ならば 1』を示す。同値類の定義と同値関係の反射性より $a\in[a]$ であるので $[a]=[b]$ であれば外延性の公理より $a\in [b]$。

定理$R$ を $x$ 上の同値関係とする。$R$ の異なる同値類同士には、同じモノが属することは無い。つまり、 $x$ に属する任意の $a$, $b$ に対して、$[a]=[b]$ または $[a]\cap [b]= 0$。

(証明) $[a]\cap [b]\neq 0$ ならば $[a]=[b]$ であることを示す。$[a]\cap [b]\neq 0$ よりある $c\in x$ が $c\in[a]\cap[b]$ を満たす。したがって補題を用いると $c\in[a]$ より $[c]=[a]$ であり $c\in[b]$ より $[c]=[b]$ であるので $[a]=[b]$。

商集合

商集合は、同値関係 $R$ による同値類だけがすべて属する集合のことである。

定義$R$ を $x$ 上の同値関係とする。このとき、「$R$ による同値類がすべて属し、それ以外のモノが属さない集合」である\[\{y\in \mathfrak{P}(x) \mid \exists a[a\in x \land y=[a]_R]\}\]を商集合とよび $x/R$ と書く。

商集合は直感的な内包的記法を使えば\[\{[a]\subset x \mid a\in x\}\]とも書けるだろう。こう書くほうがどのような集合かわかりやすいかもしれない (分出公理によって存在が保障されることはわかりにくいが)。

上で例示した $\omega$ 上の同値関係 $M$ について考えると、その同値類は $M_o$ と $M_e$ の2つであったので、商集合は\[\omega/M=\{M_o,M_e\}\]となる。適当に代表元を定めて\[\omega/M=\{[0],[1]\}\]とも書ける。

同値類同士の二項関係・写像・二項演算の定義

$x$ に関する二項関係・写像・二項演算を用いて、$x/R$ に関するそれらを定義しようとする際は注意が必要である。例えば写像 $f:x\to x$ を使って写像 $f':x/R\to x/R$ を\[[x] \mapsto [f(x)]\]と定義しようとする場合、$f$ は $aRb$ であれば $[f(a)]=[f(b)]$ であるような写像でなくてはならない。なぜなら、同じモノ (同値類) を与えても代表元の選び方によって返るモノが変わるようでは写像とは言えないからである。より形式的に説明すると、$aRb$ であれば $[a]=[b]$ であるので $f'([a])=f'([b])$ でなくてはならない。このとき、$f'$ を上のように定義するなら $[f(a)]=[f(b)]$ とならざるを得ない。

例として $\omega/M$ 上の二項演算を $\omega$ 上の加法から作ってみよう。2つの同値類 $[a]$, $[b]$ に対して\[[a]+[b]=[a+b]\]と $\omega/M$ 上の加法を定める。これがきちんと定義できていることの確認として、代表元 $a$ と $b$ の選び方を変えても結果が同じ同値類になることを示せばよい。つまり、以下のように確認すればよい。

命題上の $\omega/M$ 上の二項演算はよく定義できている。

(証明) 代表元を $a$, $b$ から $a'$, $b'$ に変えても結果が変わらないことを示す。つまり $aMa'$, $bMb'$ であれば $[a+b]=[a'+b']$ であることを示す。

$aMa'$, $bMb'$ より自然数 $z$, $w$, $z'$, $w'$ が存在して、$a+2z=a'+2w$, $b+2z'=b'+2w'$。このとき\begin{eqnarray}(a+b)+2(z+z') &=& (a+2z)+(b+2z')\\ &=& (a'+2w)+(b'+2w')\\&=& (a'+b')+2(w+w')\end{eqnarray}より $(a+b)M(a'+b')$ であり、補題より $[a+b]=[a'+b']$。

以上よりこの加法はよく定義できていることが分かった。実際に試してみると (同値類が2つしかないので、演算も4通りしかないが) \[\begin{array}{rclclclcl} M_e + M_e & =&[0]+[0] & =&[0+0]& =&[0] & =&M_e \\ M_e + M_o & =&[2]+[3] & =&[2+3]& =&[5] & =&M_o\\M_o + M_e & =&[1]+[8] & =&[1+8]& =&[9] & =&M_o\\M_o + M_o & =&[3]+[1] & =&[3+1]& =&[4] & =&M_e\end{array}\]となっている。ここではあまり深く考えずに代表元を選んでみたが、上で証明した通り、どう選んでも結果は同じである。

ここでは触れないが $\omega/M$ 上の乗法もほぼ同様の方法で定義できる。そして、この加法と乗法が結合的で可換で分配律を満たすことは証明でき、加法と乗法を元に逆演算の減法と除法も定義できるので、その四則演算を伴って $\omega/M$ は位数が 2 の有限体と呼ばれる。また、一般の $n$ を法とする合同関係による商集合にも同様の方法で加法と乗法と減法を定義でき、加法と乗法の結合性と可換性と分配性を示せる。$n$ が素数であれば除法も定義できるので、その場合の商集合は位数が $n$ の有限体と呼ばれる。