How to motivate equivalence classes

Equivalence classs are very useful in mathematics, but many of the applications require further background, like quotient spaces in topology or quotient groups in algebra. One good example is residue classes (I.e. $\mathbb{Z}/n\mathbb{Z}$).

What is another good example of an equivalence class that I could use to motivate the definition?

-
I use $\Bbb{R}/2\pi\Bbb{Z}$. Not as a quotient group or a quotient space, but simply as the set of directions in 2D-space. This is something that students have alreade seen in high school trigonometry. That $+n\cdot 2\pi$ at the end of a solution of a trig equation is an equivalence class. – Jyrki Lahtonen Apr 9 '14 at 4:26
@JyrkiLahtonen First thing I thought of as well, very good easy/accessible example, (I'd have put it in an answer). – Aaron Golden Apr 9 '14 at 8:31
In my opinion, motivating equivalences is very different from motivating equivalence classes (and in particular the construction of a quotient set as a set of equivalence classes). Which is your actual aim? – Hurkyl Apr 9 '14 at 9:40

I think that the following story is quite illuminating for introduction. Naturally, one can/should adapt/change it to better fit the audience, I just wanted to sketch the general idea.

Suppose you came here by bus. Which bus was that? You say it was the 42, which is the line that goes from the main station to the university. However, was it really the 42? Is there only a single bus carrying this number?

No, there are multiple buses marked 42, but you don't care which one you rode, because they all take the same route. You abstracted the differences between particular cars, because they were equivalent for your purposes. You have just used the concept of equivalence classes.

After that, I try to explain the intuition using graphs (informally), like here.

I hope this helps $\ddot\smile$

-
I like the idea of using a non-mathematical example to get across the idea of abstraction and equivalence. – Adam Bjorndahl Apr 9 '14 at 15:34
But did I really use the concept of equivalence classes? Equating a property of buses with the collection of all buses that have that property is a nontrivial step, and one that philosophers debated about long before mathematicians started using equivalence classes as a set-theoretic trick for representing things. – Hurkyl Apr 9 '14 at 17:13
@Hurkyl It depends, if you said "line 42" or "route 42" then no, the number does not refer to the bus itself. However, if you used expression like "the number 42 bus" or "bus-42" or any similar which refers to the bus by the number, then yes. It's a common pattern, e.g. "it's a Lamborghini" versus "its make is Lamborghini". Of course, you can argue about the semantics of natural language, but that would be just nitpicking. – dtldarek Apr 9 '14 at 21:18
@AdamBjorndahl Thanks. – dtldarek Apr 10 '14 at 12:04

I would think a good first example is the rational numbers. (Note the "quotient" terminology here, too.)

In particular, the rationals can be written as the set of integer pairs $(a,b)$ with $b\neq0$, modulo the following equivalence relation: $(a,b) \equiv (c,d)$ iff $ad = bc$.

Note that the rule described here is commonly referred to as "cross-multiplication."

There are plenty of other examples you can give to assess whether or not students have understood the definition. (Would "is a brother of" be an equivalence relation? Why or why not? Would "has the same first name as" be an equivalence relation? Why or why not? Is equality e.g. of integers an equivalence? Why or why not?) For each "yes," you could follow by discussing partitions w.r.t. an equivalence relation.

The last crucial early example from mathematics that comes to mind is the definition of the real numbers as equivalence classes formed by looking at (Cauchy) convergent sequences of rational numbers.

-
You can also look at real numbers as equivalence classes of Dedekind cuts also can't you? – ruler501 Apr 9 '14 at 5:05
two real numbers are equivalent if and only if they have the same Dedekind cut in the rationals. – ruler501 Apr 10 '14 at 20:11
You can take cuts of the rationals to find irrationals and construct the reals that way. I can look and find an article on that if you want. – ruler501 Apr 10 '14 at 20:32

I like this question very much. But I think the best approach is via a plethora of examples meant to demonstrate the variety of uses of equivalence classes. I doubt there is a singular example that can open every student's mind to the concept of equivalence classes. That said, here are some examples I have used effectively:

1) I have taught a "transition to proofs" course for a few years, and have included the following sequence of exercises. During the first few weeks or so, after working with sets and their notation, I assign this exercise:

What's $\mathbb{Z}$ Point Of This Problem?: In this problem, we are going to ''prove'' the existence of the negative integers! I say ''prove'' because we won't really understand what we've done until later but, trust me, it's what we're doing.

Because of this goal, you cannot assume any integers strictly less than 0 exist, so your algebraic steps, especially in part (d), should not involve any terms that might be negative.

That is, if you consider an equation like $x+y=x+z$, we can deduce that $y=z$, by subtracting $x$ from both sides, since $x-x=0$.

However, if we consider an equation like $x+y=z+w$, we cannot deduce that $x-z=w-y$. Perhaps $y>w$, so $w-y$ does not exist in our context... On to the problem!

Let $P=\mathbb{N}\times\mathbb{N}$. Define the set $R$ by $$R = \{((a,b),(c,d))\in P\times P\mid a+d=b+c\}$$

1. Find three different pairs $(c,d)$ such that $((1,4),(c,d))\in R$.
2. Let $(a,b)\in P$. Prove that $((a,b),(a,b))\in R$.
3. Let $((a,b),(c,d))\in R$. Prove that $((c,d),(a,b))\in R$, as well.
4. Assume $((a,b),(c,d))\in R$ and $((c,d),(e,f))\in R$. Prove that $((a,b),(e,f))\in R$, as well.

I pose this mainly as a "can you understand new notation and write a proof about it" problem, and say as much to the students.

But a few weeks later on, when we're talking about equivalence relations, I bring up this exercise again. I even write a passage in our book about this:

Remember that crazy exercise from Chapter 3 that had you prove something about a set of pairs of pairs of natural numbers, and we claimed that was proving something about the existence of the integers? What was that all about? Look back at the exercise now, Exercise [reference]. You'll see that the last three parts of the problem have you prove that the set $R$ we defined is an equivalence relation on the set $P=\mathbb{N}\times\mathbb{N}$. Look at that! You proved $R$ is reflexive, symmetric, and transitive.

What that exercise showed is that (essentially, we are glossing over some details here) any negative integer is represented as the equivalence class of pairs of integers whose difference is that negative integer. That is, $$-1\;\; \text{''}=\text{''}\;\; [(1,2)]_R = \{(1,2),(2,3),(3,4),\dots\}$$ and, for another example, $$-3\;\;\text{''}=\text{''}\;\; [(1,4)]_R=\{(1,4),(2,5),(3,6),\dots\}$$ This is only an intuitive explanation and not rigorous, mathematically speaking, but that's the idea!

For the students who might already be inclined to think abstractly and want to pursue higher math, this is a great teaser, and has led to many discussions in office hours about set theory, logic, and so on. For other students, it's a reminder that exercises from the past weren't done in a vacuum; they have a meaning, and can teach us new things. And for every student, it's at least a reminder that math is interconnected in ways we might not expect, a priori.

2) An in-class example I like to discuss involves comparing an equivalence relation to a similar (non-equivalence) relation that is meant to "encode the same information". I include the following example in the text, and follow up on it with an in-class discussion, which also serves to point out the distinction between "a relation from $A$ to $B$" and a "relation on $A$":

Let $S$ be the set of students in our class. Define a relation $R_1$ between $S$ and $\mathbb{N}$ by saying $(s,n)\in R_1$ if person $s\in S$ is $n$ years old.

Now, define a relation $R_2$ on $S$ itself by saying $(s,t)\in R_2$ if persons $s$ and $t$ are the same age (in years).

How do the relations $R_1$ and $R_2$ compare? Do they somehow ''encode'' the same information about the elements of the set $S$? Why or why not?

3) You mention $\mathbb{Z}/n\mathbb{Z}$, naturally. I think it behooves us to show why this is useful, not just that it's an equivalence relation. In the past, I have demonstrated exemplary uses via the Chinese Remainder Theorem, Fermat's Little Theorem, etc. But I've found that the most striking (and convincing) uses are ''smaller'', computationally, and serve to show how previously tedious arguments can be cleaned up.

For instance, a standard induction problem asks a student to show $\forall n\in\mathbb{N}$ that $6\mid n^3+5n$. A standard induction argument requires some algebraic manoeuvering, and ends up being entirely unenlightening for the beginning student (for whom this is meant to be practice relating to the inductive nature of such relationships). Instead, I go back and use mod 6 and say, ''There are 6 cases. Either $n$ is congruent to 0,1,2,3,4,5 modulo 6. In each case, we see...'' And there they have it.

Likewise, consider proving that any perfect square is either a multiple of 4 or one more than a multiple of 4. This can be good practice working with formal definitions (''multiple of 4 means there exists $k\in\mathbb{Z}$ such that...'') but it's far more ''fun'' for them to just see that $0^2\equiv 2^2\equiv 0$ and $1^2\equiv 3^2\equiv 1$.

Finally, divisibility tricks are fun, too. I find that college students are well aware of the ''casting out 3s/9s'' trick, but are wholly unaware of how it works. Setting up a mod 10 congruence to prove it really shows some "aha"s and smiles.

In summary, I don't think it's necessary to show a typical undergraduate the sophisticated concept of ''modding out'' a set by an equivalence relation. In a classroom setting, it usually suffices to whet their appetite by showing students the utility of equivalence relations in various settings. (In the examples above, this means (1) formally defining $\mathbb{Z}$ from $\mathbb{N}$, (ii) comparing an equivalence relation and a ''regular'' relation, and (iii) using equivalence classes to clean up a formerly ''messy'' argument.) If particular students are intrigued by this, then you might foster further discussions, either in class or in office hours (depending on the popularity/prevalence).

-

(I'm giving this as another answer, since it is completely unrelated to my other one.)

A very simple example of a natural equivalence relation is (for two straight lines on a plane) to be parallel. The equivalence classes may be thought of as directions on the plane. This may have an added benefit of showing beginners that in mathematics, properties (i.e., "having such and such direction") are basically sets (well, they may be classes, but there's no need to talk about formality of ZFC and paradoxes here).

-

As an alternative to non-mathematical or very complex examples:

I like to go back to the very basics: terms. Is $1+2$ the same as $2+1$? As an expression, it's not. The first one begins with a $1$, but not the second one. For a child, it has to be learnt that these terms are the same, although they look different.

Mathematically, it's annoying to define equivalence here. However, psychologically the big advantage is that your students know which terms (of natural numbers, say) are equivalent. So, this example helps to get the feeling that "being equivalent" means "being the same although not looking so".

-

What about a non-mathematical motivation, namely, the idea of classification? A simple example I use with my students: define an equivalence class on the set of all animals (yes, this is going to be imprecise and a bit fuzzy, but we're talking about intuition here, not formal maths!) defined by $x\equiv y$ iff $x$ and $y$ have the same number of legs. This way, we get a classification of animals with respect to the number of legs: the equivalence classes are the sets of animals with no legs, with one leg etc.

Of course, this may be not the way we usually use equivalence classes in mathematics (but it does happen, of course), but it shows that the idea of an equivalence relation and classes is a natural one for the human mind.

-
I think, one should take at least one non-mathematical example into account. I also like the examples of student's solution only changing variable names. – Markus Klein Apr 9 '14 at 7:10

To give another inner-mathematical example from another subdiscipline, which I always liked:

$$f≡g :\Leftrightarrow \int \left | f(x)-g(x) \right | \,\mathrm{d}x = 0,$$

where the integral is defined such that it ignores what happens to the integrand on sets with measure zero, e.g., the Lebesgue integral or the Henstock–Kurzweil integral.

The corresponding equivalence classes are, e.g., essential for defining convergence almost everywhere and convergence by measure, which need to be defined for these equivalence classes (and not for individual functions) if they shall have a unique limit.

A drawback of this example is that it may not be easily accessible to your students, depending on their prerequisites.

-

Consider giving the student something of a meta-motivation. (In addition to what has been proposed here about using examples from outside of mathematics, like the bus one. That is really what will turn the light on in their heads.)

Explain that in mathematics, there are many times when we want to talk about things being "equal-ish". They aren't actually the same thing, but, functionally, for our particular purposes at that time, they "do the same thing" or "look the same".

Now, since this is math, we have to wave our hands very precisely, so here's how we're going to define it (give definition).

Now show how "Bus is numbered 42" fits by going through all the parts of the definition.

Three examples from mathematics is a great motivation to you, but likely not meaningful to your students. The equivalence relation is a new concept; have them learn the new concept by seeing how it applies to something they are familiar with so that they are only dealing with one new thing and one familiar thing.

-

The example I always use is the equivalence relation, on a set of humans, "born in the same year".

-
This is the example I use in my classes to "motivate equivalence classes". In what sense is this not an answer to the question? – Martin Argerami Apr 10 '14 at 7:56
Sorry. I deleted the comment. I wanted to flag the question because I thought your question is a bit too short, but clicked the wrong button. This is of course an answer. – András Bátkai Apr 10 '14 at 8:21
Why is this a good choice? How are the reactions to this example? – Roland Apr 10 '14 at 8:53
I think it is a good choice because one can express the classes in a very explicit way: those born in 1990, in 1991, etc. Reactions are mixed, because most of our students arrive to college with this view that learning math is "give me the recipe to do the assignment". Understanding and reasoning is not something they associate with math. – Martin Argerami Apr 10 '14 at 14:26

You might attempt to motivate them using partitions. Present them with the attitude that the three properties (reflexivity, symmetry, and transitivity) are simply a convenient way to check that something is indeed a partition. Partitions are easy to visualize, so even if a student doesn't know any concrete applications yet, it should be plausible to them that such a thing could be useful.

Every other answer just gives examples of equivalence relations. This answer is more about the general point of view from which you look at them.

-

These lectures in real analysis motivate equivalence classes by constructing the rational numbers as a set of equivalence classes, which is a good motivation as it requires little more than some basic set theory and high-school level mathematics. I have also seen equivalence classes introduced more formally in Harvard's abstract algebra class.

-
Seconded. These Harvey Mudd lectures are really great. – brendansullivan07 Apr 9 '14 at 4:57

I am not sure if this is a valid answer to this question:

I would probably say that equivalence relation is a fancy name for a partition of sets and equivalence class is a fancy name for a cell of this partition. (A partition of a set $X$ is an expression for $X$ as a disjoint union of non-empty subsets of $X$.)

Indeed, one has the following "theorem":

Theorem. There is a one-to-one correspondence between equivalence relations on a set $X$ and partitions of the set $X$.

Proof. Note first that if $\sim$ is an equivalence relation on $X$, then, $\sim$-classes (non-empty by definition) partition $X$. Conversely, if $X = \sqcup_{\lambda \in \Lambda} X_\lambda$ is a partition of $X$, define a relation $\sim$ on $X$ by $x \sim y$ if $x, y \in X_\lambda$ for some $\lambda$. Note then that $\sim$ is an equivalence relation and $\sim$-classes are precisely the $X_\lambda$'s.

Then, this becomes a matter of language as it should.

-