Límite de Fraïssé

En lógica matemática, específicamente en la disciplina de la teoría de modelos, el límite de Fraïssé (también llamado construcción de Fraïssé o amalgamación de Fraïssé) es un método utilizado para construir estructuras matemáticas (infinitas) a partir de sus subestructuras (finitas). Es un ejemplo especial del concepto más general de un límite directo en una categoría .​ La técnica fue desarrollada en la década de 1950 por su homónimo, el lógico francés Roland Fraïssé .​

El punto principal de la construcción de Fraïssé es mostrar cómo se puede aproximar una estructura ( contable ) por sus subestructuras generadas finitamente. Dada una clase $\mathbf {K}$ de estructuras relacionales finitas, si $\mathbf {K}$ satisface ciertas propiedades (descritas a continuación), entonces existe una estructura contable única $\operatorname {Flim} (\mathbf {K} )$, llamado límite de Fraïssé de $\mathbf {K}$, que contiene todos los elementos de $\mathbf {K}$ como subestructuras .

El estudio general de los límites de Fraïssé y las nociones relacionadas, a veces se denomina teoría de Fraïssé. Este campo ha visto amplias aplicaciones a otras partes de las matemáticas, incluida la dinámica topológica, el análisis funcional y la teoría de Ramsey .​

Subestructuras generadas finitamente y edad

Sea un lenguaje ${\mathcal {L}}$ . Por una ${\mathcal {L}}$ -estructura, nos referimos a una estructura lógica que tiene firma ${\mathcal {L}}$ .

Dada una ${\mathcal {L}}$ -estructura ${\mathcal {M}}$ con dominio $M$, y un subconjunto $A\subseteq M$, usamos $\langle A\rangle ^{\mathcal {M}}$ para denotar la menor subestructura de ${\mathcal {M}}$ cuyo dominio contiene $A$ (es decir, la cerradura de $A$ bajo todos los símbolos de funciones y constantes en ${\mathcal {L}}$ ).

Una subestructura ${\mathcal {N}}$ de ${\mathcal {M}}$ entonces se dice que es finitamente generada si ${\mathcal {N}}=\langle A\rangle ^{\mathcal {M}}$ para algún subconjunto finito $A\subseteq M$ ​. La edad de ${\mathcal {M}}$ , denotada $\operatorname {Age} ({\mathcal {M}})$, es la clase de todas las subestructuras generadas finitamente de ${\mathcal {M}}$ .

Se puede probar que cualquier clase $\mathbf {K}$ que es la edad de alguna estructura satisface las siguientes dos condiciones:

Propiedad hereditaria (HP)

Si $A\in \mathbf {K}$ y $B$ es una subestructura finitamente generada de $A$, entonces $B$ es isomorfo a alguna estructura en $\mathbf {K}$ .

Propiedad conjunta de incrustación (JEP)

Si $A,B\in \mathbf {K}$, entonces existe $C\in \mathbf {K}$ tal que ambos $A$ y $B$ son incrustrables en $C$ .

Teorema de Fraïssé

Un diagrama conmutativo que ilustra la propiedad de fusión.

Como antes, notamos que para cualquier ${\mathcal {L}}$ -estructura ${\mathcal {M}}$, $\operatorname {Age} ({\mathcal {M}})$ cumple con HP y JEP. Fraïssé demostró una especie de resultado inverso: cuando $\mathbf {K}$ es cualquier conjunto no vacío, contable de ${\mathcal {L}}$ -estructuras finitamente generadas que tiene las dos propiedades anteriores, entonces es la edad de alguna estructura contable.

Además, supongamos que $\mathbf {K}$ satisface las siguientes propiedades adicionales:

Propiedad de amalgamación (AP)

Para cualquier estructura $A,B,C\in \mathbf {K}$, tal que existen incrustaciones $f:A\to B$, $g:A\to C$, existe una estructura $D\in \mathbf {K}$ e incrustaciones $f':B\to D$, $g':C\to D$ tal que $f'\circ f=g'\circ g$ (es decir, coinciden sobre la imagen de A en ambas estructuras).

Contabilidad esencial (EC)

Salvo isomorfismo, hay una cantidad contable de estructuras numerables en $\mathbf {K}$ .

En ese caso, decimos que K es una clase de Fraïssé, y hay una única estructura $\operatorname {Flim} (\mathbf {K} )$ (módulo isomorfismo), que es contable, homogénea cuya edad es exactamente $\mathbf {K}$ .​ Esta estructura se denomina límite de Fraïssé de $\mathbf {K}$ .

Aquí, homogéneo significa que cualquier isomorfismo $\pi :A\to B$ entre dos subestructuras finitamente generadas $A,B\in \mathbf {K}$ puede extenderse a un automorfismo de toda la estructura.

Ejemplos

El ejemplo arquetípico es la clase $\mathbf {FCh}$ de todos los ordenamientos lineales finitos, para los cuales el límite de Fraïssé es un orden lineal denso sin extremos (es decir, sin elemento más pequeño ni más grande ). Salvo isomorfismo, siempre es equivalente a la estructura $\langle \mathbb {Q} ,<\rangle$, es decir, los números racionales con el orden habitual.

Como no ejemplo, tomemos en cuenta que ni $\langle \mathbb {N} ,<\rangle$ ni $\langle \mathbb {Z} ,<\rangle$ son el límite de Fraïssé de $\mathbf {FCh}$ . Esto se debe a que, aunque ambos son contables y tienen $\mathbf {FCh}$ como su edad, ninguno es homogéneo. Para ver esto, considere las subestructuras ${\big \langle }\{1,3\},<{\big \rangle }$ y ${\big \langle }\{5,6\},<{\big \rangle }$, y el isomorfismo $1\mapsto 5,\ 3\mapsto 6$ entre ellos. Esto no se puede extender a un automorfismo de $\langle \mathbb {N} ,<\rangle$ o $\langle \mathbb {Z} ,<\rangle$, ya que no hay ningún elemento al que podamos mapear $2$, sin dejar de preservar el orden.

Otro ejemplo es la clase $\mathbf {Gph}$ de todos los grafos finitos, cuyo límite de Fraïssé es el grafo de Rado .​

ω-categoricidad

Supongamos que nuestra clase $\mathbf {K}$ bajo consideración satisface la propiedad adicional de ser uniformemente localmente finito, lo que significa que para cada $n$, hay una cuota uniforme en el tamaño de una subestructura $n$-generada. Esta condición es equivalente al hecho que el límite de Fraïssé de $\mathbf {K}$ es ω-categórico .​

Por ejemplo, la clase de espacios vectoriales de dimensión finita sobre un campo fijo es siempre una clase de Fraïssé, pero es uniformemente localmente finita solo si el campo es finito.

Véase también

• Teoría estructural de Ramsey
• Construcción de Hrushovski