Independence (mathematical logic)
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.
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 (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.
Applications to physical theory
- Paterek, T.; Kofler, J.; Prevedel, R.; Klimek, P.; Aspelmeyer, M.; Zeilinger, A.; Brukner, Č. (2010), "Logical independence and quantum randomness", New Journal of Physics, 12: 013019, Bibcode:2010NJPh...12a3019P, arXiv: , doi:10.1088/1367-2630/12/1/013019
- Székely, Gergely (2013), "The Existence of Superluminal Particles is Consistent with the Kinematics of Einstein's Special Theory of Relativity", Reports on Mathematical Physics, 72 (2): 133–152, Bibcode:2013RpMP...72..133S, arXiv: , doi:10.1016/S0034-4877(13)00021-9
- Mendelson, Elliott (1997), An Introduction to Mathematical Logic (4th ed.), London: Chapman & Hall, ISBN 978-0-412-80830-2
- Monk, J. Donald (1976), Mathematical Logic, Graduate Texts in Mathematics, Berlin, New York: Springer-Verlag, ISBN 978-0-387-90170-1
- Stabler, Edward Russell (1948), An introduction to mathematical thought, Reading, Massachusetts: Addison-Wesley