clase primaria

Let σ be a signature consisting only of a unary function symbol f. The class K of σ-structures in which f is one-to-one is a basic elementary class. This is witnessed by the theory T, which consists only of the single sentence

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

Let σ be an arbitrary signature. The class K of all infinite σ-structures is elementary. To see this, consider the sentences

${\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}))}$",

and so on. (So the sentence ${\displaystyle \rho _{n}}$ says that there are at least n elements.) The infinite σ-structures are precisely the models of the theory

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

But K is not a basic elementary class. Otherwise the infinite σ-structures would be precisely those that satisfy a certain first-order sentence τ. But then the set ${\displaystyle \{\neg \tau ,\rho _{2},\rho _{3},\rho _{4},\dots \}}$ would be inconsistent. By the compactness theorem, for some natural number n the set ${\displaystyle \{\neg \tau ,\rho _{2},\rho _{3},\rho _{4},\dots ,\rho _{n}\}}$ would be inconsistent. But this is absurd, because this theory is satisfied by any finite σ-structure with ${\displaystyle n+1}$ or more elements.

However, there is a basic elementary class K' in the signature σ' = σ ${\displaystyle \cup }$ {f}, where f is a unary function symbol, such that K consists exactly of the reducts to σ of σ'-structures in K'. K' is axiomatised by the single sentence ${\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 .