Independence (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 to be undecidable from T.
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. The following statements in set theory are known to be independent of ZF, under the assumption that ZF is consistent:
The following statements cannot be proved in ZFC to be independent of ZFC, under the added hypothesis that ZFC is consistent.
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

Since 2000, logical independence has become understood as having crucial significance in the foundations of physics.