Elementary class

Last updated

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.

Contents

Definition

A class K of structures of a signature σ is called an elementary class if there is a first-order theory T of signature σ, such that K consists of all models of T, i.e., of all σ-structures that satisfy T. If T can be chosen as a theory consisting of a single first-order sentence, then K is called a basic elementary class.

More generally, K is a pseudo-elementary class if there is a first-order theory T of a signature that extends σ, such that K consists of all σ-structures that are reducts to σ of models of T. In other words, a class K of σ-structures is pseudo-elementary if and only if there is an elementary class K' such that K consists of precisely the reducts to σ of the structures in K'.

For obvious reasons, elementary classes are also called axiomatizable in first-order logic, and basic elementary classes are called finitely axiomatizable in first-order logic. These definitions extend to other logics in the obvious way, but since the first-order case is by far the most important, axiomatizable implicitly refers to this case when no other logic is specified.

Conflicting and alternative terminology

While the above is nowadays standard terminology in "infinite" model theory, the slightly different earlier definitions are still in use in finite model theory, where an elementary class may be called a Δ-elementary class, and the terms elementary class and first-order axiomatizable class are reserved for basic elementary classes (Ebbinghaus et al. 1994, Ebbinghaus and Flum 2005). Hodges calls elementary classes axiomatizable classes, and he refers to basic elementary classes as definable classes. He also uses the respective synonyms EC class and EC class (Hodges, 1993).

There are good reasons for this diverging terminology. The signatures that are considered in general model theory are often infinite, while a single first-order sentence contains only finitely many symbols. Therefore, basic elementary classes are atypical in infinite model theory. Finite model theory, on the other hand, deals almost exclusively with finite signatures. It is easy to see that for every finite signature σ and for every class K of σ-structures closed under isomorphism there is an elementary class of σ-structures such that K and contain precisely the same finite structures. Hence, elementary classes are not very interesting for finite model theorists.

Easy relations between the notions

Clearly every basic elementary class is an elementary class, and every elementary class is a pseudo-elementary class. Moreover, as an easy consequence of the compactness theorem, a class of σ-structures is basic elementary if and only if it is elementary and its complement is also elementary.

Examples

A basic elementary class

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

.

An elementary, basic pseudoelementary class that is not basic elementary

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

"",
"",

and so on. (So the sentence says that there are at least n elements.) The infinite σ-structures are precisely the models of the theory

.

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 would be inconsistent. By the compactness theorem, for some natural number n the set would be inconsistent. But this is absurd, because this theory is satisfied by any finite σ-structure with or more elements.

However, there is a basic elementary class K' in the signature σ' = σ {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 , 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.

Pseudo-elementary class that is non-elementary

Finally, consider the signature σ consisting of a single unary relation symbol P. Every σ-structure is partitioned into two subsets: Those elements for which P holds, and the rest. Let K be the class of all σ-structures for which these two subsets have the same cardinality, i.e., there is a bijection between them. This class is not elementary, because a σ-structure in which both the set of realisations of P and its complement are countably infinite satisfies precisely the same first-order sentences as a σ-structure in which one of the sets is countably infinite and the other is uncountable.

Now consider the signature , which consists of P along with a unary function symbol f. Let be the class of all -structures such that f is a bijection and P holds for x iff P does not hold for f(x). is clearly an elementary class, and therefore K is an example of a pseudo-elementary class that is not 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.

Related Research Articles

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.

In mathematical logic, model theory is the study of the relationship between formal theories, and their models. The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in a model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shelah's stability theory.

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

Spectral methods are a class of techniques used in applied mathematics and scientific computing to numerically solve certain differential equations. The idea is to write the solution of the differential equation as a sum of certain "basis functions" and then to choose the coefficients in the sum in order to satisfy the differential equation as well as possible.

In logic and mathematics, second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory.

In mathematical logic, the Löwenheim–Skolem theorem is a theorem on the existence and cardinality of models, named after Leopold Löwenheim and Thoralf Skolem.

In mathematics, more specifically in group theory, the character of a group representation is a function on the group that associates to each group element the trace of the corresponding matrix. The character carries the essential information about the representation in a more condensed form. Georg Frobenius initially developed representation theory of finite groups entirely based on the characters, and without any explicit matrix realization of representations themselves. This is possible because a complex representation of a finite group is determined by its character. The situation with representations over a field of positive characteristic, so-called "modular representations", is more delicate, but Richard Brauer developed a powerful theory of characters in this case as well. Many deep theorems on the structure of finite groups use characters of modular representations.

In model theory, a branch of mathematical logic, two structures M and N of the same signature σ are called elementarily equivalent if they satisfy the same first-order σ-sentences.

Finite model theory is a subarea of model theory. Model theory is the branch of logic which deals with the relation between a formal language (syntax) and its interpretations (semantics). Finite model theory is a restriction of model theory to interpretations on finite structures, which have a finite universe.

In mathematical logic, a theory is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, after which an element of a deductively closed theory is then called a theorem of the theory. In many deductive systems there is usually a subset that is called "the set of axioms" of the theory , in which case the deductive system is also called an "axiomatic system". By definition, every axiom is automatically a theorem. A first-order theory is a set of first-order sentences (theorems) recursively obtained by the inference rules of the system applied to the set of axioms.

In universal algebra and in model theory, a structure consists of a set along with a collection of finitary operations and relations that are defined on it.

In mathematical logic, an ω-consistenttheory is a theory that is not only (syntactically) consistent, but also avoids proving certain infinite combinations of sentences that are intuitively contradictory. The name is due to Kurt Gödel, who introduced the concept in the course of proving the incompleteness theorem.

Constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "" and "" of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.

In logic, a modal companion of a superintuitionistic (intermediate) logic L is a normal modal logic that interprets L by a certain canonical translation, described below. Modal companions share various properties of the original intermediate logic, which enables to study intermediate logics using tools developed for modal logic.

In logic, especially mathematical logic, a signature lists and describes the non-logical symbols of a formal language. In universal algebra, a signature lists the operations that characterize an algebraic structure. In model theory, signatures are used for both purposes. They are rarely made explicit in more philosophical treatments of logic.

General set theory (GST) is George Boolos's (1998) name for a fragment of the axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms.

An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning until they are given some interpretation. The general study of interpretations of formal languages is called formal semantics.

In mathematical logic the theory of pure equality is a first-order theory. It has a signature consisting of only the equality relation symbol, and includes no non-logical axioms at all.

References