In the arithmetical hierarchy: Are there $\Delta_n^0$-complete sets? If so:
- What are examples?
- Is there a nice characterization of $\Delta_{n+1}^0$-complete (or -hard) sets in terms of (complete) sets in $\Sigma_n^0$ and/or $\Pi_n^0$?
- Is a problem necessarily $\Delta_{n+1}^0$-hard, if one can many-one-reduce both a $\Sigma_n^0$-complete and $\Pi_n^0$-complete set to it?
- What is an example of a $\Delta_3^0$-complete set?
(I mean completeness and hardness in the sense of many-one-reducibility.)
It depends what you mean by "complete."
Let's say you mean complete for Turing reducibility: that is, you want a $\Delta^0_{n+1}$ set to which everyother $\Delta^0_{n+1}$ set is Turing reducible. Then there are indeed $\Delta^0_n$ complete sets! Post's theorem implies that the $\Delta^0_{n+1}$ sets are exactly those computable from $\emptyset^{(n)}$, then $n$th Turing jump of $\emptyset$ (and we can replace "$\emptyset$" here with any computable set, of course). So $\emptyset^{(n)}$ is a natural example of a $\Delta^0_{n+1}$-complete set.
Meanwhile, note that the set $\emptyset^{(n)}$ itself is $\Sigma^0_n$, and its complement is $\Pi^0_n$. So if a $\Sigma^0_n$- or $\Pi^0_n$-complete set reduces to you, you compute $\emptyset^{(n)}$ and hence are $\Delta^0_{n+1}$-hard: you compute every $\Delta^0_{n+1}$ set.
As to your fourth question, the second jump of the emptyset $\emptyset''$ is a good example of a $\Delta^0_3$-complete set. Here are some others:
Tot: the set of indices of total computable functions.
Fin: the set of indices of computable functions with finite domain.
The set of indices of computable dense linear orders without endpoints (note that any structure with a c.e. copy has a computable copy, uniformly in the c.e. copy - so we may indeed speak of indices for computable structures of a given type).
The set of Diophantine equations $\mathcal{E}(x, \overline{y})$ with a distinguished variable $x$ such that for each $m$ the equation $\mathcal{E}(m, \overline{y})$ has a solution. (This is essentially an application of the MRDP theorem.)
The complements of any of the sets above (since the complement of a $\Delta^0_{n+1}$ set is again a $\Delta^0_{n+1}$-set, and computes the same things as it).
But maybe you want completeness for $m$-reducibility: that is, every $\Delta^0_{n+1}$ set $m$-reduces to the given set.
In this case, the answer is no due to the properness (in a precise sense) of the transfinite Ershov hierarchy. There may well be an easier way to see this, but I think this is the best one in terms of the picture it paints.
The Ershov hierarchy measures the complexity of a $\Delta^0_2$ set in terms of how it is built out of Boolean combinations of c.e. sets. We start with the finite difference hierarchy:
A set is $1$-c.e. ($1$-co-c.e.) if it is c.e. (co-c.e.).
A set is $(n+1)$-c.e. (($n+1$)-co-c.e.) if it is the set-theoretic difference of an $n$-c.e. set and a c.e. set (is the complement of an $(n+1)$-c.e. set).
The difference hierarchy basically measures how nicely we can approximate our set, in terms of how many times a "computable guessing function" needs to change its mind: $1$-c.e. corresponds to one possible change (from $0$ to $1$), $2$-c.e. corresponds to being able to change from $0$ to $1$ to $0$, and so-on.
This has a natural generalization into the transfinite via the Limit Lemma and Kleene's notion of notations for computable ordinals. Suppose $X$ is $\Delta^0_2$. By the limit lemma, there is a computable $f$ such that for each $x$ the limit $\lim_{s\rightarrow \infty}f(x, s)$ exists and $$X=\{x: \lim_{s\rightarrow\infty}f(x, s)=1\}.$$ That is, the $\Delta^0_2$ sets are exactly the limit computable sets.
Now the existence of the limit of $f$ means that $f$ can only "change its mind" finitely many times on a given $x$! And this sounds a lot like the finite difference hierarchy. The Ershov hierarchy uses Kleene's ordinal notations to extend this into the transfinite.
Before I define the Ershov hierarchy, let me briefly describe what $\mathcal{O}$ is. Elements of $\mathcal{O}$ can be thought of as special kinds of indices for computable well-orderings (this is actually hiding a lot of interesting stuff under the rug, but it won't lead you astray). Given any two such indices, I can't necessarily compare them - I can cook up two computable well-orderings such that there is no computable embedding of either into the other - so $\mathcal{O}$ is a partial order under "can computably tell is smaller than". Every computable well-ordering has lots of corresponding notations. In some contexts, notations behave well - e.g. we define a transfinite jump via a notation, but it turns out that two notations for the same ordinal yield Turing-equivalent sets; in other contexts, however, things are very dependent on exactly what notation is used (and that is the case in this context, as I mention below).
Tl;dr: $\mathcal{O}$ is a partial order of "names" for computable ordinals, ordered by "is computably smaller than"; and every computable ordinal has a notation in this sense.
Now we can define the Ershov hierarchy (and see Definition 4.1). A set $X$ is $\alpha$-c.e. if there are some computable functions $f:\mathbb{N}^2\rightarrow\{0, 1\}$ and $o:\mathbb{N}^2\rightarrow\mathcal{O}$ such that:
$f$ limit-computes $X$: $X=\{x: \lim_{s\rightarrow\infty}f(x, s)=1\}$, $\mathbb{N}\setminus X=\{x: \lim_{s\rightarrow\infty}f(x, s)=0\}$.
$f$ "begins empty": $f(x, 0)=0$ for all $x$.
$o$ "begins small": $o(x, 0)<\alpha$ for all $x$.
$o$ measures how $f$ changes, by counting down:
We always have $o(x, s)\le o(x, s+1)$; and
for each $x, s, t$ with $s<t$, if $f(x, s)\not=f(x, t)$ (i.e. $f$ changes its mind between time $s$ and time $t$) we have $o(x, s)>o(x, t)$.
What's the connection with $\Delta^0_2$ sets? Well clearly every $\alpha$-c.e. set is $\Delta^0_2$ (forget about $o$, and use the limit lemma). Conversely, given an $f$ which limit-computes $X$, we can cook up a notation $\alpha$ for $\omega+1$, basically built from the knowledge that $f$ eventually settles on every input, so that $X$ is $\alpha$-c.e. (note that this reflects that "$\alpha$-c.e.-ness" really depends on the notation $\alpha$, not just the ordinal it represents). So the $\Delta^0_2$ sets are exactly the sets which are $\alpha$-c.e. for some $\alpha\in\mathcal{O}$.
OK, so what? Well, it's not too hard to build - for any $\alpha,\beta\in\mathcal{O}$ with $\beta<\alpha$ - an $\alpha$-c.e. set which is not $m$-reducible to any $\beta$-c.e. set. Since $\mathcal{O}$ has no top element and every $\Delta^0_2$ set is $\alpha$-c.e. for some $\alpha$, this means there is no $\Delta^0_2$-complete set in the sense of $m$-reducibility.
This handles the $\Delta^0_2$ case; and now we simply show that the Ershov hierarchy can be appropriately relativized.