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 , …, an ) 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 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 sólo 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 solución en M también tiene 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 los cardenales grandes , incluido el rango dentro del rango .
Dos estructuras M y N de la misma firma σ son elementalmente equivalentes si cada oración de primer orden (fórmula sin variables libres) sobre σ es verdadera en M si y sólo si es verdadera en N , es decir, si M y N tienen la misma firma completa. Teoría de primer orden. Si M y N son elementalmente equivalentes , se escribe M ≡ N.
Una teoría de primer orden es 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 orden lineal denso ilimitado . Esto es suficiente para garantizar la equivalencia elemental, porque la teoría de los ordenamientos lineales densos ilimitados está completa, como puede demostrarse 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.
N es una subestructura elemental o un 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 ,…, an de N , φ ( a 1 , …, an ) se cumplen en N si y solo si se cumplen 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 firma σ 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 sólo 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 descendente de Löwenheim-Skolem proporciona una subestructura elemental contable para cualquier estructura infinita de primer orden con una firma contable como máximo; El teorema ascendente de Löwenheim-Skolem ofrece extensiones elementales de cualquier estructura infinita de primer orden de 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 resultar útil para construir una subestructura elemental de una estructura grande.
Sea M una estructura de firma σ y N una subestructura de M. Entonces N es una subestructura elemental de M si y sólo 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 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 ,
Cada incrustación elemental es un homomorfismo fuerte y su imagen es una subestructura elemental.
Las incorporaciones 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 cardinales grandes (ver también Punto crítico ).