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

Improve this question
$\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$
    – Ilya Nikokoshev
    Commented Oct 22, 2009 at 21:41
  • 15
    $\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$
    – Anton Geraschenko
    Commented Oct 22, 2009 at 21:49
  • 5
    $\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$
    – Ilya Nikokoshev
    Commented Oct 22, 2009 at 22:10

34 Answers 34

Reset to default
1
2
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.

Improve this answer
$\endgroup$
3
  • 5
    $\begingroup$ But this is not a statement. $\endgroup$
    – Andrés E. Caicedo
    Commented 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
    Commented 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
    Commented May 5, 2023 at 10:45
4
$\begingroup$

I want to expand on Yoo’s comment about a problem equivalent to the Continuum Hypothesis. CH is equivalent to there being a coloring of the real number plane with a countable amount of colors such that there are no (triangles with one line parallel to the y axis, and another line parallel to the x axis) whose corners are all the same color. Maybe someone will make an argument as to which answer is reasonable. The answer that there is a coloring or that there isn’t, but whatever answer gets offered it will be independent of ZFC. Here’s the link from Yoo. https://artofproblemsolving.com/community/c7h137999 And here’s a post from Rising Entropy. https://risingentropy.com/a-coloring-problem-equivalent-to-the-continuum-hypothesis/

Improve this answer
$\endgroup$
2
$\begingroup$

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

Improve this answer
$\endgroup$
14
  • 4
    $\begingroup$ 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? $\endgroup$
    – Emil Jeřábek
    Commented Nov 12, 2017 at 9:11
  • $\begingroup$ Sorry, I didn't mean for $h$ to be a set :/ $\endgroup$
    – Zetapology
    Commented Nov 12, 2017 at 15:49
  • 1
    $\begingroup$ @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? $\endgroup$
    – Noah Schweber
    Commented Nov 12, 2017 at 18:47
  • 4
    $\begingroup$ 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.") $\endgroup$
    – Noah Schweber
    Commented Nov 12, 2017 at 19:45
  • 2
    $\begingroup$ Incidentally, the definable version of "$Ord$ is weakly compact" fails - see this paper of Enayat and Hamkins. $\endgroup$
    – Noah Schweber
    Commented Nov 12, 2017 at 19:50
1
$\begingroup$

This ones kind of obvious, but

"ZFC does not derive a contradiction"

is independent of ZFC (hopefully). The mathematical community has built the foundations of mathematics on that statement, so I would say its reasonable.

Improve this answer
$\endgroup$
11
  • 2
    $\begingroup$ The question asks for "statements that aren't directly set-theoretic". I don't think any statement containing "ZFC" qualifies. $\endgroup$
    – Gerry Myerson
    Commented Feb 15, 2019 at 12:18
  • 10
    $\begingroup$ @Gerry: To be fair, Con(ZFC) is a number theoretic statement... :-) $\endgroup$
    – Asaf Karagila ♦
    Commented Feb 15, 2019 at 15:21
  • 2
    $\begingroup$ @Gerry: I draw the line at $0<1$. But that's just me... $\endgroup$
    – Asaf Karagila ♦
    Commented Feb 15, 2019 at 21:40
  • 1
    $\begingroup$ @GerryMyerson after Gödel coding, CH is a particular number, not a number-theoretic statement $\endgroup$
    – Alex Kruckman
    Commented Jul 23 at 13:23
  • 1
    $\begingroup$ I've checked my knickers, and I don't see any twists. I just think it's important to correct common misconceptions :0) Statements in the language of ZFC are usually not number-theoretic - they are not equivalent to statements about the natural numbers in the language of arithmetic. But statements about ZFC, e.g. about what it can and cannot prove, are number-theoretic. $\endgroup$
    – Alex Kruckman
    Commented Jul 23 at 13:37
1
2

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .