3
$\begingroup$

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

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

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$.

$\endgroup$
  • $\begingroup$ "...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? $\endgroup$ – Lucas Apr 9 '19 at 19:56
  • 1
    $\begingroup$ Ah yes, thanks. $\endgroup$ – Lee Mosher Apr 9 '19 at 20:49
0
$\begingroup$

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!

$\endgroup$

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.