In
mathematical logic
Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal ...
, a
theory
A theory is a rational type of abstract thinking about a phenomenon, or the results of such thinking. The process of contemplative and rational thinking is often associated with such processes as observational study or research. Theories may b ...
is complete if it is
consistent
In classical deductive logic, a consistent theory is one that does not lead to a logical contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent ...
and for every
closed formula in the theory's language, either that formula or its
negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...
is provable. That is, for every
sentence the theory
contains the sentence or its negation but not both (that is, either
or
). Recursively axiomatizable
first-order theories that are consistent and rich enough to allow general mathematical reasoning to be formulated cannot be complete, as demonstrated by
Gödel's first incompleteness theorem.
This sense of ''complete'' is distinct from the notion of a complete ''logic'', which asserts that for every theory that can be formulated in the logic, all semantically valid statements are provable theorems (for an appropriate sense of "semantically valid").
Gödel's completeness theorem
Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic.
The completeness theorem applies to any first-order theory: I ...
is about this latter kind of completeness.
Complete theories are closed under a number of conditions internally modelling the
T-schema:
* For a set of formulas
:
if and only if
and
,
* For a set of formulas
:
if and only if
or
.
Maximal consistent sets are a fundamental tool in the
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 ...
of
classical logic
Classical logic (or standard logic or Frege-Russell logic) is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this class ...
and
modal logic
Modal logic is a collection of formal systems developed to represent statements about necessity and possibility. It plays a major role in philosophy of language, epistemology, metaphysics, and natural language semantics. Modal logics extend other ...
. Their existence in a given case is usually a straightforward consequence of
Zorn's lemma, based on the idea that a
contradiction involves use of only finitely many premises. In the case of modal logics, the collection of maximal consistent sets extending a theory ''T'' (closed under the necessitation rule) can be given the structure of a
model
A model is an informative representation of an object, person or system. The term originally denoted the plans of a building in late 16th-century English, and derived via French and Italian ultimately from Latin ''modulus'', a measure.
Models c ...
of ''T'', called the canonical model.
Examples
Some examples of complete theories are:
*
Presburger arithmetic
*
Tarski's axioms for
Euclidean geometry
Euclidean geometry is a mathematical system attributed to ancient Greek mathematician Euclid, which he described in his textbook on geometry: the '' Elements''. Euclid's approach consists in assuming a small set of intuitively appealing axioms ...
* The theory of
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. Mathematical ...
linear order
In mathematics, a total or linear order is a partial order in which any two elements are comparable. That is, a total order is a binary relation \leq on some set X, which satisfies the following for all a, b and c in X:
# a \leq a ( reflexive) ...
s without endpoints
* The theory of
algebraically closed field
In mathematics, a field is algebraically closed if every non-constant polynomial in (the univariate polynomial ring with coefficients in ) has a root in .
Examples
As an example, the field of real numbers is not algebraically closed, becaus ...
s of a given
characteristic
* The theory of
real closed fields
* Every
uncountably categorical countable
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers; ...
theory
* Every
countably categorical countable theory
*
group of three elements
See also
*
Lindenbaum's lemma
*
Łoś–Vaught test In model theory, a branch of mathematical logic, the Łoś–Vaught test is a criterion for a theory to be complete, unable to be augmented without becoming inconsistent. For theories in classical logic
Classical logic (or standard logic or Frege-R ...
References
*
Mathematical logic
Model theory
{{mathlogic-stub