290
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ 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! $\endgroup$ Oct 22, 2009 at 21:41
  • 14
    $\begingroup$ @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. $\endgroup$ Oct 22, 2009 at 21:49
  • 4
    $\begingroup$ 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. $\endgroup$ Oct 22, 2009 at 22:10

34 Answers 34

382
$\begingroup$

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

$\endgroup$
17
  • 127
    $\begingroup$ This blows my mind. $\endgroup$
    – Charles
    May 31, 2010 at 17:29
  • 22
    $\begingroup$ Wow! Is this a good argument for believing in GCH? $\endgroup$ Dec 3, 2012 at 13:14
  • 8
    $\begingroup$ @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'... $\endgroup$
    – Chuck
    Dec 31, 2012 at 17:30
  • 33
    $\begingroup$ 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. $\endgroup$ Dec 31, 2012 at 18:05
  • 31
    $\begingroup$ 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. $\endgroup$ Jan 28, 2016 at 3:53
169
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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? $\endgroup$ Oct 23, 2009 at 13:11
  • 34
    $\begingroup$ 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. $\endgroup$ Oct 23, 2009 at 21:02
  • 1
    $\begingroup$ Interesting, thanks for the reference. $\endgroup$ Oct 24, 2009 at 15:20
108
$\begingroup$

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.

$\endgroup$
3
  • 17
    $\begingroup$ 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? $\endgroup$ Apr 20, 2018 at 10:16
  • 3
    $\begingroup$ @PeterLeFanuLumsdaine I've belatedly come back to this answer and had a very quick look in the Drinfeld paper and did not seen anything that mentioned the particular example of C(x,y,z) over C[x,y,z]. Perhaps the OP knows more but they seem to have disappeared $\endgroup$
    – Yemon Choi
    Jan 8, 2019 at 0:37
  • 6
    $\begingroup$ I think this answer begs for a computation of the projective dimension of $\mathbb C(x, y, z)$ with the 'right' definition. I may be wrong, but my guess is that this 'wrong' definition would allow some modules to be projective that shouldn't and therefore give our module of interest a dimension drop to 2. Does that make sense to anyone? $\endgroup$ Jun 22, 2020 at 13:54
96
$\begingroup$

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.

$\endgroup$
3
  • 5
    $\begingroup$ Wow! (Just unbelievable :-). $\endgroup$ May 16, 2013 at 8:51
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 1, 2016 at 17:22
  • 12
    $\begingroup$ @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. $\endgroup$ Nov 30, 2016 at 6:30
81
$\begingroup$

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

$\endgroup$
4
  • 9
    $\begingroup$ Actually it looks like the reverse is not open any longer: helios.impan.gov.pl/cgi-bin/fm/pdf?fm177-3-02 $\endgroup$ Jul 5, 2010 at 4:13
  • 8
    $\begingroup$ 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. $\endgroup$ Jul 5, 2010 at 5:10
  • 3
    $\begingroup$ 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 $\endgroup$
    – Yoo
    Jul 5, 2010 at 9:35
  • 4
    $\begingroup$ Since Justin's link leads to a paywall here's a survey by Arnold Miller math.wisc.edu/~miller/old/m873-05/setplane.ps $\endgroup$ Jul 5, 2010 at 15:42
78
$\begingroup$

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

$\endgroup$
10
  • 18
    $\begingroup$ 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. $\endgroup$ Sep 22, 2010 at 14:15
  • $\begingroup$ 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. $\endgroup$ Aug 16, 2011 at 9:02
  • 14
    $\begingroup$ 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}$. $\endgroup$ Aug 16, 2011 at 11:11
  • 3
    $\begingroup$ (And no large cardinals are needed here anyway. Forcing over $L$ to add $\omega_1$ random reals produces a model without definable well-orderings of $\mathbb R$.) $\endgroup$ Apr 12, 2019 at 20:52
  • 1
    $\begingroup$ How about this variant of @ZsbánAmbrus's question: Is there a definable relation $R$ on the reals such that, for every formula $φ$ over ZFC, ZFC proves ( if $φ$ defines a well-ordering of the reals then $R$ is a well-ordering of the reals )? $\endgroup$
    – user21820
    May 4, 2020 at 6:06
72
$\begingroup$

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

$\endgroup$
3
  • 18
    $\begingroup$ 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. $\endgroup$ Oct 23, 2009 at 0:16
  • 9
    $\begingroup$ 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. $\endgroup$ Oct 23, 2009 at 0:53
  • 8
    $\begingroup$ 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. $\endgroup$ Jul 4, 2010 at 11:02
69
$\begingroup$

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.

$\endgroup$
4
  • 31
    $\begingroup$ 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. $\endgroup$ Oct 23, 2009 at 14:08
  • 11
    $\begingroup$ @gowers : I am not sure what you mean by "of similar strength to Martin's axiom". Would you mind briefly commenting on this? $\endgroup$ Dec 6, 2010 at 17:30
  • 8
    $\begingroup$ (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.) $\endgroup$ Jun 29, 2013 at 4:43
  • 4
    $\begingroup$ @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. $\endgroup$ Apr 24, 2014 at 21:17
67
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ I'm probably being a stick in the mud, but it's probably worth noting that that book has quite a few non-peer-reviewed results, and so probably should be treated with the appropriate care. $\endgroup$
    – cody
    Nov 15, 2020 at 19:29
  • 1
    $\begingroup$ @cody: I have personally complained to Harvey Friedman that he doesn't formally publish enough of his work. But old habits die hard. $\endgroup$ Nov 15, 2020 at 20:58
35
$\begingroup$

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.

$\endgroup$
3
  • 6
    $\begingroup$ 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 $\endgroup$ Feb 5, 2010 at 22:50
  • 3
    $\begingroup$ 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. $\endgroup$ Apr 11, 2010 at 20:45
  • 2
    $\begingroup$ 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. $\endgroup$ May 31, 2010 at 16:57
34
$\begingroup$

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

$\endgroup$
1
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 23, 2009 at 4:24
34
$\begingroup$

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

$\endgroup$
3
  • 17
    $\begingroup$ Might as well call this statement by its name, Freiling's axiom of symmetry. $\endgroup$
    – Asaf Karagila
    May 9, 2013 at 23:33
  • 2
    $\begingroup$ This seems like the strongest argument intuitive I've ever seen for not CH. The quoted statement seems like it should be obviously true. But then the construction assuming CH of a counterexample wrecks that intuition! $\endgroup$
    – JoshuaZ
    Jul 30, 2020 at 1:37
  • $\begingroup$ @JoshuaZ I've argued elsewhere that Freiling's argument is mainly just showing that the axiom of choice violates our intuitions about probability (something we already know from the Banach-Tarski paradox), and that CH is a red herring. If Freiling's axiom of symmetry could disprove CH without using the axiom of choice, that would be another matter. But it can't. $\endgroup$ Nov 21, 2023 at 20:43
32
$\begingroup$

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

$\endgroup$
2
  • 7
    $\begingroup$ Would be nice if the funny statement could be seen here.... $\endgroup$
    – user13113
    Aug 18, 2015 at 4:13
  • 5
    $\begingroup$ 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. $\endgroup$
    – bof
    Oct 24, 2015 at 2:16
31
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ "Souslin" seems to be a French transliteration of a Russian name, sometimes spelled "Suslin" in English. $\endgroup$ Dec 7, 2022 at 18:23
23
$\begingroup$

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

$\endgroup$
2
  • 7
    $\begingroup$ 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... $\endgroup$ Oct 23, 2009 at 17:59
  • 6
    $\begingroup$ 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. $\endgroup$ Oct 24, 2009 at 8:12
23
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ You might have mentioned who proved the "less interesting" direction, which is not as trivial as many people seem to think. Phillips, N. Christopher; Weaver, Nik: The Calkin algebra has outer automorphisms, Duke Math. J. 139 (2007), 185–202. $\endgroup$
    – Nik Weaver
    Jul 30, 2020 at 0:22
21
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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.

$\endgroup$
18
$\begingroup$

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)

$\endgroup$
5
  • 3
    $\begingroup$ What does "countable cellularity" mean? $\endgroup$ Mar 25, 2011 at 20:44
  • 2
    $\begingroup$ That any collection of disjoint open subsets of a space is at most countable. $\endgroup$
    – Not Mike
    Mar 29, 2011 at 19:33
  • 1
    $\begingroup$ I've heard "countable chain condition" (or "countable antichain condition") much more often. $\endgroup$
    – Todd Trimble
    Aug 16, 2015 at 16:37
  • 6
    $\begingroup$ @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.) $\endgroup$ Aug 16, 2015 at 23:49
  • $\begingroup$ @AndreasBlass Good to know! Thanks. $\endgroup$
    – Todd Trimble
    Aug 16, 2015 at 23:54
18
$\begingroup$

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:

http://googology.wikia.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

$\endgroup$
17
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ The bounding number $\mathfrak{b}$ turns out to be the precise bound needed to know when the product of two CW complexes is again a CW complex, a result due to Andrew Brooke-Taylor (arXiv:1710.05296, talk slides) $\endgroup$
    – David Roberts
    Jan 7, 2019 at 11:19
  • $\begingroup$ @DavidRoberts To my way of thinking, that paper is actually about when the product of CW complexes (as sequential spaces) is the same as their topological product. In the cases when they are not the same, it is really the sequential space product we ought to use, not the topological space one. $\endgroup$ Nov 11, 2019 at 11:44
  • $\begingroup$ @RobertFurber hmm, interesting. I guess the product of sequential spaces is the retopologising of the topological product such that closed sets are the sequentially closed sets? $\endgroup$
    – David Roberts
    Nov 12, 2019 at 4:16
  • $\begingroup$ @DavidRoberts Yes. $\endgroup$ Nov 12, 2019 at 5:17
17
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Maybe a bit nitpicky. But since 0 cannot be in a linear independent subset, I assume real line refers,to the set of nonzero real numbers. $\endgroup$ Nov 7, 2023 at 8:12
15
$\begingroup$

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

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Oct 22, 2009 at 23:39
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 23, 2009 at 0:30
  • 2
    $\begingroup$ "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 $\endgroup$ Oct 23, 2009 at 1:16
  • 8
    $\begingroup$ 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). $\endgroup$ Jul 4, 2010 at 4:27
  • 8
    $\begingroup$ 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. $\endgroup$ Oct 19, 2010 at 10:36
14
$\begingroup$

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.

$\endgroup$
14
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Shelah proved in On Ciesielski's problem, Journal of Applied Analysis, 3(1997), 191--209, that Martin's axiom implies the statement, so it does not imply CH. On the other hand, he also showed that adding $\aleph_2$ Cohen reals one obtains a model where the statement fails. $\endgroup$ Jul 24, 2019 at 6:30
  • $\begingroup$ I think this is my favorite because you could write it out for an undergrad or even advanced high school student and have them understand the claim. $\endgroup$ Nov 6, 2023 at 20:01
12
$\begingroup$

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.

$\endgroup$
12
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ Sorry, what's SCH? $\endgroup$ Jul 30, 2020 at 2:27
  • $\begingroup$ @Gerry I would guess the Singular Cardinals Hypothesis, but I don't know for sure. $\endgroup$
    – David Roberts
    Jul 30, 2020 at 4:50
  • 1
    $\begingroup$ @Gerry As David says, it's Singular Cardinals Hypothesis. $\endgroup$ Jul 30, 2020 at 13:12
  • $\begingroup$ Good. Thanks!$ $ $\endgroup$ Jul 30, 2020 at 13:13
11
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Where can I find Sierpinski proof for the kappa pairwise non-isomorphic suborderings? $\endgroup$
    – Holo
    Mar 1, 2019 at 15:14
10
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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.) $\endgroup$ Oct 24, 2015 at 1:40
  • 2
    $\begingroup$ 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)$. $\endgroup$ Nov 12, 2017 at 21:48
5
$\begingroup$

https://www.scottaaronson.com/blog/?p=2725

Busy Beaver $8000$ is independent of ZFC. I think this is in the same spirit of this question.

$\endgroup$
3
  • 5
    $\begingroup$ But this is not a statement. $\endgroup$ Apr 12, 2019 at 20:19
  • 3
    $\begingroup$ @AndrésE.Caicedo That's true. But I still think it's in the same spirit of the question. I guess if you tried hard enough you could find a statement. $\endgroup$
    – user138306
    Apr 12, 2019 at 20:27
  • $\begingroup$ This can be turned into the statement: The halting behaviour of 8000 state Turing Machine YA2016 is independent of ZFC. However, since this TM just looks for a counterexample to Friedman's purely finitary statement on order invariant graphs (already mentioned above by Timothy Chow), it is somewhat redundant. Or it should just be mentioned below Tim's answer as being a Corollary. $\endgroup$
    – John Tromp
    May 5, 2023 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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