Depende de lo que quieres decir por "completo".
Digamos que usted quiere decir completa de Turing reducibilidad: es decir, usted desea un $\Delta^0_{n+1}$ a que everyother $\Delta^0_{n+1}$ conjunto de Turing es reducible. A continuación, hay, de hecho, $\Delta^0_n$ juegos completos! Post del teorema implica que el $\Delta^0_{n+1}$ conjuntos son exactamente los computable de$\emptyset^{(n)}$, $n$th Turing salto de $\emptyset$ (y podemos reemplazar "$\emptyset$" aquí con cualquier computable se establece, por supuesto). Por lo $\emptyset^{(n)}$ es un ejemplo natural de una $\Delta^0_{n+1}$-conjunto completo.
Mientras tanto, tenga en cuenta que el conjunto de $\emptyset^{(n)}$ sí es $\Sigma^0_n$, y su complemento es $\Pi^0_n$. Así que si un $\Sigma^0_n$- o $\Pi^0_n$-conjunto completo se reduce a usted, usted calcular $\emptyset^{(n)}$ y, por tanto, se $\Delta^0_{n+1}$duro: calcular cada $\Delta^0_{n+1}$.
En cuanto a su cuarta cuestión, el segundo salto de la emptyset $\emptyset''$ es un buen ejemplo de una $\Delta^0_3$-conjunto completo. Aquí están algunas otras:
Tot: el conjunto de índices de total de las funciones computables.
Fin: el conjunto de índices de las funciones computables con dominio finito.
El conjunto de índices de computable densa lineal órdenes sin extremos (tenga en cuenta que cualquier estructura con una "c".e. copia tiene una computable copia, de manera uniforme en el c.e. copia -, por lo que de hecho puede hablar de índices para computable estructuras de un tipo determinado).
El conjunto de Diophantine ecuaciones $\mathcal{E}(x, \overline{y})$ con un distinguido variable $x$ tal que para cada una de las $m$ la ecuación de $\mathcal{E}(m, \overline{y})$ tiene una solución. (Esto es esencialmente una aplicación de la MRDP teorema.)
Los complementos de cualquiera de los conjuntos de arriba (desde el complemento de a $\Delta^0_{n+1}$ es de nuevo un $\Delta^0_{n+1}$, y calcula las mismas cosas que a ti).
Pero tal vez usted quiere integridad de $m$-reducibilidad: es decir, todos los $\Delta^0_{n+1}$ $m$- se reduce a la serie dada.
En este caso, la respuesta es no , debido a que el propio (en un sentido preciso) de la transfinito Ershova jerarquía. Bien puede ser una manera más fácil para ver esto, pero creo que esta es la mejor en términos de la imagen que se pinta.
El Ershova jerarquía de las medidas de la complejidad de una $\Delta^0_2$ en términos de cómo se construye fuera de combinaciones Booleanas de c.e. los conjuntos. Empezamos con la diferencia finita de jerarquía:
Un conjunto es $1$-c.e. ($1$-co-c.e.) si es c.e. (co-c.e.).
Un conjunto es $(n+1)$-c.e. (($n+1$)-co-c.e.) si es que el conjunto de la teoría de la diferencia de $n$-c.e. y un conjunto c.e. conjunto (es el complemento de un $(n+1)$-c.e. conjunto).
La diferencia de jerarquía básicamente mide qué tan bien podemos aproximar a nuestro conjunto, en términos de cuántas veces un "computable adivinar la función" necesita cambiar su mente: $1$-c.e. corresponde a un posible cambio (de $0$ a $1$), $2$-c.e. corresponde a ser capaz de cambiar de$0$$1$%#%, y así sucesivamente.
Esto tiene un natural de la generalización en el transfinito a través del Límite de Lema y Kleene la noción de notaciones para computable ordinales. Supongamos $0$$X$. Por el límite lema, hay una computable $\Delta^0_2$ tal que para cada una de las $f$ el límite de $x$ existe y $\lim_{s\rightarrow \infty}f(x, s)$$$X=\{x: \lim_{s\rightarrow\infty}f(x, s)=1\}.$\Delta^0_2$ conjuntos son exactamente el límite computable conjuntos.
Ahora la existencia del límite de $ That is, the $ significa que $f$ sólo puede "cambiar de parecer" un número finito de veces en un determinado $f$! Y esto se parece mucho a la de diferencia finita de la jerarquía. El Ershova jerarquía de usos Kleene del ordinal notaciones para ampliar esta en el transfinito.
Antes de definir el Ershova jerarquía, permítanme describir brevemente lo $x$ es. Elementos de $\mathcal{O}$ puede considerarse como un tipo especial de índices para computable bien-orden (esto es en realidad esconden un montón de cosas interesantes bajo la alfombra, pero no va a llevar por mal camino). Dado a cualquiera de las dos índices, no necesariamente puede comparar puedo cocinar hasta dos computable bien ordenamientos tal que no es computable de la incrustación de ya sea en el otro - por lo $\mathcal{O}$ es un orden parcial en "puede computably digo es menor que". Cada computable bien el pedido tiene un montón de anotaciones correspondientes. En algunos contextos, notaciones se comportan bien - por ejemplo, definimos un transfinito saltar a través de una notación, pero resulta que dos notaciones para el mismo ordinal rendimiento de Turing equivalente de conjuntos; en otros contextos, sin embargo, las cosas son muy dependientes exactamente lo que se utiliza la notación (y que es el caso en este contexto, como menciono más abajo).
Tl;dr: $\mathcal{O}$ es un orden parcial de los "nombres" para computable ordinales, ordenado por "es computably menor que"; y cada computable ordinal tiene una notación en este sentido.
Ahora podemos definir la Ershova jerarquía (y ver Definición 4.1). Un conjunto $\mathcal{O}$ $X$- c.e. si hay algunas funciones computables $\alpha$ $f:\mathbb{N}^2\rightarrow\{0, 1\}$ tal forma que:
$o:\mathbb{N}^2\rightarrow\mathcal{O}$ límite-calcula $f$: $X$, $X=\{x: \lim_{s\rightarrow\infty}f(x, s)=1\}$.
$\mathbb{N}\setminus X=\{x: \lim_{s\rightarrow\infty}f(x, s)=0\}$ "comienza vacía": $f$ todos los $f(x, 0)=0$.
$x$ "comienza con pequeños": $o$ todos los $o(x, 0)<\alpha$.
$x$ mide la $o$ cambios, mediante la cuenta regresiva:
Siempre tenemos $f$; y
para cada una de las $o(x, s)\le o(x, s+1)$ $x, s, t$ si $s<t$ ($f(x, s)\not=f(x, t)$ cambia su mente entre el tiempo de la $f$ y el tiempo de $s$) tenemos a $t$.
¿Cuál es la conexión con $o(x, s)>o(x, t)$ juegos? Bien claramente cada $\Delta^0_2$-c.e. conjunto de es $\alpha$ (olvídate de $\Delta^0_2$, y utilizar el límite lema). A la inversa, dada una $o$ que limitan a calcular los $f$, podemos cocinar una notación $X$$\alpha$, básicamente construido a partir de los conocimientos que $\omega+1$ eventualmente se deposita en cada entrada, por lo que el $f$ $X$- c.e. (tenga en cuenta que esto refleja que "$\alpha$-c.e.-ness" realmente depende de la notación $\alpha$, no solo el ordinal representa). Por lo que el $\alpha$ conjuntos son exactamente los conjuntos que se $\Delta^0_2$-c.e. para algunos $\alpha$.
OK, entonces, ¿qué? Bueno, no es demasiado duro para construir - para cualquier $\alpha\in\mathcal{O}$ $\alpha,\beta\in\mathcal{O}$ - $\beta<\alpha$- c.e. establece que no es $\alpha$reducible a cualquier $m$-c.e. conjunto. Desde $\beta$ no tiene ningún elemento de la parte superior y cada una de las $\mathcal{O}$ $\Delta^0_2$- c.e. para algunos $\alpha$, esto significa que no hay $\alpha$-un conjunto completo en el sentido de $\Delta^0_2$-reducibilidad.
Este se encarga de la $m$ de los casos; y ahora simplemente nos muestran que la Ershova jerarquía puede ser adecuadamente relativizada.
