Is the range of a total $\Pi^1_1$ function $\Delta^1_1$?

67 Views Asked by At

Let $f:\mathbb{N}\rightarrow\mathbb{N}$ be a total function whose graph is definable via a $\Pi^1_1$ formula. Then is the range of $f$ a $\Delta^1_1$ set? Clearly the range is $\Pi^1_1$, but is it $\Sigma^1_1$ as well?

If it is, it possible to concretely write down a $\Sigma^1_1$ formula for the range of $f$ given a specific $\Pi^1_1$ definition of the graph of $f$.

1

There are 1 best solutions below

0
On BEST ANSWER

$a$ belongs to the range of $f$ iff $(\exists x\in\mathbb{N})(\forall y\in\mathbb{N})(y=a \lor f(x)\ne y).$

The two quantifiers in front are numeric, and $``f(x)\ne y”$ is $\Sigma_1^1,$ so the formula as a whole is $\Sigma_1^1.$