Clase de primaria - Elementary class

En la teoría de modelos , una rama de la lógica matemática , una clase elemental (o clase axiomatizable ) es una clase que consta de todas las estructuras que satisfacen una teoría fija de primer orden .

Definición

Una clase K de estructuras de una firma σ se denomina una clase elemental si hay un primer orden teoría T de la firma σ, de modo que K consta de todos los modelos de T , es decir, de todos sigma-estructuras que satisfagan T . Si T puede elegirse como una teoría que consta de una sola oración de primer orden, entonces K se llama una clase elemental básica .

Más en general, K es una clase pseudo-elemental si hay una teoría de primer orden T de una firma que se extiende σ, de modo que K se compone de todos sigma-estructuras que son reductos de sigma de modelos de T . En otras palabras, una clase K de σ-estructuras es pseudo-elemental si hay una clase elemental K ' tal que K consiste precisamente en los reductos a σ de las estructuras en K' .

Por razones obvias, las clases elementales también se denominan axiomatizables en la lógica de primer orden y las clases elementales básicas se denominan finitamente axiomatizables en la lógica de primer orden . Estas definiciones se extienden a otras lógicas de 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.

Terminología conflictiva y alternativa

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 todavía 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 primer orden Las clases axiomatizables están reservadas 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 respectivos sinónimos CE clase ${\ displaystyle _ {\ Delta}}$ y clase EC (Hodges, 1993).

Hay buenas razones para esta terminología divergente. Las firmas que se consideran en la teoría de modelos general a menudo son 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, se ocupa casi exclusivamente de 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 tanto, las clases elementales no son muy interesantes para los teóricos de modelos finitos. ${\ Displaystyle K '}$${\ Displaystyle K '}$

Relaciones fáciles entre las nociones

Claramente, cada clase elemental básica es una clase elemental, y cada clase elemental es una clase pseudoelemental. Además, como una consecuencia fácil del teorema de la compacidad , una clase de estructuras σ es básica elemental si y sólo si es elemental y su complemento también es elemental.

Ejemplos de

Una clase elemental básica

Sea σ una firma que consta solo de un símbolo de función unaria f . La clase K de estructuras σ en las que f es uno a uno es una clase elemental básica. Esto lo atestigua la teoría T , que consta solo de la oración única

${\ Displaystyle \ forall x \ forall y ((f (x) = f (y)) \ to (x = y))}$ .

Una clase pseudoelemental básica y elemental que no es elemental básica

Sea σ una firma arbitraria. La clase K de todas las estructuras σ infinitas es elemental. Para ver esto, considere las oraciones

${\ Displaystyle \ rho _ {2} = {}}$ " ", ${\ Displaystyle \ existe x_ {1} \ existe x_ {2} (x_ {1} \ not = x_ {2})}$

${\ Displaystyle \ rho _ {3} = {}}$ " ", ${\ Displaystyle \ existe x_ {1} \ existe x_ {2} \ existe x_ {3} ((x_ {1} \ not = x_ {2}) \ land (x_ {1} \ not = x_ {3}) \ tierra (x_ {2} \ not = x_ {3}))}$

etcétera. (Entonces la oración dice que hay al menos n elementos). Las infinitas estructuras σ son precisamente los modelos de la teoría ${\ Displaystyle \ rho _ {n}}$

${\ Displaystyle T _ {\ infty} = \ {\ rho _ {2}, \ rho _ {3}, \ rho _ {4}, \ dots \}}$ .

Pero K no es una clase elemental básica. De lo contrario, las infinitas estructuras σ serían precisamente aquellas que satisfacen una determinada oración de primer orden τ. Pero entonces el conjunto sería inconsistente. Según el teorema de la compacidad , para algún número natural n, el conjunto sería inconsistente. Pero esto es absurdo, porque esta teoría se satisface con cualquier estructura σ con o más elementos. ${\ Displaystyle \ {\ neg \ tau, \ rho _ {2}, \ rho _ {3}, \ rho _ {4}, \ dots \}}$${\ Displaystyle \ {\ neg \ tau, \ rho _ {2}, \ rho _ {3}, \ rho _ {4}, \ dots, \ rho _ {n} \}}$${\ Displaystyle n + 1}$

Sin embargo, hay una clase elemental básica K ' en la firma σ' = σ { 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á axiomatizado por la oración única , que expresa que f es inyectiva pero no sobreyectiva. Por tanto, K es elemental y lo que podríamos llamar pseudoelemental básico, pero no elemental básico. ${\ Displaystyle \ cup}$${\ Displaystyle (\ forall x \ forall y (f (x) = f (y) \ rightarrow x = y) \ tierra \ existe y \ neg \ existe x (y = f (x))),}$

Clase pseudoelemental que no es elemental

Finalmente, considere la firma σ consiste en una sola unario símbolo de relación P . Cada estructura σ se divide en dos subconjuntos: aquellos elementos para los que se cumple P , 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 infinitos numerables satisface precisamente las mismas oraciones de primer orden que una estructura σ en la que uno de los conjuntos es infinito numerable y el otro es incontable.

Ahora considere 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 se cumple para x si f P no se cumple para f (x) . es claramente una clase elemental y, por lo tanto, K es un ejemplo de una clase pseudoelemental que no es elemental. ${\ Displaystyle \ sigma '}$${\ Displaystyle K '}$${\ Displaystyle \ sigma '}$ ${\ Displaystyle K '}$

Clase no pseudoelemental

Sea σ una firma 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. Dado que esto también es cierto para cada firma que se extiende a σ, 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 oposición a la lógica de segundo orden, mucho más expresiva . La lógica de segundo orden, sin embargo, no conserva muchas propiedades deseables de la lógica de primer orden, como los teoremas de completitud y compacidad .

Referencias

• Chang, Chen Chung; Keisler, H. Jerome (1990) [1973], Teoría de modelos , Estudios de lógica y fundamentos de las matemáticas (3ª ed.), Elsevier , ISBN   978-0-444-88054-3
• Ebbinghaus, Heinz-Dieter; Flum, Jörg (2005) [1995], Teoría de modelos finitos , Berlín, Nueva York: Springer-Verlag , p. 360, ISBN   978-3-540-28787-2
• Ebbinghaus, Heinz-Dieter; Flum, Jörg; Thomas, Wolfgang (1994), Lógica matemática (2a ed.), Berlín, Nueva York: Springer-Verlag , ISBN   978-0-387-94258-2
• Hodges, Wilfrid (1997), Una teoría de modelo más breve , Cambridge University Press , ISBN   978-0-521-58713-6
• Poizat, Bruno (2000), Un curso de teoría de modelos: una introducción a la lógica matemática contemporánea , Berlín, Nueva York: Springer-Verlag , ISBN   978-0-387-98655-5