Equality of sets, transitive closure of a relation.

Question

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<n \}$$

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<n \} \subset \overline{S}$$

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<n \}$$

Answer 1

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<n \} $$

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<n \} $$ 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$.

Answer 2

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<n \} \subset \overline{S}$

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!