|
In mathematical logic, a first-order theory is given by a set of axioms in somelanguage. This entry lists some of the more common examples used in model theory and some of their properties.
Preliminaries The background logic for all theories is first-order logic with identity. A first-order language consists of logical symbols (e.g. variables, equality, a quantifier, connectives) and three sets: The terms and formulas are built up from this language in the usual way. A sentence is a formula with no free variables. A theory is a set of sentences, and is called closed if it contains all consequences of its elements. There are two common ways to specify theories: A theory may be: Pure identity theories The language of pure identity theory is empty, with no functions, constants, or relations. Pure identity theory has no (non-logical) axioms. It is decidable. One of the few interesting properties that can be stated in the language of pure identity theory is that of being infinite. This is given by an infinite set of axioms stating there are at least 2 elements, there are at least 3 elements, and so on: The opposite property of being finite cannot be stated in first-order logic for any theory that has arbitrarily large finite models: in fact any such theory has infinite models by the compactness theorem. In general if a property can be stated by a finite number of sentences of first-order logic then the opposite property can also be stated in first-order logic, but if a property needs an infinite number of sentences then its opposite property cannot be stated in first-order logic. Any statement of pure identity theory is equivalent to either σ(N) or to ¬σ(N) for some finite subset N of the non-negative integers, where σ(N) is the statement that the number of elements is in N. It is even possible to describe all possible theories in this language as follows. Any theory is either the theory of all sets of cardinality in N for some finite subset N of the non-negative integers, or the theory of all sets whose cardinality is not in N, for some finite or infinite subset N of the non-negative integers. (There are no theories whose models are exactly sets of cardinality N if N is an infinite subset of the integers.) The complete theories are the theories of sets of cardinality n for some finite n, and the theory of infinite sets. One special case of this is the inconsistent theory defined by the axiom ∃x ¬x = x. It is a perfectly good theory with many good properties: it is complete, decidable, finitely axiomatizable, and so on. The only problem is that has no models at all. By Godel's completeness theorem, it is the only theory (for any given language) with no models. Equivalence relations The language of equivalence relations has one binary infix relation symbol ~, no constants, and no functions. Equivalence relations satisfy the axioms: Some first order properties of equivalence relations are: The theory of an equivalence relation with exactly 2 infinite equivalence classes is an easy example of a theory which is ω-categorical but not categorical for any larger cardinal. The equivalence relation ~ should not be confused with the identity symbol '=': if x=y then x~y, but the converse is not necessarily true. Theories of equivalence relations are not all that difficult or interesting, but often give easy examples or counterexamples for various statements. The following constructions are sometimes used to produce examples of theories with certain spectra; in fact by applying them to a small number of explicit theories T one gets examples of complete countable theories with all possible uncountable spectra. If T is a theory in some language, we define a new theory 2T by adding a new binary relation to the language, and adding axioms stating that it is an equivalence relation, such that there are an infinite number of equivalence classes all of which are models of T. It is possible to iterate this construction transfinitely: given an ordinal α, define a new theory by adding an equivalence relation Eβ for each β<α, together with axioms stating that whenever β<γ then each Eγ equivalence class is the union of infinitely many Eβ equivalence classes, and each E0 equivalence class is a model of T. Informally, one can visualize models of this theory as infinitely branching trees of height α with models of T attached to all leaves. Orders The language of orders has no constants or functions, and one binary relation symbols ≤. (It is of course possible to use ≥, < or > instead as the basic relation, with the obvious minor changes to the axioms.) We define x≥y, x<y, x>y as abbreviations for y≤x, x≤y ∧¬y≤x, y<x, Some first-order properties of orders: Being well ordered ("any non-empty subset has a minimal element") is not a first-order property; the usual definition involves quantifying over all subsets. Graphs The language of graphs has no constants or functions, and one binary relation symbols R, where R(x,y) is read as "there is an edge from x to y". The axioms for the theory of graphs are The theory of random graphs has the following extra axioms for each positive integer n: The theory of random graphs is ω categorical, complete, and decidable. A statement in the language of graphs is true in this theory if and only if it is true with probability 1 for a random graph on a countable number of points. Boolean algebras There are several different languages and conventions used for Boolean algebras: For the axioms, see the article on Boolean algebras. Tarski proved that the theory of Boolean algebras is decidable. We write x ≤ y as an abbreviation for x ∧ y = x, and atom(x) as an abbreviation for ¬x = 0 ∧ ∀y y≤x → y = 0 ∨ y = x, read as "x is an atom", in other words a non-zero element with nothing between it and 0. Here are some first-order properties of Boolean algebras: Groups The language of group theory has one constant 1 (the identity), one function of valence 1 (the inverse) whose value on t is denoted by t−1, and one function of valence 2, which is usually omitted from terms. For any integer n. tn is an abbreviation for the obvious term for the nth power of t. Groups are defined by the axioms Some properties of groups that can be defined in the first-order language of groups are: The theory of Abelian groups is decidable. The theory of Infinite divisible torsion-free abelian groups is complete, as is the theory of Infinite abelian groups of exponent p (for p prime). The theory of finite groups is the set of first-order statements in the language of groups that are true in all finite groups (there are plenty of infinite models of this theory). It is not completely trivial to find any such statement that is not true for all groups: one example is "given two elements of order 2, either they are conjugate or there is a non-trivial element commuting with both of them". The properties of being finite, or free, or simple, or torsion are not first-order. More precisely, the first-order theory of all groups with one of these properties has models that do not have this property. Rings and fields The language of (unital) rings has 2 constants 0 and 1, two binary functions + and ×, and one unary function −. Rings Axioms: Addition makes the ring into an abelian group, multiplication is associative and has an identity 1, and multiplication is left and right distributive. Commutative rings The axioms for rings plus ∀x ∀y xy=yx. Fields The axioms for commutative rings plus ∀x ∃y xy=1 and ¬ 1=0. There is a slight problem with this because the submodels of fields are not fields but integral domains. One way round this (in the rare cases when it matters) is to add an extra unary function symbol representing the inverse. For any positive integer n the property that all equations of degree n have a root can be expressed by a single first-order sentence: Algebraically closed fields. The axioms for fields, plus for every positive n the axiom that all polynomials of degree n have a root. The theory is decidable and model complete but not complete. Algebraically closed fields of characteristic p The classical examples of complete theories. Categorical in all uncountable cardinals. Finite fields. The theory of finite fields is the set of all first-order statements that are true in all finite fields. Significant examples of such statements can, for example, be given by applying the Chevalley-Warning theorem, over the prime fields. The name is a little misleading as the theory has plenty of infinite models. Ax proved that the theory is decidable. Real fields Real closed fields Axioms: The theory of real closed fields is decidable (Tarski) and therefore complete. Euclidean geometry is also decidable, since Cartesian coordinates transform it into a model of a real closed field. For a first order axiomatization of Euclidean geometry, see Tarski's axioms. p-adic fields Arithmetic The language of arithmetic has: Robinson arithmetic (also called Q). Axioms (1) and (2) govern the distinguished element 0. (3) assures that S is an injection. Axioms (4) and (5) are the standard recursive definition of addition; (6) and (7) do the same for multiplication. Hence Q is Peano arithmetic without induction. Q is primarily interesting as an instance of a rather weak theory for which Gödel's incompleteness theorem holds. Axioms: Presburger arithmetic. Q without multiplication and without axioms 6 and 7; the theory of the natural numbers under addition. It is complete and decidable. First order Peano arithmetic with induction restricted to Σn formulas (for n = 0, 1, 2, ...). This is a series of more and more powerful fragments of Peano arithmetic. n=1 has about the same strength as Skolem arithmetic (also called primitive recursive arithmetic). First order Peano arithmetic, PA. The "standard" theory of arithmetic. The axioms are the axioms of Robinson arithmetic above, together with the axiom scheme of induction: ightarrow ( orall x phi(x)) for any formula φ in the language of PA. φ may contain free variables other than x. Kurt Godel's epochal 1931 paper proved PA incomplete and incompletable. Second-order arithmetic. This can refer to a first order theory (in spite of the name) with two types of variables, thought of as varying over integers and subsets of the integers. (There is also a theory of arithmetic in second order logic that is called second order arithmetic. It has only one model, unlike the corresponding theory in first order logic, which is incomplete.) The axioms are those of Robinson arithmetic, together with axioms schemes of induction and comprehension. There are many different subtheories of second order arithmetic that differ in which formulas are allowed in the induction and comprehension schemes. Complete arithmetic (also known as true arithmetic) is the theory of the standard model of arithmetic, the natural numbers N. It is complete but does not have a recursively enumerable set of axioms. Set theories The usual language of set theory has one binary relation ∈, no constants, and no functions. Some of the theories below are "class theories" which have two sorts of object, sets and classes. There are three common ways of handling this in first-order logic: Some first order set theories include: See also | ||||||||
|
| |||||||||
 |
|
| |