En la teoría de modelos , una rama de la lógica matemática , una clase elemental (o clase axiomatizable ) es una clase que consiste en todas las estructuras que satisfacen una teoría fija de primer orden .
Una clase K de estructuras de una signatura σ se denomina clase elemental si existe una teoría de primer orden T de signatura σ, tal que K consiste en todos los modelos de T , es decir, en todas las σ-estructuras que satisfacen T . Si T puede elegirse como una teoría que consiste en una única oración de primer orden, entonces K se denomina clase elemental básica .
De manera más general, K es una clase pseudoelemental si existe una teoría de primer orden T de una firma que extiende σ, tal que K consiste en todas las σ-estructuras que son reducciones a σ de modelos de T . En otras palabras, una clase K de σ-estructuras es pseudoelemental si y solo si existe una clase elemental K' tal que K consiste precisamente en las reducciones a σ de las estructuras en K' .
Por razones obvias, las clases elementales también se denominan axiomatizables en lógica de primer orden , y las clases elementales básicas se denominan finitamente axiomatizables en lógica de primer orden . Estas definiciones se extienden a otras lógicas de la manera obvia, pero dado que el caso de primer orden es, con mucho, el más importante, axiomatizable se refiere implícitamente a este caso cuando no se especifica ninguna otra lógica.
Si bien lo anterior es hoy en día la terminología estándar en la teoría de modelos "infinitos" , las definiciones anteriores ligeramente diferentes aún se utilizan en la teoría de modelos finitos , donde una clase elemental puede llamarse una clase Δ-elemental , y los términos clase elemental y clase axiomatizable de primer orden se reservan para las clases elementales básicas (Ebbinghaus et al. 1994, Ebbinghaus y Flum 2005). Hodges llama a las clases elementales clases axiomatizables , y se refiere a las clases elementales básicas como clases definibles . También utiliza los sinónimos respectivos clase EC y clase EC (Hodges, 1993).
Existen buenas razones para esta terminología divergente. Las firmas que se consideran en la teoría general de modelos suelen ser infinitas, mientras que una sola oración de primer orden contiene solo un número finito de símbolos. Por lo tanto, las clases elementales básicas son atípicas en la teoría de modelos infinitos. La teoría de modelos finitos, por otro lado, trata casi exclusivamente con firmas finitas. Es fácil ver que para cada firma finita σ y para cada clase K de σ-estructuras cerradas bajo isomorfismo hay una clase elemental de σ-estructuras tales que K y contienen precisamente las mismas estructuras finitas. Por lo tanto, las clases elementales no son muy interesantes para los teóricos de modelos finitos.
Es evidente que toda clase elemental básica es una clase elemental, y toda clase elemental es una clase pseudoelemental. Además, como consecuencia sencilla del teorema de compacidad , una clase de σ-estructuras es elemental básica si y solo si es elemental y su complemento también es elemental.
Sea σ una firma que consiste únicamente en un símbolo de función unaria f . La clase K de σ-estructuras en las que f es biyectiva es una clase elemental básica. Esto lo atestigua la teoría T , que consiste únicamente en la oración única
Sea σ una signatura arbitraria. La clase K de todas las σ-estructuras infinitas es elemental. Para ver esto, considere las oraciones
y así sucesivamente. (Entonces la oración dice que hay al menos n elementos.) Las infinitas σ-estructuras son precisamente los modelos de la teoría.
Pero K no es una clase elemental básica. De lo contrario, las σ-estructuras infinitas serían precisamente aquellas que satisfacen una cierta oración de primer orden τ. Pero entonces el conjunto sería inconsistente. Por el teorema de compacidad , para algún número natural n el conjunto sería inconsistente. Pero esto es absurdo, porque esta teoría se satisface para cualquier σ-estructura finita con o más elementos.
Sin embargo, existe una clase elemental básica K' en la signatura σ' = σ { f }, donde f es un símbolo de función unaria, tal que K consiste exactamente en las reducciones a σ de las σ'-estructuras en K' . K' está axiomatizada por la única oración , que expresa que f es inyectiva pero no sobreyectiva. Por lo tanto, K es elemental y lo que podría llamarse pseudoelemental básico, pero no elemental básico.
Finalmente, considere la signatura σ que consiste en un único símbolo de relación unaria P . Cada σ-estructura se divide en dos subconjuntos: aquellos elementos para los que P se cumple, y el resto. Sea K la clase de todas las σ-estructuras para las que estos dos subconjuntos tienen la misma cardinalidad , es decir, hay una biyección entre ellos. Esta clase no es elemental, porque una σ-estructura en la que tanto el conjunto de realizaciones de P como su complemento son numerablemente infinitos satisface precisamente las mismas oraciones de primer orden que una σ-estructura en la que uno de los conjuntos es numerablemente infinito y el otro es incontable.
Consideremos ahora la firma , que consta de P junto con un símbolo de función unaria f . Sea la clase de todas las -estructuras tales que f es una biyección y P es válido para x sólo si P no es válido para f(x) . es claramente una clase elemental y, por lo tanto, K es un ejemplo de una clase pseudoelemental que no es elemental.
Sea σ una signatura arbitraria. La clase K de todas las σ-estructuras finitas no es elemental, porque (como se muestra arriba) su complemento es elemental pero no elemental básico. Como esto también es cierto para toda signatura que extienda σ, K ni siquiera es una clase pseudoelemental.
Este ejemplo demuestra los límites del poder expresivo inherente a la lógica de primer orden en comparación con la lógica de segundo orden , mucho más expresiva . Sin embargo, la lógica de segundo orden no logra conservar muchas propiedades deseables de la lógica de primer orden, como los teoremas de completitud y compacidad .
