Ejemplo de teoría incompleta, pero decidible, y de teoría completa e indecidible, pregunta

Question

En wikipedia está escrito que

La decidibilidad no debe confundirse con la exhaustividad. Por ejemplo, la teoría de los campos algebraicamente cerrados es decidible pero incompleta, mientras que el conjunto de todos los enunciados verdaderos de primer orden sobre los enteros no negativos en el lenguaje con + y × es completo pero indecidible.

Una teoría se llama completa (ver wikpedia:teoría completa) si para cada frase o su negación es demostrable en la teoría. Pero entonces, supongo que la completitud produciría decidibilidad, ya que podemos simplemente enumerar todas las proposiciones demostrables (las pruebas son derivaciones de longitud finita) y comprobar si la actual es igual a la sentencia (o su negación) en cuestión. Por completitud, este procedimiento terminará.

Así que tal vez la completitud del sistema lógico se entiende en ese párrafo, es decir, un sistema lógico es completo si las oraciones válidas coinciden con las demostrables. En El resultado de completitud de Gödel La lógica de primer orden está completa. Tal y como está escrito aquí la teoría de los campos algebraicamente cerrados es axiomatizable en lógica de primer orden, por lo que no podría ser incompleta en este sentido, pero el párrafo citado afirma exactamente eso.

Así que, para ambas interpretaciones de la completitud, completitud de una teoría, o de un sistema lógico, el párrafo citado no tiene sentido para mí. ¿Podría alguien explicar lo que me falta, o lo que se quiere decir aquí?

Answer 1

El pasaje sobre los campos algebraicamente cerrados es correcto, pero es fácil de engañar: el característica no se especifica, por lo que la teoría ACL de campos algebraicamente cerrados no decide, por ejemplo, la sentencia " $\forall x(x+x=0)$ ." Así que ACL es de hecho un ejemplo de una teoría incompleta-pero-decidible.

Lo que sí es cierto es que el ACL $_p$ - la teoría de los campos algebraicamente cerrados de la característica $p$ , para $p\in\{$ primos $\}\cup\{0\}$ - es completa y decidible.

EDIT: La afirmación " $T$ no decide $\varphi$ " es potencialmente ambiguo, ya que tiene dos interpretaciones razonables:

• Tampoco $\varphi$ ni $\neg\varphi$ es $T$ -probable (en símbolos: $T\not\vdash\varphi$ y $T\not\vdash\neg\varphi$ ).

• Hay modelos de $T$ en el que $\varphi$ se mantiene, y hay modelos de $T$ en el que $\varphi$ falla (en símbolos: $T\not\models\neg\varphi$ y $T\not\models\varphi$ ).

Afortunadamente, por el teorema de completitud (véase más adelante) estas dos interpretaciones son equivalentes. Nótese que esto es una peculiaridad de la lógica de primer orden; por esta razón, es bueno evitar decir " $T$ decide $\varphi$ " cuando se habla de lógicas que no son de primer orden, a menos que ya se haya especificado lo que significa.

---

Creo que lo anterior resolverá tu pregunta, pero sólo para completar (jeje) déjame terminar resumiendo la situación:

• Cualquier teoría axiomática recursivamente enumerable que sea completa es también decidible (basta con buscar en las pruebas). Sin embargo, una teoría completa no tiene por qué ser decidible, por ejemplo $Th(\mathbb{N};+,\times)$ ("aritmética verdadera") es completa ( $Th(\mathcal{M})$ es siempre completa, para cualquier estructura $\mathcal{M}$ ) pero no es decidible.

  • Por cierto, por El truco de Craig una teoría es r.e.-axiomatizable si es recursivamente axiomatizable.
• La lógica de primer orden es (sana y) completa, en el siguiente sentido: para cualquier conjunto de oraciones $\Gamma$ , una frase $\varphi$ es cierto en todos los modelos de $\Gamma$ si y sólo si existe una prueba de $\varphi$ de $\Gamma$ . En símbolos, $$\Gamma\models\varphi\iff\Gamma\vdash\varphi.$$ La dirección de derecha a izquierda es básicamente trivial; la dirección de izquierda a derecha requiere trabajo.