# Equivalence relations and equivalence classes

I dont know how to start this proof? Also, our professor did not explain equivalence classes fully so I am not understanding them very well.

• What do you know about equivalence classes? – Asaf Karagila May 27 '14 at 19:27
• An equivalence relation needs to sattisfy reflexitivity, symmetry and transitivity, so you need to check whether those conditions hold for this relation. en.wikipedia.org/wiki/Equivalence_class. – Marc May 27 '14 at 19:28

You need to prove that $\sim$ is reflexive, symmetric, and transitive on $\mathbb Z$.

Then, an equivalence class of $a \in \mathbb Z$ is defined as $$[a] = \{b\mid b \in \mathbb Z \text { and } a\sim b\}$$: That is, $[a]$ is the class containing $a$ and all elements in $\mathbb Z$ that are related to $a$.

Hint: There are two equivalence classes that together, partition $\mathbb Z$.

• But the relation is not reflexive because when you subtract a number from itself you get 0? – user02398409 May 27 '14 at 19:35
• It is reflexive. Note that zero is an even number. – amWhy May 27 '14 at 19:54
• @gatorgurl4 Did you get this question figured out? You might want to think about accepting a helpful answer to each of your questions. You can accept only one answer per question, but you get two reputation points for each accepted answer. Just click on the grey $\checkmark$ to the left of the answer you'd like to accept. – amWhy May 28 '14 at 15:36

In order to prove some relation $\sim$ is an equivalence relation on some set $A$ we need to show that for $a,b,c \in A$ we have the following properties:

• $a \sim a$
• $a \sim b \implies b \sim a$
• $a \sim b, b \sim c \implies a \sim c$

Now I will give hints to to each step for your equivalence relation:

• Does $2$ divide $0$?
• If $x$ is even, is $-x$ even?
• Since we know that $a-b, b-c$ are even, we know that $a-b = 2n, b-c=2k$ for some $k,n$

Now the equivalence class of some element $a$ are defined as:

$[a] = \{ b \mid a \sim b\}$

So think about the different elements of $\mathbb{Z}$, and what their equivlence classes will be. Hint: there are only 2 distinct classes.

Hope this helps

• What I don't understand is how a can NOT be itself? I get completely how a can NOT be b (symmetrical) and if a is NOT b and b is NOT c THEN a is NOT c (transitive), but the reflexive relation baffles me. a is not a statement, it's an element of a set, so a ~ a doesn't make any sense...? – Benjamin R Aug 11 '15 at 9:07
• @BenjaminR I don't quite follow your question. $\sim$ can be defined in many different ways, even non-symmetric ways. For example, consider $\sim$ to be $<$ – DanZimm Aug 12 '15 at 1:39
• Hi Dan, I am new to logical symbols and notation. Whatever Discrete math book or reference I look at uses ~ to mean negation (or literally "not" some statement or value). That's why I find the equivalence relation questions on Math.SE and the reference on Wikipedia to equivalence classes confusing. It seems like ~ is literally used to represent the equivalence relation, am I understanding that right? – Benjamin R Aug 12 '15 at 2:24
• Okay, I couldn't see the MathJax in your comment before (I was using the iOS SE app and it doesn't render it by default). I think you are essentially saying "Consider the relation $a\:\rm R\: \it b$ if $a<b$. Is $\rm R$ an equivalence relation?" – Benjamin R Aug 12 '15 at 2:50
• @BenjaminR correct that's what I was saying in my previous comment - we are simply starting with a relation, and we want to prove that its an equivalence relation – DanZimm Aug 12 '15 at 3:01