3
$\begingroup$

I have a set $A = \{1, 2, 3\}$.

Relation $S = \{(1, 1), (1, 2), (3, 1) \}$

Relation $T = \{(1, 1), (3, 2), (3, 1) \}$

$S$ is not transitive, but $T$ is transitive. Why is that?

A relation $R$ transitive if $(a,b),(b,c)\in R\Rightarrow (a,c)\in R$.

In $S$, we have $(1, 1), (1, 2)$, and we also have $(1, 2)$. And we have $(3, 1), (1, 1)$, and also $(3, 1)$.

In $T$, we have $(3, 1), (1, 1)$, and we also have $(3, 1)$.

It seems like we have the same kind of situations in both $S$ and $T$, except $S$ has another $a, b, c$ triplet. What makes T transitive but S not?

  • 0
    Oops, don't know why I didn't see $(3,1)$ and $(1,2)$, guess I was thinking too hard.2012-12-06

3 Answers 3

4

$S$ is not transitive as @Conan noted. $T$ is transitive,because you can easily check that for $(1,1)$ the only pair which satisfy the definition is $(3,1)$: $$(1,1),(3,1)\in T\Rightarrow (3,1)\in T$$ For other pairs the antecedent of the definition is always wrong so the whole definition is satisfied for $T$.

3

deezy, in S, we have (3,1) and (1,2), but we do not have (3,2)

0

I like to graph relations to see their properties. If $R$ is a relation on a set $A$, draw a vertex for each $a \in A$. If $a \mathrel{R} b$, draw a directed edge from $a$ to $b$. The relations $S$ and $T$ above are graphed like this (I used webgraphviz):

Graph of relation S enter image description here

A relation is transitive if the graph doesn't have any length-two walks that can't be shortened to length-one walks with the same start and end. For instance, $S$ has the walk $3 \to 1 \to 1$, and that can be shortened to $3 \to 1$. Same for $T$, as a matter of fact. But $3\to 1\to 1$ is the only length-two walk in $T$, whereas in $S$ we also have $3 \to 1 \to 2$. Since there is no edge from $3$ to $1$, $S$ is not transitive.