I am looking for class of math problems which are provable in ZF if and only if they are provable in ZFC

I know that P vs NP and Riemannian hypothesis are of this class but could not find any article on that. I would also appriciate links or books on related theme. My question is: what are some other problems of the same class and how one proves such property? I am by the way undergrad of math.

Solution 1:

The relevant term here (but see the end of this answer) is absoluteness. Basically, say that a statement is absolute between two structures if its truth in one implies its truth in the other and vice versa. There is also "directional" absoluteness: if $A$ is a substructure of $B$ we say that a statement $\varphi$ is upwards-absolute (with $A$ and $B$ implicit from context) if its truth in $A$ implies its truth in $B$, and downwards-absolute if the reverse holds.

Absoluteness first rears its head (although often via different terminology, e.g. "preserved" and "reflected") in basic model theory and universal algebra. For example, one of the earliest results of this type one sees is the following:

Suppose $\mathcal{A}$ is a substructure of $\mathcal{B}$ and $\varphi(x_1,...,x_n)$ is a quantifier-free first-order formula. Then if $\forall x_1,...,x_n\varphi(x_1,...,x_n)$ is true in $\mathcal{B}$, it is also true in $\mathcal{A}$.

Put another way, this says that universal sentences are downwards-absolute between any structure-substructure pair. A more intricate result is Birkhoff's HSP theorem, which develops a connection both ways: it gives a characterization of when two algebraic structures have the same "equational" theory. If memory serves, Hodges' big model theory book has a lot of interesting information about this sort of thing.

However, "simple" absoluteness results such as the above are quite limited and certainly don't come close to applying to situations of the type we care about here. In order to bring absoluteness into play in set theory, we have to do a lot more work.

The key (initially at least; later on it gets supplanted by more complicated analogues) is the following result of Godel, which I'll phrase informally for readability:

Any model $V$ of $\mathsf{ZF}$ has a substructure $L$ satisfying $\mathsf{ZFC}$. (Moreover, $L$ is "nicely definable" inside $V$ and generally has a number of other excellent properties.)

This tells us the following: if $\varphi$ is upwards-absolute between models of $\mathsf{ZF}$, then its $\mathsf{ZFC}$-provability implies its $\mathsf{ZF}$-provability. This is because if $\varphi$ is upwards-absolute between models of $\mathsf{ZF}$ and is $\mathsf{ZFC}$-provable, we must have that $\varphi$ is true in every model $V$ of $\mathsf{ZF}$ (hence be $\mathsf{ZF}$-provable) since it is true in $L$ due to $L$'s satisfying $\mathsf{ZFC}$.

The idea then is that similarities between $V$ and $L$ can be turned into absoluteness results. For example, any arithmetical statement (basically, referring only to natural numbers) cannot rely on choice. This comes from looking at the construction of $L$: it turns out that $V$ and $L$ "have the same natural numbers" in a precise sense, and so they cannot disagree about arithmetical facts. Many mathematical principles, including the vast majority of results and conjectures in number theory, are either explicitly arithmetical (e.g. Fermat's last theorem or P=NP) or $\mathsf{ZF}$-provably equivalent to an arithmetical statement (e.g. see here re: RH).

The next two absoluteness theorems important enough to have names are Mostowski absoluteness which says that all "statements about well-foundedness" are absolute between $V$ and $L$ (hence cannot rely on choice), and Shoenfield absoluteness which applies Mostowski to prove that all $\Pi^1_2$ statements (a rather technical notion, but one which is incredibly encompassing - my understanding is that all the Millenium Problems for example, fall into this category) are absolute between $V$ and $L$. We also have higher absoluteness results contingent on additional set-theoretic hypotheses, the latter of which are called "large cardinal axioms" (and have some pretty neat names). Like Shoenfield these higher absoluteness results tend to come from clever applications of Mostowski absoluteness, but these applications are much more intricate, and in particular require us to develop more complicated analogues of Godel's $L$ as hinted at above.

These stronger absoluteness results are genuinely hard to summarize, let alone sketch proofs of. The above paragraph should however have indicated that Mostowski's principle plays an especially central role here. This is indeed true; moreover, it is by far the most approachable of the higher absoluteness theorems. Like arithmetical absoluteness, it comes from a simple observation, namely that $V$ and $L$ "have the same ordinal numbers." This, together with some thinking about transfinite recursion, ultimately gives the desired result.

But going back to the start of this answer, even before Mostowski - even before arithmetical absoluteness! - is that beautiful result of Godel about a thing called "$L$." While quite difficult, this is one of the absolute (hehehehe) jewels of set theory, and it is well worth your time.

OK, there is one useful bit of terminology I've omitted above. I chose to focus on structures, since I think that's the most intuitive framing. However the question itself was posed at the level of theories instead: $\mathsf{ZF}$ and $\mathsf{ZFC}$ are sets of sentences describing structures, not structures themselves.

With this in mind, there is another relevant term: conservativity. Given two theories $T,S$ with $S$ possibly in a larger language, we say $S$ is a conservative extension of $T$ iff $(i)$ $S$ proves everything that $T$ does in the language of $T$ but $(ii)$ those are the only things which $S$ proves in that language. Basically, $S$ is a conservative extension of $T$ iff

If the language of $S$ is no bigger than the language of $T$, then $S$ is a conservative extension of $T$ iff $S$ and $T$ are "basically the same" (= prove the same things). However, there are also weakenings of conservativity which are non-trivial even if the languages are the same: namely, we can talk about conservativity restricted to sentences of a certain form. For example, the arithmetical absoluteness result above has the following consequence, which is really what you were asking about:

$\mathsf{ZFC}$ is conservative over $\mathsf{ZF}$ for arithmetical sentences.

So properly speaking, "absoluteness" is about comparing models while "conservativity" is about comparing theories. It's also worth noting that there are many variations on the notion of conservativity - see e.g. here.

Solution 2:

I wrote a short note about exactly this.

Asaf Karagila, Absolutely Choiceless Proofs, arXiv:1402.3048 (2014)

The idea is, as the others have remarked, to use absoluteness, but not just for questions on number theory. Instead we focus on a set theoretic absoluteness.

We say that a quantifier is ordinal bounded if it quantifies about sets of finite tuples of ordinals (using the usual coding this is the same as quantifying over sets of ordinals, but it does make the statement a bit more natural).

Theorem. Suppose that $\varphi(x)$ is a formula that is upwards absolute between $L$ and $V$, then $\forall^{\sf Ord}x\,\varphi(x)$ is provable from $\sf ZF$ if and only if it is provable from $\sf ZFC$.

That is a somewhat trivial observation, but it formalises the idea that is used in quite a few places. For example, many questions in transfinite Ramsey theory are framed as "given a partition of $[\alpha]^n$, is there a homogeneous set of such and such properties?", and since the focus is partitions of ordinals, this is exactly an example for a statement that is quantified with ordinal bounded quantifiers.

(I should warn that the note was intended to be fleshed out into a paper, but that never happened since I moved my focus to other problems.)

Solution 3:

Noah gave a great answer, which is probably worth pursuing.

But in terms of the question that you actually asked, one can give a complete, comprehensive answer.

Namely, the set of statements $\varphi$ with the property that they are provable in ZF if and only if they are provable in ZFC consists precisely of the statements $\varphi$ which are either

• provable in ZF, or
• not provable in ZFC.

This is easy to see. If $\varphi$ is provable in ZF, then it is also provable in ZFC. And if $\varphi$ is not provable in ZFC, then it is not provable in ZF. So either of those properties is sufficient for the equivalence. And if $\varphi$ is provable in ZF iff provable in ZF, then it will either be provable in both or neither, and so either provable in ZF or not provable in ZFC. So the properties are necessary.

But since this kind of answer probably isn't what you wanted, and in that case I would suggest that you might not have asked the question you had intended.