Independence (mathematical logic)
Encyclopedia
In mathematical logic
, independence refers to the unprovability of a sentence
from other sentences.
A sentence σ is independent of a given first-order theory
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
.
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.
The following statements (none of which have been proved false) cannot be proved in ZFC to be independent of ZFC, even if the added hypothesis is granted that ZFC is consistent. However, they cannot be proved in ZFC (granting that ZFC is consistent), and few working set theorists expect to find a refutation of them in ZFC.
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.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, independence refers to the unprovability of a sentence
Sentence (mathematical logic)
In mathematical logic, a sentence of a predicate logic is a boolean-valued well formed formula with no free variables. A sentence can be viewed as expressing a proposition, something that may be true or false...
from other sentences.
A sentence σ is independent of a given first-order theory
Theory (mathematical logic)
In mathematical logic, a theory is a set of sentences in a formal language. Usually a deductive system is understood from context. An element \phi\in T of a theory T is then called an axiom of the theory, and any sentence that follows from the axioms is called a theorem of the theory. Every axiom...
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
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
.
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 if 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 (ZF). The following statements in set theory are known to be independent of ZF, granting that ZF is consistent:- The axiom of choice
- The continuum hypothesisContinuum hypothesisIn mathematics, the continuum hypothesis is a hypothesis, advanced by Georg Cantor in 1874, about the possible sizes of infinite sets. It states:Establishing the truth or falsehood of the continuum hypothesis is the first of Hilbert's 23 problems presented in the year 1900...
and the generalised continuum hypothesis - The Suslin conjectureSuslin's problemIn mathematics, Suslin's problem is a question about totally ordered sets posed by Mikhail Yakovlevich Suslin in a work published posthumously in 1920....
- The existence of a Kurepa tree
The following statements (none of which have been proved false) cannot be proved in ZFC to be independent of ZFC, even if the added hypothesis is granted that ZFC is consistent. However, they cannot be proved in ZFC (granting that ZFC is consistent), and few working set theorists expect to find a refutation of them in ZFC.
- The existence of strongly inaccessible cardinals
- The existence of large cardinals
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 determinacyAxiom of determinacyThe axiom of determinacy is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person games of length ω with perfect information...
- The axiom of real determinacyAxiom of real determinacyIn mathematics, the axiom of real determinacy is an axiom in set theory. It states the following:The axiom of real determinacy is a stronger version of the axiom of determinacy, which makes the same statement about games where both players choose integers; it is inconsistent with the axiom of choice...
- AD+
See also
- List of statements undecidable in ZFC
- Parallel postulateParallel postulateIn geometry, the parallel postulate, also called Euclid's fifth postulate because it is the fifth postulate in Euclid's Elements, is a distinctive axiom in Euclidean geometry...
for an example in geometryGeometryGeometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....