I have trouble understanding this concept. Why is it necessary to prove that addition or multiplication is well defined in equivalence classes? My understanding of equivalence classes is that it must be reflexive, symmetric and transitive. Doesn't proving it automatically imply that addition and multiplication can be done? Why the additional need to prove that it is 'well defined'?
Apologies if this question is too trivial; my understanding of this topic is limited.
On
Just because a relation is an equivalence, this doesn't mean it has to be "nice" with respect to any operation you'd like to put on its classes. To see this, look at a non-example of something being well-defined.
Let $V=\mathbb{R}^2$ be the plane with its usual vector space structure. Put a relation on $V$ by defining $u \sim v$ if $u = cv$ for some non-zero scalar $c$. This is an equivalence relation on $V$. The zero vector is in a class by itself, and the other classes are the vectors that form parallel lines through the origin (with the zero vector removed).
Since classes are naturally represented by vectors, you could attempt to define a natural addition on $V/\sim$ by $$ [u] + [v] = [u+v]. $$ But this fails to be well-defined, even though the relation in play is an equivalence.
The problem is that two different people could add the SAME TWO classes but get different answers. That's no good. For example, Alice wants to add the class corresponding to the $x$-axis (with zero removed) to itself. This class is $[(1,0)]$, for example. So, Alice does $$[(1,0)] + [(1,0)] = [(2,0)] = [(1,0)].$$
Bob will do the exact same class addition, but recognize that $[(1,0)]$ is also equal to $[(-1,0)]$. Then Bob gets $$[(1,0)] + [(-1,0)] = [(0,0)] \neq [(1,0)].$$
Alice and Bob have added the exact same class to itself, but got conflicting answers.
On
Suppose we have partitioned the set of all integers into $\mathbb Z_{10}$, the set of all equivalence classes modulo $10$. Let $[n] = \{x \in \mathbb Z : x \equiv n \pmod{10} \}$ be the equivalence classes.
Now let's define $[a] \vee [b] = [\operatorname{lcm}(a, b)]$ for all $[a], [b] \in \mathbb Z_{10}$
Then \begin{array}{c} [2] &\vee &[6] &= &[6] \\ [12] &\vee &[16] &= &[48] \\ \end{array}
But $[2]=[12], \ [6]=[16]$ and $[6] \ne [48]$. It follows that $\vee$ is not well defined on $\mathbb Z_{10}$.
On
Elaborating on Henning Makholm's answer:
Consider this equivalence relation on $\mathbb N$: $$a \sim b \quad\text{iff}\quad \lfloor a/10 \rfloor = \lfloor b/10 \rfloor $$ which says that two naturals are related if they differ only in their last digit.
[Define $+$ (1)]: $$[a]_\sim + [b]_\sim = [a+b]_\sim$$
The problem lies in the attempted definition (1) of the function $$ +: \mathbb{N}/_\sim \times \mathbb{N}/_\sim \to \mathbb{N}/_\sim. $$
Definition (1) is meant to be a shortcut (as a programmer you could call it syntactic sugar) for the following indirection defintion:
(2) $+$ is the unique function, so that for every $a, b \in \mathbb{N}$ the following holds: $[a]_\sim + [b]_\sim = [a+b]_\sim$.
For this definition to be well-defined you need to prove two things:
However, such a function cannot exist as Henning Makholm's answer demonstrates.
You would see the problem more easily if you tried to define $+$ in a direct way:
(3) Let $x, y \in \mathbb{N}/_\sim$. ... Then set $\mathbb{N}/_\sim \ni z = \cdots$ We set $x + y = z$.
How would you construct the "…" part to match the attempted definition above? You could say:
(4) Let $x, y \in \mathbb{N}/_\sim$. Let $a \in x, b \in y$. Then set $\mathbb{N}/_\sim \ni z = [a + b]_\sim.$.
Here you can see that the definition of $z$ might depend on the choice of $a$ and $b$. Even if that was not true, you would need to prove that $x, y \neq \emptyset$.
Even in the attempted definition (4) the problem is well-hidden, you could say. Let us remove the boilerplate and remind us what a function really is:
If $X, Y$ are sets, then the relation $f \subseteq X \times Y$ is called a function $f: X \to Y$ $:\Leftrightarrow$
- $f$ is a left-total relation: $\forall x \in X\ \exists y \in Y. (x, y) \in f$
- $f$ is a right-unique relation: $\forall (x, y) \in f\ \exists_1 z \in B. (x, z) \in f$
With $+$ being intended to be a function $+: \mathbb{N}/_\sim \times \mathbb{N}/_\sim \to \mathbb{N}/_\sim$ in mind, we can now attempt definition
(5) $+$ is the function $\{\left((a, b), c\right) \in (\mathbb{N}/_\sim \times \mathbb{N}/_\sim) \times \mathbb{N}/_\sim\, |\, [c]_\sim = [a + b]_\sim \}$.
It still needs to be proved that the given set is indeed a function. Which property of it will be violated?
Spoiler:
The set is not right-unique as Henning Makholm's answer demonstrates.
In summary, sometimes, operating only on the high-level thinking can easily lead to unforeseen and skipped-over problems.
This problem is not restricted to equivalence classes, it always appears if one uses such an indirect definition. For example,
let the exponential function $\mathrm{exp}: \mathbb{R} \to \mathbb{R}$ be the unique function so that $\forall x, y \in \mathbb{R}. f(x + y) = f(x)f(y)$.
Is $\mathrm{exp}$ well-defined?
Spoiler:
No, uniqueness is violated. This equation is satisfied by all exponential functions. For instance, apart from the obvious $x \mapsto e^x$ solution, $x \mapsto 3^x$ also satisfies the equation: $3^{x+y} = 3^x 3^y$.
Indeed, one needs some more properties, so that uniqueness is guaranteed:
The exponential function $\mathrm{exp}: \mathbb{R} \to \mathbb{R}$ is the unique Lebesgue-measurable function with $f(1) = e$, so that $\forall x, y \in \mathbb{R}. f(x + y) = f(x)f(y)$.
Source: https://en.wikipedia.org/wiki/Characterizations_of_the_exponential_function
Original source: Hewitt and Stromberg, Real and Abstract Analysis (Springer, 1965), exercise 18.46
Consider this equivalence relation on $\mathbb N$: $$a \sim b \quad\text{iff}\quad \lfloor a/10 \rfloor = \lfloor b/10 \rfloor $$ which says that two naturals are related if they differ only in their last digit.
This is a perfectly good equivalence relation, but we can't extend addition to equivalence classes by the same rule that works for modular arithmetic:
$$ [a]_\sim + [b]_\sim = [a+b]_\sim $$
The problem is that the sum of two equivalence classes now depend on which representatives we use to define their sum. For example, the rule seems to imply that $$ [11]_\sim + [32]_\sim = [43]_\sim \\ [17]_\sim + [35]_\sim = [52]_\sim $$ However $[11]_\sim$ is the same equivalence class as $[17]_\sim$, and $[32]_\sim = [35]_\sim$, but $[43]_\sim$ is not the same as $[52]_\sim$. So the definition doesn't really tell us which of the equivalence classes should be the result of $$ \{10,11,\ldots,19\} + \{30,31,\ldots,39\} $$
Checking that addition on the equivalence classes "is well-defined" means convincing oneself that this situation does not occur for the equivalence relation you're looking at.