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
Given $M=\{n\in\Bbb Z: 0\le n\le 30\}$ find the transitive closure of the relation $R\subset M\times M$ defined by $R=\{(n,m): m=3n+1\}\cup\{(8,16)\}$
So, I know that a transitive closure is the least possible subset that $R$ takes to be transitive.
But, what can I do to know the pairs that are missing in this relation. Or better, how can I describe all the pairs to recognize the missing pairs?
Start by writing out $R$ explicitly:
$$R=\{\langle 0,1\rangle,\langle 1,4\rangle,\langle 2,7\rangle,\langle 3,10\rangle,\langle 4,13\rangle,\langle 5,16\rangle,\langle 6,19\rangle,\langle 7,22\rangle,\langle 8,16\rangle,\langle 8,25\rangle,\langle 9,28\rangle\}$$
Now look for the ‘linked’ pairs, like $\langle 0,\color{brown}1\rangle$ and $\langle\color{brown}1,4\rangle$: transitivity says that when you have linked pairs like that in the relation, you must also have corresponding the ‘shortcut’ pair, in this case $\langle 1,4\rangle$. Here the linked pairs are:
$$\begin{align*} &\langle 0,1\rangle\quad\text{and}\quad\langle 1,4\rangle\;,\\ &\langle 1,4\rangle\quad\text{and}\quad\langle 4,13\rangle\;,\text{ and}\\ &\langle 2,7\rangle\quad\text{and}\quad\langle 7,22\rangle\;, \end{align*}$$
so we have to add the shortcut pairs $\langle 0,4\rangle$, $\langle 1,13\rangle$, and $\langle 2,22\rangle$.
Now repeat the process: for example, we now have the linked pairs $\langle 0,4\rangle$ and $\langle 4,13\rangle$, so we need to add $\langle 0,13\rangle$. When you finish a second pass, repeat the process again, if necessary, and keep repeating it until you have no linked pairs without their corresponding shortcut.
First note that the first coordinate $n$ of an element in $R$ must be $0\leq n\leq 9$, this is because if you take $n\geq 10$ you would get $m\geq 31$, but that would not be in $M$ and thus this pair $(n,m)\notin M\times M$.
So now $R=\{(0,1),(1,4),(2,7),(3,10),(4,13),(5,16),(6,19),(7,22),(8,25),(9,28),(8,16)\}$. To have transitivity you must add just $\{(0,4),(0,13),(1,13),(2,22)\}$ and you are done.
