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

date2026-06-06description同値関係を、対象を重ならない同値類へ分類するための関係として導入し、分割との対応を丁寧に示す講義である。prerequisites集合の基本 / 関係の基本type講義statusactive

mathdiscrete-mathequivalence-relationlecture

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

1導入どうにゅう

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

たとえば整数せいすうを 3 で割わった余あまりで分類ぶんるいすると、 $1, 4, 7$ は同おなじ分類ぶんるいに入はいる。これは $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$ belong to the same class. This does not mean $1 = 4$ . It means they are the same as long as only the remainder modulo 3 is being observed.

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

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

条件じょうけん	式しき	意味いみ
反射性はんしゃせいreflexivity	$a \sim a$	自分じぶんは自分じぶんと同類どうるいである
対称性たいしょうせいsymmetry	$a \sim b \Rightarrow b \sim a$	同類どうるいであることに向むきはない
推移性すいいせいtransitivity	$a \sim b, b \sim c \Rightarrow a \sim c$	同類どうるいの連鎖れんさは同類どうるいである

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

[a] = {x \in A ∣ x \sim a}

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

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

2Terms and definitions

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

Condition	Formula	Meaning
reflexivity反射性はんしゃせい	$a \sim a$	every element is equivalent to itself
symmetry対称性たいしょうせい	$a \sim b \Rightarrow b \sim a$	being equivalent has no direction
transitivity推移性すいいせい	$a \sim b, b \sim c \Rightarrow a \sim c$	a chain of equivalences remains an equivalence

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

[a] = {x \in A ∣ x \sim a} .

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

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

3方針ほうしん

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

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

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

data/lecture/math/discrete-math/関係の基本-講義.n.md

3Strategy

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

data/lecture/math/discrete-math/関係の基本-講義.n.md

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分割ぶんかつ.

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

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

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

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

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

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

5Precise explanation: from equivalence relations to partitions

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

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

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

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

Now take any $y \in [a]$ . Then $y \sim a$ . Since $a \sim b$ , transitivity gives $y \sim b$ , so $y \in [b]$ . Hence $[a] \subseteq [b]$ . The same argument gives $[b] \subseteq [a]$ , so $[a] = [b]$ .

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

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

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

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

6Conversely, from partitions to equivalence relations

Let a partition分割ぶんかつ of $A$ be given. Define $a \sim b$ to mean that $a$ and $b$ belong to the same block of the partition. Then $\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$ and $b$ . Transitivity推移性すいいせい holds because distinct blocks of a partition do not overlap: if $a, b$ are in the same block and $b, c$ are in the same block, then those two blocks share $b$ and therefore must be the same block, so $a, c$ are in the same block.

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

7Example: equivalence by congruence

7.1問題もんだい

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

7.1Problem

On the set of all integers $Z$ , define $a \sim b$ to mean that $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$ は 3 の倍数ばいすうなので $a \sim a$ である。

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

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

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

[0] = {[PARSE ERROR: Undefined("Command(\"dots\")")], - 6, - 3, 0, 3, 6, [PARSE ERROR: Undefined("Command(\"dots\")")]}

[1] = {[PARSE ERROR: Undefined("Command(\"dots\")")], - 5, - 2, 1, 4, 7, [PARSE ERROR: Undefined("Command(\"dots\")")]}

[2] = {[PARSE ERROR: Undefined("Command(\"dots\")")], - 4, - 1, 2, 5, 8, [PARSE ERROR: Undefined("Command(\"dots\")")]}

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

data/lecture/math/abstract-algebra/同値関係と剰余類の基本-講義.n.md

7.2Explanation

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

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

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

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

[0] = {[PARSE ERROR: Undefined("Command(\"dots\")")], - 6, - 3, 0, 3, 6, [PARSE ERROR: Undefined("Command(\"dots\")")]},

[1] = {[PARSE ERROR: Undefined("Command(\"dots\")")], - 5, - 2, 1, 4, 7, [PARSE ERROR: Undefined("Command(\"dots\")")]},

[2] = {[PARSE ERROR: Undefined("Command(\"dots\")")], - 4, - 1, 2, 5, 8, [PARSE ERROR: Undefined("Command(\"dots\")")]} .

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

data/lecture/math/abstract-algebra/同値関係と剰余類の基本-講義.n.md

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.

9証明しょうめい補足ほそく：同値関係どうちかんけいと分割ぶんかつは同おなじ情報じょうほうである

同値関係どうちかんけいequivalence relation からは、同値類どうちるいの集あつまり

X / \sim = {[x] ∣ x \in X}

ができる。これが $X$ の分割ぶんかつpartition になることを証明しょうめいする。

まず、反射性はんしゃせいより $x \sim x$ なので、 $x \in [x]$ である。したがってどの要素ようそも少すくなくとも一ひとつの類るいに入はいる。

つぎに、二ふたつの同値類どうちるい $[x]$ と $[y]$ が交まじわるとする。 $z \in [x] \cap [y]$ を取とる。このとき $z \sim x$ かつ $z \sim y$ である。対称性たいしょうせいより $x \sim z$ 、推移性すいいせいより $x \sim y$ である。すると $u \in [x]$ なら $u \sim x \sim y$ なので $u \in [y]$ である。同おなじ議論ぎろんで $[y] \subseteq [x]$ も従したがう。よって $[x] = [y]$ である。

逆ぎゃくに、 $X$ の分割ぶんかつ $[PARSE ERROR: Undefined("Command(\"mathcal\")")] C$ が与あたえられたとする。 $x \sim y$ を「 $x$ と $y$ が同おなじ部品ぶひんに属ぞくする」と定義ていぎする。各要素かくようそは一ひとつの部品ぶひんに属ぞくするので反射性はんしゃせいが成なり立たつ。同おなじ部品ぶひんに属ぞくするという条件じょうけんは左右さゆうを入いれ替かえても変かわらないので対称性たいしょうせいが成なり立たつ。また、 $x, y$ が同おなじ部品ぶひん、 $y, z$ が同おなじ部品ぶひんなら、分割ぶんかつの部品ぶひんは重かさならないため $x, z$ も同おなじ部品ぶひんに属ぞくする。よって推移性すいいせいも成なり立たつ。

9Proof supplement: equivalence relations and partitions are the same data

From an equivalence relation同値関係どうちかんけい, form the collection of equivalence classes

X / \sim = {[x] ∣ x \in X} .

This is a partition分割ぶんかつ of $X$ . First, by reflexivity, $x \sim x$ , so $x \in [x]$ . Therefore every element lies in at least one class.

Next, suppose two equivalence classes $[x]$ and $[y]$ intersect. Take $z \in [x] \cap [y]$ . Then $z \sim x$ and $z \sim y$ . By symmetry, $x \sim z$ ; by transitivity, $x \sim y$ . If $u \in [x]$ , then $u \sim x \sim y$ , so $u \in [y]$ . The same argument gives $[y] \subseteq [x]$ . Hence $[x] = [y]$ .

Conversely, let $[PARSE ERROR: Undefined("Command(\"mathcal\")")] C$ be a partition of $X$ . Define $x \sim y$ to mean that $x$ and $y$ belong to the same block. Each element belongs to a block, so reflexivity holds. The condition is symmetric, so symmetry holds. If $x, y$ are in the same block and $y, z$ are in the same block, then the two blocks intersect at $y$ , and because blocks of a partition do not overlap, they are the same block. Therefore $x, z$ are in the same block, so transitivity holds.

10演習えんしゅうリンク

data/exercise/math/discrete-math/関係と同値関係-基本演習.n.md

10Exercise links