Transitive closure applied to a relation

106 Views Asked by At

I have a hard time understanding the transitive closure applies to a relation example the relation
$$\alpha =\{⟨x,y⟩∈ \Bbb N^2\mid x=y+10\}.$$

What is the transitive closure of this relation? Wouldn't it be $\alpha+ = \alpha$ so it would stay the same? Because if we graph the relation we only have an element relied to an other once so we can't have $R^2 \cup R^3\dots$ Since the segment are only of length $1$ we only have $R^1$ which would be $R+$ right ?

In other words, if the properties irreflexivity, anti-symmetry and symmetry held for the relation $\alpha$, even if we had the transitive closure to this relation, $\alpha +$ would still be : irreflexive, anti-symmetric and symmetric, right?

Thank you!

1

There are 1 best solutions below

1
On

If the transitive closure of $\alpha$ was equal to $\alpha$ itself, that would mean that $\alpha$ itself was transitive, which is not the case. To see why, assume that $(x,y)\in\alpha$, and that $(y,z)\in\alpha$. Then $x=y+10$ and $y=z+10$. By substituting the last expression into the first, we get $x=z+20$, so certainly $x\neq z+10$, and thus $(x,z)\not\in\alpha$.

This might tip you off that the transitive closure of $\alpha$ is the set $$\alpha+ = \{(x,y)\in\mathbb{N}^2\ |\ x=y+10n, n\in\mathbb{N}, n\geq 1\}.$$

The reasoning behind this is that $\alpha^2 = \{(x,y)\in\mathbb{N}\ |\ x=y+20n\}$, that $\alpha^3 = \{(x,y)\in\mathbb{N}\ |\ x=y+30n\}$, and so on, so

$$R\cup R^2\cup R^3\cup\cdots = \{(x,y)\in\mathbb{N}^2\ |\ x=y+10n, n\in\mathbb{N}, n\geq 1\}.$$