21
$\begingroup$

Dmytro Taranovsky has a Web page on which he claims to define a system of ordinal notations strong enough to provide an ordinal analysis of full second-order arithmetic. I think (perhaps unjustly) that this claim is suspicious, since from my passing acquaintance with the subject I seem to understand that the state of the art of ordinal analysis was around $\Pi^1_2$-comprehension (e.g., Jan-Carl Stegert's doctoral dissertation building on work by Michael Rathjen), the ordinal notation systems involved are considerably more complex (reflection instances, collapsing hierarchies), and Taranovsky mentions none of this. On the other hand, a superficial look at his page does seem to make some kind of sense, and my interest in the subject is to choose the largest possible system of ordinal notations which isn't too fastidious to implement on a computer (i.e., I'm not concerned with the proof-theoretic aspect).

So before I decide to read it in great detail or not, I'd like an expert's opinion: what is to be thought of Taranovsky's ordinal notation systems? (Might they define an ordinal which is not as large as claimed? Or perhaps which could be as claimed but would be very difficult to analyse?)

$\endgroup$
  • 2
    $\begingroup$ I've analyzed one of Taranovsky's notations (the one currently under "Degrees of Recursive Inaccessibility") and I believe that most of his evaluations of his ordinals are correct; in particular, the notation C(C(2, 0, 0), 0) does seem to be the ordinal for Pi-1-1 transfinite recursion, or psi(Omega_Omega_Omega...). So even this early notation is quite strong. However, it does seem that his notation for second-order arithmetic is simpler than purportedly much weaker notations from Rathjen. So I don't know. My first doubts start to creep in when he talks about Pi-n reflection for n > 3. $\endgroup$ – Deedlit Mar 12 '13 at 0:52
  • 2
    $\begingroup$ Taranovsky's page has been updated some time ago with some proofs (not to mention the overall revisions which have happened over the years). I would love to see this question revisited, but I'm afraid the notation has still not received enough attention to have been independently analysed... $\endgroup$ – Wojowu Feb 22 '17 at 21:07
10
$\begingroup$

When Taranovsky announced his system on the Foundations of Mathematics mailing list on March 23, 2012, he wrote:

I discovered a conjectured ordinal notation system that I conjecture reaches full second order arithmetic.

The webpage you linked to has a slightly later date (April 7, 2012) but again, in the section "Ordinal Notation for Second Order Arithmetic," he says:

I conjecture that the strength of the nth ordinal notation system is between Π1n-1-CA and Π1n-1-CA0 (see the previous section for detailed correspondence), and thus the sum of the order types of these ordinal notation systems is the proof-theoretical ordinal of second order arithmetic.

So at the time, his claim was still conjectural. I do not recall seeing any responses to Taranovsky's FOM post. I'd recommend you contact him directly to learn the current status.

$\endgroup$
3
$\begingroup$

In this section of the paper Taranovsky gave a proof of well-foundedness of the system for the $C_0,C_1$ and $C_2$ subsystems of the version of $C$ defined in "Built-from-below with Passthrough for Lower Levels", and then, using a different approach, does so for $C_i$ for all $i$. The proof for $C_0,C_1,C_2$ is in ZFC, while the proof for $C_i$ is in ZFC + Measurable Cardinal. It's improtant to note that the system up to $C_\omega$ is (probably) bounded by $C(C(\Omega_2\omega,0),0)$ for the main system. People often confuse $C_i(\alpha,\beta)$ with the $n=i$ system of the main $C$. "Built from below with passthrough" C is believed to be bounded by $C(C(\Omega_2\omega,0),0)$ because for each $i$, the limit of everything constructible in $C_i(\alpha,\beta)$ for $\alpha,\beta$ are standard in the language of $\bigcup C_i$, where all ordinals $\eta$ standard in $C_n$ are built from below with passthrough by $C_{n+1}$ standard ordinals above $\eta$, seems to be $C(C(C^{i+1}(\Omega_2,\Omega_2),0),0)$ in it's standard represntation where $C^0(\alpha,\beta)=\beta\land C^{n+1}(\alpha,\beta)=C(\alpha,C^n(\alpha,\beta))$. If this is true, it would imply that the limit of everyhting constructible in $C_i$ is $C(C(\Omega_2i+\Omega_2,0),0)$. For lower values of $i$, this seems to hold. $C_0$ is only allowed to use ordinals build from below by other ordinals within it, so in can only hold finite expressions and nothing of the form $C(\alpha,\beta)$ for uncountable ordinals $\alpha,\beta$, and is therefore limited by the least $\alpha$ such that $\alpha\mapsto C(\alpha,0)$, which happens to be $\varepsilon_0$. In the main notation, $\varepsilon=C(\Omega_1,0)$ which is in it's standard representation in the $n=1$ system and is in the standard represntation $C(C(\Omega_2,0),0)$ in the $n=2$ system. Simple enough analyses can show that the limit to everything constructible in $C_1$ is $C(C(\Omega_2 2,0),0)$ and Taranovsky showed a brief conjectureand explanation of how $C(C(\Omega_2 3,0),0)$ is possibly the limit to everything expressible in $C_2$, but a full induction for $\sup\{C_i(\alpha,\beta):\alpha,\beta\in \bigcup C_i\cap\text{Stand}\}=C(C(\Omega_2\cdot(i+1),0),0)$ implying the same sentence for $C_{i+1}$ has not been proven yet.

It's interesting that Taranovsky wasn't able to provide a proof for $C_i$ for all $i$ within ZFC and had to resort to assuming the existence of Measurable Cardianls in order to prove well-foundedness for $C_i$. Perhaps such proof doesn't exist, or perhaps it does exist but it's very long and complicated and hard to think of, possibly stretching the limits of ZFC. If a theory $T$ can prove well foundedness of a recursive ordinal notation, then the limit of that notation is an ordinal below the proof-theoretic ordinal of $T$. If ZFC can't prove $C_\omega$ recursive/well-founded and the language of $C_i$ is limited by $C(C(\Omega_2i+\Omega_2,0),0)$ are both correct, then that would imply that $C(C(\Omega_2\omega,0),0)$ is equal to or larger than the proof-theoretic ordinal of ZFC. This is highly unlikely, because a proof in ZFC for $C_i$ most likely exist and not even Taranovsky himself has given such high possible values for $C(C(\Omega_2\omega,0),0)$, which was actually proposed to be the proof-theoretic ordinal of Second Order Arithmetic by the most reacent analysis.

Originally, Taranovsky believed that the limit of each $n+1$ system is within the range of $|\Pi^1_n-\text{CA}_0|_\text{Con}$ and $|\Pi^1_{n+1}-\text{CA}_0|_\text{Con}$, which is now considered wrong, and the overall system is believed to be much stronger. This is where the prosition of the "n-shiftedness" property comes in. This is perhaps the most important property when it comes to the strength of Taranovsky's $C$ and is one of the reasons it's so hard to analyse.

Firstly, how strong the notation is depends almost entirely on one factor - how strong "n-built from below" works for sufficiently large ordinals. In basic terms, $\alpha$ is 0-built from below by $\beta$ iff $\alpha<\beta$ and $\alpha$ is $k+1$-built from below by $\beta$ iff the standard representation of $\alpha$ does not use ordinals above $\alpha$, except for ordinals in the scope of an ordinal that is $k$-built from below by $\beta$. We say an ordinal $\alpha$ is in the scope of an ordinal $\beta$ iff $\alpha$ appears somewhere in the standard representation of $\beta$ within the lexicographic string in the language $\{C,0,\Omega_n\}$ that represents precisely $\beta$ within the respective $n$ system.

The reason why "n-build from below" is so important is because it's a crucial part of defining which ordinals are standard and which are not. The thing which makes Taranovsky's notation so unique is that it's not defined simply by recursion. Instead, it gives you rules that tell you the universal set of all ordinals standard in the notation and all strings valid in it, and from there you have to use the binary function $C$ as a hierarchy that connects them. In order to answer why it's so strong, first we need to ask what makes a notation strong in general. For ordinal notations, one is cosidered strong if it can express really large ordinals, but for recursive notations, they should be able to express everything below a certain ordinal, especially for notations like Taranovsky's. So it's fare to say that a recursive ordinal notation is strong if it can express "a lot" of ordinals. (whatever "a lot" means for infinities) In the case of Taranovsky's notation, which can express every ordinal below it's limit, how many terms are valid in it depends soley on the requirements for and ordinal to be valid (standard) and for that we need the ordinal $C(\alpha,\beta)$ to be standard and one of the 3 requirements for that is that $\beta$ has to be n-built from below by $C(\alpha,\beta)$.

For large ordinals, however n-bult from below starts to behave irregularly, and we get this weird property of "n-shiftedness" of functions. Typically, each ordinal that has a standard representation in a particular $n+1$-system but not in the $n$-system is a result of an $n$-shifted function. We say that a function is $n$-shifted if it's supremums are within another "layer" or nesting in the function. I know this definition is not formal, but formalizing it is aqtually quite difficult. For example, the least fixed point of $\alpha\mapsto C(\Omega_1 2+C(\Omega_1+\alpha,0),0)$ is $C(\Omega_1 2+C(\Omega_1 2,0),0)$, so this expression is not shifted. Meanwhile, the least fixed point of $\alpha\mapsto C(\Omega_2 2+C(\Omega_2+\alpha,0),0)$ is $C(\Omega_2 2+C(\Omega_2+C(\Omega_2 2,0),0),0)$ and the least fixed point of $\alpha\mapsto C(\Omega_3 2+C(\Omega_3+\alpha,0),0)$ is $C(\Omega_3 2+C(\Omega_3+C(\Omega_3+C(\Omega_3 2,0),0),0),0)$. Generally, we say that a function is $0$-shifted if it has no shiftedness properties and that a function is $n+1$-shifted if it has a $1$-shiftedness property of reflection above $n$-shifted functions within the same system. The $n=1$ system is 0-shifted, and that's why it's similar to many other Ordinal Collapsing Functions, the $n=2$ system is 1-shifted and that's why it's stronger than pretty much everything else. Generally any $n+1$ system of Taranovsky's C is $n$-shifted. This may seem like a small thing, but it totally changes the set of all ordinals standard in that notation, which we mentioned is precisely it's strength. Most other notations are $0$ shifted, so even if they seem very strong, they likely fall within the range of Taranovsky's second system.

The reason the entire notation turned out to be strnger than Taranovsky expected was because $C(\Omega_2 2,0)$ behaved irregularly and had a 1-shifted property of reflection over $C(\Omega_2+\alpha,0)$ ordinals and, simlarly, $C(\Omega_2 3,0)$ had a 1-shifted property of reflection above ordinals $C(\Omega_2 2+\alpha,0)$. It turned out that the 1-shifted reflection property of $C(\alpha+\Omega_2,0)$ over ordinals $C(\alpha+\beta,0)$ boosted the notation from it's limit to $C(\Omega_2\omega,0)$. This is precisely why, while the notation used to be thought of as limited by $Z_2$, the proof-theoretic ordinal of $Z_2$ is now belived to be $C(\Omega_2\omega,0)$. This is also precisely why the $C_i$ notation was defined, to be equivalent to what the main notation was believed to be. It just happens that $C(\alpha+\Omega_{n+1},0)$ has $n$-shifted reflection properties over ordinals $C(\alpha+\beta,0)$ and within the $n=2$ system, which is 1-shifted, we see a mild "shadow" of higher $n$-shifted properties for ordinals within it. In Taranovsky's words "Similar patterns repeat at different levels of the strength hierarchy". Overall, as it turned out that n-built from below was actually stronger than expected for ordinals standard in the $n=2$ system, Taranovsky had to form a new approximation method for n-built from below, according to which, the entire notation might reach as far as the proof-theoretic ordinal of $Z_2+\text{PD}$. None of this has been confirmed, and analyses have not gone beyond $C(C(\Omega_2 2+C(\Omega_2+C(\Omega_2,C(\Omega_2 2,0))^{C(\Omega_2,C(\Omega_2 2,0))^\omega},0),0),0)$ due to exhaustion with other ordinal notations not being sufficiently strong to provide ordinals beyond that, in order to be compared further.

Sadly, other than Taranovsky's notation being hard to compare with, the other reason it has not been done so much is because it hasn't yet gotten much attention from people qualified enough to do so.

$\endgroup$
  • 1
    $\begingroup$ One thing that would help convince that Taranovsky's system is indeed strong would be to express in a systematic way (or at least by providing numerous examples) the terms of other well-understood systems, say Arai's or the ones in Stegert's thesis, into T's own. If one could see that very large ordinals described by these other systems are convertible in T's, are compared in the same way, and are much beneath what T's can describe, this would substantiate the claim that T's system is indeed very strong. [contd.] $\endgroup$ – Gro-Tsen Feb 16 '18 at 9:55
  • 1
    $\begingroup$ [contd.] Personally, even though I am not an expert, what disturbed me about T's system is that it seems to have no equivalent of the hierarchies described by the other systems I mentioned. I am not at all convinced that T's system can adequately describe, for instance, the ordinals which are $\Pi_2$-reflecting on the $\Pi_3$-reflecting ordinals (the sort of things which makes analysis of $\Pi_4$-reflecting ordinals much more difficult than $\Pi_3$, as explained in Duchhardt's and Stegert's theses). $\endgroup$ – Gro-Tsen Feb 16 '18 at 10:04
  • $\begingroup$ For your sepcific question, it is $C(\Omega_2+C(\Omega_2,C(\Omega_2 2,0))^{C(\Omega_2,C(\Omega_2 2,0)) + \alpha},\beta)$ that is believed to correspond to the least ordinal above $\beta$ that is $\alpha-\Pi_2$-reflecting onto $\Pi_3$-reflecting ordinals. $\endgroup$ – Boris Dimitrov Feb 16 '18 at 12:16
  • $\begingroup$ Generally, it's belived that for $a=C(\Omega_2 2,0)\land b=C(\Omega_2,\alpha)$ for expressions inside $C(\Omega_2 2+\text{___},0)$ the following are true: $a$ inside $C(\Omega_2+a,0)$ corresponds to the recursively inaccessible; $C(C(\Omega_2 2+C(\Omega_2+b,0),0),0)$ is the proof-theoretic ordinal of KPi; $C(\Omega_2+b2,0)$ corresponds to the recursively Hyperinaccessible; $C(\Omega_2+b^2,0)$ corresponds to the recursively Mahlo; $C(\Omega_2+b^{2+\gamma},0)$ corresponds to the recursively $\gamma$-Mahlo; $C(\Omega_2+b^b,0)$ corresponds to the recursively Compact; $\endgroup$ – Boris Dimitrov Feb 16 '18 at 12:23
  • $\begingroup$ forgot to mention that within $C(C(\Omega_2 2+\text{___},0),0)$ $C(\Omega_2+b^{b^n},\alpha)$ should correspond to the least $\Pi_{n+2}$-reflecting ordinal above $\alpha$ and $C(\Omega_2+b^{b^\omega},\alpha)$ should be the least 1-stable ordinal above $\alpha$ for the same definition of $b$ used in the previous comment. $\endgroup$ – Boris Dimitrov Feb 18 '18 at 20:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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