Composition of relation and transitive closure?

Question

I am to find the composition of R unto R itself.

$$R=\{(1,2),(2,3),(3,4),(4,5),(5,1)\}$$

This is what I have:

a) Find the composition $R^2$

The composition of R unto R is:

$$R^2=\{(1,3),(2,4),(3,5),(4,1),(1,5)\}$$

b) Find the transitive closure

Transitive closure

$$R=\{(1,2),(2,3),(1,3)(3,4),(4,5),(3,5),(5,1),(4,1)\}$$

Answer 1

There are a couple of things you should check:

If $R\subset X\times Y$ and $S \subset Y\times Z$ are two binary relations, their composition $S\circ R$ is defined as follows: $$S\circ R = \{(x,z) \in X\times Z \big| \exists y\in Y: (x,y) \in R \text{ and } (y,z)\in S\}$$

Applying the definition, what you have for $R\circ R$ is correct, save for the last element $(1,5)$. It should be: $$(1,2)\circ(5,1) = (5,2)$$

For the second part, note that a relation $R\subset X\times X$ is transitive if for all $x,y,z\in X$:

$xRy, yRz \Rightarrow xRz$.

The transitive closure is the smallest relation $R'\subset X\times Y$ that contains $R$ and is transitive. One can check if you have constructed $R'$ by checking if $R'$ is itself transitive.

Answer 2

Both are unfortunately incorrect.

For the composition of $R$ on itself, $R^2$, this is the set of all pairs $(a,c)$ such that there exists a $b$ such that $(a,b)$ and $(b,c)$ are both elements of $R$.

You correctly found $(1,3)$ to be an element of $R^2$ since $(1,2)$ and $(2,3)$ are both elements of $R$. Similarly, you found $(2,4)$ since $(2,3)$ and $(3,4)$ are both elements of $R$.

In fact, we see that $R$ has a very nice pattern... every element is related to the element one larger than it up until you reach $5$ where it wraps back around to $1$. We see then that $R^2$ is in fact the relation where every element is related to the element two larger than it, so $(1,3),(2,4),(3,5),(4,1)$ and the final element in the relation is $(5,2)$.

The relation $R$ is actually a rather important example. It happens to be not only a relation, but a function. Furthermore, it happens to be a permutation and a very special kind of permutation called a "rotation." You can visualize it by taking a regular pentagon with vertices labeled $1,2,3,4,5$ in that order clockwise and rotating the figure.

You have in this special case of the relation actually being a function that the composition of the relation is precisely the composition of the function.

---

Now... on to the transitive closure. This you also got incorrect. Let's look at why. The transitive closure needs to be transitive. Yours is not.

You will commonly see transitivity of a relation written as follows: "A relation $R$ is called transitive if for every choice of $a,b,c$ (not necessarily unique) you have that if $(a,b)$ and $(b,c)$ are both elements of $R$ then $(a,c)$ must also be an element of $R$."

You might have thought then "Oh, well then, since I have $(1,2)$ and $(2,3)$ in $R$ that means I also need $(1,3)$ in $R$ and left it at that. Notice however, you have $(1,3)$ and you have $(3,4)$ in your attempt which means that you should also have $(1,4)$ but you forgot to include it. You in essence only computed $R\cup R^2$.

Instead, a better way to phrase transitivity in my opinion is the following: "A relation is called transitive if for every sequence of elements $a, b_1,b_2,b_3,\dots,b_k,c$ (not necessarily distinct) if $(a,b_1),(b_1,b_2),(b_2,b_3),\dots,(b_{k-1},b_k),(b_k,c)$ are all elements of $R$, then so too is $(a,c)$"

Using a bit more natural language, if you can get from point $a$ to point $c$ along any (directed) path, regardless how long or short, then there must also be a direct path from $a$ to $c$.

The transitive closure is the relation which adds all such missing pairs $(a,c)$. To build intuition, it could also be thought of in these smaller countable examples as $R\cup R^2\cup R^3\cup \cdots$, though there is no reason to actually compute each of $R,R^2,\dots$ to arrive at a final answer.

In your example, it is clear to see that $1$ can reach any of the other elements, including itself. ($1$ can reach $2$ directly using $(1,2)$, it can reach $3$ by taking two steps $(1,2)(2,3)$, it can reach $4$ with three steps $(1,2)(2,3)(3,4)$, etc...) Similarly, every element can reach every other element.

Your transitive closure in this case then happens to be $\{1,2,3,4,5\}^2$, the equivalence relation where everything is related to everything.