Hay un Leibniziana modelo sin definibles elementos, en un lenguaje finito?

Question

Un primer orden de la estructura de $M$ es Leibniziana, si alguna de las dos distintas elementos de la $a,b\in M$ satisfacer las diferentes $1$-tipos; es decir, si hay es una fórmula $\varphi$ tal que $M\models\varphi(a)$ y $M\models\neg\varphi(b)$. Por lo tanto, un Leibniziana modelo es aquel en el que se pueden distinguir dos elementos de propiedades se pueden expresar en el lenguaje, o dicho de otra manera, un Leibniziana modelo es uno en el que indiscernibles son idénticos.

En contraste, una estructura $M$ es pointwise definibles, si cada elemento individual $a\in M$ es definible en $M$, por lo que no es algunas fórmula $\varphi(x)$ que está satisfecho en $M$ sólo en $x=a$.

Cada pointwise definibles por el modelo es Leibniziana, por supuesto, ya que los elementos se pueden distinguir por sus características definitorias. Pero en general, los conceptos son distintos:

• Un Leibniziana modelo con no definible elementos (idioma infinito). En el lenguaje infinitamente muchos constante de símbolos $c_0,c_1,\ldots$, considere la posibilidad de un modelo de $M$ interpretación de todos ellos de manera diferente y tener exactamente un punto adicional, que no es la interpretación de cualquier constante. Este modelo es Leibniziana, ya que para cualesquiera dos puntos, uno de ellos es una de las constantes y por lo tanto definibles. Pero el único punto extra no es definible en $M$, debido a que cualquier fórmula $\varphi$ utiliza sólo un número finito de la constante de símbolos, y por lo tanto no se puede definir ese punto, porque en el reducto del modelo para el lenguaje de $\varphi$, hay automorfismos que permutar todos los puntos en los que no se nombran por un constante en $\varphi$. Tenga en cuenta que la mayoría de los elementos de este modelo son definibles. (Alternativamente, uno podría tener una primaria la extensión de la modelo y tenga en cuenta que todos los sin nombre puntos ser automorphic.)

• Un Leibniziana modelo sin definibles elementos (idioma infinito). Considere la posibilidad de la modelo $\langle 2^\omega,U_s\rangle_{s\2^{<\omega}}$, donde el dominio Cantor espacio de $2^\omega$, el conjunto de todas las infinitas secuencias binarias, y el predicado $U_s(z)$ tiene exactamente al $z$ comienza con el finito cadena de $s$. Así que este es el Cantor espacio con los predicados básicos abierto conjuntos. El modelo es Leibniziana, desde cualquiera de los dos distintos $y,z$ en el espacio de Cantor no debe estar de acuerdo en algunos $U_s$. Pero el modelo no tiene definidos los elementos del todo, ya que cualquier fórmula $\varphi(x)$ utiliza sólo un número finito de predicados $U_s$, y la reducción de la modelo para que el idioma tiene numerosos automorfismos sin fijo puntos: uno puede cambiar de bits en cualquier coordinar más allá de la duración de cualquier $s$ que aparece en el $\varphi$.

• Un Leibniziana modelo con no definible elementos(finito el lenguaje). Considerar la lengua con una única función símbolo $S$, y la forma de la CandyLand modelo (llamado así por Arden Koehler), que ha una piruleta de cada tamaño finito, además de una infinita palo de piruleta. Más precisamente, el modelo ha infinitamente muchos de la base de elementos de punto de $x_1,x_2,x_3,\ldots$ más uno más $x_\infty$, de tal manera que ninguno de ellos está en el rango de $S$, y además, la función de $S$ que se aplica a la base del punto de $x_n$ itera exactamente $n$ pasos antes de encontrar un punto fijo, y donde $S^k(x_\infty)$ nunca se repite. $$x_1\neq S(x_1)=S^2(x_1),\qquad x_n\neq S^k(x_n)\neq S^n(x_n)=S^{n+1}(x_n)\quad(k<n)$$ So $x_n$ is the base of a size $$ n lollipop. Tenga en cuenta que cada elemento en un número finito de lollipop es definible por el número de veces que $S$ se puede aplicar a la inversa y el número de iteración necesarias para alcanzar el punto fijo. Así que los puntos pueden ser distinguirse de cualquier otro en el modelo; y cualquiera de los dos distintos los puntos en el infinito lollipop se pueden distinguir por sus la altura, el número de veces $S$ puede ser revertido a partir de ellos. Por lo que el el modelo es Leibniziana. Pero mientras tanto, ninguno de los elementos en la infinito lollipop es definible. Para ver esto, utilice un compacidad/arriba Löwenheim-Skolem argumento para encontrar un primaria de la extensión de $M$ que tiene al menos un adicional infinito lollipop con un punto de base y, a continuación, tenga en cuenta que los dos infinito paletas son automorphic, y así no contienen definibles elementos. (Alternativamente, uno puede mostrar que la estructura de la admite eliminación de cuantificadores abajo a la lengua de $S$ juntos con los predicados $H_n(x)$ que afirman que $x$ tiene la altura $n$, lo que significa que $S$ puede ser invertida exactamente $n$ veces, pero no más de $x$, pero no cuantificador libre afirmación en este idioma puede definir el punto de partida de la piruleta infinita.)

Mi pregunta es si se puede tener todo:

Pregunta. Hay una primera estructura de orden $M$ en un número finito de el lenguaje, tal que $M$ es Leibniziana, pero no tiene definibles elementos?

Tener un ejemplo elemental, sería de ayuda para aclarar un cierto problema en el que Arden Koehler, un estudiante de posgrado en mi seminario de este semestre, es escrito.

Answer 1

Aquí está un ejemplo diferente.

Para cualquier irracional $a$, puesto $\mathcal M_a=\langle\mathbb Q,<,M,I_a\rangle$, donde \begin{align*} M(x,y,z)&\iff y=\frac{x+z}2,\\ I_a(x)&\iff a<x<a+1. \end{align*}

En $\mathcal M_a$, podemos definir el intervalo de $(a,a+1/2)$ por la fórmula $$I_a(x)\land\forall u,v\,\bigl(I_a(u)\land u<x\land M(u,x,v)\to I_a(v)\bigr).$$ Por la iteración de este proceso, podemos definir los intervalos de $(a,a+2^{-k})$ por cada $k\in\omega$, y luego nos puede girar en torno al uso del $M$ a definir cada intervalo de $\bigl(a+n2^{-k},a+(n+1)2^{-k}\bigr)$ con $n\in\mathbb Z$. Por lo tanto,

La proposición: $\mathcal M_a$ es Leibniziana.

Con el fin de descartar definibles elementos, vamos a necesitar

Reclamo: Para todos los irracionales $a,b$, las estructuras de la $\mathcal M_a$ e $\mathcal M_b$ son elementarily equivalente.

Corolario: $\mathcal M_a$ no tiene definidos los elementos.

Prueba: Supongamos por contradicción que $u$ es definible en $\mathcal M_a$ por una fórmula $\phi(x)$. A continuación, en $\mathcal M_{a'}$, $\phi$ define un elemento $u'$. Ya hemos visto anteriormente que para cualquier $k,n$, hay una fórmula que define a $\bigl(a+n2^{-k},a+(n+1)2^{-k}\bigr)$ en $\mathcal M_a$, e $\bigl(a'+n2^{-k},a'+(n+1)2^{-k}\bigr)$ en $\mathcal M_{a'}$, debemos tener $u'-u=a'-a$. Sin embargo, esto es imposible si elegimos $a'$, de modo que $a'-a$ es irracional. QED

Queda por demostrar que el reclamo. Observar:

1. $\mathcal M_a$ es isomorfo a $\mathcal M_b$ a través de un turno, si $b-a$ es racional.

2. $\mathcal M_a$ es definible en la estructura de la $\langle\mathbb Q+a\mathbb Q,<,+,\mathbb Q,1,a\rangle$.

El efecto de 1 a 2 es que podemos elegir el cero de los elementos del grupo para ser arbitrariamente cerca de $a$, por lo tanto, por la compacidad, podemos encontrar una estructura $\langle G,+,<,H,1,a\rangle$ tal que

(a) $\langle G,+,<\rangle$ es totalmente ordenado divisible grupo abelian $G$, e $H$ es su propio divisible densa subgrupo;

(b) $1\in H$, $a\in G\smallsetminus H$, $0<a<1$, y $a$ es infinitesimalmente pequeña con respecto a las $1$;

(c) $\langle H,<,M,(a,a+1)\cap H\rangle$ es una primaria de la extensión de $\mathcal M_a$.

Es bien sabido que la teoría descrita en (a) es completo y dispone de eliminación de cuantificadores, por tanto, también (a)+(b) presenta una teoría completa. Pero luego (c) implica que la teoría de la $\mathcal M_a$ es independiente de $a$.

Answer 2

Creo que una variante de su segundo ejemplo funciona. Deje $S$ (= unario función) ser el (la izquierda) de turno, y definir $P$ (= unario relación) declarando $Px$ a si $x_0=0$.

A continuación, $\varphi(x) = PS^n x$ adecuado $n$ va a distinguir dos puntos, pero no podemos definir secuencias individuales desde un primer orden de la fórmula sólo se habla de un número finito de sus elementos.

Actualización: Si queremos incluir la igualdad en nuestro idioma, me propongo tomar una densa (en $\{ 0, 1\}^{\mathbb Z}$) en órbita de dos caras secuencias como nuestro universo. A continuación, el argumento original para no definability por la eliminación de cuantificadores, como se sugiere en los comentarios de abajo, todavía va a través. El argumento es muy fácil y sencillo en principio, pero bastante aburrido (para mí) para escribir, así que permítanme simplemente ilustrar el punto crucial algo de manera informal. Permítanme introducir también el único símbolo de función $T$, interpretado como shift derecha (esto no es realmente necesario, pero si no tengo $T$ disponible, voy a utilizar un cuantificador para expresar $T$ en términos de $S$, por lo que no soy, literalmente, la eliminación de todos los cuantificadores).

Desde que me puede traer un cuantificador libre $\varphi$ a DNF, el paso clave es mirar $$ \existe y \left(\varphi_1(\overline{x},y)\de la tierra \ldots\de la tierra \varphi_n(\overline{x},y)\right) , $$ donde el $\varphi_j$ son literales (atómica o negado atómica). Permítanme ilustrar con un ejemplo: $$ \existe z \left( x_0=0\tierra y_3=0 \tierra z_0=1 \de la tierra Sz=x\tierra z=S^2y\de la tierra S^2z\no= y\right) $$ Observe que una igualdad que determina una variable en términos de la otra ya que estoy en una sola órbita. Comience por el uso de todas las igualdades que involucran $z$ a expresar $z$ en términos de las otras variables. Esto podría muestran ya que la fórmula es unsatisfiable. Si no, buscar contradicciones entre las igualdades y desigualdades. Si no aparece nada, las desigualdades que implican $z$ puede ser eliminado porque se puede entonces siempre será satisfecho por el cambio de los componentes del resto de la fórmula no hablar. Ahora todo lo que se le pide a $z$ se puede decir en términos de $x,y$, y el cuantificador ha sido eliminado. En mi ejemplo, este procedimiento da $$ x_0=0\tierra y_3=0\tierra x_{-1}=1\de la tierra y_2=1 \de la tierra x=S^3 y $$ (que yo podría, por supuesto, simplificar aún más por la caída de la segunda y cuarta conjuntos, pero esto no es necesario para el argumento general).

Actualización 2: James ejemplo (Joel versión) y la mía (la versión actualizada) en realidad están estrechamente relacionados. Joel estructura del es $\mathcal J=(\mathbb Z, <, A)$, y la mía es $\mathcal C=(\mathbb Z, S, P)$, después de la identificación de $S^na$ con $n$. El siguiente se tiene: si un elemento de $\mathcal C$ es definible, a continuación,$\mathcal J$, con $An\iff a_n=0$, también tiene un definibles por el elemento.

Para mostrar esto, supongamos que $\varphi(x)$ define $n$ en $\mathcal C$. Ahora puedo simplemente traducir lo $\varphi$ dice en el lenguaje de la $\mathcal J$, como sigue: sustituir cada ocurrencia de $S^n y$ en $\varphi$ por $\exists z \textrm{''$z$ is the $n$th successor of y''}$, y el cambio de $y$ a $z$ en este subformula de $\varphi$. Reemplazar de forma similar, $PS^n y$ por $AS^n y$ (y en el futuro a traducir $S^ny$ como se acaba de describir). A continuación, la nueva fórmula $\widetilde{\varphi}(x)$ definiría el mismo punto de $n$ en $\mathcal J$.

Answer 3

$\newcommand\Z{\mathbb{Z}}\newcommand\P{\mathbb{P}}$Aquí es una simple cuenta de una gran clase de ejemplos.

Teorema. Con probabilidad uno, la estructura $\langle\Z,<,A\rangle$ es Leibniziana y no tiene definibles elementos, donde $<$ es el orden usual de los números enteros y $A\subset\Z$ es un predicado unario elegido al azar con respecto a el que tira la moneda la probabilidad de medir.

Prueba. Casi seguramente, de un azar del predicado $A\subset\Z$ no es periódico (desde que se pone infinitamente muchos independiente de posibilidades para violar el patrón de cualquier período de tiempo determinado), y de un no-periódico $A$, la estructura de $\langle\Z,<,A\rangle$ es Leibniziana, porque con cualquier $n\in\Z$ como parámetro, podemos definir todos los otros $m\in\Z$ como un cierto número de pasos por encima o por debajo de $n$, y así ya que por el incumplimiento de la periodicidad con que el patrón de $A$ por encima y por debajo de $n$ será diferente que el correspondiente patrón de $A$ por encima y a continuación $m$, y este será un expresable propiedad distintiva $n$ e $m$. Así que con probabilidad uno, la estructura de $\Z_A$ es Leibniziana.

Del mismo modo, casi con toda seguridad, $\langle\Z,<,A\rangle$ ha no definible elementos. La idea básica (señalado por Emil en los comentarios) es que si $\varphi$ define $n$ con probabilidad positiva $\epsilon>0$, luego dado que la medida es la traducción de todos los idiomas, se sigue que $\varphi$ define cualquier $m$ con la misma probabilidad $\epsilon$. Considerando más de $1/\epsilon$ muchos puntos, nos habría una probabilidad positiva de que dos puntos distintos ambos definidos por la misma fórmula, la cual es una contradicción.

(Tenga en cuenta que para cualquier fórmula $\varphi$ en el idioma y en cualquier enteros $\vec n$, el conjunto de predicados $A\subset\Z$ para los que $\langle\Z,<,A\rangle\models\varphi(\vec n)$ es de hecho un medibles establecido en la probabilidad de espacio, ya que esto es verdad en el caso de un átomo de fórmulas, y los cuantificadores de $\varphi$ cantidad contables de uniones e intersecciones. Por lo tanto, la pregunta de si una determinada fórmula $\varphi$ define $n$ tiene algunos la probabilidad.) QED

Mi post anterior mostró que si $A\subset\Z$ es aritméticamente genérico, a continuación, $\langle\Z,<,A\rangle$ es Leibniziana y no tiene definibles elementos. La razón era que (i) es Leibniziana, porque $A$ es no periódico; y (ii) si $\varphi$ definido $n$, a continuación, algunos finito condición de $A\cap[-m,m]$ obligaría a esta situación; pero desde que finito patrón podría también surgir en otros lugares en $A$, tendríamos una traducción de $\pi(A)$ también extender esa condición, y así nos habrían $\varphi$ definición de $\pi^{-1}(n)$ como bueno, un contradicción.

MathOverflow colaboración es grande, debido a que el original, el azar, la idea apareció en Santiago de la respuesta, que luego de verificado con el forzamiento de la argumentación y, a continuación, Emil vio cómo hacer fácilmente con un elemental argumento de probabilidad. Y Cristiano es proponer otro argumento con esta estructura, que puede simplificar más las cosas.

Answer 4

Es solo una idea:

Considerar el lenguaje con dos sugestivo nombre de tipo, $\mathbb{Z}$ e $\mathcal{P}(\mathbb{Z})$, una relación binaria símbolo $\leq$ (de tipo $\mathbb{Z} \times \mathbb{Z}$), y dos binarios relación símbolos $\in^*$ e $R$ tipo $\mathbb{Z}\times\mathcal{P}(\mathbb{Z})$

Se construye un modelo de la siguiente manera. Sea f una "random" la función del poder conjunto de los números naturales a los números naturales. Nos pueblan la especie $\mathbb{Z}$ con los números enteros, la interpretación de $\leq$ como su orden habitual. Nos pueblan la especie $\mathcal{P}(\mathbb{Z})$, con una contables de la colección de `al azar" de los subconjuntos de los números enteros (por ejemplo, elegido por la moneda para decidir). Podemos entonces interpretar R $\{(f(X),X) | X \in \mathcal{P}(\mathbb{Z})\}$, e $\in^*$ as $\{(n-f(X),X) | n \in X\}$. Básicamente, $\in^*$ es el estándar elemento de la relación después de un cambio aleatorio de X.

La razón de esto se debe Leibniziana es como sigue:

• Si dos elementos n,m de la especie $\mathbb{Z}$ no son iguales, entonces `con una probabilidad de 1" hay un elemento X de la especie $\mathcal{P}(\mathbb{Z})$ tal que $n \in^* X$ pero $m \not\in^* X$
• Con probabilidad 1, no hay dos elementos X,Y de la especie $\mathcal{P}(\mathbb{Z})$ se desplaza de uno a otro, por lo que se pueden distinguir por alguna fórmula.

También es claro que los elementos deben ser definibles (a menos que estemos muy mala suerte).

EDIT: Como JDH puntos, el primer punto estaba equivocado!

Aquí es un poco más complicado) ejemplo de que funciona (creo):

Considerar el lenguaje con dos tipos, $\mathbb{Z}_1$ e $\mathbb{Z}_2$, binario relación símbolos $\leq_i$ (de tipo $\mathbb{Z}_i \times \mathbb{Z}_i$) (i = 1,2), y dos binarios relación símbolos $=^*$ e $R$ tipo $\mathbb{Z}_1\times \mathbb{Z}_2$

Se construye un modelo de la siguiente manera. Sea f una "random" bijection de la de los enteros a los enteros. Nos pueblan el tipo $\mathbb{Z}_i$ con los números enteros, la interpretación de $\leq_i$ como su orden habitual. Podemos entonces interpretar R $\{(f(n),n) | n \in \mathbb{Z}\}$, e $=^*$ as $\{(n-f(n),n) | n \in \mathbb{Z}\}$. Básicamente, $=^*$ es el estándar de la relación de igualdad en los enteros, después de un cambio aleatorio de la izquierda de la entrada.

La razón de esto se debe Leibniziana es como sigue:

• Si dos elementos n,m de la especie $\mathbb{Z}_2$ no son iguales, considere la posibilidad de grande k el tipo de orden de 2k+1-tupla (f(n-k),f(n-k-1),...,f(n),....,f(n+k)). Este tiene una baja probabilidad de ser igual al tipo de la orden de los 2k+1 tupla (f(m-k),f(m-k-1),...,f(m),....,f(m+k)) Ahora tomar k para $\infty$

• Aplicar un argumento similar a $n \neq m$ de la clase $\mathbb{Z}_1$ comparando el tipo de orden de los 2k+1 tuplas (f^{-1}(n-k),....,f^{-1}(n+k)) y (f^{-1}(m-k),....,f^{-1}(m+k))

Es también plausible, al menos, de que no hay elementos deben ser definibles (a menos que estemos muy mala suerte). La idea es que, si nos limitamos a $\leq_1$ e $\leq_2$, nos acaba de obtener dos copias disjuntas de los números enteros como un conjunto ordenado (así, sin elementos son definibles por el uso de estos por sí solos). También esperamos al azar bijection de los enteros a enteros para repetir cualquier finito patrón de comportamiento infinitamente a menudo. (Tengo que admitir que esto es más un argumento heurístico).