Understanding Equivalence Classes?

Question

I am reading about equivalence classes and I would like to make sure I understood thins properly.

My book says:

The set of equivalence classes under this equivalence relation [$\pmod n$] will be denoted by $\mathbb{Z}/ n \mathbb{Z}$

Is the following true?

$$\displaystyle \text{ } \mathbb{Z}/ 3 \mathbb{Z}=\{\{0, 3, 6, ...\}, \{1, 4, 7,...\}, \{2, 5, 8, ... \}\}$$

The book proceeds:

We shall dennote the equivalence class of $a$ by $\bar a$

$\vdots$

We can define addition an multiplication for the elements of $\mathbb{Z}/ n \mathbb{Z}$, defining modular arithmetic as follows: for $\bar a, \bar b \in \mathbb{Z}/ n \mathbb{Z}$, define their sum and product by

$$ \bar a+ \bar b = \overline {a+b} \text{ } \text{ } \text{ } \text{ } \text{ } \text{ }\text{ and } \text{ } \text{ } \text{ } \text{ } \text{ } \bar a \cdot \bar b = \overline {a b}$$

The problem that I have with this statement is that what I think it tries to capture is (I think) different from what it literally says. I will use $\mod 3$ again as an example.

What I think i tries to capture is this: we have $3$ classes under this equivalence relation, $C_1 = \{0, 3, 6, ... \}$, $C_2 = \{1, 4, 7, ... \}$, and $C_3 = \{2, 5, 8, ...\}$. Let's say we want to add an element of $a \in C_1$ to an element $b \in C_2$, and we want to know in which class the result will be. To find this, we can take any element of $x \in C_1$ and add it to any element of $y \in C_2$. The number $x+y$ will always lie in the same class as $a+b$.

---

What I think the statement is literally saying is this (for example):

$$\{0, 3, 6, ... \} + \{1, 4, 7, ...\} = \overline {3+1} = \overline {4} = \{1, 4, 7...\}$$

which I guess is fine as a definition of $+$ on these sets, but seems rather useless.

Answer 1

Your example is correct, I think you are very close to having it understood fully. Just note that in mod 3 calculations, $\bar{3} = \bar{0}$, so it makes sense that in your particular example, the addition of (the equivalence class of) 3 does not change anything. Similarly, for example $$ \bar{2} + \bar{2} = \overline{2+2} = \bar{4} = \bar{1}, $$ which does make sense as $2+2 = 4 = 1 + 3 = 1 \mod 3$.

Answer 2

You are studying something more complex than equivalence classes on a set: they are congruence classes on a set with structure (in your example on a ring), that is, equivalence classes on which the structure of the structured set is induced. So in your example addition and multiplication of $\Bbb{Z}$ are induced on the family of congruence classes $\Bbb{Z}/n\Bbb{Z}$. Congruence relation are very special case of equivalence relations: it is not always possible to induce structures in this way. The map from the set to the family of congurence classes $\bar a$ is a homomorphism (that is called natural projection homomorphism), and every homomorphism can always be obtained as a composition of a natural projection homomorphism, a bijection and an inclusion map

Answer 3

You say

Let's say we want to add an element of $a \in C_1$ to an element $b > \in C_2$, and we want to know in which class the result will be.

That is not what the definition is doing. It is telling us how to add two equivalence classes. We do this by adding two equivalence classes by adding representatives of the two classes and finding the equivalence class of the result.

As a student I found the following helpful. (Though it is not the only way to think about it.)

We can think of rational numbers as equivalence classes of pairs of integer the second of which is not $0$. We can specify when two pairs on integers belong to the same class that is: $'frac{a}{b} = \frac{c}{d}$ if and pnly if $ad = bc$.

How to we add two of these equivalence classes?

By selecting representative with the same sEcond number (the same denominator) and adding the numerators.

We are giving a definition for addition of these (rather strange, new) objects called "equivalence classes".

Your summary beginning with

What I think the statement is literary saying is this (for example):

Is absolutely correct, but giving a definition of how to add these things is not useless, it is essential.

Answer 4

I'm going to expand on DanielSchepler's comment. This is a bit of a non-answer because it steps back from the question, though see the end. Frankly, though, the approach I'm about to describe more accurately describes how we use quotient sets in most cases than the "set of equivalence classes" approach. (I mean you don't actually think about the rational number $\frac{n}{d}$ as an infinite set of pairs of numbers. You think of it in terms of representatives and then require operations on them to be "well-defined". So $\frac{n}{d}\mapsto d$ is not a well-defined function, but $\frac{n}{d}\mapsto\frac{n^2}{d^2}$ is.)

Instead of (solely) relying on some implicit global notion of equality, we can consider equipping sets with an equivalence relation on the set that will tell you when two elements of the set should be considered "equal". This is called a setoid. I'll write $(S,\approx)$ for a setoid where $S$ is a set and ${\approx}\subseteq S\times S$ is an equivalence relation on $S$. As a very simply example, given a non-empty set $S$, we can consider the setoid $(S,\approx_1)$ where $x\approx_1 y$ holds for all $x,y\in S$. This setoid behaves like a one-element setoid. While $S$ may have more than one element, they are all considered "equal" in this setoid.

The defining property of functions is that they take equal inputs to equal outputs. Adapting this to the setoid context, this means that a function between setoids $f : (S,\cong)\to(T,\simeq)$ is a (normal, set) function $\overline f: S \to T$ which satisfies the property: for all $x,y\in S$, if $x \cong y$ then $\overline f(x)\simeq \overline f(y)$. In this case we say that $\overline f$ is a well-defined function from $(S,\cong)$ to $(T,\simeq)$.

Using the simple example from before, i.e. where $\approx_1$ relates everything to everything else, this means that all inputs must be sent to the "same" (as judged by $\simeq$) output. This is the sense in which that setoid behaves as a one-element setoid.

In this context, quotienting is a straightforward operation: it corresponds to equipping a setoid with a coarser equivalence relation, i.e. one that relates all the same things the original setoid's equivalence relation related but may relate additional things. So $\mathbb{Z}/n\mathbb{Z}$ takes the setoid $(\mathbb{Z},=_\mathbb{Z})$ and produces the setoid $(\mathbb{Z},\approx_n)$ where $x \approx_n y \Leftrightarrow \exists k\in\mathbb{Z}.x - y = kn$. Now, we have the interesting and important fact that addition and multiplication of integers is already a well-defined function with respect to the setoid $(\mathbb{Z},\approx_n)$. (Check it!)

For typical set theories, every setoid, $(S,\approx)$, is isomorphic (in the setoid sense) to another setoid $(S/{\approx},=)$ where ${=}$ is the global equality and $S/{\approx}\equiv\{\{y\mid x\approx y\}\mid x\in S\}$. You should verify that the function $f: (\mathbb{Z},\approx_3)\to(\mathbb{Z}/3\mathbb{Z},=)$ with $\overline f(x) =\{y\approx_3 x\mid y\in\mathbb{Z}\}$ is well-defined; and $g : (\mathbb{Z}/3\mathbb{Z},=)\to(\mathbb{Z},\approx_3)$ with $\overline g(S) = \begin{cases}0,&\text{if }0\in S\\1, &\text{if }1\in S\\2, &\text{if }2\in S\end{cases}$ is well-defined; and, finally, that they are mutual inverses (as functions between setoids, they certainly are not bijections between $\mathbb{Z}$ and $\mathbb{Z}/3\mathbb{Z}$). That is, $\overline f(\overline g(S)) = S$ and $\overline g(\overline f(x))\approx_3 x$. The $\overline a$ in the question would be $\overline f(a)$ here. Indeed, they are asking if $\overline f(a) \stackrel{\cdot}{+} \overline f(b) = \overline f(a+b)$ where $S\stackrel{\cdot}{+}T = \{x+y\mid (x,y)\in S\times T\}$. This is true if and only if $+$ is a well-defined function on $(\mathbb{Z},\approx_3)$.

(I have a blog post that also discusses this.)