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 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 verdadera en M . Si N es una subestructura elemental de M , entonces M se llama extensión elemental de N . Una incrustación h : N → M se llama 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 evalúa en M . Se puede demostrar que dos estructuras son elementalmente equivalentes con los juegos de Ehrenfeucht–Fraïssé .
Las incrustaciones elementales se utilizan en el estudio de cardinales grandes , incluido el rango dentro de rango .
Dos estructuras M y N de la misma signatura σ son elementalmente equivalentes si cada enunciado de primer orden (fórmula sin variables libres) sobre σ es verdadero en M si y solo si es verdadero en N , es decir, si M y N tienen la misma teoría completa de primer orden. Si M y N son elementalmente equivalentes, se escribe M ≡ N .
Una teoría de primer orden está completa si y sólo si dos de sus modelos son elementalmente equivalentes.
Por ejemplo, considere el lenguaje 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 está completa, como se puede demostrar mediante la prueba de Łoś–Vaught .
En términos más generales, cualquier teoría de primer orden con un modelo infinito tiene modelos no isomorfos, elementalmente equivalentes, que pueden obtenerse mediante el teorema de Löwenheim-Skolem . Así, por ejemplo, existen modelos no estándar de la 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.
N es una subestructura elemental o submodelo elemental de M si N y M son estructuras de la misma firma σ tales 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 cumple en N si y solo si se cumple en M :
Esta definición aparece por primera vez en Tarski, Vaught (1957). [1] De ello se deduce que N es una subestructura de M .
Si N es una subestructura de M , entonces tanto N como M pueden interpretarse como estructuras en la signatura σ N que consisten 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 se dice que M es una extensión elemental de N : M N .
El teorema de Löwenheim-Skolem descendente proporciona una subestructura elemental contable para cualquier estructura infinita de primer orden con una firma contable como máximo; el teorema de Löwenheim-Skolem ascendente proporciona extensiones elementales de cualquier estructura infinita de primer orden con una cardinalidad arbitrariamente grande.
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.
Sea M una estructura de signatura σ 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 ).
Una incrustación elemental de una estructura N en una estructura M de la misma firma σ es una función h : N → M tal que para cada σ -fórmula de primer orden φ ( x 1 , …, x n ) y todos los elementos a 1 , …, a n de N ,
Toda incrustación elemental es un homomorfismo fuerte , y su imagen es una subestructura elemental.
Las incrustaciones elementales son las aplicaciones 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) desempeñan un papel importante en la teoría de cardinales grandes (véase también Punto crítico ).
