La teoría de órdenes infinitas discretas está completa

Question

En respuesta a otra pregunta, Joel David Hamkins afirma que la teoría de la interminable discretos órdenes es completa. Me sugirió que me pregunte esto como una cuestión separada así que aquí estoy : ¿cómo se puede demostrar esta afirmación ?

Claramente los ejemplos que da a mostrar que esta teoría no es $\aleph_0$categorías ($\Bbb{Z}$$\Bbb{Z}+\Bbb{Z}$ no son isomorfos. Para ver esto, observe que cualquier subconjunto de a $\Bbb{Z}$ que está delimitada desde abajo, es muy ordenada, considerando que no es el caso de $\Bbb{Z}+\Bbb{Z}$ - no sé si hay una manera más fácil la prueba).

Sospecho que esta teoría no es $\lambda$categoría para cualquier infinita cardenal $\lambda$ (a pesar de que no soy capaz de demostrarlo), así que creo que no se puede utilizar este método para probar la integridad.

Sé que hay otras maneras de mostrar su integridad como cuantificador de eliminación, pero no estoy muy conscientes de estos y la falta de práctica, así que no puedo esperanza a probar de esa manera (pero si usted me puede mostrar, con mucho gusto hubiera una respuesta mediante la eliminación de cuantificador).

Así, en una nota de lado: ¿qué métodos existen para probar que una cierta teoría es completa ?

Answer 1

Tienes toda la razón en que esta teoría no es $\kappa$categoría para cualquier $\kappa$: considerar el lineal órdenes de $\mathbb{Z}\cdot \kappa$ frente al $\mathbb{Z}\cdot(\mathbb{Q}+\kappa)$, cada uno de los cuales es discreto y de tamaño $\kappa$.

Como para muestra primaria de equivalencia, tenga en cuenta que la eliminación de cuantificador no trabajo aquí: por ejemplo, la fórmula "$\exists x\forall y(a<x<b$ pero $a<y<b\implies x=y)$", $a$ $b$ están separados por exactamente en un punto. Esta fórmula no es equivalente a cualquier cuantificador-libre.

En su lugar, el derecho de la herramienta a utilizar aquí es Ehrenfeucht-Fraisse juegos. No es demasiado difícil encontrar una estrategia ganadora para el Duplicador en el juego de $G_n(\mathbb{Z}, \mathcal{M})$ siempre $\mathcal{M}$ es una interminable discretos lineales de orden y $n\in\mathbb{N}$, de manera que todos son elementarily equivalente a $\mathbb{Z}$ (y por lo tanto a cada uno de los otros). La observación clave es que, en la longitud de la$n$, dos puntos que son más de $2^n$(ish) aparte "podría" ser infinitamente lejos; jugar con el juego un poco y verás a lo que me refiero.

---

Por cierto, este argumento se demuestra que cualquier fórmula es equivalente, sobre esta teoría, a un valor Booleano conjunción de $\Sigma_2$ fórmulas (entre estos son las oraciones de la forma "La distancia entre el $a$ $b$ es exactamente $n$"$n\in\mathbb{N}$. Así que hay una forma débil de eliminación de cuantificadores aquí, es más complicado que los que suelen tratar con (cuantificador libre y $\Sigma_1$).

Esto hace, sin embargo, dar un cuantificador de la eliminación de la ruta hacia la solución del problema: la adición de predicados diciendo: "son exactamente $n$ distancia" en el lenguaje, la teoría resultante elimina los cuantificadores. (Otro lugar donde usamos este truco está en que muestra la decidability de la aritmética de Presburger.)