4
$\begingroup$

In the following, $L_\alpha$ is the $\alpha$-th level of the constructible hierarchy, $\alpha$-recursive means definable in $L_\alpha$ by a $\Delta_1$ formula. $|\alpha\text{-recursive}|$ is the supremum of order types of all $\alpha$-recursive well-orders of $\alpha$.

I am looking for constructions of $(\alpha+1)$-recursive well-orders, whose order type is (at least) $|\alpha\text{-recursive}|$. The point is to check whether this lines up with my intuition for recursiveness, which is why I'd prefer simple well-orders.

Full context:

An MO answer by Noah Schweber says in the last part that for every ordinal $\alpha$ that is countable in $L_{\alpha+1}$, there is an ill-founded linear order in $L_{\alpha+1}$ with no infinite decreasing sequences in $L_{\alpha^+}$. By a modification of proposition 2.1 from Richard Gostanian's "The Next Admissible Ordinal" (we just replace $\alpha$-recursivity of $R$ with being in $L_{\alpha^+}$ and bound the order type of $I_R$ only from below), such a linear order must have an initial segment of length $\alpha^+$.

Cutting it off before some element would yield an $\alpha$-arithmetic well-order of any order type smaller than $\alpha^+$, and being in $L_{\alpha+1}$ implies being $\alpha+1$-recursive. So if we choose a non-Gandy $\alpha$, this allows us to create an $(\alpha+1)$-recursive well-order with order type $|\alpha\text{-recursive}|$.

This is strange, it breaks the intuition that $\alpha$-recursive well-orders formalize the idea of applying "computable operations" to $\alpha$, since the set of such operations should be closed under composition. The idea of parameter-free effective cardinals has popped up recently, and some claimed that it better formalizes these computable operations, which started an effort to define what we really mean by "computable operations".

So I've been trying to figure out a "pure" formalization - in terms of literal computation and taking $\alpha$ almost as an input - and the only working definition I got was simply taking the order types of well-orders of $\mathbb{N}$ that are computable by a Turing machine with an oracle for a well-order of $\mathbb{N}$ with order type $\alpha$. However, the supremum of these is just $\alpha^+$, which seemed suspicious (I expected something weaker than $\alpha$-recursive well-orders), so I need to check whether it makes sense by looking at a specific such well-order whose order type is "too high", i.e. a well-order computable by this oracle TM whose order type is at least $|\alpha\text{-recursive}|$.

Unfortunately, the proof of existence that I described at the start yields a relatively complex construction. Too complex for these purposes, because it uses generalizations of Harrison orders and I couldn't intuitively understand those. Does anyone know of something simpler? Although this is probably not possible, it would be ideal if it was a well-ordered set $(X,<)$ where given any $a\in X$, one can easily obtain (and choose) some $A\subseteq X$ unbounded in $\{b\in X : b<a\}$ such that the order type of $A$ is either $\omega$ or $\alpha$.

$\endgroup$
4
  • $\begingroup$ I am suspicious about your construction of a well-order of ordertype $|\alpha\text{-recursive}|$: In short, you construct this well-order by picking the well-founded part of a Harrison order over a non-Gandy $\alpha$. I am not sure how we can ensure the well-founded part is a member of $L_{\alpha+1}$, although the Harrison order itself is in $L_{\alpha+1}$. $\endgroup$
    – Hanul Jeon
    Commented Jul 31, 2023 at 14:12
  • $\begingroup$ To pick the well-founded part of a linear order, we should be able to know which element of the linear order does not admit an infinite decreasing sequence starting from the element, and the problem is that there might be an infinite decreasing sequence that is not captured by $L_{\alpha+1}$ or $L_{\alpha^+}$ as an element or a definable sequence. Then how $L_{\alpha+1}$ can discern the well-founded part of the Harrison order? $\endgroup$
    – Hanul Jeon
    Commented Jul 31, 2023 at 14:15
  • 1
    $\begingroup$ We are not using the entire well-founded part. That has order type $\alpha^+$, so for every $\beta<\alpha^+$, we have a well-founded (non-maximal) initial segment with order type $\beta+1$. That means there is an initial segment $I$ with order type $\beta$ and a minimal element $x$ above $I$, so we can define $I$ as the set of elements smaller than $x$, which should be in $L_{\alpha+1}$. That is assuming we can modify the definition of the linear order to restrict it below $x$, otherwise we'd need to use the order as a parameter and the resulting well-order would be in $L_{\alpha+2}$. $\endgroup$
    – Racheline
    Commented Aug 1, 2023 at 0:28
  • 1
    $\begingroup$ Aha, I got the point: The main point is what will happen when $\alpha$ is not Gandy. $\endgroup$
    – Hanul Jeon
    Commented Aug 1, 2023 at 2:44

0

You must log in to answer this question.

Browse other questions tagged .