Teoría de modelos finitos

Question

Parece que teoría modelo finita es considerado (en un sentido) como un tema teórico del equipo. ¿Este es el caso o hay preguntas de interés que son de interés para los logicians matemáticos o más bien teórico de modelo? Y si es así ¿cuál sería un buen lugar para aprender acerca de ellos?

Answer 1

Como usted sabe, la frase "Finito Modelo de la Teoría de la" generalmente se refiere a un campo de las matemáticas que tiene más que ver con ciencias de la computación de modelo de la teoría. Los libros por Ebbinghaus y Flum, Libkin, etc. son un buen recurso para este material.

Recientemente, sin embargo, algunos modelos teóricos han ido tomando un mayor interés en el modelo de la teoría de la finitos de estructuras, especialmente donde las conexiones con las ideas de la moderna (post-Clasificación Teoría) modelo de la teoría son posibles. Un buen ejemplo de esto es Hrushovski del trabajo en pseudo-dimensiones finitas, que se inició en su aproximado subgrupos de papel y se concretará en este documento (detrás de un paywall, lo siento). La idea es que la cuenta de la medida en una clase de finito de estructuras pueden ser elevados a dar nociones de dimensión y medida en los modelos de la teoría de su ultraproduct. Esto permite que las ideas de "geométrica" modelo de la teoría para ser utilizado en el contexto de la pseudo-finito teorías, y, a veces, uno puede demostrar que las cosas en la combinatoria finita por medio de la pseudo-límite finito (ver, por ejemplo, el Tao del post en el algebraicas regularidad lexema, o, más en general, de la filosofía, "Ultraproducts como un Puente Entre los Discretos y Continuos Análisis").

Hay un trabajo muy reciente de García, Macpherson, y Steinhorn (que creo que aún no se ha escrito todavía), el uso de pseudo-dimensiones finitas para dar condiciones suficientes para la estabilidad, la sencillez, la supersimplicity, etc. de pseudo-finito teorías.

Macpherson y Steinhorn también han trabajado en dos contextos, llamado "asintótico de clases" y "robusto clases", en la cual las propiedades de una clase de finito de estructuras permiten establecer conexiones con el infinitary modelo de la teoría de sus límites. Aquí está una encuesta de estas ideas.

Usted puede estar interesado en el trabajo de Cameron Hill, especialmente este papel, que (entre otras cosas) se aborda la cuestión de cuándo la teoría de un Fraïssé límite es súper sencilla.

Con respecto a cero-una de las leyes, ciertamente, no todo es conocido. Hay una buena encuesta del estado de la técnica en 1989... bueno, es un buen lugar para empezar) por Kevin Compton llamado "0-1 Leyes de la Lógica y de la Combinatoria" (paywall de nuevo, suspiro).

He aquí un ejemplo de un muy interesante abrir cero-uno de la ley (que tiene que ver con finitely presentado estructuras, no finitos de estructuras, pero aún así es muy interesante!): Considere la posibilidad de la reproducción aleatoria de grupo modelo $G(n,r,l) = \langle x_1,\dots,x_n \mid w_1,\dots,w_r\rangle$ donde $w_1,\dots,w_r$ son relaciones de longitud $l$ elegido uniformemente al azar de todos reducido de palabras de longitud $l$ en los generadores $x_1,\dots,x_n$. Julia Caballero conjeturó que para cualquier $n\geq 2$$r\geq 0$, en el límite de $l\rightarrow\infty$, 1. el $G(n,r,l)$ satisfacer un cero a la ley y 2. el casi seguro de que la teoría es la teoría de los grupos gratis en $n$ generadores. Ambas hipótesis están abiertas.

Si usted está interesado en grupos finitos, también puede echar un vistazo a estas mathoverflow preguntas: ¿hay un 0-1 de la ley para la teoría de grupos? (y los enlaces de matemáticas stackexchange pregunta) y la Densidad de primer orden conjuntos definibles en la dirigida unión de grupos finitos.

Algo que me interesa mucho es el fenómeno que en muchos ejemplos interesantes de la cero-una ley para una clase de finito de estructuras, cuando existe, coincide con la teoría de la Fraïssé límite de esta clase. Por supuesto, hay ejemplos en los que estas teorías existen, pero son diferentes, pero a veces, esto puede ser solucionado mediante la sustitución de la Fraïssé límite con un Hrushovski de la construcción (véase, por ejemplo, Baldwin y Sela, "la Aleatoriedad y la semigenericity"). A mi conocimiento, no hay ninguna que cumpla la comprensión de este fenómeno en general.

Sin duda hay mucho más que decir, pero este ya es bastante largo, y yo no tenía la intención de escribir un estudio exhaustivo. Espero que algunas de estas cosas despertar su interés.

Answer 2

Me parece recordar haber escuchado que si $\varphi$ es una primera sentencia de orden, entonces el límite como $n\to\infty$ de la probabilidad que $\varphi$ es cierto en modelos de tamaño $n$ debe ser bien $0$ o $1$. Me parece que puedan interesar más científicos de la computación.