Elementary class - Citizendia

In the branch of mathematical logic called model theory, an elementary class (or axiomatizable class) is a class consisting of all structures satisfying a fixed first-order theory. Mathematical logic is a subfield of Logic and Mathematics with close connections to Computer science and Philosophical logic. In Mathematics, model theory is the study of (classes of mathematical structures such as groups, Fields graphs or even models In Set theory and its applications throughout Mathematics, a class is a collection of sets (or sometimes other mathematical objects that can be unambiguously In Universal algebra and in Model theory, a structure consists of an underlying set along with a collection of Finitary functions and relations First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science In Mathematical logic, a theory is a set of sentences in a Formal language.

1 Definition
2 Conflicting and alternative terminology
3 Easy relations between the notions
4 Examples
5 References

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. In Set theory and its applications throughout Mathematics, a class is a collection of sets (or sometimes other mathematical objects that can be unambiguously In Universal algebra and in Model theory, a structure consists of an underlying set along with a collection of Finitary functions and relations In Logic, especially Mathematical logic, a signature lists and describes the Non-logical symbols of a Formal language. First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science In Mathematical logic, a theory is a set of sentences in a Formal language. e. , of all σ-structures which 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 which extends σ, such that K consists of all σ-structures which are reducts to σ of models of T. In Logic, a pseudoelementary class is a class of structures derived from an Elementary class (one definable in first order logic by omitting some of In Universal algebra and in Model theory, a reduct of an algebraic structure is obtained by omitting some of the operations and relations of that structure In other words, a class K of σ-structures is pseudo-elementary iff 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

It should be noted that 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. In Mathematics, model theory is the study of (classes of mathematical structures such as groups, Fields graphs or even models Finite model theory is a subfield of Model theory that focuses on properties of logical languages such as First-order logic, over finite structures such as 1994, Ebbinghaus and Flum 2005). Hodges calls elementary classes axiomatizable classes, and he refers to basic elementary classes as definable classes. In the branch of Mathematical logic called Model theory, an elementary class (or axiomatizable class) is a class consisting of all 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. In Logic, especially Mathematical logic, a signature lists and describes the Non-logical symbols of a Formal language. First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science This article is a technical mathematical article in the area of predicate logic Therefore basic elementary classes are untypical 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 which is closed under isomorphism there is an elementary class $K'$ of σ-structures such that K and $K'$ 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 iff it is elementary and its complement is also elementary. In Mathematical logic, the compactness theorem states that a (possibly Infinite) set of first-order sentences has a model, Iff every ↔

Examples

A basic elementary class

Let σ be a signature consisting only of a unary function symbol f. A unary function is a function that takes one argument. In Computer science, a Unary operator is a subset of unary function 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

$\forall x\forall y( (f(x)=f(y)) \to (x=y) )$ .

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

ρ 2 =

" $\exist x_1\exist x_2(x_1 \not =x_2)$ ",

ρ 3 =

" $\exist x_1\exist x_2\exist x_3((x_1 \not =x_2) \and (x_1 \not =x_3) \and (x_2 \not =x_3))$ ",

and so on. (So the sentence $ρ 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 which 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. In Mathematical logic, the compactness theorem states that a (possibly Infinite) set of first-order sentences has a model, Iff every But this is absurd, because this theory is satisfied by any σ-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.

A pseudo-elementary class that is not 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. In Mathematics, a partition of a set X is a division of X into non-overlapping " parts " or " blocks " Let K be the class of all σ-structures for which these two subsets have the same cardinality, i. In Mathematics, the cardinality of a set is a measure of the "number of elements of the set" 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 $K'$ 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). ↔ $K'$ is clearly an elementary class, and therefore K is an example of a pseudo-elementary class which is not elementary.

A class that is not pseudo-elementary

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. First-order logic (FOL is a formal Deductive system used in mathematics philosophy linguistics and computer science 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, however, fails to retain many desirable properties of first-order logic, such as the compactness theorem.

References

Chang, Chen Chung & Keisler, H. Jerome (1990), Model Theory (3rd ed. H Jerome Keisler is an American Mathematician, currently professor emeritus at University of Wisconsin-Madison. ), Studies in Logic and the Foundations of Mathematics, Elsevier, ISBN 978-0-444-88054-3
Ebbinghaus, Heinz-Dieter & Flum, Jörg (2005), Finite model theory, Berlin, New York: Springer-Verlag, pp. Elsevier, the world's largest Publisher of Medical and Scientific literature, forms part of the Reed Elsevier group Springer Science+Business Media or Springer (ˈʃpʁɪŋɐ is a worldwide Publishing company based in Germany, which publishes textbooks academic 360, ISBN 978-3-540-28787-2
Ebbinghaus, Heinz-Dieter; Flum, Jörg & Thomas, Wolfgang (1994), Mathematical Logic (2nd ed. ), Berlin, New York: Springer-Verlag, ISBN 978-0-387-94258-2
Hodges, Wilfrid (1997), A shorter model theory, Cambridge University Press, ISBN 978-0-521-58713-6
Poizat, Bruno (2000), A Course in Model Theory: An Introduction to Contemporary Mathematical Logic, Berlin, New York: Springer-Verlag, ISBN 978-0-387-98655-5

Springer Science+Business Media or Springer (ˈʃpʁɪŋɐ is a worldwide Publishing company based in Germany, which publishes textbooks academic Wilfrid Hodges (born 1941 is a British Mathematician, known for his work in Model theory. Cambridge University Press (known colloquially as CUP is a Publisher given a Royal Charter by Henry VIII in 1534 Springer Science+Business Media or Springer (ˈʃpʁɪŋɐ is a worldwide Publishing company based in Germany, which publishes textbooks academic

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |

Contents