In
mathematical logic
Mathematical logic is the study of logic, 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 for ...
, independence is the unprovability of a
sentence from other sentences.
A
sentence σ is independent of a given
first-order theory
First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantif ...
''T'' if ''T'' neither proves nor refutes σ; that is, it is impossible to prove σ from ''T'', and it is also impossible to prove from ''T'' that σ is false. Sometimes, σ is said (synonymously) to be undecidable from ''T''; this is not the same meaning of "
decidability" as in a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whethe ...
.
A theory ''T'' is independent if each axiom in ''T'' is not provable from the remaining axioms in ''T''. A theory for which there is an independent set of axioms is independently axiomatizable.
Usage note
Some authors say that σ is independent of ''T'' when ''T'' simply cannot prove σ, and do not necessarily assert by this that ''T'' cannot refute σ. These authors will sometimes say "σ is independent of and consistent with ''T''" to indicate that ''T'' can neither prove nor refute σ.
Independence results in set theory
Many interesting statements in set theory are independent of
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). The following statements in set theory are known to be independent of ZF, under the assumption that ZF is consistent:
*The
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 ...
*The
continuum hypothesis and the
generalized continuum hypothesis
*The
Suslin conjecture In mathematics, Suslin's problem is a question about totally ordered sets posed by and published posthumously.
It has been shown to be independent of the standard axiomatic system of set theory known as ZFC: showed that the statement can neither ...
The following statements (none of which have been proved false) cannot be proved in ZFC (the Zermelo-Fraenkel set theory plus the axiom of choice) to be independent of ZFC, under the added hypothesis that ZFC is consistent.
*The existence of
strongly inaccessible cardinal
In set theory, an uncountable cardinal is inaccessible if it cannot be obtained from smaller cardinals by the usual operations of cardinal arithmetic. More precisely, a cardinal is strongly inaccessible if it is uncountable, it is not a sum of f ...
s
*The existence of
large cardinal
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least Î ...
s
*The non-existence of
Kurepa trees
The following statements are inconsistent with the axiom of choice, and therefore with ZFC. However they are probably independent of ZF, in a corresponding sense to the above: They cannot be proved in ZF, and few working set theorists expect to find a refutation in ZF. However ZF cannot prove that they are independent of ZF, even with the added hypothesis that ZF is consistent.
*The
axiom of determinacy
*The
axiom of real determinacy
*
AD+
Applications to physical theory
Since 2000, logical independence has become understood as having crucial significance in the foundations of physics.
See also
*
List of statements independent of ZFC
*
Parallel postulate for an example in
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
Notes
References
*
*
*
{{Mathematical logic
Mathematical logic
Proof theory