13

I need clarification.

Let $A=\{1,2,3\}$ be a set and $R=\{(1,2)\}$ be a relation on $A$.

Is it a Transitive relation? I am confused because some text books say $R$ is transitive if it contains only one ordered pair.

I am not able to explain why $R$ can said to be transitive in the above case.

A relation is said to be transitive if $(a,b) \in R$ and $(b,c) \in R$ then $(a,c) \in R $.

If P then Q.

$P: (a,b) \in R$ and $(b,c) \in R$ and $Q:(a,c) \in R$

But here only one condition of $P$ is satisfied. According to some source, if second condition i.e, $(b,c) \in R$ does not exist, $R$ is said to be transitive. Can we say $R$ is transitive? Or do we need both conditions of $P$?

amWhy
  • 209,954
SHREE6174
  • 445
  • 2
    The relation is transitive only in the sense that there is no counterexample to the claim. Nobody can find an A, B and a C such that (A, B) is in, and (B, C) is in, but (A, C) isn't. Transitivity does not assert that there must exist an A, B, and a C, only that if there is (A, B) and (B, C) then there must be (A, C). – Kaz May 05 '13 at 03:02

4 Answers4

19

The transitive condition is true vacuously. That's like saying "All the women in the car are on fire" is true, when a man is in the car alone.

vadim123
  • 82,796
  • 2
    I find it's much easier to remember colorful ones. – vadim123 May 04 '13 at 18:03
  • Let us take example, a relation 'perpendicular to' for the set {$l_1, l_2$} is it transitive? – SHREE6174 May 04 '13 at 18:05
  • @Shree: maybe. If $l_1, l_2$ are not perpendicular, than the relation is transitive on these two. If they are perpendicular, then $l_1 \perp l_2$, and $l_2 \perp l_1$, but $l_1 \perp l_1$ is false, so it's not transitive. – vadim123 May 04 '13 at 18:06
  • Ya. Thanks for fire example. I cleared.. Thank you. – SHREE6174 May 04 '13 at 18:12
15

Yes, it is a transitive relation, vacuously so. That is, there are no counter examples in the relation that violate transitivity.

Transitivity requires that

If $(P)$: $(i)$ $(a, b) \in R\;$ AND $(ii)$ $(b, c) \in R$, (conditions)

THEN $(Q)$: it must follow that $(a, c) \in R$ (consequent)

Since $(P)$, the conditions (i) and (ii), will never both be realized/satisfies since the only element in $R$ is $(1, 2)$, we have that the implication $(P) \implies (Q)$ is vacuously true.

NOTE: We can equivalently define transitivity as a property that HOLDS UNLESS there exists a case (counterexample) for which both conditions in $(P)$ are met, but the consequent $(Q)$ is false (does not hold.)

amWhy
  • 209,954
  • Give any real world example for this. I am not clearing.If there is no (1) then how can we say (2)? – SHREE6174 May 04 '13 at 18:03
  • That's the nature of material implication: "If A then B" is false if and only if A is true, and B is false. So if A is false, we have a "vacuously true" implication. – amWhy May 04 '13 at 18:05
  • now clear. But It is difficult to convince with examples. – SHREE6174 May 04 '13 at 18:07
  • I agree, that's why we call the transitivity to hold vacuously. real-life. Examples turn out to seem absurd: This one might make sense: If I promise to pay you 10 dollars if team A wins, but it turns out that team A loses, I can still pay you 10 dollars, and wouldn't be lying. I'd lie if and only if I promised to pay you if team A wins, and team A does indeed win, but I renig on my promise. – amWhy May 04 '13 at 18:11
  • Oh right.. Yes you are right. So Transitivity is vacuous. Thank you..@amWhy – SHREE6174 May 04 '13 at 18:17
  • @amWhy: Nice feedback and discourse, plus nice answer. +1 – Amzoti May 05 '13 at 00:43
  • Hi, I got another doubt. If $R={(1,2), (2,1)}$ is $R$ transitive? – SHREE6174 Oct 23 '14 at 16:57
  • No, because it does not contain $(1, 1)$ – amWhy Oct 23 '14 at 17:10
  • In that case $(a,b)$ and $(b,a)$ are in $R$. Can we consider this as $(a,b)$ and $(b,c)$. That means, Can $a$ and $c$ be same? – SHREE6174 Oct 23 '14 at 17:15
  • 1
    Yes, exactly. If the set were transitive, then $(1, 2), (2, 1) \rightarrow (1, 1)$. Since $(1, 1) \notin R$, the relation is not transitive. – amWhy Oct 23 '14 at 17:19
4

$R$ is transitive in an empty sense, because in a transitive relation, we want the following $ \forall x,y,z\in A, (x,y)\in R \wedge (y,z)\in R \Rightarrow (x,z)\in R $, but this doesn't guarantee the existence of $3$ pairs in $R$. For simplicity, let's write $ \alpha =[(x,y)\in R \wedge (y,z)\in R], \beta =[(x,z)\in R] $. So what we want is that $ \alpha \Rightarrow \beta$, but if $ \alpha $ has a truth value of $0$, then according to the truth table of implication, then $\beta$ will always have a truth value of $1$, which means that a relation $R$ is transitive if $ \alpha$ implies $ \beta $ in $R$.

For example in this case, only $(1,2)$ is in $R$ (meaning $ \alpha $ has a truth value of $0$, because we cannot find $2$ distinct pairs in $R$), and therefore, $ \beta $ has a truth value of $1$, therefore, we found that $ \alpha \Rightarrow \beta$, and therefore, $R$ is transitive.

Jaroslaw Matlak
  • 4,895
AnonymouseCat
  • 1,221
2

Yes, the relation will be transitive, but for vacuous reasons. There are no pairs $(a,b)$ and $(b,c)$ in $R$, so the statement $$\forall (a,b),(c,d)\in R (b=c \Rightarrow (a,d)\in R)$$ does in fact hold.

tghyde
  • 2,055