同値関係どうちかんけいequivalence relationと分割ぶんかつpartition

1導入どうにゅう

同値関係どうちかんけいequivalence relationの目的もくてきは、対象たいしょうobjectを「同おなじものと見みなす」基準きじゅんで分類ぶんるいすることである。ここで重要じゅうようなのは、完全かんぜんに等ひとしいという意味いみではなく、今いまの目的もくてきに対たいして同おなじ扱あつかいをする、という意味いみである。

たとえば整数せいすうを 3 で割わった余あまりで分類ぶんるいすると、$$1,4,7$$1,4,7 は同おなじ分類ぶんるいに入はいる。これは $$1=4$$1=4 という意味いみではない。3 で割わった余あまりを見みる限かぎり同おなじ、という意味いみである。

同値関係どうちかんけいequivalence relationは、対象たいしょうを「同おなじ種類しゅるい」として分わけるための関係かんけいである。順序じゅんじょのように上うえや下したを決きめるのではなく、同値類どうちるいequivalence classという箱はこへ分類ぶんるいする。

2用語ようごと定義ていぎ

集合しゅうごうset $$A$$A 上うえの二項関係にこうかんけいbinary relation $$\sim$$\sim が同値関係どうちかんけいequivalence relationであるとは、次つぎの 3 条件じょうけんを満みたすことである。表ひょうの $$a,b,c$$a,b,c は $$A$$A の任意にんいの元げんelementとする。

$$a\in A$$a\in A に対たいして、$$a$$a の同値類どうちるいequivalence classを

で定義ていぎする。同値類どうちるいequivalence classは、$$a$$a と同類どうるいと見みなされる元げんelementを集あつめた集合しゅうごうsetである。

同値関係どうちかんけいequivalence relationには反射性はんしゃせいreflexivity・対称性たいしょうせいsymmetry・推移性すいいせいtransitivityの三みっつがすべて必要ひつようである。そこから得えられる分割ぶんかつpartitionは、空からでない部分集合ぶぶんしゅうごうたちが互たがいに重かさならず、全体ぜんたいを覆おおう構造こうぞうである。分割ぶんかつを作つくる各かく部分集合ぶぶんしゅうごうsubsetは、分割ぶんかつのブロックblockと呼よばれることがある。

3方針ほうしん

同値関係どうちかんけいequivalence relationを確認かくにんするときは、3 条件じょうけんを別々べつべつに証明しょうめいする。特とくに推移性すいいせいtransitivityは見落みおとしやすい。$$a\sim b$$a\sim b と $$b\sim c$$b\sim c から $$a\sim c$$a\sim c を導みちびけるかを必かならず確認かくにんする。

また、同値関係どうちかんけいequivalence relationを導入どうにゅうする理由りゆうは、集合しゅうごうsetを同値類どうちるいequivalence classに分わけるためである。したがって「何なにが変かわるか」よりも、「何なにを無視むしして同一視どういつしするか」を先さきに考かんがえる。

証明しょうめいでは、三みっつの性質せいしつを別々べつべつに確認かくにんする。失敗しっぱいを示しめすときは、反射性はんしゃせいなら $$aRa$$aRa が欠かける元げんelement、対称性たいしょうせいや推移性すいいせいなら条件じょうけんを破やぶる組くみを 1 つ示しめせばよい。

4直感的ちょっかんてきな説明せつめい

同値関係どうちかんけいequivalence relationは、集合しゅうごうsetの元げんelementに色いろを付つけることとして考かんがえられる。同おなじ色いろの元げんelementを同類どうるいと見みなす。反射性はんしゃせいreflexivityは各かく元げんelementが何なんらかの色いろを持もつこと、対称性たいしょうせいsymmetryは同おなじ色いろであることに向むきがないこと、推移性すいいせいtransitivityは色いろが途中とちゅうで変かわらないことに対応たいおうする。

この色分いろわけが正ただしくできると、集合しゅうごうsetは互たがいに重かさならない部分集合ぶぶんしゅうごうsubsetに分わかれる。この分わけ方かたが分割ぶんかつpartitionである。

同値類どうちるいequivalence classは互たがいに重かさならない箱はこであり、各かく元げんelementは必かならず 1 つの箱はこに入はいる。2 つの箱はこが少すこしでも重かさなれば、推移性すいいせいtransitivityにより実じつは同おなじ箱はこになる。

5厳密げんみつな説明せつめい：同値関係どうちかんけいequivalence relationから分割ぶんかつpartitionへ

同値関係どうちかんけいequivalence relation $$\sim$$\sim が与あたえられると、同値類どうちるいequivalence classの集あつまりは $$A$$A の分割ぶんかつpartitionになる。つまり、次つぎの 2 つが成立せいりつする。

1. 任意にんいの $$a\in A$$a\in A は少すくなくとも 1 つの同値類どうちるいequivalence classに属ぞくする。
2. 2 つの同値類どうちるいequivalence classは、一致いっちするか、交まじわらないかのどちらかである。

まず 1 つ目めは、反射性はんしゃせいreflexivityより $$a\sim a$$a\sim a なので $$a\in \left[a\right]$$a\in[a] である。

つぎに 2 つ目めを示しめす。$$\left[a\right]\cap \left[b\right]\ne \text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$[a]\cap[b]\ne\varnothing とする。このとき、ある $$x$$x が存在そんざいして $$x\in \left[a\right]$$x\in[a] かつ $$x\in \left[b\right]$$x\in[b] である。定義ていぎより $$x\sim a$$x\sim a かつ $$x\sim b$$x\sim b である。対称性たいしょうせいsymmetryより $$a\sim x$$a\sim x であり、推移性すいいせいtransitivityより $$a\sim b$$a\sim b である。

任意にんいの $$y\in \left[a\right]$$y\in[a] を取とると、$$y\sim a$$y\sim a である。さらに $$a\sim b$$a\sim b なので、推移性すいいせいtransitivityより $$y\sim b$$y\sim b である。したがって $$y\in \left[b\right]$$y\in[b] であり、$$\left[a\right]\subseteq \left[b\right]$$[a]\subseteq[b] である。同様どうように $$\left[b\right]\subseteq \left[a\right]$$[b]\subseteq[a] なので $$\left[a\right]=\left[b\right]$$[a]=[b] である。

6逆ぎゃくに、分割ぶんかつpartitionから同値関係どうちかんけいequivalence relationへ

分割ぶんかつpartitionとは、$$A$$A の空からでない部分集合ぶぶんしゅうごうsubsetの集あつまりで、互たがいに交まじわらず、全体ぜんたいを覆おおうものである。

分割ぶんかつpartitionが与あたえられたら、「$$a$$a と $$b$$b が同おなじ部品ぶひんに属ぞくする」と定義ていぎして $$a\sim b$$a\sim b とする。このとき $$\sim$$\sim は同値関係どうちかんけいequivalence relationである。反射性はんしゃせいreflexivityは $$a$$a が必かならず何なんらかの部品ぶひんに属ぞくすることから従したがう。対称性たいしょうせいsymmetryは「同おなじ部品ぶひんに属ぞくする」が対称たいしょうな主張しゅちょうであることから従したがう。推移性すいいせいtransitivityについて、$$a,b$$a,b が同おなじ部品ぶひんに属ぞくし、$$b,c$$b,c も同おなじ部品ぶひんに属ぞくするとする。2 つの部品ぶひんは $$b$$b を共有きょうゆうするので、分割ぶんかつの部品ぶひんが互たがいに交まじわらないことから同一どういつである。したがって $$a,c$$a,c も同おなじ部品ぶひんに属ぞくする。

分割ぶんかつpartitionから同値関係どうちかんけいequivalence relationを作つくるときは、「同おなじブロックblockに属ぞくする」ことを関係かんけいにする。自分じぶんは自分じぶんと同おなじブロックblockに属ぞくし、向むきを逆ぎゃくにしても変かわらず、同おなじブロックblockを経由けいゆしても同おなじブロックblockに留とどまる。

7例題れいだい：合同ごうどうによる同値関係どうちかんけいequivalence relation

7.1問題もんだい

整数せいすう全体ぜんたい $$\mathbb{Z}$$\mathbb Z に対たいして、$$a\sim b$$a\sim b を「$$a-b$$a-b が 3 の倍数ばいすうである」と定義ていぎする。これは同値関係どうちかんけいequivalence relationであることを確認かくにんし、同値類どうちるいequivalence classを述のべよ。

7.2解説かいせつ

反射性はんしゃせいreflexivityについて、$$a-a=0$$a-a=0 は 3 の倍数ばいすうなので $$a\sim a$$a\sim a である。

対称性たいしょうせいsymmetryについて、$$a\sim b$$a\sim b とすると、ある $$k\in \mathbb{Z}$$k\in\mathbb Z により $$a-b=3k$$a-b=3k と書かける。すると $$b-a=-3k=3(-k)$$b-a=-3k=3(-k) なので $$b\sim a$$b\sim a である。

推移性すいいせいtransitivityについて、$$a\sim b$$a\sim b かつ $$b\sim c$$b\sim c とする。すると、ある $$k,\ell \in \mathbb{Z}$$k,\ell\in\mathbb Z により $$a-b=3k$$a-b=3k、$$b-c=3\ell$$b-c=3\ell と書かける。両式りょうしきを足たすと $$a-c=3(k+\ell )$$a-c=3(k+\ell) なので $$a\sim c$$a\sim c である。

同値類どうちるいequivalence classは、3 で割わった余あまりごとに

である。この例れいは、同値関係どうちかんけいequivalence relationが集合しゅうごうsetを重かさならない分類ぶんるいclassificationへ分解ぶんかいすることを示しめしている。

8見分みわけ方かた

• 対象たいしょうを「同おなじ種類しゅるい」に分わけたいなら、同値関係どうちかんけいequivalence relationを考かんがえる。
• 同値関係どうちかんけいequivalence relation を示しめすには、反射性はんしゃせいreflexivity、対称性たいしょうせいsymmetry、推移性すいいせいtransitivityを別々べつべつに確認かくにんする。
• 同値類どうちるいequivalence class は、代表元だいひょうげんそのものではなく、代表元だいひょうげんと同類どうるいな元げんelementの集合しゅうごうsetである。
• 分割ぶんかつpartition が表あらわれたら、同おなじ部品ぶひんに属ぞくするという同値関係どうちかんけいequivalence relationを作つくれる。

見分みわけるときは、関係かんけいの性質せいしつと分類ぶんるいの性質せいしつを対応たいおうさせる。同値類どうちるいequivalence classが重かさなるなら同おなじ同値類どうちるいであり、代表元だいひょうげんを変かえても属ぞくする同値類どうちるいは変かわらない。

9証明しょうめい補足ほそく：2 つの構成こうせいは互たがいに逆ぎゃくである

ここまでで、同値関係どうちかんけいequivalence relation $$\sim$$\sim から同値類どうちるいの集あつまり

を作つくり、分割ぶんかつpartitionから「同おなじブロックblockに属ぞくする」という同値関係どうちかんけいを作つくった。この 2 つの構成こうせいを往復おうふくすると、最初さいしょの情報じょうほうに戻もどる。

同値関係どうちかんけいから始はじめた場合ばあい、$$x$$x と $$y$$y が同おなじ同値類どうちるいに属ぞくすることは $$\left[x\right]=\left[y\right]$$[x]=[y] と同値どうちであり、これは $$x\sim y$$x\sim y と同値どうちである。したがって分割ぶんかつから作つくり直なおした関係かんけいは元もとの $$\sim$$\sim に一致いっちする。

分割ぶんかつ $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C から始はじめた場合ばあい、$$x$$x の同値類どうちるいは $$x$$x を含ふくむ $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C の唯一ゆいいつのブロックblockそのものである。したがって同値類どうちるいを集あつめて作つくり直なおした分割ぶんかつは $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C に一致いっちする。

10演習えんしゅうリンク

11関連かんれんリンク