14
$\begingroup$

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.

$\endgroup$
47
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Just curious, how did you come up with this example? $\endgroup$ – Ovi Apr 30 '18 at 6:39
  • $\begingroup$ @Ovi: Nothing deep -- I just looked for the simplest-to-describe nontrivial equivalence relation on a well-known ring I could come up with that isn't a congruence. (And then I restricted it from $\mathbb Z$ to $\mathbb N$ so the simple explanation in terms of digits would agree with a simple symbolic definition too). $\endgroup$ – Henning Makholm Apr 30 '18 at 10:47
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In your example, you added classes by adding representative members. Perhaps a union of the classes would be more like addition. Intersect with the complement of a class would be like subtracting that class. $\endgroup$ – richard1941 May 1 '18 at 23:08
  • $\begingroup$ But a union of classes is not a class again. $\endgroup$ – Randall May 1 '18 at 23:25
  • $\begingroup$ Curious as to why the downvotes. $\endgroup$ – Randall May 1 '18 at 23:26
  • $\begingroup$ Downvote was not intentional. You would have to use the "advanced" touchpad on my computer to appreciate this. They added so many wonderful "features" and "gestures" that my cursor is all over the place and is effectively out of control. At this point the stackworks software will not let me change anything. Meanwhile, I have already taken my ancient copy of Hewitt & Stromberg 450 miles north to new home in Nevada. I remember that class well: the instructor had dementia and we had to teach ourselves. At least we didn't have cursor malware in 1970. $\endgroup$ – richard1941 May 3 '18 at 15:51
7
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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:

  • Existence of such a function
  • Uniqueness of it

However, such a function cannot exist as Henning Makholm's answer demonstrates.

Going deeper and uncovering the 'hidden' problems

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.

Well-definedness in other areas

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.