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

Equivalence relations同値関係どうちかんけい and partitions分割ぶんかつ

1導入どうにゅう

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

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

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

1Introduction

The purpose of an equivalence relation同値関係どうちかんけい is to classify objects対象たいしょう by a rule that says when they should be treated as the same. The point is not that the objects are literally equal, but that they are the same for the purpose currently being considered.

For example, if integers are classified by their remainder when divided by 3, then $$1,4,7$$1,4,7 belong to the same class. This does not mean $$1=4$$1=4. It means they are the same as long as only the remainder modulo 3 is being observed.

An equivalence relation divides objects into boxes called equivalence classes同値類どうちるい; unlike an order, it does not place one object above or below another.

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と呼よばれることがある。

2Terms and definitions

A binary relation二項関係にこうかんけい $$\sim$$\sim on a set集合しゅうごう $$A$$A is an equivalence relation同値関係どうちかんけい if it satisfies the following three conditions for arbitrary $$a,b,c\in A$$a,b,c\in A.

For $$a\in A$$a\in A, the equivalence class同値類どうちるい of $$a$$a is defined by

An equivalence class is the set of elements regarded as the same kind as $$a$$a.

A partition分割ぶんかつ of $$A$$A is a collection of nonempty subsets of $$A$$A that are pairwise disjoint and whose union is all of $$A$$A. The subsets in the partition are often called blocks.

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 つ示しめせばよい。

3Strategy

To verify an equivalence relation同値関係どうちかんけい, prove the three conditions separately. In particular, transitivity推移性すいいせい is easy to miss: from $$a\sim b$$a\sim b and $$b\sim c$$b\sim c, one must be able to derive $$a\sim c$$a\sim c.

The reason to introduce an equivalence relation is to divide a set into equivalence classes. Therefore, before asking what changes, ask what feature is being ignored so that objects are identified.

Prove the three properties separately. To disprove reflexivity, give an element for which $$a\text{[PARSE ERROR: Undefined("Command("not")")]}\sim a$$a\not\sim a. To disprove symmetry or transitivity, give one pair or triple that violates the corresponding implication.

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

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

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

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

4Intuitive explanation

An equivalence relation同値関係どうちかんけい can be imagined as coloring the elements of a set. Elements with the same color are treated as equivalent. Reflexivity反射性はんしゃせい means every element has some color, symmetry対称性たいしょうせい means sameness of color has no direction, and transitivity推移性すいいせい means the color does not change in the middle of a chain.

When this coloring is valid, the set is divided into non-overlapping subsets. That division is a partition分割ぶんかつ.

Equivalence classes behave like disjoint boxes: every element belongs to exactly one. If two classes overlap at even one element, symmetry and transitivity force them to be the same class.

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] である。

5Precise explanation: from equivalence relations to partitions

Suppose an equivalence relation同値関係どうちかんけい $$\sim$$\sim is given on $$A$$A. The collection of equivalence classes forms a partition分割ぶんかつ of $$A$$A. This means two things.

1. Every $$a\in A$$a\in A belongs to at least one equivalence class.
2. Any two equivalence classes are either equal or disjoint.

The first point follows from reflexivity反射性はんしゃせい. Since $$a\sim a$$a\sim a, we have $$a\in \left[a\right]$$a\in[a].

For the second point, suppose $$\left[a\right]\cap \left[b\right]\ne \text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$[a]\cap[b]\ne\varnothing. Then there exists $$x$$x such that $$x\in \left[a\right]$$x\in[a] and $$x\in \left[b\right]$$x\in[b]. By definition, $$x\sim a$$x\sim a and $$x\sim b$$x\sim b. By symmetry対称性たいしょうせい, $$a\sim x$$a\sim x, and by transitivity推移性すいいせい, $$a\sim b$$a\sim b.

Now take any $$y\in \left[a\right]$$y\in[a]. Then $$y\sim a$$y\sim a. Since $$a\sim b$$a\sim b, transitivity gives $$y\sim b$$y\sim b, so $$y\in \left[b\right]$$y\in[b]. Hence $$\left[a\right]\subseteq \left[b\right]$$[a]\subseteq[b]. The same argument gives $$\left[b\right]\subseteq \left[a\right]$$[b]\subseteq[a], so $$\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に留とどまる。

6Conversely, from partitions to equivalence relations

Let a partition分割ぶんかつ of $$A$$A be given. Define $$a\sim b$$a\sim b to mean that $$a$$a and $$b$$b belong to the same block of the partition. Then $$\sim$$\sim is an equivalence relation同値関係どうちかんけい.

Reflexivity反射性はんしゃせい holds because every element belongs to some block. Symmetry対称性たいしょうせい holds because the statement "belong to the same block" is symmetric in $$a$$a and $$b$$b. Transitivity推移性すいいせい holds because distinct blocks of a partition do not overlap: if $$a,b$$a,b are in the same block and $$b,c$$b,c are in the same block, then those two blocks share $$b$$b and therefore must be the same block, so $$a,c$$a,c are in the same block.

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

7Example: equivalence by congruence

7.1問題もんだい

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

7.1Problem

On the set of all integers $$\mathbb{Z}$$\mathbb Z, define $$a\sim b$$a\sim b to mean that $$a-b$$a-b is a multiple of 3. Verify that this is an equivalence relation同値関係どうちかんけい and describe the equivalence classes同値類どうちるい.

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へ分解ぶんかいすることを示しめしている。

7.2Explanation

For reflexivity反射性はんしゃせい, $$a-a=0$$a-a=0 is a multiple of 3, so $$a\sim a$$a\sim a.

For symmetry対称性たいしょうせい, suppose $$a\sim b$$a\sim b. Then $$a-b=3k$$a-b=3k for some integer $$k$$k. Hence $$b-a=-3k=3(-k)$$b-a=-3k=3(-k), so $$b\sim a$$b\sim a.

For transitivity推移性すいいせい, suppose $$a\sim b$$a\sim b and $$b\sim c$$b\sim c. Then $$a-b=3k$$a-b=3k and $$b-c=3\ell$$b-c=3\ell for integers $$k,\ell$$k,\ell. Adding the two equations gives $$a-c=3(k+\ell )$$a-c=3(k+\ell), so $$a\sim c$$a\sim c.

The equivalence classes are the classes according to remainders modulo 3:

This example shows how an equivalence relation同値関係どうちかんけい decomposes a set into non-overlapping classes.

8見分みわけ方かた

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

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

8Recognition criteria

• Use an equivalence relation同値関係どうちかんけい when objects should be divided into classes of the same kind.
• To prove that a relation is an equivalence relation, check reflexivity反射性はんしゃせい, symmetry対称性たいしょうせい, and transitivity推移性すいいせい separately.
• An equivalence class同値類どうちるい is not a chosen representative. It is the set of all elements equivalent to the representative.
• When a partition分割ぶんかつ appears, one can define an equivalence relation by saying that two elements are in the same block.

Match properties of the relation with properties of the classification: overlapping equivalence classes are equal, and changing the representative does not change its 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 に一致いっちする。

9Proof supplement: the two constructions are inverse

We have constructed the collection of equivalence classes

from an equivalence relation同値関係どうちかんけい, and an equivalence relation from a partition分割ぶんかつ by declaring two elements equivalent when they lie in the same block. Applying these constructions successively returns the original data.

Starting with an equivalence relation, $$x$$x and $$y$$y lie in the same equivalence class exactly when $$\left[x\right]=\left[y\right]$$[x]=[y], which is equivalent to $$x\sim y$$x\sim y. Thus the relation reconstructed from the partition is the original relation.

Starting with a partition $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C, the equivalence class of $$x$$x is exactly the unique block of $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C containing $$x$$x. Thus the partition reconstructed from the equivalence classes is $$\text{[PARSE ERROR: Undefined("Command("mathcal")")]}C$$\mathcal C itself.

10演習えんしゅうリンク

10Exercise links

11関連かんれんリンク

11Related links