Is R transitive if R = {(a,a), (b,a), (b,b), (b,c), (c,a), (c,b), (c,c)}

Question

I know the rule is ((a R b) ∧ (b R c)) → a R c but since (a,b) is not in R in the first place can R still be transitive?

Answer 1

Your rule uses the letters $a, b, c$ and your relation uses the letters $a, b, c$. This is an unfortunate coincidence.

The rule is meant for any triple of elements in your set, in any order (including the possibilitu that two or three of them are equal). Not just the elements named $a, b, c$ in that specific order. So for instance, since $$ (b\,R\,c)\land (c\,R\,a) $$ we have to check that $b\,R\,a$. And since $$ (b\,R\,c)\land (c\,R\,b) $$ we also have to check that $b\, R\, b$. And so on.

In this case, $R$ is finite and relatively small, so it's viable to just take every single triple that fulfills the first part (hypothesis) of the transitivity rule (of the 27 possible triples, there are 13 that fulfill the hypothesis), and check that the pair that transitivity requires $R$ to contain in each case is indeed contained in $R$.

For larger sets and larger relations, the relation is often not given as a concrete list of pairs, but rather "all pairs of elements in the set which fullfill property $X$", and in that gase, it's usually a good idea to write more general arguments than just an exhaustive list.

Answer 2

You can draw yourself a (directed multi)graph of your relation with vertices representing each element in your set and directed edges going from one vertex to another if that pair is in the relation (in that order).

Here is a drawing of the graph of your relation.

Now, a rephrasing of what it means to be transitive:

If you can travel along the directed edges along a path in the direction of the edges from one vertex to another in any amount of time using any number of edges in the path, if the relation is actually transitive that implies that you should also have a way to travel directly from the starting point to the ending point.

Note: This more general rephrasing of the transitivity property highlights a few key aspects which are often lost on new students. Primarily, the starting point and ending point may be the same thing! There is no requirement that in the original definition of transitivity that $a,b,c$ must all be distinct. The relation $\{(a,b),(b,a)\}$ is not transitive since it is missing $(a,a)$ as well as $(b,b)$.

Next, it highlights the point that we don't only care about paths of length $2$, but we also care about paths of any length. If $\mathcal{R}$ is a transitive relation, that requires that for any collection of elements $a,b_1,b_2,b_3,\dots,b_n,c$ (not necessarily distinct), if we have $a\mathcal{R}b_1,b_1\mathcal{R}b_2,b_2\mathcal{R}b_3,\dots,b_{n-1}\mathcal{R}b_n,$ and $b_n\mathcal{R}c$ then we must also have $a\mathcal{R}c$. This becomes particularly important to note when talking about the transitive closure of a relation. It is a common mistake to only go through and add the missing "shortcuts" for length two paths but don't go and check to see if after having done so this causes more shortcuts for newly created length two paths needing to be added.

Another common mistake when talking about transitivity is again in being confused about what happens if there are missing or not enough elements or pairs to have a path that you need a shortcut for. The empty relation is transitive! So is the relation $\{(a,b)\}$! Any path (if one exists in the first place) of any length (even of length $1$) must have a shortcut of length $1$ that you can take. Just because there are no paths needing a shortcut that doesn't prevent a relation from being considered transitive. The only thing that would cause a relation to not be transitive is if you can describe a path that should have a shortcut but doesn't have one.

---

We see by looking at your picture that indeed, you can travel from anywhere to anywhere else directly, noting that $a$ is what we might call a "sink", once you reach $a$ you can't leave.