# The degrees of categoricity above $\mathbf{0}^{\prime\prime}$

Barbara F. Csima and Dino Rossegger  Department of Pure Mathematics,
University of Waterloo, Waterloo, Ontario<EMAIL_ADDRESS>Department of
Mathematics, University of California, Berkeley and Institute of Discrete
Mathematics and Geometry, Technische Universität Wien<EMAIL_ADDRESS>
###### Abstract.

We give a characterization of the degrees of categoricity of computable
structures greater or equal to $\mathbf{0}^{\prime\prime}$. They are precisely
the _treeable_ degrees – the least degrees of paths through computable trees –
that compute $\mathbf{0}^{\prime\prime}$. As a corollary, we obtain several
new examples of degrees of categoricity. Among them we show that every degree
$\mathbf{d}$ with
$\mathbf{0}^{(\alpha)}\leq\mathbf{d}\leq\mathbf{0}^{(\alpha+1)}$ for $\alpha$
a computable ordinal greater than $2$ is the strong degree of categoricity of
a rigid structure. Another corollary of our characterization partially answers
a question of Fokina, Kalimullin, and Miller: Every degree of categoricity
above $\mathbf{0}^{\prime\prime}$ is strong. Using quite different techniques
we show that every degree $\mathbf{d}$ with
$\mathbf{0}^{\prime}\leq\mathbf{d}\leq\mathbf{0}^{\prime\prime}$ is the strong
degree of categoricity of a structure. Together with the above example this
answers a question of Csima and Ng. To complete the picture we show that there
is a degree $\mathbf{d}$ with
$\mathbf{0}^{\prime}\leq\mathbf{d}\leq\mathbf{0}^{\prime\prime}$ that is not
the degree of categoricity of a rigid structure.

###### 1991 Mathematics Subject Classification:

03C75, 03D45,03E15

Csima is partially supported by an NSERC Discovery Grant. The work of the
second author was supported by the European Union’s Horizon 2020 Research and
Innovation Programme under the Marie Skłodowska-Curie grant agreement No.
101026834 — ACOSE

Two isomorphic copies of a mathematical structure share the same structural
properties and, thus, one usually considers structures up to isomorphism.
However, Fröhlich and Shepherdson [FS56] and, independently, Malt’sev [Mal62]
showed that isomorphic copies of a structure can behave quite differently with
respect to their algorithmic properties. They produced two isomorphic
computable fields $\mathcal{K}_{1}$ and $\mathcal{K}_{2}$ such that
$\mathcal{K}_{1}$ has a computable transcendence basis, while
$\mathcal{K}_{2}$ fails to have a computable transcendence basis. This leads
to the conclusion that there can not be a computable function that is an
isomorphism between these two fields [FS56, Corollary 5.51].

Two computable isomorphic structures $\mathcal{A}$ and $\mathcal{B}$ that are
computably isomorphic have the same computability theoretic properties and if
$\mathcal{A}$ has computable isomorphisms between all its computable
isomorphic copies then $\mathcal{A}$ is said to be _computably categorical_.
As we have seen even natural structures fail to be computably categorical and
often one would like to know how far apart the computable copies of these
structures can be with respect to their computability theoretic properties.
This is best captured by measuring the Turing complexity of the isomorphisms
between computable copies. Towards this, Fokina, Kalimullin, and Miller
introduced the following notion [FKM10].

######  Definition 1.

Let $\tau$ be a computable vocabulary, $\mathcal{A}$ be a computable
$\tau$-structure, and let $(\mathcal{B}_{e})_{e\in\omega}$ be an enumeration
of all computable $\tau$-structures. The _categoricity spectrum of
$\mathcal{A}$_ is the set

$CatSpec(\mathcal{A})=\bigcap_{e\in\omega:\mathcal{B}_{e}\cong\mathcal{A}}\\{deg(X):(\exists
f:\mathcal{A}\cong\mathcal{B}_{e})X\geq_{T}f\\}.$

If $\mathbf{d}\in CatSpec(\mathcal{A})$ is a least element, then $\mathbf{d}$
is called the _degree of categoricity of $\mathcal{A}$_.

The study of this notion has been one of the most active areas in computable
structure theory in the last decade. See [Fra17] for a survey of developments
until 2017. One of the main goals in the area is to obtain a characterization
of the Turing degrees that are degrees of categoricity.

Fokina, Kalimullin, and Miller [FKM10] showed that every degree $\mathbf{d}$
d-c.e. in and above $\mathbf{0}^{(n)}$ for some $n\in\omega$ is a degree of
categoricity and that $\mathbf{0}^{(\omega)}$ is a degree of categoricity.
Csima, Franklin, and Shore [CFS+13] generalized these results to the
hyperarithmetic hierarchy, showing that both $\mathbf{0}^{(\alpha)}$ for
$\alpha$ a computable limit ordinal and every degree $\mathbf{d}$ d-c.e. in
and above $\mathbf{0}^{(\alpha)}$ for $\alpha$ computable successor ordinal
are degrees of categoricity. The former result was later improved by Csima,
Deveau, Harrison-Trainor, and Mahmoud [Csi+18] to degrees c.e. in and above
limit ordinals.

It is known that not every Turing degree is a degree of categoricity. Csima,
Franklin, and Shore [CFS+13] showed that every degree of categoricity must be
hyperarithmetic and Anderson and Csima [AC12] provided several examples of
degrees that are not degrees of categoricity. For example, they obtained a
$\Sigma^{0}_{2}$ degree that is not a degree of categoricity.

Recently, Csima and Ng [CN22] showed that every $\Delta^{0}_{2}$ degree is a
degree of categoricity. They asked whether for every computable ordinal
$\alpha$, every Turing degree $\mathbf{d}$,
$\mathbf{0}^{(\alpha)}\leq\mathbf{d}\leq\mathbf{0}^{(\alpha+1)}$ is a degree
of categoricity.

The main goal of this article is a characterization of the degrees of
categoricity on the cone above $\mathbf{0}^{\prime\prime}$. We characterize
these degrees by showing that they are exactly the degrees of Turing-least
paths through computable trees in $\omega^{\omega}$ (Corollary 4). Using
classical results about $\Pi^{0}_{1}$ function singletons we then obtain that
every degree $\mathbf{d}$ with
$\mathbf{0}^{(\alpha)}\leq\mathbf{d}\leq\mathbf{0}^{(\alpha+1)}$ for $\alpha$
a computable ordinal greater or equal to $2$ is the degree of categoricity of
a rigid structure. Building on a construction by Csima and Ng [CN22] that
showed that every $\Delta^{0}_{2}$ degree is a degree of categoricity we
complete the picture by showing that every degree $\mathbf{d}$,
$\mathbf{0}^{\prime}\leq\mathbf{d}\leq\mathbf{0}^{\prime\prime}$ is a degree
of categoricity. We thus obtain a positive answer to their first question
(Theorem 13). We also obtain more exotic examples. Using Harrington’s example
of a non-arithmetic $\Pi^{0}_{2}$ singleton [Har76], we obtain degrees of
categoricity that are not between $\mathbf{0}^{(\alpha)}$ and
$\mathbf{0}^{(\alpha+1)}$ for any computable ordinal (Corollary 9).

Another driving question in the area is whether for every degree of
categoricity $\mathbf{d}$ there are computable structures $\mathcal{A}$ and
$\mathcal{B}$ such that $\mathbf{d}$ is the least degree computing
isomorphisms between $\mathcal{A}$ and $\mathcal{B}$. Such degrees are called
_strong_ degrees of categoricity and at the time of writing all known examples
of degrees of categoricity are strong. One corollary of our characterization
partially answers this question: Every degree of categoricity above
$\mathbf{0}^{\prime\prime}$ is strong (Corollary 5).

All of the above results are corollaries of our main theorem whose proof is a
modification of a recent construction of Turetsky that coded paths through
trees into the automorphisms of a structure [Tur20]. In order to state it, we
need to recall a bit of notation. Given a tree $T\subseteq\omega^{<\omega}$ we
denote by $[T]\subseteq\omega^{\omega}$ the set of paths through $T$. For two
sets $P,Q\subseteq\omega^{\omega}$ we say that $P$ is Muchnik reducible to Q,
$P\leq_{w}Q$, if for every $q\in Q$ there is $p\in P$ with $p\leq_{T}q$. We
can computably translate elements of $\omega^{\omega}$ to elements of
$2^{\omega}$ and sets of natural numbers and thus will use Muchnik
reducibility to compare sets of these types. The _computable dimension_ of a
structure is the number of computable copies that are not computably
isomorphic. This number is either finite or $\omega$ and constructions of
examples of finite computable dimension usually involve heavy computability
theoretic machinery. The first example of such a structure was given by
Goncharov [Gon80]. The following is our main theorem from which most other
results in this article are derived.

######  Theorem 1.

Let $T\subseteq\omega^{<\omega}$ be a computable tree such that
$[T]\geq_{w}\\{\emptyset^{\prime\prime}\\}$. Then there is a computable
structure $\mathcal{S}_{1}$ with computable dimension $2$ such that

$CatSp(\mathcal{S}_{1})=\\{\deg(X):\\{X\\}\geq_{w}[T]\\}.$

Furthermore, if $[T]$ is a singleton, then $\mathcal{S}_{1}$ is rigid.

Theorem 1 is proven in Section 1.1 and its corollaries are derived in Section
1.2. In Section 2 we modify the construction of Csima and Ng to show that
every degree $\mathbf{d}$ with
$\mathbf{0}^{\prime}\leq\mathbf{d}\leq\mathbf{0}^{\prime\prime}$ is the degree
of categoricity of a structure.

At last, in Section 3 we generalize a construction by Bazhenov and Yamaleev
[BY17] to show that there is a Turing degree $\mathbf{d}$,
$\mathbf{0}^{\prime}\leq\mathbf{d}\leq\mathbf{0}^{\prime\prime}$ that is not
the degree of categoricity of a rigid structure. This shows that the lower
bound in Theorem 1 can not be improved.

##  1\. Characterizing degrees of categoricity above
$\mathbf{0}^{\prime\prime}$

###  1.1. Degrees of categoricity and paths

Recall that for two sets $X,Y\subseteq\omega^{\omega}$, $X$ is _Muchnik
reducible_ to $Y$, $X\leq_{w}Y$ if for every $y\in Y$ there is $x\in X$ such
that $x\leq_{T}y$. Turetsky proved that given a computable tree
$T\subseteq\omega^{<\omega}$ there is a computable, computably categorical
structure $\mathcal{S}$ such that the paths of $T$ and the non-trivial
automorphisms of $\mathcal{S}$ are Muchnik equivalent modulo
$\mathbf{0}^{\prime\prime}$ [Tur20]. In other words,

$\\{\emptyset^{\prime\prime}\oplus
f:f\in[T]\\}\equiv_{w}\\{\emptyset^{\prime\prime}\oplus\nu:\nu\in
Aut(\mathcal{S})\setminus id\\}.$

Turetsky also exhibited how the structure $\mathcal{S}$ can be adapted to
obtain a structure $\mathcal{S}_{1}$ that is not hyperarithmetically
categorical and has computable dimension $2$. For this structure, it is the
case that the isomorphisms between the two copies witnessing the computable
dimension are Muchnik equivalent to the paths through $T$ modulo
$\mathbf{0}^{\prime\prime}$.

If one can eliminate the $\mathbf{0}^{\prime\prime}$ in these results one
obtains a coding technique that allows the coding of paths through trees into
categoricity spectra of structures of computable dimension $2$. If $T$ has a
unique path $f$, i.e., $f$ is a $\Pi^{0}_{1}$ function singleton, then an
analysis of Turetsky’s construction shows that the structure $\mathcal{S}_{1}$
obtained from $T$ is rigid.

Our first result improves on Turetsky’s by eliminating
$\emptyset^{\prime\prime}$ on the right. We obtain this result by adding
requirements to Turetsky’s construction with the aim of coding
$\emptyset^{\prime\prime}$ into the presentation of $\mathcal{S}$.

######  Lemma 2.

Let $T\subseteq\omega^{<\omega}$ be a computable tree. Then there is a
computable, computably categorical structure $\mathcal{S}$ such that

$\\{\nu:\nu\in(Aut(\mathcal{S})-\\{id\\})\\}\equiv_{w}\\{f\oplus\emptyset^{\prime\prime}:f\in[T]\\}.$

In particular, $|[T]|=1$ if and only if $|Aut(\mathcal{S})-\\{id\\}|=1$.

Lemma 2 is the main ingredient to our proof of Theorem 1. Its proof is a
modification of Turetsky’s infinite injury construction [Tur20, Theorem 2]. We
give a full description of the structure we are going to construct and the
construction, but only sketch the verification in the sense that we prove that
our construction works and gives the desired results if Turetsky’s initial
construction works. Thus, the reader is encouraged to read this together with
Turetsky’s proof for a full verification.

###### Proof sketch..

Given a tree $T$ the vocabulary of $\mathcal{S}$ consists of a unary relations
$U$, $(W_{\sigma})_{\sigma\in\omega^{<\omega}}$, and $(S_{n})_{n\in\omega}$
($V_{n}$ in Turetsky’s construction), binary relations $P$ and
$(E_{n})_{n\in\omega}$, and a unary function $f$. We denote by
$[\omega]^{<\omega}$ the set of all finite subsets of the natural numbers. The
universe of $\mathcal{S}$ will be
$[\omega]^{<\omega}\times\omega^{<\omega}\sqcup C$ where $C$ is an infinite
computable set. The relation symbols $U$ and $f$ and the set $C$ are used to
help with the following issue. During the construction we will want $S_{n}(x)$
to hold for larger and larger $n$ on elements of
$[\omega]^{<\omega}\times\omega$. The issue is, that this would result in a
c.e. structure and not a computable structure. To overcome this we do not
define the $S_{n}$ directly on the $x$ but rather using an element $y\in C$
that is associated to $x$ by $f$, i.e., $f(x)=y$. Formally, we will have the
following.

The relation $U$ is used to identify $C$, i.e. $U^{\mathcal{S}}=C$. We will
have that ${S_{n}}^{\mathcal{S}}\cap\overline{C}=\emptyset$ while none of the
relations $W_{\sigma}$, $E_{n}$ and $P$ hold on any element in $C$. We will
also delcare $f^{\mathcal{S}}(x)=x$ for all $x\not\in C$ and for each $x\in C$
$f(x)\not\in C$. Furthermore, for each $x\in C$ there will be a unique $n$
such that $S_{n}(x)$ holds. During the construction we will ignore $C$, $U$
and $f$ and simply declare that $S_{n}(x)$ holds for some element $x$ in
$[\omega]^{<\omega}\times\omega^{<\omega}$. What this means is that we pick an
unused element $y\in C$, set $f(y)=x$ and $S_{n}(y)$ if no element with these
properties exists at that point of the construction.

With the exception of the relation $S_{n}$, our structure looks exactly as the
one constructed in [Tur20, Theorem 2]. For
$(F,\tau),(G,\rho)\in[\omega]^{<\omega}\times\omega^{<\omega}$ we have that:

  * •

${W}^{\mathcal{S}}_{\sigma}((F,\tau))$ if and only if $\sigma=\tau$

  * •

${E_{i}}^{\mathcal{S}}((F,\tau),(G,\rho))$ if and only if $\tau=\rho$ and
$F\Delta G=\\{i\\}$

  * •

$P^{\mathcal{S}}((F,\rho),(G,\tau))$ if and only if
$\rho\operatorname{{}^{\smallfrown}}i$ for some $i$ and one of the following
holds:

    * –

$i\not\in F$ and $|G|$ is even or

    * –

$i\in F$ and $|G|$ is odd.

It is convenient to think of each $W_{\sigma}$ slice of $\mathcal{S}$ as an
infinite dimensional hypergraph with the edge relations given by the $E_{i}$.
One can then prove that the automorphisms of these slices in the reduct
$(E_{i})_{i\in\omega}$ are exactly the maps of the form
$(F,\sigma)\mapsto(F\Delta H,\sigma)$ for some fixed $H\in[\omega]^{<\omega}$
[Tur20, Claim 2.1]. So, let $g$ be a non-trivial automorphism of the structure
we have defined so far, then $g$ acts non-trivially on one of the
$W^{\mathcal{S}}_{\sigma}$, i.e., $g:(F,\sigma)\mapsto(F\Delta H,\sigma)$ for
$H\neq\emptyset$. In particular $g:(\emptyset,\sigma)\mapsto(H,\sigma)$. The
$P$ predicate forces $g$ to act on $\sigma\operatorname{{}^{\smallfrown}}i$
for $i\in H$. This can be used to prove that the automorphisms of this
presentation of $\mathcal{S}$ are Muchnik equivalent to the paths through $T$.

The only remaining issue is that $\mathcal{S}$ has many computable
presentations and so far we have only controlled the automorphisms of one such
presentation. This is where the $S_{n}$ predicates come in. They are used to
ensure that $\mathcal{S}$ is computably categorical. This process is what
requires a $\mathbf{0}^{\prime\prime}$ priority argument and thus introduces
the $\emptyset^{\prime\prime}$ in the original construction. The construction
will give rise to a $\mathbf{0}^{\prime\prime}$ computable tree
$Q\subseteq\omega^{<\omega}$ that is $\mathbf{0}^{\prime\prime}$ isomorphic to
$T$ such that for $\sigma\in Q$, $S_{n}((F,\sigma))$ will hold for all
$n\in\omega$ and $F\in[\omega]^{<\omega}$ and for $\sigma\not\in Q$, there is
an $n$ such that $S_{n}((F,\sigma))$ holds if and only if $F=\emptyset$. One
can show that the automorphisms of $\mathcal{S}$ are then Muchnik equivalent
to the paths through $Q$. In particular, there is a $1-1$ correspondence
between $Aut(\mathcal{S})\setminus id$ and $[Q]$ [Tur20, Claim 2.2].

However, $Q$ is only $\mathbf{0}^{\prime\prime}$ isomorphic to the original
tree $T$. This is why we modify our construction by forcing that $\sigma\in Q$
with $\sigma(i)\downarrow$ satisfies $2\mid\sigma(i)$ if and only if
$i\in\emptyset^{\prime\prime}$. Now, given an automorphism of $\mathcal{S}$ we
can compute a path $f\in[Q]$ and from $f\oplus\emptyset^{\prime\prime}$ we can
compute a path through $T$ by computing the isomorphism. However, the
condition on $Q$ guarantees that $f\geq_{T}\emptyset^{\prime\prime}$ and thus
$\\{\nu:\nu\in(Aut(\mathcal{S})\setminus\\{id\\})\\}\geq_{w}\\{f\oplus\emptyset^{\prime\prime}:f\in[T]\\}$.
That
$\\{\nu:\nu\in(Aut(\mathcal{S})\setminus\\{id\\})\\}\leq_{w}\\{f\oplus\emptyset^{\prime\prime}:f\in[T]\\}$
follows from a similar argument. Given $f\in[T]$,
$f\oplus\emptyset^{\prime\prime}$ can compute an element of $[Q]$ and thus a
non-trivial automorphism of $\mathcal{S}$.

_Construction._ Turetsky’s construction had a requirement $G$, requirements
$N_{\pi}$ for every $\pi\in T$ and $M_{i}$ for every $i\in\omega$. We add
requirements $R_{i}$ for $i\in\omega$ where $R_{i}$ has the aim to code the
membership of $i$ in $\emptyset^{\prime\prime}$.

We use Turetsky’s order of requirements, interleaving our requirements $R_{i}$
such that $R_{i}\leq N_{\pi}$ for all $\pi$ with $|\pi|=i+1$. The potential
outcomes for $R_{i}$ are $\infty\leq fin$. Using the fact that
$\emptyset^{\prime\prime}$ is $\Sigma^{0}_{2}$ we fix a computable function
$f$ such that $x\in\emptyset^{\prime\prime}$ if and only if $W_{f(x)}$ is a
proper initial segment of $\omega$ and $W_{f(x)}=\omega$ otherwise. We will
also need to modify Turetsky’s strategy for $N_{\pi}$ where
$\pi\neq\emptyset$. The goal of the strategy $M_{i}$ is to ensure that if
$\tau$ is a strategy on the true path (i.e., the left most path of the
priority tree visited infinitely often) and $\mathcal{M}_{i}$ – the $i$th
computable structure in a computable enumeration of the structures in the
language of $\mathcal{S}$ – is isomorphic to $\mathcal{S}$, then
$\mathcal{M}_{i}$ is computably isomorphic to $\mathcal{S}$. This strategy is
unmodified and we thus omit it here.

At the end of every stage $s$, declare $S_{k}((\emptyset,\sigma))$ for every
$k<s$ and $\sigma\in s^{<s}$ not chosen by any strategy.

_Strategy for $R_{i}$._ Suppose $\tau$ is a strategy for $R_{i}$ visited at
stage $s$. Check if $W_{f(x),s}\supset W_{f(x),t}$ where $t$ is the last stage
that $\tau$ acted if it exists. If so let the outcome of $\tau$ be $\infty$.
Otherwise finish with outcome $fin$.

_Strategy for $N_{\pi\operatorname{{}^{\smallfrown}}i}$._ Suppose $\tau$ is a
strategy for the requirement $N_{\pi\operatorname{{}^{\smallfrown}}i}$. Then
there is a unique $\rho\subset\tau$ such that $\rho$ is a strategy for
$N_{\pi}$ and a unique $\sigma\subset\tau$ such that $\sigma$ is a strategy
for $R_{|\pi|}$. Suppose $s_{0}$ is the first stage such that $\tau$ is
visited and that $\rho$ has declared $\zeta$ to be the image of $\pi$. If the
outcome of $\sigma$ is $\infty$, then choose the least even $m>s_{0}$ not
mentioned in the construction and declare
$\zeta\operatorname{{}^{\smallfrown}}m$ to be the image of
$\pi\operatorname{{}^{\smallfrown}}i$. Otherwise choose the least odd
$m>s_{0}$ not mentioned in the construction and declare
$\zeta\operatorname{{}^{\smallfrown}}m$ to be the image of
$\pi\operatorname{{}^{\smallfrown}}i$.

At every stage $s$ when $\tau$ is visited, declare
$S_{n}((\emptyset,\zeta\operatorname{{}^{\smallfrown}}m))$ for the least $n$
such that $S_{n}((\emptyset,\zeta\operatorname{{}^{\smallfrown}}m))$ does not
hold at this stage and declare
$S_{k}((F,\zeta\operatorname{{}^{\smallfrown}}m))$ for all $k<n$ and
$F\subseteq\\{0,\dots,s\\}$. Take the outcome `outcome`.

_Verification._ Let $P$ be the tree of strategies of this construction and let
$T$ be the tree of strategy of [Tur20, Theorem 2]. Given $\sigma\in P$, define
its reduct $\sigma_{r}\in T$ by deleting the occurences of $R$-strategies from
$\sigma$. I.e., assume without loss of generality that no $R_{i}$ strategy is
succeeded by any $R_{j}$ strategy for $i,j\in\omega$ and define

$k(-1)=-1\text{ and
}k(i)=\begin{cases}k(i-1)+1&\sigma(k(i-1)+1)\not\in\\{\infty,fin\\}\\\
k(i-1)+2&\text{otherwise}\end{cases}$

for $i\geq 0$ and let $\sigma_{r}(i)=\sigma(k(i))$. Let
$P^{-}=\bigcap_{i\in\omega}\left\\{\sigma\in
P:\sigma(|\sigma|-1)\not\in\\{\infty,fin\\}\right\\}$. While $P^{-}$ is not a
set-theoretic tree, it still is a tree as a partial order. It is then easy to
see that the map $h:P^{-}\to T:\sigma\mapsto\sigma_{r}$ is a homomorphism of
trees that preserves the priority ordering, i.e., for $\sigma,\tau\in P^{-}$

$\sigma\preccurlyeq\tau\implies h(\sigma)\preccurlyeq h(\tau)\text{ and
}\sigma\leq^{P}\tau\implies h(\sigma)\leq^{T}h(\tau).$

######  Claim 2.1.

If a path $f\in[T]$ is visited infinitely often, then there is a path
$g\in[P^{-}]=[P]$ such that $h(g)=f$. Moreover, if $f$ is least in $[T]$ with
respect to the priority ordering, then $g$ can be taken least in $[P]$.

###### Proof.

Run a strategy $\sigma$ for $R_{i}$ in isolation and let the true outcome of
$\sigma$ be the leftmost outcome of $\sigma$ that occurs infinitely often.
Clearly the true outcome is $\infty$ if and only if $W_{i}$ is infinite and
$fin$ otherwise. Furthermore, it does not depend on the outcome of any other
strategies. Denote this outcome by $t_{i}$. Given a strategy $\sigma\in T$
that is visited infinitely often note that for $\tau,\rho\in h^{-1}(\sigma)$,
$|\tau|=|\rho|$. Consider the string $\tau\in h^{-1}(\sigma)$ obtained by
filling the gaps by $t_{i}$, i.e., if $\tau(j)$ is the $i$th occurence of
$\infty$ or $fin$ in $\tau$, then $\tau(j)=t_{i}$. Clearly, $\tau$ is visited
infinitely often. Also, no string that was visited infinitely often in
$h^{-1}(\sigma)$ can be to the left of $\tau$ as they can only differ on
positions containing $\infty$ or $fin$. The claim now follows by induction on
the length of $\tau$. ∎

By 2.1 we have that if $f$ is the true path in our construction, then $h(f)$
is the true path in the original construction. We have to prove that the
strategies fulfil their goals, i.e., the $M_{i}$ strategy ensures that if
$\mathcal{M}_{i}\cong\mathcal{S}$, then $\mathcal{M}_{i}$ is computably
isomorphic to $\mathcal{S}$. The verification of this is exactly as in
Turetsky’s original proof and thus omitted here. We also have to show that the
$N_{\pi}$ strategies together ensure that we compute isomorphisms through a
tree $Q$ isomorphic to $T$. At last we have to prove that every automorphism
computes $\emptyset^{\prime\prime}$. This is done via the following claims.
Let $f$ be the true path through the construction, that is the
lexicographically least path in the priority tree that is visited infinitely
often during the construction.

######  Claim 2.2.

Let $(F,\sigma)\in\mathcal{S}$ with $F\neq\emptyset$. Then
$S_{n}^{\mathcal{S}}(F,\sigma)$ for all $n\in\omega$ if and only if

  1. (1)

$\sigma$ is the image of $\pi$ as declared by some $N_{\pi}$ strategy
$\tau\subset f$,

  2. (2)

for $i\in\omega$ such that $\pi(i)\downarrow$, $W_{f(i)}=\\{1\dots n\\}$ if
$2\nmid\sigma(i)$ and $W_{f(i)}=\omega$ otherwise.

###### Proof.

If $\sigma$ is the image of $N_{\pi}$ as declared by the unique $N_{\pi}$
strategy $\tau\subset f$, then $S_{n}^{\mathcal{S}}(F,\sigma)$ for all
$F\subseteq[\omega]^{<\omega}$ and $n\in\omega$.

On the other hand, if $S_{n}^{\mathcal{S}}(F,\sigma)$ for all $n\in\omega$,
then there is a unique $N_{\pi}$ strategy $\tau$ with $\sigma$ declared the
image of $\pi$ that acts infinitely often. We have that $\tau\subset f$
because if $\tau$ was to the right of the true path then it could grow a
single $\sigma$ only finitely many times before being initialized. Notice that
by induction the map $\pi\mapsto\sigma$ mapping $N_{\pi}$ strategies to their
images $\sigma$ is Lipschitz. Thus $\sigma(i)\downarrow$ for all $i$ such that
$\pi(i)$ is defined. Furthermore, there are unique $\rho_{i}\subseteq\tau$
such that $\rho_{i}$ is a strategy for $R_{i}$. By $\tau$ being on the true
path $\rho_{i}$ has outcome $fin$ if and only if $W_{f(i)}=\\{1\dots n\\}$ for
some $n\in\omega$ and $\rho_{i}$ has outcome $\infty$ if and only if
$W_{f(i)}=\omega$. By construction $2\nmid\sigma(i)$ in the first case and
$2\mid\sigma(i)$ in the second case. ∎

######  Claim 2.3.

For every non-trivial automorphism $g$ of $\mathcal{S}$,
$g\geq_{T}\emptyset^{\prime\prime}$.

###### Proof.

By [Tur20, Claim 2.1] for every automorphism $g$ and every $\sigma$ there is
$H_{\sigma}\in[\omega]^{<\omega}$ such that $g((F,\sigma))=(F\Delta
H_{\sigma},\sigma)$ for all $F\in[\omega]^{<\omega}$. If $g$ is non-trivial
then there must be $\sigma$ such that
$g((\emptyset,\sigma))=(H_{\sigma},\sigma)$ for some $H_{\sigma}\neq\emptyset$
with $S_{n}^{\mathcal{S}}((H_{\sigma},\sigma))$ for all $n\in\omega$. Now, by
2.2, $\sigma$ codes an initial segment of $\emptyset^{\prime\prime}$. We can
now compute $\emptyset^{\prime\prime}$ iteratively as follows. Pick the least
$i\in H_{\sigma}$. We have that
$P^{\mathcal{S}}((\emptyset,\sigma),(\emptyset,\sigma\operatorname{{}^{\smallfrown}}i))$
but $\neg
P^{\mathcal{S}}((H_{\sigma},\sigma),(\emptyset,\sigma\operatorname{{}^{\smallfrown}}i))$,
so in particular
$g((\emptyset,\sigma\operatorname{{}^{\smallfrown}}i))=(H_{\sigma\operatorname{{}^{\smallfrown}}i},\sigma\operatorname{{}^{\smallfrown}}i)$
for some $H_{\sigma\operatorname{{}^{\smallfrown}}i}\neq\emptyset$. As
$S_{n}^{\mathcal{S}}(\emptyset,\sigma_{i})$ for all $n$, also
$S_{n}^{\mathcal{S}}(H_{\sigma\operatorname{{}^{\smallfrown}}i},\sigma\operatorname{{}^{\smallfrown}}i)$
for all $n$. Thus, the strategy declaring
$\sigma\operatorname{{}^{\smallfrown}}i$ has been visited infinitely often and
so $\sigma\operatorname{{}^{\smallfrown}}i\in Q$. By 2.2, $2|i$ if and only if
$i\not\in\emptyset^{\prime\prime}$. Iterate this procedure to compute initial
segments of $\emptyset^{\prime\prime}$ of arbitrary length and thus
$\emptyset^{\prime\prime}$. ∎

Let $\sigma_{\tau}$ be the image of $\tau$ as declared by some $N_{\tau}$
strategy on $f$ and $\sigma_{\rho}$ be the image of $\rho$ as declared by some
$N_{\rho}$ strategy on $f$. Then by choice of $\sigma_{\tau}$, $\sigma_{\rho}$
during the construction $\sigma_{\tau}\preccurlyeq\sigma_{\rho}$ if and only
if $\tau\preccurlyeq\rho$. Let $Q$ be the set of images of the $N_{\pi}$
strategies, then $Q$ is a tree isomorphic to $T$. Notice that
$\mathbf{0}^{\prime\prime}$ can compute the true path and thus
$\\{f\oplus\emptyset^{\prime\prime}:f\in[T]\\}\equiv_{w}[Q]$. To finish the
proof it remains to show the following.

######  Claim 2.4.

The sets $\\{\nu:\nu\in(Aut(\mathcal{S})\setminus\\{id\\})\\}$ and $[Q]$ are
in bijection and Muchnik equivalent.

###### Proof.

This is just [Tur20, Claim 2.2]. ∎

∎

Modifying the structure $\mathcal{S}$ slightly as in [Tur20, Theorem 3] we can
obtain a proof of Theorem 1.

###### Proof of Theorem 1.

Let $\mathcal{S}$ be the structure from Lemma 2. The structure
$\mathcal{S}_{1}$ is obtained by adding two new elements $a_{odd}$ and
$a_{even}$ to $\mathcal{S}$ and a new constant symbol $c$ to its vocabulary.
The structure $\mathcal{S}_{1}$ satisfies

  * •

$P^{\mathcal{S}_{1}}(a_{even},(F,\langle\rangle))$ if and only if $|F|$ is
even,

  * •

$P^{\mathcal{S}_{1}}(a_{odd},(F,\langle\rangle))$ if and only if $|F|$ is odd,

  * •

$c^{\mathcal{S}_{1}}=a_{even}$,

and no other relation holds on $a_{even}$ or $a_{odd}$. Let $\mathcal{S}_{2}$
be identical to $\mathcal{S}_{1}$ except that $c^{\mathcal{S}_{2}}=a_{odd}$.
Turetsky proved that this structure has computable dimension 2 and that every
path through $Q$ computes an isomorphism between $\mathcal{S}_{1}$ and
$\mathcal{S}_{2}$ and vice versa. We will include this here for completeness
and include a proof that this structure is rigid if $[Q]$ is a singleton.
Theorem 1 then follows from the fact that $Q\cong T$ and if
$[T]\geq_{\omega}\\{\emptyset^{\prime\prime}\\}$, then $[T]\equiv_{w}[Q]$.

Note that given $\mathcal{B}$ isomorphic to $\mathcal{S}_{1}$ via $f$, the
substructure of $\mathcal{B}$ that does not contain $f(a_{even})$,
$f(a_{odd})$ in the language of $\mathcal{S}$ is isomorphic to $\mathcal{S}$.
As $\mathcal{S}$ is computably categorical, there is a computable isomorphism
$g$ between this substructures. This isomorphism can be extended to an
isomorphism between $\mathcal{S}_{1}$ and $\mathcal{B}$ by letting
$g(a_{even})=f(a_{even})$ and $g(a_{odd})=f(a_{odd})$. If
$c^{\mathcal{B}}=a_{even}$, this isomorphism is clearly computable. Otherwise,
using a similar argument we obtain a computable isomorphism between
$\mathcal{B}$ and $\mathcal{S}_{2}$.

Notice that every isomorphism $g$ between $\mathcal{S}_{1}$ and
$\mathcal{S}_{2}$ induces a non-trivial automorphism of $\mathcal{S}$ as
$g(a_{even})=a_{odd}$ and hence
$g((\emptyset,\langle\rangle))=(F,\langle\rangle)$ for some non-empty set $F$.
But if $[T]$ is a singleton, then $\mathcal{S}$ has exactly one non-trivial
automorphism. Note, that in this case there is no non-trivial automorphism of
$\mathcal{S}_{1}$, as the only such automorphism of $\mathcal{S}_{1}$ would
map $(\emptyset,\langle\rangle)\mapsto(\\{n\\},\langle\rangle)$ and hence
$c^{\mathcal{S}_{1}}=a_{even}\mapsto a_{odd}\neq C^{\mathcal{S}_{1}}$. Thus,
$\mathcal{S}_{1}$ is rigid. ∎

###  1.2. Treeable degrees

######  Definition 2 ([BKY18]).

For any computable structure $\mathcal{S}$, the _spectral dimension_ of
$\mathcal{S}$ is the least $k\leq\omega$ such that there exists an enumeration
$(\mathcal{A}_{i},\mathcal{B}_{i})_{i<k}$ of pairs of computable copies of
$\mathcal{S}$ such that

$CatSpec(\mathcal{S})=\bigcap_{i<k}\\{deg(X):(\exists
f\leq_{T}X)f:\mathcal{A}_{i}\cong\mathcal{B}_{i}\\}.$

A degree $\mathbf{d}$ is a _strong degree of categoricity_ if there is a
structure $\mathcal{S}$ of spectral dimension $1$ with degree of categoricity
$\mathbf{d}$.

One of the main open questions in the area is whether every degree of
categoricity is strong. Using Theorem 1 we will answer this question for
degrees on the cone above $\mathbf{0}^{\prime\prime}$.

Recall that $P\subseteq\omega^{\omega}$ is a $\Pi^{0}_{1}$ class if there is a
computable tree $T$ with $P=[T]$.

######  Definition 3.

A Turing degree $\mathbf{d}$ is _treeable_ if there is a $\Pi^{0}_{1}$ class
$P$ such that there exists $p\in P$ with $deg(p)=\mathbf{d}$ and
$P\geq_{w}\\{p\\}$.

######  Lemma 3.

Every degree of categoricity is treeable.

###### Proof.

Let $\mathcal{A}$ be a computable structure computed by $\Phi_{e}$ and let
$I(\mathcal{A})=\\{j:\Phi_{j}\cong\mathcal{A}\\}$ be the set of indices of its
computable copies. Then

$deg(f)\in CatSpec(\mathcal{A})\iff\forall j(\exists g\leq_{T}f)(j\in
I(\mathcal{A})\to g:\Phi_{e}\cong\Phi_{j})$

If the above characterization was $\Sigma_{1}^{1}$ we would get a computable
tree witnessing the treeability of the categoricity spectrum of $\mathcal{A}$.
Unfortunately, the set $I(\mathcal{A})$ is only guaranteed to be
$\Sigma^{1}_{1}$ and thus the characterization is in general $\Sigma^{1}_{2}$.

However, Csima, Franklin, and Shore [CFS+13] showed that every degree of
categoricity is hyperarithmetic. If $\mathcal{A}$ has degree of categoricity
$\mathbf{d}$, then $I(\mathcal{A})$ is arithmetical in $\mathbf{d}$ and thus
$\Delta_{1}^{1}$. So, if $\mathbf{d}$ is the degree of categoricity of a
structure $\mathcal{A}$, then $CatSpec(\mathcal{A})$ is $\Sigma_{1}^{1}$ and
thus the set of paths through a computable tree. This tree has $\mathbf{d}$ as
its Turing least path and so $\mathbf{d}$ is treeable. ∎

Clearly, if a structure $\mathcal{S}$ has computable dimension $2$, then it
has spectral dimension $1$ and thus any degree of categoricity of a structure
with computable dimension $2$ must be strong. We thus obtain the following
from Theorem 1.

######  Corollary 4.

Let $\mathbf{d}\geq\mathbf{0}^{\prime\prime}$. Then $\mathbf{d}$ is a degree
of categoricity if and only if it is treeable.

######  Corollary 5.

Every degree of categoricity above $\mathbf{0}^{\prime\prime}$ is strong.

######  Question 1.

Is every treeable degree the degree of categoricity of a structure?

Which degrees are treeable? Recall that $f\in\omega^{\omega}$ is a
$\Pi^{0}_{1}$ function singleton if there is a tree $T$ with $[T]=\\{f\\}$.
Clearly degrees that contain $\Pi^{0}_{1}$ function singletons are treeable
degrees and one can find plenty of examples of those in the literature. Let us
summarize.

Abusing notation we say that a degree $\mathbf{d}$ is a $\Pi^{0}_{1}$ function
singleton if it contains a $\Pi^{0}_{1}$ function singleton. We now list
examples of classes of degrees that are $\Pi^{0}_{1}$ function singletons and
thus by Theorem 1 degrees of categoricity of rigid structures with computable
dimension $2$.

Most of these examples are obtained using the following trick due to Jockusch
and McLaughlin [JM69]. Let $X$ be a $\Pi^{0}_{2}$ singleton, i.e., the only
solution to a $\Pi^{0}_{2}$ predicate. Then it is defined by a formula
$\forall u\exists vR(u,v,X)$ which can be rewritten as

$\forall
u\exists(v>u)\forall(x<v)R(u,v,\chi_{X}\operatorname{\upharpoonright}x)$

where $R(u,v,\chi_{X}\operatorname{\upharpoonright}x)$ implies
$R(u,v,\chi_{X}\operatorname{\upharpoonright}y)$ for $y<x$. Let $f(u)$ be the
string $\sigma\preceq\chi_{A}$ of length $\mu v[R(u,v,\sigma)]$. Then
$f\leq_{T}A$ by definition and $A\leq_{T}f$ as the length of the strings in
the range of $f$ is unbounded. The function $f$ itself is a $\Pi^{0}_{1}$
singleton as it is the unique solution to the equation

$\forall x(f(x)\in 2^{<\omega}\land R(x,|f(x)|,f(x)))\land\forall(\tau\preceq
f(x))\neg R(x,|\tau|,\tau).$

So, a degree $\mathbf{d}$ contains a $\Pi^{0}_{1}$ function singleton if and
only it contains a $\Pi^{0}_{2}$ singleton. The following theorem is well
known.

######  Lemma 6 (folklore, see [Sac90, Section II.4.]).

For all computable ordinals $\alpha$, $\mathbf{0}^{(\alpha)}$ is a
$\Pi^{0}_{1}$ function singleton.

######  Lemma 7 (folklore, see [Odi99]).

If $\mathbf{d}$ is a $\Pi^{0}_{1}$ function singleton, then so is every
$\mathbf{c}$ with $\mathbf{d}\leq\mathbf{c}\leq\mathbf{d}^{\prime}$.

###### Proof.

Let $D\in\mathbf{d}$ be a $\Pi^{0}_{2}$ singleton defined via $\varphi(X)$ and
let $C\in\mathbf{c}$, then $C$ is limit computable from $D$, say via the
$\Delta^{0}_{2}$ function $\psi(X,y)$. Consider the set $C\oplus D$. It is the
unique solution to the formula

$\varphi(X_{odd})\land\left(\psi(X_{odd},y)\leftrightarrow 2y\in X\right)$

where $X_{odd}=\\{x:2x+1\in X\\}$. Using the above trick we get that the
degree $\mathbf{c}$ of $C\oplus D$ is a $\Pi^{0}_{1}$ function singleton. ∎

Combining Lemma 6 for $\alpha\geq 2$ with Lemma 7 and Theorem 1 we get a new
class of degrees that are degrees of categoricities and answer a question
posed by Csima and Ng [CN22].

######  Corollary 8.

Fix $\alpha>2$ and let $\mathbf{d}$ be such that
$\mathbf{0}^{(\alpha)}\leq\mathbf{d}\leq\mathbf{0}^{(\alpha+1)}$, then there
is a computable rigid structure $\mathcal{S}$ with computable dimension $2$
such that $dgCat(\mathcal{S})=\mathbf{d}$.

We can get even more. Harrington [Har76] showed the existence of a
$\Pi^{0}_{2}$ singleton $A$ that is not arithmetical and such that
$A^{(n)}\not\geq\emptyset^{(\omega)}$ for all $n$. While the degree of $A$
itself might not satisfy the conditions of Corollary 4 we can take
$A^{\prime\prime}$ to obtain the following.

######  Corollary 9.

There exists a non-arithmetic degree $\mathbf{d}$,
$\mathbf{d}\not\geq\mathbf{0}^{(\omega)}$, such that for all $n\in\omega$ and
$\mathbf{c}\in[\mathbf{d}^{(n)},\mathbf{d}^{(n+1)}]$ is the degree of
categoricity of a rigid structure with computable dimension $2$.

It is also not hard to give examples of degrees that are not treeable degrees
by looking at sufficiently generic degrees. This is not surprising as examples
of degrees that are not degrees of categoricity are usually obtained by
building degrees that are sufficiently generic [AC12, FS14].

######  Lemma 10.

Let $\mathbf{d}$ be sufficiently generic, then $\mathbf{d}$ is not treeable.

###### Proof.

Let $T$ be a tree with Turing-least element of degree $\mathbf{d}$ and let

(1) $\varphi(x)\iff\exists i\forall
n\,\Phi_{i}^{x}\operatorname{\upharpoonright}n\in T\land\forall i(\forall
n\,\Phi_{i}^{x}\operatorname{\upharpoonright}n\in T\to x\leq_{T}\Phi_{i}^{x})$

Since $x\leq_{T}\Phi_{i}^{x}$ is $\Sigma^{0}_{3}$, $\varphi(x)$ is
$\Pi^{0}_{4}$. Furthermore, $\varphi(f)$ if and only if $deg(f)=\mathbf{d}$.
So, say $g\in\mathbf{d}$ is $4$-generic, then there is $\sigma\subset p$ such
that $\sigma\Vdash\varphi(x)$. But then for all $f\supset\sigma$ $\varphi(f)$
and we can choose such $f$ to be Turing incomparable with $g$. Thus
$\mathbf{d}$ is not treeable. ∎

######  Proposition 11.

For every computable ordinal $\alpha$, there is a hyperarithmetic degree
$\mathbf{d}$ with $\mathbf{d}\geq\mathbf{0}^{(\alpha)}$ that is not a degree
of categoricity.

###### Proof.

Let $\psi(x)$ be given similar to $\varphi(x)$ as defined in Eq. 1 but replace
$x$ with $x^{(\alpha)}$. Let $\mathbf{c}$ be a hyperarithmetic
$(\alpha+4)$-generic degree, then $\mathbf{c}^{(\alpha)}$ is not a degree of
categoricity as it is not treeable by the same argument as in Lemma 10 with
$\psi(x)$ in place of $\varphi(x)$. ∎

Note that by Eq. 1 in the proof of Lemma 10 every treeable degree is a
countable $\Pi^{0}_{4}$ class. Tanaka [Tan72] showed that every countable
$\Sigma^{0}_{n+1}$ class contains a $\Pi^{0}_{n}$ singleton. So, in
particular, if $\mathbf{d}$ is treeable, then it contains a $\Pi^{0}_{4}$
singleton.

######  Proposition 12.

Every degree of categoricity contains a $\Pi^{0}_{4}$ singleton.

##  2\. Degrees of categoricity in
$[\mathbf{0}^{\prime},\mathbf{0}^{\prime\prime}]$

In this section we show that all degrees between $\mathbf{0}^{\prime}$ and
$\bf{0^{\prime\prime}}$ are degrees of categoricity. In [FKM10], Fokina,
Kalimullin and Miller showed that every degree d.c.e. in and above
$\mathbf{0}^{(n)}$ for some $n$ is a degree of categoricity. They did this by
noting that their proof that every d.c.e. degree is a degree of categoricity
relativises to give that every degree d.c.e. in and above a given degree is a
degree of categoricity _relative to the given degree_ , and then using Marker
extensions to get the desired result. Now that Csima and Ng have shown that
every $\Delta^{0}_{2}$ degree is a degree of categoricity in [CN22], we can
verify that the methods of Fokina, Kalimullin and Miller also apply in this
case, and obtain the desired result.

To begin, we give the definition of a categoricity spectrum relative to a
degree.

######  Definition 4.

Let $\tau$ be a computable vocabulary, let $\bf{c}$ be a Turing degree, let
$\mathcal{A}$ be a $\bf{c}$-computable $\tau$-structure, and let
$(\mathcal{B}_{e})_{e\in\omega}$ be an enumeration of all $\bf{c}$-computable
$\tau$-structures. The _categoricity spectrum of $\mathcal{A}$ relative to
$\bf{c}$_ is the set

$CatSpec_{\bf{c}}(\mathcal{A})=\bigcap_{e\in\omega:\mathcal{B}_{e}\cong\mathcal{A}}\\{deg(X):(\exists
f:\mathcal{A}\cong\mathcal{B}_{e})X\geq_{T}f\\}.$

The proof given in Theorem 5.9 of [FKM10] shows that if ${\bf
d}\geq_{T}{\mathbf{0}^{(m)}}$, and if there exists a
$\mathbf{0}^{(m)}$-_acceptable_ structure $\mathcal{M}$ with
$CatSpec_{\mathbf{0}^{(m)}}(\mathcal{M})$ the upper cone above ${\bf d}$, then
${\bf d}$ is a strong degree of categoricity. A
$\mathbf{0}^{(m)}$-_acceptable_ structure is one with a
$\mathbf{0}^{(m)}$-computable copy in which all predicates have an infinite
computable subset. So it remains to argue that if
$\mathbf{0}^{\prime}<\mathbf{d}<\mathbf{0}^{\prime\prime}$, then there is a
${\mathbf{0}^{(1)}}$-_acceptable_ structure $\mathcal{M}$ with
$CatSpec_{\mathbf{0}^{(1)}}(\mathcal{M})$ the upper cone above ${\bf d}$.

We now consider the proof given in [CN22] that every $\Delta^{0}_{2}$ degree
is a strong degree of categoricity. It proceeds by considering a
$\Delta^{0}_{2}$ appoximation to a set $D\in{\bf d}$, an effective list of the
possible computable structures, and builds the structures $\mathcal{A}$ and
$\hat{\mathcal{A}}$ that witness ${\bf d}$ as a strong degree of categoricity
in a stage-by-stage construction. Though the proof as described in the paper
uses infinitely many relation symbols, it is noted that this is just a
convenience - the structure can be easily converted into a graph using
standard codings. Running the construction relative to an oracle
$\mathbf{0}^{\prime}$, for a degree ${\bf d}\geq{\bf 0^{\prime}}$ that is
$\Delta^{0}_{2}$ in ${\bf 0^{\prime}}$ (i.e.,
$\mathbf{0}^{\prime}\leq\mathbf{d}\leq\mathbf{0}^{\prime\prime}$), and
adjoining the standard copy of a structure with strong degree of categoricity
$\mathbf{0}^{\prime}$ then yields a structure with strong degree of
categoricity ${\bf d}$ relative to $\mathbf{0}^{\prime}$. Moreover, when we
transform the presentation into a graph, we easily obtain the infinite
computable subset of the edge relation required to guarantee an acceptable
copy of the structure \- they occur as we mark off the independent modules
where the different requirements will act. Combining this with Corollary 8 and
Csima and Ng’s result we obtain the following.

######  Theorem 13.

Every degree $\mathbf{d}$ with
$\mathbf{0}^{(\alpha)}\leq\mathbf{d}\leq\mathbf{0}^{(\alpha+1)}$ for some
computable ordinal $\alpha$ is the degree of categoricity of a computable
structure.

##  3\. Not the degree of categoricity of a rigid structure

Corollary 8 shows that for $\alpha>2$, every degree $\mathbf{d}$ between
$\mathbf{0}^{(\alpha)}$ and $\mathbf{0}^{(\alpha+1)}$ is the degree of
categoricity of a rigid structure. Bazhenov and Yamaleev showed that there is
a $2$-c.e. degree that is not the degree of categoricity of a rigid stucture
[BY17]. In this section we prove the following theorem.

######  Theorem 14.

There is a degree $\mathbf{d}$,
$\mathbf{0}^{\prime}<\mathbf{d}<\mathbf{0}^{\prime\prime}$, that is not the
degree of categoricity of a rigid structure.

Theorem 14 shows a limitation to Turetsky’s technique of coding paths through
trees into the automorphisms of a structure: If one were to code treeable
degrees below $\mathbf{0}^{\prime\prime}$, one would not be able to preserve
the 1-1 correspondence between automorphisms and paths through the tree.

The main ingredient of the proof of Theorem 14 is the following lemma. Its
proof combines Bazhenov and Yamaleev’s construction with a true stage
argument.

######  Lemma 15.

There exists a degree $deg(D)$,
$\mathbf{0}^{\prime}<deg(D)<\mathbf{0}^{\prime\prime}$ that satisfies the
following: for all computable structures $\mathcal{A}$ and $\mathcal{B}$ and
all $\Delta^{0}_{3}$ isomorphisms $g:\mathcal{A}\cong\mathcal{B}$,
$deg(D)=deg(g)$ implies that there is a computable structure $\mathcal{N}$ and
an isomorphism $f:\mathcal{A}\cong\mathcal{N}$ with $deg(f)\not\leq deg(D)$.

Notice that Lemma 15 already shows that there is a degree
$\mathbf{d}\in(\mathbf{0}^{\prime},\mathbf{0}^{\prime\prime})$ that is not the
strong degree of categoricity of any rigid structure.

###### Proof of Lemma 15.

Let $g\leq\mathbf{0}^{\prime\prime}$, then $g$ is limit computable in
$\mathbf{0}^{\prime}$. Assume that we have an approximation to
$\emptyset^{\prime}$ in terms of finite strings $\sigma_{i}$ where

$|\sigma_{i}|=\min\\{\mu
x[x\operatorname{\searrow}\emptyset^{\prime}_{i}],i\\}\quad\text{ and
}\quad(\sigma_{i}(x)\downarrow\Rightarrow\sigma_{i}(x)=\emptyset^{\prime}_{i}(x)).$

Let the triple $(\mathcal{A},\mathcal{B},g)$ consist of computable graphs
$\mathcal{A}$, $\mathcal{B}$ and a $\Delta^{0}_{2}(\emptyset^{\prime})$
function $g$. Then we may approximate this triple via the triples
$(\mathcal{A}[s],\mathcal{B}[s],g[s])$ where $\mathcal{A}[s]$ and
$\mathcal{B}[s]$ are substructures of $\mathcal{A}$, respectively
$\mathcal{B}$, with universe $\\{0,\dots,s\\}$, and, say that $g$ is limit
computable via $\Phi_{e}^{\emptyset^{\prime}}$, then
$g[s](x)=\Phi_{e}^{\sigma_{s}}(x,t)$ where
$t=\max\\{r<s:\Phi_{e,s}^{\sigma_{s}}(x,r)\downarrow\\}$. Note that it is not
necessarily the case that $\lim_{s\to\infty}g[s]=g$. However, if $i_{0},\dots$
is a sequence of true stages in our approximation to $\emptyset^{\prime}$,
then $\lim_{s\to\infty}g[i_{s}]=g$. We will work with an enumeration of the
approximations of all such triples
$(\mathcal{A}_{e},\mathcal{B}_{e},g_{e})_{e\in\omega}$. Our construction will
build a set $D$, $\emptyset^{\prime}\leq_{T}D\leq_{T}\emptyset^{\prime\prime}$
and ensure that if $g_{e}:\mathcal{A}_{e}\cong\mathcal{B}_{e}$ and
$g_{e}\equiv_{T}D$, then there is a computable structure
$\mathcal{N}_{e}\cong\mathcal{A}_{e}$ and an isomorphism
$f_{e}:\mathcal{N}_{e}\cong\mathcal{A}_{e}$ such that $f_{e}\not\leq_{T}D$.
That is, for every $e$ we aim to satisfy the following infinite set of
requirements

$S_{e,i}:\quad\left(g_{e}:\mathcal{A}_{e}\cong\mathcal{B}_{e}\land
g_{e}\in\Delta^{0}_{3}\land D=\Phi_{e}^{g_{e}}\land
g_{e}=\Theta_{e}^{D}\right)\Rightarrow f_{e}\neq\Phi_{i}^{D}$

and the global requirement

$G:\emptyset^{\prime}\leq_{T}D.$

The requirement $G$ is satisfied by building
$D=\hat{D}\oplus\emptyset^{\prime}$.

Given $\sigma,\tau\in 2^{<\omega}$ we say that $\tau$ is _$\sigma$ -true_, if
$\tau\preceq\sigma$. We call a stage $t$ an $s$-true stage if the stage $t$
approximation $\sigma_{t}$ is $\sigma_{s}$-true. The key difference of our
construction to Bazhenov and Yamaleev’s construction is that at stage $s$ we
only consider the work of strategies acting at $\sigma_{s}$-true stages to
build $D$.

For people who have seen that construction it might be easy to see that
satisfying $\mathcal{S}_{e,i}$ using true stages gives a set that is
$\Delta^{0}_{2}(\emptyset^{\prime})$ and can not be the degree of categoricity
of a rigid structure.

The difficulty arises from coding $\emptyset^{\prime}$. The key argument for
the coding is that if we take $D=\hat{D}\oplus\emptyset^{\prime}$, then the
computation $\Psi_{i}^{D}$ might only change finitely many times at any $x$
given that we preserve finite injury of $\hat{D}$ on the true path. This is
because at some point in the approximation of $\emptyset^{\prime}$ no bit
lower than the use of $\Psi_{i}^{D}(x)$ will change anymore. Thus, if at that
point we have ensured that on the true path $\Psi_{i}^{D}(x)\neq f_{e}$, then
this will hold in the limit. However, with more complicated sets, such as
$\emptyset^{\prime\prime}$ this is not true anymore.

Let $i_{0},\dots$ be the sequence of true stages for $\emptyset^{\prime}$.
Together with $D=\lim_{j\to\omega}D[i_{j}]$ we will build
$\mathcal{N}_{e}=\lim_{j\to\omega}\mathcal{N}_{e}[j]$. Say that a stage $s$ in
the construction is $e$-expansionary if
$\mathcal{N}_{e}[s+1]\neq\mathcal{N}_{e}[s]$. An $e$-expansionary stage is
always caused by some strategy that tries to satisfy $S_{e,i}$. Let $s$ be an
$e$-expansionary stage, then $\mathcal{N}_{e}[s]$ will have universe
$\\{0,\dots,s\\}$ and will embed into $\mathcal{A}_{e}$. Say we are at some
stage $s$, and $t<s$ is $e$-expansionary. The strategy acting for a
requirement $S_{e,i}$ might force us to change the embedding $f_{e}[t]$
because $g_{e}[s]\neq g_{e}[t]$. There are two ways we can do this.

${\mathcal{A}_{e}[s]}$${\mathcal{A}_{e}[t]}$${\mathcal{B}_{e}[s]}$${\mathcal{N}_{e}[s]}$${\mathcal{N}_{e}[t]}$$\scriptstyle{g_{e}[s]}$$\scriptstyle{g_{e}[t]}$$\scriptstyle{id}$$\scriptstyle{id\circ
f_{e}[t]\circ id^{-1}}$$\scriptstyle{g_{e}[s]^{-1}\circ g_{e}[t]\circ
f_{e}[t]\circ id^{-1}}$$\scriptstyle{f_{e}[t]}$$\scriptstyle{id}$

We can extend any partial embedding of $\mathcal{N}_{e}[s]$ into
$\mathcal{A}_{e}[s]$ by recursively mapping elements not in the domain to the
least element not in the range as $N_{e}[s]=A_{e}[s]=\\{0,\dots,s\\}$. We say
that $f_{e}[s]$ is the _id-extension_ of $f_{e}[t]$ if it is obtained by
extending $id\circ f_{e}[t]\circ id^{-1}$ and $f_{e}[s]$ is a _g-extension_ of
$f_{e}[t]$ if it is obtained by extending $g_{e}[s]^{-1}\circ g_{e}[t]\circ
f_{e}[t]\circ id^{-1}$. Note that we can take _g-extensions_ because
technically $g_{e}[t]:\mathcal{A}_{e}[t]\rightarrow\mathcal{B}_{e}[t]$ and
$\mathcal{B}_{e}[t]\subseteq\mathcal{B}_{e}[s]$.

We use upper case greek letters to denote Turing operators and the
corresponding lower case greek letters to denote their use. We abuse notation
and do not write the oracle in the use function as the oracle will be implied
from the context. As we are only interested in total functions we can make the
following assumption on uses without loss of generality: If
$\Phi^{X}(x)\downarrow$, then for all $y<x$, $\Phi^{X}(y)\downarrow$ and
$\varphi(y)<\varphi(x)$. During the construction we will use the following
length agreement functions:

$L(e)[s]=\max\bigg{\\{}x:\forall(y\leq
x)\Big{[}\Phi_{e}^{g_{e}}(y)[s]=D[s](y)\land\\\
\forall(z<\varphi_{e}(y)[s])\left(\Theta_{e}^{D}(z)[s]=g_{e}(z)[s]\land(\\{0,\dots,\varphi_{e}(y)[s]\\}\subseteq\mathcal{A}_{e}[s])\right)\Big{]}\bigg{\\}}$
$l(e,i)[s]=\max\\{x:\forall(y\leq x)(f_{e}(y)[s]=\Psi_{i}^{D}(y)[s])\\}$

The priority ordering on our requirements is given by
$S_{e,i}<S_{e^{\prime},i^{\prime}}$ if and only if $\langle e,i\rangle<\langle
e^{\prime},i^{\prime}\rangle$. If the above is true, we say that $S_{e,i}$ has
higher priority than $S_{e^{\prime},i^{\prime}}$. Assume we are at stage $s$
of the construction and let $t$ be the last $s$-true stage. At the beginning
of $s$ we let $D[s]=D[t]$. A strategy $S_{e,i}$ might require attention
because of the following reasons:

  1. (1)

Its witness $x_{e,i}$ is undefined.

  2. (2)

$x_{e,i}\not\in D[s]$, $x_{e,i}<L(e)[s]$, and $f_{e}(y)$ is undefined for some
$y<\varphi_{e}(x_{e,i})[s]$.

  3. (3)

$x_{e,i}\not\in D[s]$, $x_{e,i}<L(e)[s]$, and
$\varphi_{e}(x_{e,i})[s]<l(e,i)[s]$.

  4. (4)

$x_{e,i}\in D[s]$ and $x_{e,i}<L(e)[s]$.

#### Construction.

At stage $0$ define $D[0]=\emptyset$, $\mathcal{N}_{e}=\emptyset$ and
$f_{e}=\emptyset$ for all $e\in\omega$. Say we are at stage $s>0$ of the
construction. Let $D[s]=D[t]$ and then enumerate $2x+1$ into $D[s]$ for all
$x$ such that $x\in\emptyset^{\prime}_{s}$. Find the least requirement that
requires attention and initialize all lower priority strategies. Then choose
the following depending on what caused the attention.

  1. (1)

Define $x_{e,i}$ to be an even number larger than all numbers used in the
construction so far.

  2. (2)

Let $s^{-}$ be the last $e$-expansionary stage. Define $\mathcal{N}_{e}[s]$
and $f_{e}[s]$ as the $id$-extension of $f_{e}[s^{-}]$.

  3. (3)

Enumerate $x_{e,i}$ into $D[s]$.

  4. (4)

Extract $x_{e,i}$ from $D[s]$. Let $s^{-}$ be the last $e$-expansionary stage.
Define $\mathcal{N}_{e}[s]$ and $f_{e}[s]$ as the $g$ extension of
$f_{e}[s^{-}]$.

#### Verification.

We first verify the construction for a single requirement $S_{e,i}$ in
isolation. Say $S_{e,i}$ acts for the first time at stage $s_{0}$ and picks
$x_{e,i}$. Notice that as $S_{e,i}$ will never be initialized it won’t ever
act again because of reason (1). Now, say that $s_{1}>s_{0}$ is a true stage
such that
$\emptyset^{\prime}_{s_{0}}\operatorname{\upharpoonright}x_{e,i}/2=\emptyset^{\prime}\operatorname{\upharpoonright}x_{e,i}/2$.
By our isolation assumption the bits below $x_{e,i}$ in our approximation to
$D$ won’t change anymore after $s_{1}$.

Say $S_{e,i}$ needs attention because of reason (2) at true stage
$s_{2}>s_{1}$. We do an $id$-extension of $f_{e}[s^{-}]$. Such an extension
can always be done because $f_{e}:\mathcal{N}_{e}\to\mathcal{A}_{e}[s^{-}]$
and $\mathcal{A}_{e}[s^{-}]\subseteq\mathcal{A}_{e}[s_{2}]$. If $S_{e,i}$
never needs attention again we have satisfied $S_{e,i}$. Now, say that $s_{3}$
is a true stage such that $S_{e,i}$ receives attention. Then this can not be
because of reason (2) because if $x_{e,i}<L(e)[s_{3}]$, then
$\Theta^{D}_{e}(z)[s_{3}]=\Theta^{D}_{e}(z)[s_{2}]=g_{e}[s]$ for all
$z<\varphi_{e}(x_{e,i})[s]$ and so
$\varphi_{e}(x_{e,i})[s_{2}]=\varphi_{e}(x_{e,i})[s_{3}]$ and we have already
extended $f_{e}$ at $s_{2}$. Thus $S_{e,i}$ must act because of reason (3) and
so $x_{e,i}$ is enumerated into $D$ at stage $s_{3}$. Notice that, since
$s_{3}$ is a true stage, for every $t\geq s_{3}$, $s_{3}$ is $t$-true. Let
$s_{4}$ be the next true stage such that $S_{e,i}$ receives attention. Notice
that this must be because of reason (4) as $x_{e,i}\in D[s_{4}]$. We extract
$x_{e,i}$ from $D$ and do a $g$-extension hoping to diagonalize against
$\Psi_{i}^{D}$ computing $f_{e}$. It might be the case that there is a stage
$t$ (not necessarily a true stage), $s_{3}<t<s_{4}$ such that $t=s_{4}^{-}$,
$g_{e}[t]\subseteq g_{e}[s_{4}]$ and the $g$-extension of $f_{e}[t]$ is an
$id$-extension. Say $S_{e,j}$ does the $g$-extension at $t$, then $S_{e,j}$ is
not of higher priority than $S_{e,i}$ as otherwise $S_{e,i}$ would have been
reset. But then $L(e)[t]>x_{e,j}>x_{e,i}$ and thus $S_{e,j}=S_{e,i}$. So,
after doing the $g$-extension at $s_{4}$ we have that

$f_{e}[s_{4}]\supseteq f_{e}[t]\neq
f_{e}[s_{3}]=\Psi_{i}^{D}[s_{3}]\subseteq\Psi_{i}^{D}[s_{4}].$

So we have successfully diagonalized and given that $D$ does not change below
$x_{e,i}$ anymore $\Psi_{i}^{D}\neq f_{e}$.

We have that $x_{e,i}>L(e)[s_{4}+1]$. This allows $g_{e}$ to change and
achieve that $L(e)[s_{5}]>x_{e,i}$ at some stage $s_{5}$. The risk is that
$\varphi_{e}(x_{e,i})[s_{5}]<\varphi_{e}(x_{e,i})[s_{4}]$ and that thus we
might want to take action because of $(3)$ again. Notice that this would imply
that $g_{e}$ changed below $\varphi_{e}(x_{e,i})[s_{4}]$. But at $s_{4}$ we
had that

$\forall(z<\varphi_{e}(x_{e,i})[s_{4}])(\Theta_{e}^{D}(z)[s_{4}]=g_{e}(z)[s_{4}]).$

So this is particularly true for all $z<\varphi_{e}(x_{e,i})[s_{5}]$. By our
assumption on use functions $\varphi$ that $x<y$ implies
$\varphi(x)<\varphi(y)$ we have that

$\theta_{e}(\varphi_{e}(x_{e,i})[s_{5}])<\theta_{e}(\varphi_{e}(x_{e,i})[s_{4}])\leq
x_{e,i}$

and as
$D[s_{4}]\operatorname{\upharpoonright}x_{e,i}=D[s_{5}]\operatorname{\upharpoonright}x_{e,i}$,

$\forall(z<\varphi_{e}(x_{e,i})[s_{5}])(\Theta_{e}^{D}(z)[s_{4}]=g_{e}(z)[s_{5}]=g_{e}(z)[s_{4}])$

contradicting that $g_{e}$ changed below $\varphi_{e}(x_{e,i})$. Notice that a
true stage $t$ is $s$-true for all $s>t$. Thus, in isolation, $S_{e,i}$ will
never require attention after stage $s_{4}$.

We now drop the isolation assumption. Notice first that if $t>s_{4}$ and
$f_{e}[t]\operatorname{\upharpoonright}\varphi_{e}(x_{e,i})[s_{4}]\neq
f_{e}[s_{4}]\operatorname{\upharpoonright}\varphi_{e}(x_{e,i})[s_{4}]$, then
by the argument in the above paragraph this can only have happened because of
a $g$-extension of a higher priority argument which would cause $S_{e,i}$ to
initialize. Let us show that no requirement is initialized infinitely often.
Recall that in isolation every requirement requires attention at most $4$
times on the true path. Using the fact that every true stage $t$ is $s$-true
for all $t>s$ we can see by induction that for every requirement there is a
stage after which it is not initialized again. By the same argument, there is
a stage $t$ such that if $S_{e,i}$ requires attention at $s>t$, then it is the
highest priority requirement needing attention and thus will receive attention
at $s$.

Notice, that if the lefthand side of the implication in $S_{e,i}$ is true,
then $\mathcal{N}_{e}$ is necessarily infinite and isomorphic to
$\mathcal{A}_{e}$ as for every $i$, $S_{e,i}$ receives attention because of
condition (2) at least once. Furthermore, no $\Psi_{i}^{D}$ can compute
$f_{e}$, by our above argument. So, every requirement $S_{e,i}$ is satisfied.
The requirement $G$ is trivially satisfied in the limit. ∎

######  Lemma 16.

A degree $\mathbf{d}$ is a degree of categoricity of a rigid structure if and
only if it is the strong degree of categoricity of a rigid structure.

###### Proof.

The direction from right to left is trivial. For the other direction recall
that the spectral dimension of a rigid structure is finite [BKY16, Theorem
3.1]. So say $\mathcal{A}$ is a rigid structure with spectral dimension
$\alpha$, $1<\alpha<\omega$ and consider the cardinal sum
$\bigotimes\mathcal{A}$, i.e., if $\tau$ is the vocabulary of $\mathcal{A}$,
then $\tau^{+}=\tau\cup\\{R_{i}/1:\in\omega\\}$ is the vocabulary of
$\bigotimes\mathcal{A}$, and every column $R_{i}^{\bigotimes\mathcal{A}}$ is
isomorphic to a copy of $\mathcal{A}$. $\bigotimes\mathcal{A}$ is clearly
computably presentable and rigid. Furthermore, if $\mathcal{A}$ has degree of
categoricity $\mathbf{d}$, then there are computable copies
$\mathcal{A}_{n,1}$, $\mathcal{A}_{n,2}$, $n<\alpha$ and unique isomorphisms
$f_{n}:\mathcal{A}_{n,1}\to\mathcal{A}_{n,2}$ such that $\bigoplus
deg(f_{n})=\mathbf{d}$. Consider the structures
$(\bigotimes\mathcal{A})_{1}\cong(\bigotimes\mathcal{A})_{2}\cong\bigotimes\mathcal{A}$
such that $n\mapsto\langle i,n\rangle$ are uniformly computable isomorphisms
between $\mathcal{A}_{(i\mod\alpha),j}$ and the $i$th column of
$(\bigotimes\mathcal{A})_{j}$. Then
$(\bigotimes\mathcal{A})_{1},(\bigotimes\mathcal{A})_{2}$ witness that
$\mathbf{d}$ is the strong degree of categoricity of a rigid structure. ∎

Since Lemma 16 shows that every degree of categoricity of a rigid structure is
the strong degree of categoricity of a rigid structure and Lemma 15 shows that
there is a degree that is not the strong degree of a rigid structure we
immediately get Theorem 14.

## References

  * [AC12] Bernard A. Anderson and Barbara F. Csima  “Degrees That Are Not Degrees of Categoricity”, 2012  arXiv: http://arxiv.org/abs/1210.4220
  * [BKY16] Nikolay Alekseevich Bazhenov, I. Kalimullin and Mars Mansurovich Yamaleev  “Degrees of Categoricity vs. Strong Degrees of Categoricity”  In _Algebra and Logic_ 55.2, 2016, pp. 173–177  URL: http://link.springer.com/content/pdf/10.1007/s10469-016-9385-6.pdf
  * [BKY18] Nikolay A. Bazhenov, Iskander Sh Kalimullin and Mars M. Yamaleev  “Degrees of Categoricity and Spectral Dimension”  In _The Journal of Symbolic Logic_ 83.1, 2018, pp. 103–116
  * [BY17] Nikolay A. Bazhenov and Mars M. Yamaleev  “Degrees of Categoricity of Rigid Structures”  In _Conference on Computability in Europe_ Springer, 2017, pp. 152–161
  * [CFS+13] Barbara F. Csima, Johanna NY Franklin and Richard A. Shore  “Degrees of Categoricity and the Hyperarithmetic Hierarchy”  In _Notre Dame Journal of Formal Logic_ 54.2, 2013, pp. 215–231  URL: http://projecteuclid.org/euclid.ndjfl/1361454975
  * [CN22] Barbara F. Csima and Keng Meng Ng  “Every $\Delta^{0}_{2}$ Degree Is a Strong Degree of Categoricity”  In _Journal of Mathematical Logic_ , 2022
  * [Csi+18] Barbara F. Csima, Michael Deveau, Matthew Harrison-Trainor and Mohammad Assem Mahmoud  “Degrees of Categoricity above Limit Ordinals”  In _Computability_ IOS Press, 2018, pp. 1–11
  * [FKM10] Ekaterina Fokina, Iskander Kalimullin and Russell Miller  “Degrees of Categoricity of Computable Structures”  In _Archive for Mathematical Logic_ 49.1, 2010, pp. 51–67  URL: http://www.springerlink.com/index/W3J4V27000575230.pdf
  * [Fra17] Johanna NY Franklin  “Strength and Weakness in Computable Structure Theory”  In _Computability and Complexity_ Springer, 2017, pp. 302–323
  * [FS14] Johanna NY Franklin and Reed Solomon  “Degrees That Are Low for Isomorphism”  In _Computability_ 3.2 IOS Press, 2014, pp. 73–89
  * [FS56] Albrecht Fröhlich and John C. Shepherdson  “Effective Procedures in Field Theory”  In _Philosophical Transactions of the Royal Society of London A: Mathematical, Physical and Engineering Sciences_ 248.950, 1956, pp. 407–432  URL: http://rsta.royalsocietypublishing.org/content/248/950/407.short
  * [Gon80] S.. Goncharov  “Problem of the Number of Non-Self-Equivalent Constructivizations”  In _Algebra and Logic_ 19.6, 1980, pp. 401–414  URL: http://www.springerlink.com/index/N65V717103720280.pdf
  * [Har76] Leo Harrington  “Arithmetically Incomparable Arithmetic Singletons”, 1976
  * [JM69] Carl Jockusch and Thomas McLaughlin  “Countable Retracing Functions and $\Pi^{0}_{2}$ Predicates”  In _Pacific Journal of Mathematics_ 30.1, 1969, pp. 67–93
  * [Mal62] A.. Maltsev  “On Recursive Abelian Groups”  In _Soviet Mathematics. Doklady_ 3, 1962
  * [Odi99] P Odifreddi  “Classical Recursion Theory, Volume II” 143, Studies in Logic and the Foundations of Mathematics, 1999
  * [Sac90] Gerald E. Sacks  “Higher Recursion Theory”  Cambridge University Press, 1990  URL: https://www.google.com/books?hl=el&lr=&id=0zMoDgAAQBAJ&oi=fnd&pg=PA1&dq=sacks+higher+recursion+theory&ots=IDwfndsQGF&sig=D52CKNtLflVS9LwdMkVWQLDwn9A
  * [Tan72] Hisao Tanaka  “A Property of Arithmetic Sets”  In _Proceedings of the American Mathematical Society_ 31.2, 1972, pp. 521–524
  * [Tur20] Dan Turetsky  “Coding in the Automorphism Group of a Computably Categorical Structure”  In _Journal of Mathematical Logic_ 20.03 World Scientific Publishing Co., 2020  DOI: 10.1142/S0219061320500166


# On the plane and its coloring

Jaan Parts

(Kazan, Russia<EMAIL_ADDRESS>
###### Abstract

We provide a human-verifiable proof that, in a certain sense, the chromatic
number of the plane is exactly 7.

##  1 Introduction

It is generally accepted that the rainbow contains seven colors. Although in
the traditions of different nations, the sets of these colors are different.
According to the legend, Isaac Newton identified five primary colors: red,
yellow, green, blue and violet. Later, he added two more: orange and indigo,
as he believed that the number of primary colors corresponds to the number of
primary notes in an octave. There is no indigo in Russian, but there is a word
for light blue. But according to the number of primary colors, there seems to
be agreement. Following Newton, we want to see a similar color harmony for the
plane.

The original title was "The chromatic number of the plane is 7 $-$ a human-
verifiable proof". But my dear editors dissuaded me from using it.

On the one hand, there is no mistake here: we will indeed be talking about the
exact number of colors. Recall that the chromatic number of the plane (denoted
$\chi$) is the minimum number of sets into which the Euclidean plane can be
partitioned such that the distance between any two points taken from the same
set is not equal to some forbidden distance $f$, which is usually taken $f=1$.
It is customary to assign a color to each such set (along with an ordinal
number) and talk about a coloring of the plane. Any coloring with a forbidden
distance is called proper.

It is known that 7 colors are enough for a proper coloring of the plane. This
is easy to demonstrate by tiling a plane in the form of a honeycomb using
regular hexagons. Each such hexagon takes one of seven colors and has a
diameter slightly less than one. This construction, whose authorship is
attributed to John Isbell [4], gives an estimate $\chi\leq 7$ at once for the
entire interval of forbidden distances $1\leq f\leq\sqrt{7}/2\approx
1.322876$.

To obtain a lower bound of $\chi$, a (finite) graph is usually constructed
with the corresponding value of $\chi$, but other considerations are possible.
By the way, we are not the first to announce the proof of the exact value of
$\chi$. For example, Kai-Rui Wang proved [5] that $\chi=4$. True, this was
before Aubrey de Grey showed [3] that $\chi\geq 5$. Alexander Soifer
conjectured [4] that $\chi=7$, which is the value we will focus on.

On the other hand, since this article was being prepared for the April issue
of the journal, we considered it possible to remain silent (temporarily) that
we will be talking about the chromatic number of a plane with an interval of
forbidden distances $1\leq f\leq d$ $(d>1)$, moreover, about a specific set of
such intervals. We hasten to assure the reader that everything below will be
honest, without deception.

Some forbidden distance intervals have one surprising property: there are
values of $d$ for which $\chi$ is known exactly. This fact was discovered by
Geoffrey Exoo [2] who constructed a 203-vertex 7-chromatic graph with
$d=\sqrt{43/25}\approx 1.311488<\sqrt{7}/2$ . If we recall the whole history
of colorings [4], in most generalizations of the plane chromatic number
problem, the gap between the known lower and upper bounds of $\chi$ only gets
larger, so the existence of such islands of exact knowledge is like a miracle.

Recently, Joanna Chybowska-Sokół, Konstanty Junosza-Szaniawski, and Krzysztof
Węsek considered a graph of a different construction [1], which (among other
things) allowed them to get $d\approx 1.285987$.

Here we go a little further and, for $d=2\sin(2\pi/9)\approx 1.285575$, offer
a simple constructive proof that can be verified without using a computer.

##  2 Polychromatic vertices

In some cases, instead of the forbidden interval of the asymmetric form $1\leq
f\leq d$, it is more convenient to consider the symmetric interval
$1-\varepsilon\leq f\leq 1+\varepsilon$. These forms are interchangeable,
$d=(1+\varepsilon)/(1-\varepsilon)$.

The transition from one forbidden distance ($\varepsilon=0$) to a non-zero
interval of forbidden distances ($\varepsilon>0$) significantly affects
coloring. For example, two colors are no longer enough to color a straight
line $\mathbb{R}^{1}$.

To show that the chromatic number of the plane $\mathbb{R}^{2}$ with
$\varepsilon>0$ is not less than 6, only three vertices of a regular unit
triangle are sufficient. Indeed, for any fixed proper coloring of the plane,
there is a point A whose $\varepsilon$-neighbourhood contains three colors 1,
2, 3. On a circle of unit radius centered at point A, there is a point B whose
$\varepsilon$-neighborhood contains two other colors 4, 5. If we place two
vertices of the triangle at points A and B (let’s call them tri- and bi-
chromatic, respectively), the remaining vertex C will have color 6. It remains
to prove the existence of tri- and bi-chromatic vertices for any proper
coloring of the plane, which is not very difficult (see lemma 3.1 in [1]).

Note that this construction can be generalized to an Euclidean space
$\mathbb{R}^{n}$ of arbitrary dimension $n\in\mathbb{Z}_{\geq 0}$ : for any
proper coloring, there is such an $(n+1)$-vertex regular unit simplex, whose
vertices will occupy sequentially $\\{n+1,\;n,\;n-1,\,\dots,1\\}$ colors. In
other words, the chromatic number of $\mathbb{R}^{n}$ with $\varepsilon>0$ is
at least ${n+2\choose 2}=(n+1)(n+2)/2$.

##  3 Main construction

We will rely on the construction proposed in [1]. Namely, a 4-chromatic graph
is constructed, all vertices of which are located in the annulus between
circles with radii 1 and $d$ and are connected by edges of length from 1 to
$d$ for some $d\geq 1$. An additional central vertex is connected by edges to
all annulus vertices and is located on a properly colored plane so that its
$\varepsilon$-neighborhood contains points of at least three colors. In other
words, the central vertex is tri-chromatic, which results in a 7-chromatic
graph.

In fact, we took the 2601-vertex graph from [1] (claim 3.3, construction 1),
and reduced it a little bit. One circle of unit radius was enough for us, on
which 18 vertices are evenly distributed, including one bi-chromatic vertex.
The resulting 19-vertex graph (Fig. 1) is already suitable for use in the
proof of the

Figure 1: A 19-vertex 7-chromatic graph with bi- and tri-chromatic vertices. A
variant of the 7-coloring is shown.

######  Theorem.

[1], [2] The chromatic number of the plane with an interval of forbidden
distances $[\,1,d\,]$ is 7 for $d\in(\,2\sin(2\pi/9),\sqrt{7}/2\,]$.

###### Proof.

Consider the 19-vertex graph shown in Fig. 1. We temporarily discard the
central vertex and renumber the remaining 18 vertices sequentially clockwise
from 1 to 18. For convenience, we can arrange them in a row, as shown in Fig.
2. We will identify the vertices and their numbers (indices), taking into
account that the indexing is done modulo 18.

Since the 18-vertex graph contains an odd cycle $C_{5}$, at least three colors
are required (numbered 1, 2, 3 in Fig. 2). Let $m$ denote the number of
consecutive (from $i$ to $i+m-1$) vertices of the same color, bounded by two
vertices ($i-1$ and $i+m$) of other colors. We will show successively that in
any proper 3-coloring a) only pairs ($m=2$) and triplets ($m=3$) are allowed,
b) they cannot occur simultaneously, c) a bi-chromatic vertex is not allowed.
Note that each vertex $i$ of the 18-vertex graph has degree 4 and is connected
to vertices $i\pm 3$ and $i\pm 4$. Therefore, $m\leq 3$, and the coloring rule
applies: 1) two consecutive vertices $i$ and $i+1$ of two different colors
give the remaining third color to the vertices $i-2$ and $i+3$.

To show $m\neq 1$, it suffices to make sure that the sequences of colors 123
and 121 are not allowed. To do this, we assign these colors to the three
consecutive vertices, after which, based on the rule described above, we
sequentially color some other vertices, until we come to a contradiction.

Case 123 is shown in Fig. 2a. The vertices are colored in the following
sequence (arrow means the colors are uniquely defined by specified vertices):
let vertices 7, 8, 9 be colors 1, 2, 3; then $\\{7,8\\}\Rightarrow\\{4,11\\}$;
$\\{8,9\\}\Rightarrow\\{5,12\\}$; $\\{4,5\\}\Rightarrow 1$;
$\\{11,12\\}\Rightarrow 15$; this leads to a conflict: vertices 1 and 15
connected by an edge take the same color.

Case 121 is shown in Fig. 2b: assign colors to $\\{7,8,9\\}$; then
$\\{7,8\\}\Rightarrow 11$; and whatever color the vertex $10$ takes, we get
three different colors of $\\{8,9,10\\}$ or $\\{9,10,11\\}$, which brings us
to the case 123 considered earlier.

Thus, the colors necessarily occur either in pairs or in triplets; the vertex
$i$, both nearest vertices of which $i\pm 1$ have other colors, is forbidden.
In other words, the following coloring rules are added: 2) two consecutive
vertices $i$ and $i+1$ of different colors give these colors to the vertices
$i-1$ and $i+2$ respectively; 3) a pair or triple of vertices of the same
color is bounded by vertices of two different colors (because of the edges
connecting the vertices $i$ and $i+3$).

Let us show that pairs and triplets cannot alternate in any proper 3-coloring.
To do this, consider the initial sequence of colors 331122233 (containing a
pair and a triple), and continue coloring using the rules above (Fig. 2c):
specify colors of $\\{5,6,\dots,13\\}$; then $\\{6,7\\}\Rightarrow 3$;
$\\{11,12\\}\Rightarrow 15$; $\\{3,15\\}\Rightarrow 18$;
$\\{7,18\\}\Rightarrow 4$; $\\{4,5\\}\Rightarrow 1$; which leads to a conflict
in the coloring of the vertices 1 and 15.

Thus, only two different proper 3-colorings are possible, containing either
six triples or nine pairs. Now it is easy to check that any vertex is
connected by edges to vertices of two different colors. Hence, at least four
colors are required to color a 18-vertex graph with one bi-chromatic vertex.
(In any of the two possible 3-colorings, there will be a sequence 1$x$223,
where $x$ is 1 or 2, and the first vertex of this sequence cannot be changed
to a bi-chromatic one.)

It remains to place in the center one tri-chromatic vertex connected by edges
to all other vertices, which will result in a 7-chromatic 19-vertex graph
shown in Fig. 1. To complete the proof, note that this graph has edges of
length 1 and $2\sin(2\pi/9)$, the latter gives the lower bound on $d$, while
the upper bound $\sqrt{7}/2$ is given by Isbell’s tessellation.

∎

Figure 2: To the proof of the Theorem. The vertex numbers are shown at the
top, then below are the specific cases of coloring. The initial color
assignments are bordered. Conflicts are shown in gray.

##  4 Additions

Aubrey de Grey suggested starting the coloring from a bi-chromatic vertex,
which simplifies the proof (see Fig. 2d). Let vertex 1 of 18-vertex graph be
colors 1 and 2. Then, in any proper 3-coloring vertices 4, 5, 15 and 16 must
be color 3, so vertices 7, 8, 9, 11, 12 and 13 cannot be color 3. Then,
without loss of generality let vertex 7 be color 1. Then
$\\{7,15\\}\Rightarrow 11$, $\\{5,11\\}\Rightarrow 8$, $\\{8,15\\}\Rightarrow
12$, $\\{5,12\\}\Rightarrow 9$, $\\{9,16\\}\Rightarrow 13$,
$\\{7,13\\}\Rightarrow 10$, $\\{9,10\\}\Rightarrow 6$, $\\{10,11\\}\Rightarrow
14$, $\\{6,7\\}\Rightarrow 3$, $\\{13,14\\}\Rightarrow 17$, so vertices 3 and
17 are both color 3, contradiction.

Who can do better?

However, it all depends on the criteria. The second version is more
straightforward, requires less checks, looks more compact. The first version
probably allows a better understanding of what is happening (since it gives
all colorings without a bi-chromatic vertex, which are already limited) and
requires fewer coloring operations (if we don’t count initial color
assignments).

It can be seen that in second version of the proof, two vertices are
redundant. If vertex 1 is bi-chromatic, then one of the following pairs of
vertices can be removed: $\\{2,18\\}$, $\\{2,6\\}$, $\\{8,12\\}$, or
$\\{14,18\\}$. In the first version of the proof, four vertices are not
involved in the coloring.

Aubrey also suggested using several bi-chromatic vertices instead of one.
Thus, one can try to reduce the number of vertices involved in the proof.
Recall that a bi-chromatic vertex appears at the boundary of two regions of
different colors. Apparently, at least 9 such vertices are required. Indeed,
if we take a circle with a radius slightly greater than one, then for its
3-coloring with a forbidden unit distance, at least 7 segments are required.
But if there are 7 or 8 segments, then one of them will border on two segments
of the same color, and as a result, there will be a pair of points of the same
color at a unit distance from each other. Therefore, at least 9 segments are
required, which means 9 bi-chromatic vertices.

One can do without a bi-chromatic vertex, for example, by considering a
29-vertex graph shown in Fig. 3 with edge length between 1 and
$d=2\sin(5\pi/22)\approx 1.309721$. Here all vertices, except for the central
one, occupy two concentric circles of radii 1 and $d$. But the proof with the
19-vertex graph seems simpler, and $d$ turns out to be smaller.

Figure 3: A 29-vertex 7-chromatic graph with tri-chromatic vertex.

It would be good to go further with a decrease in $d$, but apparently this
cannot be done within the framework of such constructions. The value of $d$ is
limited by the existence of a three-color tiling [1] of an annulus with an
outer radius $2\sin(2\pi/9)$.

I thank Alexander Soifer and Aubrey de Grey, who found an error in every
second statement. But it’s better to check everything anyway.

## References

  * [1] J. Chybowska-Sokół, K. Junosza-Szaniawski, and K. Węsek, Coloring distance graphs on the plane. arXiv:2201.04499v1, 12 Jan 2022.
  * [2] G. Exoo. $\varepsilon$-unit distance graphs. Discrete & Computational Geometry, vol. 33, 2005, pp. 117–123.
  * [3] A.D.N.J. de Grey, The chromatic number of the plane is at least 5. Geombinatorics, vol. 28, no. 1, 2018, pp. 18–31.
  * [4] A. Soifer, The mathematical coloring book. Mathematics of coloring and the colorful life of its creators. Springer, New York, 2009.
  * [5] K.-R. Wang, Chromatic number of Euclidean plane. arXiv:1507. 00025v1, 1 Jul 2015.