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.
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 (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.
- 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
Notes
- 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, arXiv:0811.4542, Bibcode:2010NJPh...12a3019P, 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, arXiv:1202.5790, Bibcode:2013RpMP...72..133S, doi:10.1016/S0034-4877(13)00021-9
References
- 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
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 The parallels axiom P is independent of the remaining geometry axioms R there are models 1 that satisfy R and P but also models 2 3 that satisfy R but not P A sentence s is independent of a given first order theory T if T neither proves nor refutes s that is it is impossible to prove s from T and it is also impossible to prove from T that s is false Sometimes s 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 Usage noteSome authors say that s is independent of T when T simply cannot prove s and do not necessarily assert by this that T cannot refute s These authors will sometimes say s is independent of and consistent with T to indicate that T can neither prove nor refute s Independence results in set theoryMany 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 The axiom of determinacy The axiom of real determinacy AD Applications to physical theorySince 2000 logical independence has become understood as having crucial significance in the foundations of physics See alsoList of statements independent of ZFC Parallel postulate for an example in geometryNotesPaterek T Kofler J Prevedel R Klimek P Aspelmeyer M Zeilinger A Brukner C 2010 Logical independence and quantum randomness New Journal of Physics 12 013019 arXiv 0811 4542 Bibcode 2010NJPh 12a3019P doi 10 1088 1367 2630 12 1 013019 Szekely 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 arXiv 1202 5790 Bibcode 2013RpMP 72 133S doi 10 1016 S0034 4877 13 00021 9ReferencesMendelson Elliott 1997 An Introduction to Mathematical Logic 4th ed London Chapman amp 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
