Zheng and Weihrauch (http://www-sst.informatik.tu-cottbus.de/~wwwti/zheng/publications/1999/mfcs99.pdf) define a real number $x$ to be $\Sigma_n$ if and only if there is a computable function $f:\mathbb{N}^n\rightarrow\mathbb{Q}$ such that $x=\sup_{i_1}\inf_{i_2}...f(i_1,...,i_n)$. Another possible definition is that $x$ is $\Sigma_n$ if and only if its Dedekind cut $\{q\in\mathbb{Q}|q<x\}$ is defined by a $\Sigma_n$ formula (using an encoding of rational numbers with natural numbers). Zheng and Weihrauch's definition is at least as strong as mine because $q<\sup_{i_1}\inf_{i_2}...f(i_1,...,i_n)\iff\exists i_1 \forall i_2 ... q<f(i_1,...,i_n)$. Are the two definitions equivalent, or is there a real number that is $\Sigma_n$ by my definition but not by Zheng and Weihrauch's for some $n$?
- $\begingroup$ I believe the answer is yes. First do the $\Sigma_1$ and $\Pi_1$ cases. Then the rest should follow by induction. $\endgroup$Jason Rute– Jason Rute2016-04-02 20:50:18 +00:00Commented Apr 2, 2016 at 20:50
1 Answer
They are the same as the following induction proof shows.
Base case: For $\Sigma_1$, if $x = \sup_i f(i)$ for $f$ computable, then $q < x$ is equivalent to the $\Sigma_1$ statement $\exists i [q<f(i)]$. Conversely, if $\{q\mid q < x\}$ is computably enumerable, then $x = \sup_i f(i)$ where $f(i)$ is a computable enumeration of all $q < x$.
For $\Pi_1$, if $x = \inf_i f(i)$ for $f$ computable, then $q \leq x$ is equivalent to $\forall i [q \leq f(i)]$. Conversely, if $\{q\mid q \leq x\}$ is co-c.e., then $x = \inf_i f(i)$ where $f(i)$ is a computable enumeration of ${q\mid q > x}$ (which is c.e., since it is the complement of $\{q\mid q \leq x\}$).
Induction step: For $\Sigma_{n+1}$, assume $x = \sup_i f(i)$ where $f(i)$ is $\Pi_n[i]$. By the induction hypothesis, $\{q\mid q\leq f(i)\}$ is $\Pi^n[i]$. Then $q \leq x$ is equivalent to some $\Sigma_{n+1}$ formula expressing $\exists i\ [q \leq f(i)]$.
Conversely, if $C = \{q\mid q < x\}$ is $\Sigma_{n+1}$, then $q < x$ is equivalent to $\exists i\ \phi(i,q)$ where $\phi(i,q)$ is $\Pi_n$. Since $C$ is downward closed, we may assume $\phi(i,q)$ is downward closed in $q$. (Replace $\phi(i,q)$ with $q\leq q_{i_0} \land \phi(i_1,q_{1_0})$ where $i$ encodes the pair $(i_0,i_1)$ and $q_i$ is the $i$th rational.) Now, let $$f(i) := \sup\{q\mid \phi(i,q)\}.$$ Then $x = \sup_i f(i)$, and by the induction hypothesis, $f(i)$ is $\Pi_1[i]$.
The $\Pi_{n+1}$ case is similar. QED
