0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
0

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.