Espectro de elementos en un conjunto.

Question

Supongamos que$X$ es un espectro. ¿Es$\mathbb{N}\setminus X$ un espectro?

Por espectro, queremos decir que es el conjunto que contiene todos los números naturales$n$ st; hay un modelo de$\phi$ con exactamente$n$ elementos (para algunas oraciones de primer orden$\phi$ en algún idioma$\mathcal{L}$).

Answer 1

(Editado en respuesta a los comentarios)

No sé la respuesta - nadie lo hace! Este es un problema abierto, lo que significa que demostrar que los espectros son cerrados bajo complementa o la prestación de un contraejemplo (un ejemplo de un espectro de $X$ cuyo complementar $\mathbb{N}\setminus X$ no es un espectro) sería un nuevo resultado matemático.

En un comentario en tu anterior pregunta, boumol publicó un enlace a la nota siguiente sobre finito espectros por Stanley Burris: https://www.math.uwaterloo.ca/~snburris/htdocs/WWW/PDF/espectros.pdf

El siguiente párrafo de estas notas respuestas a tu pregunta:

"En 1956, Asser miró a la pregunta de si el complemento de un espectro es de nuevo un espectro - el problema sigue abierto. Un fascinante resultado fue demostrado por Jones y Selman, en 1974, cuando demostraron que un subconjunto de $\mathbb{N}$ es un espectro en el fib puede ser aceptada por alguna máquina de Turing no determinista en tiempo $2^{O(n)}$. De esto se sigue que si NP es cerrado bajo la complementa, es decir, NP = co-NP, entonces los espectros son también cerrado bajo complementa. En consecuencia, para mostrar que los espectros no son cerrados bajo complementa es al menos tan difícil como muestra NP $\neq$ co-NP, y por lo tanto P $\neq$ NP."

Explicar las clases de NP y co-NP está fuera del alcance de esta respuesta, pero el llevar el mensaje de este párrafo es que si se puede mostrar que los espectros no son cerrados bajo complementa, también se han logrado resolver uno de los más importantes problemas abiertos en matemáticas y ciencias de la computación por demostrar que P$\neq$NP. Así que esto es duro.