List of statements undecidable in ZFC
The mathematical statements discussed below are provably undecidable in ZFC (the Zermelo–Fraenkel axioms plus the axiom of choice, the canonical axiomatic set theory of contemporary mathematics), assuming that ZFC is consistent. A statement is undecidable in ZFC (a.k.a. independent of ZFC) if it can neither be proven nor disproven from the axioms of ZFC.
Moreover the following statements are undecidable in ZFC:
- The continuum hypothesis (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 undecidability results are also due to Gödel/Cohen.)
- The generalized continuum hypothesis (GCH);
- The axiom of constructibility (V = L);
- The diamond principle (◊);
- Martin's axiom (MA);
- MA + ¬CH. (Undecidability shown by Solovay and Tennenbaum.)
We have the following chains of implication:
- V = L → ◊ → CH.
- V = L → GCH → CH.
- CH → MA
Another statement that is undecidable in ZFC is:
- If the set S has fewer elements than T (in the sense of cardinality), then S also has fewer subsets than T.
Several statements related to the existence of large cardinals cannot be proven in ZFC (assuming ZFC is consistent). These are undecidable in 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 undecidable in 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
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 ℵ1 and 2ℵ0. 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ℵ0.
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 (In) which covers X and such that In has length at most εn. Borel's conjecture, that every strong measure zero set is countable, is undecidable in ZFC.
A subset X of the real line is -dense if every open interval contains -many elements of X. Whether all -dense sets are order-isomorphic is undecidable in ZFC.
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 a partition of the ordinal number into two colors with no monochromatic uncountable sequentially closed subset is undecidable in ZFC, ZFC + CH, and ZFC + ¬CH, assuming consistency of a Mahlo cardinal. This theorem of Shelah answers a question of H. Friedman.
In 1973, Saharon Shelah showed that the Whitehead problem ("is every abelian group A with Ext1(A, Z) = 0 a free abelian group?") is undecidable in ZFC. An abelian group with Ext1(A, Z) = 0 is called a Whitehead group; MA + ¬CH proves the existence of a non-free Whitehead group, while V = L proves that all Whitehead groups are free. In one of the earliest applications of proper forcing, Shelah constructed a model of ZFC + CH in which there is a non-free Whitehead group.
Consider the ring A=R[x,y,z] of polynomials in three variables over the real numbers and its field of fractions M=R(x,y,z). The projective dimension of M as A-module is either 2 or 3, but it is undecidable in ZFC whether it is equal to 2; it is equal to 2 if and only if CH holds.
One can write down a concrete polynomial P∈Z[x1,...x9] such the statement "there are integers m1,...,m9 with P(m1,...,m9)=0" can neither be proven nor disproven in ZFC (assuming ZFC is consistent). This follows from Yuri Matiyasevich's resolution of Hilbert's tenth problem; the polynomial is constructed so that it has an integer root if and only if ZFC is inconsistent.
A stronger version of Fubini's theorem for positive functions, where the function is no longer assumed to be measurable but merely that the two iterated integrals are well defined and exist, is undecidable in ZFC. On the one hand, CH implies that there exists a function on the unit square whose iterated integrals are not equal — the function is simply the indicator function of an ordering of [0, 1] equivalent to a well ordering of the cardinal ω1. A similar example can be constructed using MA. On the other hand, the consistency of the strong Fubini theorem was first shown by Friedman. It can also be deduced from a variant of Freiling's axiom of symmetry.
The Normal Moore Space conjecture, namely that every normal Moore space is metrizable, can be disproven assuming CH or MA + ¬CH, and can be proven assuming a certain axiom which implies the existence of large cardinals. Since the existence of large cardinals has not been proven to be consistent with ZFC, we cannot yet say that the Normal Moore Space conjecture is undecidable in ZFC.
Various assertions about finite, P-points, Q-points,...
S- and L- spaces
Garth Dales and Robert M. Solovay proved in 1976 that Kaplansky's conjecture, namely that every algebra homomorphism from the Banach algebra C(X) (where X is some compact Hausdorff space) into any other Banach algebra must be continuous, is independent of ZFC. CH implies that for any infinite X there exists a discontinuous homomorphism into any Banach algebra.
Consider the algebra B(H) of bounded linear operators on the infinite-dimensional separable Hilbert space H. The compact operators form a two-sided ideal in B(H). The question of whether this ideal is the sum of two properly smaller ideals is undecidable in ZFC, as was proved by Andreas Blass and Saharon Shelah in 1987.
Miroslav Bačák and Petr Hájek proved in 2008 that the statement "every Asplund space of density character ω1 has a renorming with the Mazur intersection property" is independent of ZFC. The result is shown using Martin's maximum axiom, while Mar Jiménez and José Pedro Moreno (1997) had presented a counterexample assuming CH.
- Kunen, Kenneth (1980). Set Theory: An Introduction to Independence Proofs. Elsevier. ISBN 0-444-86839-9.
- Baumgartner, J., All -dense sets of reals can be isomorphic, Fund. Math. 79, pp.101 -- 106, 1973
- Solovay, R. M.; Tennenbaum, S. (1971). "Iterated Cohen extensions and Souslin's problem". Annals Of Mathematics Second Series 94 (2): 201–245. doi:10.2307/1970860. JSTOR 1970860.
- Baumgartner, J., J. Malitz, and W. Reiehart, Embedding trees in the rationals, Proc. Nat. Acad. Science, U.S.A., 67, pp. 1746 -- 1753, 1970
- Shelah, S., Free limits of forcing and more on Aronszajn trees, Israel Journal of Mathematics, 40, pp. 1 -- 32, 1971
- Devlin, K., and H. Johnsbraten, The Souslin Problem, Lecture Notes on Mathematics 405, Springer, 1974
- Silver, J., The independence of Kurepa's conjecture and two-cardinal conjectures in model theory, in Axiomatic Set Theory, Proc. Symp, in Pure Mathematics (13) pp. 383 - 390, 1967
- Shelah, S., Proper and Improper Forcing, Springer 1992
- Schlindwein, Chaz, Shelah's work on non-semiproper iterations I, Archive for Mathematical Logic (47) 2008 pp. 579 -- 606
- Schlindwein, Chaz, Shelah's work on non-semiproper iterations II, Journal of Symbolic Logic (66) 2001, pp. 1865 -- 1883
- Shelah, S. (1974). "Infinite Abelian groups, Whitehead problem and some constructions". Israel Journal of Mathematics 18: 243–256. doi:10.1007/BF02757281. MR 0357114.
- Shelah, S., Whitehead groups may not be free even assuming CH I, Israel Journal of Mathematics (28) 1972
- Shelah, S., Whitehead groups may not be free even assuming CH II, Israel Journal of Mathematics (350 1980
- Barbara L. Osofsky (1968). "Homological dimension and the continuum hypothesis" (PDF). Transactions of the American Mathematical Society: 217–230.
- Barbara L. Osofsky (1973). Homological Dimensions of Modules. American Mathematical Soc. p. 60.
- James P. Jones (1980). "Undecidable diophantine equations". Bull. Amer. Math. Soc. 3 (2): 859–862. doi:10.1090/s0273-0979-1980-14832-6.
- Friedman, Harvey (1980). "A Consistent Fubini-Tonelli Theorem for Nonmeasurable Functions". Illinois J. Math. 24 (3): 390–395. MR 573474.
- Freiling, Chris (1986). "Axioms of symmetry: throwing darts at the real number line". Journal of Symbolic Logic 51 (1): 190–200. JSTOR 2273955. MR 830085.
- H. G. Dales, W. H. Woodin (1987). An introduction to independence for analysts.
- Judith Roitman (1992). "The Uses of Set Theory". Mathematical Intelligencer 14 (1).
- Farah, Ilijas (2007). "All automorphisms of the Calkin algebra are inner". arXiv:0705.3085.
- Phillips, N. C.; Weaver, N. (2007). "The Calkin algebra has outer automorphisms". Duke Mathematical Journal 139 (1): 185–202. doi:10.1215/S0012-7094-07-13915-2.