# trivial but non-trivial equivalence relations

Define a binary relation $R$ on a set $A$ by saying $xRy$ iff $x$ and $y$ have the same whatever.

"Whatever" is of course some specified function on $A$.

This is a "trivial" equivalence relation: you specify it in effect by specifying the partition of the set $A$.

Define another binary relation $S$ on $A=\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}$ by saying $xSy$ iff $x-y$ is a multiple of $3$.

Undergraduates who haven't thought about this do not instantly say "Oh, I see: $xSy$ iff $x$ and $y$ leave the same remainder on division by $3$." Instead they go through proving reflexiveness, symmetry, and transitivity from the definition. In proving transitivity they ask whether $x-y$ is a multiple of $3$ and $y-z$ is a multiple of $3$ implies $x-z$ is a multiple of $3$, and they may have to think about it before they come up with $x-z=(x-y)+(y-z)$. After all, what would possess anyone to subtract $y$ only to instantly add it back in again?

So this is a "nontrivial" equivalence relation in that one doesn't instantly specify the partition of $A$, and proving the three properties requires some algebra rather than just knowing the definition of the three properties or knowing which partition is used. In fact, after they've proved the three properties it's not obvious until they think further just what the partition is. But on the other hand, it's trivial in that they can do the algebra without having abstruse ideas in algebra appear to be what the problem is all about.

What other examples of this sort are there, suitable as exercises in a class where the idea of equivalence relations is first introduced?

In other words, examples are sought in which

• Reflexiveness, symmetry, and transitivity will not be obvious in virtue of the relation having been defined by saying what the set-partition is;
• Proving those three properties takes more work that merely chasing the definitions of those three properties;
• But proving them isn't so hard that that becomes the hard part of the problem;
• After they've proved them, they still have to do some further thought to figure out what the partition is.

Later edit: I'd like things that are usable in a course I'm teaching, whose only prerequisite is first-semester calculus, which is not actually used. I can't use concepts that would take substantial time to develop.

-
How about the obvious generalisation of your example to cosets of groups? –  Alex B. Apr 3 '12 at 15:48
Fix $f:A\to A$ and let $x\sim y$ iff there exist $m$ and $n$ such that $f^m(x)=f^n(y)$? –  Henning Makholm Apr 3 '12 at 15:54
Clarifying question: Do you require that a partition (i.e., a nice set of canonical labels for the equivalence classes) can be found by your students after some nontrivial amount of thought, or can you also use examples where the nicest description of the partition is "the partition induced by such-and-such equivalence relation"? For the latter, you should be able to speak about, say, germs on $\mathbb R^1$, or integer sequences with bounded differences. Or commensurability of nonzero reals. –  Henning Makholm Apr 3 '12 at 16:59
I'd like to have examples where they could be asked to identify the partition and it would mean something. But if you know of some that otherwise fit, maybe we should see them. –  Michael Hardy Apr 3 '12 at 17:06

I think the best example may be one of the simplest, namely fractions. Probably few if any of your students have encountered the rigorous pair-based construction of rational numbers. Here the equivalence classes may be viewed as (the slope of) discrete lines in $\mathbb Z^2$ passing through $(0,0)$. But this probably will not be immediate to most students at this level. Moroever, it serves as an excellent exercise because it forces students to make rigorous one of the most hardwired intuitive examples of an equivalence relation. It is the pons asinorum of the theory of equivalence relations.

-
This is the best one so far . . . . . . . . –  Michael Hardy Apr 4 '12 at 19:33
$(a,b)\sim(c,d)$ iff $ad=bc$. This is on the class of pairs of integers in which not both are $0$. If both are $0$, then the relation is not transitive. I think I'll use this one and express it in that way. This allows the "rational number $\infty$", i.e. pairs in which the first component is not $0$ and the second is. –  Michael Hardy Apr 4 '12 at 21:18
@Michael $\:(a,b)\sim (0,0)\:$ by $\:0\cdot d = 0\cdot c.\:$ So there is only one equivalence class if you allow $(0,0).\:$ It's better to use $(x,y)$ for $y/x$ (vs. $x/y$) to preserve the correspondence with slopes of lines. –  Bill Dubuque Apr 4 '12 at 21:31
Everything is related to $(0,0)$ if you allow $(0,0)$, but the relation is not transitive if you do that, so it would then make no sense to speak of "equivalence classes". –  Michael Hardy Apr 4 '12 at 22:41
@Michael If you allow $(0,0)$ then $(a,b)\sim (0,0)\sim (c,d)$ so every pair is in the relation. Thus the relation is an equivalence relation, though a trivial one. –  Bill Dubuque Apr 4 '12 at 23:12

Isomorphisms for finite dimensional vector spaces.

-
This won't work with my target audience, though. –  Michael Hardy Apr 4 '12 at 19:29

One quite nontrivial example, at least for undergraduates, is to show that the relation of homotopy of continuous maps is an equivalence relation. The nontrivial fact here is that transitivity relies on the glueing lemma. Maybe you do not need to formulate the exercise in full generality (i.e. if the undergrads get scared by abstract things). For example just considering continuous maps between euclidean spaces might suffice.

I am very unsure however if this example meets all the criteria of your desired exercise..

-
I'd write either "nontrivial" as one word or "non-trivial" with a hyphen. "Non-" is a prefix. –  Michael Hardy Apr 4 '12 at 17:33
I up-voted this one. But of course it won't work with my current target audience. –  Michael Hardy Apr 4 '12 at 19:33
Thanks for the corrections, always happy to learn something new :) When I have time I shall try to think of an example better suited for your targeted audience. –  user22705 Apr 4 '12 at 20:34
(I've notice "non" standing alone like this in various places on the internet and I have started to suspect that that usage is commonplace among young people.) –  Michael Hardy Apr 4 '12 at 21:21

How about taking $A$ to be some set of functions from $\mathbb{R}$ to $\mathbb{R}$ and defining the equivalence relation $fRg$ to mean $\lim_{x\to\infty} \frac{f(x)}{g(x)} = 1$ (and in particular the limit exists)? If $A$ is the set of polynomials then you can show that this relation is "trivial" in your sense, but perhaps not "trivially trivial". If $A$ is larger then it is not so trivial.

-
To make it a little more interesting, have $fRg$ iff $\lim_{x\to\infty}\frac{f(x)}{g(x)}$ is finite and non-zero, where $A$ is the set of polynomials. –  Brian M. Scott Apr 5 '12 at 19:48
Projective $n$-space, as the set of points $[a_0\colon\cdots\colon a_n]$ with $[a_0\colon\cdots\colon a_n] = [b_0\colon\cdots\colon b_n]$ if and only if there exists $\lambda\neq 0$ with $a_i=\lambda b_i$ for $i=1,\ldots,n$.
They corresponds to lines through the origin in affine $n$-space.
In thinking about Bill Dubuque's answer, I decided to all the "rational number $\infty$" because I want to write the pairs as pairs rather than as fractions. I want to avoid telling the students that they are fractions because then they might miss the non-triviality of the proof of transitivity. –  Michael Hardy Apr 4 '12 at 21:23
@Michael: Then you can present it as $\mathbb{P}^1_{\mathbb{Z}}$; there are then two ways of finding the "same" in the equivalence relation: they represent the same fraction (or $\infty$), or they lie in the same line through the origin. –  Arturo Magidin Apr 4 '12 at 21:25