Discrete maths Equivalence relations and classes How do i do this?
Let the natural number N be our universe. We start by defining the property P(q) :
q is even. We define the relation R on N as follows: ∀n,m (n, m) ∈ R iff P(n + m).
a) Show that R is an equivalence relation.
b) Can you determine how many equivalence classes the relation R has?
 A: For (a)
First, instantiate n and m to be arbitrary in $N$ (which gets rid of the forall quantifier). After that, you go over the definition of an equivalence relation and prove that the conditions hold one by one. Namely:
$(n,n) \in R$. (Reflexivity) (here, we don't even use the m, which is fine as we chose arbitrary n, m) This proof is trivial and I assume you can do that on your own (hint: x + x = 2*x)
$(n,m) \in R \iff (m,n) \in R $ (Symmetry).
Proof for symmetry:
$(\Rightarrow)$ Ass.: $(n,m) \in R$. Hence, $n + m \equiv_2 0$. By commutativity of $+$ operator, we know that $n + m = m + n$, from which directly follows that $m + n \equiv_2 0$
You argue that addition is symmetric, i.e. if $n + m \equiv_2 0$ so is $m + n \equiv_2 0$. Hence, $(m,n) \in R$
$(\Leftarrow)$ Indirect proof. Ass.: $(n,m) \not\in R$. By identical reasoning, it is clear that $(m,n) \not\in R$. By indirect proof, it follows that $(m,n) \in R \Rightarrow (n,m) \in R$
To show transitivity, you need to chose another arbitrary, fixed $p \in N$ and show:
$(n,p) \in R \ \land \ (p,m) \in R \Rightarrow (n,m) \in R$.
You could do a case distinction based on if $p \equiv_2 0$ and $p \not\equiv_2 0$.
