2

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?

Juniven Acapulco
  • 9,654
Sally
  • 21

2 Answers2

2

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.

Bill Dubuque
  • 272,048
0

You cannot "split" this into two relations, you have to treat it as a whole. Put it in brackets if it helps: $$a\,R\,b\quad\hbox{if and only if}\quad (a=b\ \hbox{or}\ a-b=2^n\ \hbox{for some $n\in\Bbb N$})\ .$$ Now if $a=b$ then the RHS is true (because the first part is true), so $a\,R\,b$. That is, $a\,R\,a$ for all $a$, and $R$ is reflexive.

For symmetry you might think through the problem like this: suppose $a\,R\,b$. Does it necessarily follow that $b\,R\,a$? Well, since $a\,R\,b$, one possibility is that $a=b$: then certainly $b=a$ and so $b\,R\,a$. But what if $a\ne b$? Then $a-b$ is a power of $2$: does this mean that either $b=a$ or $b-a$ is a power of $2$? Obviously not for the first, and not for the second either because $b-a$ will be negative. This should suggest the example that $3\,R\,1$ but $1\,\not R\,3$. Then all you need to say for the answer is:

$R$ is not symmetric because, for example, $3\,R\,1$ but $1\,\not R\,3$.

In the same way you can show that $R$ is not transitive. Try it for yourself.

David
  • 82,662
  • I don't understand why knowing that a=b is reflexive is enough to show that R is reflexive when a-b=2^n is not reflexive. – Sally May 08 '14 at 01:05
  • 1
    But this is exactly what I said in the first line of my answer - you cannot treat this as two separate relations. You have to ask, if $a=b$, is the statement in brackets in my answer always true? – David May 08 '14 at 01:17