Highness for isomorphism at Scott rank $\omega_{1}^{\mathrm{CK}}$

Abstract

We prove that a Turing degree is high for Scott rank $\omega_{1}^{\mathrm{CK}}$ if and only if it is high for isomorphism, answering Question 1 of Franklin, Rossegger, and Turetsky (arXiv, 2026). The result follows from a uniform encoding of arbitrary computable tree path problems by isomorphism problems between computable structures of Scott rank at most $\omega_{1}^{\mathrm{CK}}$ in a fixed finite language. The structures are isomorphic exactly when the tree has an infinite path, and paths and isomorphisms are uniformly computable from one another. The key step is a normal form preserving the path problem in which the extendible nodes are computable at each fixed level, with the decision procedure allowed to depend nonuniformly on the level. We obtain this form by coupling a binary path code with numerical decoding bounds: upward closure and Dickson’s lemma give a finite description of extendibility at each level. Applying the classical Boolean group-tree construction then yields computable infinitary definitions of all finite tuple orbits. The construction and both reductions are uniform, while the highness equivalence uses the usual nonuniform convention.

Note. This paper was generated entirely by AI, including MiMo, using an automated research pipeline developed by Chenghua Liu and Hanyu Li.

1 Introduction

A Turing degree is high for isomorphism if it computes an isomorphism between every pair of isomorphic computable structures. This notion, introduced by Calvert, Franklin, and Turetsky [1], measures the strength needed to identify computable presentations of the same structure. Restricting the structures by Scott rank relates this computational problem to the complexity of defining automorphism orbits.

Write $\kappa=\omega_{1}^{\mathrm{CK}}$ . Franklin, Rossegger, and Turetsky [4] ask whether a degree can be high for Scott rank $\kappa$ without being high for Scott rank $\kappa+1$ , and hence without being high for isomorphism. Their Theorem 19 shows that highness for rank $\kappa$ suffices to compute a descending sequence in every ill-founded computable linear order. We prove the stronger conclusion that it suffices to compute a path through every ill-founded computable tree. By [1, Proposition 2.6], this is equivalent to highness for isomorphism and therefore answers their Question 1 negatively.

Computable structures of rank $\kappa$ already have a substantial construction theory. Makkai [6] produced an arithmetical example, Knight and Millar [5] obtained computable examples, and Calvert, Knight, and Millar [2] realized the rank by computable trees. The group-tree construction presented in [5, §3] encodes paths by automorphisms. Its Scott-rank analysis uses computable bounds on the well-founded node ranks at each fixed level [5, Theorem 3.7]. The issue here is to meet such a local rank condition while preserving the path problem of an arbitrary input tree, rather than constructing a particular example of high Scott rank.

We use the nonuniform highness convention of [4, Definition 2]: $\mathbf{d}$ is high for Scott rank $\alpha$ if every pair of isomorphic computable structures of rank $\alpha$ has a $\mathbf{d}$ -computable isomorphism. The program may depend on the pair. Our convention for Scott rank is likewise that of [4, Definition 1]: $\operatorname{SR}(\mathcal{M})$ is the least $\alpha$ such that every finite tuple orbit is definable, without parameters, by a $\Sigma^{\mathrm{in}}_{\alpha}$ formula. In particular, $\operatorname{SR}(\mathcal{M})\leq\kappa$ if every finite tuple orbit has a computable infinitary definition of some computable complexity. Neither the defining formulas nor their complexities need be uniform in the tuples.

All computable structures have domain $\omega$ , after a computable recoding when necessary. A computable tree is a prefix-closed decidable subset of $\omega^{<\omega}$ , and $[T]$ denotes its set of infinite paths. Uniformity in a tree means uniformity in an index for its characteristic function.

Theorem 1.

Uniformly from a computable tree $T\subseteq\omega^{<\omega}$ , one can construct computable structures $\mathcal{A}_{T},\mathcal{B}_{T}$ in a fixed finite language such that:

1.
Every finite tuple orbit in either structure has a computable infinitary definition. In particular, $\operatorname{SR}(\mathcal{A}_{T}),\operatorname{SR}(\mathcal{B}_{T})\leq\kappa$ .
2.
$\mathcal{A}_{T}\cong\mathcal{B}_{T}$ if and only if $[T]\neq\varnothing$ .
3.
A path in $T$ computes an isomorphism $\mathcal{A}_{T}\to\mathcal{B}_{T}$ , and every such isomorphism computes a path in $T$ . Both conversions are uniform in an index for $T$ .

The new step is the normal form in Lemma 2. We write a path in binary and attach numerical bounds by which each entry must have been decoded. For a fixed binary prefix, increasing these bounds preserves extendibility. Dickson’s lemma then gives a finite basis for the extendible bound vectors. Thus extendibility is computable on each fixed level, although the finite bases need not be obtainable uniformly. This yields the local ordinal bounds required for the Scott analysis.

We combine this recoding with the classical Boolean group-tree construction of Makkai and Morozov, as presented in [5, §3 and Theorem 3.1]. Finite sets of nodes form Boolean groups, and parity over parent fibres defines the projections between levels. Naming different root vectors in two copies forces an isomorphism to encode a nonzero coherent translation, from which a path can be recovered. We give a fixed finite-language presentation and explicit orbit definitions, so that the rank bound and the uniform reductions can be checked directly. Sections 2–4 prove Theorem 1; Section 5 derives the highness equivalence.

2 A levelwise normal form for tree path problems

For a tree $S$ , write $S_{n}$ for its $n$ -th level and put

\operatorname{Ext}(S)_{n}=\{\sigma\in S_{n}:(\exists X\in[S])\,\sigma\preceq X\}.

Here $\preceq$ denotes the initial-segment relation. A node is extendible if it lies on an infinite path, and dead otherwise. Write $S_{\sigma}$ for the subtree of extensions of $\sigma$ , with root $\sigma$ . On a well-founded subtree we use

\operatorname{rk}_{S}(\sigma)=\sup\{\operatorname{rk}_{S}(\tau)+1:\tau\text{ is a child of }\sigma\},

so leaves have rank zero. Extendible nodes are assigned rank $\infty$ , greater than every ordinal. We use the same convention for other rooted trees and forests.

Lemma 2.

Uniformly from a computable tree $T$ , one can construct a computable tree $S\subseteq\omega^{<\omega}$ and uniform computable conversions between paths in $T$ and paths in $S$ such that, for each fixed $n$ , the set $\operatorname{Ext}(S)_{n}$ is computable. The last assertion is not uniform in $n$ .

Proof.

Code $f\in\omega^{\omega}$ by the binary real

X_{f}=0^{f(0)}1\,0^{f(1)}1\,0^{f(2)}1\cdots.

For a finite binary string $\eta$ , let $R_{T}(\eta,i)$ mean that $\eta$ contains at least $i+1$ occurrences of $1$ , and that the numbers of zeros in its first $i+1$ completed blocks form a node of $T$ . This predicate is computable and remains true when $\eta$ is extended.

Consider

Q_{T}=\{(X,b)\in 2^{\omega}\times\omega^{\omega}:(\forall i)\,R_{T}(X\upharpoonright b(i),i)\}.

Every member of $Q_{T}$ computes a path in $T$ : the conditions ensure infinitely many delimiters, and every decoded initial segment belongs to $T$ . Conversely, from $f\in[T]$ compute $X_{f}$ and

b_{f}(i)=\sum_{j\leq i}(f(j)+1).

Then $(X_{f},b_{f})\in Q_{T}$ .

To represent $Q_{T}$ by a computable tree, regard a node of length $n$ as a pair $(\rho,u)\in 2^{n}\times\omega^{n}$ , coding its $j$ -th coordinate by $2u(j)+\rho(j)$ . Put $(\rho,u)$ in $S$ exactly when

(\forall i<n)\bigl[u(i)\leq n\ \Longrightarrow\ R_{T}(\rho\upharpoonright u(i),i)\bigr].

(1)

Membership is decidable. If a prefix has length $m<n$ , every check it requires has $i<m$ and $u(i)\leq m$ ; that same check was required at length $n$ , with the same binary prefix of length $u(i)$ . Thus $S$ is prefix-closed. Its root is the empty sequence, even when $T$ is empty.

Under the coordinate coding, $[S]=Q_{T}$ . Indeed, for a branch $(X,b)\in[S]$ and a fixed $i$ , choose $n\geq\max\{i+1,b(i)\}$ . Equation (1) then checks $R_{T}(X\upharpoonright b(i),i)$ . Conversely, every initial segment of a member of $Q_{T}$ passes all the required checks. This proves the claimed uniform conversions between path sets.

Fix $n$ and $\rho\in 2^{n}$ , and define

U_{\rho}=\{u\in\omega^{n}:(\rho,u)\in\operatorname{Ext}(S)_{n}\}.

The set $U_{\rho}$ is upward closed in the coordinatewise order. If $(X,b)\in Q_{T}$ extends $(\rho,u)$ and $v\geq u$ , replace the first $n$ coordinates of $b$ by $v$ , leaving the rest unchanged. The predicates $R_{T}$ remain true because increasing a decoding bound only extends the binary string being inspected. The resulting member of $Q_{T}$ extends $(\rho,v)$ .

By Dickson’s lemma [3], every upward closed subset of $\omega^{n}$ has finitely many minimal elements. We recall the argument. Every infinite sequence of natural numbers has an infinite nondecreasing subsequence: either some value occurs infinitely often, or the tails are unbounded and one can choose a strictly increasing subsequence. Applying this successively in the finitely many coordinates shows that every infinite sequence in $\omega^{n}$ contains two terms, in their original order, that are coordinatewise comparable. Hence antichains, and in particular sets of minimal elements, are finite. Moreover, every element of an upward closed set lies above a minimal element, since it has only finitely many predecessors in $\omega^{n}$ .

Let $M_{\rho}$ be the finite set of minimal elements of $U_{\rho}$ , allowing the empty set. Then

u\in U_{\rho}\quad\Longleftrightarrow\quad(\exists v\in M_{\rho})(\forall j<n)\,v(j)\leq u(j).

(2)

For this fixed $n$ , there are only $2^{n}$ choices of $\rho$ . Their finite bases can therefore be included as constants in a decision procedure for $\operatorname{Ext}(S)_{n}$ . No procedure for finding these bases as $n$ varies is needed or asserted. ∎

Lemma 3.

For the tree $S$ in Lemma 2 and each $n$ , there is a computable ordinal $\beta_{n}$ such that

\operatorname{rk}_{S}(\sigma)<\beta_{n}\qquad\text{for every }\sigma\in S_{n}\setminus\operatorname{Ext}(S)_{n}.

Proof.

Fix $n$ . By Lemma 2, the dead nodes on level $n$ form a computable set. Form a rooted tree $W_{n}$ whose immediate successors are coded by these nodes, with a copy of $S_{\sigma}$ rooted at the successor coded by $\sigma$ . Membership in $W_{n}$ is computable: first test whether the successor code denotes a dead level- $n$ node, and then use the decision procedure for $S$ . The tree $W_{n}$ is well-founded, since an infinite path would lie in one of the attached dead subtrees. Its Kleene–Brouwer ordering is a computable well-order. Its order type plus one is a computable ordinal strictly greater than the rank of every attached subtree, and may be used as $\beta_{n}$ . The decision procedure for the dead nodes, and hence the resulting bound, is only asserted to exist separately for each $n$ . ∎

3 The Boolean group construction

We now use the group-tree construction from [5, §3] to turn paths into isomorphisms. The construction itself uses only membership in $S$ ; the local information from Lemma 3 will enter the Scott analysis in the next section.

Let $\epsilon$ be the empty sequence, so $S_{0}=\{\epsilon\}$ . For each $n$ , let

G_{n}=\mathcal{P}_{\mathrm{fin}}(S_{n})

be the Boolean group of finite subsets of $S_{n}$ , with symmetric difference as addition. We keep the level in the code of each vector; in particular, the zero vectors $0_{n}=\varnothing$ at different levels are distinct elements. Define

\pi_{n}:G_{n+1}\longrightarrow G_{n},\qquad\pi_{n}(F)=\bigl\{\sigma\in S_{n}:|\{\tau\in F:\tau\upharpoonright n=\sigma\}|\text{ is odd}\bigr\}.

(3)

Parity shows that $\pi_{n}$ is a homomorphism. Put $V=\coprod_{n}G_{n}$ , and define $p:V\to V$ by $p\upharpoonright G_{n+1}=\pi_{n}$ and $p\upharpoonright G_{0}=\mathrm{id}$ .

To obtain a fixed finite language, we name translation relations by indices rather than using a separate symbol for each translation. Adjoin an index sort $I$ , a copy of $(\omega,0,s)$ . For $k\in\omega$ , write $\overline{k}=s^{k}(0)$ for its numeral in this sort. Let $\ell:V\to I$ be the level map, so $\ell(F)=\overline{n}$ for $F\in G_{n}$ . Fix, independently of $S$ , a computable bijection

e:\omega\times\mathcal{P}_{\mathrm{fin}}(\omega^{<\omega})\longrightarrow\omega

with computable inverse. Define the ternary relation $D$ by

D(\overline{e(n,H)},F,F^{\prime})\quad\Longleftrightarrow\quad H\subseteq S_{n},\quad F,F^{\prime}\in G_{n},\quad F^{\prime}=F\mathbin{\triangle}H.

(4)

It is false on all other triples. In particular, an index that decodes to $(n,H)$ with $H\not\subseteq S_{n}$ names the empty relation.

The language consists of the unary predicate $I$ , constants $0,c$ , unary functions $s,p,\ell$ , and the ternary relation $D$ . We use a one-sorted presentation on $I\sqcup V$ : extend $s$ by the identity on $V$ , and extend $p,\ell$ by the identity on $I$ . Hereafter $V(x)$ abbreviates $\neg I(x)$ . The index sort is rigid, since every one of its elements is the value of a numeral.

These interpretations are computable uniformly from $S$ . A finite set belongs to $G_{n}$ exactly when all of its members belong to $S_{n}$ , which is a finite computable test. Thus the tagged domain has a computable coding as an infinite decidable subset of $\omega$ ; its increasing enumeration gives a computable bijection with $\omega$ , uniformly from $S$ . This also makes the codes of the vectors $0_{n}$ uniformly computable. No extendibility information is used in this presentation.

Let $\mathcal{A}$ and $\mathcal{B}$ have the same reduct just described, with

c^{\mathcal{A}}=0_{0},\qquad c^{\mathcal{B}}=1_{0}:=\{\epsilon\}.

Thus the two elements of $G_{0}$ are $0_{0}$ and $1_{0}$ .

Lemma 4.

An isomorphism $\mathcal{A}\to\mathcal{B}$ is exactly a map fixing $I$ pointwise and acting on each $G_{n}$ as

F\longmapsto F\mathbin{\triangle}h_{n},\qquad h_{n}\in G_{n},\qquad\pi_{n}(h_{n+1})=h_{n},\qquad h_{0}=1_{0}.

(5)

Automorphisms of either structure have the same description with $h_{0}=0_{0}$ .

Proof.

An isomorphism $f$ fixes $I$ pointwise because it fixes $0$ and preserves $s$ . Preservation of $\ell$ then forces it to preserve each level. Set $h_{n}=f(0_{n})$ . Applying $f$ to $D(\overline{e(n,F)},0_{n},F)$ gives $f(F)=h_{n}\mathbin{\triangle}F$ . Since $p(0_{n+1})=0_{n}$ , preservation of $p$ yields $\pi_{n}(h_{n+1})=h_{n}$ . For an isomorphism $\mathcal{A}\to\mathcal{B}$ , preservation of $c$ gives $h_{0}=1_{0}$ . For an automorphism of either structure, the translation on $G_{0}$ fixes its named element and hence is zero.

Conversely, a coherent sequence $(h_{n})$ defines a bijection on each level. The homomorphism identity gives

\pi_{n}(F\mathbin{\triangle}h_{n+1})=\pi_{n}(F)\mathbin{\triangle}h_{n},

so the resulting map preserves $p$ . Translating both vector arguments in (4) leaves their difference unchanged, so it preserves $D$ . It preserves $I,s,\ell,0$ by its definition, and the condition at level zero ensures preservation of $c$ . ∎

Lemma 5.

Paths in $S$ and isomorphisms $\mathcal{A}\to\mathcal{B}$ compute one another uniformly.

Proof.

Given a path $X\in[S]$ , put $h_{n}=\{X\upharpoonright n\}$ . These vectors satisfy (5), and the corresponding isomorphism is computable from $X$ .

Conversely, an isomorphism $f$ computes the finite sets $h_{n}=f(0_{n})$ . Start with $\sigma_{0}=\epsilon\in h_{0}$ . If $\sigma_{n}\in h_{n}$ , the coherence equation says that an odd, and therefore nonzero, number of members of $h_{n+1}$ have parent $\sigma_{n}$ . Choose the one with least code and call it $\sigma_{n+1}$ . Then $\sigma_{n}\preceq\sigma_{n+1}$ and $\sigma_{n}\in S_{n}$ for all $n$ , so their union is a path through $S$ . The procedure uses only evaluations of $f$ and finite searches. ∎

4 The Scott rank bound

An orbit condition must determine whether a finite translation can be extended coherently through all higher levels. The point of the normal form is that, at each fixed level, failure of such an extension is witnessed by a tree rank below one computable ordinal.

On the vector sort define the proper child relation

C(x,y)\quad\Longleftrightarrow\quad V(x)\wedge V(y)\wedge p(y)=x\wedge y\neq x.

This makes $V$ a forest with roots $0_{0},1_{0}$ . The subtree rooted at $F\in G_{n}$ is its lift tree: a child of a vector is a vector on the next level projecting to it. Each lift node has a unique ancestor chain back to $F$ .

Lemma 6.

A vector $F\in G_{n}$ has an infinite branch in its lift tree if and only if $F\subseteq\operatorname{Ext}(S)_{n}$ . If $\sigma\in F\setminus\operatorname{Ext}(S)_{n}$ , the lift tree of $F$ is well-founded and has rank at most $\operatorname{rk}_{S}(\sigma)$ .

Proof.

Suppose every member of $F$ is extendible. Choose a path extending each member, and at each higher level take the finite set of nodes on these paths. Paths extending distinct level- $n$ nodes remain distinct, so the resulting vectors project to one another and give an infinite lift branch. For $F=\varnothing$ , use the all-zero branch.

Now fix a dead node $\sigma\in F$ . We define a map from the lift tree of $F$ into $S_{\sigma}$ that takes children to children. Send its root to $\sigma$ . If a lift node $E$ has been sent to $\tau\in E$ and $E^{\prime}$ is a child of $E$ , the parity equation (3) ensures that $E^{\prime}$ contains a child of $\tau$ . Send $E^{\prime}$ to the child with least code. Uniqueness of ancestor chains makes this prescription consistent. An infinite lift branch would map to an infinite branch through $S_{\sigma}$ , which is impossible. Finally, well-founded induction gives the rank inequality: if $q$ is this map and the inequality holds at the children of a lift node $E$ , then

\operatorname{rk}(E)=\sup_{E^{\prime}\text{ child of }E}\bigl(\operatorname{rk}(E^{\prime})+1\bigr)\leq\sup_{E^{\prime}\text{ child of }E}\bigl(\operatorname{rk}_{S}(q(E^{\prime}))+1\bigr)\leq\operatorname{rk}_{S}(q(E)).

Apply this at the root. ∎

For each computable ordinal $\alpha$ , rank at least $\alpha$ in this forest has a computable infinitary definition. Fixing computable ordinal notations, define

$\displaystyle H_{0}(x)$	$\displaystyle\equiv V(x),$	(6)
$\displaystyle H_{\alpha+1}(x)$	$\displaystyle\equiv\exists y\,\bigl(C(x,y)\wedge H_{\alpha}(y)\bigr),$
$\displaystyle H_{\lambda}(x)$	$\displaystyle\equiv V(x)\wedge\bigwedge_{j}H_{\lambda_{j}}(x)\qquad(\lambda\text{ a nonzero limit}),$

where $(\lambda_{j})_{j}$ is the computable cofinal sequence supplied by the chosen notation for $\lambda$ . The recursion along the notation makes the limit conjunctions effective and yields a computable infinitary formula of computable complexity. Induction on $\alpha$ shows that $H_{\alpha}$ holds exactly at nodes of rank at least $\alpha$ , with infinite rank included. At a successor step, rank at least $\alpha+1$ is equivalent to having a child of rank at least $\alpha$ ; at a limit, it is equivalent to having rank at least every $\lambda_{j}$ .

Choose $\beta_{n}$ as in Lemma 3 and set $\theta_{n}(x)=H_{\beta_{n}}(x)$ . By Lemma 6, for $F\in G_{n}$ we have

\theta_{n}(F)\quad\Longleftrightarrow\quad F\subseteq\operatorname{Ext}(S)_{n}.

(7)

Vectors with extendible support have infinite lifts. Any other vector contains a dead node $\sigma\in S_{n}$ , so its lift rank is at most $\operatorname{rk}_{S}(\sigma)<\beta_{n}$ . A notation for $\beta_{n}$ is chosen only for this particular level; a computable sequence of such notations is not required.

Consider a nonempty tuple of vector-sort elements $a_{i}=(n_{i},F_{i})$ , and let $N=\max_{i}n_{i}$ . In $\mathcal{A}$ , define

	$\displaystyle\varphi_{\bar{a}}(\bar{x})\equiv\exists z\,\bigl[$	$\displaystyle V(z)\wedge\ell(z)=\overline{N}\wedge\theta_{N}(z)\wedge p^{N}(z)=c$		(8)
		$\displaystyle}{\displaystyle\wedge\bigwedge_{i}D\bigl(\overline{e(n_{i},F_{i})},p^{N-n_{i}}(z),x_{i}\bigr)\bigr].$		(8)

Here $p^{k}$ is the $k$ -fold iterate of $p$ , with $p^{0}$ the identity. All numerals in the formula are finite terms in $0,s$ ; the entries of $\bar{a}$ are not used as parameters.

We verify that (8) defines the orbit of $\bar{a}$ . If an automorphism sends $\bar{a}$ to $\bar{b}$ , let $(h_{n})$ be its coherent translation sequence. Taking $z=h_{N}$ works: the higher coordinates form an infinite lift branch, so $\theta_{N}(h_{N})$ holds, and $p^{N}(h_{N})=h_{0}=0_{0}=c^{\mathcal{A}}$ . The translation relations express precisely that $b_{i}=F_{i}\mathbin{\triangle}h_{n_{i}}$ .

Conversely, suppose $\bar{b}$ satisfies (8), witnessed by $z$ . Equation (7) and Lemma 6 extend $z$ upward to a coherent sequence. Below level $N$ , use its iterated projections. The condition $p^{N}(z)=c^{\mathcal{A}}=0_{0}$ ensures that the resulting translation is an automorphism, by Lemma 4. The last conjunction in (8) makes it send each $a_{i}$ to $b_{i}$ .

Index-sort elements have singleton orbits defined by their numerals. For a mixed tuple, conjoin these singleton definitions with (8) for the vector-sort coordinates. A tuple entirely in $I$ needs only the singleton definitions, and the empty tuple has the tautological orbit definition. Each resulting formula is computable infinitary of computable complexity. Therefore $\operatorname{SR}(\mathcal{A})\leq\kappa$ .

The automorphisms of $\mathcal{B}$ are the same zero-root translations. In $\mathcal{B}$ , the condition

D\bigl(\overline{e(0,\{\epsilon\})},c,w\bigr)

defines $w=0_{0}$ , since $c^{\mathcal{B}}=1_{0}$ . Replacing $p^{N}(z)=c$ in (8) by

D\bigl(\overline{e(0,\{\epsilon\})},c,p^{N}(z)\bigr)

therefore gives the same orbit verification in $\mathcal{B}$ , without changing the conclusion about computable infinitary definability. Thus $\operatorname{SR}(\mathcal{B})\leq\kappa$ as well. Together with Lemmas 2 and 5, this completes the proof of Theorem 1.

5 Highness at the boundary ranks

Corollary 7.

A Turing degree is high for Scott rank $\omega_{1}^{\mathrm{CK}}$ if and only if it is high for isomorphism. These conditions are also equivalent to highness for Scott rank $\omega_{1}^{\mathrm{CK}}+1$ . In particular, the degree requested in Question 1 of [4] does not exist.

Proof.

Let $\mathbf{d}$ be high for Scott rank $\kappa$ . We first use the padding observation following Definition 2 of [4]. Given isomorphic computable structures of rank at most $\kappa$ , take their tagged disjoint unions with a fixed computable structure of exact rank $\kappa$ , whose existence follows from [5]. The tagged sums have exact rank $\kappa$ , and an isomorphism between them restricts to an isomorphism between the original structures. Hence $\mathbf{d}$ computes isomorphisms for pairs of rank at most $\kappa$ as well.

For any ill-founded computable tree $T$ , Theorem 1 supplies isomorphic computable structures $\mathcal{A}_{T},\mathcal{B}_{T}$ of rank at most $\kappa$ . A $\mathbf{d}$ -computable isomorphism between them computes a path in $T$ . Thus $\mathbf{d}$ computes a path through every ill-founded computable tree.

For completeness, the passage from this path property to highness for isomorphism is the following implication from [1, Proposition 2.6]. Let $\mathcal{C},\mathcal{D}$ be isomorphic computable structures in a common computable language, and enumerate the atomic formulas of that language. Form a tree of finite sequences of nested finite injections from $\mathcal{C}$ to $\mathcal{D}$ . At stage $j$ , require that the injection cover the first $j$ elements in both domain and range. Require also that the first $j$ atomic formulas agree in truth value on every assignment from its domain and the corresponding image assignment. These are finite computable tests, so the tree is computable and prefix-closed. An isomorphism supplies a path by taking suitable finite restrictions. Conversely, the union along any path is a total bijection, and every atomic formula on every tuple is eventually checked. The union is therefore an isomorphism. Applying the path property gives a $\mathbf{d}$ -computable isomorphism $\mathcal{C}\to\mathcal{D}$ . The reverse implication, from highness for isomorphism to highness for rank $\kappa$ , follows directly from the definitions.

Finally, every computable structure has Scott rank at most $\kappa+1$ . Together with the same tagged-sum observation at $\kappa+1$ , this identifies highness for that rank with highness for isomorphism, as noted in [4, §4]. ∎

The finite bases and ordinal bounds are used only to prove the rank bound. They are not inputs to the construction of the structures or to the extraction of a path. Consequently, for each input tree, the isomorphism program supplied by nonuniform highness can be composed with the uniform extraction without any additional oracle information.

Remark (Exact rank).

If $T$ has a path but no hyperarithmetical path, both structures in Theorem 1 have rank exactly $\kappa$ . They are isomorphic, and if their common rank were computable, the computable-rank upper bound of [4, Lemma 2], together with the padding observation, would give a hyperarithmetical isomorphism. The extracted path in $T$ would then be hyperarithmetical, a contradiction.

In this case the well-founded node ranks of $S$ have no common computable bound. Indeed, if a computable ordinal $\gamma$ bounded all of them, the rank-at-least- $\gamma+1$ test, constructed as in (6) for the child relation of $S$ , would decide extendibility uniformly in the node using a hyperarithmetical oracle. Starting at the root and repeatedly choosing the least extendible child would yield a hyperarithmetical path in $S$ , and hence in $T$ . In particular, the levelwise bounds $\beta_{n}$ cannot be bounded by a computable ordinal.

References

[1] Wesley Calvert, Johanna N. Y. Franklin, and Dan Turetsky, Structural highness notions, Journal of Symbolic Logic 88(4) (2023), 1692–1724. doi:10.1017/jsl.2022.35.
[2] Wesley Calvert, Julia F. Knight, and Jessica Millar, Computable trees of Scott rank $\omega_{1}^{\mathrm{CK}}$ , and computable approximation, Journal of Symbolic Logic 71(1) (2006), 283–298. doi:10.2178/jsl/1140641175.
[3] Leonard E. Dickson, Finiteness of the odd perfect and primitive abundant numbers with $n$ distinct prime factors, American Journal of Mathematics 35(4) (1913), 413–422. doi:10.2307/2370405.
[4] Johanna N. Y. Franklin, Dino Rossegger, and Dan Turetsky, Structural vs. computational complexity, arXiv preprint, 2026. arXiv:2606.15196v1.
[5] Julia F. Knight and Jessica Millar, Computable structures of rank $\omega_{1}^{\mathrm{CK}}$ , Journal of Mathematical Logic 10(1–2) (2010), 31–43. doi:10.1142/S0219061310000912. Author version: arXiv:math/0508507.
[6] Michael Makkai, An example concerning Scott heights, Journal of Symbolic Logic 46(2) (1981), 301–318. doi:10.2307/2273623.

Highness for isomorphism at Scott rank ω1CK

Abstract

1 Introduction

Theorem 1.

2 A levelwise normal form for tree path problems

Lemma 2.

Proof.

Lemma 3.

Proof.

3 The Boolean group construction

Lemma 4.

Proof.

Lemma 5.

Proof.

4 The Scott rank bound

Lemma 6.

Proof.

5 Highness at the boundary ranks

Corollary 7.

Proof.

Remark (Exact rank).

References

Highness for isomorphism at Scott rank $\omega_{1}^{\mathrm{CK}}$