Methods for proving an equivalence relation

390 Views Asked by At

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

2

There are 2 best solutions below

2
On BEST ANSWER

Hint

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

0
On

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.