What is transitive closure?

Question

I have the relation: $$T = \{(i,j) \in \mathbb{N}^2 \mid i-10=j\}$$
And I need to find the relation $T^+$ (the transitive closure relation)
which I dont really understand

PS. need help formatting

Answer 1

The transitive closure of a relation $T$ is the smallest relation $T'$ that:

1. Contains everything $T$ contains
2. Is additionally transitive.

$(10,0)\in T$, and $(20,10)\in T$, so we'd expect by transitivity that $(20,0)\in T$, but this isn't true. We'd need to add $(20,0)$ to $T'$ for this to have any hope of being transitive, but this alone won't be enough.

I'd suggest to repeat the above process a few times, and see if there's some pattern to the stuff you need to add. By this, I mean that if you also need to add $(21,1)$ (which you will), does this means that $T'$ just has to be everything of the form $(n+10,n)$ and $(n+20,n)$? Is this enough to make it transitive? Or you will you have to add more?

If you're struggling, a stronger hint is below:

All of $(10,0)$, $(20,0)$, $(30,0)$, etc., must be in $T'$ for it to be transitive. The same is true for $(11,1),(21,1),(31,1)$. Is there some general pattern here?

Furthermore, the solution is below, but I'd recommend you try to figure it out yourself still.

$T' = \{(i,j)\in\mathbb{N}^2\mid \exists k\in\mathbb{N}_{\geq 1}\text{ s.t. }i-10k = j\}$. Essentially, our issue before was we could always find $(10,0),(20,10),(30,20),(40,30)$, etc, and so by transitivity we'd be required to have that $(40,0)\in T'$. The general pattern is that $(n+10k,n)$ must always be in $T'$ for $k\geq 1$.

Answer 2

The transitive closure of T, a binary relation for A, is the
intersection of all transitive relations containing T.

First note that A×A is a transitive relation for A that
contains every relation for A including T.
Thus the intersection is not empty. In addition any
intersection of transitive relations for A is transitive.

Hence the definition is well defined, being the smallest transitive
relation contaning T.

For a point by point description, it is the set of all pairs
(a,b) for which there is a sequence x1,.. x_n (possibility zero
long) with aTx1, x1Tx2,.. x_nTb.

To prove this is the transitive closure, first show it is
transitive and contains T. Next show that every transitive
relation containing T, must contain all of the above described (a,b).