22
$\begingroup$

Let the proof theoretic ordinal $\alpha$ of a theory $T$ be the least recursive ordinal such that $T$ does not prove that $\alpha$ is well-founded. This ordinal is intended to quantify in some sense the complexity or power of a theory.

Does anyone know what is the proof theoretic ordinal of $ZFC$ or any non-trivial $ZFC$ extensions? Wikipedia says this is unknown for $ZFC$ as of 2008, but maybe there has been some recent progress? Thank you.

Improve this question
$\endgroup$
4
  • 3
    $\begingroup$ I believe that proof-theoretic ordinals for much weaker theories (e.g., $\Pi^1_3$-$CA_0$, a subtheory of second-order arithmetic) are still unknown; the state of the art appears to be around $\Pi^1_2$-$CA_0$, if I understand the state of things correctly. $\endgroup$
    – Noah Schweber
    Commented Oct 5, 2013 at 20:03
  • 3
    $\begingroup$ No real progress towards this goal, in the sense that proof theory has a long way to go to reach $\mathsf{ZFC}$ or comparable theories. In some of his latest talks (on the consistency of $\mathsf{PA}$), Cohen suggested he had a way of understanding this ordinal $\alpha$, but I could never see a coherent presentation, and I doubt there was something sufficiently developed to allow us to unambiguously identify an ordinal as the proof-theoretic ordinal for $\mathsf{ZFC}$. $\endgroup$
    – Andrés E. Caicedo
    Commented Oct 5, 2013 at 20:04
  • 1
    $\begingroup$ For example, already an analysis of $\Pi^1_2$-$CA_0$ by Rathjen required very complicated ordinal notations, and recently (see the intro to miami.uni-muenster.de/servlets/DerivateServlet/Derivate-5965/…) a serious error was found (and patched, I think) in Rathjen's work around this level. $\endgroup$
    – Noah Schweber
    Commented Oct 5, 2013 at 20:05
  • $\begingroup$ That's helpful, thank you both Noah and Andres. I will take a look at that Rathjen reference. $\endgroup$
    – user40919
    Commented Oct 5, 2013 at 20:35

1 Answer 1

Reset to default
16
$\begingroup$

As Andres and I have stated in the comments, we are still nowhere near a proof-theoretic analysis of $ZFC$ or similar theories; even full second-order arithmetic remains well out of reach.

The paper "The Art of Ordinal Analysis" by Michael Rathjen does a good job of both describing ordinal analyses which have succeeded (e.g., $PA$), and showing how new difficulties arise as we climb towards higher and higher comprehension axioms (still around the level of $\Pi^1_2$-$CA_0$ by the end of the paper). I think this might be worth reading, if you want an explanation of why finding proof-theoretic ordinals of strong theories is "hard."

Improve this answer
$\endgroup$
11
  • 8
    $\begingroup$ Re: total lay-person-ness, let me clarify something: in the realm of proof-theoretic ordinals, I don't actually "know" anything. On the plus side, I have read a number of survey articles, and nodded my head sagely through dozens - dozens! - of conversations on the subject. :P $\endgroup$
    – Noah Schweber
    Commented Oct 5, 2013 at 20:54
  • 2
    $\begingroup$ That said, I think that understanding the ordinal for $SOA$ (or even its fragments) is thought to be necessary for finding the ordinal for $ZFC$, for at least three reasons: $\endgroup$
    – Noah Schweber
    Commented Oct 5, 2013 at 20:55
  • 2
    $\begingroup$ First of all, since $SOA$ is a subtheory of $ZFC$, all the difficulties of analyzing $SOA$ will surely show up in trying to analyze $ZFC$; so at the very least, $SOA$ should be far easier to understand than $ZFC$. (In particular, I expect $SOA$ to be analyzed in my lifetime; I do not expect that of $ZFC$, and in fact would be very surprised if I lived to see it.) $\endgroup$
    – Noah Schweber
    Commented Oct 5, 2013 at 20:56
  • 2
    $\begingroup$ Second, $SOA$ and $ZFC$ aren't really that alien; already in analyzing subtheories of $SOA$, it has been extremely useful to recast them as weak set theories, such as $KP$; see section 2.2 of Rathjen's paper. So in analyzing bigger and bigger subsystems of $SOA$, we're already "climbing towards" $ZFC$ in some sense; it seems reasonable that this will be how we eventually get to $ZFC$. So then not only is $SOA$ likely easier than $ZFC$, it is probably an actual "step along the way." $\endgroup$
    – Noah Schweber
    Commented Oct 5, 2013 at 20:59
  • 2
    $\begingroup$ Finally, the techniques used in ordinal analyses have been revolutionized multiple times already in the course of getting to (somewhere around) $\Pi^1_2$-$CA_0$. The twist that is dearest to my heart is the use of uncountable cardinals in ordinal notations developed by Bachmann (mentioned by Rathjen on pp. 11), but Rathjen's article describes a number of interesting developments. The point is, "ordinal analysis" is not one specific tool that could reach $ZFC$ if we just put more effort into it; rather, it has needed many fundamentally new ways of thinking even to get up to $\Pi^1_2$-$CA_0$. $\endgroup$
    – Noah Schweber
    Commented Oct 5, 2013 at 21:04

You must log in to answer this question.

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