Understanding the relation between transitive closure and convergent series

71 Views Asked by At

I am trying to better understand the concept of a transitive closure of a relation in the infinite case.

Suppose we have the set {$ q \in \mathbb{Q}| \exists n \in \mathbb{N}, q = 1 - (\frac{1}{2})^n $} $\cup$ {1},

or

{0,$\frac{1}{2}, \frac{3}{4}, \frac{7}{8},..., 1$}

Consider the relation $R$ on that set s.t.:

$xRy$ iff $y = x + (1 - x)\frac{1}{2}$

So, $\frac{1}{2}R\frac{3}{4}R\frac{7}{8}...$ and $R$ is not transitive.

Let $R^+$ be the transitive closure of $R$.

Question 1:

Is it the case that $\frac{1}{2} R^+ 1$?

My confusion:

  • For any particular natural $n$, the sequence of length $n$ on the relation $R$, starting at $\frac{1}{2}$, does not lead to 1.

  • On the other hand, $1/2 +1/4+ 1/8+... = 1$

  • In the link (nlab), transitive closure is defined using sequences of length $n$ (where $n$ is a natural number). With this in mind:

Question 2

Does it make sense to define a transitive closure relation with a sequence of length $\omega$ (infinite ordinal) , and would that make a difference here?

1

There are 1 best solutions below

0
On BEST ANSWER

You have already stated why the answer to the first question is No. The transitive closure of $R$ is the smallest relation that extends $R$ and is transitive. Since the intersection of a collection of transitive relations is also a transitive relation, and since any relation on a set $S$ is a subset of $S^2$, which is transitive, we can define the transitive closure of $R$ to be the intersection of all transitive relations extending $R$. In particular, note that the transitive closure of $R$ is a subset of all transitive relations extending $R$.

But

$$x\ \hat R\ y \iff \exists n \in \Bbb N, \{a_i\}_{i=0}^n\text{ such that } a_0 = x, a_n = y\text{ and }\forall i < n, a_i\ R\ a_{i+1}$$

is a transitive relation, extends $R$ and $1/2\ \hat R\ 1$ is false. Since the transitive closure $R^+$ of $R$ is a sub-relation of $\hat R$, $1/2\ R^+\ 1$ must also be false. (Yes, $\hat R$ actually is $R^+$, but that full equality is not necessary to deduce this result.)

Now, can you define a transitive extension $R'$ of $R$ by

$$x\ R'\ y \iff \exists\{a_i\}_{i=0}^\omega\text{ with } a_0 = x, a_\omega = y\text{ and }\forall i < \omega, a_i\ R\ a_{i+1}?$$

The answer is yes, for any relation $R$ on any set $S$, that does define a transitive extension of $R$. But if we then define the set $$S_\omega = \{x \in S \mid \exists \{a_n\}_{n\in \Bbb N}\text{ with }a_0 = x \text{ and } \forall n\in \Bbb N, a_n\ R\ a_{n+1}\}$$ that is, $x \in S_\omega$ if there is some infinite ascending $R$-related chain from $x$ - then for all $x\in S_\omega, y \in S$, we have $x\ R'\ y$, and for any $x \notin S_\omega$, it isn't related on-the-right to anything different than it would be under the transitive closure $R^+$. So we either get everything or nothing from this extension. The reason for this is that there is no $n$ with $n+1 = \omega$. Thus the condition $a_n\ R\ a_{n+1}$ puts no restrictions on the value of $y=a_\omega$.

If you want something interesting, you need to add some additional condition that relates $a_\omega$ to the values of earlier elements in the sequence. But there is no natural condition that can be applied to aribitrary relations. Any such condition is going to have to depend on properties of the specific relation. So we cannot define $a_\omega$ in general. But there are specific relations, such as this one where an appropriate condition can be made.

For the relation $R$ defined here, for any real number $x$ (not just in the set you specified), if $\{a_n\}_{n\in\Bbb N}$ is an ascending chain from $a_0 = x$, you can show that $\lim_{n\to\infty} a_n$ converges, thus we can define $$x\ R'\ y \iff \exists\{a_i\}_{i=0}^\omega\text{ with } a_0 = x, a_\omega = y\text{ and }\forall i < \omega, a_i\ R\ a_{i+1}\text{ and } \lim_{n\to\infty} a_n = a_\omega$$ and have a transitive extension $R'$ of $R$ with $1/2\ R'\ 1$. YAY!

But even easier, for any such sequence $\{a_n\}$ ascending under $R$, it is not hard to show that $\lim_{n\to\infty} a_n = 1$ always. Which means we could have just defined $R' = R^+ \cup \{(x, 1)\mid x \in \Bbb R\}$ ... Yay? Okay - this particular relation is not all that interesting. There are other relations that would have produced something less simple by this concept.

So, that leaves your final question:

would that make a difference here?

No. It does not. The question was not about some arbitrary transitive extension of $R$, it was about the transitive closure of $R$. The existence of other transitive extensions, however they are defined, is immaterial.