Question: What are some natural examples of recursive pseudowellorderings?

By natural, I mean in the style of reasonable ordinal notation systems as opposed to dependent on a Gödel numbering or an enumeration of Turing machines.

A recursive pseudowellordering is a non-well-founded recursive linear order that does not have hyperarithmetic infinite descending sequences. Its significance is that its initial well-founded segment has order type $ω_1^{\mathrm{CK}}$, which is above all recursive ordinals. In a way, it acts as a universal ordinal notation system because we can specify an initial well-founded segment and get an ordinal notation system with arbitrary recursive length, with the notation of an ordinal independent of the segment used (and unlike Kleene's $\mathcal{O}$, a recursive pseudowellordering is recursive). (However, my guess is that it will be impractical, and in particular that if $α$ is too large, its notation size will in a sense be related to a fast-growing function based on $α$.)

Using Gödel numbering, here is an example recursive pseudo-well-ordering (quoted from a Wikipedia article but originally written by me):
Let S be ATR0 or another recursively axiomatizable theory that has an $ω$-model but no hyperarithmetical $ω$-models, and (if needed) conservatively extend $S$ with Skolem functions. Let $T$ be the tree of (essentially) finite partial $ω$-models of $S$: A sequence of natural numbers $x_1,x_2,...,x_n$ is in $T$ iff $S$ plus $∃m \, φ(m) ⇒ φ(x_{⌈φ⌉})$ for the first $n$ formulas $φ$ with one free numeric variable ($⌈φ⌉$ is the Gödel number) has no inconsistency proof shorter than $n$. Then the Kleene–Brouwer order of $T$ is a recursive pseudowellordering.

In a sense, we can almost get natural recursive pseudowellorderings. Given a typical natural theory $S$ and a reasonable ordinal notation system $A$ for its $Π^1_1$ proof ordinal, $S$ is consistent with $A$ being a recursive pseudowellordering. The reason is that well-foundness of $A$ will typically be unprovable even in $S$ augmented with all true $Σ^1_1$ statements, and nonexistence of hyperarithmetical infinite descending paths is $Σ^1_1$. This construction (and its conjectured extension to nonrecursive ordinals) is a key building block for the question Ordinal analysis and nonrecursive ordinals.

Thus, we have a dichotomy. We have reasonable recursive ordinal notation systems for (somewhat) strong theories (which consistent with those theories are pseudowellorderings), but unless this question is answered, no known actual natural recursive pseudowellorderings. I would argue that this asymmetry is fundamental, and is related to that if a large cardinal axiom does not appear to have an easy inconsistency, then it is likely $Π^1_1$ sound (and more): If something natural looks like a well-ordering, then typically it either is a well-ordering or has a simple infinite descending path. However, answers to this question may provide a cautionary tale on this point as well as insights into recursion theory.



Your Answer

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

Browse other questions tagged or ask your own question.