What are some reasonable-sounding statements that are independent of ZFC?

Question

Every now and then, somebody will tell me about a question. When I start thinking about it, they say, "actually, it's undecidable in ZFC."

For example, suppose $A$ is an abelian group such that every short exact sequence of abelian groups $0\to\mathbb Z\to B\to A\to0$ splits. Does it follow that $A$ is free? This is known as Whitehead's Problem, and it's undecidable in ZFC.

What are some other statements that aren't directly set-theoretic, and you'd think that playing with them for a week would produce a proof or counterexample, but they turn out to be undecidable? One answer per post, please, and include a reference if possible.

Answer 1

"If a set X is smaller in cardinality than another set Y, then X has fewer subsets than Y."

Althought the statement sounds obvious, it is actually independent of ZFC. The statement follows from the Generalized Continuum Hypothesis, but there are models of ZFC having counterexamples, even in relatively concrete cases, where X is the natural numbers and Y is a certain uncountable set of real numbers (but nevertheless the powersets P(X) and P(Y) can be put in bijective correspondence). This situation occurs under Martin's Axiom, when CH fails.

Answer 2

UPDATE: I edited the answer by adding details and adding a reference. In particular, I specialized from an arbitrary field to the complex numbers in response to John's comment.

Here's an example from commutative algebra. The projective dimension of a module M is defined as the minimal length of a projective resolution of M. Let S be the ring ℂ[x,y,z] and M be the module ℂ(x,y,z). Then the projective dimension of M is undecidable in ZFC. More specifically, the projective dimension of M is 2 if the continuum hypothesis holds, and it is 3 if the continuum hypothesis fails.

This follows from Barbara Osofsky's work (MR0548131); see Theorem 2.51 of Homological Dimensions of Modules. She seems to have a huge number of results which would be relevant to this question.

Answer 3

re:

Here's an example from commutative algebra. . Let S be the ring $\mathbb{C}[x,y,z]$ and M be the module $\mathbb{C}(x,y,z)$. Then the projective dimension of $M$ is $2$ if the continuum hypothesis holds, and it is $3$ if the continuum hypothesis fails.

Drinfeld has pointed out (see http://arxiv.org/abs/math/0309155v4 ) that the set-theoretic problems are coming from using the wrong definition of "projective". Raynaud and Gruson proved that projectivity of a module M is equivalent to the combination of three conditions:

(1) flatness

(2) decomposition as a direct sum of countably generated modules

(3) Mittag-Leffler condition

That (2) is possible for projective modules is a theorem of Kaplansky but the decomposition is non-canonical, and this is what introduces the axiom of choice into the proof of "free implies projective".

As I understood it from Drinfeld's lecture, only (1) and (3) are necessary for applications and for developing homological algebra, and (2) is undesirable because it is too strong a condition when working with infinite dimensional bundles. He proposed either "flat and Mittag-Leffler" directly, or a minor variant of that, as a definition of what he called "projectivity with a human face", that would work smoothly in the existing applications and allow a reasonable generalization to the infinite dimensional case.

Also, (1) and (3) are definable in first-order logic, so there is less chance of set theoretic problems from quantification over large or complicated structures.

Answer 4

If X is a compact Hausdorff space, and f is an algebra homomorphism from C(X) to some Banach Algebra, must f be continuous?

This question turns out to be independent. The affirmative answer is referred to as Kaplansky's Conjecture.

Answer 5

One of my favourites is

"Three clouds cover the plane"

where a subset $A \subseteq \mathbb{R}^2$ is a cloud around $a$ if every line through $a$ has a finite intersection with $A$.

This is due to Péter Komjáth; see http://www.cs.elte.hu/~kope/p28.ps.

In fact, three clouds cover the plane if and only if CH is true.

If the continuum is at most $\aleph_n$, then you can cover the plane with $n+2$ clouds (whether the reverse holds is open) (see comments).

Answer 6

"There is no definable well-ordering of the real numbers."

Although many mathematicians simply believe this statement to be true, actually, it is independent of ZFC. In Goedel's constructible universe $L$, for example, there is a definable well-ordering of the reals, having complexity $\Delta^1_2$ in the descriptive set-theoretic hierarchy. That is, the well-ordering is a subset of the plane $\mathbb R\times\mathbb R$, and it is the projection of the complement of the projection of a Borel set (and simultaneously, the complement of another such set).

The idea that well-orders of the reals cannot in principle be described or constructed is simply not correct.

Answer 7

This isn't an answer but an argument that there isn't really a good answer. Having done a good amount of set theory and seen how you prove some of these statements to be independent, I tend to be rather skeptical about how reasonable these statements actually sound. Typically, while these statements sound like they're talking about some ordinary mathematical object, they aren't really, because their independence comes from very large and pathological objects that are far remote from your usual mathematical experience.

For example, in the Whitehead problem, you have to realize that while abelian groups sound very down-to-earth, uncountable abelian groups can have incredibly complicated structure. As a (fairly difficult!) exercise, you can prove that a countable product $\mathbb Z^\mathbb N$ of copies of $\mathbb Z$ is not free, and in fact admits no homomorphism to $\mathbb Z$ besides the obvious finite sums of projections. On the other hand, the Whitehead problem has an affirmative answer if you restrict to countable groups, and this is something you could come up with if you thought about it for a week.

Answer 8

My favourite is the statement that if $X$ is a set of reals, and for every sequence $(a_n)$ of positive reals you can find a sequence of intervals $(I_n)$ that cover $X$ such that $I_n$ has length at most $a_n$, then $X$ is countable. I think it's of a similar strength to Martin's axiom.

Answer 9

Harvey Friedman has devoted a large portion of his career to finding "natural" statements that are unprovable in ZFC. One example is given at the end of Martin Davis's article "The incompleteness theorem," Notices AMS 53 (2006), 414-418:

http://www.ams.org/notices/200604/fea-davis.pdf

It takes a paragraph or so to state the definitions so I won't do so here, but the point is that, unlike many other examples, which clearly make reference to uncountable sets or are just Goedelian diagonalization statements in disguise, Friedman's proposition is a purely finitary statement in graph theory whose statement gives no hint of large cardinals. Indeed it is a small perturbation of a graph-theoretical theorem with an elementary proof.

For another example of Friedman's work, see his book Boolean Relation Theory and Incompleteness, a draft of which is downloadable from his website:

https://u.osu.edu/friedman.8/foundational-adventures/boolean-relation-theory-book/

Here Friedman presents a family of innocuous-looking elementary statements about functions and sets and unions/intersections/complements. Almost all statements in the family have easy proofs in ZFC (or actually much weaker systems), but one of them requires a large cardinal axiom.

Friedman is aware that these examples don't quite reach the holy grail of a completely natural finitary mathematical statement that is independent of ZFC, but he continues to make progress in this direction. You can subscribe to the Foundations of Mathematics mailing list if you want to keep track of his latest results.

Answer 10

Paul Erdős proved a funny statement about analytic functions to be equivalent to the continuum hypothesis. The same proof can also be found in Proofs from THE BOOK.

Let $\{f \}$ be a family of pairwise distinct analytic functions on the complex numbers such that for each $z ∈ \Bbb C$ the set of values $\{f (z)\}$ is at most countable (that is, it is either finite or countable); let us call this property (P0). Does it then follow that the family itself is at most countable?

Erdős proves:

Theorem 5. If $c > ℵ_1$, then every family $\{f \}$ satisfying (P0) is countable. If, on the other hand, $c = ℵ_1$, then there exists some family $\{f \}$ with property (P0) which has size $c$.

Answer 11

For every function $f$ mapping the reals into the set of all countable subsets of the reals, there are real numbers $x$ and $y$ such that $x \notin f(y)$ and $y \notin f(x)$.

This innocent and reasonable statement is actually equivalent to the negation of the Continuum Hypothesis. The equivalence was first proved by Sierpiński, and is actually very easy to see.

If CH holds, let $\{x_\alpha: \alpha < \omega_1\}$ be an enumeration of the reals in type $\omega_1$, the function defined by $f(x_\alpha)=\{x_\beta: \beta \leq \alpha \}$ is a counterexample to the boxed statement or otherwise we'd have a pair of ordinals $\alpha, \beta < \omega_1$ such that both $\alpha < \beta$ and $\beta < \alpha$.

Suppose now that CH fails and let $f: \mathbb{R} \to [\mathbb{R}]^{\leq \aleph_0}$. Let $S$ be a set of reals of cardinality $\aleph_1$. Let $T=\bigcup \{f(x): x \in S \}$. The set $T$ has cardinality $\aleph_1$ and hence we can pick a real number $y \notin T$. Since $f(y)$ is countable we can pick a real number $z \in S \setminus f(y)$. We have both $z \notin f(y)$ and $y \notin f(z)$.

Answer 12

Following Eric Wofsey's point, you probably are interested in things that don't involve the pathologies of arbitrary uncountable objects. Some people have argued that the only things "ordinary mathematicians" care about are things that are representable in second-order arithmetic. (This gives you arbitrary real numbers, arbitrary complete separable metric spaces, Borel and analytic sets on all of those, and similarly interesting amounts of algebraic stuff.) The project of Steven Simpson's book Subsystems of Second-Order Arithmetic is to analyze just what axioms are needed to prove which results. All of the things considered there are far weaker than ZFC. But it's interesting to discover that beyond the axioms of Peano Arithmetic and the existence of arbitrary recursive sets of natural numbers, there are exactly five natural strengths. That is, there are five levels such that very large numbers of theorems from ordinary mathematics fall at exactly one of the levels, where any theorem at one level can be proved by assuming any theorem at that level or higher. Interestingly, things like the Heine-Borel theorem and the Bolzano-Weierstrass theorem, which are often thought of as equivalent, actually fall at different levels.

Not everything falls exactly at these levels though. Some things do still depend on a version of the axiom of choice, which is above any of these five levels, and there are other results like Goodstein's theorem and Borel determinacy that are higher still (I believe).

Answer 13

Another example is certain strong forms of Fubini's Theorem.

If you have a real value function on the product of two closed intervals which is bounded, and which is measurable in either coordinate when you fix the other, are the two iterated integrals equal?

(In the actual Fubini's theorem you care about joint measurability, not just measurability on either coordinate.)

If you assume CH, it is easy to construct counterexamples. It turns it is also consistent to have models where it is true.

I don't have a good reference on this, if you know of one please add it in to my answer.

Answer 14

"The real line is the only endless dense complete linear order in which every family of disjoint intervals is countable."

This statement generalizes the familar characterization of the real line (due to Cantor) as the unique endless dense complete linear order having a countable dense set. Souslin inquired whether this separability condition can be weaked to the condition on families of disjoint intervals. (Here, complete means that the order as the LUB property.)

This statement is known as Souslin's Hypothesis, and it is independent of ZFC. It is false under the combinatorical assertion known as Diamond, but follows from Martin's Axiom at $\aleph_1$. The proof that the statement is consistent, due to Solovay and Tennenbaum, is highly important in the history of set theory, since it required the development of iterated forcing, now a fundamental tool.

Answer 15

Sometimes ZFC is just not sufficient to prove statements which morally should be true. The axiom of projective determinacy is perhaps the best known instance of this. If you don't know what this is, consider the following example: take a Borel set (or even a $G_\delta$ set) in $\mathbb{R}^3$, project it in $\mathbb{R}^2$, take the complement and project it into $\mathbb{R}$. One cannot prove in ZFC that the resulting set is Lebesgue measurable (or has the property of Baire, or the perfect set property). However, this is an easy consequence of PD which in turn can be proved using large cardinals (Martin and Steel, "A Proof of Projective Determinacy", JAMS).

Answer 16

A recent example is the question of existence of outer automorphisms of the Calkin algebra of a separable infinite-dimensional Hilbert space (this is quotient algebra of the algebra of all bounded operators by its ideal of compact operators). See this paper of Farah for details.

A feature this example shares with Kaplansky's conjecture mentioned above is the use of CH for the construction of the desired object. For the other direction (proving non-existence of an outer automorphism), which is more interesting, Farah uses a natural combinatorial axiom (OCA) which can be forced in any model of ZFC.

Wikipedia also has a list of independence results.

Answer 17

Here's one (a corollary of some work I did with Keith Kearnes):

It is undecidable in ZFC whether there exists a commutative Noetherian domain of size $\aleph_{2}$ with a finite residue field.

Answer 18

Laver tables of order $n$ provide a potential answer (although it's not proven to be independent of ZFC, and may not be independent of ZFC).

The Laver table of order $n$ is the $2^n \times 2^n$ table of an operation $\star$ defined recursively by $$ p \star 1 = p+1 \bmod {2^n}\\ p \star (q \star r) = (p \star q) \star (p \star r). $$ They arise naturally in the study of (self) left-distributive systems (systems satisfying the second axiom above).

The first row of this table ($1 \star p$) is always periodic with some period $m$ dividing $2^n$. Let $p(n)$ be this periodicity. Assuming an extremely large cardinal, Laver showed that $p(n)$ increases without bound as $n$ increases. (The consistency of this large cardinal axiom, the existence of a self-embedded cardinal, is apparently in doubt.) Under this same large cardinal hypothesis, Dougherty showed, for instance, that the first $n$ for which $p(n)>m$ grows faster than any primitive recursive function of $m$.

I'm not sure what the current state of belief is on whether this statement is independent of ZFC. There were various other statements first proved by Laver using this large cardinal hypothesis that were later proved by Dehornoy; for instance, there is an algorithm to decide the word problem in a free left-distributive algebra.

I could have sworn there was a statement in this theory that was known to be independent of ZFC, but I couldn't find it when I looked.

I'm not a logician. Apologies if I'm misstating any results.

References:

https://googology.fandom.com/wiki/Laver_table

Randall Dougherty, Critical points in an Algebra of Elementary Embeddings, Ann. Pure Appl. Logic 65 (1993), no. 3, 211-241, http://arxiv.org/abs/math/9205202

Answer 19

The assertion that the union of any $\aleph_1$ many measure zero sets is still measure zero. This is independent of ZFC. Of course, it implies the failure of the Continuum Hypothesis, but is not equivalent to this.

There is a huge variety of such statements in the field known as Cardinal Characteristics of the Continuum. For example, what is the additivity of the meager ideal (the ideal of all meager sets)? It is at least $\aleph_1$, but can be larger. What is the smallest size of a family of functions $f:\omega \to\omega$ such that every function is bounded by an element of the family? It can be $\aleph_1$, or larger independently. There are dozens of such examples.

Answer 20

In the ring of bounded operators on (complex, separable) Hilbert space, the ideal of compact operators is the sum of two properly smaller ideals. (I mean 2-sided ideals, in the algebraic sense, not topologically closed ideals.)

In the Stone-Cech compactification of a half-open interval minus the interval itself (call this space X), there exist two points such that the only compact, connected subset of X containing both points is X itself.

Both of these statements are true under CH (or various weaker assumptions) but not provable in ZFC. Lest anyone remind me that there should be only one statement per answer, I point out that, despite appearances, these two statements are provably equivalent. See an old paper of mine, "Near coherence of filters II," Trans. A.M.S. 300 (1987) 557-581, for the equivalence, and references there to older papers, including one with Gary Weiss and one with Saharon Shelah, for the CH result and the independence from ZFC.

Answer 21

One of my favorites has to do with products of spaces of countable cellularity:

"If X and Y are topological spaces with countable cellularity then their product X x Y has countable cellularity"

Is independent of ZFC. (The failing example being a Souslin line)

Answer 22

My favourite one(in fact it is equivalent to continuum hypothesis, proving equivalency is a very nice exercise, btw):

Real line (excluding 0) could be represented as a countable union of linearly independent (over $\mathbb{Q}$) subsets.

Answer 23

$``$Given any function $f:\Bbb R\times\Bbb R\to\Bbb R$, there exist functions $g_n,h_n:\Bbb R\to \Bbb R\,$ ($n=1,2,...$) such that$$f(x,y)=\sum_{n=1}^\infty g_n(x)h_n(y)\quad(x,y\in\Bbb R)."$$That this statement is independent of ZFC was pointed out in a comment by MathOverflow user @GHfromMO on consideration of answers to a question posted on this site. This statement (actually a stronger one in which the sums are all finite) was shown in 1954 by Roy O. Davies to be a consequence of the continuum hypothesis (CH). However, I do not know whether the converse is true, namely whether it is as strong as CH. (The statement with finite sums, even restricted to the single case $f(x,y):=\exp xy$, is shown by Davies to imply CH.)

Answer 24

Of course, it follows from the negative solution to Hilbert's 10th problem (Putnam-Davis-Robinson-Matijasevic) that one can construct a specific diophantine equation $P(x_1,x_2,...,x_m)=0$ for some $m$ such that the solvability of this equation (over $\mathbb Z$) is undecidable in ZFC. I actually think $m$, and the degree of $P$, can be made to be quite smallish.

It follows, of course, that the equation has no integer solutions (for if it had, this would have been easily demonstrable in ZFC). But ZFC is not capable of providing a proof of this fact (assuming that ZFC is consistent. If it's not then it can provide a proof of anything...)

Answer 25

My favorite is the first problem I worked on, back in 1966 when I was an undergraduate. The question is: does every non separable Banach space have an uncountable biorthogonal system? Shelah constructed a counterexample under diamond; Kunen later gave a C(K) counterexample using CH. In 2005 Stevo Todorcevic gave a positive answer when mm > aleph_1. His paper "Biorthogonal Systems and Quotient spaces via Baire Category" appeared in Math. Annalen in the last couple of years.

Answer 26

Is every regular ($T_3$) topological space $X$ that is hereditarily separable (all subspaces are separable) Lindelöf (every open cover of $X$ has a countable subcover) ?

A counterexample is known as an S-space and Baumgartner showed there are models of ZFC without them. But under CH (and many other axioms) they do exist. Interestingly, in ZFC there does exist an L-space (a hereditarily Lindelöf space that is not separable), which was surprising to many topologists, who expected a certain duality to hold between S- and L-spaces. For a short intoduction see these slides.

Answer 27

Is there a vector space with three non-isomorphic Hilbert space structures? A negative answer is equivalent to the conjunction CH + SCH.

Pf: An infinite-dimensional Hilbert space with Hilbert dimension $\kappa$ has vector space dimension $\kappa^{\aleph_0}.$ So we're really asking whether there is $\kappa$ such that $\kappa^{\aleph_0} \ge \kappa^{++}.$ The first such $\kappa$ would have cofinality $\omega,$ and from Silver's theorem we can see that $\kappa^{\aleph_0}=\kappa^+$ holding for all countable cofinality $\kappa$ is equivalent to CH + SCH.

Another nice fact is that every Fréchet space is homeomorphic to a unique Hilbert space. This gives us two more "natural" equivalents of CH + SCH: "Every real vector space has at most two Fréchet space structures up to homeomorphism," and "Every real vector space has at most two Banach space structures up to homeomorphism."

Answer 28

The statement, "Any two $\aleph_1$-dense subsets of the reals are order isomorphic."

A subset $X$ of $R$ is called $\aleph_1$-dense if between any two real numbers, there are exactly $\aleph_1$ elements of $X$. On the one hand, Sierpinski used a diagonalization argument (working within $ZFC$) to construct $\kappa$ pairwise non-isomorphic suborderings of $\mathbb R$ each of density $\kappa$, where $\kappa$ is the cardinality of $\mathbb R$, so the Continuum Hypothesis implies that this statement fails. On the other hand, James Baumgartner used a clever forcing argument to build models of $ZFC$ where the size of $\mathbb R$ is $\aleph_2$ and any two $\aleph_1$-dense suborderings of $\mathbb R$ are isomorphic.

See "All aleph_1 dense sets of reals can be isomorphic," James E. Baumgartner, Fundamenta Mathematicae v. LXXIX (1973), pp. 101-106.

Answer 29

Albin Jones has a draft paper on his web page, "Even more partitioning triples of countable ordinals", which has a survey of infinite Ramsey theory results stated in terms of ordinals.

Let $\omega$ be the first infinite ordinal and let $\omega_1$ be the first uncountable ordinal. Citing results of Todorcevic and Hajnal, Jones says that if you color pairs of elements of $\omega_1$ in blue and red, then it is independent of ZFC to decide whether there must be either a blue subset of type $\omega_1$ or a red subset of type $\omega+2$.

Answer 30

"There exists a complete metric space $(X,d)$ and a Borel probability measure $\mu$ on $X$ with non-separable support."

This has been discussed elsewhere on MO (I forget where, sorry), but is shown to require a large cardinal axiom in Fremlin's Measure Theory, section 438.