Límites de las estructuras finitas - lógica de primer orden

Question

Suponga que $\mathcal{C}=\{M_i:i\in I\}$ es una colección infinita de diferentes finito $\mathcal{L}$-estructuras de primer orden lenguaje $\mathcal{L}$. La pregunta es:

1. ¿Qué tipo de infinito "límites" nos puede producir a partir de la clase $\mathcal{C}$?
2. ¿Qué tipo de "transferencia principios" son válidas para los diferentes límites que podemos tomar.
3. ¿Qué ventajas podría existir trabajando en el límite de $\mathcal{M}$, en lugar de trabajar directamente en la clase $\mathcal{C}$.

Tal vez el ejemplo prototípico es el ultraproduct de la construcción, en el que la transferencia principio es Łoś del Teorema y tiene la ventaja de que, entre otras cosas, de ser un infinito estructura y también está equipado con una cierta noción de la medida de conjuntos definibles.

Sin embargo, he oído también sobre profinite estructuras (inverso de los límites finitos de estructuras), y sobre Fraïssé límites, entre otros. Pero no estoy seguro de cuáles son sus principales propiedades, o si existe algún tipo de transferencia de principio (tal vez sólo por algún tipo de fórmulas). Agradecería si alguien puede dar alguna información o de referencia a la vista.

La respuesta final sería una completa clasificación de los posibles límites junto con sus propiedades, pero, por supuesto, entiendo que tal cosa sólo podía existir en el mundo platónico. Por lo tanto, cualquier respuesta parcial será apreciado así.

Answer 1

Ya que la pregunta es bastante amplia, la respuesta puede ser un poco trivial, pero hay ejemplos más interesantes dada posteriormente, con la debida referencia.

Vamos a tomar una convergencia de la secuencia de $(M_n) \to \mathcal{M}$ (todo lo que sigue se aplica también a las secuencias aleatorias). Para definir con precisión lo que la convergencia decir, vamos a definir la métrica $$d_{FO}(M_1,M_2) = \begin{cases} 2^{-\min(q(\varphi))} & \mbox{for } M_1 \models \varphi \wedge M_2 \not\models \varphi\\ 0 & \mbox{otherwise}\\ \end{casos}$$ (donde $q(\varphi)$ es el cuantificador de la profundidad de la fórmula). Así que este indicador depende de la más pequeña fórmula de la separación de las dos estructuras. Supongamos que hemos definido correctamente nuestro espacio de modo que tenemos como costumbre que una sucesión es convergente si es de Cauchy. Dos estructuras son elementarily equivalente si son a distancia $0$. Desde finitos de estructuras son categóricos, la clase de equivalencia de todos los finitos de estructuras son los únicos, pero las clases de equivalencia de infinito estructuras pueden ser infinitas. Llame a un infinito estructura de una $*$-límite si se puede obtener como el límite de una convergencia de la secuencia de finito de estructuras.

Ahora, las consecuencias de estas definiciones:

(1). Todos los $*$-límites de lo finito modelo de propiedad (FMP). Sin embargo, la caracterización de las teorías con la FMP es una tarea difícil.

(2). Asimismo, mediante la definición de $\mathcal{M} \models \varphi$ implica que existe un $i$ tal que para todo $n>i$, $M_n \models \varphi$. Obtener una estimación de $i$ depende de la velocidad de convergencia.

(3). Supongo que te refieres a ¿cuál es la ventaja de trabajar en $\mathcal{M}$ en lugar de $(M_n)$. Bueno, si usted no tiene estimaciones sobre la tasa de convergencia, si usted tiene $M_i \models \varphi$, no sabe si no es una anomalía porque usted tomó una demasiado pequeña estructura. Así que algunas de las pruebas que podrían funcionar mejor en el límite, ya que puede estar libre de tales artefactos. Sin embargo todos los que no son de primer orden de los parámetros (por ejemplo, la conexión) no son continuas, con el límite, por lo que no puede ser exacta a utilizar para todas las estimaciones.

Un ejemplo interesante (o más bien un contra-ejemplo), el vínculo entre la Fraïssé límites y de una clase de finito de estructuras es la clase de triángulo libre de los gráficos. El límite de la secuencia de $(T_n)$ donde $T_n$ es la distribución uniforme en todo triángulo-gráficos gratuitos en $n$ vértices, es $\mathcal{B}$, el bipartito equivalente a la Rado gráfico. Esto sucede debido a que casi todos triángulo-gráficos gratuitos son bipartitas. Sin embargo, la Fraïssé límite del triángulo libre de los gráficos no es bipartito, por lo que no hay transferencia de principio a todos. Esto contrasta fuertemente con la clase de todos los gráficos y el Rado gráfico. Ver los detalles, las pruebas y las maravillas [0].

Para una clasificación de todos los posibles límites... hay un montón de ellos, ¿verdad? Sin embargo, hay algunos interesantes resultados de más alcance restringido. Demasiado como para dar una overwiew aquí, pero podemos tener dos ejemplos interesantes. Hay una clasificación de reducts de la Rado gráfico [1], o Ove Ahlman del trabajo [2], que precisamente el estudio de la clase de estructuras que pueden ser obtenidos de los límites de las secuencias (con algunas otras hipótesis).

[0] Kolaitis, Promel, Rothschild, "$K_{l+1}$libre de gráficos: asintótica estructura y un 0-1 de la ley", Trans. Amer. De matemáticas. Soc., 303 (1987).

[1] Simon Thomas, "Reducts del Azar Gráfico", J. de la Lógica Simbólica 56 (1991).

[2] Ove Ahlman, "estructuras Simples axiomatized por casi seguro de teorías", Anales de la Pura y Aplicada de la Lógica 167 (2016).