In
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, a
theory
A theory is a systematic and rational form of abstract thinking about a phenomenon, or the conclusions derived from such thinking. It involves contemplative and logical reasoning, often supported by processes such as observation, experimentation, ...
is complete if it is
consistent
In deductive logic, a consistent theory is one that does not lead to a logical contradiction. A theory T is consistent if there is no formula \varphi such that both \varphi and its negation \lnot\varphi are elements of the set of consequences ...
and for every
closed formula in the theory's language, either that formula or its
negation
In logic, negation, also called the logical not or logical complement, is an operation (mathematics), operation that takes a Proposition (mathematics), proposition P to another proposition "not P", written \neg P, \mathord P, P^\prime or \over ...
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 semantics, semantic truth and syntactic Provability logic, provability in first-order logic.
The completeness theorem applies ...
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
In mathematical logic, model theory is the study of the relationship between theory (mathematical logic), formal theories (a collection of Sentence (mathematical logic), sentences in a formal language expressing statements about a Structure (mat ...
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 c ...
and
modal logic
Modal logic is a kind of logic used to represent statements about Modality (natural language), necessity and possibility. In philosophy and related fields
it is used as a tool for understanding concepts such as knowledge, obligation, and causality ...
. Their existence in a given case is usually a straightforward consequence of
Zorn's lemma
Zorn's lemma, also known as the Kuratowski–Zorn lemma, is a proposition of set theory. It states that a partially ordered set containing upper bounds for every chain (that is, every totally ordered subset) necessarily contains at least on ...
, based on the idea that a
contradiction
In traditional logic, a contradiction involves a proposition conflicting 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 , .
Models can be divided in ...
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, omi ...
*
Tarski's axioms for
Euclidean geometry
Euclidean geometry is a mathematical system attributed to ancient Greek mathematics, Greek mathematician Euclid, which he described in his textbook on geometry, ''Euclid's Elements, Elements''. Euclid's approach consists in assuming a small set ...
* The theory of
dense linear order
In mathematics, a total order 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 ( ref ...
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 . In other words, a field is algebraically closed if the fundamental theorem of algebra ...
s 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.
Def ...
s
* Every
uncountably categorical countable
In mathematics, a Set (mathematics), set is countable if either it is finite set, 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 fro ...
theory
* Every
countably categorical countable theory
*
group of three elements*
True arithmetic or any other
elementary diagram
See also
*
Lindenbaum's lemma
*
Łoś–Vaught test
References
*
Mathematical logic
Model theory
{{mathlogic-stub