clase primaria

Sea σ una signatura 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 se evidencia en la teoría T , que consiste únicamente en la única oración.

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

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

${\displaystyle \rho _{2}={}}$"${\displaystyle \exists x_{1}\exists x_{2}(x_{1}\not =x_{2})}$",

${\displaystyle \rho _{3}={}}$"${\displaystyle \exists x_{1}\exists x_{2}\exists x_{3}((x_{1}\not =x_{2})\land (x_{1}\not =x_{3})\land (x_{2}\not =x_{3}))}$",

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

${\displaystyle T_{\infty }=\{\rho _{2},\rho _{3},\rho _{4},\dots \}}$.

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

Sin embargo, existe una clase elemental básica K ' en la signatura σ' = σ${\displaystyle \cup }${ f }, donde f es un símbolo de función unaria, de tal manera que K consiste exactamente en los reductos a σ de las σ'-estructuras en K ' . K ' se axiomatiza mediante la única oración${\displaystyle (\forall x\forall y(f(x)=f(y)\rightarrow x=y)\land \exists y\neg \exists x(y=f(x))),}$, lo 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, consideremos la signatura σ que consiste en un único símbolo de relación unaria P. Toda σ-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 cuales estos dos subconjuntos tienen la misma cardinalidad , es decir, existe 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 satisfacen precisamente las mismas sentencias de primer orden que una σ-estructura en la que uno de los conjuntos es numerablemente infinito y el otro no es numerable.

Ahora considere la firma${\displaystyle \sigma '}$, que consiste en P junto con un símbolo de función unaria f . Sea${\displaystyle K'}$ser la clase de todos${\displaystyle \sigma '}$-estructuras tales que f es una biyección y P se cumple para x si y solo si P no se cumple para f(x) .${\displaystyle K'}$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. Dado que esto también es cierto para toda signatura que extiende σ, K ni siquiera es una clase pseudoelemental.

Este ejemplo demuestra las limitaciones del poder expresivo inherente a la lógica de primer orden, en contraposición a la lógica de segundo orden, mucho más expresiva . Sin embargo, la lógica de segundo orden no conserva muchas propiedades deseables de la lógica de primer orden, como los teoremas de completitud y compacidad .