FACTOID # 4: Just 1% of the houses in Nevada were built before 1939.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > List of first order theories

In mathematical logic, a first-order theory is given by a set of axioms in some language. This entry lists some of the more common examples used in model theory and some of their properties. Mathematical logic is a discipline within mathematics, studying formal systems in relation to the way they encode intuitive concepts of proof and computation as part of the foundations of mathematics. ... It has been suggested that Predicate calculus be merged into this article or section. ... In mathematics, model theory is the study of the representation of mathematical concepts in terms of set theory, or the study of the models which underlie mathematical systems. ...

Contents


Preliminaries

The background logic for all theories is first-order logic with identity. It has been suggested that Predicate calculus be merged into this article or section. ... // Computer programming In object-oriented programming, object identity is a mechanism for distinguishing different objects from each other. ...


A language consists of three sets:

  • Constant symbols (examples: 0, 1),
  • Functions symbols (examples: +, ×), each with some positive integer called its valence,
  • Relation symbols (or predicates) (examples: ≤, ∈) each with some positive integer called its valence.

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. It has been suggested that Predicate calculus be merged into this article or section. ...


There are two common ways to specify theories:

  1. List or describe a set of sentences, called the axioms of the theory. This set may be finite or infinite.
  2. Give a model or set of models of the language, and define a theory to be the set of sentences holding in all these models. For example, the "theory of finite fields" consists of all sentences in the language of fields that are true in all finite fields.

A theory may be:

  • Complete: for any statement, either it or its negation is provable;
  • Model complete;
  • Decidable: There is an algorithm to decide which statements are provable;
  • Finitely axiomatizable: the axioms are finite in number;
  • Recursively axiomatizable;
  • α-categorical: All models of cardinality α are isomorphic;
  • Consistent: Not all statements are provable;
  • Stable (or ω-stable).

In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ... A logical system is decidable iff there exists an algorithm such that for every well-formed formula in that system there exists a maximum finite number N of steps such that the algorithm is capable of deciding in less than or equal to N algorithmic steps whether the formula is... In model theory, Morleys categoricity theorem is a theorem of Michael D. Morley which states that if a first-order theory is complete in a countable language, then if it is categorical in some uncountable cardinality, it is categorical in all uncountable cardinalities. ...

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:

  • x1x2 ¬x1 = x2, ∃x1x2x3 ¬x1 = x2 ∧ ¬x1 = x3 ∧ ¬x2 = x3,...

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 relation symbol ≡, no constants, and no functions. Equivalence relations obey the axioms: In mathematics, an equivalence relation on a set X is a binary relation on X that is reflexive, symmetric and transitive, i. ...

  • Reflexivex xx;
  • Symmetricxy xyyx;
  • Transitive: ∀xyz xyyzxz.

Some first order properties of equivalence relations are:

  • ≡ has an infinite number of equivalence classes;
  • ≡ has exactly n equivalence classes (for any fixed positive integer n);
  • All equivalence classes are infinite;
  • All equivalence classes have size exactly n (for any fixed positive integer n).

The theory of an equivalence relation with exactly 2 equivalence classes, both infinite, is an easy example of a theory which is ω-categorical but not categorical for any larger cardinal. In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x in X | x ~ a } The notion of equivalence classes is useful for constructing sets... In mathematics, given a set X and an equivalence relation ~ on X, the equivalence class of an element a in X is the subset of all elements in X which are equivalent to a: [a] = { x ∈ X | x ~ a } The notion of equivalence classes is useful for constructing sets out...


The equivalence relation ≡ should not be confused with the identity symbol =: if x=y then xy, 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 xy, x<y, x>y as abbreviations for yx, xy ∧¬yx, y<x,


Some first-order properties of orders:

  • Transitive: ∀xyz xyyzxz
  • Reflexive: ∀x x ≤ x
  • Antisymmetric: ∀xy xyyxx = y
  • Partial: Transitive∧Reflexive∧Antisymmetric;
  • Simple (or total or linear): Partial ∧ ∀xy xyyx
  • Densexz x<z → ∃y x<yy<z ("Between any 2 distinct elements there is another element")
  • There is a smallest element: ∃xy xy
  • There is a largest element: ∃xy yx
  • Every element has an immediate successor: ∀xyz x<zyz

The theory of dense simple orders with no smallest or largest element is complete, ω categorical, but not categorical for any uncountable cardinal. There are 3 other very similar theories: the theory of dense simple orders with a:

  • Smallest but no largest element;
  • Largest but no smallest element;
  • Largest and smallest element.

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

  • Symmetic: ∀xy R(x,y)→ R(y,x)
  • Anti-reflexive: ∀x ¬R(x,x) ("no loops")

The theory of random graphs has the following extra axioms for each positive integer n:

  • For any two disjoint finite sets of size n, there is a point joined to all points of the first set and to no points of the second set. (For each fixed n, it is easy to write this statement in the language of graphs.)

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. In mathematics, a random graph is a graph that is generated by some random process. ...


Boolean algebras

There are several different languages and conventions used for Boolean algebras: In mathematics and computer science, Boolean algebras, or Boolean lattices, are algebraic structures which capture the essence of the logical operations AND, OR and NOT as well as the corresponding set theoretic operations intersection, union and complement. ...

  1. The language has 2 constants, 0 and 1, and two binary functions ∧ and ∨ ("and" and "or"), and one unary function ¬ ("not"). This is a little confusing as the functions use the same symbols as the propositional functions of first-order logic.
  2. In set theory, a common convention is that the language has 2 constants, 0 and 1, and two binary functions · and +, and one unary function −. The three functions have the same interpretation as the functions in the first convention. Unfortunately, this convention clashes badly with the next convention:
  3. In algebra, the usual convention is that the language has 2 constants, 0 and 1, and two binary functions · and +. The function · has the same meaning as ∧, but a+b means ab∧¬(ab). The reason for this is that the axioms for a Boolean algebra are then just the axioms for a ring with 1 plus ∀x x2 = x. Unfortunately this clashes with the standard convention in set theory given above.

For the axioms, see the article on Boolean algebras. Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics and computer science, Boolean algebras, or Boolean lattices, are algebraic structures which capture the essence of the logical operations AND, OR and NOT as well as the corresponding set theoretic operations intersection, union and complement. ...


Tarski proved that the theory of Boolean algebras is decidable.


We write xy as an abbreviation for xy = x, and atom(x) as an abbreviation for ¬x = 0 ∧ ∀y yxy = 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:

  • Atomic: ∀x x=0 ∨ ∃y yx ∧ atom(y)
  • Atomless: ∀x ¬atom(x)

The theory of atomless Boolean algebras is ω-categorical and complete.


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 In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ...

  • Identity: ∀x 1x = xx1 = x
  • Inverse: ∀x x−1x = 1xx−1 = 1
  • Associative: ∀xyz (xy)z = x(yz)

Some properties of groups that can be defined in the first-order language of groups are:

  • Abelianxy xy = yx.
  • Torsion freex2 = 1→x = 1, ∀x3 = 1 → x = 1, ∀x4 = 1 → x = 1, ...
  • Divisiblexy y2 = x, ∀xy y3 = x, ∀xy y4 = x, ...
  • Infinite (as in identity theory)
  • Exponent n (for any fixed positive integer n) ∀x xn = 1
  • Nilpotent of class n (for any fixed positive integer n)
  • Solvable of class n (for any fixed positive integer n)

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). In mathematics, an element x of a ring R is called nilpotent if there exists some positive integer n such that xn = 0. ... In mathematics, solvable usually refers to the idea of a solvable group, or the corresponding idea of a solvable Lie algebra. ...


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. In mathematics, a ring is an algebraic structure in which addition and multiplication are defined and have properties listed below. ...


Commutative rings The axioms for rings plus ∀xy xy=yx. In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation obeys the commutative law. ...


Fields The axioms for commutative rings plus ∀xy 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. This article presents the essential definitions. ...


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:

  • a1a2... ∀ anx (...((x+a1)x +a2)x+...)x+an = 0

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. In mathematics, a field F is said to be algebraically closed if every polynomial of degree at least 1, with coefficients in F, has a zero (root) in F (i. ...


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. In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many elements. ... In mathematics, Chevalleys theorem on solutions of polynomial equations over a finite field F with q elements, q a power of the prime number p, states that for a polynomial P(X1, ..., XN) of total degree d, with d < N, the number M of solutions of P(X1, ..., XN... In mathematics, the characteristic of a ring R with identity element 1R is defined to be the smallest positive integer n such that n1R = 0 (where n1R is defined as 1R + ... + 1R with n summands). ...


Real fields


Real closed fields Axioms: In mathematics, a real closed field is an ordered field F in which any of the following equivalent conditions are true: Every non-negative element of F has a square root in F, and any polynomial of odd degree with coefficients in F has at least one root in F...

  • xy x=yyx+yy=0.
  • For every odd positive n, the axiom stating that every polynomial of degree n has a root.
  • For every positive n, the axiom ∀ a1a2... ∀ an a1a1+a2a2+ ...+anan=0 → a1=0∨a2=0∨ ... ∨an=0 (0 is not a non-trivial sum of squares).

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. Euclid Euclidean geometry is a mathematical system due to the Hellenistic mathematician Euclid of Egypt. ... Cartesian means relating to the French mathematician and philosopher Descartes, who, among other things, worked to merge algebra and Euclidean geometry. ... Tarskis axioms, due to Alfred Tarski, are an axiom set for the substantial fragment of Euclidean geometry, called elementary, that is formulable in first order logic with identity, and requiring no set theory. ...


p-adic fields


Arithmetic

The language of arithmetic has a constant 0, a function S of valence 1 (the successor), and two functions + and × of valence 2. Some authors replace S by a constant 1; these are related in the obvious way by 1 = S0 and St = 1 + t. Sometimes Sx is denoted by x′.


Presburger arithmetic The language of Presburger arithmetic consists of one binary function +. Presburger arithmetic is the theory of the non-negative integers under addition. It is complete and decidable. Presburger arithmetic is the first-order theory of the natural numbers with addition. ...


Robinson arithmetic (also called Q) This is "Peano arithmetic without induction" and is an example of a rather weak theory for which Gödel's incompleteness theorem holds. Axioms: In mathematics, Robinson arithmetic, or Q, is a fragment of the theory of the natural numbers, set out in R. M. Robinson (1950). ... In mathematical logic, Gödels incompleteness theorems are two celebrated theorems proven by Kurt Gödel in 1931. ...

  1. ∀x Sx ≠ 0
  2. ∀x x ≠ 0 → ∃y Sy = x
  3. ∀x∀y x ≠ y → S(x) ≠ Sy
  4. ∀x x + 0 = x
  5. ∀x∀y x + Sy = S(x + y)
  6. ∀x x × 0 = 0
  7. ∀x∀y x × Sy = (x × y) + y

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. The fragment for n=1 has about the same strength as Skolem arithmetic (also called primitive recursive arithmetic).


First order Peano arithmetic. This is the "standard" theory of arithmetic. The axioms are the axioms of Robinson arithmetic above, together with the axiom scheme of induction: In mathematics, the Peano axioms (or Peano postulates) are a set of first-order axioms proposed by Giuseppe Peano which determine the theory of Peano arithmetic (also known as first-order arithmetic). ... In mathematics, Robinson arithmetic, or Q, is a fragment of the theory of the natural numbers, set out in R. M. Robinson (1950). ...

  • (for any formula φ in the language of PA, possibly containing free variables other than x.)

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 sub-theories of second order arithmetic that differ in which formulas are allowed in the induction and comprehension schemes. In mathematical logic, second order arithmetic is a stronger version of Peano arithmetic that allows quantification over subsets of the integers, rather than just over integers. ...


Complete arithmetic (also known as true arithmetic) is the theory of the standard model { 0, 1, 2, 3, ... } of arithmetic. 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:

  1. Use first-order logic with two types.
  2. Use ordinary first-order logic, but add a new unary predicate "Set", where "Set(t)" means informally "t is a set".
  3. Use ordinary first-order logic, and instead of adding a new predicate to the language, treat "Set(t)" as an abbreviation for "∃y ty"

Some first order set theories include:

  • Kripke-Platek set theory (a weak set theory without powersets);
  • Zermelo set theory;
  • Zermelo-Fraenkel set theory;
  • Von Neumann-Bernays-Gödel set theory;
  • Morse–Kelley set theory;
  • New Foundations.

The Kripke-Platek axioms of set theory (KP) are a system of axioms of axiomatic set theory. ... Zermelo set theory, as set out in an important paper in 1908 by Ernst Zermelo, is the ancestor of modern set theory. ... Zermelo-Fraenkel set theory, commonly abbreviated ZFC, is the most common form of axiomatic set theory, and as such is the most common foundation of mathematics. ... In foundations of mathematics, Von Neumann-Bernays-Gödel set theory (NBG) is an axiom system for set theory designed to yield the same results as Zermelo-Fraenkel set theory, together with the axiom of choice (ZFC), but with only a finite number of axioms, that is without axiom schemas. ... Morse–Kelley set theory or Kelley–Morse set theory (MK or KM) is a set theory with proper classes properly extending the usual set theory ZF. It is a first order theory (though it can be confused with second-order ZF). ... In mathematical logic, New Foundations (NF) is a candidate set theory proposed by Willard van Orman Quine, obtained from a streamlined version of the theory of types of Bertrand Russell. ...

See also

This is a list of mathematical theories, by Wikipedia page. ...

References

  • Wilfrid Hodges, A shorter model theory (1997) Cambridge University Press ISBN 0-521-58713-1
  • C. C. Chang, H. J. Keisler Model theory ISBN 0720406927
  • David Marker Model Theory: An Introduction ISBN 0387987606

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m