# How to prove equivalence relations

I'm going through Pinter's "A Book of Abstract Algebra" and I'm currently on the topic of Partitions and Equivalence Relations. I'm having a little trouble understanding the way he (and apparently many other authors) word their questions. For instance, he asks:

Prove that each of the following is an equivalence relation on the indicated set. Then describe the partition associated with the equivalence relation.

On $\mathbb{Z}$, show that $a\cong b$ iff $|a|$ = $|b|$.

Which is simple enough, but I'm confused by the 'iff' part. I know how I'm supposed to prove something like this, but I'm often not confident because I thought that I'm supposed to be proving two conditional statements:

If $a\cong b$, then $|a|$ = $|b|$, and If $|a|$ = $|b|$, then $a\cong b$.

I know how to prove the second conditional and apparently that's the only one I'm supposed to prove, but then what's the point of the 'iff'? Is there something I'm not understanding?

• You've provided too little context about what the book is asking. There is no general definition of what $a\cong b$ means for $a,b\in\Bbb Z$, unlike $|a|$ which means the absolute value of $a$. The"iff" you are stating could be the definition of $a\cong b$, in which case of course there would be nothing to prove. Many other definitions of equivalence relations '$\cong$' can be imagined, but in most cases they would make that "iff" invalid. One definition for which it would be valid is if $a\cong b$ were defined by $a^2=b^2$. But how are we to know the true definition? – Marc van Leeuwen Jan 22 '16 at 6:02
• sorry, will edit to clarify. – hijasonno Jan 22 '16 at 6:14
• is that any better? – hijasonno Jan 22 '16 at 6:26
• The "iff" is apparently being used to define the meaning of $\cong$. The author is saying that $a \cong b$ means that $|a| = |b|$. – David Jan 22 '16 at 7:43
• Yupp, I see that now. Thanks so much! – hijasonno Jan 22 '16 at 9:06

In my copy of Pinter, he actually asks:

Prove that each of the following is an equivalence relation on the indicated set. Then describe the partition associated with that equivalence relation.

1. On $\mathbb{Z}$, $m\cong n$ iff $|m| = |n|$

Pinter is defining what $m\cong n$ means and asking you to show that $\cong$ is an equivalence relation.

The generic proof for an equivalence relation looks like:

• Reflexivity: Let $a\in \text{[whatever set]}$. Then [chain of logic based on definition of $\cong$], therefore $a \cong a$.
• Symmetry: Assume $a \cong b$, i.e. [spell out what this means]. Then [chain of logic], i.e. $b \cong a$.
• Transitivity: Assume $a \cong b$ and $b \cong c$, i.e. [spell out what this means]. Then [chain of logic], i.e. $a \cong c$.

E.g. the proof for your example would look like:

• Reflexivity: Let $a\in\mathbb{Z}$. Then [stuff you write], therefore $a \cong a$.
• Symmetry: Assume $a \cong b$, i.e. $|a| = |b|$. Then [stuff you write], i.e. $b \cong a$.
• Transitivity: Assume $a \cong b$ and $b \cong c$, i.e. $|a| = |b|$ and $|b| = |c|$. Then [stuff you write], i.e. $a \cong c$.

As a very strong hint, the last step before you write "therefore $x \cong y$" will be "$|x| = |y|$, therefore $x \cong y$".

Try doing it yourself first. Spoiler: This question contains an answer, though I think it's awkwardly worded.

• Yeah I edited my question, so we are reading the same thing. I see now! So the whole point of the 'iff' is for the first conditional to act as our definition for the equivalence, and so the second conditional is what we actually have to prove using reflexivity, symmetry, and transitivity. – hijasonno Jan 22 '16 at 9:05
• @hijasonno: I think of it as a translation process: we take the assumptions in congruence language (e.g. $a\cong b$ and $b \cong c$), translate them into statements in the language of the other domain (e.g. statements about natural numbers), come to some conclusion in the other domain (e.g. $|a|=|c|$), then translate that conclusion back into the congruence language ($a \cong c$). – Frentos Jan 22 '16 at 10:33