Is $R$ reflexive?
Is $R$ symmetric?
Is $R$ transitive?
I know $a=b$ is an equivalence relation so it is reflexive, symmetric, and transitive. I know $a-b=2^n$ is reflexive but not symmetric or transitive.
Not symmetric because:
$6-2=2^2$ but $2-6$ cannot be expressed as $2^{\text{natural number}}$.
Not transitive because:
$6-4=2^1$ and $4-3=2^0$ but $6-3$ cannot be expressed as $2^{\text{natural number}}$.
I did the truth tables for $P$ iff $Q$ or $R$ and the statement is true if either $Q$ and $R$ are both true, $Q$ is true and $R$ is false, or $R$ is true and $Q$ is false.
Therefore, I thought it would be enough to show that because $a=b$ is an equivalence relation, $aRb$ iff $a=b$ or $a-b=2^n$ is an equivalence relation too.
However, I got this question wrong on an exam.
Do you have to show that both $a=b$ and $a-b=2^n$ are equivalence relations to show $aRb$ is one?
Best Answer
Hint $\ $ You have $\ a\,R\,b \iff a-b \in \{0\}\cup \{2^n\} =: S.\,$ Suppose more generally that $\,S\subset \Bbb Z\,$ is arbitrary set of integers containing $\,0.\,$ Then checking the equivalence relation properties
reflexive: $\quad\ \ \ a\, R\, a \iff 0\in S,\ $ which is true by hypothesis
symmetric: $\,\ (a\, R\, b\,\Rightarrow\, b\, R\, a)\iff (a\!-\!b\in S\,\Rightarrow\, b\!-a\!\in S)$
transitive: $\ \ \ (a\, R\, b,\ b\,R\,c\,\Rightarrow\, a\, R\, c)\iff (a\!-\!b,b\!-c\in S\,\Rightarrow\,a\!-\!c\in S)$
If so then $\,b=0\,$ in "symmetric" yields $\,a\in S\,\Rightarrow\, -a\in S,\,$ i.e. $\,S\,$ is closed under the operation of negation. Thus $\,a,c\in S\,\Rightarrow\,-c\in S\,$ so substituting $b,c \to 0,-c\,$ in "transitive" yields $\,a+c\in S,\,$ i.e. $\,S\,$ is closed under addition. Conversely, if $\,S\,$ is closed under addition and negation then then it satisfies the listed implications, so $\,R\,$ is an equivalence relation. If you know group theory then you will recognize this as the subgroup test, i.e. $\,R\,$ is an equivalence relation iff $\,S\,$ is a subgroup of the additive group of integers.