enter image description here

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.

  • $\begingroup$ What do you know about equivalence classes? $\endgroup$ – Asaf Karagila May 27 '14 at 19:27
  • $\begingroup$ 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. $\endgroup$ – 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$.

  • $\begingroup$ But the relation is not reflexive because when you subtract a number from itself you get 0? $\endgroup$ – user02398409 May 27 '14 at 19:35
  • $\begingroup$ It is reflexive. Note that zero is an even number. $\endgroup$ – amWhy May 27 '14 at 19:54
  • 1
    $\begingroup$ @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. $\endgroup$ – 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

  • $\begingroup$ 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...? $\endgroup$ – Benjamin R Aug 11 '15 at 9:07
  • 1
    $\begingroup$ @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 $<$ $\endgroup$ – DanZimm Aug 12 '15 at 1:39
  • $\begingroup$ 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? $\endgroup$ – Benjamin R Aug 12 '15 at 2:24
  • $\begingroup$ 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?" $\endgroup$ – Benjamin R Aug 12 '15 at 2:50
  • 1
    $\begingroup$ @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 $\endgroup$ – DanZimm Aug 12 '15 at 3:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.