Teoría de primer orden con ordenación lineal

Question

( Actualizado ) Estoy tratando de resolver el siguiente problema, ¡cualquier ayuda sería muy apreciada!

Sea la teoría en el lenguaje que contiene sólo el símbolo relacional binario , y dice ``la relación es un ordenamiento lineal, y cada elemento tiene un sucesor inmediato en ''.

(a) Escriba con precisión en el lenguaje de la lógica de primer orden.

(b) Demuestre que existe una frase en el lenguaje, que no puede ser decidida a partir de los axiomas de .

Esto es lo que tengo hasta ahora:

a) = { x y z ((x y y z) x z), x (x x), x y ((x y y x) x = y), x y (x y y x), x y z (x z x y)}

Creo que esto es correcto.

b) Estoy un poco confundido con respecto a la letra b). Lo que estoy pensando es que tengo que demostrar que existe una sentencia que es indecidible. Así que, basándome en la sugerencia de Max (gracias), se me ocurrió la siguiente frase:

x y z (z x (z y y x) .

Esto es indecidible, porque no hay ninguna frase en la que se demuestre esta sentencia.

Answer 1

Ya he respondido en los comentarios sobre cómo expresar que cada elemento tiene un sucesor inmediato y creo que lo has entendido, así que no me extenderé aquí (a no ser que quieras que lo haga)

Para la segunda parte, la idea es utilizar lo que algunos llaman el teorema de la corrección que no es más que un teorema que dice que la forma en que hacemos las pruebas está bien. Afirma que "Para cualquier lenguaje $L$ , teoría $T$ y la fórmula $\phi$ , si $T\vdash \phi$ , entonces cualquier modelo $M$ de $T$ tiene $M\models \phi$ ". Intuitivamente dice que si se puede demostrar algo, entonces es "siempre verdadero".

Aquí ya que queremos demostrar que $\Gamma$ hace no demostrar una determinada fórmula queremos utilizar el contrapositivo: si hay algún modelo $M$ de $\Gamma$ tal que $\neg(M\models \phi)$ , entonces no hay prueba de $\phi$ en $\Gamma$ . Además, si también encontramos un modelo $N$ de $\Gamma$ tal que $N\models \phi$ Tendremos que no hay pruebas de $\neg \phi$ en $\Gamma$ .

Por lo tanto, lo que queremos hacer es encontrar una fórmula $\phi$ y modelos de $\Gamma$ $M,N$ tal que $M\models \phi$ y $N\models \neg \phi$ . Un modelo de $\Gamma$ es simplemente un conjunto totalmente ordenado en el que cualquier elemento tiene un sucesor inmediato. ¿Cuáles son los más sencillos? Supongo que son $\mathbb{N}$ y $\mathbb{Z}$ con la ordenación habitual. Obviamente no son isomorfos (como conjuntos ordenados) ya que $\mathbb{N}$ está bien ordenado y $\mathbb{Z}$ no lo es.

Este hecho nos hace pensar (sin razón, porque la equivalencia elemental y el isomorfismo son conceptos diferentes) que debería haber alguna fórmula que se cumpla en uno y no en el otro.

Dicha fórmula sería "todo elemento tiene un predecesor inmediato" (dejaré que lo escribas bien, es un buen ejercicio - lo llamaré $\phi$ ), que se mantiene en $\mathbb{Z}$ pero no en $\mathbb{N}$ ( $0$ no tiene ningún predecesor).

Así que hemos encontrado una fórmula $\phi$ tal que $\mathbb{Z}\models \phi$ , $\mathbb{N}\models \neg\phi$ . Por lo tanto, por lo que he mostrado antes, no hay pruebas en $\Gamma$ de $\phi$ o $\neg\phi$ : $\phi$ es indecidible en $\Gamma$