# Equality of sets, transitive closure of a relation.

We can prove that the intersection of a set of transitive relations in a set $$A$$ is also a transitive relation in the set $$A$$. With this, given $$S \subset A \times A$$ we can find the lowest transitive relation that contains $$S$$ that we call $$\overline {S}$$ transitive closure. With this construction of the transitive closure I am trying to prove:

$$\overline{S} = \{ (x,y) \in A \times A : \exists n\in \mathbb{N} \text{ and }a_0=x,a_1,...,a_n=y \text{ such that } (a_i,a_{i+1}) \in S \text{ for } 0\leq i

It's easy to show that

$$\{ (x,y) \in A \times A : \exists n\in \mathbb{N} \text{ and }a_0=x,a_1,...,a_n=y \text{ such that } (a_i,a_{i+1}) \in S \text{ for } 0\leq i

I can not show that

$$\overline{S} \subset \{ (x,y) \in A \times A : \exists n\in \mathbb{N} \text{ and }a_0=x,a_1...,a_n=y \text{ such that } (a_i,a_{i+1}) \in S \text{ for } 0\leq i

• There's something wrong here because $x$ and $y$ don't ever seem to be used in your characterization of $\overline S$. – Robert Shore Apr 9 '19 at 17:23
• Sorry, I edited the question. – Lucas Apr 9 '19 at 17:30

Let me use some notation for your relation: $$S_\infty = \{ (x,y) \in A \times A : \exists n\in \mathbb{N} \text{ and }x = a_0,a_1,...,a_n=y \text{ such that } \\ (a_i,a_{i+1}) \in S \text{ for } 0\leq i

Define a sequence by induction $$S = S_1 \subset S_2 \subset S_3 \subset\cdots$$ where, for $$N \ge 2$$, we have $$S_N = \{ (x,y) \in A \times A : \exists n\in \{1,...,N\} \text{ and }x = a_0,a_1,...,a_n= y \text{ such that } \\ (a_i,a_{i+1}) \in S_{N-1} \text{ for } 0\leq i Let's consider the set $$\cup_{N \in \mathbb N} S_N$$. This set is a transitive relation, because for any three elements $$x,y,z \in A$$ such that $$(x,y), (y,z) \in \cup_{N \in \mathbb N} S_N$$, there is a single value of $$N$$ for which $$(x,y)$$, $$(y,z) \in S_N$$, and it follows that $$(x,z) \in S_{N+1}$$. Since $$\overline S$$ is the intersection of all transitive relations containing $$S$$, we may therefore conclude that $$\overline S \subset \bigcup_{N \in \mathbb N} S_N$$ Next we show that $$\bigcup_{N \in \mathbb N} S_N \subset S_\infty$$ To see why, consider any $$(x,y) \in \cup_{N \in \mathbb N} S_N$$. We can find $$N$$ such that $$(x,y) \in S_N$$. We can then apply the definition of $$S_N$$ to interpolate between $$x$$ and $$y$$ using relations in $$S_{N-1}$$, i.e. we can find a chain $$x = a_0,....,a_n = y$$ so that $$(a_i,a_{i+1}) \in S_{N-1}$$, $$i=0,...,n-1$$. We thus have a finite chain from $$x$$ to $$y$$ using relations in $$S_{N-1}$$. And next, we can apply the definition of $$S_{N-1}$$ to interpolate between each pair $$a_i,a_{i+1}$$ using relations in $$S_{N-1}$$, getting a longer but still finite chain from $$x$$ to $$y$$ using relations in $$S_{N-2}$$. Continuing by downward induction, we eventually obtain a chain of relations in $$S_1 = S$$ from $$x$$ to $$y$$, proving that $$(x,y) \in \overline S$$.

Putting the last two together we get $$\overline S \subset S_\infty$$.

• "...because for any three elements $x,y,z \in A$ such that $(x,y), (y,z) \in \cup_{N \in \mathbb N} S_N$..." I think it should be $x, y, z \in A$ right? – Lucas Apr 9 '19 at 19:56
• Ah yes, thanks. – Lee Mosher Apr 9 '19 at 20:49

If you have shown that

$$\{ (x,y) \in A \times A : \exists n\in \mathbb{N} \text{ and }a_0=x,a_1,...,a_n=y \text{ such that } (a_i,a_{i+1}) \in S \text{ for } 0\leq i

then you're essentially done. All you need next is to show that

1. the long expression on the right defines a transitive relation.
2. the long expression on the right is a superset of $$S$$.

Both of these are simple exercises in definition chasing. But the combination of them means exactly that the long expression is one of the things that $$\bar S$$ is defined to be the smallest of. Since you already know that it is no larger than $$\bar S$$, it must be $$\bar S$$ itself!