1
$\begingroup$

Problem

How can I show transitive closure of these relations on $\{1,2,3,4\}$?

  1. $\{(1,2), (2,1), (2,3), (3,4), (4,1)\}$

  2. $\{(2,1), (2,3), (3,1), (3,4), (4,1), (4,3)\}$

  3. $\{(1,2), (1,3), (1,4), (2,3), (2,4), (3,4)\}$

  4. $\{(1,1),(1,4), (2,1), (2,3), (3,1), (3,2), (3,4), (4,2)\}$

Attempt

None. I don't understand what "show transitive closure" means.

$\endgroup$
6
  • $\begingroup$ Do you understand what the transitive closure of a relation is? $\endgroup$ Jul 31, 2013 at 8:42
  • $\begingroup$ Is it the definition of a transitive relation? $(x,y) \wedge (y,z) \Rightarrow (x,z)$? $\endgroup$
    – user87509
    Jul 31, 2013 at 8:44
  • $\begingroup$ A good way to do this on small sets is to draw the relation as a graph where the nodes are the elements and there is an arrow from $x$ to $y$ if $x$ is related to $y$. Then finding the transitive closure is a matter of drawing in those arrows you can get by following successive arrows. $\endgroup$ Jul 31, 2013 at 8:44
  • $\begingroup$ No, it’s another relation related to the original one. The basic idea is that it’s formed by adding ordered pairs to the original relation until you get a transitive relation. There’s a little more to it than that, though: you have to add the minimum possible set of pairs that will do this. I’ll write up an answer that does the first one as an example. $\endgroup$ Jul 31, 2013 at 8:45
  • 1
    $\begingroup$ I see that $Set_1$ is not transitive, as $\exists (1,2) \wedge \exists (2,3)$ but $\not\exists(3,2)$. $\endgroup$
    – user87509
    Jul 31, 2013 at 8:46

1 Answer 1

1
$\begingroup$

Let $R=\{\langle 1,2\rangle,\langle 2,1\rangle,\langle 2,3\rangle,\langle 3,4\rangle,\langle 4,1\rangle\}$ on $\{1,2,3,4\}$. What failure of transitivity do we have here?

$$\begin{align*} &\langle 1,2\rangle,\langle 2,1\rangle\in R,\text{ but }\langle 1,1\rangle\notin R\\ &\langle 1,2\rangle,\langle 2,3\rangle\in R,\text{ but }\langle 1,3\rangle\notin R\\ &\langle 2,1\rangle,\langle 1,2\rangle\in R,\text{ but }\langle 2,2\rangle\notin R\\ &\langle 2,3\rangle,\langle 3,4\rangle\in R,\text{ but }\langle 2,4\rangle\notin R\\ &\langle 3,4\rangle,\langle 4,1\rangle\in R,\text{ but }\langle 3,1\rangle\notin R\\ &\langle 4,1\rangle,\langle 1,2\rangle\in R,\text{ but }\langle 4,2\rangle\notin R\\ \end{align*}$$

This means that in order to expand $R$ to a transitive relation, we must add at least the six ordered pairs $\langle 1,1\rangle,\langle 1,3\rangle,\langle 2,2\rangle,\langle 2,4\rangle,\langle 3,1\rangle$, and $\langle 4,2\rangle$. This gives us the relation

$$R\,'=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 1,3\rangle,\langle 2,1\rangle,\langle 2,2\rangle,\langle 2,3\rangle,\langle 2,4\rangle,\langle 3,1\rangle,\langle 3,4\rangle,\langle 4,1\rangle,\langle 4,2\rangle\}\;.$$

Are there any failures of transitivity here?

$$\begin{align*} &\langle 1,2\rangle,\langle 2,4\rangle\in R\,',\text{ but }\langle 1,4\rangle\notin R\,'\\ &\langle 1,3\rangle,\langle 3,4\rangle\in R\,',\text{ but }\langle 1,4\rangle\notin R\,'\\ &\langle 3,1\rangle,\langle 1,3\rangle\in R\,',\text{ but }\langle 3,3\rangle\notin R\,'\\ &\langle 3,1\rangle,\langle 1,2\rangle\in R\,',\text{ but }\langle 3,2\rangle\notin R\,'\\ &\langle 3,4\rangle,\langle 4,2\rangle\in R\,',\text{ but }\langle 3,2\rangle\notin R\,' \end{align*}$$

Thus, $R\,'$ isn’t yet transitive: we need to add at least the pairs $\langle 1,4\rangle,\langle 3,2\rangle$, and $\langle 3,3\rangle$ to $R\,'$ to have any hope of having a transitive relation. This gives us the relation

$$R''=\{\langle 1,1\rangle,\langle 1,2\rangle,\langle 1,3\rangle,\langle 1,4\rangle,\langle 2,1\rangle,\langle 2,2\rangle,\langle 2,3\rangle,\langle 2,4\rangle,\langle 3,1\rangle,\langle 3,2\rangle,\langle 3,3\rangle,\langle 3,4\rangle,\langle 4,1\rangle,\langle 4,2\rangle\}\;.$$

Note that in $R''$ the elements $1,2$, and $3$ of $A$ are all related to everything in $A$; only $4$ is not. And that gives us some failures of transitivity in $R''$:

$$\begin{align*} &\langle 4,1\rangle,\langle 1,3\rangle\in R'',\text{ but }\langle 4,2\rangle\notin R''\\ &\langle 4,1\rangle,\langle 1,4\rangle\in R'',\text{ but }\langle 4,4\rangle\notin R'' \end{align*}$$

There are some other failures, but in each case the missing pair is either $\langle 4,3\rangle$ or $\langle 4,4\rangle$. Thus, to make $R''$ transitive we must at least add these two pairs. Call the resulting relation $\overline{R}$. We can’t add any more pairs, because $\overline{R}=A\times A$: it already contains every possible ordered pair. And finally we do have a transitive relation.

Because at each stage I added only those ordered pairs that that I had actually shown to be necessary for transitivity, this $\overline{R}$ is the smallest transitive relation containing the original relation $R$; by definition it is the transitive closure of $R$. The problem asks you to find and write out the transitive closures of the other three relations as well.

There are much more efficient ways to find the transitive closure of a relation, but at this point it’s probably most instructive for you to do everything by hand, so to speak, as I did above.

$\endgroup$
8
  • $\begingroup$ I haven't started reading your answer yet, but, Mr. Scott, thank you very much for all the detailed teaching and help you provide on this site. You are amazing! $\endgroup$
    – user87509
    Jul 31, 2013 at 9:10
  • $\begingroup$ @positiveimpact: You’re very welcome. And thank you. $\endgroup$ Jul 31, 2013 at 9:18
  • $\begingroup$ Follow-up hint: In this case, we have $\langle 1,2\rangle,\langle 2,3\rangle,\langle 3,4\rangle,\langle 4,1\rangle\in R$, this already immplies $\overline{R}=A\times A$. (why?) $\endgroup$
    – Tomas
    Jul 31, 2013 at 10:29
  • $\begingroup$ Regarding this set: $\{(2,1),(2,3),(3,1),(3,4),(4,1),(4,3)\}$ -- There are no paths that originate from 1. I think I obtained transitive closure at R^2 by adding the pairs $(2,4),(3,3),(4,4)$. Is my thought correct? Can I obtain transitive closure if there are paths from a to b, but no paths from b, in this case from every element in set $A$ to 1, yet no paths from 1 to another element in $A$? $\endgroup$
    – user87509
    Jul 31, 2013 at 11:25
  • $\begingroup$ @Tomas I'm not sure why! How does that imply $R^*$ is $A$ x $A$? And what do you mean by $A$ x $A$? Does this mean 4x4 =16, i.e., there are four nodes in set $A$, so there are 16 possible combinations of nodes? $\endgroup$
    – user87509
    Jul 31, 2013 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy