Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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)\}$$
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.
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.
