同値関係どうちかんけいequivalence relationと剰余類じょうよるいresidue class

date2026-06-06document_iddoc_03e8d91ec8a9df8b45d2aa5890853ebbdescription同値関係、同値類、商集合、剰余類を、代表元によらない構造を作る準備として説明する。prerequisites[同値関係/どうちかんけい]と[分割/ぶんかつ] / [商集合/しょうしゅうごう]と[自然/しぜん]な[射影/しゃえい]type講義content_typelecturestatusactive

mathabstract-algebradiscrete-mathlecture

抽象代数ちゅうしょうだいすうで商構造しょうこうぞうを作つくる前まえに、「どの元げんを同おなじものとして扱あつかうか」を決きめる必要ひつようがある。そのための道具どうぐが同値関係どうちかんけいである。

同値関係どうちかんけいは、対象たいしょうを分類ぶんるいする規則きそくである。分類ぶんるいされた一ひとつ一ひとつの箱はこが同値類どうちるいequivalence classであり、同値類どうちるい全体ぜんたいの集合しゅうごうが商集合しょうしゅうごうquotient setである。

data/lecture/math/discrete-math/equivalence-relations-and-partitions.lecture.n.md data/lecture/math/discrete-math/quotient-sets-and-canonical-projections.lecture.n.md

equivalence relation同値関係どうちかんけい and residue class剰余類じょうよるい

Before building quotient structures in abstract algebra抽象代数ちゅうしょうだいすう, we must decide which elements will be treated as the same. The tool for doing this is an equivalence relation同値関係どうちかんけい.

An equivalence relation同値関係どうちかんけい is a rule for classifying objects. Each box in the classification is an equivalence class同値類どうちるい, and the set of all equivalence classes is the quotient set商集合しょうしゅうごう.

data/lecture/math/discrete-math/equivalence-relations-and-partitions.lecture.n.md data/lecture/math/discrete-math/quotient-sets-and-canonical-projections.lecture.n.md

1同値関係どうちかんけいの三みっつの条件じょうけん

集合しゅうごう $X$ 上じょうの関係かんけい $\sim$ が同値関係どうちかんけいであるとは、任意にんいの $x, y, z \in X$ に対たいして次つぎを満みたすことである。

x \sim x

x \sim y \Rightarrow y \sim x

x \sim y and y \sim z \Rightarrow x \sim z

それぞれ、反射性はんしゃせい、対称性たいしょうせい、推移性すいいせいである。

1The three conditions for an equivalence relation同値関係どうちかんけい

A relation $\sim$ on a set $X$ is an equivalence relation同値関係どうちかんけい if it satisfies the following conditions for every $x, y, z \in X$ .

x \sim x

x \sim y \Rightarrow y \sim x

x \sim y and y \sim z \Rightarrow x \sim z

These are called reflexivity, symmetry, and transitivity, respectively.

2同値類どうちるい

元げん $a \in X$ の同値類どうちるいを

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

で定義ていぎする。同値類どうちるいは、代表元だいひょうげん $a$ そのものではなく、 $a$ と同おなじものとみなされる元げん全体ぜんたいの集合しゅうごうである。

代表元だいひょうげんは名前なまえであり、同値類どうちるいが本ほん体たいである。実際じっさい、 $a \sim b$ であることと

[a] = [b]

であることは同値どうちである。 $a \sim b$ かつ $x \in [a]$ なら、 $x \sim a$ と推移性すいいせいから $x \sim b$ 、すなわち $x \in [b]$ である。逆ぎゃくに $x \in [b]$ なら、対称性たいしょうせいより $b \sim a$ であり、 $x \sim b$ と推移性すいいせいから $x \sim a$ 、すなわち $x \in [a]$ である。したがって $[a] = [b]$ となる。逆ぎゃくに $[a] = [b]$ なら、反射性はんしゃせいより $a \in [a] = [b]$ だから $a \sim b$ である。

同値類どうちるいを全部ぜんぶ集あつめた集合しゅうごうを商集合しょうしゅうごうquotient setという。つまり、商集合しょうしゅうごうでは元げんそのものではなく、同値類どうちるいを新あたらしい元げんとして扱あつかう。

2Equivalence classes

The equivalence class同値類どうちるい of an element $a \in X$ is defined by

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

An equivalence class同値類どうちるい is not the representative $a$ itself, but the set of all elements regarded as the same as $a$ .

The representative is a name; the equivalence class is the actual object. In fact, $a \sim b$ if and only if

[a] = [b]

If $a \sim b$ and $x \in [a]$ , then $x \sim a$ , so transitivity gives $x \sim b$ and hence $x \in [b]$ . Conversely, if $x \in [b]$ , symmetry gives $b \sim a$ , and transitivity applied to $x \sim b$ gives $x \sim a$ . Thus $x \in [a]$ , proving the reverse inclusion and therefore $[a] = [b]$ . Conversely, if $[a] = [b]$ , reflexivity gives $a \in [a] = [b]$ , so $a \sim b$ .

The set of all equivalence classes is called the quotient set商集合しょうしゅうごう. Thus, in a quotient set, the new elements are not the original elements themselves, but their equivalence classes.

3剰余類じょうよるい

正せいの整数せいすう $n$ を固定こていする。整数せいすう $a, b$ に対たいして

a \sim b ⟺ n ∣ (a - b)

と定さだめる。これは同値関係どうちかんけいである。反射性はんしゃせいは $a - a = 0$ かつ $n ∣ 0$ 、対称性たいしょうせいは $n ∣ (a - b)$ なら $b - a = - (a - b)$ より $n ∣ (b - a)$ 、推移性すいいせいは $n ∣ (a - b)$ かつ $n ∣ (b - c)$ なら $a - c = (a - b) + (b - c)$ より $n ∣ (a - c)$ であることから従したがう。このとき $a$ の同値類どうちるい

[a]_{n} = {a + k n ∣ k \in Z}

を剰余類じょうよるいresidue classという。

たとえば $n = 5$ のとき、

[2]_{5} = {[PARSE ERROR: Undefined("Command(\"dots\")")], - 8, - 3, 2, 7, 12, [PARSE ERROR: Undefined("Command(\"dots\")")]}

である。これらは全すべて 5 で割わった余あまりが 2 である。

3Residue classes

Fix a positive integer $n$ . For integers $a, b$ , define

a \sim b ⟺ n ∣ (a - b)

This is an equivalence relation. Reflexivity follows from $n ∣ 0$ ; symmetry follows because $n ∣ (a - b)$ implies $n ∣ (b - a)$ ; and transitivity follows because divisibility of both $a - b$ and $b - c$ implies divisibility of their sum $a - c$ . The equivalence class of $a$ ,

[a]_{n} = {a + k n ∣ k \in Z}

is called a residue class剰余類じょうよるい.

For example, when $n = 5$ ,

[2]_{5} = {[PARSE ERROR: Undefined("Command(\"dots\")")], - 8, - 3, 2, 7, 12, [PARSE ERROR: Undefined("Command(\"dots\")")]}

All of these integers have remainder 2 when divided by 5.

以下いかでは、法ほう $n$ を固定こていしている間あいだ、 $[a]_{n}$ を $[a]$ と略記りゃくきする。したがって以下いかの $[a]$ は、この $n$ を法ほうとする剰余類じょうよるいを表あらわす。

From this point on, while the modulus $n$ is fixed, we abbreviate $[a]_{n}$ as $[a]$ . Thus $[a]$ below means the residue class modulo this fixed $n$ .

4代表元だいひょうげんによらず定さだまること（well-definedness）

商集合しょうしゅうごうの上じょうで演算えんざんを定義ていぎするとき、代表元だいひょうげんの選えらび方かたに依存いぞんしてはいけない。この性質せいしつを「代表元だいひょうげんによらず定さだまる」、または well-defined であるという。

たとえば剰余類じょうよるいで

[a] + [b] = [a + b]

と定義ていぎしたいなら、 $a$ を同おなじ類るいの別べつの代表元だいひょうげん $a^{'}$ に変かえ、 $b$ を同おなじ類るいの別べつの代表元だいひょうげん $b^{'}$ に変かえても、結果けっかの類るいが同おなじであることを確認かくにんする必要ひつようがある。

この例れいでは、 $[a] = [a^{'}]$ と $[b] = [b^{'}]$ なら $n ∣ (a - a^{'})$ と $n ∣ (b - b^{'})$ である。したがって $n ∣ ((a + b) - (a^{'} + b^{'}))$ となり、 $[a + b] = [a^{'} + b^{'}]$ である。これで代表元だいひょうげんを変かえても和わが変かわらないことが証明しょうめいできた。

同様どうように積せきを $[a] [b] = [a b]$ と定義ていぎしたいなら、

a b - a^{'} b^{'} = a (b - b^{'}) + b^{'} (a - a^{'})

が $n$ の倍数ばいすうであることから $[a b] = [a^{'} b^{'}]$ を得える。したがって積せきも代表元だいひょうげんによらず定さだまる。この確認かくにんを省はぶくと、商集合しょうしゅうごうの上じょうの演算えんざんが実じつは定さだまっていない可能性かのうせいがある。

4Independence of representatives (well-definedness)

When defining an operation on a quotient set商集合しょうしゅうごう, the result must not depend on the choice of representative. This property is called well-definedness.

For example, if we want to define addition of residue classes by

[a] + [b] = [a + b]

then we must check that changing $a$ to another representative $a^{'}$ of the same class and changing $b$ to another representative $b^{'}$ of the same class does not change the resulting class.

In this example, $[a] = [a^{'}]$ and $[b] = [b^{'}]$ imply $n ∣ (a - a^{'})$ and $n ∣ (b - b^{'})$ . Hence $n ∣ ((a + b) - (a^{'} + b^{'}))$ , so $[a + b] = [a^{'} + b^{'}]$ . This proves that changing representatives does not change the sum.

Similarly, to define the product by $[a] [b] = [a b]$ , observe that

a b - a^{'} b^{'} = a (b - b^{'}) + b^{'} (a - a^{'})

is a multiple of $n$ , so $[a b] = [a^{'} b^{'}]$ . Thus the product is also independent of representatives. If this check is omitted, an operation on the quotient set may not actually be determined.

5注意ちゅうい：well-defined でない定義ていぎの例れい

$Z / 2 Z$ で、剰余類じょうよるい $[a]$ から整数せいすう $a$ そのものを返かえす写像しゃぞうを作つくろうとすると失敗しっぱいする。なぜなら $[0] = [2]$ だが、代表元だいひょうげんを 0 と選えらぶと値あたいは 0、2 と選えらぶと値あたいは 2 になるからである。

商集合しょうしゅうごうの元げんは代表元だいひょうげんではなく類るいである。類るいに対たいして何なにかを定義ていぎするときは、代表元だいひょうげんを変かえても同おなじ値あたいになることを必かならず確認かくにんする。

5Warning: an example of a definition定義ていぎ that is not well-defined

In $Z / 2 Z$ , suppose we try to define a map that sends a residue class $[a]$ to the integer representative $a$ itself. This fails because $[0] = [2]$ , but choosing representative 0 gives value 0, while choosing representative 2 gives value 2.

An element of a quotient set is a class, not a representative. Whenever something is defined on classes, one must check that changing representatives gives the same value.

6演習えんしゅうリンク

data/exercise/math/abstract-algebra/equivalence-relations-and-congruences.exercise.n.md

6Exercise link

data/exercise/math/abstract-algebra/equivalence-relations-and-congruences.exercise.n.md

7まとめ

同値関係どうちかんけいは、元げんを分類ぶんるいする規則きそくである。剰余類じょうよるいは整数せいすうを余あまりで分類ぶんるいした同値類どうちるいであり、合同式ごうどうしきと後あとに学まなぶ商構造しょうこうぞうの基礎きそになる。商集合しょうしゅうごうで演算えんざんするには、代表元だいひょうげんによらず結果けっかが定さだまることを必かならず確認かくにんする。

7Summary

An equivalence relation同値関係どうちかんけい is a rule for classifying elements. A residue class剰余類じょうよるい is an equivalence class同値類どうちるい that classifies integers by remainder, and it is the basis for congruences and quotient structures studied later. To operate on a quotient set, one must always check that the result is independent of the representative.