# Understanding Equivalence and Relations

Can someone please explain these answers? I have reviewed the slides and read about properties of equality but I still don't understand how to apply it to these sets.

For each the following relations on the set of integers list all that apply (Reflexive, Symmetric, Antisymmetric, Transitive, or none):

$R1 = \{(a, b)\mid a \neq b\}$; Solution: Symmetric

$R2 = \{(a, b)\mid a < b\}$; Solution: Antisymmetric, Transitive

$R3 = \{(a, b) \mid a = b\text{ or }a = b + 1\}$; Solution: Reflexive, Antisymmetric

$R4 = \{(a, b) \mid a = b\}$; Solution: Reflexive, Symmetric, Antisymmetric, Transitive

$R5 = \{(a, b) \mid a = 2b\}$; Solution: Antisymmetric

$R6 = \{(a, b) \mid a < 10 - b\}$; Solution: Symmetric

• There's an awful lot here; what's tripping you up? – Nick Peterson Jun 22 '13 at 3:35
• The question isn't "Which of these are equivalence relations"... the question is "which of these properties does each relation satisfy?" – Nick Peterson Jun 22 '13 at 3:36
• Well, this is for a summer course and the person teaching it is working on a PhD and this is the first class they have taught. They haven't been very well with explaining things and have had to rush over a lot and I don't understand these properties towards a set like (a,b). For instance, I know Symmetric is a relation if (a, b) is in R whenever (b, a) is in R, for some (a, b) is in R but that doesn't help me. – Hermes Trismegistus Jun 22 '13 at 3:37
• Why does that not help you? What is giving you problems when you try to check if one of the given relations satisfy it? – Tobias Kildetoft Jun 22 '13 at 3:39
• I don't understand how to apply them. I know this is probably very basic but I just don't get even the first problem. Is it saying that for (a, b) where (a, b) can be anything, it can be symmetrical? And if that's the case, couldn't it also be asymmetrical for other values of (a, b)? Sorry, I am lost altogether. – Hermes Trismegistus Jun 22 '13 at 3:43

Let's review what each property means. Your question deals with relations on the integers; so, let's say that we are working with a relation $R\subseteq\mathbb{Z}\times\mathbb{Z}$.

## Symmetric:

$R$ is called symmetric if for all $(a,b)\in R$, we also have $(b, a)\in R$.

For instance, $R_1$ is symmetric: if $(a,b)\in R_1$, then $a\neq b$, which implies $b\neq a$ and therefore $(a,b)\in R_1$.

On the other hand, $R_3$ is not symmetric; $(5,4)\in R_3$, but $(4,5)\notin R_3$.

## Antisymmetric:

$R$ is called antisymmetric if whenever $(a,b)\in R$ and $a\neq b$, we have $(b,a)\notin R$.

So, for instance, $R_1$ is not antisymmetric; $(3,5)$ and $(5,3)$ are both elements of $R_1$.

On the other hand, $R_5$ is antisymmetric: if $a=2b$ and $a\neq 0$, then $b\neq 2a$ and so $(b,a)\notin R_5$; if $a=0$ and $a=2b$, then $a=b=0$, so it is fine.

## Transitive:

$R$ is called transitive if whenever $(a,b)\in R$ and $(b,c)\in R$, we also have $(a,c)\in R$.

For instance, $R_1$ is not transitive: $(3,5)\in R_1$ and $(5,3)\in R_1$, but $(3,3)\notin R_1$.

On the other hand, $R_2$ is transitive: if $(a,b),(b,c)\in R$, then $a<b$ and $b<c$; therefore $a<c$, and $(a,c)\in R_2$.

## Reflexive:

$R$ is called reflexive if $(a,a)\in R$ for all $a$.

So, $R_1$ is not reflexive: if $(a,a)\in R_1$, then $a\neq a$... which is clearly not true.

On the other hand, $R_3$ is reflexive; since any $a\in\mathbb{Z}$ satisfies $a=a$ (and, therefore, either $a=a$ or $a=a+1$), we have $(a,a)\in R_3$.

Hope this helps.

• This does, I wish he would have explained it like this. It's a lot easier when integers are plugged into the properties. Sorry for any trouble. – Hermes Trismegistus Jun 22 '13 at 3:52
• "On the other hand, R3 is not symmetric; (5,4)∈R3, but (4,5)∉R3." How is (4,5) not in R3? – Hermes Trismegistus Jun 22 '13 at 4:04
• @HermesTrismegistus: we are working with ordered pairs. So $(4,5)$ is not in R3 because $4 \neq 5$ and $4 \neq 5+1$. The fact that $5=4+1$ is not important – Ross Millikan Jun 22 '13 at 4:13
• @HermesTrismegistus Exactly as Ross says. $R_3$ is the set of all ordered pairs $(a,b)$ such that either $a=b$ or $a=b+1$. Plugging in $a=4$ and $b=5$ does not satisfy either condition, and so $(4,5)\notin R_3$. – Nick Peterson Jun 22 '13 at 4:15
• Thanks guys. I will just have to keep working with this. I really appreciate the time you have spent trying to help me. – Hermes Trismegistus Jun 22 '13 at 4:29

That’s potentially $6\cdot 4=24$ properties to check, so let me just do a sample. I’ll start with $R_1$.

• Reflexive? In order for $R_1$ to be reflexive, it has to be true that if $n$ is any integer, then $\langle n,n\rangle\in R_1$. This means that $n\ne n$. Obviously that’s not true for every integer, since in fact it’s not true for any integer. Thus, $R_1$ is not reflexive.

• Symmetric? In order for $R_1$ to be symmetric, it has to be true that if $m$ and $n$ are integers, and $\langle m,n\rangle\in R_1$, then $\langle n,m\rangle\in R_1$ as well. Suppose that $\langle m,n\rangle\in R_1$; by the definition of $R_1$ this means that $m\ne n$. But of course in that case $n\ne m$, so (again by the definition of $R_1$) $\langle n,m\rangle\in R_1$. Thus, $R_1$ is symmetric. This is just a fancy way of saying that if $m\ne n$, then $n\ne m$.

• Antisymmetric? In order for $R_1$ to be antisymmtric, the following has to be true: if $m$ and $n$ are integers, $\langle m,n\rangle\in R_1$, and $\langle n,m\rangle\in R_1$, then $m=n$. Suppose that we take $m=0$ and $n=1$. $0\ne 1$, so by definition $\langle 0,1\rangle\in R_1$. And $1\ne 0$, so by definition $\langle 1,0\rangle\in R_1$. Can we conclude from this that $0=1$? Obviously not, so $R_1$ is not antisymmetric.

• Transitive? In order for $R_1$ to be transitive, the following has to be true: if $k,m$, and $n$ are integers, $\langle k,m\rangle\in R_1$, and $\langle m,n\rangle\in R_1$, then $\langle k,n\rangle\in R_1$. Take $k=0$, $m=1$, and $n=0$. Then $0\ne 1$, so $\langle k,m\rangle=\langle 0,1\rangle\in R_1$, and $1\ne 0$, so $\langle m,n\rangle=\langle 1,0\rangle\in R_1$, but $\langle k,n\rangle=\langle 0,0\rangle$, and $\langle 0,0\rangle$ is not in $R_1$, because it’s obviously not true that $0\ne 0$.

Now let’s take a look at $R_3$: $\langle m,n\rangle\in R_3$ if and only if $m=n$ or $m=n+1$.

• Reflexive? In order for $R_3$ to be reflexive, it has to be true that if $n$ is any integer, then $\langle n,n\rangle\in R_3$. This means that $n=n$ or $n=n+1$, which is clearly true, so $R_3$ is reflexive.

• Symmetric? In order for $R_3$ to be symmetric, it has to be true that if $m$ and $n$ are integers, and $\langle m,n\rangle\in R_3$, then $\langle n,m\rangle\in R_3$ as well. Suppose that $\langle m,n\rangle\in R_1$; by the definition of $R_1$ this means that $m=n$ or $m=n+1$. If $m=n$, then $n=m$, and $\langle n,m\rangle\in R_3$, but what if $m=n+1$? Then $n=m-1$, so $n\ne m$ and $n\ne m+1$, and therefore $\langle n,m\rangle\notin R_3$. To give a concrete, specific counterexample, take $m=1$ and $n=0$; then $m=n+1$, so $\langle m,n\rangle=\langle 1,0\rangle\in R_3$, but $0\ne 1$ and $0\ne 1+1$, so $\langle 0,1\rangle\notin R_3$. Thus, $R_3$ is not symmetric.

• Antisymmetric? In order for $R_3$ to be antisymmtric, the following has to be true: if $m$ and $n$ are integers, $\langle m,n\rangle\in R_3$, and $\langle n,m\rangle\in R_3$, then $m=n$. Suppose that $\langle m,n\rangle\in R_3$ and $\langle n,m\rangle\in R_3$. The first of these means that $m$ is either $n$ or $n+1$. If $m=n+1$, then obviously $n=m-1$, so $n\ne m$ and $n\ne m+1$, and therefore $\langle n,m\rangle\notin R_3$, contrary to hypothesis. Thus, it must be that $m=n$, and it follows that $R_3$ is antisymmetric.

• Transitive? In order for $R_3$ to be transitive, the following has to be true: if $k,m$, and $n$ are integers, $\langle k,m\rangle\in R_3$, and $\langle m,n\rangle\in R_3$, then $\langle k,n\rangle\in R_3$. Take $k=2$, $m=1$, and $n=0$. Then $k=2=1+1=m+1$, so $\langle k,m\rangle=\langle 2,1\rangle\in R_3$, and $m=1=0+1=n+1$, so $\langle m,n\rangle=\langle 1,0\rangle\in R_3$, but $\langle k,n\rangle=\langle 2,0\rangle\notin R_3$, because $2\ne 0$ and $2\ne 0+1$. This example shows that $R_3$ is not transitive.

The details of checking each of the four properties for each of the other four relations will be different, but this should at least give you a start on how to think about the problem. Note that showing that a relation $R$ does have a property requires giving a general argument covering all possible cases; to show that $R$ does not have a property, on the other hand, you need only find a single counterexample to the property, one lonely instance in which it fails.

Let me just look at a few, to show you what's going on.

Consider $R_1$.

It is symmetric, because whenever $a\ne b$, then $b\ne a$--so whenever $\langle a,b\rangle \in R_1,$ then $\langle b,a\rangle \in R_1$.

In order for $R_1$ to be reflexive, we'd need to know that $\langle a,a\rangle \in R_1$ for all integers $a$, meaning $a\ne a$ for all integers $a$. You should be able to think of some counterexamples for that, I hope.

In order for $R_1$ to be antisymmetric, we'd need to know that whenever $\langle a,b\rangle ,\langle b,a\rangle \in R_1,$ then $a=b,$ meaning that $a\ne b$ and $b\ne a$ together imply that $a=b$.

For $R_1$ to be transitive, we would need to know that whenever $\langle a,b\rangle ,\langle b,c\rangle \in R_1,$ then $\langle a,c\rangle \in R_1,$ meaning that $a\ne b$ and $b\ne c$ together imply $a\ne c$. I leave a counterexample to you.

Consider $R_3$.

It should be clear that $\langle a,a\rangle \in R_3$ for all integers $a$--since $a=a$--so $R_3$ is reflexive.

$R_3$ isn't symmetric, since if $a=b+1$ (which happens sometimes when $a$ and $b$ are integers), then we have neither $b=a$ nor $b=a+1$. Sometimes, then, we can have $\langle a,b\rangle \in R_3$ with $\langle b,a\rangle \notin R_3$. (Can you think of any examples?)

Now, suppose $\langle a,b\rangle ,\langle b,a\rangle \in R_3$. Since $\langle b,a\rangle \in R_3,$ then $b=a$ or $b=a+1,$ so it is impossible for $a=b+1.$ Since $\langle a,b\rangle \in R_3$ and $a\ne b+1,$ it follows that $a=b.$ Thus, $R_3$ is antisymmetric.

Suppose $\langle a,b\rangle ,\langle b,c\rangle \in R_3$. If $a=b$ or $b=c,$ then we can conclude $\langle a,c\rangle \in R_3,$ but what about if $a\ne b$ and $b\ne c$? Well then $a=b+1$ and $b=c+1$, so $a=c+2$, and so $\langle a,c\rangle \notin R_3$. Thus, $R_3$ is not transitive.

Does that help clear things up?

• Kind of, but for R3 doesn't OR mean that it can be either one or the other? That it doesn't have to be both? – Hermes Trismegistus Jun 22 '13 at 4:09
• @Hermes: Indeed, it doesn't have to be both (in fact, it can't be both, in this case), but it may be either one. For example, $\langle 9,8\rangle\in R_3,$ since $9=8+1,$ but also $\langle 9,9\rangle\in R_3,$ since $9=9$. – Cameron Buie Jun 22 '13 at 4:11
• Which part of my $R_3$ discussion is your biggest sticking point? – Cameron Buie Jun 22 '13 at 4:13
• Well, if it only has to satisfy one condition and the ordered pair, wouldn't it be symmetric since (a,b) could be (9,9)? Or does the ordered pair (a,b) have to satisfy all possible values? – Hermes Trismegistus Jun 22 '13 at 4:32
• In order to be symmetric, we have to know that for every $\langle a,b\rangle\in R_3,$ we also have $\langle b,a\rangle\in R_3$. Using the example I gave above, we know that $\langle 9,8\rangle\in R_3.$ However, $\langle 8,9\rangle\notin R_3,$ since neither $8=9$ nor $8=9+1$ is true. – Cameron Buie Jun 22 '13 at 4:37