List Of Statements Undecidable In ZFC

The mathematical statements discussed below are independent of ZFC (the canonical axiomatic set theory of contemporary mathematics, consisting of the Zermelo–Fraenkel axioms plus the axiom of choice), assuming that ZFC is consistent. A statement is independent of ZFC (sometimes phrased "undecidable in ZFC") if it can neither be proven nor disproven from the axioms of ZFC.

Axiomatic set theory

In 1931, Kurt Gödel proved his incompleteness theorems, establishing that many mathematical theories, including ZFC, cannot prove their own consistency. Assuming ω-consistency of such a theory, the consistency statement can also not be disproven, meaning it is independent. A few years later, other arithmetic statements were defined that are independent of any such theory, see for example Rosser's trick.

The following set theoretic statements are independent of ZFC, among others:
* the continuum hypothesis or CH (Gödel produced a model of ZFC in which CH is true, showing that CH cannot be disproven in ZFC; Paul Cohen later invented the method of forcing to exhibit a model of ZFC in which CH fails, showing that CH cannot be proven in ZFC. The following four independence results are also due to Gödel/Cohen.);
* the generalized continuum hypothesis (GCH);
* a related independent statement is that if a set ''x'' has fewer elements than ''y'', then ''x'' also has fewer subsets than ''y''. In particular, this statement fails when the cardinalities of the power sets of ''x'' and ''y'' coincide;
* the axiom of constructibility (''V'' = ''L'');
* the diamond principle (◊);
* Martin's axiom (MA);
* MA + ¬CH (independence shown by Solovay and Tennenbaum).
* Every Aronszajn tree is special (EATS);

We have the following chains of implications:
:''V'' = ''L'' → ◊ → CH,
:''V'' = ''L'' → GCH → CH,
:CH → MA,
and (see section on order theory):
:◊ → ¬ SH,
:MA + ¬CH → EATS → SH.

Several statements related to the existence of large cardinals cannot be proven in ZFC (assuming ZFC is consistent). These are independent of ZFC provided that they are consistent with ZFC, which most working set theorists believe to be the case. These statements are strong enough to imply the consistency of ZFC. This has the consequence (via Gödel's second incompleteness theorem) that their consistency with ZFC cannot be proven in ZFC (assuming ZFC is consistent). The following statements belong to this class:
* Existence of inaccessible cardinals
* Existence of Mahlo cardinals
* Existence of measurable cardinals (first conjectured by Ulam)
* Existence of supercompact cardinals

The following statements can be proven to be independent of ZFC assuming the consistency of a suitable large cardinal:
* Proper forcing axiom
* Open coloring axiom
* Martin's maximum
* Existence of 0^#
* Singular cardinals hypothesis
* Projective determinacy (and even the full axiom of determinacy if the axiom of choice is not assumed)

Set theory of the real line

There are many cardinal invariants of the real line, connected with measure theory and statements related to the Baire category theorem, whose exact values are independent of ZFC. While nontrivial relations can be proved between them, most cardinal invariants can be any regular cardinal between ℵ₁ and 2^ℵ₀. This is a major area of study in the set theory of the real line (see Cichon diagram). MA has a tendency to set most interesting cardinal invariants equal to 2^ℵ₀.

A subset ''X'' of the real line is a strong measure zero set if to every sequence (''ε_n'') of positive reals there exists a sequence of intervals (''I_n'') which covers ''X'' and such that ''I_n'' has length at most ''ε_n''. Borel's conjecture, that every strong measure zero set is countable, is independent of ZFC.

A subset ''X'' of the real line is $\aleph_1$-dense if every open interval contains $\aleph_1$-many elements of ''X''. Whether all $\aleph_1$-dense sets are order-isomorphic is independent of ZFC.

Order theory

Suslin's problem asks whether a specific short list of properties characterizes the ordered set of real numbers R. This is undecidable in ZFC. A ''Suslin line'' is an ordered set which satisfies this specific list of properties but is not order-isomorphic to R. The diamond principle ◊ proves the existence of a Suslin line, while MA + ¬CH implies EATS ( every Aronszajn tree is special), which in turn implies (but is not equivalent to) the nonexistence of Suslin lines. Ronald Jensen proved that CH does not imply the existence of a Suslin line.

Existence of Kurepa tree

HOME


Content is Copyleft
Website design, code, and AI is Copyrighted (c) 2014-2017 by Stephen Payne


Consider donating to Wikimedia



As an Amazon Associate I earn from qualifying purchases