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

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

mathabstract-algebradiscrete-mathlecture

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

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.

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.

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.

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$ .

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.

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.

6Exercise link

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

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.