# Methods for proving an equivalence relation

I'll be taking introductory abstract algebra in the fall, and so to prepare, I'm working through Pinter's text. Chapter 12 includes a number of exercises asking the student to prove that something is an equivalence relation and to describe the associated partition. For example: In $\mathbb{Q}$, $r \sim s$ iff $r - s \in \mathbb{Z}$.

I think I'm okay with most (?) of this. I'd show this is an equivalence relation like so: If $x, y, z \in \mathbb{Q}$, then $x - x = 0 \in \mathbb{Z}$, and so $x \sim x$. Second, if $x \sim y$, then $y - x = -(x - y) \in \mathbb{Z}$, and so $x \sim y \implies y \sim x$. Finally, if $x \sim y$ and $y \sim z$, then $x - z = (x - y) - (z - y) \in \mathbb{Z}$, and so $x \sim z$.

The two parts I'm not sure about: First, that last f on the iff. Essentially, this means I have to prove that if $r \sim s$, then their difference is an integer, right? But I thought this is merely how this particular equivalence relation is defined. How do I know that $r \sim s$ until I look at their difference?

Second, I have a basic idea of what the partition is, but I'm not sure how to form the statement. The equivalence class $[q] = \{k + q : k \in \mathbb{Z}, q \in \mathbb{Q} \}$. But if anything, that seems as though it would be the definition for a single equivalence class, not the description of the partition. (Now that I look at it again, it also leaves out the fact that $k$ is arbitrary but $q$ is fixed.)

If anyone can offer any hints, I'd very much appreciate it. (Though I'm guessing the second of my questions might be more amenable to a No-this-is-how-you-do-it than to a hint, per se.)

-
The text defines $r$ to be equivalent to $s$ iff (if and only if) the difference is an integer. There is nothing for you to prove, the difference being an integer is the defining condition for the equivalence relation. – André Nicolas Aug 7 '13 at 4:32
@AndréNicolas So are you saying the question is poorly written? I guess I was originally reading it like "r R s <--> r - s in Z," where R is not necessarily an equivalence relation. But ~ usually does mean equivalence relation, right? – dmk Aug 9 '13 at 14:53
The question is not poorly written, it is quite clear. But to show this is an equivalence relation, all you need to do is to verify that the conditions for an equivalence relation are satisfied. You don't have to prove that if $r\equiv s$ then $r-s$ is an integer, you have been told that is what $\equiv$ means for this exercise, – André Nicolas Aug 9 '13 at 14:59
@AndréNicolas So what you were saying then is that there's nothing for me to prove beyond what I'd already proved? – dmk Aug 9 '13 at 15:40
Yes, you had completely finished proving that the relation is an equivalence realtion. And it is a clean well-organized proof. – André Nicolas Aug 9 '13 at 16:40

Hint

Prove that the associated partition is $$\{[q]\, |\, q\in[0,1)\}$$

-
My first thought was, OK, that's true, but is it necessary to be so restrictive? For example, in Z_4, [1] = [5] = [61] = ... Well, sure, but we only need [1]. Two days later, though, it clicked: "Succinct" is a better adjective than "restrictive." (And to complete the analogy for myself, the partition of Z_4 would be {[k] : k = 0, 1, 2, 3}.) (Not sure how to do the @ thing here...) – dmk Aug 9 '13 at 15:16
If we want to give a set usually we write its elements without repetition. – user63181 Aug 9 '13 at 15:28

For your first part: Definitions are iff, or if and only if statements, as they are essentially stating that two things are equivalent -- the new term, and its definition. It shouldn't be affecting what you need to prove, except that you can use both that $r \sim s \implies r - s \in \mathbb{Z}$ and that $r - s \in \mathbb{Z} \implies r \sim s$.

For the second part, a better way of putting it would be as follows:

For each $q \in \mathbb{Q}$, the equivalence class of $q$ under $\sim$ is as follows: $[q] = \{q + k : k \in \mathbb{Z}\}$.

By saying this, you describe all of the equivalence classes making up the partition in one statement, and also take care of having $q$ fixed and $k$ varying.

-

This post is to answer the question above:

How do I know that r∼s until I look at their difference?

Answer: Use an indexing number m, with m = r - g(r), with g(r) being the next lower integer from r. Then each class can be represented as Am (I don't know how to subscript). m will be some rational number between zero (inclusive) and 1 (non-inclusive).

-