Connection between computable real numbers and the arithmetic hierarchy

150 Views Asked by At

I am trying to prove the following statement: The set of indices for recursive convergent sequences of rational numbers is $\Pi_{2}$-complete.

Any hint would be appreciated! I am not very sure how can one formally speak about a convergent sequence in $\mathbb{N}$, then any resource to see the full description of the possible theory that has been developed would be also appreciated!.

1

There are 1 best solutions below

0
On BEST ANSWER

It seems to me that the set is $\Pi_3$-complete, rather than $\Pi_2$ complete.

First, notice that to say that a sequence is convergent is naturally a $\Pi_3$ assertion, since you have to say: for every $n$ there is a stage in the sequence such that for all sequence numbers beyond that stage, they are within $\frac 1n$ of each other. This is three alternating quantifiers $\forall \exists \forall$, and so convergence is within the class $\Pi_3$.

Conversely, suppose we are given a $\Pi_3$ formula $\varphi(x) = \forall n\exists m\forall k\ \psi(x,n,m,k)$, where $\psi$ is $\Delta_0$. Let's construct a sequence of rational numbers in a computable way, such that the sequence converges if and only if $\varphi(x)$ holds. Our sequence will converge to $0$ if and only if the statement is true, and otherwise, it will have oscillations of some small size near zero preventing convergence. On input $x$, we start enumerating the sequence, which will consist of a lot of $0$s, with some other numbers occasionally added in. For each $n$, we start looking for an $m$ that will survive for all $k$ with $\psi(x,n,m,k)$. Every time we have to change to a new candidate $m$ for a given $n$, because the previous one failed at some $k$, then we cause a temporary bump in the sequence by placing the number $\frac1n$ on the sequence, and then back to all $0$s. If every $n$ has an $m$ that survives for all $k$, then for each $n$ there will be at most finitely many such bumps, and so the sequence will converge to zero, since by waiting we will be able to bound the size of the bumps as low as we like. If some $n$ has no $m$ that survives for all $k$, then the sequence will have infinitely many bumps of size $\frac 1n$, preventing convergence.

In this way, our method reduces any $\Pi_3$-problem to the convergence problem, showing that it is $\Pi_3$-complete.