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 be ...
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 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: ...
is about this latter kind of completeness.
Complete theories are closed under a number of conditions internally modelling the
T-schema
The T-schema ("truth schema", not to be confused with " Convention T") is used to check if an inductive definition of truth is valid, which lies at the heart of any realisation of Alfred Tarski's semantic theory of truth. Some authors refer to it ...
:
* 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 of
classical logic and
modal logic. Their existence in a given case is usually a straightforward consequence of
Zorn's lemma, based on the idea that a
contradiction
In traditional logic, a contradiction occurs when a proposition conflicts either with itself or established fact. It is often used as a tool to detect disingenuous beliefs and bias. Illustrating a general tendency in applied logic, Aristotle's ...
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
Presburger arithmetic is the first-order theory of the natural numbers with addition, named in honor of Mojżesz Presburger, who introduced it in 1929. The signature of Presburger arithmetic contains only the addition operation and equality, omit ...
*
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 ...
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. Mathematically ...
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 fields of a given
characteristic
* The theory of
real closed field
In mathematics, a real closed field is a field ''F'' that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.
D ...
s
* 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 In mathematical logic, Lindenbaum's lemma, named after Adolf Lindenbaum, states that any consistent theory of predicate logic can be extended to a complete consistent theory. The lemma is a special case of the ultrafilter lemma for Boolean algebra ...
*
Łoś–Vaught test In model theory, a branch of mathematical logic, the Łoś–Vaught test is a criterion for a theory to be complete
Complete may refer to:
Logic
* Completeness (logic)
* Completeness of a theory, the property of a theory that every formula in th ...
References
*
Mathematical logic
Model theory
{{mathlogic-stub