In
first-order logic, a first-order theory is given by a
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
of axioms in some
language. This entry lists some of the more common examples used in
model theory
In mathematical logic, model theory is the study of the relationship between formal theories (a collection of sentences in a formal language expressing statements about a mathematical structure), and their models (those structures in which the s ...
and some of their properties.
Preliminaries
For every natural mathematical structure there is a
signature
A signature (; from la, signare, "to sign") is a handwritten (and often stylized) depiction of someone's name, nickname, or even a simple "X" or other mark that a person writes on documents as a proof of identity and intent. The writer of a ...
σ listing the constants, functions, and relations of the theory together with their
arities
Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...
, so that the object is naturally a
σ-structure. Given a signature σ there is a unique first-order language ''L''
σ that can be used to capture the first-order expressible facts about the σ-structure.
There are two common ways to specify theories:
#List or describe a set of
sentences in the language ''L''
σ, called the axioms of the theory.
#Give a set of σ-structures, and define a theory to be the set of sentences in ''L''
σ 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.
An L
σ theory may:
*be consistent: no proof of contradiction exists;
* be satisfiable: there exists a σ-structure for which the sentences of the theory are all true (by the
completeness theorem
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in the theory's language or its negation is provable
Mathematics
* The completeness of the real numbers, which implies t ...
, satisfiability is equivalent to consistency);
*be complete: for any statement, either it or its negation is provable;
*have
quantifier elimination;
*
eliminate imaginaries;
* be
finitely axiomatizable;
*be
decidable: There is an algorithm to decide which statements are provable;
*be recursively axiomatizable;
*be
model complete In model theory, a first-order theory is called model complete if every embedding of its models is an elementary embedding.
Equivalently, every first-order formula is equivalent to a universal formula.
This notion was introduced by Abraham Robinson ...
or sub-model complete;
*be
κ-categorical
In mathematical logic, a theory is categorical if it has exactly one model (up to isomorphism). Such a theory can be viewed as ''defining'' its model, uniquely characterizing the model's structure.
In first-order logic, only theories with a fini ...
: All models of
cardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...
κ are isomorphic;
*be
stable
A stable is a building in which livestock, especially horses, are kept. It most commonly means a building that is divided into separate stalls for individual animals and livestock. There are many different types of stables in use today; the ...
or unstable;
*be
ω-stable
In the mathematical field of model theory, a complete theory is called stable if it does not have too many types. One goal of classification theory is to divide all complete theories into those whose models can be classified and those whose model ...
(same as
totally transcendental
In the mathematical field of model theory, a complete theory is called stable if it does not have too many types. One goal of classification theory is to divide all complete theories into those whose models can be classified and those whose model ...
for
countable theories);
*be
superstable
In the mathematical field of model theory, a complete theory is called stable if it does not have too many types. One goal of classification theory is to divide all complete theories into those whose models can be classified and those whose model ...
*have an
atomic model;
*have a
prime model
In mathematics, and in particular model theory, a prime model is a model that is as simple as possible. Specifically, a model P is prime if it admits an elementary embedding into any model M to which it is elementarily equivalent (that is, into an ...
;
*have a
saturated model
In mathematical logic, and particularly in its subfield model theory, a saturated model ''M'' is one that realizes as many complete types as may be "reasonably expected" given its size. For example, an ultrapower model of the hyperreals is \al ...
.
Pure identity theories
The signature of the 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:
*∃''x''
1 ∃''x''
2 ¬''x''
1 = ''x''
2, ∃''x''
1 ∃''x''
2 ∃''x''
3 ¬''x''
1 = ''x''
2 ∧ ¬''x''
1 = ''x''
3 ∧ ¬''x''
2 = ''x''
3,...
These axioms define the theory of an infinite set.
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
In mathematics, Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are ...
''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 it has no models at all. By Gödel's completeness theorem, it is the only theory (for any given language) with no models. It is not the same as the theory of the
empty set
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
(in versions of first-order logic that allow a model to be empty): the theory of the empty set has exactly one model, which has no elements.
Unary relations
A set of unary relations ''P''
''i'' for ''i'' in some set ''I'' is called independent if for every two disjoint finite subsets ''A'' and ''B'' of ''I'' there is some element ''x'' such that ''P''
''i''(''x'') is true for ''i'' in ''A'' and false for ''i'' in ''B''. Independence can be expressed by a set of first-order statements.
The theory of a countable number of independent unary relations is complete, but has no
atomic models
Atomic theory is the scientific theory that matter is composed of particles called atoms. Atomic theory traces its origins to an ancient philosophical tradition known as atomism. According to this idea, if one were to take a lump of matter an ...
. It is also an example of a theory that is
superstable
In the mathematical field of model theory, a complete theory is called stable if it does not have too many types. One goal of classification theory is to divide all complete theories into those whose models can be classified and those whose model ...
but not
totally transcendental
In the mathematical field of model theory, a complete theory is called stable if it does not have too many types. One goal of classification theory is to divide all complete theories into those whose models can be classified and those whose model ...
.
Equivalence relations
The signature of
equivalence relation
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric and transitive. The equipollence relation between line segments in geometry is a common example of an equivalence relation.
Each equivalence relation ...
s has one binary infix relation symbol ~, no constants, and no functions. Equivalence relations satisfy the axioms:
*
Reflexive ∀''x'' ''x''~''x'';
*
Symmetric ∀''x'' ∀''y'' ''x''~''y'' → ''y''~''x'';
*
Transitive: ∀''x'' ∀''y'' ∀''z'' (''x''~''y'' ∧ ''y''~''z'') → ''x''~''z''.
Some first order properties of equivalence relations are:
*~ has an infinite number of
equivalence classes
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements ...
;
*~ 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 infinite
equivalence class
In mathematics, when the elements of some set S have a notion of equivalence (formalized as an equivalence relation), then one may naturally split the set S into equivalence classes. These equivalence classes are constructed so that elements a ...
es is an easy example of a theory which is ω-categorical but not categorical for any larger
cardinal
Cardinal or The Cardinal may refer to:
Animals
* Cardinal (bird) or Cardinalidae, a family of North and South American birds
**''Cardinalis'', genus of cardinal in the family Cardinalidae
**''Cardinalis cardinalis'', or northern cardinal, the ...
.
The equivalence relation ~ should not be confused with the
identity
Identity may refer to:
* Identity document
* Identity (philosophy)
* Identity (social science)
* Identity (mathematics)
Arts and entertainment Film and television
* ''Identity'' (1987 film), an Iranian film
* ''Identity'' (2003 film), ...
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 2
''T'' 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 ''E
0'' 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 signature of
orders
Order, ORDER or Orders may refer to:
* Categorization, the process in which ideas and objects are recognized, differentiated, and understood
* Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of d ...
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:
*Transitive: ∀''x'' ∀''y'' ∀''z'' ''x'' ≤ ''y''∧''y'' ≤ ''z'' → ''x'' ≤ ''z''
*Reflexive: ∀''x'' ''x ≤ ''x''
*
Antisymmetric: ∀''x'' ∀''y'' ''x'' ≤ ''y'' ∧ ''y'' ≤ ''x'' → ''x'' = ''y''
*
Partial
Partial may refer to:
Mathematics
* Partial derivative, derivative with respect to one of several variables of a function, with the other variables held constant
** ∂, a symbol that can denote a partial derivative, sometimes pronounced "partial ...
: Transitive ∧ Reflexive ∧ Antisymmetric;
*
Linear
Linearity is the property of a mathematical relationship (''function'') that can be graphically represented as a straight line. Linearity is closely related to '' proportionality''. Examples in physics include rectilinear motion, the linear r ...
(or total): Partial ∧ ∀''x'' ∀''y'' ''x'' ≤ ''y'' ∨ ''y'' ≤ ''x''
*
Dense
Density (volumetric mass density or specific mass) is the substance's mass per unit of volume. The symbol most often used for density is ''ρ'' (the lower case Greek letter rho), although the Latin letter ''D'' can also be used. Mathematically ...
: ∀''x'' ∀''z'' ''x'' < ''z'' → ∃''y'' ''x'' < ''y'' ∧ ''y'' < ''z'' ("Between any 2 distinct elements there is another element")
*There is a smallest element: ∃''x'' ∀''y'' ''x'' ≤ ''y''
*There is a largest element: ∃''x'' ∀''y'' ''y'' ≤ ''x''
*Every element has an immediate successor: ∀''x'' ∃''y'' ∀''z'' ''x'' < ''z'' ↔ ''y'' ≤ ''z''
The theory DLO of ''dense linear orders without endpoints'' (i.e. no smallest or largest element) is complete, ω-categorical, but not categorical for any uncountable cardinal. There are three other very similar theories: the theory of dense linear orders with a:
* Smallest but no largest element;
* Largest but no smallest element;
* Largest and smallest element.
Being
well ordered
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-or ...
("any non-empty subset has a minimal element") is not a first-order property; the usual definition involves quantifying over all ''subsets''.
Lattices
Lattices can be considered either as special sorts of partially ordered sets, with a signature consisting of one binary relation symbol ≤, or as
algebraic structure
In mathematics, an algebraic structure consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplication), and a finite set of ...
s with a signature consisting of two binary operations ∧ and ∨. The two approaches can be related by defining ''a'' ≤ ''b'' to mean ''a''∧''b'' = ''a''.
For two binary operations the axioms for a lattice are:
For one relation ≤ the axioms are:
*Axioms stating ≤ is a partial order, as above.
*
(existence of c = a∧b)
*
(existence of c = a∨b)
First order properties include:
*
(
distributive lattices)
*
(
modular lattice
In the branch of mathematics called order theory, a modular lattice is a lattice (order), lattice that satisfies the following self-duality (order theory), dual condition,
;Modular law: implies
where are arbitrary elements in the lattice, &nbs ...
s)
Heyting algebras can be defined as lattices with certain extra first-order properties.
Completeness is not a first order property of lattices.
Graphs
The signature of
graphs
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
has no constants or functions, and one binary relation symbol ''R'', where ''R''(''x'',''y'') is read as "there is an edge from ''x'' to ''y''".
The axioms for the theory of graphs are
*Symmetric: ∀''x'' ∀''y'' ''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, and its countable model is called the
Rado graph
In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed (with probability one) by choosing independently at random for each pair of its vertices whe ...
. A statement in the language of graphs is true in this theory if and only if the probability that an ''n''-vertex
random graph models the statement tends to 1 in the limit as ''n'' goes to infinity.
Boolean algebras
There are several different signatures and conventions used for
Boolean algebras
In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a gen ...
:
#The signature has two constants, 0 and 1, and two binary functions ∧ and ∨ ("and" and "or"), and one unary function ¬ ("not"). This can be confusing as the functions use the same symbols as the
propositional functions of first-order logic.
#In
set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly conce ...
, a common convention is that the language has two 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:
#In
algebra
Algebra () is one of the broad areas of mathematics. Roughly speaking, algebra is the study of mathematical symbols and the rules for manipulating these symbols in formulas; it is a unifying thread of almost all of mathematics.
Elementary a ...
, the usual convention is that the language has two constants, 0 and 1, and two binary functions · and +. The function · has the same meaning as ∧, but ''a''+''b'' means ''a''∨''b''∧¬(''a''∧''b''). The reason for this is that the axioms for a Boolean algebra are then just the axioms for a ring with 1 plus ∀''x'' ''x''
2 = ''x''. Unfortunately this clashes with the standard convention in set theory given above.
The axioms are:
*The axioms for a distributive lattice (see above)
*∀a ''a''∧¬''a'' = 0, ∀a ''a''∨¬''a'' = 1 (properties of negation)
*Some authors add the extra axiom ¬0 = 1, to exclude the trivial algebra with one element.
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:
*Atomic: ∀''x'' ''x'' = 0 ∨ ∃''y'' ''y'' ≤ ''x'' ∧ atom(''y'')
*Atomless: ∀''x'' ¬atom(''x'')
The theory of atomless Boolean algebras is ω-categorical and complete.
For any Boolean algebra ''B'', there are several invariants defined as follows.
*the ideal ''I''(''B'') consists of elements that are the sum of an atomic and an atomless element (an element with no atoms below it).
*The quotient algebras ''B''
''i'' of ''B'' are defined inductively by ''B''
0=''B'', ''B''
''k''+1 = ''B''
''k''/''I''(''B''
''k'').
*The invariant ''m''(''B'') is the smallest integer such that ''B''
''m''+1 is trivial, or ∞ if no such integer exists.
*If ''m''(''B'') is finite, the invariant ''n''(''B'') is the number of atoms of ''B''
''m''(''B'') if this number is finite, or ∞ if this number is infinite.
*The invariant ''l''(''B'') is 0 if ''B''
''m''(''B'') is atomic or if ''m''(''B'') is ∞, and 1 otherwise.
Then two Boolean algebras are
elementarily equivalent 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.
If ''N'' is a substructure of ''M'', one often ...
if and only if their invariants ''l'', ''m'', and ''n'' are the same. In other words, the values of these invariants classify the possible completions of the theory of Boolean algebras. So the possible complete theories are:
*The trivial algebra (if this is allowed; sometimes 0≠1 is included as an axiom.)
*The theory with ''m'' = ∞
*The theories with ''m'' a natural number, ''n'' a natural number or ∞, and ''l'' = 0 or 1 (with ''l'' = 0 if ''n'' = 0).
Groups
The signature of
group theory
In abstract algebra, group theory studies the algebraic structures known as group (mathematics), groups.
The concept of a group is central to abstract algebra: other well-known algebraic structures, such as ring (mathematics), rings, field ...
has one constant 1 (the identity), one function of arity 1 (the inverse) whose value on ''t'' is denoted by ''t''
−1, and one function of arity 2, which is usually omitted from terms. For any integer ''n'', ''t''
''n'' is an abbreviation for the obvious term for the ''n''th power of ''t''.
Groups are defined by the axioms
*''Identity'': ∀''x'' 1''x'' = ''x'' ∧ ''x''1 = ''x''
*''Inverse'': ∀''x'' ''x''
−1''x'' = ''1'' ∧ ''xx''
−1 = ''1''
*''Associativity'': ∀''x''∀''y''∀''z'' (''xy'')''z'' = ''x''(''yz'')
Some properties of groups that can be defined in the first-order language of groups are:
*
Abelian
Abelian may refer to:
Mathematics Group theory
* Abelian group, a group in which the binary operation is commutative
** Category of abelian groups (Ab), has abelian groups as objects and group homomorphisms as morphisms
* Metabelian group, a grou ...
: ∀''x'' ∀''y'' ''xy'' = ''yx''.
*
Torsion free: ∀''x'' ''x''
2 = 1→''x'' = 1, ∀''x'' ''x''
3 = 1 → ''x'' = 1, ∀''x'' ''x''
4 = 1 → ''x'' = 1, ...
*
Divisible: ∀''x'' ∃''y'' ''y''
2 = ''x'', ∀''x'' ∃''y'' ''y''
3 = ''x'', ∀''x'' ∃''y'' ''y''
4 = ''x'', ...
*Infinite (as in identity theory)
*
Exponent
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
''n'' (for any fixed positive integer ''n''): ∀''x'' ''x''
''n'' = 1
*
Nilpotent
In mathematics, an element x of a ring R is called nilpotent if there exists some positive integer n, called the index (or sometimes the degree), such that x^n=0.
The term was introduced by Benjamin Peirce in the context of his work on the class ...
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
A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
).
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
Free may refer to:
Concept
* Freedom, having the ability to do something, without having to obey anyone/anything
* Freethought, a position that beliefs should be formed only on the basis of logic, reason, and empiricism
* Emancipate, to procur ...
, or
simple
Simple or SIMPLE may refer to:
*Simplicity, the state or quality of being simple
Arts and entertainment
* ''Simple'' (album), by Andy Yorke, 2008, and its title track
* "Simple" (Florida Georgia Line song), 2018
* "Simple", a song by Johnn ...
, 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 signature of (unital)
rings has two constants 0 and 1, two binary functions + and ×, and, optionally, one unary negation 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 ring
In mathematics, a commutative ring is a ring in which the multiplication operation is commutative. The study of commutative rings is called commutative algebra. Complementarily, noncommutative algebra is the study of ring properties that are not sp ...
s
The axioms for rings plus ∀''x'' ∀''y'' ''xy'' = ''yx''.
Field
Field may refer to:
Expanses of open ground
* Field (agriculture), an area of land used for agricultural purposes
* Airfield, an aerodrome that lacks the infrastructure of an airport
* Battlefield
* Lawn, an area of mowed grass
* Meadow, a grass ...
s
The axioms for commutative rings plus ∀''x'' (¬ ''x'' = 0 → ∃''y'' ''xy'' = 1) and ¬ 1 = 0.
Many of the examples given here have only universal, or ''algebraic'' axioms. The
class
Class or The Class may refer to:
Common uses not otherwise categorized
* Class (biology), a taxonomic rank
* Class (knowledge representation), a collection of individuals or objects
* Class (philosophy), an analytical concept used differentl ...
of structures satisfying such a theory has the property of being closed under substructure. For example, a subset of a group closed under the group actions of multiplication and inverse is again a group. Since the signature of fields does not usually include multiplicative and additive inverse, the axioms for inverses are not universal, and therefore a substructure of a field closed under addition and multiplication is not always a field. This can be remedied by adding unary inverse functions to the language.
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:
*∀ ''a''
1 ∀ ''a''
2... ∀ ''a''
''n'' ∃''x'' (...((''x''+''a''
1)''x'' +''a''
2)''x''+...)''x''+''a''
''n'' = 0
Perfect fields
The axioms for fields, plus axioms for each prime number ''p'' stating that if ''p'' 1 = 0 (i.e. the field has
characteristic ''p''), then every field element has a ''p''th root.
Algebraically closed fields of characteristic ''p''
The axioms for fields, plus for every positive ''n'' the axiom that all polynomials of degree ''n'' have a root, plus axioms fixing the characteristic. The classical examples of complete theories.
Categorical in all uncountable cardinals. The theory ''ACF''
p has a ''universal domain property'', in the sense that every structure ''N'' satisfying the universal axioms of ''ACF''
p is a substructure of a sufficiently large algebraically closed field
, and additionally any two such embeddings ''N'' → ''M'' induce an
automorphism
In mathematics, an automorphism is an isomorphism from a mathematical object to itself. It is, in some sense, a symmetry of the object, and a way of mapping the object to itself while preserving all of its structure. The set of all automorphisms ...
of ''M''.
Finite field
In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s
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
In number theory, the Chevalley–Warning theorem implies that certain polynomial, polynomial equations in sufficiently many variables over a finite field have solutions. It was proved by and a slightly weaker form of the theorem, known as Cheval ...
, 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.
Formally real fields
The axioms for fields plus, for every positive integer ''n'', the axiom:
* ∀ ''a''
1 ∀ ''a''
2... ∀ ''a''
''n'' ''a''
1''a''
1+''a''
2''a''
2+ ...+''a''
''n''''a''
''n''=0 → ''a''
''1''=0∧''a''
''2''=0∧ ... ∧''a''
''n''=0.
That is, 0 is not a non-trivial sum of squares.
Real closed fields
The axioms for formally real fields plus the axioms:
*∀''x'' ∃''y'' (''x''=''yy'' ∨ ''x''+''yy''= 0);
*for every odd positive integer ''n'', the axiom stating that every polynomial of degree ''n'' has a root.
The theory of real closed fields is effective and complete and therefore decidable (the
Tarski–Seidenberg theorem In mathematics, the Tarski–Seidenberg theorem states that a set in (''n'' + 1)-dimensional space defined by polynomial equations and inequalities can be projected down onto ''n''-dimensional space, and the resulting set is still defina ...
). The addition of further function symbols (e.g., the exponential function, the sine function)
may change decidability.
''p''-adic fields
showed that the theory of ''p''-adic fields is decidable and gave a set of axioms for it.
[ ]
Geometry
Axioms for various systems of geometry usually use a typed language, with the different types corresponding to different geometric objects such as points, lines, circles, planes, and so on. The signature will often consist of binary incidence relations between objects of different types; for example, the relation that a point lies on a line. The signature may have more complicated relations; for example ordered geometry might have a ternary "betweenness" relation for 3 points, which says whether one lies between two others, or a "congruence" relation between 2 pairs of points.
Some examples of axiomatized systems of geometry include
ordered geometry,
absolute geometry,
affine geometry,
Euclidean geometry,
projective geometry, and
hyperbolic geometry. For each of these geometries there are many different and inequivalent systems of axioms for various dimensions. Some of these axiom systems include "completeness" axioms that are not first order.
As a typical example, the axioms for projective geometry use 2 types, points and lines, and a binary incidence relation between points and lines. If point and line variables are indicated by small and capital letter, and ''a'' incident to ''A'' is written as ''aA'', then one set of axioms is
*
(There is a line through any 2 distinct points ''a'',''b'' ...)
*
(... which is unique)
*
(Veblen's axiom: if ''ab'' and ''cd'' lie on intersecting lines, then so do ''ac'' and ''bd''.)
*
(Every line has at least 3 points)
Euclid did not state all the axioms for Euclidean geometry explicitly, and the first complete list was given by Hilbert in
Hilbert's axioms. This is not a first order axiomatization as one of Hilbert's axioms is a second order completeness axiom.
Tarski's axioms
Tarski's axioms, due to Alfred Tarski, are an axiom set for the substantial fragment of Euclidean geometry that is formulable in first-order logic with identity, and requiring no set theory (i.e., that part of Euclidean geometry that is formulabl ...
are a first order axiomatization of Euclidean geometry. Tarski showed this axiom system is complete and decidable by relating it to the complete and decidable theory of real closed fields.
Differential algebra
* The theory DF of
differential field
In mathematics, differential rings, differential fields, and differential algebras are rings, fields, and algebras equipped with finitely many derivations, which are unary functions that are linear and satisfy the Leibniz product rule. A natur ...
s.
The signature is that of fields (0, 1, +, −, ×) together with a unary function ∂, the derivation.
The axioms are those for fields together with
:
:
For this theory one can add the condition that the characteristic is ''p'', a prime or zero,
to get the theory DF
''p'' of differential fields of characteristic ''p'' (and similarly with the other theories below).
If ''K'' is a differential field then the field of constants
The theory of differentially perfect fields is the theory of differential fields together with the condition that the field of constants is perfect; in other words, for each prime ''p'' it has the axiom:
:
(There is little point in demanding that the whole field should be a
perfect field, because in non-zero characteristic this implies the differential is 0.)
For technical reasons to do with
quantifier elimination, it is sometimes more convenient to force the constant field to be perfect by adding a new symbol ''r'' to the signature with the axioms
:
:
* The theory of
differentially closed fields (DCF) is the theory of differentially perfect fields with axioms saying that if ''f'' and ''g'' are
differential polynomials and the
separant In mathematics, a differential field ''K'' is differentially closed if every finite system of differential equations with a solution in some differential field extending ''K'' already has a solution in ''K''. This concept was introduced by . Differe ...
of ''f'' is nonzero and ''g''≠0 and ''f'' has order greater than that of ''g'', then there is some ''x'' in the field with ''f''(''x'')=0 and ''g''(''x'')≠0.
Addition
The theory of the natural numbers with a successor function has signature consisting of a constant 0 and a unary function ''S'' ("successor": ''S''(''x'') is interpreted as ''x''+1), and has axioms:
# ∀x ¬ Sx = 0
# ∀x∀y Sx = Sy → x = y
#Let ''P''(''x'') be a
first-order formula with a single
free variable ''x''. Then the following formula is an axiom:
:(''P''(0) ∧ ∀''x''(''P''(''x'')→''P''(''Sx''))) → ∀''y'' ''P''(''y'').
The last axiom (induction) can be replaced by the axioms
*For each integer ''n''>0, the axiom ∀x SSS...Sx ≠ x (with ''n'' copies of ''S'')
* ∀x ¬ x = 0 → ∃y Sy = x
The theory of the natural numbers with a successor function is complete and decidable, and is κ-categorical for uncountable κ but not for countable κ.
Presburger arithmetic is the theory of the natural numbers under addition, with signature consisting of a constant 0, a unary function ''S'', and a binary function +. It is complete and decidable. The axioms are
# ∀x ¬ Sx = 0
# ∀x∀y Sx = Sy → x = y
# ∀x x + 0 = x
# ∀x∀y x + Sy = S(x + y)
#Let ''P''(''x'') be a first-order formula with a single free variable ''x''. Then the following formula is an axiom:
:(''P''(0) ∧ ∀''x''(''P''(''x'')→''P''(''Sx''))) → ∀''y'' ''P''(''y'').
Arithmetic
Many of the first order theories described above can be extended to complete recursively enumerable consistent theories. This is no longer true for most of the following theories; they can usually encode both multiplication and addition of natural numbers, and this gives them enough power to encode themselves, which implies that
Gödel's incompleteness theorem applies and the theories can no longer be both complete and recursively enumerable (unless they are inconsistent).
The signature of a theory of arithmetic has:
*The constant 0;
*The
unary function, the
successor function
In mathematics, the successor function or successor operation sends a natural number to the next one. The successor function is denoted by ''S'', so ''S''(''n'') = ''n'' +1. For example, ''S''(1) = 2 and ''S''(2) = 3. The successor functio ...
, here denoted by prefix ''S'', or by prefix σ or postfix ′ elsewhere;
*Two
binary function
In mathematics, a binary function (also called bivariate function, or function of two variables) is a function that takes two inputs.
Precisely stated, a function f is binary if there exists sets X, Y, Z such that
:\,f \colon X \times Y \rightar ...
s, denoted by infix + and ×, called "addition" and "multiplication."
Some authors take the signature to contain a constant 1 instead of the function ''S'', then define ''S'' in the obvious way as ''St'' = 1 + ''t''.
Robinson arithmetic
In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q is ...
(also called Q). Axioms (1) and (2) govern the distinguished element 0. (3) assures that ''S'' is an
injection
Injection or injected may refer to:
Science and technology
* Injective function, a mathematical function mapping distinct arguments to distinct values
* Injection (medicine), insertion of liquid into the body with a syringe
* Injection, in broadca ...
. Axioms (4) and (5) are the standard recursive definition of addition; (6) and (7) do the same for multiplication. Robinson arithmetic can be thought of as Peano arithmetic without induction. Q is a weak theory for which
Gödel's incompleteness theorem holds.
Axioms:
# ∀''x'' ¬ S''x'' = 0
# ∀''x'' ¬ ''x'' = 0 → ∃''y'' S''y'' = ''x''
# ∀''x''∀''y'' S''x'' = S''y'' → ''x'' = ''y''
# ∀''x'' ''x'' + 0 = ''x''
# ∀''x''∀''y'' ''x'' + S''y'' = S(''x'' + ''y'')
# ∀''x'' ''x'' × 0 = 0
# ∀''x''∀''y'' ''x'' × S''y'' = (''x'' × ''y'') + ''x''.
IΣ
n is first order Peano arithmetic with induction restricted to
Σn formulas (for ''n'' = 0, 1, 2, ...). The theory IΣ
0 is often denoted by IΔ
0. This is a series of more and more powerful fragments of Peano arithmetic. The case ''n'' = 1 has about the same strength as
primitive recursive arithmetic
Primitive recursive arithmetic (PRA) is a quantifier-free formalization of the natural numbers. It was first proposed by Norwegian mathematician , reprinted in translation in as a formalization of his finitist conception of the foundations of ar ...
(PRA).
Exponential function arithmetic
In proof theory, a branch of mathematical logic, elementary function arithmetic (EFA), also called elementary arithmetic and exponential function arithmetic,C. Smoryński, "Nonstandard Models and Related Developments" (p. 217). From ''Harvey Frie ...
(EFA) is IΣ
0 with an axiom stating that ''x''
''y'' exists for all ''x'' and ''y'' (with the usual properties).
First order
Peano arithmetic
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 u ...
, PA. The "standard" theory of arithmetic. The axioms are the axioms of
Robinson arithmetic
In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q is ...
above, together with the axiom scheme of induction:
*
for any formula φ in the language of PA. φ may contain free variables other than ''x''.
Kurt Gödel
Kurt Friedrich Gödel ( , ; April 28, 1906 – January 14, 1978) was a logician, mathematician, and philosopher. Considered along with Aristotle and Gottlob Frege to be one of the most significant logicians in history, Gödel had an imme ...
's 1931 paper proved that PA is incomplete, and has no consistent recursively enumerable completions.
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.
For the real numbers, the situation is slightly different: The case that includes just addition and multiplication cannot encode the integers, and hence
Gödel's incompleteness theorem does not apply.
Complications arise when adding further function symbols (e.g., exponentiation).
Second order arithmetic
Second-order arithmetic 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 signature will typically be the signature 0, ''S'', +, × of arithmetic, together with a membership relation ∈ between integers and subsets (though there are numerous minor variations). The axioms are those of
Robinson arithmetic
In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q is ...
, together with axiom schemes of
induction
Induction, Inducible or Inductive may refer to:
Biology and medicine
* Labor induction (birth/pregnancy)
* Induction chemotherapy, in medicine
* Induced stem cells, stem cells derived from somatic, reproductive, pluripotent or other cell t ...
and
comprehension.
There are many different subtheories of second order arithmetic that differ in which formulas are allowed in the induction and comprehension schemes.
In order of increasing strength, five of the most common systems
are
*
, Recursive Comprehension
*
, Weak König's lemma
*
, Arithmetical comprehension
*
, Arithmetical Transfinite Recursion
*
,
comprehension
These are defined in detail in the articles on
second order arithmetic
In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation of mathematics, foundation for much, but not all, ...
and
reverse mathematics.
Set theories
The usual signature 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:
#Use first-order logic with two types.
#Use ordinary first-order logic, but add a new unary predicate "Set", where "Set(''t'')" means informally "''t'' is a set".
#Use ordinary first-order logic, and instead of adding a new predicate to the language, treat "Set(''t'')" as an abbreviation for "∃''y'' ''t''∈''y''"
Some first order set theories include:
*Weak theories lacking
powerset
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is postu ...
s:
**
S' (Tarski, Mostowski, and Robinson, 1953); (finitely axiomatizable)
**
Kripke–Platek set theory; KP;
**
Pocket set theory
Pocket set theory (PST) is an alternative set theory in which there are only two infinite cardinal numbers, ℵ0 (aleph-naught, the cardinality of the set of all natural numbers) and ''c'' (the cardinality of the continuum). The theory was first s ...
**
General set theory, GST
**
Constructive set theory, CZF
*
Mac Lane set theory and
Elementary topos theory
In mathematics, a topos (, ; plural topoi or , or toposes) is a category (mathematics), category that behaves like the category of Sheaf (mathematics), sheaves of Set (mathematics), sets on a topological space (or more generally: on a Site (math ...
*
Zermelo set theory; Z
*
Zermelo–Fraenkel set theory
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 ...
; ZF, ZFC;
*
Von Neumann–Bernays–Gödel set theory; NBG; (finitely axiomatizable)
*
Ackermann set theory
In mathematics and logic, Ackermann set theory (AST) is an axiomatic set theory proposed by Wilhelm Ackermann in 1956.
The language
AST is formulated in first-order logic. The formal language, language L_ of AST contains one binary relation \in ...
;
*
Scott–Potter set theory
*
New Foundations
In mathematical logic, New Foundations (NF) is an axiomatic set theory, conceived by Willard Van Orman Quine as a simplification of the theory of types of ''Principia Mathematica''. Quine first proposed NF in a 1937 article titled "New Foundations ...
; NF (finitely axiomatizable)
*
Positive set theory
*
Morse–Kelley set theory
In the foundations of mathematics, Morse–Kelley set theory (MK), Kelley–Morse set theory (KM), Morse–Tarski set theory (MT), Quine–Morse set theory (QM) or the system of Quine and Morse is a first-order axiomatic set theory that is closely ...
; MK;
*
Tarski–Grothendieck set theory
Tarski–Grothendieck set theory (TG, named after mathematicians Alfred Tarski and Alexander Grothendieck) is an axiomatic set theory. It is a non-conservative extension of Zermelo–Fraenkel set theory (ZFC) and is distinguished from other axio ...
; TG;
Some extra first order axioms that can be added to one of these (usually ZF) include:
*
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
,
axiom of dependent choice In mathematics, the axiom of dependent choice, denoted by \mathsf , is a weak form of the axiom of choice ( \mathsf ) that is still sufficient to develop most of real analysis. It was introduced by Paul Bernays in a 1942 article that explores whi ...
*
Generalized continuum hypothesis
*
Martin's axiom
In the mathematical field of set theory, Martin's axiom, introduced by Donald A. Martin and Robert M. Solovay, is a statement that is independent of the usual axioms of ZFC set theory. It is implied by the continuum hypothesis, but it is consist ...
(usually together with the negation of the continuum hypothesis),
Martin's maximum In set theory, a branch of mathematical logic, Martin's maximum, introduced by and named after Donald Martin, is a generalization of the proper forcing axiom, itself a generalization of Martin's axiom. It represents the broadest class of forcing ...
*
◊ and
♣
*
Axiom of constructibility (V=L)
*
proper forcing axiom In the mathematical field of set theory, the proper forcing axiom (''PFA'') is a significant strengthening of Martin's axiom, where forcings with the countable chain condition (ccc) are replaced by proper forcings.
Statement
A forcing or parti ...
*
analytic determinacy
Generally speaking, analytic (from el, ἀναλυτικός, ''analytikos'') refers to the "having the ability to analyze" or "division into elements or principles".
Analytic or analytical can also have the following meanings:
Chemistry
* A ...
,
projective determinacy In mathematical logic, projective determinacy is the special case of the axiom of determinacy applying only to projective sets.
The axiom of projective determinacy, abbreviated PD, states that for any two-player infinite game of perfect informatio ...
,
Axiom of determinacy
*Many
large cardinal axioms
See also
*
Glossary of areas of mathematics
Mathematics is a broad subject that is commonly divided in many areas that may be defined by their objects of study, by the used methods, or by both. For example, analytic number theory is a subarea of number theory devoted to the use of methods ...
*
List of mathematical theories
This is a list of mathematical theories.
{{columns-list, colwidth=20em,
*Algebraic K-theory
*Almgren–Pitts min-max theory
*Approximation theory
*Asymptotic theory
*Automata theory
*Bifurcation theory
*Braid theory
*Brill–Noether theory
* Cat ...
References
Further reading
*
*
* {{ citation , last=Marker , first=David , title= Model Theory: An Introduction , publisher=Springer , year=2002 , isbn=0-387-98760-6, series=
Graduate Texts in Mathematics
Graduate Texts in Mathematics (GTM) (ISSN 0072-5285) is a series of graduate-level textbooks in mathematics published by Springer-Verlag. The books in this series, like the other Springer-Verlag mathematics series, are yellow books of a standard s ...
, volume= 217
First-order theories, List of
First-order theories, List of
First-order theories
In first-order 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.
Preliminaries
For every natural mathematical structure ...