Is $f(A) \in \Delta_n$ if $A \in \Delta_n$ when $f$ is computable?

Question

It's not hard to see that at least $f(A) \in \Sigma_n$, but is $f(A) \in \Pi_n$ true in general?

Answer 1

I assume that by $f(A)$ you mean the image of the set $A$ under $f$. To keep clear the distinction between the image of $f$ on a subset of its domain and on a point in its domain, let me use the notation $f[A]$ instead.

In general, when $A$ is $\Delta^0_n$ and $f$ is computable, it is not the case that $f[A]$ is $\Pi^0_n$. The basic reason is that taking the image of a set by a computable function is analogous to adding an existential quantifier. This is one of the central ideas in computability theory and descriptive set theory and underlies the arithmetic and projective hierarchies.

Here's an easy example illustrating this which will also answer your question. Consider the subset $A$ of $\mathbb{N}^2$ defined by $$ A = \{(a, b) \mid \text{program } a \text{ halts in at most } b \text{ steps}\}. $$ This set is computable, hence $\Delta^0_1$. And the function $\pi\colon \mathbb{N}^2 \to \mathbb{N}$ which projects onto the first coordinate is also certainly computable. But $\pi[A]$ is the set of halting programs, which is famously not $\Pi^0_1$.

More or less the same example also works for any $n \geq 1$. Recall that the $\Delta^0_n$ sets are exactly those computable by $0^{(n - 1)}$. So the set $$ A = \{(a, b) \mid \text{program } a \text{ with oracle } 0^{(n - 1)} \text{ halts in at most } b \text{ steps}\} $$ is $\Delta^0_n$, but its projection onto the first coordinate is $0^{(n)}$, which is famously not $\Pi^0_n$.

And in case you are concerned that in these examples the set $A$ is a subset of $\mathbb{N}^2$ rather than $\mathbb{N}$, just recall that there is a computable way to code pairs of natural numbers by single natural numbers so that the projection functions are computable.