2

Okay I am having some difficulties understanding whether a relation is transitive.

For example, we have the set $R=\{1,2,3,4\}$. How can $R_1=\{(3,4)\}$ be transitive when something like $R_2=\{(1,1),(1,2),(2,1)\}$ is not transitive?

I know that a relation $S$ is transitive iff $(a,b),(b,c) \in S$ implies that $(a,c) \in S$.

Stefan Mesken
  • 16,651

1 Answers1

0

$R_1$ is clearly transitive. You seem to think that it isn't: What's your counterexample?

$R_2$, on the other hand, is not transitive. We have $(2,1),(1,2) \in R_2$ but $(2,2) \not \in R_2$.

Stefan Mesken
  • 16,651
  • yes, but does it have to conclude all elements of the 'main' set or is it enough to check that all (a,b) , (b,c) implies (a,c) –  Jan 09 '18 at 21:56
  • The reason why I don't see how R1 is transitive is simply because there's only (a,b) but there's no (b,c).. so there's too few elements to make it transitive in my mind –  Jan 09 '18 at 21:57
  • There are many (b,c)'s. However, they are not in the relation. What the transitivity means: for every a, b, c in the set: if aRb and bRc then aRc. (If a is not in relation with b, or b not in relation with c - nobody cares: a can be or can be not in relation with c.) This kind-of follows from general rules for implication ($p\implies q$ is true if $p$ is false / false implies anything.) –  Jan 09 '18 at 22:00
  • 1
    I see... Transitivity, spelled out more carefully, reads "$\forall a \forall b \forall c \colon (a,b) \in R \wedge (b,c) \in R \implies (a,c) \in R$". Since, for $R_1$ there are no $a,b,c$ with $(a,b),(b,c) \in R$, the premise of this sentence if false. A false premise implies everything, so the statement is true. – Stefan Mesken Jan 09 '18 at 22:01
  • Correct! That is exactly the reason. –  Jan 09 '18 at 22:01
  • Allright I didn't know that I should think that way about R1. Sounds interesting thanks –  Jan 09 '18 at 22:15
  • 1
    @Djhoe It may help to write down the negation of "$R_1$ is transitive". That's equivalent to "$\exists a \exists b \exists c \colon (a,b) \in R_1 \wedge (b,c) \in R_1 \wedge (a,c) \not \in R_1$". It's somewhat more intuitive that this negation is not true (which is why $R_1$ is not not transitive and thus transitive). – Stefan Mesken Jan 09 '18 at 22:19