I read the Wikipedia article on Absoluteness recently and found mention of Shoenfield’s Absoluteness Theorem, which states that if $ \phi $ is any $ \Sigma^{1}_{2} $- or $ \Pi^{1}_{2} $-sentence of second-order arithmetic, then $ \phi $ is absolute between any two models of $ \sf ZF $ that have the same ordinals. The article says that the Riemann Hypothesis and the $ \sf P $-versus-$ \sf NP $ Problem can be expressed as $ \Pi^{1}_{2} $-sentences, so if these two statements happen to be independent of $ \sf ZF $, then it is not possible to use the method of forcing to establish their independence.

Ever since Cohen invented forcing in 1963, no other essentially new technique has been found of creating models of set theory (maybe inner model theory counts as a new technique in the sense of the post-1970 works of John Steel and Ronald Jensen on the core model, but I believe that the main idea behind inner model theory goes back to either von Neumann or Gödel). Hence, to cut the long story short, my question is:

Do current experts in set theory have any idea about what new methods of proving independence results would involve? Do they believe that finding a new method of proving independence results is within the reach of current technology?

  • $\begingroup$ Inner models began with von Neumann and his proof that regularity can be added or removed without affecting the consistency of the theory. $\endgroup$
    – Asaf Karagila
    Mar 15, 2013 at 11:08
  • $\begingroup$ @Asaf: It’s always a pleasure to receive your quick responses! :) Thanks for clarifying that point. $\endgroup$ Mar 15, 2013 at 11:11
  • $\begingroup$ I also have two problems with the question posted here. First of all, not that many experts roam this site. There are a few, and there are a few more in MathOverflow. But I don't know if enough people to actually answer. The second issue is that many problems which are "of interest of set theorists" are not number theoretically expressible. That is, they are not problems one can write in a $\Pi^1_2$ statement, or so, in the language of arithmetic. So even if a new method would arise, there is no guarantee that it will have any implications on RH and so on. $\endgroup$
    – Asaf Karagila
    Mar 15, 2013 at 11:11
  • $\begingroup$ And lastly, to drive that second point home, what Shoenfield's theorem is really telling us that if you want to prove that RH is independent of ZF you will have to come up with a way of producing models with different ordinals. Otherwise the same issues as with forcing come up again. But set theorists love the fact that the ordinals between a model and its extensions are the same. For example the rank is absolute, so if you have the same ordinals then the amount of new sets that were added was "reasonable". If you add new ordinals, or change them altogether, how can you control the additions? $\endgroup$
    – Asaf Karagila
    Mar 15, 2013 at 11:14
  • 3
    $\begingroup$ There are actually at least two very interesting programmes that run orthogonal to developing new techniques of establishing independence from ZFC. Woodin's "Ultimate $L$" programme (see also the posts from Andrés Caicedo's blog) and Sy Friedman's "Hyperuniverse" programme have the aim of refining/restricting our concept of the "universe" of sets. (In particular, Ultimate $L$ would imply that CH is true!) $\endgroup$
    – user642796
    Mar 15, 2013 at 11:48

1 Answer 1


Nice question. Let me first point out that the Riemann Hypothesis and $\mathsf{P}$-vs-$\mathsf{NP}$ are much simpler than $\Pi^1_2$: The former is $\Pi^0_1$, see this MO question, and the assertion that $\mathsf{P}=\mathsf{NP}$ is a $\Pi^0_2$ statement ("for every code for a machine of such and such kind there is a code for a machine of such other kind such that ..."). The difference in the superscript is that these are arithmetic statements, so we do not need to quantify over reals.

I think versions of your question have been asked before here and on MO, so you may find additional remarks if you search there for a bit. In particular, let me point you to this question, and my answer there. Briefly:

A natural approach to showing that a statement is independent of $\mathsf{ZFC}$ is to show that it holds in a small inner model, such as $L$, while its negation follows from appropriate large cardinal hypotheses. For example, projective determinacy and many of its consequences are statements of this kind. In fact, more and more levels of the projective hierarchy are forcing invariant as we climb through the consistency strength hierarchy. (For a bit more on this, see this MO question.) There is much more that can be said on the role of large cardinals, the inner model hypothesis, the ultimate $L$ program, etc, but I do not think these are examples of the developments your question is about, and this still does not address statements that are $\Pi^1_2$ or of lower complexity.

It would be a major breakthrough (larger even than the development of forcing) if we figure out a technique that changes (truth in) the standard model of arithmetic.

If at all possible, I do not think we are anywhere near achieving that.

Short of it, work for establishing consistency/independence of arithmetic or low-level projective statements focuses on producing non-standard models, in fact, models that are not $\omega$-models (that is, models whose version of $\omega$ is non-standard).

Harvey Friedman has been particularly successful here, and he has produced a body of examples from finite combinatorics that are independent of $\mathsf{ZFC}$. The origin of this idea comes from the Paris-Harrington theorem showing the independence of a strengthening of Ramsey's theorem from $\mathsf{PA}$ via the method of indicators.

Most of his approach is explained in his monograph on Boolean Relation Theory, available from his page. His results tend to involve large cardinals as well. The idea is that we use the large cardinals to prove the combinatorial statement under consideration. For arithmetic statements $\phi$, this of course means that the result is true in $\omega$. We then produce appropriate non-$\omega$-models of $\mathsf{ZFC}$ where the statement fails. The construction here is delicate, and not as malleable as using forcing. But his monograph and many of his papers show plenty of applications.

You see why this approach is slightly unsatisfactory, since we know which statement ($\phi$ or $\lnot\phi$) is true, regardless of whether $\mathsf{ZFC}$ is strong enough to establish it. (This is why it would be so significant to have "forcing-like" tools affecting the standard model of arithmetic.) On the other hand, the large cardinals typically involved in many of his examples are "small" (in the neighborhood of Mahlo cardinals), so we may as well think of his approach as producing examples of statements independent of $V=L$, which in itself is remarkable.

Still, we are far from what would be ideal. There is a quote from the Boolean Relation Theory book that I included in one of the links above, but let me repeat it here:

There were no candidates for Concrete Mathematical Incompleteness from ZFC being offered. In fact, to this day, no candidates for Concrete Mathematical Incompleteness have arisen from the natural course of mathematics.

To drive the point home: I do not see any way of adapting the known techniques to establish the independence of "natural" problems such as the Riemann hypothesis, $\mathsf{P}=\mathsf{NP}$, or many of their humbler relatives. Even forgetting $\mathsf{ZFC}$ and doing this in the context of $\mathsf{PA}$ seems out of reach, even though there is a large literature on models of $\mathsf{PA}$ and (arithmetic) combinatorial statements independent of $\mathsf{PA}$, with plenty of techniques not available for set theory.

  • 1
    $\begingroup$ Thank you so much for this wealth of information! $\endgroup$ Mar 15, 2013 at 17:03

You must log in to answer this question.

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