Grados mínimos de estructuras

Question

Para esta pregunta, a estructura significa una estructura de primer orden en un lenguaje computable con dominio $\omega$ ; a copia de una estructura $\mathcal{A}$ es una estructura $\mathcal{B}\cong\mathcal{A}$ .

---

Dada una estructura $\mathcal{A}$ podemos intentar comprender la complejidad computacional teórica de $\mathcal{A}$ de diversas maneras. Un enfoque muy natural consiste en analizar la espectro de $\mathcal{A}$ : $$Spec(\mathcal{A})=\{d: d\text{ computes a copy of $ \. $}\}.$$ El espectro es siempre(ish) cerrado hacia arriba, pero más allá puede ser un objeto muy complicado, por lo que es natural considerar la grado de $\mathcal{A}$ : $$deg(\mathcal{A})=\min\{d: d\text{ computes a copy of $ \. $}\}.$$ Por desgracia, no todas las estructuras tienen un título: Linda Richter demostró que, a menos que $\mathcal{A}$ es "localmente complicado", entonces $Spec(\mathcal{A})$ contiene un par mínimo : hay $d_0, d_1\in Spec(\mathcal{A})$ tal que $d_0, d_1>_T0$ pero $d_0\wedge d_1\equiv_T0$ . Si $\mathcal{A}$ no tiene una copia computable, esto significa que $deg(\mathcal{A})$ no existe. Por ejemplo, si $\mathcal{L}$ es un orden lineal sin copia computable, $\mathcal{L}$ no tiene título.

Esto aborda la existencia de menos grados de presentaciones; me pregunto mínimo grados de presentación. Diga $d\in Spec(\mathcal{A})$ est $\mathcal{A}$ -minimal si no hay $e\in Spec(\mathcal{A})$ con $e<_Td$ .

Con optimismo:

Pregunta 1: ¿Cada estructura $\mathcal{A}$ tener un $\mathcal{A}$ -¿grado mínimo?

Y en sentido contrario,

Pregunta 2: ¿Existe un orden lineal $\mathcal{L}$ - sin copia computable - que tiene un $\mathcal{L}$ -¿grado mínimo?

Answer 1

Pregunta 1: ¿Cada estructura $\mathcal{A}$ tener un $\mathcal{A}$ -¿grado mínimo?

No. Diamondstone, Greenberg y Turetsky muestran que el conjunto de array no computable grados es un espectro de grados.

Y Downey, Jockusch y Stob demostraron que un título es array no computable si calcula a pb-genérico set. Ahora bien, si $G=A\oplus B$ es pb-genérica, entonces también lo son $A$ et $B$ y son estrictamente Turing por debajo de $A\oplus B$ .

Pregunta 2: ¿Existe un orden lineal $\mathcal{L}$ que tiene un $\mathcal{L}$ -¿grado mínimo?

Sí. Russell Miller demostró que existe un orden lineal cuyo espectro de grados incluye cada $\Delta^0_2$ grado, pero no $\mathbf 0$ .

Y Sacks demostró que hay un grado mínimo de Turing que es $\Delta^0_2$ Así hemos terminado.

Referencias

David Diamondstone, Noam Greenberg y Daniel Turetsky , Espectros naturales de alto grado , Computabilidad 2 (2013), n.º 1, 1--8.

Russell Miller , Les $\Delta^0_2$ -espectro de un orden lineal , J. Lógica simbólica 66 (2001), nº 2, 470--486.