6
$\begingroup$

For a computable$^*$ ordinal $\alpha$ (viewed as an $\{<\}$-structure), say that a first-order sentence $\sigma$ in a relational language $\Sigma\supseteq \{<\}$ decidably clarifies $\alpha$ iff $\alpha$ has a decidable expansion satisfying $\sigma$ and whenever $\mathcal{X}=(X;...),\mathcal{Y}=(Y;...)$ are decidable models of $\sigma$ with $\{<\}$-reducts isomorphic to $\alpha$ then the isomorphism between those $\{<\}$-reducts is computable.

For example, the sentence saying that $F$ "behaves like" (the graph of) ordinal exponentiation successfully clarifies all ordinals up to $\epsilon_0$ (and possibly a ways past that). My question is:

Is there a $\sigma$ which decidably clarifies every (infinite) computable ordinal?

If we drop the decidability requirement the answer is yes, but by a very unnatural trick. Fix some computable linear order $\mathcal{L}\cong\omega_1^{CK}\cdot (1+\eta)$ (a Harrison order) with index $e\in\mathbb{N}$. Consider the $\{<,U,S,R_+,R_\times, I\}$-sentence $\sigma$ which says the following:

  • $U$ picks out the initial segment of the domain of length $\omega$ (= elements not above any nonzero limit element).

  • On the segment picked out by $U$, the symbols $R_+ ,R_\times$ define (the graphs of) addition/multiplication functions the expansion by which turns $U$ into a model of Robinson arithmetic whose ordering agrees with the restriction of $<$ (and so is necessarily isomorphic to $\mathbb{N}$). I'll call this model "$\mathcal{N}$."

  • $I$ is the graph of an order-preserving bijection between the $\{<\}$-reduct of the universe and some initial segment of $(\Phi_e)^\mathcal{N}$.

Note that if $\alpha$ is a computable ordinal and $\mathcal{X}_0$ is a copy of $\alpha$, then there is exactly one expansion of $\mathcal{X}_0$ to a model of $\sigma$; in particular, the isomorphism defined by $I$ is unique since $\alpha$ is actually a well-ordering. Basically, if $\mathcal{X}$ is an expansion of $\alpha$ satisfying $\sigma$, then $\mathcal{X}$ "describes" an explicit isomorphism between $\mathcal{X}\upharpoonright\{<\}$ and a specific initial segment of $\mathcal{L}$, and given two such expansions $\mathcal{X},\mathcal{Y}$ we first (computably) identify the two "$\mathcal{N}$-parts" and then compose the appropriate isomorphisms.

I suspect that there is a general trick similar to either this answer of Ville Salo or Hanf's Model-theoretic methods in the study of elementary logic (pointed out to me by Fedor Pakhomov in a comment on a now-deleted question of mine) for "decidabilizing" this, but I don't see the details. In particular, I unfortunately don't have access to Hanf's paper.


$^*$It turns out that in general we can have copies $\mathcal{X},\mathcal{Y}$ of the same countable ordinal such that no isomorphism between them is computable in $\mathcal{O}^\mathcal{X}\oplus\mathcal{O}^\mathcal{Y}$, so there is no hope of doing this for arbitrary countable ordinals. However, the first "non-$\mathcal{O}$-clarifiable" ordinal is extremely large - at least as big as this fellow - and so I don't think the details of that argument will be useful to this question.

$\endgroup$
9
  • $\begingroup$ What is a decidable model? $\endgroup$
    – Farmer S
    Commented Oct 20 at 1:42
  • $\begingroup$ @FarmerS A model (with domain $\mathbb{N}$) whose whole elementary diagram is computable. For example, $(\mathbb{N};+,\times)$ is a computable structure (= atomic diagram is computable) which is not decidable. $\endgroup$ Commented Oct 20 at 1:55
  • $\begingroup$ So would the isomorphism between the two copies of $\alpha$ itself not just be computable? (Given it is computable relative to the join of $\mathcal{X}$ and $\mathcal{Y}$, which itself is computable.) $\endgroup$
    – Farmer S
    Commented Oct 20 at 2:01
  • $\begingroup$ Agreed, but why would it not be computable, given it is computable from the join of $\mathcal{X}$ and $\mathcal{Y}$, which themselves are computable? $\endgroup$
    – Farmer S
    Commented Oct 20 at 2:03
  • $\begingroup$ @FarmerS Oops, good catch, fixing! $\endgroup$ Commented Oct 20 at 2:08

0

You must log in to answer this question.

Browse other questions tagged .