Understanding Equivalence and Relations

Question

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

Answer 1

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.

Answer 2

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?

Answer 3

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.