7
$\begingroup$

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.

  • 0
    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.2012-04-03

5 Answers 5

5

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.

  • 0
    Ah, I was misunderstanding your point. Yes, you're correct.2012-04-05
3

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.

  • 0
    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.2012-04-05
2

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

  • 0
    (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.)2012-04-04
2

Isomorphisms for finite dimensional vector spaces.

  • 0
    This won't work with my target audience, though.2012-04-04
1

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.

  • 0
    @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.2012-04-04