Hace un subconjunto de los números naturales existe, que no es un espectro?

Question

Hemos tenido la siguiente definición de un espectro:

$S \subset \mathbb{N}\backslash\{0\}$ es llamado espectro, si existe un lenguaje formal L y L-fórmula $\phi$ de tal manera, que para cada una de las $n \in \mathbb{N}, n \neq 0$: $n\in S \Leftrightarrow \phi$ tiene un modelo con un dominio con cardinalidad n.

Ahora la pregunta es: ¿existe un subconjunto de a $\mathbb{N}\backslash\{0\}$ que no es un espectro? Supongo que existe un subconjunto, que no es un espectro. Es mi suposición correcta? Pero incluso si esto es correcto, no sé cómo este subconjunto se vería o cómo se podría demostrar esto. Tal vez alguien podría ayudarme a prueba mi hipótesis o decirme por qué está mal.

Answer 1

Hay, esencialmente, sólo countably muchos $\phi$, pero hay una cantidad no numerable de subconjuntos.

Answer 2

Dado $\phi$ $n \in \Bbb{N}_{>0}$ es decidable si $\phi$ tiene un modelo de cardinalidad $n$, así que el espectro es un conjunto recursivo. Un no-recursiva como, por ejemplo, el conjunto de los números de Gödel de las fórmulas que se demostrable en PA (la aritmética de Peano) no puede ser un espectro.

Answer 3

De hecho, no es una caracterización exacta en términos de la teoría de la complejidad de la clase de espectros: $A$ es un espectro si y sólo si $A$ es en la complejidad de la clase NEXP. Para cualquier conjunto no en NEXP no es un espectro.

Ver, por ejemplo, la sección 5.4 de la encuesta papel de los Cincuenta años del espectro problema. Esto significa que el clásico espectro problema (sobre la cual el artículo enlazado es una encuesta) - "Es el complemento de un espectro de un espectro?" - es equivalente a la conocida problema abierto en la teoría de la complejidad, "¿ NEXP=coNEXP?"