En la teoría de modelos , una rama de la lógica matemática , dos estructuras M y N de la misma firma σ se denominan elementalmente equivalentes si satisfacen las mismas oraciones σ de primer orden .
Si N es una subestructura de M , a menudo se necesita una condición más fuerte. En este caso N se llama una subestructura elemental de M si cada fórmula σ de primer orden φ ( a 1 ,…, a n ) con parámetros a 1 ,…, a n de N es verdadera en N si y solo si es cierto en M . Si N es una subestructura elemental de M , entonces M se llama unextensión elemental de N . Una incrustación h : N → M se denomina incrustación elemental de N en M si h ( N ) es una subestructura elemental de M .
Una subestructura N de M es elemental si y solo si pasa la prueba de Tarski-Vaught : toda fórmula de primer orden φ ( x , b 1 ,…, b n ) con parámetros en N que tiene una solución en M también tiene una solución en N cuando se evaluó en M . Se puede demostrar que dos estructuras son elementalmente equivalentes a los juegos Ehrenfeucht-Fraïssé .
Estructuras elementalmente equivalentes
Dos estructuras M y N de la misma firma σ son elementalmente equivalente si cada frase de primer orden (fórmula sin variables libres) sobre σ es cierto en M si y sólo si es verdad en N , es decir, si M y N tienen el mismo completa teoría de primer orden. Si M y N son elementalmente equivalente, se escribe M ≡ N .
Una teoría de primer orden es completa si y solo si dos de sus modelos son elementalmente equivalentes.
Por ejemplo, considere el idioma con un símbolo de relación binaria '<'. El modelo R de números reales con su orden habitual y el modelo Q de números racionales con su orden habitual son elementalmente equivalentes, ya que ambos interpretan '<' como un ordenamiento lineal denso ilimitado . Esto es suficiente para asegurar la equivalencia elemental, porque la teoría de los ordenamientos lineales densos ilimitados es completa, como se puede demostrar con la prueba de Łoś-Vaught .
De manera más general, cualquier teoría de primer orden con un modelo infinito tiene modelos no isomórficos, elementalmente equivalentes, que pueden obtenerse mediante el teorema de Löwenheim-Skolem . Así, por ejemplo, existen modelos no estándar de aritmética de Peano , que contienen otros objetos además de los números 0, 1, 2, etc., y sin embargo son elementalmente equivalentes al modelo estándar.
Subestructuras elementales y extensiones elementales
N es una subestructura elemental de M si N y M son estructuras de la misma firma σ tal que para todas las fórmulas σ de primer orden φ ( x 1 ,…, x n ) con variables libres x 1 ,…, x n , y todos los elementos a 1 ,…, a n de N , φ ( a 1 ,…, a n ) se cumplen en N si y solo si se cumplen en M :
- norteφ ( a 1 ,…, a n ) si si Mφ ( a 1 ,…, a n ).
De ello resulta que N es una subestructura de M .
Si N es una subestructura de M , entonces ambos N y M pueden ser interpretadas como estructuras en la firma σ N que consiste en σ junto con un nuevo símbolo constante para cada elemento de N . Entonces N es una subestructura elemental de M si y solo si N es una subestructura de M y N y M son elementalmente equivalentes como σ N- estructuras.
Si N es una subestructura elemental de M , se escribe N M y dice que M es una extensión elemental de N : M N .
El teorema descendente de Löwenheim-Skolem da una subestructura elemental contable para cualquier estructura infinita de primer orden en la mayoría de firmas contables; el teorema ascendente de Löwenheim-Skolem da extensiones elementales de cualquier estructura infinita de primer orden de cardinalidad arbitrariamente grande.
Prueba de Tarski-Vaught
La prueba de Tarski-Vaught (o criterio de Tarski-Vaught ) es una condición necesaria y suficiente para que una subestructura N de una estructura M sea una subestructura elemental. Puede ser útil para construir una subestructura elemental de una estructura grande.
Deje que M sea una estructura de la firma σ y N una subestructura de M . Entonces N es una subestructura elemental de M si y solo si para cada fórmula de primer orden φ ( x , y 1 ,…, y n ) sobre σ y todos los elementos b 1 ,…, b n de N , si M x φ ( x , b 1 ,…, b n ), entonces hay un elemento a en N tal que M φ ( a , b 1 ,…, b n ).
Incrustaciones elementales
Una incrustación elemental de una estructura N en una estructura M de la misma firma σ es un mapa h : N → M tal que para cada fórmula σ de primer orden φ ( x 1 ,…, x n ) y todos los elementos a 1 , …, Una n de N ,
- norteφ ( a 1 ,…, a n ) si y solo si Mφ ( h ( a 1 ),…, h ( a n )).
Cada incrustación elemental es un fuerte homomorfismo , y su imagen es una subestructura elemental.
Las incrustaciones elementales son los mapas más importantes en la teoría de modelos. En la teoría de conjuntos , las incrustaciones elementales cuyo dominio es V (el universo de la teoría de conjuntos) juegan un papel importante en la teoría de los grandes cardinales (ver también Punto crítico ).
Referencias
- Chang, Chen Chung ; Keisler, H. Jerome (1990) [1973], Model Theory , Studies in Logic and the Foundations of Mathematics (3a ed.), Elsevier, ISBN 978-0-444-88054-3.
- Hodges, Wilfrid (1997), Una teoría de modelos más breve , Cambridge: Cambridge University Press , ISBN 978-0-521-58713-6.
- Monk, J. Donald (1976), Lógica matemática , Textos de posgrado en matemáticas, Nueva York • Heidelberg • Berlín: Springer Verlag, ISBN 0-387-90170-1