¿Cuál es un ejemplo de un modelo finito en lógica de primer orden que tiene un único elemento indefinible?

Question

Esto es (una ligera paráfrasis) de la pregunta 1.3.14 del libro Model Theory de Chang y Keisler.

"Demuestre que para cada número natural $n$ Hay una lengua $L_n$ y el modelo finito $M_n$ de $L$ tal que $M_n$ tiene precisamente $n$ elementos indefinidos".

Aquí, un elemento $x\in M$ es definible si existe una fórmula (de primer orden) en $L$ , llamado $\phi$ , de tal manera que $x$ es el único elemento de $M$ Satisfaciendo a $\phi$ . Por supuesto, "indefinible" significa "no definible".

Está marcado con estrellas, lo que indica que es más difícil que un problema estándar de ese libro.

Chang y Keisler señalan que $n=1$ es el único caso difícil. Con ese espíritu, aquí está la prueba para todos $n\neq 1$ .

Dejemos que $L_n$ tienen un único símbolo de predicado de 2 lugares (estoy pensando en $L_n = \{ < \}$ ). Sea $M_n$ sea el orden parcial con el mínimo a y con elementos $b_1,...,b_{n}$ con $a < b_i$ para todos $i$ y el $b_i$ incomparables entre sí.

En primer lugar, hay que tener en cuenta que a es definible: satisface de forma única $\phi(x) =$ para todo y, $x\leq y$ .

Ahora bien, si $n =0$ no hay $b_i$ y, por tanto, en este modelo, tenemos 0 elementos indefinibles.

Si $n > 1$ Entonces afirmo que todos los $b_i$ son indefinibles. La respuesta corta es que cualquier permutación del $b_i$ puede extenderse a un isomorfismo único de $M_n$ . Por lo tanto, para cualquier fórmula $\phi$ tenemos $\phi(b_i)$ si $\phi(b_j)$ para todos $b_j$ . Por lo tanto, no $\phi$ puede señalar cualquier $b_i$ , por lo que cada $b_i$ es indefinible.

Esta prueba falla completamente para $n=1$ , ya que entonces $b_1$ es el único elemento que satisface "b_1 no es a". O más bien en el espíritu de la lógica de primer orden, $b_1$ es el único elemento que satisface $\phi(x) =$ hay un $y$ tal que para todo $z$ , $y< z$ y $x$ no es igual a $y$ ." Por cierto, esto demuestra que cualquier modelo que funcione para $n=1$ debe tener al menos 3 elementos.

Entonces, mi pregunta es:

¿Cuál es un ejemplo de un lenguaje con modelo finito que tiene precisamente un elemento indefinible? ¿Se conoce la menor cardinalidad de dicho modelo?

Gracias de antemano.

Answer 1

Si sus lenguajes tienen necesariamente la relación =, que es una suposición común, entonces el caso n=1 es imposible en un modelo finito. La razón es que si un modelo $M$ tiene $k$ elementos $x_1$ , $x_2$ , ... $x_k$ para un número finito de $k\gt 1$ y cada $x_i$ se define por $\varphi_i(x)$ para $i\lt k$ , entonces el elemento restante $x_k$ se define mediante la fórmula $\neg\varphi_1(x)\wedge\cdots\wedge \neg\varphi_{k-1}(x)$ . Si $M$ tiene un solo elemento, entonces se define por la fórmula $x=x$ .

Pero si no insistimos en que $=$ está en la lengua, entonces dejemos que $L$ ser el lenguaje vacío, que no tiene ninguna relación. En este caso, no hay fórmulas atómicas y, por tanto, no hay fórmulas bien formadas para definir elementos, por lo que un modelo de un punto tiene exactamente un elemento indefinible.

Si permitimos infinitos modelos, entonces podemos arreglar fácilmente para tener exactamente un elemento indefinible, incluso en un lenguaje con $=$ . Por ejemplo, considere el lenguaje con infinitos símbolos constantes, y tenga un modelo donde todas estas constantes son interpretadas por diferentes elementos, y hay un objeto extra sin nombre. Ese objeto extra será el único elemento no definible, incluso cuando $=$ está en la lengua.

Answer 2

No se puede tener la igualdad como una relación en el lenguaje que se interpreta como igualdad en el modelo, de lo contrario se puede definir el elemento indefinible como aquel (uno) que no es igual a ninguno de los definibles. La mayoría de los lenguajes de uso común tienen igualdad, por lo que es difícil pensar en un ejemplo natural que describa, por ejemplo, estructuras algebraicas u objetos combinatorios.