# Structural Highness Notions

Wesley Calvert  School of Mathematical and Statistical Sciences
Mail Code 4408
1245 Lincoln Drive
Southern Illinois University
Carbondale, Illinois 62901
USA<EMAIL_ADDRESS>http://lagrange.math.siu.edu/calvert ,  Johanna N.Y.
Franklin  Department of Mathematics
Room 306, Roosevelt Hall
Hofstra University
Hempstead, NY 11549-0114
USA<EMAIL_ADDRESS>http://www.johannafranklin.net and  Dan
Turetsky  School of Mathematics and Statistics
Victoria University of Wellington
Wellington
New Zealand<EMAIL_ADDRESS>
###### Abstract.

We introduce several highness notions on degrees related to the problem of
computing isomorphisms between structures, provided that isomorphisms exist.
We consider variants along axes of uniformity, inclusion of negative
information, and several other problems related to computing isomorphisms.
These other problems include Scott analysis (in the form of back-and-forth
relations), jump hierarchies, and computing descending sequences in linear
orders.

The second author was supported in part by Simons Foundation Collaboration
Grant #420806. Portions of this material are based upon work supported by the
National Science Foundation under Grant No. DMS-1928930 while the first author
participated in a program hosted by the Mathematical Sciences Research
Institute in Berkeley, California, during the Fall 2020 semester.

###### Contents

  1. 1 Introduction
  2. 2 Highness and uniform highness for isomorphism
    1. 2.1 Relationship between highness for isomorphism and benchmark Turing degrees
    2. 2.2 High for a restricted class of isomorphisms
  3. 3 Scott analysis
  4. 4 Computing descending sequences
    1. 4.1 Degrees that are high for descending sequences
    2. 4.2 Computing jump hierarchies
    3. 4.3 $\Pi^{1}_{1}$-tracing of majorized classes
    4. 4.4 A class without $\Pi^{1}_{1}$ traces
  5. 5 Reticence
  6. 6 Randomness and genericity
  7. 7 Summary of results and future directions

##  1\. Introduction

The concepts of lowness and highness allow us to describe the power of an
oracle. While they were originally established in the context of degree theory
by Soare in the early 1970s [25], they have been generalized to other areas of
computability theory. In this paper, we investigate the application of
highness to computable structure theory.

A set is low in a given setting if using it as an oracle in that context
yields results no different from those obtained by using a computable set as
an oracle. For instance, a set $A$ is low in degree theory if
$A^{\prime}\equiv_{T}0^{\prime}$, and it is low for a particular randomness
notion if it cannot derandomize any random set [10]. Lowness has even been
studied in the context of learning theory [24].

Highness, on the other hand, has been studied in fewer settings. To define a
lowness notion, we only need a relativizable class such as the
$\Delta^{0}_{2}$ sets or the Martin-Löf random reals. To define a highness
notion, we need some kind of maximality as well. In the case of the
$\Delta^{0}_{2}$ sets, this role is played by $0^{\prime}$; in the case of the
Martin-Löf random reals, we must turn to the idea of highness for pairs of
randomness notions and compare one class to another class containing it [14]
since there is no natural “maximally random” real.

In this paper, we discuss computable structure theory. Lowness was first
studied in this setting by Franklin and Solomon in [12] as _lowness for
isomorphism_ : a degree $\mathbf{d}$ is low for isomorphism if, for any two
computable structures $\mathcal{A}$ and $\mathcal{B}$, the degree $\mathbf{d}$
only computes an isomorphism between $\mathcal{A}$ and $\mathcal{B}$ if there
is already a computable isomorphism between them.111Csima has also introduced
the notion of _lowness for categoricity_ [6], though it has not been
investigated in much depth as of yet.

The class of degrees that are low for isomorphism defies easy
characterization. No degree comparable to $\mathbf{0}^{\prime}$ is low for
isomorphism except $\mathbf{0}$. On the other hand, every 2-generic degree is
[12]. Further work was done on this class by Franklin and Turetsky [15] and
then, once again, Franklin and Solomon [13], but these papers only suggest
that the class is more complicated than had been initially thought.
Nevertheless, it seems to be somewhat robust: Franklin and Turetsky have
characterized these degrees as those that are low for paths [9], and Franklin
and McNicholl have characterized them as those that are low for isometric
isomorphism [11].

Turning to highness in the context of computable structure theory, we say that
a degree is high for isomorphism if it can compute an isomorphism between any
two isomorphic computable structures.

######  Definition 1.1.

We call a degree $\mathbf{d}$ high for isomorphism if for any two computable
structures $\mathcal{M}$ and $\mathcal{N}$ with $\mathcal{M}\cong\mathcal{N}$,
there is a $\mathbf{d}$-computable isomorphism from $\mathcal{M}$ to
$\mathcal{N}$.

Note that the degree of Kleene’s $\mathcal{O}$ is high for isomorphism.
Indeed, $\mathcal{O}$ can compute a path through the tree of partial
isomorphisms of any two computable structures for which such a path exists.
Thus, in analogy with the $\Delta^{0}_{2}$ degrees, $\mathcal{O}$ is the
maximal object for isomorphism.

For a set $X$, we will take

$\mathcal{O}^{X}=\\{e:\text{$\\{e\\}^{X}$ is the graph of a binary relation
that well-orders $\omega$}\\}$

and $\mathcal{O}=\mathcal{O}^{\emptyset}$. By standard results described, for
instance, in [23], this is equivalent to the usual definition involving
notations for ordinals.

We also define a uniform version of highness for isomorphism in keeping with
uniform versions of other concepts in computable structure theory [7].

######  Definition 1.2.

We call a degree $\mathbf{d}$ uniformly high for isomorphism if there is a
$D\in\mathbf{d}$ and a total computable $f$ such that for any computable
structures $\mathcal{M}_{i}\cong\mathcal{M}_{j}$, the function
$\\{f(i,j)\\}^{D}$ is an isomorphism from $\mathcal{M}_{i}$ to
$\mathcal{M}_{j}$.

The primary focus of this paper is highness for isomorphism, but we also
consider several other structural highness notions. We begin in Section 2 with
a discussion of the types of degrees that are high for isomorphism. In Section
3, we turn to Scott analysis in an attempt to characterize these degrees
further, and in Section 4, we consider degrees that are high for descending
sequences, that is, those that can compute a descending sequence in any
computable ill-founded linear order. In Section 4.2, we relate these notions
to degrees that can compute jump structures on arbitrary Harrison orders. We
then consider a structural equivalent of enumerability, “reticence,” and the
reticent versions of all of the previously considered notions in Section 5. In
Section 6, we make some brief remarks on the relationships between highness
for isomorphism and randomness and genericity, and we conclude the paper with
some open questions in Section 7.

##  2\. Highness and uniform highness for isomorphism

We begin by noting the following connection between the degrees that are high
for isomorphism and those that are uniformly high for isomorphism.

######  Proposition 2.1.

If $\mathbf{d}$ is high for isomorphism, then $\mathbf{d}^{\prime\prime}$ is
uniformly high for isomorphism.

###### Proof.

Observe that $\\{e\\}^{D}$ being an isomorphism between $\mathcal{M}_{i}$ and
$\mathcal{M}_{j}$ is a $\Pi^{0}_{2}(D)$ property of $e,i$ and $j$: being total
and surjective are $\Pi^{0}_{2}$, and being injective and being a partial
isomorphism are $\Pi^{0}_{1}$. Thus, given $i$ and $j$, $D^{\prime\prime}$ can
iterate through the $e$s until it finds one giving an isomorphism and then
output $\\{e\\}^{D}$. ∎

Now we turn our attention to establishing a characterization of the degrees
that are (uniformly) high for isomorphism and proceed to some existence
results.

We observe that if $\mathbf{d}$ is not high for isomorphism, then there is a
$\Sigma^{1}_{1}$ class of which it computes no element: the class of
isomorphisms between some pair of isomorphic computable structures.222By a
$\Sigma^{1}_{1}$ class, we mean a $\Sigma^{1}_{1}$ subset of
$\omega^{\omega}$. This leads to the following definition inspired by the
characterization of a $\Pi^{0}_{1}$ class as the set of paths through some
computable tree.

######  Definition 2.2.

We call a degree $\mathbf{d}$ high for paths if for every nonempty
$\Pi^{0}_{1}$ class of functions $\mathcal{P}$, the degree $\mathbf{d}$
computes an element of $\mathcal{P}$. Similarly, a degree $\mathbf{d}$ is
called uniformly high for paths if there is a $D\in\mathbf{d}$ and a total
computable $f$ such that for every nonempty $\Pi^{0}_{1}$ class of functions
$\mathcal{P}_{i}$, the function $\\{f(i)\\}^{D}$ is an element of
$\mathcal{P}_{i}$.

As $\Sigma^{1}_{1}$ classes are uniformly projections of $\Pi^{0}_{1}$ classes
in the sense that any $\Sigma^{1}_{1}$ class can be viewed as the projection
on the first coordinate of the set of paths through a $\Pi^{0}_{1}$ subtree of
$\left(\omega^{\omega}\right)^{2}$, we could replace $\Pi^{0}_{1}$ with
$\Sigma^{1}_{1}$ in this definition without changing the class of degrees
described. This gives us the following:

######  Observation 2.3.

If $\mathbf{d}$ is (uniformly) high for paths, then it (uniformly) computes an
element of every nonempty $\Sigma^{1}_{1}$ class, and conversely.

This allows us to make use, from time to time, of the following result
(described, for instance, in [23]).

######  Theorem 2.4 (Gandy Basis Theorem).

Every nonempty $\Sigma^{1}_{1}$ class has a member $f$ such that
$\omega_{1}^{f}=\omega_{1}^{ck}$.

We now present a characterization of the degrees that are high for isomorphism
in terms of highness for paths; we will need the following notation for the
proof.

######  Notation 2.5.

If $S,T\subseteq\omega^{<\omega}$ are trees, we define $S\star
T=\\{(\sigma_{0},\sigma_{1}):\sigma_{0}\in S\ \&\ \sigma_{1}\in T\ \&\
|\sigma_{0}|=|\sigma_{1}|\\}$ and give this a tree structure by
$(\sigma_{0},\sigma_{1})\subseteq(\tau_{0},\tau_{1})$ if
$\sigma_{i}\subseteq\tau_{i}$ for $i<2$.

Note that we can identify $S\star T$ with a tree in $\omega^{<\omega}$ in an
effective fashion.

######  Proposition 2.6.

A degree is (uniformly) high for isomorphism if and only if it is (uniformly)
high for paths.

###### Proof.

Suppose that $\mathbf{d}$ is (uniformly) high for paths. Given two isomorphic
computable structures, we construct the tree $\mathcal{I}$ of partial
isomorphisms, noting that this tree is uniformly computable in the two
structures. Now $\mathbf{d}$ computes a path through $\mathcal{I}$, which is
an isomorphism.

The other direction follows from the proof of Theorem 2.18, but we give a
proof here as well. The reader familiar with the interplay between trees and
linear orders may recognize that these are substantially the same proof, but
as trees are more general objects than linear orders, this version is somewhat
simpler. Let $\mathbf{d}$ be (uniformly) high for isomorphism, and let
$\mathcal{T}$ be a nonempty $\Pi^{0}_{1}$ class of functions generated by a
computable tree $T$.

Our proof is based on rank-saturated trees of infinite rank [4, 8]; we will
require the following facts:

  1. (1)

There is a computable rank-saturated tree $S$ of infinite rank that has a
computable path. (This follows from the proof of Lemma 1 in [8], beginning
with a Harrison order with a computable descending sequence; such an order is
constructed in the proof of Theorem 2.18.)

  2. (2)

Any two computable rank-saturated trees of infinite rank are isomorphic.
(Proposition 2, [8])

  3. (3)

If $S$ is a computable rank-saturated tree of infinite rank and $T$ is any
computable tree with a path, then $T\star S$ is a computable rank-saturated
tree of infinite rank. (Proposition 1, [8])

Then $S$ and $T\star S$ are our two computable structures in some appropriate
language. Let $f$ be a computable path through $S$. Since $\mathbf{d}$ can
compute an isomorphism between $S$ and $T\star S$, we have that $\mathbf{d}$
can carry $f$ over to a path in $T\star S$ and then project that down to a
path in $T$ as required. Furthermore, this process is uniform in the
isomorphism. ∎

###  2.1. Relationship between highness for isomorphism and benchmark Turing
degrees

We first note that the degrees that are high for isomorphism are necessarily
strong:

######  Proposition 2.7.

If $\mathbf{d}$ is high for isomorphism, then $\mathbf{d}$ computes every
$\Delta^{1}_{1}$ set.

###### Proof.

If $X$ is $\Delta^{1}_{1}$, then $\\{X\\}$ is a $\Sigma^{1}_{1}$ class, and
thus $\mathbf{d}$ computes $X$. ∎

Another perspective reinforces this insight.

######  Proposition 2.8.

Kleene’s $\mathcal{O}$ is arithmetical over any degree high (or uniformly
high) for isomorphism. Furthermore, we have the following:

  1. (1)

If $\mathbf{d}$ is high for isomorphism, then $\mathcal{O}$ is
$\Pi^{0}_{3}(\mathbf{d})$ and thus $\mathbf{d}^{(3)}\geq\mathcal{O}$.

  2. (2)

If $\mathbf{d}$ is uniformly high for isomorphism, then $\mathcal{O}$ is
$\Sigma^{0}_{2}(\mathbf{d})$ and thus $\mathbf{d}^{(2)}\geq\mathcal{O}$.

###### Proof.

Note that $X=\\{(i,j):\mathcal{M}_{i}\cong\mathcal{M}_{j}\\}$ is a
$\Sigma^{1}_{1}$-complete set (folklore, see [19]). However, if $\mathbf{d}$
is high for isomorphism with $D\in\mathbf{d}$, then $(i,j)\in X$ if and only
if $\exists e\,[\\{e\\}^{D}:\mathcal{M}_{i}\cong\mathcal{M}_{j}]$, and the
matrix of the right-hand side is $\Pi^{0}_{2}(D)$. Then $\Sigma^{1}_{1}$ sets
are $\Sigma^{0}_{3}(\mathbf{d})$, making
$\mathcal{O}\in\Pi^{0}_{3}(\mathbf{d})$.

If, instead, $\mathbf{d}$ is uniformly high for isomorphism as witnessed by
$D$ and $f$, then we can strip off the opening existential quantifier from the
previous argument: $(i,j)\in X$ if and only if
$\\{f(i,j)\\}^{D}:\mathcal{M}_{i}\cong\mathcal{M}_{j}$. In this case,
$\Sigma^{1}_{1}$ sets are $\Pi^{0}_{2}(\mathbf{d})$, making
$\mathcal{O}\in\Sigma^{0}_{2}(\mathbf{d})$. ∎

We now progress toward showing the existence of degrees strictly below
$\mathcal{O}$ which are high for isomorphism. To this end, we use the
following known strengthening of the Gandy Basis Theorem:

######  Lemma 2.9 (Folklore, see Exercise 2.5.6 in [5]).

If $\mathcal{Q}\subseteq\omega^{\omega}$ is a nonempty $\Sigma^{1}_{1}$ class,
there is an $X\in\mathcal{Q}$ with $\mathcal{O}^{X}\leq_{T}\mathcal{O}$.
Furthermore, an index for a witnessing Turing reduction can be uniformly
obtained from an index for $\mathcal{Q}$.

###### Proof.

Let

$\displaystyle\mathcal{R}=\\{(X,f)\in\mathcal{Q}\times(\omega\cup\\{-1\\})^{\omega}$
$\displaystyle:\text{if $f(e)=-1$, then $\\{e\\}^{X}$ is ill-founded,}$
$\displaystyle\text{and if $f(e)=n>-1$, then
$\\{e\\}^{X}\cong\\{n\\}^{\emptyset}$}\\}.$

Note that $\mathcal{R}$ is $\Sigma^{1}_{1}$. In order to show that
$\mathcal{R}$ is nonempty via the Gandy Basis Theorem, we fix
$X\in\mathcal{Q}$ with $\omega_{1}^{X}=\omega_{1}^{ck}$. Then for every $e$
such that $\\{e\\}^{X}$ is well founded, there is an $n$ with
$\\{e\\}^{X}\cong\\{n\\}^{\emptyset}$, so we define $f(e)=n$ for such an $n$.
For $e$ such that $\\{e\\}^{X}$ is ill founded, we define $f(e)=-1$. Then
$(X,f)\in\mathcal{R}$.

As $\mathcal{R}$ is a nonempty $\Sigma^{1}_{1}$ class, there is some
$(X,f)\in\mathcal{R}$ computable from $\mathcal{O}$. Then
$e\in\mathcal{O}^{X}$ if and only if $-1<f(e)\in\mathcal{O}$, and so
$\mathcal{O}^{X}\leq_{T}\mathcal{O}$. Furthermore, the process for
constructing the Turing reduction is uniform from an index for $\mathcal{Q}$.
∎

Since there is a Turing functional $\Phi$ with $\Phi^{\mathcal{O}^{X}}=X$ for
all $X$, we immediately get $X\leq_{T}\mathcal{O}$ uniformly for the $X$ of
the above lemma. This also follows from the construction.

Note that our construction relativizes to provide the following:

######  Lemma 2.10.

For any oracle $A$, if $\mathcal{Q}$ is a non-empty $\Sigma^{1}_{1}(A)$ class,
there is an $X\in\mathcal{Q}$ with $X\leq_{T}\mathcal{O}^{A}$ and
$\mathcal{O}^{A,X}\leq_{T}\mathcal{O}^{A}$, and indices for these reductions
can be found uniformly from an index for $\mathcal{Q}$ independently of $A$.

We will also need some basic results about pointed perfect trees.

######  Definition 2.11.

A pointed perfect tree is a function $f:2^{<\omega}\to 2^{<\omega}$ such that
$\sigma\subseteq\tau$ if and only if $f(\sigma)\subseteq f(\tau)$ and such
that for every $X\in 2^{\omega}$, we have that
$f(X)=\bigcup_{n}f(X\mskip-3.0mu\mskip-3.0mu\upharpoonright_{n})$ computes
$f$.

A uniformly pointed perfect tree is a pointed perfect tree $f$ such that there
is a Turing functional $\Phi$ with $\Phi^{f(X)}=f$ for all $X\in 2^{\omega}$.

If $f$ is a pointed perfect tree and $Y\in 2^{\omega}$, we define $g=f\oplus
Y$ by

$g(\sigma)=f(\sigma\oplus
Y\mskip-3.0mu\mskip-3.0mu\upharpoonright_{|\sigma|}),$

and if $f$ and $g$ are pointed perfect trees, we define $g\leq f$ if
$\text{range}(g)\subseteq\text{range}(f)$.

Some explanation may be in order on the terminology. The literal “tree” in
question is the downward closure of the range of the function $f$, and under
the conditions described, this tree is, in fact, perfect in the sense that
there is splitting beyond any finite node. In several older papers the authors
have consulted that use this terminology, there seems to be no clear
explanation of why the term “pointed” has the meaning it is given here.

######  Lemma 2.12.

If $f$ is a (uniformly) pointed perfect tree, then the following hold:

  1. (1)

For any $Y\in 2^{\omega}$, $g=f\oplus Y$ is a (uniformly) pointed perfect
tree,

  2. (2)

$Y\leq_{T}g(X)$ for every $X\in 2^{\omega}$, and

  3. (3)

$Y\leq_{T}g$.

###### Proof.

Certainly $g$ is a function with the necessary extension condition. It remains
in point 1 to show the (uniform) computability of $g$ from each $g(X)$. For
any $X$, we have $g(X)=f(X\oplus Y)$, so $g(X)$ computes $f$ by assumption.
The pair $(g(X),f)=(f(X\oplus Y),f)$ computes $X\oplus Y$ and so computes $Y$,
and $(f,Y)$ computes $g$. Since $g$ computes $g(0^{\infty})$, it follows that
$Y\leq_{T}g$. All of this is uniform if the reduction from $f(X\oplus Y)$ to
$f$ is. ∎

Note that the formula that says “$f$ is a uniformly pointed perfect tree” is
arithmetic (the argument relies on the compactness of $2^{\omega}$). Note also
that if $f$ is a pointed perfect tree, $|f(\sigma)|\geq|\sigma|$ for all
$\sigma$.

We are now ready to construct a high for isomorphism degree strictly below
$\mathcal{O}$. Our proof is inspired by Jockusch and Simpson’s construction in
[21] of a minimal upper bound for $\Delta^{1}_{1}$ with a triple jump
computable from $\mathcal{O}$, although we use strongly hyperlow trees (i.e.,
trees $f$ such that $\mathcal{O}^{f}\leq_{T}\mathcal{O}$) rather than their
$\Delta^{1}_{1}$ trees.

######  Proposition 2.13.

There is a degree $\mathbf{d}$ which is high for isomorphism with
$\mathbf{d}^{(3)}=\mathcal{O}$.

###### Proof.

For a set $X$, we take $X^{(3)}=\\{e:\exists m\,[\lambda
z.\\{e\\}^{X}(m,z)\text{ is total}]\\}$.

We build an $\mathcal{O}$-computable sequence of uniformly pointed perfect
trees $f_{0}\geq f_{1}\geq\dots$ where
$\mathcal{O}^{f_{i}}\leq_{T}\mathcal{O}$ for each $i$ (and the sequence of
indices for the reductions is computable in $\mathcal{O}$). We alternate
between working to force the triple jump and coding the next required
isomorphism.

We begin by setting $f_{0}$ to be the identity: $f_{0}(\sigma)=\sigma$.

Suppose we have defined $f_{n}$ with $n=2\langle e,0\rangle$. Consider the
class

$\displaystyle U_{e}=\\{g:\ $ $\displaystyle\text{$g$ is a uniformly pointed
perfect tree}\ \&\ g\leq f_{n}$ $\displaystyle\&\ \exists m\,[\lambda
z.\\{e\\}^{g(X)}(m,z)\text{ is total for every $X\in 2^{\omega}$}]\\}.$

This is arithmetic relative to $f_{n}$ (again, this relies on compactness) and
thus is a $\Sigma^{1}_{1}(f_{n})$ class. Thus $\mathcal{O}^{f_{n}}$ can decide
whether $U_{e}$ is empty, and since $\mathcal{O}^{f_{n}}\leq_{T}\mathcal{O}$,
so can $\mathcal{O}$.

If $U_{e}$ is nonempty, there is a $g\in U_{e}$ with
$\mathcal{O}^{g}\leq_{T}\mathcal{O}^{f_{n}}\leq_{T}\mathcal{O}$, and indices
for the relevant reductions can be obtained effectively. We thus let
$f_{n+1}=g$, and we have now forced $e$ into the triple jump. By replacing $g$
with $\lambda\sigma.g(0^{n}\widehat{\phantom{\alpha}}\sigma)$, we may assume
that $|f_{n+1}(\langle\rangle)|>n$.

If $U_{e}$ is empty, we let $f_{n+1}=f_{n}$ (again, adjusting to ensure
$|f_{n+1}(\langle\rangle)|>n$). By our actions at steps $2\langle
e,m+1\rangle$ for $m\in\omega$, we will force $e$ out of the triple jump.

Now suppose instead that we have defined $f_{n}$ with $n=2\langle
e,m+1\rangle$. If $U_{e}$ was nonempty at step $2\langle e,0\rangle$, then the
triple jump is already forced at $e$, so we let $f_{n+1}=f_{n}$.

If $U_{e}$ was empty at step $2\langle e,0\rangle$, we know there are $\tau$
and $z$ such that
$\\{e\\}^{f_{n}(\sigma)}(m,z)\mskip-3.0mu\mskip-3.0mu\uparrow$ for every
$\sigma\supseteq\tau$: if this were not the case, we could define an $h$ as
follows for a contradiction.

  * •

Let $h(\langle\rangle)=\sigma$ for the first string $\sigma$ discovered with
$\\{e\\}^{f_{n}(\sigma)}(m,0)\mskip-3.0mu\mskip-3.0mu\downarrow$.

  * •

For $\rho\in 2^{<\omega}$ and $i<2$, let
$h(\rho\widehat{\phantom{\alpha}}i)=\sigma$ for the first string
$\sigma\supseteq h(\rho)\widehat{\phantom{\alpha}}i$ discovered with
$\\{e\\}^{f_{n}(\sigma)}(m,|\rho|+1)\mskip-3.0mu\mskip-3.0mu\downarrow$.

By assumption, $h$ is total. Now we let $g=f_{n}\circ h$. Note that
$h\leq_{T}f_{n}$, so $g\leq_{T}f_{n}$, and for every $X$, $g(X)=f(h(X))$. Thus
$g$ is a uniformly pointed perfect tree, and $g\leq f_{n}\leq f_{2\langle
e,0\rangle}$. Also, $\lambda z.\\{e\\}^{g(X)}(m,z)$ is total for all $X$, and
so $g\in U_{e}$ contrary to assumption. Therefore, there must be such a $\tau$
and $z$. The set of such pairs $(\tau,z)$ is arithmetical in $f_{n}$, and so
$\mathcal{O}^{f_{n}}\leq_{T}\mathcal{O}$ can uniformly find such a pair.

We define $f_{n+1}(\sigma)=f_{n}(\tau\widehat{\phantom{\alpha}}\sigma)$. So
$\\{e\\}^{f_{n+1}(X)}(m,z)\mskip-3.0mu\mskip-3.0mu\uparrow$ for every $X\in
2^{\omega}$, and we have taken another step towards forcing the triple-jump at
$e$.

Suppose instead we have defined $f_{n}$ with $n=2\langle k,m\rangle+1$. We
will choose $f_{n+1}$ able to compute an isomorphism between $\mathcal{M}_{k}$
and $\mathcal{M}_{m}$ if such an isomorphism exists. Consider
$V_{n}=\\{r\in\omega^{\omega}\ |\ r:\mathcal{M}_{k}\cong\mathcal{M}_{m}\\}$.
This is a $\Sigma^{1}_{1}$ class, and $\mathcal{O}$ can therefore determine
whether it is empty.

If $V_{n}$ is empty, we define $f_{n+1}=f_{n}$. If $V_{n}$ is nonempty, then
we note that $V_{n}$ is also a $\Sigma^{1}_{1}(f_{n})$ class. This means that
there is an $r\in V_{n}$ with
$\mathcal{O}^{r,f_{n}}\leq_{T}\mathcal{O}^{f_{n}}\leq_{T}\mathcal{O}$, and
relevant indices can be obtained effectively. Let $R$ be a set coding $r$ in
some effective fashion, and let $f_{n+1}=f_{n}\oplus R$. Then
$f_{n+1}\leq_{T}(f_{n},R)$, and so $\mathcal{O}^{f_{n+1}}\leq_{T}\mathcal{O}$.

By construction, $|f_{n+1}(\langle\rangle)|>n$ for every $n=2\langle
e,0\rangle$. We let

$D=\bigcup_{n=2\langle e,0\rangle}f_{n+1}(\langle\rangle).$

Then for every $n$, $D=f_{n}(X)$ for some $X$, so if
$\mathcal{M}_{k}\cong\mathcal{M}_{m}$, we can let $n=2\langle k,m\rangle$.
Furthermore, for the $r$ chosen at step $n$, we have

$r\equiv_{T}R\leq_{T}f_{n}\oplus R=f_{n+1}\leq_{T}D,$

and thus $D$ computes an isomorphism between $\mathcal{M}_{k}$ and
$\mathcal{M}_{m}$.

Furthermore, $e\in D^{(3)}$ precisely when $U_{e}$ is nonempty by
construction. Since the construction is $\mathcal{O}$-computable,
$D^{(3)}\leq_{T}\mathcal{O}$. By Proposition 2.8, $\mathbf{d}=\text{\bf
deg}(D)$ is the desired degree. ∎

From this result, combined with Proposition 2.1, we immediately obtain the
following.

######  Corollary 2.14.

There is a degree $\mathbf{d}$ which is uniformly high for isomorphism with
$\mathbf{d}^{\prime}=\mathcal{O}$.

It is worthwhile to contrast the state of our knowledge for the jumps of
degrees high for isomorphism with those uniformly high for isomorphism.
Certainly both classes are closed upwards in the Turing degrees. Proposition
2.8 tells us that a degree high for isomorphism is at most three jumps below
$\mathcal{O}$, and we have an example showing that this is tight. On the other
hand, the same proposition tells us that a degree uniformly high for
isomorphism is at most two jumps below $\mathcal{O}$, but the best example we
have is only one jump below $\mathcal{O}$. We can, at least, rule out one
nonexample.

######  Proposition 2.15.

If $\mathbf{d}$ is high for isomorphism with $\mathbf{d}^{(3)}=\mathcal{O}$,
then $\mathbf{d}^{\prime}$ is not uniformly high for isomorphism.

###### Proof.

If $\mathbf{d}^{\prime}$ were uniformly high for isomorphism, then by
Proposition 2.8, $\mathcal{O}$ would be $\Sigma^{0}_{2}(\mathbf{d}^{\prime})$
and thus $\Sigma^{0}_{3}(\mathbf{d})$. As $\mathbf{d}$ is high for
isomorphism, $\mathcal{O}$ is $\Pi^{0}_{3}(\mathbf{d})$, and so $\mathcal{O}$
would be $\Delta^{0}_{3}(\mathbf{d})$, contradicting
$\mathbf{d}^{(3)}=\mathcal{O}$. ∎

It is perhaps natural to wonder whether $\mathcal{O}$ is the only bound of all
degrees below $\mathcal{O}$ which are high for isomorphism. We might also ask
whether the degrees high for isomorphism are linearly ordered, or whether
there is a least degree which is high for isomorphism. The next result
resolves all of these questions.

######  Proposition 2.16.

There exist degrees $\mathbf{d}_{1}$ and $\mathbf{d}_{2}$, each uniformly high
for isomorphism, with $\mathbf{d}_{i}\lneq_{T}\mathcal{O}$ such that
$\mathbf{d}_{1}\oplus\mathbf{d}_{2}\equiv_{T}\mathcal{O}$, and any
$\mathbf{d}\leq_{T}\mathbf{d}_{1},\mathbf{d}_{2}$ is hyperarithmetic.

###### Proof.

We will construct, effectively in $\mathcal{O}$, two degrees $\mathbf{d}_{1}$
and $\mathbf{d}_{2}$, each of which enumerates $\omega-\mathcal{O}$, and such
that $\mathbf{d}_{1}\oplus\mathbf{d}_{2}\equiv_{T}\mathcal{O}$. By Theorem
5.2, these degrees will be uniformly high for isomorphism.

Let $\langle\cdot,\cdot\rangle$ be a bijection of $\omega^{2}$ with
$\omega-\\{2^{k}:k\in\omega\\}$. We first define an operator $R$ on
$2^{<\omega}$ by setting $R(\sigma)$ to be the set of $n$ such that there is
$k$ with $\sigma(\langle k,n\rangle)=1$, and we set
$\delta_{1,0}=\delta_{2,0}=\emptyset$. We will maintain that
$R(\delta_{1,s}),R(\delta_{2,s})\subset\omega-\mathcal{O}$, and we will
arrange that
$\bigcup_{s}R(\delta_{1,s})=\bigcup_{s}R(\delta_{2,s})=\omega-\mathcal{O}$.

At stage $5s$, we search, using oracle $\mathcal{O}$, for some $\sigma\in
2^{<\omega}$ extending $\delta_{1,5s}$ such that
$\varphi_{s}^{\sigma}(s)\mskip-3.0mu\mskip-3.0mu\downarrow$ and
$R(\sigma)\cap\mathcal{O}=\emptyset$. If such a $\sigma$ exists (a
$\Sigma_{1}^{1}$ condition), we set $\delta_{1,5s+1}=\sigma$ and
$\delta_{2,5s+1}=\delta_{2,5s}\cup\\{(2^{k_{5s}},1)\\}$ for the least
$k_{5s}>\left|\delta_{2,5s}\right|$. Otherwise, we set
$\delta_{1,5s+1}=\delta_{1,5s}$ and
$\delta_{2,5s+1}=\delta_{2,5s}\cup\\{(2^{k_{5s}},0)\\}$. At stage $5s+1$, we
act similarly, exchanging the roles of $\delta_{1}$ and $\delta_{2}$.

At stage $5s+2$, we let $n_{5s+1}$ be the least such that

$n_{5s+1}\in(\omega-\mathcal{O})\cap\left(\omega-R\left(\delta_{1,5s+2}\right)\right)$

and find the least $k_{5s+2}$ such that $\langle
k_{5s+2},n_{5s+1}\rangle>\left|\delta_{1,5s+2}\right|$. We set

$\delta_{1,5s+3}=\delta_{1,5s+2}\cup\left\\{(\langle
k_{5s+1},n_{5s+1}\rangle,1)\right\\}$

and $\delta_{2,5s+3}=\delta_{2,5s+2}$. At stage $5s+3$, we act similarly,
again exchanging the roles of $\delta_{1}$ and $\delta_{2}$.

At stage $5s+4$, we let $s=\langle e_{1},e_{2}\rangle$. Fix the least
$k_{1}>|\delta_{1,5s+4}|$ and $k_{2}>|\delta_{2,5s+4}|$. We search, using
oracle $\mathcal{O}$, for some $\sigma_{1}$ extending $\delta_{1,5s+4}$ and
$\sigma_{2}$ extending $\delta_{2,5s+4}$ with
$\sigma_{1}(2^{k_{1}})=\sigma_{2}(2^{k_{2}})=1$ and
$R(\sigma_{1})\cap\mathcal{O}=R(\sigma_{2})\cap\mathcal{O}=\emptyset$ and some
$m$ with
$\Phi_{e_{1}}^{\sigma_{1}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow\neq\Phi_{e_{2}}^{\sigma_{2}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow$.
If such $\sigma_{1}$ and $\sigma_{2}$ exist (a $\Sigma^{1}_{1}$ condition), we
set $\delta_{1,5s+5}=\sigma_{1}$ and $\delta_{2,5s+5}=\sigma_{2}$.

If no such pair exists, we instead search for a split above just
$\delta_{1,5s+4}$. If there are strings $\tau_{1},\tau_{2}$ both extending
$\delta_{1,5s+4}$ with $\tau_{1}(2^{k_{1}})=\tau_{2}(2^{k_{1}})=1$ and
$R(\tau_{1})\cap\mathcal{O}=R(\tau_{2})\cap\mathcal{O}=\emptyset$ and some $m$
with
$\Phi_{e_{1}}^{\tau_{1}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow\neq\Phi_{e_{1}}^{\tau_{2}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow$,
then we let

$\delta_{1,5s+5}=\delta_{1,5s+4}\cup\\{(2^{k_{1}},0)\\}$

and

$\delta_{2,5s+5}=\delta_{2,5s+4}\cup\\{2^{k_{2}},1)\\}.$

Otherwise, we let $\delta_{1,5s+5}=\delta_{1,5s+4}\cup\\{(2^{k_{1}},1)\\}$ and
$\delta_{2,5s+5}=\delta_{2,5s+4}\cup\\{(2^{k_{2}},0)\\}$.

We now let $D_{i}=\bigcup\limits_{s\in\omega}\delta_{i,s}$ for each $i$. We
note that, by construction, each $D_{i}$ enumerates $(\omega-\mathcal{O})$ and
is computable from $\mathcal{O}$; indeed, $\mathcal{O}$ can compute
$D_{i}^{\prime}$, since when we find at stage $5s$ that there is no $\sigma$
which both forces convergence and maintains disjointness from $\mathcal{O}$,
we commit to never allowing $\varphi_{s}^{D_{i}}(s)$ to converge. By a
standard argument, $D_{1}\oplus D_{2}$ can compute the sequence
$(\delta_{1,s},\delta_{2,s})_{s\in\omega}$. Thus the join can compute
$\mathcal{O}$, as $n\in\mathcal{O}$ if and only if $n\not\in
R(\delta_{1,5(n+1)})$.

Finally, we argue that if $X\leq_{T}D_{1},D_{2}$, then $X$ is hyperarithmetic.
Fix $s=\langle e_{1},e_{2}\rangle$ with
$X=\Phi_{e_{1}}^{D_{1}}=\Phi_{e_{2}}^{D_{2}}$. Then we must not have found the
desired strings $\sigma_{1},\sigma_{2}$ at stage $5s+4$. Suppose we found the
subsequent strings $\tau_{1},\tau_{2}$ and the corresponding $m$ instead. Then
$D_{2}(2^{k_{2}})=1$ and
$\Phi_{e_{2}}^{D_{2}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow$, so there is some
initial segment of $D_{2}$ witnessing this convergence and extending
$\delta_{2,5s+4}$. There is some $j$ such that
$\Phi_{e_{1}}^{\tau_{j}}(m)\neq\Phi_{e_{2}}^{D_{2}}(m)$, which gives us a pair
$\sigma_{1},\sigma_{2}$, contrary to the above.

So we did not find $\tau_{1}$ and $\tau_{2}$, meaning that
$D_{1}(2^{k_{1}})=1$. Thus, for any $m$ and any $\tau$ extending
$\delta_{1,5s+4}$ with $\tau(2^{k_{1}})=1$ and
$R(\tau)\cap\mathcal{O}=\emptyset$, we have

$\Phi_{e_{1}}^{\tau}(m)\mskip-3.0mu\mskip-3.0mu\downarrow\Rightarrow\Phi_{e_{1}}^{\tau}(m)=\Phi_{e_{1}}^{D_{1}}(m)=X(m).$

Thus $X(m)=1$ if and only if there is such a $\tau$ with
$\Phi_{e_{1}}^{\tau}(m)=1$, and $X(m)=0$ if and only if there is such a $\tau$
with $\Phi_{e_{1}}{\tau}(m)$. These are both $\Sigma^{1}_{1}$ conditions, so
$X$ is $\Delta^{1}_{1}$. ∎

###  2.2. High for a restricted class of isomorphisms

In the definition of highness for isomorphism, we considered isomorphisms
between any two computable structures. We will now restrict our attention to
isomorphisms of a particular class of computable structures, namely
presentations of the Harrison order $\omega_{1}^{ck}\cdot(1+\mathbb{Q})$; a
similar analysis was done in the context of lowness for isomorphism by Suggs
[26].

######  Definition 2.17.

A degree $\mathbf{d}$ is high for isomorphism for Harrison orders if
$\mathbf{d}$ computes an isomorphism between any two computable linear orders
of order type $\omega_{1}^{ck}(1+\mathbb{Q})$. We define _uniformly high for
isomorphism for Harrison orders_ in the natural way.

Our goal is to show that this is the same class of degrees previously
considered and thus that Harrison orders are universal in the context of
highness for isomorphism (i.e. restricting attention from all structures to
Harrison orders gives no loss of generality), much as, e.g., computable Polish
spaces are in the context of lowness for isomorphism [11].

######  Theorem 2.18.

The degrees which are (uniformly) high for isomorphism for Harrison orders are
precisely the degrees which are (uniformly) high for isomorphism.

We begin with the following lemma, recalling Notation 2.5.

######  Lemma 2.19.

$S\star T$ has an infinite path if and only if both $S$ and $T$ do. Moreover,
if $S$ and $T$ are computable, then a path through $S\star T$ uniformly
computes paths through $S$ and $T$, and the join of a path through $S$ with a
path through $T$ uniformly computes a path through $S\star T$.

###### Proof.

A sequence $((\sigma_{0}^{i},\sigma_{1}^{i}))_{i\in\omega}$ is a path through
$S\star T$ if and only if $(\sigma_{0}^{i})_{i\in\omega}$ is a path through
$S$ and $(\sigma_{1}^{i})_{i\in\omega}$ is a path through $T$. ∎

###### Proof of Theorem 2.18.

The backwards direction is immediate. For the other direction, we will show
that (uniform) highness for isomorphism for Harrison orders implies (uniform)
highness for paths. Specifically, given a computable tree $T$ generating a
$\Pi^{0}_{1}$ class, we will uniformly exhibit a pair of computable linear
orders such that if $[T]$ is nonempty, then the linear orders are both of
order type $\omega_{1}^{ck}(1+\mathbb{Q})$, and we will give a uniform process
to compute an element of $[T]$ from an isomorphism between the orders. This
will suffice to establish the result.

First, we fix a Harrison order $\mathcal{H}$, i.e., a computable linear order
of order type $\omega_{1}^{ck}(1+\mathbb{Q})$ with no descending
hyperarithmetic sequence. Let $\mathcal{L}=\mathcal{H}(1+\mathbb{Q})$. Note
that $\mathcal{L}\cong\mathcal{H}$: it is easy to see that
$(1+\mathbb{Q})(1+\mathbb{Q})$ has a least element and is otherwise a
countable dense linear order without endpoints, whence
$(1+\mathbb{Q})(1+\mathbb{Q})\cong 1+\mathbb{Q}$; and multiplication of linear
orders is associative. Furthermore, there is a computable embedding
$\iota:\mathbb{Q}\hookrightarrow\mathcal{L}$: fix some $h\in\mathcal{H}$, and
define $\iota(q)=(h,q)$. Let $S$ be the tree of finite descending sequences in
$\mathcal{H}$.

Now fix a computable tree $T$.

######  Claim 2.20.

If $T$ has an infinite path, then $KB(S\star T)$, the Kleene-Brouwer ordering
on $S\star T$, has order type $\omega_{1}^{ck}(1+\mathbb{Q})+1$, where the
final element is $\langle\rangle$, the root of $S\star T$.

###### Proof of claim.

We fix $n\in\omega$ extendable to an infinite path through $T$ and note that
$KB(S\star T)\cong\left(\sum_{i\in\omega}\mathcal{L}_{i}\right)+1$, where
$\mathcal{L}_{i}$ is the Kleene-Brouwer ordering of the subtree extending the
$i$th child of the root. As none of these subtrees have a hyperarithmetic
path, each $\mathcal{L}_{i}$ is either well founded or has order type
$\omega_{1}^{ck}(1+\mathbb{Q})+\alpha$ for some (possibly empty) well order
$\alpha$. To establish the claim, it suffices to show that there are
infinitely many $i$ such that $\mathcal{L}_{i}$ is ill founded. However, each
$i$ corresponding to a pair $(a,n)$ with $a$ in the ill-founded part of
$\mathcal{H}$ is extendible to a path through $S\star T$, and so such an
$\mathcal{L}_{i}$ is ill founded. As there are infinitely many such $a$, the
claim follows. ∎

Note that $S$ has the property that if $\sigma\in S$ is extendible to an
infinite path, then $\sigma$ has infinitely many immediate children in $S$. It
follows that $S\star T$ has the same property.

Let $\mathcal{K}$ be the order made from $KB(S\star T)$ by removing the root
$\langle\rangle$. Then $\mathcal{L}$ and $\mathcal{K}$ are our two orders of
order type $\omega_{1}^{ck}(1+\mathbb{Q})$. Observe that if $\tau\in S\star
T$, then $\\{\rho\in S\star T:\rho\supset\tau\\}$ is a computable, convex set
in $\mathcal{K}$.

Suppose now that $f:\mathcal{L}\cong\mathcal{K}$. We recursively construct a
sequence $(\tau_{n})_{n\in\omega}$ of elements of $S\star T$ with
$\tau_{n}\subset\tau_{n+1}$ and maintain the inductive assumption that
$f\circ\iota$ maps a nontrivial interval of $\mathbb{Q}$ into $\\{\rho\in
S\star T:\rho\supset\tau_{n}\\}$ (and thus that this interval of $K$ is ill
founded, and so $\tau_{n}$ is extendible to a path through $S\star T$). We
begin with $\tau_{0}=\langle\rangle$.

Suppose we have defined $\tau_{n}$. Then we let $(\alpha_{m})_{m\in\omega}$
enumerate the immediate children of $\tau_{n}$. Observe that
$\bigsqcup_{m}\\{\rho\in S\star T:\rho\supseteq\alpha_{m}\\}$ partitions
$\\{\rho\in S\star T:\rho\supset\tau_{n}\\}$, each component of the partition
is convex in the ordering of $K$, and the components are arranged with order
type $\omega$ (in the ordering of $K$). So there must be rationals
$q_{0}<q_{1}$ and an $m$ with $f(\iota(q_{0})),f(\iota(q_{1}))\in\\{\rho\in
S\star T:\rho\supseteq\alpha_{m}\\}$. We search for such an $m$ and define
$\tau_{n+1}=\alpha_{m}$. Now, we can observe that $\\{\rho\in S\star
T:\rho\supset\tau_{n+1}\\}$ contains the open interval from $f(\iota(q_{0}))$
to $f(\iota(q_{1}))$, and so the inductive assumption is maintained.

Thus $f$ uniformly computes $(\tau_{n})_{n\in\omega}$, which is a path through
$S\star T$, and therefore it gives a path through $T$. This completes the
proof. ∎

##  3\. Scott analysis

As we consider our intuition for what might make a degree high for
isomorphism, we naturally look to the possibility of back-and-forth arguments:
the reason that the countable dense linear order without endpoints is
computably categorical is that we can computably find the necessary extensions
for a partial isomorphism.

A sweeping generalization of this condition is given by the so-called _back-
and-forth relations_.

######  Definition 3.1.

Let $\mathcal{A}$ and $\mathcal{B}$ be structures, and let $\bar{a}$ and
$\bar{b}$ be finite tuples of the same length in $\mathcal{A}$ and
$\mathcal{B}$, respectively. We then define the following relations:

  1. (1)

We say that $(\mathcal{A},\bar{a})\leq_{1}(\mathcal{B},\bar{b})$ if and only
if every finitary $\Sigma_{1}$ formula true of $\bar{b}$ in $\mathcal{B}$ is
true of $\bar{a}$ in $\mathcal{A}$.

  2. (2)

For $\alpha>1$, we say that
$(\mathcal{A},\bar{a})\leq_{\alpha}(\mathcal{B},\bar{b})$ if and only if for
every finite $\bar{d}\subseteq\mathcal{B}$ and every $\beta<\alpha$ there is
some finite $\bar{c}\subseteq\mathcal{A}$ such that
$(\mathcal{B},\bar{b}\bar{d})\leq_{\beta}(\mathcal{A},\bar{a}\bar{c})$.

In some cases—for instance, the countable dense linear order without
endpoints—these are easy to compute. In general, they are not. For instance,
among computable ordinals, these relations specify the place of each element
of $\bar{a}$ in its copy of $\omega^{\alpha}$ for some appropriate $\alpha$.
These relations are discussed in detail in [1, 3].

It is reasonable to hope that the degrees which are uniformly high for
isomorphism would be exactly those degrees which can uniformly compute all of
these relations. Although this does not turn out to be true, we believe the
concept is interesting and that the separation gives important information
about both classes.

######  Definition 3.2.

We say that a degree $\mathbf{d}$ is _Scott complete_ if and only if there is
an algorithm which, given indices for a computable structure $\mathcal{A}$ and
a Harrison order $\mathcal{H}$, will give an index for a
$\mathbf{d}$-computable function
$\mathbf{b}:\left(\mathcal{A}^{<\omega}\right)^{2}\times\mathcal{H}\to\\{0,1\\}$
with the following properties (we abbreviate $\mathbf{b}(\bar{a},\bar{b},x)=1$
by $\bar{a}\leq_{x}\bar{b}$):

  1. (1)

If $\mathbf{1}$ is the least element of $\mathcal{H}$, then
$\bar{a}\leq_{\mathbf{1}}\bar{b}$ if and only if every finitary $\Sigma_{1}$
formula true of $\bar{b}$ is true of $\bar{a}$.

  2. (2)

If $x\in\mathcal{H}$ is not the least element, then $\bar{a}\leq_{x}\bar{b}$
if and only if for every finite $\bar{d}\subseteq\mathcal{A}$ and every $y<x$
there is some finite $\bar{c}\subseteq\mathcal{A}$ such that
$\bar{b}\bar{d}\leq_{y}\bar{a}\bar{c}$.

While we do not explicitly name the uniformity in this definition (having
nothing to say at this point about a nonuniform variant), it is germane to
note that the notion of Scott completeness belongs to the family of “uniform”
highness notions we explore in this paper. Since we know that no degree can be
both high for isomorphism and low for $\omega_{1}^{ck}$, the following result
separates the two classes.

######  Proposition 3.3.

There is a degree which is Scott complete and low for $\omega_{1}^{ck}$.

###### Proof.

The two conditions of Definition 3.2 can be applied in the context of any
linear order $\mathcal{L}$. Moreover, for any structure $\mathcal{A}$ and any
linear order $\mathcal{L}$, there always exists a sequence
$(\leq_{x}:x\in\mathcal{L})$ satisfying these conditions, since we can always
take the standard back-and-forth relations for the greatest well-founded
initial segment of $\mathcal{L}$, and equality thereafter.

Now consider the set $S$ of all triples $(e,i,\mathbf{b})$ where $e$ is the
index for a computable structure, $i$ is the index for a linear order, and
$\mathbf{b}$ is a function satisfying the conditions of Definition 3.2. The
set of selectors $\eta:\mathbb{N}^{2}\to 2^{\omega}$ such that for every
$(e,i)$ we have $(e,i,\eta(e,i))\in S$ is now a $\Sigma^{1}_{1}$ class. By the
Gandy Basis Theorem, this class has an element which is low for
$\omega_{1}^{ck}$. ∎

The key difference is that a sequence $(\leq_{x}:x\in\mathcal{L})$ always
exists for any structure $\mathcal{A}$ and any linear order $\mathcal{L}$. In
contrast, $\Sigma^{1}_{1}$ classes do not always have elements, and pairs of
structures do not always have isomorphisms between them.

As the proof shows, Scott completeness follows from computing an element of a
particular $\Sigma^{1}_{1}$ class, and thus by Proposition 2.6, highness for
isomorphism implies Scott completeness. We will find, however, that combining
Scott completeness with an additional property gives a characterization of the
degrees that are high for isomorphism (Theorem 4.48).

##  4\. Computing descending sequences

Now we consider the task of finding descending sequences in linear orders. The
reader familiar with the theory of computable ordinals and the Kleene-Brouwer
ordering may expect this to be the same as the task of finding paths through
trees and thus the same as that of finding isomorphisms, but this turns out
not to be the case.

######  Definition 4.1.

If $\mathcal{L}$ is a linear order, a tight descending sequence in $L$ is an
infinite descending sequence which is unbounded below in the ill-founded part
of $\mathcal{L}$, i.e., if $f$ is a tight descending sequence and $g$ is any
descending sequence, then for every $n$ there is an $m$ with
$f(m)<_{\mathcal{L}}g(n)$.

######  Definition 4.2.

A degree $\mathbf{d}$ is high for (tight) descending sequences if any
computable ill-founded linear order $\mathcal{L}$ has a
$\mathbf{d}$-computable (tight) descending sequence.

Degrees that are uniformly high for (tight) descending sequences are defined
analogously.

As the descending sequences through a computable linear order form a
$\Pi^{0}_{1}$ class, it follows by Proposition 2.6 that (uniform) highness for
isomorphism implies (uniform) highness for descending sequences. We will show
that this implication is strict. As the set of indices for computable ill-
founded linear orders is $\Sigma^{1}_{1}$-complete, Proposition 2.8 holds for
(uniform) highness for descending sequences in place of (uniform) highness for
isomorphism, so the separation will not follow from a simple jump analysis. In
the nonuniform case, the separation turns out to be related to the question of
exactly which degrees can be coded into the descending sequences of a linear
order; we begin by introducing some notation.

######  Notation 4.3.

For $\sigma$ a nonempty finite sequence, let $l(\sigma)=\sigma(|\sigma|-1)$ be
the last element of $\sigma$.

For $\overline{\sigma}=(\sigma_{0},\dots,\sigma_{n-1})$ a collection of finite
sequences, write $l(\overline{\sigma},i)$ for $l(\sigma_{i})$.

For a linear order $\mathcal{L}$, let $W(\mathcal{L})$ denote the (possibly
empty) greatest well-founded initial segment.

######  Lemma 4.4.

If $\mathcal{L}$ is an infinite computable linear order, then either
$\mathcal{L}$ has a computable descending sequence or it has a
$\mathbf{0}^{\prime}$-computable ascending sequence.

###### Proof.

Suppose $\mathcal{L}$ has no computable descending sequence. Then
$\mathcal{L}$ must have a least element, as otherwise we can construct a
computable descending sequence $(a_{n})_{n\in\omega}$ by setting $a_{0}$ to be
any element and then, given $a_{n}$, searching for an element less than
$a_{n}$ to get $a_{n+1}$. For an $x\in\mathcal{L}$ that is not the greatest
element of $\mathcal{L}$, by applying the same argument to
$\\{y\in\mathcal{L}:x<_{\mathcal{L}}y\\}$, we see that $x$ must have an
immediate successor. Let $z$ be the least element of $\mathcal{L}$, and for
$x\in\mathcal{L}$ not the greatest element, let $s(x)$ be its immediate
successor. Then $z,s(z),s(s(z)),\dots$ is a $\mathbf{0}^{\prime}$-computable
ascending sequence. ∎

It is not hard to construct an ill-founded computable linear order such that
every descending sequence computes $\emptyset^{\prime}$. Similarly, one can
construct $n$ ill-founded computable linear orders such that every degree
computing a descending sequence through each of them computes
$\emptyset^{(n)}$. This turns out to be the best that is possible.

######  Proposition 4.5.

If $\mathcal{L}_{0},\dots,\mathcal{L}_{n-1}$ are computable ill-founded linear
orders and $X\not\in\Delta^{0}_{n+1}$, then there are descending sequences
$f_{0},\dots,f_{n-1}$ through $\mathcal{L}_{0},\dots,\mathcal{L}_{n-1}$,
respectively, such that $X\not\leq_{T}f_{0}\oplus\dots\oplus f_{n-1}$.

###### Proof.

The proof proceeds by induction on $n$.

First, suppose there is $k>0$ such that at least $k$ of the linear orders have
a descending $\mathbf{0}^{(k)}$-computable sequence. If $k=n$, the theorem
follows. Otherwise, without loss of generality,
$\mathcal{L}_{n-k},\dots,\mathcal{L}_{n-1}$ have descending
$\mathbf{0}^{(k)}$-computable sequences $f_{n-k},\dots,f_{n-1}$. Then, as
$X\not\in\Delta^{0}_{n-k+1}(\mathbf{0}^{(k)})$, by the inductive hypothesis
relative to $\mathbf{0}^{(k)}$ there are descending sequences
$f_{0},\dots,f_{n-k-1}$ through $\mathcal{L}_{0},\dots,\mathcal{L}_{n-k-1}$
such that $X\not\leq_{T}f_{0}\oplus\dots\oplus
f_{n-k-1}\oplus\mathbf{0}^{(k)}$, and thus
$X\not\leq_{T}f_{0}\oplus\dots\oplus f_{n-1}$.

Now suppose there is no such $k$. We use forcing in which a condition is a
tuple $(\sigma_{0},\dots,\sigma_{n-1})$ such that for $i<n$, $\sigma_{i}$ is a
finite descending sequence through $\mathcal{L}_{i}$, and if $\sigma_{i}$ is
nonempty, $l(\sigma_{i})\not\in W(\mathcal{L}_{i})$. We say that
$(\tau_{0},\dots,\tau_{n-1})$ extends $(\sigma_{0},\dots,\sigma_{n-1})$ if
each $\tau_{i}$ extends $\sigma_{i}$. Note that in general the set of
conditions is properly $\Sigma^{1}_{1}$. Clearly, a sufficiently generic
filter for this notion of forcing gives a tuple $(f_{0},\dots,f_{n-1})$ such
that $f_{i}$ is an infinite descending sequence through $\mathcal{L}_{i}$ for
$i<n$. We will show that a sufficiently generic filter gives
$f_{0}\oplus\dots\oplus f_{n-1}\not\geq_{T}X$.

For $\Phi$ a functional and
$\overline{\sigma}=(\sigma_{0},\dots,\sigma_{n-1})$, we will write
$\Phi^{\overline{\sigma}}$ for
$\Phi^{\sigma_{0}\oplus\dots\oplus\sigma_{n-1}}$.

Suppose $\overline{\sigma}$ is a condition and $\Phi$ is a Turing functional.
We must show that $\overline{\sigma}$ has an extension $\overline{\tau}$ with
$\overline{\tau}\Vdash[\Phi^{f_{0}\oplus\dots\oplus f_{n-1}}\neq X]$. If there
is an extension $\overline{\tau}$ and an $m$ with
$\Phi^{\overline{\tau}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow\neq X(m)$, then
we are done, and if there is an $m$ and a
$\overline{\tau}\preceq\overline{\sigma}$ such that for all
$\overline{\rho}\preceq\overline{\tau}$,
$\Phi^{\overline{\rho}}(m)\mskip-3.0mu\mskip-3.0mu\uparrow$, then we are also
done. Now let us suppose towards a contradiction that neither of these hold.

Let $D=\\{(\alpha_{0},\dots,\alpha_{n-1}):\alpha_{i}\supseteq\sigma_{i}\\}$;
$D$ is certainly computable. We will use
$\overline{\alpha},\overline{\beta},\overline{\gamma},\overline{\delta}$ for
elements of $D$, in contrast with
$\overline{\sigma},\overline{\tau},\overline{\rho}$ for conditions, and as
before, we will write $\Phi^{\overline{\alpha}}$ for
$\Phi^{\alpha_{0}\oplus\dots\oplus\alpha_{n-1}}$.

For $\overline{\alpha},\overline{\beta}\in D$, we write
$\overline{\alpha}\trianglelefteq\overline{\beta}$ if
$l(\overline{\alpha},i)\leq_{L_{i}}l(\overline{\beta},i)$ for all $i<n$; we
further write $\overline{\alpha}\bot\overline{\beta}$ if
$\overline{\alpha}\not\trianglelefteq\overline{\beta}$,
$\overline{\beta}\not\trianglelefteq\overline{\alpha}$, and, for each $i<n$,
$l(\overline{\alpha},i)\neq l(\overline{\beta},i)$. We define extension on $D$
in the natural fashion.

We construct uniformly $\Sigma^{0}_{1}(\mathbf{0^{\prime}})$ sets
$(A_{k})_{k\in\omega}$, each a subset of $D$, as follows.

  * •

$A_{0}=\\{\overline{\sigma}\\}$.

  * •

If we see $\overline{\alpha}\in D$ satisfying the following:

    * –

$\overline{\alpha}$ extends some element of $A_{k}$;

    * –

$\Phi^{\overline{\alpha}}(k)\mskip-3.0mu\mskip-3.0mu\downarrow$;

    * –

There are no $\overline{\beta},\overline{\beta}^{\prime}\in D$ and
$m\in\omega$ with $\overline{\alpha}\trianglelefteq\overline{\beta}$,
$\overline{\alpha}\trianglelefteq\overline{\beta}^{\prime}$ and
$\Phi^{\overline{\beta}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow\neq\Phi^{\overline{\beta}^{\prime}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow$;
and

    * –

$\overline{\alpha}\bot\overline{\gamma}$ for every $\overline{\gamma}$ already
enumerated into $A_{k+1}$;

then we enumerate $\overline{\alpha}$ into $A_{k+1}$.

######  Claim 4.6.

For every $k$ and $\overline{\alpha}\in A_{k}$, for some $i<n$,
$l(\overline{\alpha},i)\not\in W(\mathcal{L}_{i})$.

###### Proof.

Suppose not and fix an $\overline{\alpha}$ for which this fails. Then for
every condition $\overline{\rho}$,
$\overline{\alpha}\trianglelefteq\overline{\rho}$. Observe that

$X(m)=b\iff\exists\overline{\beta}\in
D\,[(\overline{\alpha}\trianglelefteq\overline{\beta})\wedge\Phi^{\overline{\beta}}(m)=b].$

This holds because if $X(m)=b$, then by assumption on $\overline{\sigma}$, a
condition $\overline{\rho}\preceq\sigma$ with $\Phi^{\overline{\rho}}(m)=b$
exists, and this is our witnessing $\overline{\beta}$. Then the existence of
the $\overline{\rho}$ for $X(m)$ and $\overline{\alpha}\in A_{k}$ implies
there cannot exist a witnessing $\overline{\beta}^{\prime}$ for $b\neq X(m)$.

Thus $X$ is computable, contrary to assumption. ∎

######  Claim 4.7.

If $A_{m}$ is finite for every $m\leq k$, then $A_{k}$ contains a condition
(and in particular, $A_{k}\neq\emptyset$).

###### Proof.

We proceed by induction on $k$. The result for $k=0$ is immediate.

Now consider the inductive case $k+1$. By the inductive hypothesis, we can fix
a condition $\overline{\alpha}=(\alpha_{0},\dots,\alpha_{n-1})\in A_{k}$. As
$|A_{k+1}|$ is finite, we fix $b_{i}<_{\mathcal{L}_{i}}l(\overline{\alpha},i)$
for each $i<n$ such that for every $\overline{\gamma}\in A_{k+1}$, if
$l(\overline{\gamma},i)\not\in W(L_{i})$, then
$b_{i}<_{\mathcal{L}_{i}}l(\overline{\gamma},i)$. Let
$\overline{\alpha}^{\prime}=(\alpha_{0}\widehat{\phantom{\alpha}}b_{0},\dots,\alpha_{n-1}\widehat{\phantom{\alpha}}b_{n-1})$.
We can see that $\overline{\alpha}^{\prime}$ is a condition. By the previous
claim, $\overline{\gamma}\not\trianglelefteq\overline{\alpha}$ for any
$\overline{\gamma}\in A_{k+1}$.

By our assumption on $\overline{\sigma}$, there is a condition
$\overline{\tau}\preceq\overline{\alpha}^{\prime}$ with
$\Phi^{\overline{\tau}}(n)\mskip-3.0mu\mskip-3.0mu\downarrow$. There cannot be
$\overline{\beta},\overline{\beta}^{\prime}\in D$ and $m\in\omega$ blocking
$\overline{\tau}$’s enumeration into $A_{k+1}$, as both would be conditions
extending $\overline{\sigma}$, and one of them would force
$\Phi^{f_{0}\oplus\dots\oplus
f_{n-1}}(m)\mskip-3.0mu\mskip-3.0mu\downarrow\neq X(m)$ contrary to assumption
on $\overline{\sigma}$.

Eventually we will locate $\overline{\tau}$. As
$l(\overline{\tau},i)\leq_{\mathcal{L}_{i}}b_{i}$ for $i<n$, it cannot be that
there is a $\overline{\gamma}\in A_{k+1}$ such that
$\overline{\gamma}\trianglelefteq\overline{\tau}$. Thus if there is
$\overline{\gamma}\in A_{k+1}$ such that
$\neg(\overline{\gamma}\bot\overline{\tau})$, it must be that
$\overline{\tau}\trianglelefteq\overline{\gamma}$, and thus
$\overline{\gamma}$ is a condition, so $\overline{\gamma}$ is the desired
element of $A_{k+1}$. Otherwise, $\overline{\tau}$ will be enumerated into
$A_{k+1}$ and $\overline{\tau}$ is the desired element of $A_{k+1}$. ∎

Note that if $n=1$, then the $\overline{\alpha}\bot\overline{\gamma}$
condition on $A_{k+1}$ implies each $A_{k+1}$ is a singleton. It follows that,
contrary to assumption, $\mathcal{L}_{0}$ has a
$\mathbf{0}^{\prime}$-computable descending sequence. Henceforth, we assume
$n>1$.

######  Claim 4.8.

There is a $k$ such that $A_{k}$ is infinite.

###### Proof.

Suppose not and consider the tree $T$ of finite sequences $\pi$ such that for
all $k<|\pi|$, $\pi(k)\in A_{k}$, and for $k<|\pi|-1$, the sequence $\pi(k+1)$
extends $\pi(k)$. Note that a path through $T$ gives a tuple
$(g_{0},\dots,g_{n-1})$ such that $g_{i}$ is a descending sequence through
$\mathcal{L}_{i}$ extending $\sigma_{i}$ for $i<n$ and such that
$\Phi^{g_{0}\oplus\dots\oplus g_{n-1}}=X$ is total. Also, as the $A_{k}$s are
finite and uniformly $\Sigma^{0}_{2}$, the class $[T]$ is effectively compact
relative to $\mathbf{0}^{\prime\prime}$. Thus $X\in\Delta^{0}_{3}$ contrary to
assumption. ∎

Now we can fix $k$ such that $A_{k}$ is infinite. For $i<n$, let
$B_{i}=\\{l(\overline{\alpha},i):\overline{\alpha}\in A_{k}\\}$. Note that for
$\overline{\alpha},\overline{\alpha}^{\prime}\in A_{k}$, since
$\overline{\alpha}\bot\overline{\alpha}^{\prime}$, we have that
$l(\overline{\alpha},i)\neq l(\overline{\alpha}^{\prime},i)$ for all $i<n$.
Thus each $B_{i}$ is infinite. Furthermore, each $B_{i}$ is $\Sigma^{0}_{2}$.

######  Claim 4.9.

Each of the $\mathcal{L}_{i}$s has a $\mathbf{0}^{(n)}$-computable descending
sequence, contrary to assumption.

###### Proof.

Fix $i$ and define a sequence $c_{0},\dots,c_{n-1}$ enumerating
$\\{0,\dots,n-1\\}$ as follows:

  * •

$c_{n-1}=i$;

  * •

Having defined $c_{j+1},\dots,c_{n-1}$, by assumption there is

$r\in\\{0,\dots,n-1\\}\setminus\\{c_{j+1},\dots,c_{n-1}\\}$

such that $L_{r}$ has no $\mathbf{0}^{(j+1)}$-computable descending sequence.
Let $c_{j}$ be such an $r$.

We now recursively build a sequence of injective functions $h_{j}:\omega\to
A_{k}$ and sets $C_{j}\subseteq B_{c_{j}}$ for $j<n-1$ such that $h_{j}$ is
$\mathbf{0}^{(j+2)}$-computable and $C_{j}$ is $\Sigma^{0}_{j+2}$ and
infinite. We construct them as follows:

  * •

$C_{0}=B_{c_{0}}$;

  * •

For $j<n-1$, given $C_{j}\subseteq B_{c_{j}}\subseteq\mathcal{L}_{c_{j}}$,
give $C_{j}$ the ordering induced by $\mathcal{L}_{c_{j}}$. Then $C_{j}$ is
$\mathbf{0}^{(j+1)}$-computably isomorphic to a
$\mathbf{0}^{(j+1)}$-computable linear order. By Lemma 4.4 relative to
$\mathbf{0}^{(j+1)}$ and the fact that $\mathcal{L}_{c_{j}}$ has no
$\mathbf{0}^{(j+1)}$-computable descending sequence, there is some
$\mathbf{0}^{(j+2)}$-computable ascending sequence through $C_{j}$. Each
element of this sequence comes from some unique $\overline{\alpha}\in A_{k}$,
so let $h_{j}$ list these elements of $\overline{\alpha}$ in the order given
by the ascending sequence. That is, the ascending sequence is

$l(h_{j}(0),c_{j})<_{\mathcal{L}_{c_{j}}}l(h_{j}(1),c_{j})<_{\mathcal{L}_{c_{j}}}\dots.$

  * •

For $j<n-2$, given $h_{j}$, let

$C_{j+1}=\\{l(h_{j}(m),c_{j+1}):m\in\omega\\}.$

As $h_{j}$ is injective and distinct elements of $A_{k}$ give distinct
elements of $B_{c_{j+1}}$, $C_{j+1}$ is infinite.

We observe that for $j<n-1$,
$\text{range}(h_{j+1})\subseteq\text{range}(h_{j})$. Thus, there is some
injective $g:\omega\to\omega$ such that $h_{j+1}=h_{j}\circ g$. By thinning
the ascending sequence which gives rise to $h_{j+1}$, we may assume that $g$
is ascending. This can be done without affecting the complexity of $h_{j+1}$.

It follows that for all $m_{0}<m_{1}$ and $j<n-1$, we have

$l(h_{n-2}(m_{0}),c_{j})<_{\mathcal{L}_{c_{j}}}l(h_{n-2}(m_{1}),c_{j}).$

As $h_{n-2}(m_{0})\bot h_{n-2}(m_{1})$, it must be true that

$l(h_{n-2}(m_{0}),i)>_{\mathcal{L}_{i}}l(h_{n-2}(m_{1}),i).$

As $h_{n-2}$ is $\mathbf{0}^{(n)}$-computable, this is a
$\mathbf{0}^{(n)}$-computable descending sequence in $\mathcal{L}_{i}$. ∎

This completes the proof of Proposition 4.5. ∎

######  Lemma 4.10.

If $\mathcal{L}$ is a computable ill-founded linear order with no arithmetic
tight descending sequences, then for every $n$ there is an
$a\in\mathcal{L}\setminus W(\mathcal{L})$ such that
$\\{z\in\mathcal{L}:z<_{\mathcal{L}}a\\}$ has no $\Delta^{0}_{n}$ descending
sequences.

###### Proof.

Suppose not, and fix an $n$ for which this fails. Then

$\mathcal{L}\setminus W(\mathcal{L})=\\{a:\text{$a$ bounds a $\Delta^{0}_{n}$
descending sequence}\\}$

is arithmetic, and as it has no least element, there is an arithmetic tight
descending sequence in $\mathcal{L}$. ∎

######  Porism 4.11.

If $\mathcal{L}_{0},\dots,\mathcal{L}_{n}$ are ill-founded linear orders
without arithmetic tight descending sequences and $X$ is not arithmetic, then
a sufficiently generic filter for the forcing notion described in the proof of
Proposition 4.5 will give tight descending sequences through the
$\mathcal{L}_{i}$ such that the join of these sequences does not compute $X$.

###### Proof.

Clearly a sufficiently generic filter gives a tight descending sequence. Given
a condition $\overline{\sigma}$ and a functional $\Phi$, we may first extend
$\overline{\sigma}$ such that each $l(\overline{\sigma},i)$ bounds no
$\Delta^{0}_{n+1}$ descending sequence in $\mathcal{L}_{i}$. By the arguments
given, $\overline{\sigma}$ can be extended to a $\overline{\tau}$ such that
$\overline{\tau}\Vdash\Phi^{f_{0}\oplus\dots\oplus f_{n-1}}\neq X$. ∎

Proposition 4.5 demonstrates the limit of what can be coded into the
descending sequences of finitely many linear orders. We consider the result to
be of independent interest, but the proof also serves as an opportunity to
develop the tools we will need to show a similar result for degrees that are
high for descending sequences in Theorem 4.12.

###  4.1. Degrees that are high for descending sequences

######  Theorem 4.12.

If $X$ is not arithmetical, there is a degree that is high for tight
descending sequences and does not compute $X$.

###### Proof.

Let $\\{\mathcal{L}_{e}:e\in\omega\\}$ be a listing of the computable ill-
founded linear orders without arithmetic tight descending sequences. This
cannot be an effective listing, but its true complexity will not be relevant.

We construct our degree via forcing. Here, a condition is a pair
$(\sigma_{0},\sigma_{1})$ satisfying the following:

  * •

$\sigma_{0}:\omega^{2}\to\omega$ and
$\sigma_{1}:\omega\to\omega\times\\{0,1\\}$ are finite partial functions; and

  * •

If $\sigma_{1}(n)=(e,0)$, then $\tau=\lambda x.\sigma_{0}(n,x)$ is a finite
descending sequence in $\mathcal{L}_{e}$ that is extendible to an infinite
descending sequence.

A condition
$\overline{\sigma}^{\prime}=(\sigma_{0}^{\prime},\sigma_{1}^{\prime})$ extends
$\overline{\sigma}=(\sigma_{0},\sigma_{1})$ if the following hold:

  * •

$\sigma_{0}^{\prime}$ extends $\sigma_{0}$ and $\sigma_{1}^{\prime}$ extends
$\sigma_{1}$;

  * •

If $\sigma_{1}(n)=(m,1)$, then for $\tau=\lambda x.\sigma_{0}(n,x)$ and
$\tau^{\prime}=\lambda x.\sigma_{0}^{\prime}(n,x)$, we have
$\tau^{\prime}(x)=\emptyset^{(m)}(x)$ for all $x$ such that $|\tau|\leq
x<|\tau^{\prime}|$.

Given a filter $F$ for this notion of forcing, we let
$f=\bigcup\limits_{(\sigma_{0},\sigma_{1})\in F}\sigma_{0}$. If $F$ is
sufficiently generic, then for every $m$ there is an $n$ and a
$(\sigma_{0},\sigma_{1})\in F$ with $\sigma_{1}(n)=(m,1)$, and for this $n$,
$\lambda x.f(n,x)=^{*}\emptyset^{(m)}$. Thus, $f$ will bound every arithmetic
set. Furthermore, if $F$ is sufficiently generic, then for every $e$ there is
an $n$ and a $(\sigma_{0},\sigma_{1})\in F$ with $\sigma_{1}(n)=(e,0)$. For
this $n$, $\lambda x.f(n,x)$ will be a tight descending sequence through
$\mathcal{L}_{e}$. It follows that $f$ is high for descending sequences.

Suppose we have a condition $\overline{\sigma}$ and a Turing functional
$\Phi$. We wish to argue that $\overline{\sigma}$ can be extended to force
$\Phi^{f}\neq X$. Let $m=\max\left\\{m^{\prime}:\exists n<|\sigma_{1}|\
\left[\sigma_{1}(n)=(m^{\prime},1)\right]\right\\}$. Let $E=\left\\{e:\exists
n<|\sigma_{1}|\ \left[\sigma_{1}(n)=(e,0)\right]\right\\}$. Then any
$\overline{\tau}$ extending $\overline{\sigma}$ is committed to writing sets
$=^{*}\emptyset^{(m^{\prime})}$ for some $m^{\prime}\leq m$ on some finitely
many columns of $\tau_{0}$ and to writing descending sequences through
$\mathcal{L}_{e}$ for $e\in E$ on other columns of $\tau_{0}$, but is
unconstrained on the remaining columns of $\tau_{0}$.

Let $n=|E|$. By Lemma 4.10, we may first extend the descending sequences coded
in $\sigma_{1}$ such that none of them can be extended to $\Delta^{0}_{n+m+1}$
descending sequences. Now, working relative to $\emptyset^{(m)}$, the main
argument in the proof of Theorem 4.5 shows that we can extend to such a
$\overline{\tau}$ (we are in the “no such $k$” case in the proof of that
theorem).

Thus for a sufficiently generic filter, $\Phi^{f}\neq X$, and the degree of
$f$ is our desired degree. ∎

This stands in contrast with the high for isomorphism degrees, which compute
all $\Delta^{1}_{1}$ sets (Proposition 2.7).

######  Corollary 4.13.

There is a degree which is high for tight descending sequences but not high
for isomorphism.

Of course, the above result is heavily nonuniform. We now turn our attention
to the uniform case, where we will show that we can separate the uniform and
non-uniform notions, but not merely by looking at computation of
hyperarithmetical degrees. Toward this end, we begin with the following
technical result.

######  Lemma 4.14.

Fix $(U_{n})_{n\in\omega}$ an effective listing of $\Sigma^{1}_{1}$ subsets of
$\omega$. A degree $\mathbf{d}$ is uniformly high for descending sequences if
and only if there is a $\mathbf{d}$-computable partial function
$f:\omega\to\omega$ such that if $U_{n}$ is nonempty, then
$f(n)\mskip-3.0mu\mskip-3.0mu\downarrow\geq\min U_{n}$.

###### Proof.

Suppose $\mathbf{d}$ is uniformly high for descending sequences. We construct
$f$ as follows. On input $n$, for each $m\in\omega$, we let $T_{m}$ be a
computable tree having a path if and only if $m\in U_{n}$. We take
$\mathcal{L}_{m}$ to be the Kleene-Brouwer ordering of $T_{m}$, so $U_{n}$ is
nonempty if and only if $\mathcal{L}=\mathcal{L}_{0}+\mathcal{L}_{1}+\dots$ is
ill founded. We ask $\mathbf{d}$ to provide us with a descending sequence in
$\mathcal{L}$ as in the definition of uniformly high for descending sequences.
If $\mathbf{d}$ produces an output, we define $f(n)=m$, where $m$ is such that
the first element of the putative descending sequence occurs in
$\mathcal{L}_{m}$.

If $U_{n}$ is truly nonempty, then $\mathbf{d}$ will produce output, and the
first element of this output will bound a descending sequence, and so some
$\mathcal{L}_{m^{\prime}}$ with $m^{\prime}\leq m$ will be ill founded and
thus $m^{\prime}\in U_{n}$.

Now suppose $\mathbf{d}$ computes such an $f$. Given an ill-founded linear
order $\mathcal{L}$, we construct a descending sequence as follows. First, we
fix $n_{0}$ such that $U_{n_{0}}=\mathcal{L}\setminus W(\mathcal{L})$. This is
nonempty by assumption, and so $f(n_{0})\mskip-3.0mu\mskip-3.0mu\downarrow$
with $\\{0,\dots,f(n_{0})\\}\cap U_{n_{0}}\neq\emptyset$. Let $a_{0}$ be the
$\mathcal{L}$-rightmost element of $\\{0,\dots,f(n_{0})\\}$; this gives us
$a_{0}\in U_{n_{0}}$.

Given $a_{i}\in U_{n_{0}}$, we fix $n_{i+1}$ such that $U_{n_{i+1}}=\\{x\in
U_{n_{0}}:x<_{\mathcal{L}}a_{i}\\}$. This is nonempty by assumption, so
$f(n_{i+1})\mskip-3.0mu\mskip-3.0mu\downarrow$ with
$\\{0,\dots,f(n_{i+1})\\}\cap U_{n_{i+1}}\neq\emptyset$. Let $a_{i+1}$ be the
$\mathcal{L}$-rightmost element amongst those $\\{0,\dots,f(n_{i+1})\\}$ which
are to the left of $a_{i}$; this gives us $a_{i+1}\in U_{n_{i+1}}$.

Now the sequence $(a_{i})_{i\in\omega}$ is a descending sequence in
$\mathcal{L}$ and is uniformly computable from $f$ and an index for
$\mathcal{L}$. ∎

######  Theorem 4.15.

If $\mathbf{d}$ is uniformly high for descending sequences and $\mathbf{b}$ is
PA over $\mathbf{d}$, then $\mathbf{b}$ is uniformly high for isomorphism.

###### Proof.

Fix a computable ill-founded tree $T$. We show how to uniformly prune $T$ to a
$\mathbf{d}$-computable, finitely branching tree (with a
$\mathbf{d}$-computable bound on the branches). Then, as $\mathbf{b}$ is PA
over $\mathbf{d}$, it will uniformly compute a path through said tree.

We fix $f$ as in Lemma 4.14 and proceed recursively. First, we define $n_{0}$
such that $U_{n_{0}}=\\{m\in\omega:\text{$\langle m\rangle$ is extendible in
$T$}\\}$. Given $n_{0},\dots,n_{k-1}$, we then define

$T_{k}=\\{\sigma\in 2^{k}:(\forall i<k)\,\sigma(i)\leq f(n_{i})\\}$

and, then, $n_{k}$ such that

$U_{n_{k}}=\\{m\in\omega:(\exists\sigma\in
T_{k})\,\text{$\sigma\widehat{\phantom{\alpha}}m$ is extendible in $T$}\\}.$

Inductively, using the properties of $f$, each $T_{k}$ contains a string
extendible in $T$. Then the tree $\\{\sigma\in T:(\forall
i<|\sigma|)\,\sigma(i)\leq f(n_{i})\\}$ is our pruned tree.∎

######  Corollary 4.16.

If $\mathbf{d}$ is uniformly high for descending sequences, then $\mathbf{d}$
computes every $\Delta^{1}_{1}$ set.

###### Proof.

Fix $X\in\Delta^{1}_{1}$, and suppose $\mathbf{d}$ does not compute $X$ for a
contradiction. By the cone avoidance basis theorem [17], there is a
$\mathbf{b}$ that is PA over $\mathbf{d}$ which does not compute $X$. But then
$\mathbf{b}$ is uniformly high for isomorphism, contradicting Proposition 2.7.
∎

Thus, we cannot separate uniform highness for descending sequences from
highness for isomorphism simply by looking at the sorts of degrees they
compute as we did for the nonuniform case. Nevertheless, they are separate
classes of degrees. The remainder of this section is devoted to separating
these classes, though we will need to develop a number of tools first.

###  4.2. Computing jump hierarchies

Given a computable linear order $\mathcal{L}$, a _jump hierarchy_ on
$\mathcal{L}$ is a function $h:\mathcal{L}\to 2^{\omega}$ such that for all
$x\in\mathcal{L}$, $h(x)=\bigoplus_{y<_{\mathcal{L}}x}h(y)^{\prime}$. For
every computable well order, of course, an initial segment of the standard
hyperarithmetical hierarchy constitutes a jump hierarchy [23]. There are,
however, linear orders which do not admit a jump hierarchy, and this property
is not invariant under isomorphism. In particular, there are Harrison orders
with jump hierarchies and those without.

The terminology for jump hierarchies varies in the literature. A jump
hierarchy is sometimes called a _jump structure_ or a _Turing jump hierarchy_.

In any case, computing a jump hierarchy on a long linear order is a strong
standard for a degree. For instance, no hyperarithmetical degree can compute a
jump hierarchy on any Harrison order. This gives rise to the following
definition.

######  Definition 4.17.

We say that a degree $\mathbf{d}$ is _jump complete_ if and only if there is
an algorithm which, given an index for a computable Harrison order which
admits a jump hierarchy, will compute such a hierarchy from oracle
$\mathbf{d}$.

######  Proposition 4.18.

Every degree which is uniformly high for isomorphism is jump complete.

###### Proof.

Given a Harrison order $\mathcal{H}$, the set of jump hierarchies on
$\mathcal{H}$ is a $\Sigma^{1}_{1}$ class. A degree that is uniformly high for
isomorphism can compute an element of such a class as long as it is nonempty.
∎

######  Proposition 4.19.

There is a degree that is Scott complete but not jump complete.

###### Proof.

By Proposition 3.3, there is a degree that is Scott complete and low for
$\omega_{1}^{ck}$. On the other hand, Harrington (unpublished; see [18])
showed that the set of computable linear orders admitting jump hierarchies is
$\Sigma^{1}_{1}$-complete, and so the same argument as in Proposition 2.8(2)
shows that if $\mathbf{d}$ is jump complete, then
$\mathbf{d}^{\prime\prime}\geq_{T}\mathcal{O}$. ∎

Jump hierarchies are interesting in their own right, but they will also be an
important tool to separating uniform highness for descending sequences from
highness for isomorphism. In particular, in Corollary 4.47 we will construct a
degree $\mathbf{d}$ which is uniformly high for descending sequences and a
linear order $\mathcal{L}$ admitting jump hierarchies, and such that
$\mathbf{d}$ does not compute any jump hierarchy on $\mathcal{L}$. This gives
the following.

######  Proposition 4.20.

There is a degree that is uniformly high for descending sequences but not jump
complete.

###  4.3. $\Pi^{1}_{1}$-tracing of majorized classes

We continue developing the tools necessary for our intended separation result.
Here, we consider traceability.

######  Definition 4.21.

For $\sigma,\tau\in\omega^{\leq\omega}$, we say that $\sigma$ majorizes $\tau$
if for every $x\in\text{dom}(\sigma)\cap\text{dom}(\tau)$,
$\sigma(x)\geq\tau(x)$.

The following is an effectivization of results surrounding Laver forcing in
set theory (see Bartoszynski [2] §7.3.D).

######  Definition 4.22.

An order is a nondecreasing function $h:\omega\to\omega$ such that $h(0)>0$
and $\lim_{s}h(s)=\infty$.

For $h$ an order and $f\in\omega^{\omega}$, an $h$-trace of $f$ is a sequence
$(V_{n})_{n\in\omega}$ such that for all $n$, $|V_{n}|\leq h(n)$ and
$f\mskip-3.0mu\mskip-3.0mu\upharpoonright{n}\in V_{n}$.

An $h$-trace $(V_{n})_{n\in\omega}$ is $\Pi^{1}_{1}$ if the $V_{n}$s are
uniformly $\Pi^{1}_{1}$.

Our goal is the following:

######  Lemma 4.23.

If $\mathcal{P}\subset\omega^{\omega}$ has compact closure, $\Phi$ is a Turing
functional, and $f\in\omega^{\omega}$ is such that for every $g$ majorizing
$f$, $\Phi^{g}\in\mathcal{P}$, then for every computable order $h$, there is
an element of $\mathcal{P}$ with a $\Pi^{1}_{1}$ $h$-trace.

The proof of this lemma will require a number of ingredients. We begin with
the following definitions.

######  Definition 4.24.

  1. (1)

A Laver tree with stem $\tau$ is a tree $T\subseteq\omega^{<\omega}$ with
$\tau\in T$ such that for every $\sigma\in T$ with $\sigma\not\subset\tau$,
there are infinitely many $n\in\omega$ with
$\sigma\widehat{\phantom{\alpha}}n\in T$.

  2. (2)

A stemless Laver tree is a Laver tree with stem $\langle\rangle$.

  3. (3)

A set $A\subseteq T$ covers $T$ if every path through $T$ meets an element of
$A$.

######  Notation 4.25.

If $T$ is a Laver tree with stem $\tau$ and $\sigma\supseteq\tau$ is on $T$,
then

$T^{\sigma}=\\{\rho\in
T:\rho\supseteq\sigma\\}\cup\\{\rho:\rho\subseteq\sigma\\}.$

Observe that $T^{\sigma}$ is a Laver tree with stem $\sigma$, and also that if
$T$ is a stemless Laver tree, then for every $f\in\omega^{\omega}$ there is a
$g\in[T]$ majorizing $f$. Our intention is to build a $\Pi^{1}_{1}$ sequence
$(V_{n})_{n\in\omega}$ and a stemless Laver tree $T$ such that for every
$g\in[T]$ with $\Phi^{g}$ total, $(V_{n})_{n\in\omega}$ is an $h$-trace for
$\Phi^{g}$.

######  Definition 4.26.

Suppose $T$ is a Laver tree with stem $\tau$ and $A\subseteq T$ is upwards
closed in $T$. Let $\mathcal{L}$ be a linear order with distinguished least
and greatest elements, respectively 0 and $\infty$, and a successor function
$+1$ (with $\infty+1=\infty$). An $(A,\mathcal{L},T)$ Laver ranking is a
function $r:\\{\sigma\in T:\tau\subseteq\sigma\\}\to\mathcal{L}$ satisfying
the following:

  * •

$r(\sigma)=0$ if and only if $\sigma\in A$; and

  * •

For $\sigma\not\in A$,
$r(\sigma)=\liminf_{\sigma\widehat{\phantom{\alpha}}n\in
T}[r(\sigma\widehat{\phantom{\alpha}}n)+1]$.

Observe that for $\mathcal{L}$ countable, the collection $LR(A,\mathcal{L},T)$
of $(A,\mathcal{L},T)$ Laver rankings is an arithmetic class relative to
$A,\mathcal{L}$ and $T$.

######  Lemma 4.27.

For any Laver tree $T$ with stem $\tau$ and $A\subseteq T$ upwards closed, an
$(A,\omega_{1}\cup\\{\infty\\},T)$ Laver ranking exists.

###### Proof.

We construct an increasing sequence of partial functions
$(r_{\alpha})_{\alpha<\omega_{1}}$. We begin by defining $r_{0}(\sigma)=0$ for
$\sigma\in A$ and $r_{0}(\sigma)\mskip-3.0mu\mskip-3.0mu\uparrow$ for
$\sigma\not\in A$.

Having defined $r_{\beta}$ for $\beta<\alpha$, we let
$r_{<\alpha}=\bigcup_{\beta<\alpha}r_{\beta}$. If
$r_{<\alpha}(\sigma)\mskip-3.0mu\mskip-3.0mu\downarrow$, then we define
$r_{\alpha}(\sigma)=r_{<\alpha}(\sigma)$. If
$r_{<\alpha}(\sigma)\mskip-3.0mu\mskip-3.0mu\uparrow$ but there are infinitely
many $n$ such that $\sigma\widehat{\phantom{\alpha}}n\in T$ and
$r_{<\alpha}(\sigma\widehat{\phantom{\alpha}}n)\mskip-3.0mu\mskip-3.0mu\downarrow$,
then we define $r_{\alpha}(\sigma)=\alpha$. Otherwise, we leave
$r_{\alpha}(\sigma)$ undefined.

By cardinality considerations, there is $\lambda<\omega_{1}$ such that
$r_{\lambda}=r_{\lambda+1}$. We define $r(\sigma)=r_{\lambda}(\sigma)$ for
$\sigma\in\text{dom}(r_{\lambda})$ and $r(\sigma)=\infty$ for
$\sigma\not\in\text{dom}(r_{\lambda})$.

Clearly $r$ is as required. ∎

Let $\dot{r}_{A,T}$ be the $(A,\omega_{1}\cup\\{\infty\\},T)$ Laver ranking
just constructed. Lemmas 4.34 and 4.35 will imply that it is unique. Observe
that for sufficiently large countable $\lambda$, $\dot{r}_{A,T}$ is an
$(A,\lambda\cup\\{\infty\\},T)$ Laver ranking as well. This Laver ranking
tells us about the existence of Laver trees.

######  Definition 4.28.

For $T$ a Laver tree with stem $\tau$ and $A\subseteq T$ upwards closed,
define $T_{A}$ recursively:

  * •

If $\sigma\subseteq\tau$, then $\sigma\in T_{A}$;

  * •

If $\sigma\in T_{A}$ with $\sigma\supseteq\tau$ and
$\sigma\widehat{\phantom{\alpha}}n\in T$ with
$\dot{r}_{A,T}(\sigma\widehat{\phantom{\alpha}}n)<\dot{r}_{A,T}(\sigma)<\infty$,
then $\sigma\widehat{\phantom{\alpha}}n\in T_{A}$;

  * •

If $\sigma\in T_{A}$ with $\sigma\supseteq\tau$ and $\sigma\in A$, then for
every $\sigma\widehat{\phantom{\alpha}}n\in T$,
$\sigma\widehat{\phantom{\alpha}}n\in T_{A}$; and

  * •

If $\sigma\in T_{A}$ with $\sigma\supseteq\tau$ and
$\sigma\widehat{\phantom{\alpha}}n\in T$ with
$\dot{r}_{A,T}(\sigma\widehat{\phantom{\alpha}}n)=\dot{r}_{A,T}(\sigma)=\infty$,
then $\sigma\widehat{\phantom{\alpha}}n\in T_{A}$.

We now present some basic facts about these $T_{A}$s.

######  Lemma 4.29.

If $T$ is a Laver tree with stem $\tau$ and $\dot{r}_{A,T}(\tau)=\infty$, then
$T_{A}$ is a Laver tree and no element of $[T_{A}]$ meets $A$.

If $T$ is a Laver tree with stem $\tau$ and $\dot{r}_{A,T}(\tau)<\infty$, then
$T_{A}$ is a Laver tree covered by $A\cap T_{A}$.

In either case, for all $\sigma\in T_{A}$ with $\sigma\supseteq\tau$,
$\dot{r}_{A,T}(\sigma)=\dot{r}_{A,T_{A}}(\sigma)$.

###### Proof.

Suppose $\dot{r}_{A,T}(\tau)=\infty$. By induction on $|\sigma|$, if
$\tau\subseteq\sigma\in T_{A}$, then $\dot{r}_{A,T}(\sigma)=\infty$. As
$T_{A}\cap A=\emptyset$, all $\sigma\supseteq\tau$ on $T_{A}$ have
$\dot{r}_{A,T_{A}}(\sigma)=\infty$.

Now suppose $\dot{r}_{A,T}(\tau)<\infty$. Then for any $g\in[T_{A}]$,
$\dot{r}_{A,T}$ is decreasing along $g$ after $\tau$ until it reaches $0$. For
$\sigma\in T_{A}$ with $\sigma\supseteq\tau$, by induction on
$\dot{r}_{A,T}(\sigma)$, $\dot{r}_{A,T}(\sigma)=\dot{r}_{A,T_{A}}(\sigma)$. ∎

######  Lemma 4.30.

For any $A\subseteq T$, $\text{range}\,(\dot{r}_{A,T})\setminus\\{\infty\\}$
is closed downwards.

###### Proof.

Fix $\beta\leq\alpha$ and $\sigma$ with $\dot{r}_{A,T}(\sigma)=\alpha$. We
must show that there is a $\tau$ with $\dot{r}_{A,T}(\tau)=\beta$. We
construct a sequence $\sigma=\sigma_{0}\subset\sigma_{1}\subset\dots$ with
$\beta\leq\dot{r}_{A,T}(\sigma_{i+1})<\dot{r}_{A,T}(\sigma_{i})$.

Suppose we have defined $\sigma_{i}$. If $\dot{r}_{A,T}(\sigma_{i})=\beta$, we
are done. Otherwise, there is an $n$ with
$\beta\leq\dot{r}_{A,T}(\sigma_{i}\widehat{\phantom{\alpha}}n)<\dot{r}_{A,T}(\sigma_{i})$.
Define $\sigma_{i+1}=\sigma_{i}\widehat{\phantom{\alpha}}n$ for such an $n$.

By the well-foundedness of the ordinals, this sequence must terminate in a
$\sigma_{i}$ with $\dot{r}_{A,T}(\sigma_{i})=\beta$. ∎

We will sometimes abuse notation by writing $\dot{r}_{A,T}$ when
$A\not\subseteq T$, in which case this should be understood as $\dot{r}_{A\cap
T,T}$. This will not be a problem because of the following two lemmas.

######  Lemma 4.31.

Let $T$ be a Laver tree with stem $\tau$, and let $A\subseteq B\subseteq T$.
Then for all $\sigma\supseteq\tau$ with $\sigma\in T$,
$\dot{r}_{B,T}(\sigma)\leq\dot{r}_{A,T}(\sigma)$.

###### Proof.

This follows by induction on $\dot{r}_{A,T}(\sigma)$. ∎

######  Lemma 4.32.

Let $T_{0}\subseteq T_{1}$ be Laver trees with a common stem $\tau$, and let
$A\subseteq T_{1}$. Then for all $\sigma\supseteq\tau$ with $\sigma\in T_{0}$,
$\dot{r}_{A,T_{1}}(\sigma)\leq\dot{r}_{A,T_{0}}(\sigma)$.

###### Proof.

This follows by induction on $\dot{r}_{A,T_{0}}(\sigma)$. ∎

We would like to construct our trace $(V_{n})_{n\in\omega}$ using
$\dot{r}_{A,T}$ for various $A$ and $T$, but we lack an effective way to
directly reason about $\dot{r}_{A,T}$. We will show, however, that it suffices
to reason about $(A,\mathcal{L},T)$ Laver rankings, where $\mathcal{L}$ is a
Harrison order.

For $\mathcal{L}$ an ill-founded linear order, it may be that no
$(A,\mathcal{L},T)$ Laver ranking exists (in particular, the $\liminf$
required by the definition may not exist). We can put various conditions on
what such a ranking will look like when it does exist, though.

######  Notation 4.33.

For a linear order $\mathcal{L}$ with least and greatest elements $0$ and
$\infty$, respectively, let $W(\mathcal{L})$ be the maximal well-founded
initial segment of $\mathcal{L}\setminus\\{\infty\\}$. We identify
$W(\mathcal{L})$ with an initial segment of the ordinals in the standard
fashion (such identification being unique), writing, for example,
$r(\sigma)=\alpha$ when $r(\sigma)\in W(\mathcal{L})$ and
$[0,r(\sigma))_{\mathcal{L}}$ has order type $\alpha$.

######  Lemma 4.34.

For $r$ an $(A,\mathcal{L},T)$ Laver ranking, there is no $\sigma$ such that
$r(\sigma)\in W(\mathcal{L})$ with $r(\sigma)<\dot{r}_{A,T}(\sigma)$.

###### Proof.

Suppose not. We construct a sequence of strings
$\sigma=\sigma_{0}\subset\sigma_{1}\subset\dots$ with
$r(\sigma_{i+1})<r(\sigma_{i})$ for a contradiction, maintaining the inductive
assumption that $r(\sigma_{i})<\dot{r}_{A,T}(\sigma_{i})$. Clearly this holds
for $i=0$.

Suppose we have defined $\sigma_{i}$. As
$\dot{r}_{A,T}(\sigma_{i})>r(\sigma_{i})$, it is clear that
$\dot{r}_{A,T}(\sigma_{i})\neq 0$, and thus $\sigma_{i}\not\in A$. As
$r(\sigma_{i})<\infty$, there are infinitely many $n$ such that
$r(\sigma_{i}\widehat{\phantom{\alpha}}n)<r(\sigma_{i})$, whereas for almost
every $n$, $\dot{r}_{A,T}(\sigma_{i}\widehat{\phantom{\alpha}}n)\geq
r(\sigma_{i})$. We can therefore define
$\sigma_{i+1}=\sigma_{i}\widehat{\phantom{\alpha}}n$ for an $n$ satisfying
both of these. ∎

Note that this implies that if $\dot{r}_{A,T}(\sigma)=\infty$, then
$r(\sigma)\not\in W(\mathcal{L})$.

######  Lemma 4.35.

For $r$ an $(A,\mathcal{L},T)$ Laver ranking, if
$\dot{r}_{A,T}(\sigma)<\infty$, then $r(\sigma)\in W(\mathcal{L})$ and
$r(\sigma)=\dot{r}_{A,T}(\sigma)$.

###### Proof.

We show by induction on $\dot{r}_{A,T}(\sigma)$ that $r(\sigma)\in
W(\mathcal{L})$ with $r(\sigma)\leq\dot{r}_{A,T}(\sigma)$. For
$\dot{r}_{A,T}(\sigma)=0$, this is immediate.

For $0<\dot{r}_{A,T}(\sigma)<\infty$, there are infinitely many $n$ with
$\dot{r}_{A,T}(\sigma\widehat{\phantom{\alpha}}n)<\dot{r}_{A,T}(\sigma)$. By
the inductive hypothesis, $r(\sigma\widehat{\phantom{\alpha}}n)\in
W(\mathcal{L})$ with
$r(\sigma\widehat{\phantom{\alpha}}n)\leq\dot{r}_{A,T}(\sigma\widehat{\phantom{\alpha}}n)<\dot{r}_{A,T}(\sigma)$.
Thus these $\sigma\widehat{\phantom{\alpha}}n$ witness that $r(\sigma)\in
W(\mathcal{L})$ with $r(\sigma)\leq\dot{r}_{A,T}(\sigma)$.

The result then follows by Lemma 4.34. ∎

######  Lemma 4.36.

If $A$ and $T$ are hyperarithmetic, then for every $\sigma$ with
$\dot{r}_{A,T}(\sigma)<\infty$, $\dot{r}_{A,T}(\sigma)<\omega_{1}^{ck}$.

###### Proof.

Suppose not. We know that for some countable $\lambda$, $\dot{r}_{A,T}$ is an
$(A,\lambda\cup\\{\infty\\},T)$ Laver ranking with
$\dot{r}_{A,T}(\sigma)\geq\omega_{1}^{ck}$. By Lemma 4.35, for any
$(A,\mathcal{L},T)$ Laver ranking $r$, we have that $r(\sigma)\in
W(\mathcal{L})$. Thus a computable linear order $\mathcal{K}$ is well founded
if and only if there exists a countable linear order $\mathcal{L}$, an
$(A,\mathcal{L},T)$ Laver ranking $r$, and an embedding
$\mathcal{K}\hookrightarrow[0,r(\sigma))_{\mathcal{L}}$. However, this is a
$\Sigma^{1}_{1}$ definition of well-foundedness. ∎

######  Lemma 4.37.

If $\mathcal{H}$ has order type $\omega_{1}^{ck}(1+\mathbb{Q})+1$ with least
and greatest elements $0$ and $\infty$, respectively, then for any
hyperarithmetic $A$ and $T$, there is an $(A,\mathcal{H},T)$ Laver ranking.

###### Proof.

We can identify $W(\mathcal{H})$ with $\omega_{1}^{ck}$ and see that
$\dot{r}_{A,T}$ is an $(A,\mathcal{H},T)$ Laver ranking. ∎

Letting a computable $\mathcal{H}$ be as in Lemma 4.37 and continuing the
identification of $W(\mathcal{H})$ with $\omega_{1}^{ck}$, we observe that for
hyperarithmetic $A$ and $T$, the relation
$\\{(\sigma,\alpha):\dot{r}_{A,T}(\sigma)=\alpha\\}$ has a $\Pi^{1}_{1}$
definition:

$\dot{r}_{A,T}(\sigma)=\alpha\iff\forall r\in
LR(A,\mathcal{H},T)\,[r(\sigma)=\alpha].$

Moreover, for each $\beta<\omega_{1}^{ck}$,
$\\{(\sigma,\alpha):\alpha<\beta\wedge\dot{r}_{A,T}(\sigma)=\alpha\\}$ is
$(A\oplus T)^{(2\beta+3)}$-computable, and in fact uniformly so. We can
observe that if $\sigma\in T$ is such that
$\dot{r}_{A,T}(\sigma)=\alpha<\infty$, then $(T^{\sigma})_{A}$ is
hyperarithmetic relative to $A$ and $T$ and uniformly so given $\alpha$.

We are now ready to prove Lemma 4.23.

###### Proof of Lemma 4.23.

Without loss of generality, we define $h(n)=n+1$. (We are working in Baire
space and thus can compress via pairing without affecting the compactness of
the closure.) Fix $(\tau_{n})_{n\in\omega}$ an effective listing of
$\omega^{<\omega}$ such that $\tau_{i}\subset\tau_{j}$ implies $i<j$, and thus
$\tau_{0}$ is the empty string $\langle\rangle$. Assume this listing has the
property that for all $\tau$ and $b$, $\tau\widehat{\phantom{\alpha}}b$ occurs
earlier in the listing than $\tau\widehat{\phantom{\alpha}}(b+1)$.

We perform a construction of length $\omega_{1}^{ck}$, enumerating partial
functions $k:\omega^{<\omega}\to\omega^{<\omega}$ and
$\ell_{m}:(m+1)\to\omega^{m}$ for $m\in\omega$. We will also define
hyperarithmetic trees $T_{n,m}$ for some $n\leq m$. We adopt the notation
$A_{\rho}=\\{\sigma:\rho\subseteq\Phi^{\sigma}\\}$, and for $n>0$,
$\tau^{-}_{n}$ is the parent of $\tau_{n}$.

We will ensure the following properties hold:

  * •

$k$ is injective, order preserving and length preserving, and its domain is
downwards closed. Furthermore, for any $\tau$ such that $k(\tau)$ is defined,
$k(\tau)$ majorizes $\tau$.

  * •

If $\tau_{n}$ majorizes $f$, then $k(\tau_{n})$ is defined, as are
$\ell_{m}(n)$ for all $m\geq n$.

  * •

For $n\leq m$, $\ell_{m}(n)\mskip-3.0mu\mskip-3.0mu\downarrow$ if and only if
$T_{n,m}$ is defined.

  * •

For $n\leq m$, if $\ell_{m}(n)\mskip-3.0mu\mskip-3.0mu\downarrow$, then
$\dot{r}_{A,T}(k(\tau_{n}))<\infty$ for $T=T_{n,m}$ and $A=A_{\ell_{m}(n)}$.

  * •

For every $n\leq m$ such that $T_{n,m}$ is defined, $T_{n,m}$ is a Laver tree
with stem $k(\tau_{n})$.

  * •

If $T_{n,m}$ is defined for $n<m$, then $T_{n,m-1}$ is defined and
$T_{n,m}=(T_{n,m-1})_{A}$ for $A=A_{\ell_{m}(n)}$.

  * •

For any $n>0$, suppose that $\tau_{j}=\tau_{n}^{-}$. If
$k(\tau_{n})\mskip-3.0mu\mskip-3.0mu\downarrow$, then $T_{j,n-1}$ is defined
and $k(\tau_{n})\in T_{j,n-1}$. If $T_{n,n}$ is defined, then
$T_{n,n}=\left(T_{j,n-1}^{k(\tau_{n})}\right)_{A}$ for $A=A_{\ell_{n}(n)}$.

This essentially describes the construction. We begin with
$k(\langle\rangle)=\langle\rangle$, $\ell_{0}(0)=\langle\rangle$, and
$T_{0,0}=\omega^{<\omega}$.

For $n>0$, let $\tau_{j}=\tau_{n}^{-}$. We wait to see if $k(\tau_{j})$ and
$T_{j,n-1}$ are ever defined. If this happens, we then define $k(\tau_{n})$ to
be the $n$th child of $k(\tau_{j})$ on $T_{j,n-1}$.

For $n\leq m$ with $m>0$, if $m=n$, we then let $\tau_{j}=\tau_{n}^{-}$ and
let $T=T_{j,n-1}^{k(\tau_{n})}$; if $m>n$, we let $T=T_{n,m-1}$ (including
when $n=0$). We wait until $T$ is defined and then search for
$\rho\in\omega^{m}$ such that $\dot{r}_{A,T}(k(\tau))<\infty$ for
$A=A_{\rho}$; if we see such a $\rho$, we define $\ell_{m}(n)=\rho$ and
$T_{n,m}=T_{A}$ for $A=A_{\rho}$.

Most of the stated properties of the construction are immediate.

######  Claim 4.38.

For $m\leq n$, if $\ell_{m}(n)\mskip-3.0mu\mskip-3.0mu\downarrow$, then
$\dot{r}_{A,T}(k(\tau_{n}))<\infty$ for $T=T_{n,m}$ and $A=A_{\ell_{m}(n)}$.

###### Proof.

This is immediate from the construction except in the case $m=n=0$. We handle
this case by observing that
$A_{\ell_{0}(0)}=A_{\langle\rangle}=\omega^{<\omega}$, and so
$\dot{r}_{A,T}(k(\tau_{0}))=0$. ∎

######  Claim 4.39.

$k$ is injective, and if $k(\tau)$ is defined, then $k(\tau)$ majorizes
$\tau$.

###### Proof.

This follows by induction on $|\tau|$. The case $\tau=\langle\rangle$ is
immediate.

Suppose $k(\tau_{j})$ is defined, and let
$\tau_{n}=\tau_{j}\widehat{\phantom{\alpha}}b$. Note that $n>b$. Then, if
$k(\tau_{n})$ is defined, it is the $n$th child of $k(\tau_{j})$ on
$T_{j,n-1}$, so $k(\tau_{n})=k(\tau_{j})\widehat{\phantom{\alpha}}c$ for some
$c\geq n>b$. By induction, $k(\tau_{n})$ majorizes $\tau_{n}$.

Now suppose $\tau_{n^{\prime}}=\tau_{j}\widehat{\phantom{\alpha}}b^{\prime}$
is another child of $\tau_{j}$ such that $n^{\prime}>n$ and thus
$b^{\prime}>b$. If $k(\tau_{n^{\prime}})$ is defined, it is the $n^{\prime}$th
child of $k(\tau_{j})$ on $T_{j,n^{\prime}-1}\subseteq T_{j,n-1}$, and thus it
is the $(\geq n^{\prime})$th child of $\tau_{j}$ on $T_{j,n-1}$. It follows
that $k(\tau_{n^{\prime}})\neq k(\tau_{n})$. By induction, $k$ is injective. ∎

######  Claim 4.40.

If $\tau_{n}$ majorizes $f$, then $k(\tau_{n})$ is defined, as is
$\ell_{m}(n)$ for all $m\geq n$.

###### Proof.

This follows by induction on $|\tau_{n}|$. Note that $k(\tau_{0})$ and
$\ell_{0}(0)$ are explicitly defined at the start of the construction.

For $n>0$ with $\tau_{n}$ majorizing $f$, let $\tau_{j}=\tau_{n}^{-}$. By
induction, $k(\tau_{j})$ and $T_{j,n-1}$ are eventually defined, so
$k(\tau_{n})$ is defined.

Now, we do a subinduction on $m\geq n$ (if $n=0$, we restrict ourselves to
$m>n$). Let $T$ be as given in the definition of $\ell_{m}(n)$. By induction,
$T$ is eventually defined. Let $\pi=\ell_{m-1}(n)$ if $m>n$ and
$\pi=\ell_{j}(n-1)$ if $m=n$. Note that $[T]$ is covered by $A_{\pi}$ by
construction.

As $\mathcal{P}$ has compact closure, there are only finitely many $y$ with
$[\pi\widehat{\phantom{\alpha}}y]\cap\mathcal{P}\neq\emptyset$. We list these
as $y_{0},y_{1},\dots,y_{s-1}$. Let
$A_{i}=A_{\pi\widehat{\phantom{\alpha}}y_{i}}$ and, towards a contradiction,
suppose $\dot{r}_{A_{i},T}(k(\tau_{n}))=\infty$ for every $i<s$. Now we define
a sequence of Laver trees $T=Q_{0}\supseteq Q_{1}\supseteq\dots\supseteq
Q_{s}$ by $Q_{i+1}=(Q_{i})_{A_{i}}$. By Lemmas 4.31 and 4.32,
$\dot{r}_{A_{i},Q_{i}}(k(\tau_{n}))=\infty$ for all $i<s$, and thus $[Q_{s}]$
is disjoint from $A_{i}$ for all $i<s$. However, $\tau_{n}$ majorizes $f$ and
$k(\tau_{n})$ majorizes $\tau_{n}$, so $k(\tau_{n})$ can be extended to a
$g\in[Q_{s}]$ majorizing $f$. Then $\Phi^{g}\in\mathcal{P}$ by assumption and
$g\in[T]$, so $g$ meets $A_{\pi}$ and thus $\pi\subset\Phi^{g}$. But $g$
avoids all $A_{i}$, and thus
$\pi\widehat{\phantom{\alpha}}y_{i}\not\subset\Phi^{g}$ for any $i<s$, giving
us a contradiction.

Thus there is some $y_{i}$ such that $\dot{r}_{A_{i},T}(k(\tau_{n}))<\infty$,
and so $\rho=\pi\widehat{\phantom{\alpha}}y_{i}$ is as desired for the
definition of $\ell_{m}(n)$. ∎

Thus our construction has the stated properties. Now we define

$V_{m}=\\{\ell_{m}(n):n\leq m\\}.$

These are uniformly $\Pi^{1}_{1}$ and of the correct size. We can also define

$T=\\{k(\tau):\text{$\tau$ majorizes $f$}\\}$

and observe that $T$ is a stemless Laver tree.

######  Claim 4.41.

For every $g\in[T]$, $(V_{m})_{m\in\omega}$ is an $h$-trace of $\Phi^{g}$.

###### Proof.

Fix $n\leq m$ largest with $\tau_{n}\subset g$, and let $\rho=\ell_{m}(n)$.
Then, by construction, $g\in[T_{n,m}]$ and thus $g$ meets $A_{\rho}$. This
guarantees that $\Phi^{g}\mskip-3.0mu\mskip-3.0mu\upharpoonright{m}=\rho\in
V_{m}$. ∎

This completes the proof of Lemma 4.23. ∎

###  4.4. A class without $\Pi^{1}_{1}$ traces

At this point, we can finally complete the separation of uniform highness for
descending sequences and highness for isomorphism. Suppose $\mathcal{H}$ is a
Harrison order and $(X_{a})_{a\in\mathcal{H}}$ is a jump structure on
$\mathcal{H}$. We wish to show that there is no $\Pi^{1}_{1}$ $h$-trace for
$(X_{a})_{a\in\mathcal{H}}$ for an appropriately chosen computable order $h$,
not depending on $(X_{a})_{a\in\mathcal{H}}$.

######  Lemma 4.42.

Suppose $V$ is a finite set with $|V|\leq n$. Then there are sets
$(U_{a})_{a\in H}$ satisfying:

  * •

For all $a$, $|U_{a}|\leq n$;

  * •

For all $a<b$, $U_{a}\subseteq U_{b}$;

  * •

$V=\bigcup_{a\in W(\mathcal{H})}U_{a}$; and

  * •

Each $U_{a}$ is enumerable from $X_{a}$ uniformly in $a$, $n$, and a
$\Pi^{1}_{1}$ index for $V$.

###### Proof.

We fix uniformly computable trees $T_{i}\subseteq\omega^{<\omega}$ such that
$T_{i}$ is well founded if and only if $i\in V$. Define $R(i,a)$ to be the
relation “$X_{a}$ computes a tree-rank function from $T_{i}$ to
$\mathcal{H}_{<a}$” (a standard tree-rank function, not a Laver ranking). Note
that $\\{i:R(i,a)\\}$ is uniformly $\Sigma^{0}_{3}(X_{a})$ and that $i\in V$
if and only if there is some $a\in W(\mathcal{H})$ satisfying $R(i,a)$.

Now we define

$W_{a}=\left\\{i:R(i,a)\wedge\neg\exists
j_{0}<\dots<j_{n-1}\bigwedge_{s<n}[(j_{s}<i\wedge R(j_{s},a))\vee(\exists
b<a)R(j_{s},b)]\right\\}.$

Define $\widehat{W}_{a}=\bigcup_{b\leq a}W_{b}$. We claim that
$(\widehat{W}_{a})_{a\in\mathcal{H}}$ is as desired except for not being
uniformly enumerable from $X_{a}$.

First, towards a contradiction, we fix some $a$ with $|\widehat{W}_{a}|>n$ and
then fix distinct $i_{0},\dots,i_{n}\in\widehat{W}_{a}$. For each $s\leq n$,
we fix $b_{s}\leq a$ with $i_{s}\in W_{b_{s}}$ and let $b=\max\\{b_{s}:s\leq
n\\}$. Now we let $i=\max(W_{b}\cap\\{i_{0},\dots,i_{n}\\})$ and derive a
contradiction from $i\in W_{b}$.

Clearly, for $a\in W(\mathcal{H})$, we have that $W_{a}\subseteq V$. For $i\in
V$, let $a$ be least such that $R(i,a)$ holds. Then
$\bigcup_{b<a}W_{b}\subseteq V\setminus\\{i\\}$, and so
$|\bigcup_{b<a}W_{b}|<n$. This gives us that $i\in W_{a}$, and it follows that
$V=\bigcup_{a\in W(H)}\widehat{W}_{a}$.

Now we observe that $\widehat{W}_{a}$ is $\Sigma^{0}_{4}(X_{a})$ uniformly in
$a$, $n$, and a $\Pi^{1}_{1}$ index for $V$, so we define

$U_{a}=\bigcup_{b+3\leq a}\widehat{W}_{b}.\qed$

######  Proposition 4.43.

Let $\mathcal{H}$ be a Harrison order. There is a computable order $h$ such
that no jump structure on $\mathcal{H}$ has a $\Pi^{1}_{1}$ $h$-trace.

###### Proof.

We fix some $b+1\in\mathcal{H}\setminus W(\mathcal{H})$ nonuniformly and let
$J^{Z}(e)=\Phi^{Z}_{e}(e)$ for all $e\in\omega$ and $Z\in 2^{\omega}$. By the
recursion theorem, there is an injective computable sequence $e_{i,j}$ for
$i\in\omega$ and $j\leq i$ such that we control the behavior of each
$J(e_{i,j})$. We let $r_{i}=\max\\{\langle b+1,e_{i,j}\rangle+1:j\leq i\\}$
and define a computable order $h$ such that $h(r_{i})\leq i+1$ for all $i$.

Now we let $((V_{m}^{i})_{m\in\omega})_{i\in\omega}$ be a uniform listing of
all $\Pi^{1}_{1}$ $h$-traces. We let $(U_{a}^{i})_{a\in H}$ be as in Lemma
4.42 for $V=V_{r_{i}}^{i}$ and $n=h(r_{i})$ and define $J^{Z}(e_{i,j})$ as
follows: we first attempt to enumerate $U_{b}^{i}$, working under the
assumption that $Z=X_{b}$; and, letting $\sigma_{0},\sigma_{1},\dots$ be the
elements we enumerate in order of enumeration, we define
$J^{Z}(e_{i,j})\mskip-3.0mu\mskip-3.0mu\downarrow$ if and only if $\sigma_{j}$
exists and $\sigma_{j}(e_{i,j})=0$.

Now we suppose $(X_{a})_{a\in\mathcal{H}}$ is a jump structure on
$\mathcal{H}$. Towards a contradiction, we further suppose
$(V_{n}^{i})_{n\in\omega}$ traces $X=\\{\langle a,x\rangle:x\in X_{a}\\}$, and
we fix $\sigma\in V_{r_{i}}^{i}$ an initial segment of $X$. Then
$V_{r_{i}}^{i}\subseteq U_{b}^{i}$ and $U_{b}^{i}$ is enumerated by $X_{b}$,
so $\sigma=\sigma_{j}$ for some $j<h(r_{i})\leq i+1$. Then

$\langle b+1,e_{i,j}\rangle\in X\iff e_{i,j}\in X_{b+1}\iff
J^{X_{b}}(e_{i,j})\mskip-3.0mu\mskip-3.0mu\downarrow\iff\sigma(e_{i,j})=0,$

which contradicts $\sigma$ being an initial segment of $X$. ∎

######  Lemma 4.44.

Suppose $\mathcal{P}$ is a $\Pi^{0}_{1}$ class and $f\in\omega^{\omega}$ is
such that every function dominating $f$ computes an element of $\mathcal{P}$.
Then there is a $\Phi$ and an $f^{\prime}$ such that for every function $g$
majorizing $f^{\prime}$, $\Phi^{g}$ is an element of $\mathcal{P}$.

###### Proof.

We perform Hechler forcing: a condition is a pair $(\sigma,g)$ such that
$\sigma\in\omega^{<\omega}$, $g\in\omega^{\omega}$, and $\sigma\subset g$; we
say that $(\sigma_{0},g_{0})\leq(\sigma_{1},g_{1})$ if
$\sigma_{0}\supseteq\sigma_{1}$ and $g_{0}$ majorizes $g_{1}$.

If $F$ is a sufficiently generic filter, $g_{F}=\bigcup_{(\sigma,g)\in
F}\sigma$ is a total function majorizing every $g$ with $(\sigma,g)\in F$.
Note that for any condition $(\sigma,g)$, if we define

$g^{\prime}(x)=\left\\{\begin{array}[]{cl}\sigma(x)&x<|\sigma|\\\
\max\\{f(x),g(x)\\}&\text{otherwise,}\end{array}\right.$

then $g^{\prime}$ dominates $f$ and $(\sigma,g^{\prime})\leq(\sigma,g)$. So
for a sufficiently generic filter $F$, $g_{F}$ will dominate $f$. We fix
$\Psi$ such that $\Psi^{g_{F}}\in\mathcal{P}$. Now we consider the following
set of conditions:

$D=\\{(\sigma,g):[\Psi^{\sigma}]\cap\mathcal{P}=\emptyset\\}\cup\\{(\sigma,g):\exists
n\,\forall(\sigma^{\prime},g^{\prime})\leq(\sigma,g)\,[\Psi^{\sigma^{\prime}}(n)\mskip-3.0mu\mskip-3.0mu\uparrow]\\}.$

$F$ must not meet $D$, so there is some $(\tau,f^{\prime})\in F$ with no
extension in $D$. We claim this is our desired $f^{\prime}$.

We define a functional $\Phi$ as follows: given $g$ majorizing $f^{\prime}$,
we define a sequence $\tau=\sigma_{0}\subset\sigma_{1}\subset\dots$ such that
$\Psi^{\sigma_{n}}\mskip-3.0mu\mskip-3.0mu\upharpoonright{n}\mskip-3.0mu\mskip-3.0mu\downarrow$
and for all $x$ with $|\sigma_{n}|\leq x<|\sigma_{n+1}||$,
$\sigma_{n+1}(x)\geq g(x)$. Then we define
$\Phi^{g}=\bigcup_{n}\Psi^{\sigma_{n}}$.

Now, towards a contradiction, we suppose $n$ is least such that there is no
$\sigma_{n+1}$. Then for

$g^{\prime}(x)=\left\\{\begin{array}[]{cl}\sigma_{n}(x)&x<|\sigma_{n}|\\\
g(x)&\text{otherwise,}\end{array}\right.$

$(\sigma_{n},g^{\prime})\in D$ is an extension of $(\tau,f^{\prime})$, giving
us a contradiction. Thus $\Phi^{g}$ is total.

Again towards a contradiction, we suppose $\Phi^{g}\not\in\mathcal{P}$. Then
there is some least $n$ such that
$[\Psi^{\sigma_{n}}]\cap\mathcal{P}=\emptyset$. For the same $g^{\prime}$ as
previously, $(\sigma_{n},g^{\prime})\in D$ is an extension of
$(\tau,f^{\prime})$, once more giving us a contradiction. ∎

Let $\mathcal{H}$ be a Harrison order which admits a jump structure. Then the
collection of jump structures on $\mathcal{H}$ is a $\Pi^{0}_{2}$ subset of
$2^{\omega}$, and there is a $\Pi^{0}_{1}$
$\mathcal{P}\subseteq\omega^{\omega}\times 2^{\omega}$ which projects onto
$\mathcal{H}$.

######  Theorem 4.45.

Let $\mathcal{H}$ be a Harrison order which admits a jump structure, and let
$\mathcal{P}$ be a $\Pi^{0}_{1}$ class which projects onto the jump structures
of $\mathcal{H}$. Then for any $f\in\omega^{\omega}$, there is a $g$
dominating $f$ which does not compute an element of $\mathcal{P}$.

###### Proof.

Suppose not. Then, by Lemma 4.44, there are $\Phi$ and $f$ such that for every
$g$ majorizing $f$, $\Phi^{g}\in\mathcal{P}$. By composing with projection, we
get $\Psi$ such that for every $g$ majorizing $f$, $\Psi^{g}$ is a jump
structure on $\mathcal{H}$. As the collection of jump structures is a subset
of $2^{\omega}$, it has compact closure, and by Lemma 4.23, for every
computable order $h$ there is a jump structure on $\mathcal{H}$ with a
$\Pi^{1}_{1}$ $h$-trace. This contradicts Proposition 4.43. ∎

######  Lemma 4.46.

If $\mathcal{L}$ is a computable linear order (where we identify the domain
with $\omega$) and $f$ is a descending sequence (thought of as an element of
$\omega^{\omega}$), then any $g$ majorizing $f$ uniformly computes a
descending sequence through $\mathcal{L}$.

###### Proof.

Let $a_{0}$ be the $\mathcal{L}$-rightmost of the first $g(0)$ elements of
$\mathcal{L}$, and, given $a_{n}$, define $a_{n+1}$ to be the
$\mathcal{L}$-rightmost of the first $g(n+1)$ elements of $\mathcal{L}$ which
are to the left of $a_{n}$. Inductively, $f(n)\leq_{\mathcal{L}}a_{n}$, and so
a candidate for $a_{n+1}$ exists; in particular, $f(n+1)$ is such an element.
∎

######  Corollary 4.47.

There is a degree which is uniformly high for descending sequences but not
high for isomorphism.

###### Proof.

Let $f$ be a total function such that for every $e$ such that
$\mathcal{L}_{e}$ is ill founded, $f^{[e]}$ is a descending sequence. By
Theorem 4.45, there is a $g$ majorizing $f$ which is not high for paths, and
by Lemma 4.46, this $g$ is uniformly high for descending sequences. ∎

We will strengthen this result in Theorem 5.3.

Though highness, even uniform highness, for descending sequences does not
suffice to imply highness for isomorphism, the addition of a different
property provides the missing strength, although this property itself seems
rather weak (see Proposition 3.3).

######  Theorem 4.48.

A degree $\mathbf{d}$ is high for isomorphism if and only if it is both high
for descending sequences and Scott complete.

###### Proof.

Given isomorphic computable structures $\mathcal{A}$ and $\mathcal{B}$, we
form a structure $\mathcal{A}\odot\mathcal{B}$ by expanding the cardinal sum
of $\mathcal{A}$ and $\mathcal{B}$ with two new constant symbols $a,b$, adding
new elements to instantiate them, and adding a new relation $S$ such that
$aSx$ for exactly those $x\in\mathcal{A}$ and $bSx$ for exactly those
$x\in\mathcal{B}$. We take a Harrison order $\mathcal{H}$ whose well-founded
part $W(\mathcal{H})$ is Turing equivalent to $\mathcal{O}$, a standard
operation described in [16, 20], and let $(\leq_{x}:x\in\mathcal{H})$ be the
Scott analysis computed by $\mathbf{d}$.

We now consider the points $a,b$. As $\mathcal{A}\cong\mathcal{B}$,
$a\cong_{\alpha}b$ for all ordinals $\alpha$, and thus $a\cong_{x}b$ for every
$x\in W(\mathcal{H})$. If for all $x\in\mathcal{H}\setminus W(\mathcal{H})$ we
have $a\ncong_{x}b$, then $\mathbf{d}$ easily computes $W(\mathcal{H})$ and
thus computes $\mathcal{O}$, making $\mathbf{d}$ high for isomorphism.

Thus we can assume that there is some $x\in\mathcal{H}\setminus
W(\mathcal{H})$ such that $a\cong_{x}b$ and take
$\mathcal{H}^{\prime}=\mathcal{H}\upharpoonright_{x}$. Since $\mathbf{d}$ is
high for descending sequences, we find a $\mathbf{d}$-computable descending
sequence $(s_{i}:i\in\mathbb{N})\subseteq\mathcal{H}^{\prime}$. We will use
$(\leq_{s_{i}}:i\in\mathbb{N})$ to compute an isomorphism
$f:\mathcal{A}\to\mathcal{B}$. We construct a sequence
$(\tilde{f}_{t}:t\in\mathbb{N})$ of finite partial isomorphisms; for
notational convenience, we will also construct $\delta_{t}$ a tuple of the
elements of $\text{dom}(f_{t})$ and $\gamma_{t}$ a tuple of the elements of
$\text{range}(f_{t})$.

We let $\tilde{f}_{0}=\\{(a,b)\\}$, denoting $\delta_{0}=(a)$ and
$\gamma_{0}=(b)$. Now, at stage $2t$, we take the first
$c\in\mathcal{A}\setminus\text{dom}(\tilde{f}_{2t})$ and find (using oracle
$\mathbf{d}$) some $d$ such that
$\delta_{2t}\widehat{\phantom{\alpha}}c\leq_{s}\gamma_{2t}\widehat{\phantom{\alpha}}d$
for $s=s_{2t}$. We set $\tilde{f}_{2t+1}=\tilde{f}_{2t}\cup\\{(c,d)\\}$ and
make $\delta_{2t+1}=\delta_{2t}\widehat{\phantom{\alpha}}c$ and
$\gamma_{2t+1}=\gamma_{2t}\widehat{\phantom{\alpha}}d$. We act symmetrically
at stage $2t+1$ so that both $\mathcal{A}$ and $\mathcal{B}$ are exhausted. We
now define $\tilde{f}=\bigcup\limits_{t\in\mathbb{N}}\tilde{f}_{t}$ and
$f=\tilde{f}\setminus\\{(a,b)\\}$. Finally, we can see that
$f:\mathcal{A}\to\mathcal{B}$ is an isomorphism.

The converse follows from the discussion at the conclusion of Section 3 and at
the beginning of the present section. ∎

######  Corollary 4.49.

There is a degree which is uniformly high for descending sequences but not
Scott complete, and conversely.

###### Proof.

By Corollary 4.47, uniform highness for descending sequences does not imply
highness for isomorphism, and thus cannot imply Scott completeness.

As observed in Section 3, Scott completeness does not imply highness for
isomorphism, and thus cannot imply highness for descending sequences.
Alternatively, this follows from the same reasoning employed in Proposition
4.19. ∎

##  5\. Reticence

It is standard in computability to distinguish between positive information
(e.g., an enumeration) and complete information. A structural analogue of this
distinction is what we call “reticence.” By this we mean that a degree that
is, for instance, uniformly high for isomorphism ”in the reticent sense”
should not only compute isomorphisms where they exist but refrain from
computing things that seem to be isomorphisms when no isomorphism exists. We
present a formal definition here.

######  Definition 5.1.

Let $\mathbf{d}$ be a Turing degree which is uniformly high for a given notion
$\mathcal{N}$. That is, there is some $I\subseteq\omega$ (depending on
$\mathcal{N}$) and a $\mathbf{d}$-computable function $F$ such that if $i\in
I$, then $F(i)\in\omega^{\omega}$ has some $\mathcal{N}$-appropriate relation
to $i$, (e.g., uniformly high for paths, where $I$ is the set of indices for
nonempty $\Pi^{0}_{1}$ classes and $F(i)\in\mathcal{P}_{i}$).

We say that $\mathbf{d}$ is uniformly high for $\mathcal{N}$ in the reticent
sense if $F$ can be chosen such that for every $i\not\in I$, the partial
function $F(i)$ diverges for all inputs.

Of course, being uniformly high for some notion in the reticent sense implies
being uniformly high in the normal sense. Possibly the most interesting
feature of reticence from our perspective is that our various highness
properties, apparently distinct without reticence, collapse when this further
requirement is introduced.

######  Theorem 5.2.

The following properties of a degree $\mathbf{d}$ are equivalent:

  1. (1)

$\mathbf{d}$ enumerates all $\Sigma^{1}_{1}$ sets.

  2. (2)

$\mathbf{d}$ is uniformly high for paths in the reticent sense.

  3. (3)

$\mathbf{d}$ is uniformly high for isomorphism in the reticent sense.

  4. (4)

$\mathbf{d}$ is uniformly high for descending sequences in the reticent sense.

  5. (5)

$\mathbf{d}$ is uniformly high for tight descending sequences.

  6. (6)

$\mathbf{d}$ is uniformly high for tight descending sequences in the reticent
sense.

###### Proof.

The proof is organized as follows:

${(1)}$${(2)}$${(3)}$${(5)}$${(6)}$${(4)}$

(1 $\Rightarrow$ 2) Let $\mathcal{P}_{e}$ be an effective listing of
$\Pi^{0}_{1}$ classes in Baire space. By assumption, $\mathbf{d}$ enumerates
$X=\\{(\sigma,e):[\sigma]\cap\mathcal{P}_{e}\neq\emptyset\\}$.

Given $e$, we search for a string $\sigma_{0}$ with $(\sigma_{0},e)\in X$.
Having found such a $\sigma_{0}$, we define
$F(e)\mskip-3.0mu\mskip-3.0mu\upharpoonright{|\sigma_{0}|}=\sigma_{0}$. We
then search for a string $\sigma_{1}\in X$ strictly extending $\sigma_{0}$,
and continue in this fashion.

If $\mathcal{P}_{e}$ is empty, then there is no such $\sigma_{0}$, and so we
will leave $F(e)$ everywhere divergent. On the other hand, if
$\mathcal{P}_{e}$ is nonempty, then we will find our sequence of $\sigma_{i}$s
and use them to define
$F(e)\in\bigcap_{i}[\sigma_{i}]\subseteq\mathcal{P}_{e}$.

Thus $f$ witnesses that $\mathbf{d}$ is uniformly high for paths in the
reticent sense.

($2\Rightarrow 3)$ Given computable structures $\mathcal{M}_{i}$ and
$\mathcal{M}_{j}$, $\\{(f,f^{-1}):\mathcal{M}_{i}\cong_{f}\mathcal{M}_{j}\\}$
is a $\Pi^{0}_{1}$ class.

($3\Rightarrow 2$) In the proof of Proposition 2.6, we gave a uniform
procedure for transforming a $\Pi^{0}_{1}$ class into a pair of computable
structures such that the structures are isomorphic if and only if the class is
nonempty, and every isomorphism computes an element of the class. The result
follows.

($2\Rightarrow 4$) The infinite descending sequences through a computable
linear order form a $\Pi^{0}_{1}$ class, and an index for the $\Pi^{0}_{1}$
class can be effectively obtained from an index for the linear order.

($1\Rightarrow 6$) Let $\mathcal{L}_{e}$ be an effective listing of computable
linear orders. By assumption, $\mathbf{d}$ enumerates $X=\\{(a,e):\text{$a$ is
in the ill-founded part of $\mathcal{L}_{e}$}\\}$. We fix such an enumeration
$(X_{s})_{s\in\omega}$ and assume $X_{s}$ is finite for every $s$. Given $e$,
we search for $a_{0}\in\mathcal{L}_{e}$ with $(a_{0},e)\in X$; if we find such
an $a_{0}$ at stage $s$, we make sure to choose it such that $a_{0}$ is the
leftmost element of $\mathcal{L}_{e}$ with $(a_{0},e)\in X_{s}$. We then
search for an $a_{1}\in\mathcal{L}_{e}$ with $(a_{1},e)\in X$ and
$a_{1}<_{\mathcal{L}_{e}}a_{0}$; again, we choose $a_{1}$ to be the leftmost
eligible element at the stage we find it. We continue in this fashion and
define $F(e)=\langle a_{0},a_{1},\dots\rangle$

Clearly if $\mathcal{L}_{e}$ is well founded, then we never find $a_{0}$, and
so $F(e)$ diverges for all inputs. Suppose now that $b$ is an element of the
ill-founded part of $\mathcal{L}_{e}$. There there is some $s$ with $(b,e)\in
X_{s}$, and so any $a_{n}$ chosen on or after stage $s$ will be
$\leq_{\mathcal{L}_{e}}b$ by construction.

($6\Rightarrow 5$) This is immediate.

($4\Rightarrow 1$) Given a $\Sigma^{1}_{1}$ set $Y$, there is a computable
sequence of linear orders $(\mathcal{L}_{e_{n}})_{n\in\omega}$ such that
$\mathcal{L}_{e_{n}}$ is ill founded if and only if $n\in Y$. Therefore, $n\in
Y$ if and only if $F(e_{n})$ produces any output, which gives a
$\mathbf{d}$-computable enumeration.

($5\Rightarrow 1$) Fix a $\Sigma^{1}_{1}$ set $Y$. Then there is a computable
sequence of linear orders $(\mathcal{L}_{e_{n}})_{n\in\omega}$ such that
$\mathcal{L}_{e_{n}}$ is ill founded if and only if $n\in Y$. Now fix a
Harrison order $H$ and, for each $n$, define $i_{n}$ so that
$\mathcal{L}_{i_{n}}=\mathcal{L}_{e_{n}}+H$. Then $\mathcal{L}_{i_{n}}$ will
be ill founded and $F(i_{n})$ will produce a tight descending sequence through
it. Then $n\in Y$ if and only if $F(i_{n})$ enumerates an element of the
$\mathcal{L}_{e_{n}}$ part of $\mathcal{L}_{i_{n}}$, which gives a
$\mathbf{d}$-computable enumeration. ∎

The striking thing about this result is the light it sheds on the known
separations among the “nonreticent” versions of these properties. The
separation for any two of these properties must somehow be driven by how the
degrees in question handle the “dark matter” of, e.g., the nonisomorphic
structures or non-ill-founded orders. To the present authors, at least, this
feature was not obvious from our initial proofs of separation.

Theorem 5.2 and Corollary 4.47 immediately separate uniform highness for
descending sequences from the reticent notion. We can also separate uniform
highness for isomorphism from the reticent notions.

######  Theorem 5.3.

There is a $\mathbf{d}$ with $\mathbf{d}^{\prime}\equiv_{T}\mathcal{O}$ that
is uniformly high for descending sequences but not high for isomorphism, and
such that there is no $\mathbf{b}$ that is uniformly high for descending
sequences in the reticent sense such that $\mathbf{d}\leq_{T}\mathbf{b}$ and
$\mathcal{O}\not\leq_{T}\mathbf{b}$.

###### Proof.

Fix $(\mathcal{P}_{e})_{e\in\omega}$ an effective listing of all $\Pi^{0}_{1}$
classes in Baire space. Now define $c(0)=-1$ and, for $n>0$, define $c(n)$ to
be the largest $x$ such that $\langle x,y\rangle<n$ for some $y$ where
$\langle\cdot,\cdot\rangle$ is the standard pairing function. As before, we
write $J$ for the universal jump functional. We define a forcing notion and
then carefully build a sequence through the notion.

Our conditions will be triples
$(\tau,f,n)\in\omega^{<\omega}\times\omega^{\omega}\times\omega$ satisfying:

  * •

$\tau$ majorizes $f$;

  * •

$c(|\tau|)<n$;

  * •

$f$ is strongly hyperlow; and

  * •

For $e<n$, if $\mathcal{P}_{e}$ is nonempty, then $f^{[e]}$ majorizes an
element of $\mathcal{P}_{e}$.

Condition $(\sigma,g,m)$ extends condition $(\tau,f,n)$ if:

  * •

$\sigma\supseteq\tau$;

  * •

$g$ majorizes $f$;

  * •

$m\geq n$; and

  * •

For all $x<|\tau|$, $g(x)=f(x)$.

If $(\sigma,g,m)$ extends $(\tau,f,n)$ and, in addition, $g^{[e]}=f^{[e]}$ for
all $e<r$, then we say that $(\sigma,g,m)$ $r$-extends $(\tau,f,n)$. Thus
$0$-extension is simply extension.

We build an $\mathcal{O}$-computable sequence of conditions
$(\tau_{0},f_{0},n_{0}),(\tau_{1},f_{1},n_{1}),\dots$, each extending the
previous. Our degree $\mathbf{d}$ will be the degree of
$G=\bigcup_{s}\tau_{s}$. We begin by setting $\tau_{0}$ to be the empty
string, $f_{0}$ to be the constant $0$ function, and $n_{0}=0$.

At stage $3s$. Suppose we have constructed $(\tau_{3s},f_{3s},n_{3s})$. Let
$e=n_{3s}$. An oracle for $\mathcal{O}$ can determine whether
$\mathcal{P}_{e}$ is empty. If so, we define $f_{3s+1}=f_{3s}$. If not, we fix
some $h\in\mathcal{P}_{e}$ such that $f_{3s}\oplus h$ is strongly hyperlow; we
define $f_{3s+1}^{[e]}(x)=\max\\{f_{3s}^{[e]}(x),h(x)\\}$ and
$f_{3s+1}(x)=f_{3s}(x)$ elsewhere. In either case, we let
$\tau_{3s+1}=\tau_{3s}$ and $n_{3s+1}=e+1$. We have now forced that $G^{[e]}$
dominates an element of $\mathcal{P}_{e}$ if the latter is nonempty. Note that
our new condition $e$-extends the previous condition.

At stage $3s+1$. Suppose we have constructed
$(\tau_{3s+1},f_{3s+1},n_{3s+1})$. Let $e=n_{3s+1}$ and consider the set of
$g$ satisfying the following:

  * •

$g$ majorizes $f_{3s+1}$;

  * •

For all $e<n_{3s+1}$, $g^{[e]}=f_{3s+1}^{[e]}$; and

  * •

For all $\sigma\supseteq\tau_{3s+1}$ majorizing $g$,
$J^{\sigma}(s)\mskip-3.0mu\mskip-3.0mu\uparrow$.

This is a $\Pi^{0}_{1}(f_{3s+1})$ class, and so $\mathcal{O}$ can determine
whether it is empty. If it is nonempty, let $n_{3s+2}=n_{3s+1}$,
$\tau_{3s+2}=\tau_{3s+1}$, and $f_{3s+2}$ be some strongly hyperlow element of
the class; we have now forced $J^{G}(s)\mskip-3.0mu\mskip-3.0mu\uparrow$.

If instead the class is empty, we begin building a sequence of extensions:

$(\tau_{3s+1},f_{3s+1},n_{3s+1})=(\rho_{0},h_{0},m_{0}),(\rho_{1},h_{1},m_{1}),(\rho_{2},h_{2},m_{2}),\dots$

Each term is constructed from the previous term following the process for
stage $3s$, and so each $(\rho_{k+1},h_{k+1},m_{k+1})$ $m_{k}$-extends
$(\rho_{k},h_{k},m_{k})$. After constructing the $k$th term, we ask
$\mathcal{O}$ if there is a $\sigma$ satisfying the following:

  * •

$\sigma\supseteq\tau_{3s+1}$;

  * •

$c(|\sigma|)<m_{k}$;

  * •

$\sigma$ majorizes $h_{k}$; and

  * •

$J^{\sigma}(s)\mskip-3.0mu\mskip-3.0mu\downarrow$.

If there is no such $\sigma$ for any $k$, then $H=\lim_{k}h_{k}$ is an element
of the earlier $\Pi^{0}_{1}(f_{3s+1})$ class which we assumed was empty,
giving us a contradiction. Thus eventually we locate such a $k$ and witnessing
$\sigma$. We then define $\tau_{3s+2}=\sigma$, $f_{3s+2}=h_{k}$ and
$n_{3s+2}=m_{k}$. We have now forced
$J^{G}(s)\mskip-3.0mu\mskip-3.0mu\downarrow$.

At stage $3s+2$. Suppose we have constructed
$(\tau_{3s+1},f_{3s+1},n_{3s+1})$. Fix $T\subseteq\omega^{<\omega}$ a
computable tree such that $[T]$ is the $\Pi^{0}_{1}$ class guaranteed by Lemma
4.45. We may assume that for all oracles $X$ and all $t$, if
$(\Phi_{s}^{X}\mskip-3.0mu\mskip-3.0mu\upharpoonright{t})\mskip-3.0mu\mskip-3.0mu\downarrow$,
then $(\Phi_{s}^{X}\mskip-3.0mu\mskip-3.0mu\upharpoonright{t})\in T$. We again
build a sequence of extensions:

$(\tau_{3s+2},f_{3s+2},n_{3s+2})=(\rho_{0},h_{0},m_{0}),(\rho_{1},h_{1},m_{1}),(\rho_{2},h_{2},m_{2}),\dots$

Each term is again constructed from the previous term following the process
for stage $3s$, and so each $(\rho_{k+1},h_{k+1},m_{k+1})$ $m_{k}$-extends
$(\rho_{k},h_{k},m_{k})$. After constructing the $k$th term, we ask
$\mathcal{O}$ if there is a $g\in\omega^{\omega}$, a
$\sigma\in\omega^{<\omega}$ and a $t\in\omega$ satisfying the following:

  * •

$g$ majorizes $h_{k}$;

  * •

$(\sigma,g,m_{k})$ extends $(\tau_{3s+2},f_{3s+2},n_{3s+2})$; and

  * •

There is no $\sigma^{\prime}\supseteq\sigma$ majorizing $g$ with
$(\Phi_{s}^{\sigma^{\prime}}\mskip-3.0mu\mskip-3.0mu\upharpoonright{t})\mskip-3.0mu\mskip-3.0mu\downarrow$.

Towards a contradiction, we suppose there are never any such $g$, $\sigma$,
and $t$ for any $k$. Let $H=\lim_{k}h_{k}$. Given an oracle $g$ majorizing
$H$, we may assume $g$ extends $\tau_{3s+2}$. Consider the following
algorithm:

  * •

Let $\sigma_{0}=\tau_{3s+2}$;

  * •

Given $\sigma_{i}$, search for a $\sigma_{i+1}\supseteq\sigma_{i}$ that
majorizes $g$ with
$\Phi_{s}^{\sigma_{i+1}}(i)\mskip-3.0mu\mskip-3.0mu\downarrow$.

If this algorithm finds a $\sigma_{i}$ for every $i$, it computes a path
through $T$ via $\Phi_{s}$, but by Lemma 4.45, there is some $g$ majorizing
$H$ for which it fails. Fix such a $g$ and let $i$ be least such that the
algorithm fails to define $\sigma_{i+1}$. Furthermore, let $k$ be such that
$c(|\sigma_{i}|)<m_{k}$. Then this $g$, $\sigma=\sigma_{i}$, and $t=i$ are as
desired for $k$, contrary to assumption.

Therefore, eventually we locate a $k$ for which $g$ and $\sigma$ exist. We fix
such $g$ and $\sigma$ with $g$ strongly hyperlow. We set
$(\tau_{3s+3},f_{3s+3},n_{3s+3})=(\sigma,g,m_{k})$, and we have now forced
that $\Phi_{s}^{G}\not\in[T]$.

By construction, $G^{[e]}$ majorizes an element of $\mathcal{P}_{e}$ whenever
the latter is nonempty. It follows that $\mathbf{d}$ is uniformly high for
descending sequences. It also follows that $\mathbf{d}$ enumerates
$\mathcal{O}$: a $\Pi^{0}_{1}$ class $\mathcal{P}_{e}$ is empty if and only if
$\mathcal{P}_{e}\cap\\{g:\forall x\,[g(x)\leq G^{[e]}(x)]\\}$ is empty, and
the latter is effectively compact relative to $G$. We force the jump, so
$\mathbf{d}^{\prime}\leq_{T}\mathcal{O}$ and thus
$\mathbf{d}^{\prime}\equiv_{T}\mathcal{O}$. We also ensure that $\mathbf{d}$
is not high for isomorphism, as it does not compute an element of $[T]$.

Now suppose $\mathbf{b}\geq_{T}\mathbf{d}$ is uniformly high for descending
sequences in the reticent sense. Then $\mathbf{b}$ enumerates
$\omega\setminus\mathcal{O}$, and since $\mathbf{d}$ enumerates $\mathcal{O}$,
$\mathbf{b}$ does too. Thus, $\mathbf{b}$ computes $\mathcal{O}$. ∎

######  Corollary 5.4.

There is a degree that is uniformly high for isomorphism, but not in the
reticent sense.

###### Proof.

Let $\mathbf{d}$ be as in Theorem 5.3, and take $\mathbf{b}$ to be both PA
over $\mathbf{d}$ and low over $\mathbf{d}$. Then $\mathbf{b}$ is uniformly
high for isomorphism by Theorem 4.15, but not in the reticent sense, as
$\mathbf{b}$ is above $\mathbf{d}$ but not $\mathcal{O}$. ∎

##  6\. Randomness and genericity

We conclude with some quick remarks on the ability of degrees that are high
for isomorphism to compute generic and random sets.

######  Fact 6.1.

All degrees that are high for isomorphism compute a $\Sigma^{1}_{1}$-generic
since $\Sigma^{1}_{1}$-generics form a $\Sigma^{1}_{1}$ class, but the
converse may not hold.

This contrasts, sharply and unsurprisingly, with the situation for degrees
that are low for isomorphism: every Cohen 2-generic is itself low for
isomorphism, as is every degree computable from a Cohen 2-generic [12].

######  Fact 6.2.

All degrees that are high for isomorphism compute a $\Pi^{1}_{1}$-random since
the class of $\Pi^{1}_{1}$ randoms is $\Sigma^{1}_{1}$.

Again, this contrasts with the situation for degrees that are low for
isomorphism: no Martin-Löf random degree is low for isomorphism [12].

We now use the notion of genericity to explore the relationship between
degrees that are low for isomorphism and degrees that are high for
isomorphism. Recall that the triple jump of a degree high for isomorphism must
compute $\mathcal{O}$. While this does not give an exact characterization of
highness for isomorphism, it would be nice if it at least ruled out the
degrees which are low for isomorphism. However, this is not the case.

######  Theorem 6.3 (Kurtz [22]).

A degree $\mathbf{b}$ is the $n$th jump of a weakly $(n+1)$-generic degree if
and only if $\mathbf{b}>\mathbf{0}^{(n)}$ and $\mathbf{b}$ is hyperimmune
relative to $\mathbf{0}^{(n)}$.

It follows that the degree of $\mathcal{O}$ is the $n$th jump of a weakly
$n$-generic degree for every $n$ and thus the double jump of a 2-generic, and
therefore in particular it is the double jump of a low-for-isomorphism degree.

##  7\. Summary of results and future directions

At the time of this writing, the following questions appear both entirely open
and deeply interesting.

######  Question 7.1.

Is there a jump complete degree which is not uniformly high for isomorphism?

######  Question 7.2.

Is there a jump complete degree which is not uniformly high for descending
sequences?

######  Question 7.3.

Is there a jump complete degree which is not Scott complete?

######  Question 7.4.

Is there a degree $\mathbf{d}$ which is uniformly high for isomorphism, with
$\mathbf{d}^{\prime\prime}\equiv_{T}\mathcal{O}$?

## References

  * [1] C.J. Ash and J. Knight.  Computable Structures and the Hyperarithmetical Hierarchy.  Number 144 in Studies in Logic and the Foundations of Mathematics. North-Holland, 2000.
  * [2] Tomek Bartoszyński and Haim Judah.  Set theory: On the structure of the real line.  A K Peters, Ltd., Wellesley, MA, 1995.
  * [3] J. Barwise.  Back-and-forth through infinitary logic.  In M. D. Morley, editor, Studies in Model Theory, number 8 in Studies in Mathematics, pages 5–34. Mathematical Association of America, 1973\.
  * [4] W. Calvert, J. F. Knight, and J. Millar.  Computable trees of Scott rank $\omega_{1}^{CK}$, and computable approximation.  Journal of Symbolic Logic, 71:283–298, 2006.
  * [5] C. T. Chong and L. Yu.  Recursion Theory.  Number 8 in De Gruyter Series in Logic and its Applications. De Gruyter, 2015.
  * [6] Barbara Csima.  Degrees of categoricity and related notions, November 2013.  BIRS Computable Model Theory Workshop.
  * [7] R. Douni, D. Khirshvel’d, and B. Khusainov.  Uniformity in the theory of computable structures.  Algebra Logika, 42(5):566–593, 637, 2003.
  * [8] Ekaterina B. Fokina, Sy-David Friedman, Valentina Harizanov, Julia F. Knight, Charles McCoy, and Antonion Montalbán.  Isomorphism relations on computable structures.  Journal of Symbolic Logic, 77:122–132, 2012.
  * [9] Johanna N. Y. Franklin and Dan Turetsky.  Taking the path computably traveled.  J. Logic Comput., 29(6):969–973, 2019.
  * [10] Johanna N.Y. Franklin.  Lowness and highness properties for randomness notions.  In T. Arai et al., editor, Proceedings of the 10th Asian Logic Conference, pages 124–151. World Scientific, 2010.
  * [11] Johanna N.Y. Franklin and Timothy H. McNicholl.  Degrees of and lowness for isometric isomorphism.  J. Log. Anal., 12:Paper 6, 23, 2020.
  * [12] Johanna N.Y. Franklin and Reed Solomon.  Degrees that are low for isomorphism.  Computability, 3(2):73–89, 2014.
  * [13] Johanna N.Y. Franklin and Reed Solomon.  Lowness for isomorphism, countable ideals, and computable traceability.  MLQ Math. Log. Q., 66(1):104–114, 2020.
  * [14] Johanna N.Y. Franklin, Frank Stephan, and Liang Yu.  Relativizations of randomness and genericity notions.  Bull. Lond. Math. Soc., 43(4):721–733, 2011.
  * [15] Johanna N.Y. Franklin and Dan Turetsky.  Lowness for isomorphism and degrees of genericity.  Computability, 7(1):1–6, 2018.
  * [16] Harvey Friedman.  Recursiveness in $\Pi^{1}_{1}$ paths through $\mathcal{O}$.  Proc. Amer. Math. Soc., 54:311–315, 1976.
  * [17] R. O. Gandy, G. Kreisel, and W. W. Tait.  Set existence.  Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys., 8:577–582, 1960.
  * [18] Jun Le Goh.  Inseparable $\Pi^{1}_{1}$ sets.  In preparation.
  * [19] S. S. Goncharov and Dzh. Naĭt.  Computable structure and antistructure theorems.  Algebra Logika, 41(6):639–681, 757, 2002.
  * [20] Sergey S. Goncharov, Valentina S. Harizanov, Julia F. Knight, and Richard A. Shore.  $\Pi^{1}_{1}$ relations and paths through $\mathcal{O}$.  J. Symbolic Logic, 69(2):585–611, 2004.
  * [21] C. G. Jockusch, Jr. and S. G. Simpson.  A degree-theoritic definition of the ramified analytical hierarchy.  Annals of Mathematical Logic, 10:1–32, 1976.
  * [22] Stuart A. Kurtz.  Notions of weak genericity.  J. Symbolic Logic, 48(3):764–770, 1983.
  * [23] G. E. Sacks.  Higher Recursion Theory.  Number 2 in Perspectives in Logic. Cambridge University Press, 2016.
  * [24] Theodore A. Slaman and Robert M. Solovay.  When oracles do not help.  In Fourth Annual Workshop on Computational Learning Theory, pages 379–383. Morgan Kaufman., Los Altos, CA, 1991.
  * [25] Robert Soare.  The Friedberg-Muchnik theorem re-examined.  Canadian J. of Math., 24:1070–1078, 1972.
  * [26] Jacob Suggs.  Degrees that are low for $\mathcal{C}$ isomorphism.  PhD thesis, University of Connecticut, 2015.