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→ℤ→B→A→0 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.

  • 3
    I think this is a very good question, but the example given doesn't seem particularly outside of normal logic intuition. When you say the group is "free" it means "it can be proven that there exists a basis B such that..." so surely you need find that specific B --- that really can't follow from a description like you gave without some mechanism! – Ilya Nikokoshev Oct 22 '09 at 21:41
  • 7
    @ilya: I don't understand your objection to the example. The statement is that Whitehead's problem is independent of ZFC (which allows you to do things like chose elements of sets, and lots of other constructions). I agree it would be silly to say that it's independent of the empty list of axioms. – Anton Geraschenko Oct 22 '09 at 21:49
  • 2
    Mm, I think I misunderstood what ZFC is. I wanted to point out that axiom of choice (or something) should be necessary which was obvious to the asker from the start. Apologies. – Ilya Nikokoshev Oct 22 '09 at 22:10

28 Answers 28

"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.

  • 88
    This blows my mind. – Charles May 31 '10 at 17:29
  • 13
    Wow! Is this a good argument for believing in GCH? – Mozibur Ullah Dec 3 '12 at 13:14
  • 5
    @Joel Can I get a reference for this? In particular what is the meaning of 'fewer' in the statement? Does this hold because of some 'weird' failures of separation, i.e. it is unable to 'create' subsets where we normally would expect it to? I agree with Charles, this is mind-bending to say the least, and makes me doubt the conceptual robustness of ZFC, especially since it is supposed to be so good at giving us a theory of 'size'... – Chuck Dec 31 '12 at 17:30
  • 19
    I had meant "fewer" in the sense of cardinality. In other words, the question is whether $\kappa\lt\lambda$ implies $2^\kappa\lt 2^\lambda$. The answer is that this is independent of ZFC. It is consistent with ZFC, for example, that the power set $P(\mathbb{N})$ is bijective with $P(Y)$ for some uncountable set $Y$, such as $Y=\omega_1$. Indeed, the assertion that $2^\omega=2^{\omega_1}$ is known as Luzin's hypothesis. As for a reference, this is covered in any good graduate set theory text book, such as Jech's book Set Theory. – Joel David Hamkins Dec 31 '12 at 18:05
  • 14
    Well, if ZFC is not consistent, then nothing is independent of it. So it would be silly to ask for examples of independence without assuming consistency. – Joel David Hamkins Jan 28 '16 at 3:53

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.

  • 1
    That's bizarre. If somebody tracks down a reference, I'd be curious to know: is this true for any field k? What kind of bounds on the projective dimension can you prove in ZFC? – John Goodrick Oct 23 '09 at 13:11
  • 21
    It has to do with the cardinality of the field. In his book Basic Homological Algebra, Scott Osbourne proves that a module generated by \aleph_m elements has projective dimension at most m+n+1, where n is the maximum projective dimension of a finitely generated submodule. What's going on here is that these modules are disgustingly infinitely generated. Something generated by \aleph_m elements can be written as a direct limit of a chain of things generated by \aleph_{m-1} elements, and you use that and induction on m to prove it. – Eric Wofsey Oct 23 '09 at 21:02
  • 1
    Interesting, thanks for the reference. – John Goodrick Oct 24 '09 at 15:20


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.

  • 3
    Do we know how this problem resolves the independence dichotomy in the linked answer? I.e. does the notion of “flat Mittag-Leffler dimension” make a good replacement for “projective dimension”, and if so, do we know what the fML dimension of $\mathbb{C}(x,y,z)$ over $\mathbb{C}[x,y,z]$ is? – Peter LeFanu Lumsdaine Apr 20 at 10:16

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.

  • 2
    Wow! (Just unbelievable :-). – Włodzimierz Holsztyński May 16 '13 at 8:51
  • I kind of want the answer to be "no" - homomorphisms between infinite objects shouldn't just magically happen to be continuous like that, at least not without a very good reason. – goblin Oct 1 '16 at 17:22
  • 3
    @goblin: I think, kind of a motivation for the statement is provided by the fact that every $\ast$-algebra homomorphism from a Banach algebra with isometric involution into a C*-algebra is continuous. – Benedikt Hunger Nov 30 '16 at 6:30

"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.

  • 13
    I think this misconception comes down partly to a difference between formal and informal usage. To “construct a widget W with property P” often covers (informally) not just the construction of W, but also the proof of P for it. In this sense, it is indeed impossible to construct a w-o of the reals in ZFC, by the very independence result you give. – Peter LeFanu Lumsdaine Sep 22 '10 at 14:15
  • To Peter LeFanu Lumsdaine: can you at least construct a widget W that we can prove is a well-ordering of reals if there exists at least one well-ordering? That's the case we have with P!=NP: we can give a concrete algorithm that we can prove solves an NP-complete problem if P=NP. – Zsbán Ambrus Aug 16 '11 at 9:02
  • 10
    Zsbán, we can prove in ZFC that there is a well-ordering. So the issue isn't existence of the well-ordering, but rather the question of whether there is a definable such well-ordering. It is consistent with ZFC that there is a very low complexity definition, and it also follows from large cardinals thought to be consistent that there is no definable such ordering anywhere in the projective hierarchy. Meanwhile, there is a particular universal definition $\varphi$ in set theory, such that any universe of set theory can be extended to one where $\varphi$ defines a well-ordering of $\mathbb{R}$. – Joel David Hamkins Aug 16 '11 at 11:11

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.

  • 22
    A set of reals with this property is usuall called strong measure zero. The question of whether such have to be countable is called the Borel Conjecture. It was first proven independent by Laver. – Richard Dore Oct 23 '09 at 14:08
  • 9
    @gowers : I am not sure what you mean by "of similar strength to Martin's axiom". Would you mind briefly commenting on this? – Andrés E. Caicedo Dec 6 '10 at 17:30
  • 6
    (Since this was not addressed: Martin's axiom is equiconsistent with $\mathsf{ZFC}$, as is this statement, so the mention of Martin's axiom and strength is a distraction, if by strength we mean consistency strength, which is the common usage. If what is meant is that the Borel conjecture is about as useful in terms of consequences as Martin's axiom, I disagree strongly.) – Andrés E. Caicedo Jun 29 '13 at 4:43
  • 2
    @AndresCaicedo: I think he meant Martin's Axiom (MA) implies a counterexample. As for the other direction: A counterexample follows from axioms that are very incompatible with MA. But there are some consequences of existence and of nonexistence of counterexamples of the behavior of cardinals of the continuum. – Boaz Tsaban Apr 24 '14 at 21:17

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:


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:


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.

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).

  • 7
    Actually it looks like the reverse is not open any longer: helios.impan.gov.pl/cgi-bin/fm/pdf?fm177-3-02 – Justin Palumbo Jul 5 '10 at 4:13
  • 4
    My friend Ramiro de la Vega recently obtained a result for a related concept. A spray centered at $c$ is a subset of the plane that meets every circle centered at $c$ in only finitely many points. Unlike the situation for clouds, one can prove that 3 sprays cover the plane, independently of the status of CH. See "Decompositions of the plane and the size of the continuum", Ramiro de la Vega, Fund. Math. 203 (2009), 65-74, and "Covering the plane with sprays", James H. Schmerl, Fund. Math. 208 (2010), 263-272. – Andrés E. Caicedo Jul 5 '10 at 5:10
  • 3
    Speaking of stuff on the plane, a certain problem of coloring the plane with no corners is equivalent to CH too - artofproblemsolving.com/Forum/viewtopic.php?f=73&t=137999 – Yoo Jul 5 '10 at 9:35
  • 3
    Since Justin's link leads to a paywall here's a survey by Arnold Miller math.wisc.edu/~miller/old/m873-05/setplane.ps – Peter Krautzberger Jul 5 '10 at 15:42

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 removed 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 Z^N of copies of Z is not free, and in fact admits no homomorphism to 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.

  • 8
    There's a big difference between "We don't know if there are pathological groups," and "We provably can't know if there are pathological groups." There are lots of places where things get complicated, and people either prove theorems or find counterexamples. And in most cases we just kind of assume on or the other of those is possible. It's substantially different to know that is a hopeless process. – Richard Dore Oct 23 '09 at 0:16
  • 3
    I guess my point is that most of the time you can't prove things when you're dealing with things that are complicated because they are very infinite. That is, when I see this kind of problem, I don't assume you can solve it. This might just be because I've done too much set theory. – Eric Wofsey Oct 23 '09 at 0:53
  • 4
    This makes a lot of sense to me,say, in the context of Whitehead's problem. But I cannot, for instance, understand how Harvey Friedman's example could be a fact about large cardinals in disguise. It would be great if you could explain more. – Keivan Karai Jul 4 '10 at 11:02

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).

  • 3
    Borel Determinacy is interesting because it really uses Replacement. In fact, it was known that ZFC-Replacement was insufficient to prove Borel Determinacy before Borel Determinacy was proven. – Richard Dore Oct 23 '09 at 4:24

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.

  • 6
    The CH result is due to Sierpinski; the independence result was shown almost simultaneously by Chris Freiling, Harvey Friedman, and Miklos Laczkovich. See Ciesielski's survey math.wvu.edu/~kcies/prepF/56STA/STAsurvey.html – François G. Dorais Feb 5 '10 at 22:50
  • 2
    One nice way to get the statement to be true is using Freiling's axioms of symmetry. There's a proof of it in Chris Freiling. Axioms of symmetry: Throwing darts at the real line. The Journal of Symbolic Logic, 51, 1986. – David R. MacIver Apr 11 '10 at 20:45
  • 2
    One reference for strong Fubini theorems is Joe Shipman's paper, "Cardinal conditions for strong Fubini theorems," Trans. Amer. Math. Soc. 321 (1990), 465-481. – Timothy Chow May 31 '10 at 16:57

"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.

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.

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)$.

  • 10
    Might as well call this statement by its name, Freiling's axiom of symmetry. – Asaf Karagila May 9 '13 at 23:33

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).

  • 5
    Not sure if this is the right forum for this, but: do you think PD is "morally true" because it follows from large cardinal axioms, which themselves are "morally true"? Or does PD follow from some other set of ethical principles? Guess I'm somewhat of a libertine, myself... – John Goodrick Oct 23 '09 at 17:59
  • 4
    Maybe I didn't choose the right word. Anyway, for me, PD is a strong justification for large cardinals, not the other way round. But this is, of course, a philosophical rather than mathematical discussion. – Todor Tsankov Oct 24 '09 at 8:12

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.

  • 6
    Would be nice if the funny statement could be seen here.... – Hurkyl Aug 18 '15 at 4:13
  • 2
    If I remember right, the funny statement is that there is a uncountable famility of entire functions which assumes only countably many different values at each point in the complex plane. – bof Oct 24 '15 at 2:16

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 are 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.

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.

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)

  • 1
    What does "countable cellularity" mean? – Qiaochu Yuan Mar 25 '11 at 20:44
  • That any collection of disjoint open subsets of a space is at most countable. – Not Mike Mar 29 '11 at 19:33
  • I've heard "countable chain condition" (or "countable antichain condition") much more often. – Todd Trimble Aug 16 '15 at 16:37
  • 3
    @ToddTrimble You've been listening to set theorists more than topologists. (Admittedly, the topologists who are interested in cellularity are often set theorists in disguise.) – Andreas Blass Aug 16 '15 at 23:49
  • @AndreasBlass Good to know! Thanks. – Todd Trimble Aug 16 '15 at 23:54

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.

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(x1,x2,...,xm)=0 for some m such that the solvability of this equation (over 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...)

  • This not right. The theorem of Matijasevic et al. states that there is a specific polynomial equation p(y, x_1, ..., x_n) such that the set of all integers a for which p(a, x_1, ..., x_n) has a solution where all the x_i's are integers is "undecidable," but here "undecidable" means uncomputable, i.e. you could never write a Java script to determine membership in this set. "Undecidable from ZFC" means that both the statement and its negation are logically consistent with ZFC. – John Goodrick Oct 22 '09 at 23:39
  • 1
    Greg Igusa says: That doesn't sound right to me. If the set A of a for which p(a, x_i) has a solution is undecidable, then there would have to be a specific integer a_0 for which the question "does p(a_0,x_i) have a solution" is independent of ZFC, else we could compute the set A by searching for proofs as to whether or not the polynomial has a solution. But this gives an example of a polynomial as in the original answer. – Anton Geraschenko Oct 23 '09 at 0:30
  • 2
    "Given a number a, search for some number n and some proof (from ZFC) that p(a, n) holds" is not a good algorithm for deciding whether or not (exists x) p(a, x) is true. If you do find such n and such a proof, then OK, you're done; but otherwise, you'll get stuck in an infinite loop. The set of a for which p(a,x) has a solution is always r.e., but not always recursive: en.wikipedia.org/wiki/Diophantine_set – John Goodrick Oct 23 '09 at 1:16
  • 5
    Since some of the references here are long, let me give a comment-sized statement: The solution of Hilbert's 10th problem also shows that there is a Diophantine equation E such that E has a solution if and only if ZFC is inconsistent (and this equivalence is provable in Peano Arithmetic). So those of us who think ZFC is consistent think E has no solutions but ZFC can't prove that. Those who think ZFC is inconsistent could make their case by finding a solution of E (but it would probably be easier just to exhibit a proof of a contradiction in ZFC). – Andreas Blass Jul 4 '10 at 4:27
  • 5
    Greg Igusa's argument above shows by contradiction the existence of a polynomial $p$ whose solvability is independent of ZFC, but does not by itself tell us how to get our hands on such a $p$. The missing ingredient is the result that one can computably translate arbitrary existential ($\Sigma^0_1$) statements into statements about solvability of Diophantine equations. This yields both the uncomputability (Matiyasevich's theorem), and the fact that a specific $p$ can be found (as in Andreas Blass' comment and Alon Amit's answer) since $\neg$Con(ZFC) is a $\Sigma^0_1$ statement. – Bjørn Kjos-Hanssen Oct 19 '10 at 10:36

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.

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 R each of density kappa, where kappa is the cardinality of 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 R is aleph-2 and any two aleph-1-dense suborderings of 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.

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.

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

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

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.



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

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$.

  • Along the same lines: It is a theorem that if you color pairs of elements of $\omega_1$ in blue and red, then there must be either a red stationary subset of type $\omega_1$ or a blue closed subset of type $\omega+1$. It is independent if instead we require the blue homogeneous set not to be closed. (Laver.) – Andrés E. Caicedo Oct 24 '15 at 1:40
  • This example really surprised me when I saw it at first, because while cardinals frequently show strange undecideable behavior, ordinals are usually pretty concrete. Then I realized that the statement is fundamentally about $\wp(\omega_1)$, not about $\omega_1$ itself, and I realized this is not as surprising as that after all. The set $\omega_1$ I expect to act concretely; not so much $\wp(\omega_1)$. – Harry Altman Nov 12 '17 at 21:48

I really think the following one is just intuitive. However, not only is it consistent to be false in ZFC, it is actually not known to be consistent in ZFC (its consistency follows from the existence of a weakly compact cardinal).

The conjecture is second-order, and thus must be regarded in NBG rather than ZFC, though I think this isn't too much of a cheat for the question. Furthermore, the negation of this conjecture is only known to be consistent as long as there is a worldly cardinal. A meager assumption nonetheless, but still quite a jump from ZFC in consistency strength.

Let $D$ be the class of all doubletons of ordinals (i.e. $\{\alpha,\beta\}$ such that $\alpha<\beta$). Let a class $H\subseteq D$ be containable iff there is some class $h$ such that every element of $H$ is a subclass of $h$ and every doubleton of $h$ is an element of $H$. The Doubleton Ordinal conjecture is as follows:

For any class proper class $X\subseteq D$, there is a containable proper class $H\subseteq D$ such that either $H\subseteq X$ or $H$ is disjoint from $X$.

Although this seems quite reasonable, it does not hold in $V_{\kappa+1}$ (the successor of $\kappa$ is used for second-order logic) for the least worldly cardinal $\kappa$. This is quite a strange result indeed.

In fact, $V_{\kappa+1}$ satisfies the Doubleton Ordinal conjecture iff $\kappa$ is $0$, $\omega$, or weakly compact.

  • 3
    If every element of $H$ is a subset of $h$, then $H$ is included in $\mathcal P(h)$, and in particular, it is a set. So, how could there be a set-containable proper class? – Emil Jeřábek Nov 12 '17 at 9:11
  • Sorry, I didn't mean for $h$ to be a set :/ – Zetapology Nov 12 '17 at 15:49
  • 1
    @Zetapology You probably mean "... disjoint from no containable proper class" (nothing is disjoint from every containable proper class). I guess I don't find this any more reasonable than "every set either contains or is disjoint from a club" over ZF, say (although of course this is subjective - I'm not trying to give you a hard time, I was just curious if you had a more specific motivation). Also, unless I'm missing something "$H$ is containable" is just saying "$H=[h]^2$ for some class $h$;" is that accurate? – Noah Schweber Nov 12 '17 at 18:47
  • 3
    I think this would be phrased much clearly as "$Ord$ is weakly compact" - introducing the term "containable" isn't necessary. (What you write is just "every 2-coloring of pairs of ordinals has a homogeneous proper class.") – Noah Schweber Nov 12 '17 at 19:45
  • 2
    Incidentally, the definable version of "$Ord$ is weakly compact" fails - see this paper of Enayat and Hamkins. – Noah Schweber Nov 12 '17 at 19:50

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.