modelos lógicos de primer orden

Question

Dejemos que $\Gamma$ sea el conjunto de frases que contienen la fórmula

$\exists x(x\neq f^n(x)) $

para cada $n>0$ .

Estoy tratando de conocer los modelos de $\Gamma$ en particular, ¿hay una sola frase de FOL que sea verdadera exactamente en los modelos de $\Gamma$ . Gracias.

Answer 1

Si hubiera una sola frase $\phi$ que es equivalente a la colección infinita de sentencias $\exists x\,(f^n(x)\neq x)$ , que abreviaré como $\beta_n$ entonces, por el teorema de completitud para la lógica de primer orden, habría una deducción formal de $\phi$ de la $\beta_n$ 's. Esa deducción, al ser una lista finita de sentencias, utilizaría sólo finitamente muchas de las $\beta_n$ 's. Elige un número $m$ más grande que todos los finitos $n$ de tal manera que $\beta_n$ se utiliza en su deducción. Considere un modelo que consiste en $m$ y una función $f$ que los permuta cíclicamente --- un solo ciclo de longitud $m$ . Este modelo satisface todas las $\beta_n$ utilizado en su deducción (de hecho, satisface $\beta_n$ por cada $n$ que no es divisible por $m$ ), por lo que, gracias a esa deducción, satisface $\phi$ . Pero no satisface $\beta_m$ . Así que $\phi$ no es equivalente a la colección de todos sus $\beta$ 's.

Answer 2

$$ \forall n \exists x (n > 0 \implies x \neq f^n(x)) $$

Para todos $n$ más grande que $0$ existe $x$ que no es igual a $f^n(x)$ .