Independence (mathematical logic)
Term in mathematical logic
In mathematical logic, independence is the unprovability of some specific sentence from some specific set of other sentences. The sentences in this set are referred to as "axioms".
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 concept is unrelated to the idea of "decidability" as in a decision problem.)
A theory T is independent if no axiom in T is provable from the remaining axioms in T. A theory for which there is an independent set of axioms is independently axiomatizable.
01Usage 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 σ.
02Independence 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, under the assumption that ZF is consistent:
- The axiom of choice
- The continuum hypothesis and the generalized continuum hypothesis
- The Suslin conjecture
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 cardinals
- The existence of large cardinals
- 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.
03Complete (strong) independence
A set of sentences is independent, or simply independent, if no sentence in the set is provable from the others. This is equivalent to saying that for each sentence in the set there exists an interpretation under which that sentence is false but all the others are true.
There is another sense of independence, called complete independence, or strong independence. A set of sentences is completely independent if for every subset, there exists an interpretation under which all the members of that subset are true and all the others are false. This is equivalent to saying that all combinations of the sentences being true or false are consistent.
04Applications to physical theory
Since 2000, logical independence has become understood as having crucial significance in the foundations of physics.
Sources and credits
This article is adapted from the Wikipedia article “Independence (mathematical logic)”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.
Images, from Wikimedia Commons:
- Euclidian and non euclidian geometry.png by Unknown author, CC BY-SA 3.0
Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.
