Logical independence on:
[Wikipedia]
[Google]
[Amazon]
In
In mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, 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
In mathematical logic, a theory (also called a formal theory) is a set of sentences in a formal language. In most scenarios a deductive system is first understood from context, giving rise to a formal system that combines the language with deduct ...
''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
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
.)
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 ofZermelo–Fraenkel set theory
In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes suc ...
(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
In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
*The continuum hypothesis
In mathematics, specifically set theory, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states:
Or equivalently:
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this ...
and the generalized continuum hypothesis
In mathematics, specifically set theory, the continuum hypothesis (abbreviated CH) is a hypothesis about the possible sizes of infinite sets. It states:
Or equivalently:
In Zermelo–Fraenkel set theory with the axiom of choice (ZFC), this ...
*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 cardinal
In the mathematical field of set theory, a large cardinal property is a certain kind of property of transfinite cardinal numbers. Cardinals with such properties are, as the name suggests, generally very "large" (for example, bigger than the least ...
s
*The non-existence of Kurepa tree
In set theory, a Kurepa tree is a tree (''T'', <) of height ω1, each of whose levels is
...
s
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
In mathematics, the axiom of determinacy (abbreviated as AD) is a possible axiom for set theory introduced by Jan Mycielski and Hugo Steinhaus in 1962. It refers to certain two-person topological games of length ω. AD states that every game o ...
*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
In geometry, the parallel postulate is the fifth postulate in Euclid's ''Elements'' and a distinctive axiom in Euclidean geometry. It states that, in two-dimensional geometry:
If a line segment intersects two straight lines forming two interior ...
for an example in geometry
Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...
Notes
References
* * * {{Mathematical logic Mathematical logic Proof theory