1

According to my book:

R = {(1,2), (2,3), (1,3), (2,1)} is not transitive because (1,1) and (2,2) are missing. I don't see why (1,1) & (2,2) would be relevant here since aRb and bRc => aRc has been fulfilled.

According to my book #2:

R = {(1,1), (2,2), (3,3)}

Is both symmetric and transitive. How is it transitive?

user3734083
  • 31

4 Answers4

1

The first relation is not transitive as you have 1R2 and 2R1 (and 2R1 and 1R2). If it were transitive you would have 1R1 (and 2R2). But you do not.

For the second relation. It is transitive, since the only relations are 1R1 and 2R2 and 3R3. So, the only couples xRy and yRZ are

  • 1R1 and 1R1, which needs 1R1 to complete the transitivity condition.
  • 2R2 and 2R2, which needs 2R2 to complete the transitivity condition.
  • 3R3 and 3R3, which needs 3R3 to complete the transitivity condition.

The key point is that a,b,c do not need to be (all) distinct.

quid
  • 42,135
1

First question: $1R2$ and $2R1$. Transivity would imply that $1R1$. Notice that $a$ and $c$ in the definition of transitivity don't have to be different.

Second question: $1R1$ and $1R1$, transivity implies that $1R1$. Ok. Same for $2$ and $3$. No counterexamples, so $R$ is transitive.

ajotatxe
  • 65,084
1

You are saying that $aRb\wedge bRc\Rightarrow aRc$ has been fullfilled. That is not true:

Here we have $1R2\wedge2R1$ but not $1R1$.

On your second question:

Can you find $a,b,c$ such that $aRb\wedge bRc$ and not $aRc$? No, you can't. Direct conclusion: $R$ is transitive.

drhab
  • 151,093
0

In the first relation, we have $(1, 2) \in R $ and $(2, 1)\in R$, hence, if the relation were transitive, we would need $(1, 1) \in R$.

In the second relation, it is trivially transitive, because transitivity fails only if there exist $a, b, c$ such that $(a, b) \in R$ and $(b, c) \in R$, and $(a, c) \notin R$. There is no such failure in relation $2$.

amWhy
  • 209,954
  • The definition of transitivity uses $aRb$ and $bRc$ to imply $aRc$, doesn't it mean $a,b,c$ should be distinct? – Vigneshwaren Nov 12 '14 at 15:10
  • @Vigneshwaren no it does not. As said explictly in both of the other two answers. – quid Nov 12 '14 at 15:12
  • The definition of transitivity requires that IF $a R b$ and $bRc$, then we require $a R c$. But if $(a, b) \notin R$ and $(b, c)\notin R$. It doesn't matter what the status of $a$ in relation to $c$. – amWhy Nov 12 '14 at 15:13