Decisión y el espectro de innumerables

Question

En el año 2000, Hart, Hrushovski, y Laskowski clasificados completos de todos los de primer orden teorías contables lengua hasta sus innumerables espectros. Sin embargo, esto también implica que, dado un $any$ (recursivo, de primer orden, completa, en una contables idioma), $T$, se puede determinar lo que es incontable el espectro es? Más explícitamente, existe un procedimiento de decisión para hacerlo?

Claramente, podemos hacer esto para inestables teorías. Pero primero, tenemos que determinar si es o no un arbitrario (recursivo) la teoría de la $T$ es inestable. Asimismo categóricas teorías.

Gracias.

Answer 1

No existe ningún algoritmo para decidir si una teoría recursiva es estable o no.

Edit: La construcción original no funcionó, como Alex Kruckaman se indicó en los comentarios. Aquí está una manera de arreglar esto.

Supongamos que existe un algoritmo para decidir si una teoría recursiva es estable o no. Aquí es un algoritmo que resuelva la detención problema con él. Dada una máquina de Turing M y una palabra w, considere la posibilidad de un lenguaje con un único binario relación $<$. La teoría afirma que $<$ es lineal pedido con un máximo y un mínimo elemento, que, además, cada elemento de esperar que a la mínima que tiene un predecesor inmediato y cada elemento de esperar que la máxima ha inmediato sucesor. Si $\phi_n$ es la frase que afirma que existen en la mayoría de las $n$ elementos en el universo, $\phi_n$ ocupa en nuestra teoría de la iff la máquina ya ha detenido en el $n$-ésimo paso.

Usted consigue una teoría completa. Si se detiene la máquina, a continuación, es sólo la teoría de un finito linealmente conjunto ordenado, claramente estable. De lo contrario, es la teoría de una copia de los números enteros no negativos números seguidos por una copia del valor no positivo de los números enteros, que es inestable.

Esta prueba también muestra que no existe ningún algoritmo para decidir si una teoría es categórico, o PIN, etc.

Edit: de hecho, creo que la decisión de problema en la estabilidad de la complejidad de la $\Pi_2$. Usted necesita demostrar que para cada fórmula hay algunos $N$ de manera tal que la fórmula no lineal de orden de un conjunto de tamaño $N$. Esto le da una cota superior de a $\Pi_2$ sobre la complejidad, y el problema es lo suficientemente general como para ser, probablemente, $\Pi_2$- completa.