Elementary class

In model theory, a branch of mathematical logic, an elementary class (or axiomatizable class) is a class consisting of all structures satisfying a fixed first-order theory.

In model theory, a branch of mathematical logic, an elementary class (or axiomatizable class) is a class consisting of all structures satisfying a fixed first-order theory. \forall x\forall y( (f(x)=f(y)) \to (x=y) ) . \rho_2={} " \exist x_1\exist x_2(x_1 \not =x_2) ", \rho_3={} " \exist x_1\exist x_2\exist 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 \rho_n says that there are at least n elements.) The infinite σ-structures are precisely the models of the theory 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 \{\neg\tau, \rho_2, \rho_3, \rho_4, \dots\} would be inconsistent. By the compactness theorem, for some natural number n the set \{\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 n+1 or more elements. However, there is a basic elementary class K ' in the signature σ' = σ \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 (\forall x\forall y(f(x) = f(y) \rightarrow x=y) \land \exists y\neg\exists x(y = f(x))), , which expresses that f is injective but not surjective. Therefore, K is elementary and what could be called basic pseudo-elementary, but not basic elementary. === Non-pseudo-elementary class=== Let σ be an arbitrary signature. The class K of all finite σ-structures is not elementary, because (as shown above) its complement is elementary but not basic elementary. Since this is also true for every signature extending σ, K is not even a pseudo-elementary class. This example demonstrates the limits of expressive power inherent in first-order logic as opposed to the far more expressive second-order logic. Second-order logic, however, fails to retain many desirable properties of first-order logic, such as the completeness and compactness theorems.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1272955638 under CC BY-SA 4.0; modifications have been made.