Computable sequence of rationals with a noncomputable limit

[Hill]

TL;DR

There is a computable sequence of rational numbers with limit whose n-th binary digit is not a computable function of n

This is a proof of the above statement in Stillwell's "Reverse Mathematics", p.77:

My question is, how do we know that the sequence $r_1, r_2, ...$ converges?

 

[jedishrfu]

Doesn't this come from the series being finite binary expansion? Being finite it will sum to a finite number.

 

[FactChecker]

You should describe $D$ for us, I assume it is a subset of the natural numbers.
With that in mind:
Since $f$ is an injection on a subset of $D$, each $r_n \lt \sum_{i=1}^\infty 2^{-i} = 1$. Since the sequence, $r_n$ is increasing and bounded, it converges.

 

[Hill]

Doesn't this come from the series being finite binary expansion? Being finite it will sum to a finite number.

I don't understand.
I understand that each $r_n$ has a finite binary expansion. I also understand that if the sequence converges, the limit is a finite number. I just don't see how we know that the sequence converges.

 

[Hill]

You should describe $D$ for us, I assume it is a subset of the natural numbers.

Yes, it is.

Since $f$ is an injection on a subset of $D$, each $r_n \lt \sum_{i=1}^\infty 2^{-i} = 1$. Since the sequence, $r_n$ is increasing and bounded, it converges.

The sequence $r_n=\sum_{i=1}^n 2^{-i}$ is increasing, but not necessarily the sequence $r_n=\sum_{i=1}^n 2^{-f(i)}$, I think.

 

[jedishrfu]

You are summing to n not to infinity. Convergence doesn't come into play.

A finite expansion will have a finite number of terms and in this case each term is $2^{-1}$ or did I misread the text.

 

[Hill]

You are summing to n not to infinity. Convergence doesn't come into play.

A finite expansion will have a finite number of terms and in this case each term is $2^-1$ or did I misread the text.

The statement is about n-th binary digit of the limit. For the limit to exist, the sequence needs to converge, doesn't it?

 

[Hill]

Perhaps it is not important for my question, but in case it clarifies the proof, here is the description of $D$, with explanation of the notation:

 

[Hill]

Since $f$ is an injection on a subset of $D$, each $r_n \lt \sum_{i=1}^\infty 2^{-i} = 1$. Since the sequence, $r_n$ is increasing and bounded, it converges.

You're right. The sequence $r_n=\sum_{i=1}^n 2^{-f(i)}$ is increasing. I was mistaken in the post #5.