# Results in descriptive set theory on some represented spaces

Mathieu Hoyrup111615 rue du jardin botanique, 54600 Villers-lès-Nancy, France,
<EMAIL_ADDRESS>
Descriptive set theory was originally developed on Polish spaces. It was later
extended to $\omega$-continuous domains [Sel04] and recently to quasi-Polish
spaces [dB13]. All these spaces are countably-based. Extending descriptive set
theory and its effective counterpart to general represented spaces, including
non-countably-based spaces has been started in [PdB15].

We study the spaces $\mathcal{O}(\mathbb{N}^{\mathbb{N}})$,
$\mathcal{C}(\mathbb{N}^{\mathbb{N}},2)$ and the Kleene-Kreisel spaces
$\mathbb{N}{\langle\alpha\rangle}$. We show that there is a
$\Sigma^{0}_{2}$-subset of $\mathcal{O}(\mathbb{N}^{\mathbb{N}})$ which is not
Borel. We show that the open subsets of $\mathbb{N}^{\mathbb{N}^{\mathbb{N}}}$
cannot be continuously indexed by elements of $\mathbb{N}^{\mathbb{N}}$ or
even $\mathbb{N}^{\mathbb{N}^{\mathbb{N}}}$, and more generally that the open
subsets of $\mathbb{N}{\langle\alpha\rangle}$ cannot be continuously indexed
by elements of $\mathbb{N}{\langle\alpha\rangle}$. We also derive effective
versions of these results.

These results give answers to recent open questions on the classification of
spaces in terms of their base-complexity, introduced in [dBSS16]. In order to
obtain these results, we develop general techniques which are refinements of
Cantor’s diagonal argument involving multi-valued fixed-point free functions
and that are interesting on their own right.

##  1 Introduction

The core concepts of descriptive set theory are the definitions of
pointclasses, i.e. classes of sets, according to the way those sets can be
described.

It was originally developed on Polish spaces, where the definitions of
pointclasses are extensional: they describe how the sets in the classes
$\boldsymbol{\boldsymbol{\Sigma}}_{0}^{1}$, $\Sigma^{0}_{1}$,
$\boldsymbol{\boldsymbol{\Sigma}}^{0}_{2}$, etc. are built starting from basic
open sets in a countable basis [Kec95]. In particular these definitions imply
that all these classes can be parametrized by the Baire space
$\mathcal{N}=\mathbb{N}^{\mathbb{N}}$, which is usually expressed by saying
that on a Polish space $\mathbf{X}$, each class $\Gamma(\mathbf{X})$ has a
$\mathcal{N}$-universal set, i.e. a set $U$ in
$\Gamma(\mathcal{N}\times\mathbf{X})$ such that
$\Gamma(\mathbf{X})=\\{U_{f}:f\in\mathcal{N}\\}$ where
$U_{f}=\\{x\in\mathbf{X}:(f,x)\in U\\}$. All this extends to quasi-Polish
space, by slightly changing the definitions of the pointclasses [Sel04, dB13].

On a general represented space, the definitions are intensional: a set belongs
to a pointclass if its preimage under the representation belongs to that
pointclass [PdB15]. However this definition does not give information about
what those sets look like and how to obtain them.

Given a represented space, we are interested in understanding more concretely
what the elements of the various pointclasses look like, or how they can be
described. We provide here essentially impossibility results, stating that
there is no simple way of describing them. A typical result is that for some
particular represented spaces $\mathbf{X},\mathbf{Y}$, there is no
$\mathbf{Y}$-universal open set, i.e. there is no open subset $U$ of
$\mathbf{X}\times\mathbf{Y}$ such that
$\mathcal{O}(\mathbf{X})=\\{U_{y}:y\in\mathbf{Y}\\}$ or equivalently there is
no continuous surjection from $\mathbf{Y}$ to $\mathcal{O}(\mathbf{X})$. The
space $\mathbf{Y}$ is usually $\mathcal{N}$ or some Kleene-Kreisel space
$\mathbb{N}{\langle\alpha\rangle}$. We also derive effective versions of such
a result: there is no computable surjection from any $\Sigma^{1}_{k}$-subset
of $\mathbb{N}$ to the computable open subsets of $\mathbf{X}$, or there is no
$\Delta^{1}_{k}$-oracle enumerating those computable open sets.

We develop general tools that enable to prove these impossibility results in a
number of interesting cases, in particular for the space of clopen subsets of
$\mathcal{N}$ or the Kleene-Kreisel spaces $\mathbb{N}{\langle\alpha\rangle}$.
These tools treat the continuous and computable settings in the same way.

Our tools and techniques are based on Cantor’s diagonal argument: the
existence of a fixed-point free function is used to disprove the existence of
an enumeration. However we usually work on spaces that are lattices of open
sets, where every function has a fixed-point but where a _multi-valued_ fixed-
point free function may exist, and we need to develop techniques enabling us
to deal with multi-valued functions. In particular we introduce the notion of
a _canonizable space_.

The paper is organized as follows. In Section 2 we give all the necessary
notions about represented spaces and their topologies. In Section 3 we prove
that the space $\mathcal{O}(\mathcal{N})$ contains a $\Sigma^{0}_{2}$-subset
that is not Borel. In Section 4 we develop techniques based on the diagonal
argument to prove some impossibility results. In Section 5 we apply these
techniques to prove that some particular spaces have no
$\mathcal{N}$-universal open set. In Section 6 we refine our techniques and
introduce the notion of a canonizable space to include parameters spaces other
than $\mathcal{N}$ and its subspaces. We apply this technique to classify the
Kleene-Kreisel spaces and and to prove a result about Markov computability.

##  2 Background

Represented spaces are at the basis of computability theory on general spaces
[Wei00]. We follow the modern presentation given in [Pau15], [PdB15].

A _represented space_ is a pair $\mathbf{X}=(X,\delta_{X})$, where
$\delta_{X}:\subseteq\mathcal{N}\to X$ is a partial onto map. We often
identify $\mathbf{X}$ with its carrier set $X$, for commodity. If
$\delta_{X}(p)=x$ then we say that $p$ is a _name_ of $x$. A point
$x\in\mathbf{X}$ is _computable_ if it has a computable name. We denote by
$\mathbf{X}_{c}$ the set of computable points of $\mathbf{X}$. A function
$f:\mathbf{X}\to\mathbf{Y}$ is _continuous_ (resp.  _computable_) if there
exists a continuous (resp. computable) function
$F:\text{dom}(\delta_{X})\to\text{dom}(\delta_{Y})$ mapping any name of any
$x\in\mathbf{X}$ to a name of $f(x)$. We call $F$ a _realizer_ of $f$.

Two represented spaces $\mathbf{X},\mathbf{Y}$ are computably isomorphic,
denoted $\mathbf{X}\cong\mathbf{Y}$, if there is a bijection between that is
computable in both directions.

#### Cartesian product.

The product of two represented spaces $\mathbf{X},\mathbf{Y}$ is denoted by
$\mathbf{X}\times\mathbf{Y}$. A name of $(x,y)$ is simply a pair of names of
$x$ and $y$ (two elements of $\mathcal{N}$ can be paired into another element
of $\mathcal{N}$). One has
$\mathbf{X}\times\mathbf{Y}\cong\mathbf{Y}\times\mathbf{X}$.

#### Exponentiation.

The set of continuous functions from $\mathbf{X}$ to $\mathbf{Y}$ is itself a
represented space denoted by $\mathcal{C}(\mathbf{X},\mathbf{Y})$. A name for
a continuous function $f:\mathbf{X}\to\mathbf{Y}$ is a name for any continuous
realizer $F$ of $f$ (such a name gives the information needed to evaluate $F$,
for instance it encodes a list of pairs $(u,v)$ of finite sequences such that
for every $p\in\text{dom}(\delta_{X})$, (i) if $u$ is a prefix of $p$ and
$(u,v)$ appears in the list then $F(p)$ extends $v$ and (ii) for every prefix
$v$ of $F(p)$ there exists a prefix $u$ of $p$ such that $(u,v)$ appears in
the list).

The evaluation map
$\text{eval}:\mathbf{X}\times\mathcal{C}(\mathbf{X},\mathbf{Y})\to\mathbf{Y}$
is computable and
$\mathcal{C}(\mathbf{X}\times\mathbf{Y},\mathbf{Z})\cong\mathcal{C}(\mathbf{X},\mathcal{C}(\mathbf{Y},\mathbf{Z}))$.

#### Topology.

Every represented space $\mathbf{X}=(X,\delta_{X})$ has a canonical topology
$\tau_{X}$, which is the final topology of $\delta_{X}$: a set $U\subseteq X$
is open iff $\delta_{X}^{-1}(U)$ is the intersection of an open subset of
$\mathcal{N}$ with $\text{dom}(\delta_{X})$. As
$\text{dom}(\delta_{X})\subseteq\mathcal{N}$ is countably-based, hence
sequential, the final topology of $\delta_{X}$ is sequential. The set of open
subsets of $\mathbf{X}$ is itself a represented space obtained as follows. The
Sierpiński space $\mathbb{S}=(\\{\bot,\top\\},\delta_{\mathbb{S}})$ where
$\delta_{\mathbb{S}}(0^{\mathbb{N}})=\bot$ and $\delta_{\mathbb{S}}(p)=\top$
for $p\neq 0^{\mathbb{N}}$. A subset $U$ of $\mathbf{X}$ is then open exactly
when its characteristic function $\boldsymbol{1}_{U}:\mathbf{X}\to\mathbb{S}$
is continuous. The space of open subsets of $X$ is then
$\mathcal{O}(\mathbf{X}):=\mathcal{C}(\mathbf{X},\mathbb{S})$ with its
canonical representation. In turn, the topology on $\mathcal{O}(\mathbf{X})$
is the Scott topology, which coincides with the $\omega$-Scott topology (see
[dBSS16] for more details).

#### Subspace.

If $\mathbf{X}=(X,\delta_{X})$ is a represented space then any subset
$A\subseteq X$ has a canonical representation $\delta_{A}$, which is simply
the restriction of $\delta_{X}$ to $\delta_{X}^{-1}(A)$. Thus it immediately
induces notions of continuous and computable functions from $A$ to any other
represented space. It is known that sequential topological spaces are not
stable under taking subspace topologies. Similarly, the topology on $A$
induced by $\delta_{A}$ is not in general the subspace topology, but is
richer. In the same way, the topology on a product of represented spaces is
not in general the product topology but is richer.

#### Admissibility.

One has to be careful as there are two a priori distinct notions of continuity
for functions from $\mathbf{X}$ to $\mathbf{Y}$: the functions having a
continuous realizer, and the functions that are continuous w.r.t. to the
induced topologies. One easily checks that a continuous (i.e. continuously
realizable) function is always continuous w.r.t. the induced topologies,
however the converse implication fails without further assumption on the
representation. The appropriate condition that makes this implication an
equivalence is the admissibility of the representation. A representation is
admissible if, intuitively, representing a point $x$ is equivalent to being
able to know which open sets contain $x$. The evaluation map
$\text{eval}:\mathbf{X}\times\mathcal{O}(\mathbf{X})\to\mathbb{S}$,
equivalently $\text{eval}:\mathbf{X}\to\mathcal{O}(\mathcal{O}(\mathbf{X}))$
is computable: the space $\mathbf{X}$ is _admissible_ (resp.  _computably
admissible_) if the inverse of
$\text{eval}:\mathbf{X}\to\mathcal{O}(\mathcal{O}(\mathbf{X}))$ is continuous
(resp. computable). In this article, for the general results do not require
the representations to be admissible, which is useful when one deals with
Markov computability for instance (see Section 6.3).

#### Multifunctions.

Often, a computation taking a name of $x\in\mathbf{X}$ as input and producing
a name of some $y\in\mathbf{Y}$ as output does not induce a function from
$\mathbf{X}$ to $\mathbf{Y}$, as $y$ might depend not only on $x$, but on the
name of $x$ given as input. For instance, given a real number $x\in[0,1]$ it
is possible to compute some $y\in[0,1]$ such that $y\neq x$. However it is not
possible to compute the same $y$ for all name of any $x$, as it would induce a
computable, hence continuous function from $[0,1]$ to $[0,1]$ without fixed-
point, violating the Intermediate Value Theorem. A _multifunction_ is a set-
valued function $f:\mathbf{X}\to 2^{\mathbf{Y}}$, denoted by
$f:\mathbf{X}\rightrightarrows\mathbf{Y}$. A multifunction
$f:\mathbf{X}\rightrightarrows\mathbf{Y}$ is continuous (resp. computable) if
there exists a continuous (resp. computable) function
$F:\text{dom}(\delta_{X})\to\mathcal{N}$ such that $\delta_{Y}(F(p))\in
f(\delta_{X}(p))$ for all $p\in\text{dom}(\delta_{X})$.

#### Descriptive set theory.

Notions from descriptive set theory originally developed on Polish spaces
[Kec95] have a straightforward extension to any represented space [PdB15]. The
question is then whether the results also extend, and how.

Any pointclass $\Gamma(\mathcal{N})$ on $\mathcal{N}$ induces a pointclass on
$\mathbf{X}$ as follows: $A\subseteq\mathbf{X}$ belongs to
$\Gamma(\mathbf{X})$ if there is a set $B\subseteq\mathcal{N}$ in
$\Gamma(\mathcal{N})$ such that
$\delta_{X}^{-1}(A)=B\cap\text{dom}(\delta_{X})$.

In a topological space, the class of Borel sets is the smallest class
containing the open sets and closed under taking complements and countable
unions.

###  2.1 Retractions

As we have already mentioned, if $A$ is a subset of a represented space
$\mathbf{X}$, then the represented subspace $\mathbf{A}=(A,\delta)$ is not a
topological subspace in general. Similarly, if there are continuous (i.e.,
continuously realizable) functions $f:\mathbf{Y}\to\mathbf{X}$ and
$g:f(\mathbf{Y})\to\mathbf{Y}$ such that $g\circ f=\text{id}_{\mathbf{Y}}$,
then $f$ is not necessarily a topological embedding because $g$ is not
necessarily continuous for the subspace topology on $f(\mathbf{Y})$. However
if $g$ has a continuous extension over $\mathbf{X}$ then $f$ is a topological
embedding.

######  Definition 2.1.

A _section-retraction_ is a pair $(s,r)$ of functions
$s:\mathbf{Y}\to\mathbf{X}$, $r:\mathbf{X}\to\mathbf{Y}$ such that $r\circ
s=\text{id}_{\mathbf{Y}}$. If both $s$ and $r$ are continuous, then
$\mathbf{Y}$ is called a _continuous retract_ of $\mathbf{X}$. If both $s$ and
$r$ are computable, then $\mathbf{Y}$ is called a _computable retract_ of
$\mathbf{X}$.

Intuitively, elements of $\mathbf{Y}$ can be encoded by elements of
$\mathbf{X}$. If $r(x)=y$ then $x$ is a code for $y$, and every $y$ has a
canonical code, given by $s(y)$. It implies in particular that $\mathbf{Y}$ is
a continuous (resp. computable) image of $\mathbf{X}$.

######  Lemma 2.1.

If $\mathbf{Y}$ and $\mathbf{Y}^{\prime}$ are continuous (resp. computable)
retracts of $\mathbf{X}$ and $\mathbf{X}^{\prime}$ respectively, then
$\mathcal{C}(\mathbf{Y},\mathbf{Y}^{\prime})$ is a continuous (resp.
computable) retract of $\mathcal{C}(\mathbf{X},\mathbf{X}^{\prime})$. In
particular $\mathcal{O}(\mathbf{Y})$ is a continuous (resp. computable)
retract of $\mathcal{O}(\mathbf{X})$.

###### Proof.

Let $(s,r)$ and $(s^{\prime},r^{\prime})$ be sections-retractions for
$\mathbf{Y},\mathbf{X}$ and $\mathbf{Y}^{\prime},\mathbf{X}^{\prime}$
respectively. Let
$S:\mathcal{C}(\mathbf{Y},\mathbf{Y}^{\prime})\to\mathcal{C}(\mathbf{X},\mathbf{X}^{\prime})$
map $f$ to $s^{\prime}\circ f\circ r$ and
$R:\mathcal{C}(\mathbf{Y},\mathbf{Y}^{\prime})\to\mathcal{C}(\mathbf{X},\mathbf{X}^{\prime})$
map $g$ to $r^{\prime}\circ g\circ s$. The pair $(S,R)$ is easily a section-
retraction. The case of $\mathcal{O}(\mathbf{Y}),\mathcal{O}(\mathbf{X})$ is
obtained by taking $\mathbf{X}^{\prime}=\mathbf{Y}^{\prime}=\mathbb{S}$. ∎

If $A$ is a _closed_ subset of $X$ then the topology of the represented space
$\mathbf{A}$ coincides with the subspace topology. Moreover,

######  Lemma 2.2.

If $A$ is a closed subset of $\mathbf{X}$ then $\mathcal{O}(\mathbf{A})$ is a
continuous retract of $\mathcal{O}(\mathbf{X})$. If $A$ is a
$\Pi^{0}_{1}$-subset of $\mathbf{X}$ then $\mathcal{O}(\mathbf{A})$ is a
computable retract of $\mathcal{O}(\mathbf{X})$.

###### Proof.

Let $r:\mathcal{O}(\mathbf{X})\to\mathcal{O}(\mathbf{A})$ map $V$ to $V\cap A$
and $s:\mathcal{O}(\mathbf{A})\to\mathcal{O}(\mathbf{X})$ map $U$ to $U\cup
A^{c}$. ∎

We will need the following result in several places.

######  Lemma 2.3.

$\mathcal{N}$ is a computable retract of $\mathcal{C}(\mathcal{N},2)$.

###### Proof.

Each clopen set $C\in\mathcal{C}(\mathcal{N},2)$ encodes a function
$f:\mathbb{N}\to\mathbb{N}$, which is a kind of modulus of continuity of $C$
at certain points, defined as follows. For each $n$, let
$c_{n}:\mathbb{N}\to\mathbb{N}$ be the constant function with value $n$, and
$c_{n,k}(i)=n$ for $i\neq k$, $c_{n,k}(k)=n+1$. If $C$ does not contain
$c_{n}$, then let $f(n)=0$. If $C$ contains $c_{n}$, then let
$f(n)=\max\\{k\geq 1:c_{n,k}\notin C\\}$. We then define $r(C):=f$.

Every $f:\mathbb{N}\to\mathbb{N}$ is encoded in some
$C\in\mathcal{C}(\mathcal{N},2)$, defined as follows. For each
$n\in\mathbb{N}$, if $f(n)=0$ then let $C\cap[n]=\emptyset$. If $f(n)=k+1$
then let $C\cap[n]=\\{g:g(k+1)=n\\}$. We then define $s(f):=C$.

The functions $r$ and $s$ are computable and one easily checks that $r\circ
s(f)=f$ for all $f$. ∎

##  3 A non-Borel set

On Polish spaces, the Borel hierarchy built from the open sets coincides with
the hierarchy lifted from $\mathcal{N}$ by the representation: for instance a
set is a countable union of closed sets if and only if its pre-image is a
countable union of closed sets.

On quasi-Polish spaces, the same holds if the definition of the Borel
hierarchy is slightly amended: for instance
$\boldsymbol{\boldsymbol{\Sigma}}^{0}_{2}$-sets are not countable unions of
closed sets, but countable unions of differences of open sets.

Here we show that on admissibly represented spaces this is no more true in
general: in the space $\mathcal{O}(\mathcal{N})$ there exists a
$\Sigma^{0}_{2}$-subset of $\mathcal{O}(\mathcal{N})$ that is not even Borel.

To build this set, we first work on an intermediate space.

###  3.1 Product topology

We have seen that two represented spaces $\mathbf{X}$ and $\mathbf{Y}$
naturally induce a third represented space $\mathbf{X}\times\mathbf{Y}$. The
topology induced by that representation is not in general the product
topology, but its sequentialization.

A simple example is given by $\mathbf{X}=\mathcal{N}$ and
$\mathbf{Y}=\mathcal{O}(\mathcal{N})$. The evaluation map
$\mathcal{N}\times\mathcal{O}(\mathcal{N})\to\mathbb{S}$ is continuous (and
computable), however it is not continuous w.r.t. the product topology, because
$\mathcal{N}$ is not locally compact (see [EH02] for more details on this
topic). In other words the set
$\\{(f,O)\in\mathcal{N}\times\mathcal{O}(\mathcal{N}):f\in O\\}$ is not open
for the product topology (but it is sequentially open, or open for the
topology induced by the representation). It is even worse.

######  Proposition 3.1.

$E=\\{(f,O)\in\mathcal{N}\times\mathcal{O}(\mathcal{N}):f\in O\\}$ is not
Borel for the product topology.

###### Proof.

We prove that for every Borel set $A$, there exists a dense $G_{\delta}$-set
$G\subseteq\mathcal{N}$ such that for every $f\in G$,
$(f,\mathcal{N}\setminus\\{f\\})\in A\iff(f,\mathcal{N})\in A$. It implies the
result as it is obviously false for the set $E$. To prove it, we show that the
class of sets satisfying this condition contains the open sets in the product
topology and is closed under taking complements and countable unions, which
implies that this class contains the Borel sets.

First, consider a basic open set $A=[u]\times\mathcal{U}_{K}$ where $u$ is a
finite sequence of natural numbers, $K$ is a compact subset of $\mathcal{N}$
and $\mathcal{U}_{K}=\\{O\in\mathcal{O}(\mathcal{N}):K\subseteq O\\}$. Define
$G=[u]^{c}\cup[u]\setminus K$, which is a dense open set. For $f\in[u]^{c}$,
no $(f,O)$ belongs to $A$. For $f\in[u]\setminus K$, both
$(f,\mathcal{N}\setminus\\{f\\})$ and $(f,\mathcal{N})$ belong to $A$.

If $A$ satisfies the condition with a dense $G_{\delta}$-set $G$, then $A^{c}$
satisfies the condition with the same $G$. If $A_{i}$ satisfy the condition
with dense $G_{\delta}$-sets $G_{i}$ then $\bigcup_{i}A_{i}$ satisfies the
condition with $G=\bigcap_{i}G_{i}$. ∎

###  3.2 The space of open subsets of the Baire space

We can now prove the result. Note that in the statement, the class of Borel
subsets of $\mathcal{O}(\mathcal{N})$ is as usual the smallest class
containing the open subsets and closed under taking complement and countable
intersections.

######  Theorem 3.1.

There is a $\Sigma^{0}_{2}$-subset of $\mathcal{O}(\mathcal{N})$ which is not
Borel.

###### Proof.

We show that
$\mathcal{N}\mathrel{\times_{\text{prod}}}\mathcal{O}(\mathcal{N})$ is a
retract of $\mathcal{O}(\mathcal{N})$ in some way. We build:

  * •

A continuous function
$s:\mathcal{N}\mathrel{\times_{\text{prod}}}\mathcal{O}(\mathcal{N})\to\mathcal{O}(\mathcal{N})$,

  * •

A $\Sigma^{0}_{2}$-measurable function
$r:\mathcal{O}(\mathcal{N})\to\mathcal{N}\times\mathcal{O}(\mathcal{N})$,

  * •

Such that $r\circ s=\text{id}$.

First, these ingredients enable to derive the result. Indeed, let $E$ from
Proposition 3.1 and $F:=r^{-1}(E)\subseteq\mathcal{O}(\mathcal{N})$. As $E$ is
open in $\mathcal{N}\times\mathcal{O}(\mathcal{N})$, $F$ is $\Sigma^{0}_{2}$.
However $F$ is not Borel, otherwise $E=s^{-1}(F)$ would be Borel in
$\mathcal{N}\mathrel{\times_{\text{prod}}}\mathcal{O}(\mathcal{N})$.

Let us now build $s$ and $r$. First observe that
$\mathcal{O}(\mathcal{N})\cong\mathcal{O}(\mathcal{N})\times\mathcal{O}(\mathcal{N})$
and that the topology on
$\mathcal{O}(\mathcal{N})\times\mathcal{O}(\mathcal{N})$ coincides with the
product topology.

Lemma 2.3 provides two computable functions
$r_{0}:\mathcal{C}(\mathcal{N},2)\to\mathcal{N}$ and
$s_{0}:\mathcal{N}\to\mathcal{C}(\mathcal{N},2)$ such that $r_{0}\circ
s_{0}=\text{id}$. Observing that $\mathbb{S}$ and $2$ are two represented
spaces with the same underlying set and that
$\mathcal{O}(\mathcal{N})\cong\mathcal{C}(\mathcal{N},\mathbb{S})$, those
functions can be interpreted as $r_{1}:\mathcal{O}(\mathcal{N})\to\mathcal{N}$
and $s_{1}:\mathcal{N}\to\mathcal{O}(\mathcal{N})$ with $r_{1}\circ
s_{1}=\text{id}$. However, while $s_{1}$ is still computable, $r_{1}$ is not
computable but is $\Sigma^{0}_{2}$-measurable.

Let us simply pair $s_{1}$ and $r_{1}$ with the identity on
$\mathcal{O}(\mathcal{N})$: let $s(f,O^{\prime})=(s_{1}(f),O^{\prime}))$ and
$r(O,O^{\prime})=(r_{1}(O),O^{\prime})$. ∎

In particular, that $\Sigma^{0}_{2}$-set is not a countable union of
differences of open sets, as it should be on Polish or quasi-Polish spaces.
More generally, it is not a countable boolean combination of open sets.

In order to overcome the mismatch between the hierachy inherited from
$\mathcal{N}$ via the representation and the class of Borel sets, one may
attempt to change the definition of Borel sets. In [NV97] the Borel sets are
redefined as the smallest class containing the open sets and the saturated
compact sets. We observe here that this class is too large in the space
$\mathcal{O}(\mathcal{N})$. First, if $U\subseteq\mathcal{N}$ is open then the
set $\\{V\in\mathcal{O}(\mathcal{N}):U\subseteq V\\}$ is compact and saturated
in $\mathcal{O}(\mathcal{N})$. From this it is easy to see that the set built
above is Borel in this weaker sense. However this notion of Borel sets is too
loose, because compact saturated sets do not usually have a Borel pre-image.
For instance, the singleton $\\{\mathcal{N}\\}$ is compact saturated but its
pre-image is a $\boldsymbol{\boldsymbol{\Pi}}^{1}_{1}$-complete set, hence is
not Borel.

We leave the following questions for future work:

  * •

What do the $\boldsymbol{\boldsymbol{\Sigma}}^{0}_{2}$-subsets of
$\mathcal{O}(\mathcal{N})$ look like?

  * •

Is it possible to modify the definition of Borel sets on
$\mathcal{O}(\mathcal{N})$ to match exactly the sets that have a Borel pre-
image under the representation?

##  4 Parametrizations

In this section we investigate whether a collection of objects $A$ can be
parametrized by another collection $B$. Formally, $A$ and $B$ are represented
spaces and $A$ is parametrized by $B$ if $A$ is a continuous image of $B$. We
will also be interested in the computable version.

Given $A$, one tries to find the “simplest” space $B$ such that $A$ is a
continuous image of $B$. Simplicity can be measured by restricting our
attention to spaces $B$ that are subspaces of $\mathcal{N}$, and identifying
their minimal descriptive complexity. The Borel hierachy is too fine-grained
for this: $A$ is a continuous image of some Borel subset of $\mathcal{N}$ iff
it a continuous image of a $\Sigma^{1}_{1}$-subset of $\mathcal{N}$ iff it is
a continuous image of $\mathcal{N}$. Therefore, the complexity of
parametrizing a space is better measured by the hyperprojective hierarchy
$\\{\boldsymbol{\boldsymbol{\Sigma}}^{1}_{\alpha}\\}$ where $\alpha$ ranges
over the countable ordinals. It happens that the levels of this hierarchy
correspond to a hierarchy of spaces, the Kleene-Kreisel spaces
$\mathbb{N}{\langle\alpha\rangle}$, as stated by Theorem 4.2 below: a
represented space is a continuous image of some
$\boldsymbol{\boldsymbol{\Sigma}}^{1}_{\alpha}$-subset of $\mathcal{N}$ if and
only if it is a continuous image of $\mathbb{N}{\langle\alpha\rangle}$.

###  4.1 Kleene-Kreisel functionals

The Kleene-Kreisel functionals were introduced independently by Kleene [Kle59]
and Kreisel [Kre59]. They can be defined in the framework of represented
spaces, as in [SS15b] for instance.

If $\alpha$ is a countable ordinal then the space
$\mathbb{N}{\langle\alpha\rangle}$ is defined inductively as follows. Let
$\mathbb{N}{\langle 0\rangle}=\mathbb{N}$,
$\mathbb{N}{\langle\alpha+1\rangle}=\mathcal{C}(\mathbb{N}{\langle\alpha\rangle},\mathbb{N})$
and
$\mathbb{N}{\langle\lambda\rangle}=\prod_{i\in\omega}\mathbb{N}{\langle\beta(\lambda,i)\rangle}$
for a limit ordinal $\lambda$ and a fixed numbering $\beta(\lambda,i)$ of the
ordinals smaller than $\lambda$.

We will need the following results.

#### Functionals of finite type.

The following results can be found in [Nor80] and were proved by Kleene and
Kreisel.

######  Lemma 4.1.

For each $k\in\mathbb{N}$, $\mathbb{N}{\langle k\rangle}$ contains a dense
computable sequence.

######  Theorem 4.1 (Theorem 5.22 in [Nor80]).

Let $k\in\mathbb{N}$ and $A\subseteq\mathcal{N}$. The following conditions are
equivalent:

  * •

$A\in\Sigma^{1}_{k}(\mathcal{N})$,

  * •

There exists a computable predicate
$R\subseteq\mathcal{N}\times\mathbb{N}{\langle\alpha\rangle}\times\mathbb{N}$
such that

$x\in A\iff\exists y\in\mathbb{N}{\langle\alpha\rangle}\forall n,R(x,y,n).$

In particular, every $\Sigma^{1}_{k}$-set is a computable image of a
$\Pi^{0}_{1}$-subset of $\mathbb{N}{\langle k\rangle}$, but Theorem 4.1 says
more and we will need it later.

#### Functionals of countable type.

In [SS15a] an admissible representation $\delta_{\alpha}$ of
$\mathbb{N}{\langle\alpha\rangle}$ is built. Let
$D_{\alpha}=\text{dom}(\delta_{\alpha})$.

######  Theorem 4.2 ([SS15a]).

Let $\alpha$ be a countable ordinal. One has
$D_{\alpha+1}\in\boldsymbol{\boldsymbol{\Pi}}^{1}_{\alpha}(\mathcal{N})$. A
set $A\subseteq\mathcal{N}$ belongs to
$\boldsymbol{\boldsymbol{\Sigma}}^{1}_{\alpha}(\mathcal{N})$ iff it is a
continuous image of $\mathbb{N}{\langle\alpha\rangle}$.

###  4.2 Diagonal argument.

We now present the basic tool used to prove impossibility results about
continuous parametrizations. It is a variation on Cantor’s diagonal argument.
It might be possible to make it an instance of Lawvere’s categorical
formulation of the diagonal argument [Law69].

Let $\mathbf{Y}$ be a represented space. If
$h:\mathbf{Y}\rightrightarrows\mathbf{Y}$ is a multifunction then a point
$y\in Y$ is a _fixed-point_ of $h$ if $y\in h(y)$. We say that $h$ is _fixed-
point free_ if $h$ has no fixed-point. A computable fixed-point free
multifunction can be thought as an algorithm taking some $y$ as input
(represented by a name) and producing some $y^{\prime}\neq y$ as output (which
may not be the same for all names of $y$).

######  Proposition 4.1.

Let $\mathbf{Y}$ be a represented space. If $\mathbf{Y}$ admits a continuous
fixed-point free multifunction, then $\mathcal{C}(\mathcal{N},\mathbf{Y})$ is
not a continuous image of $\mathcal{N}$.

###### Proof.

Let $h:\mathbf{Y}\rightrightarrows\mathbf{Y}$ have no fixed-point and
$H:\text{dom}(\delta_{Y})\to\text{dom}(\delta_{Y})$ be a continuous realizer
of $h$. Let $\phi:\mathcal{N}\to\mathcal{C}(\mathcal{N},\mathbf{Y})$ be
continuous. The function $\phi$ can equivalently be typed as
$\phi:\mathcal{N}\times\mathcal{N}\to\mathbf{Y}$, let
$\Phi:\mathcal{N}\times\mathcal{N}\to\text{dom}(\delta_{Y})$ be a continuous
realizer of $\phi$. We define $F:\mathcal{N}\to\mathbf{Y}$ by
$F(f):=\delta_{Y}(H(\Phi(f)(f)))$. The function $F$ is continuous and is not
in the range of $\phi$ because for each $f$, $F$ differs from $\phi(f)$ at
$f$: $F(f)=\delta_{Y}(H(\Phi(f)(f)))\neq\delta_{Y}(\Phi(f)(f))=\phi(f)(f)$.
Therefore $\phi$ is not onto. ∎

In other words, in that case $\mathcal{C}(\mathcal{N},\mathbf{Y})$ is not a
continuous image of any $\boldsymbol{\boldsymbol{\Sigma}}^{1}_{1}$-subset of
$\mathcal{N}$.

######  Remark 4.1.

Under the same assumption about $\mathbf{Y}$, the same argument shows that for
any set $A\subseteq\mathcal{N}$, $\mathcal{C}(A,\mathbf{Y})$ is not a
continuous image of $A$.

###  4.3 Complexity of computable enumerations

We will also investigate the computable counterpart of parametrizations.

######  Definition 4.1.

Let $\mathbf{X}$ be a represented space and $\Gamma(\mathbb{N})$ a pointclass.
We say that $\mathbf{X}_{c}$ is _$\Gamma$ -enumerable_ if $\mathbf{X}_{c}$ is
a computable image of some set in $\Gamma(\mathbb{N})$.

The proof of Proposition 4.1 is effective and immediately implies the
following effective version.

######  Proposition 4.2.

If $\mathbf{Y}$ admits a computable fixed-point free multifunction then there
is no computable function from $\mathcal{N}$ to
$\mathcal{C}(\mathcal{N},\mathbf{Y})$ containing all the computable elements
in its range.

###### Proof.

In the proof of Proposition 4.1, if $H$ and $\Phi$ are computable, then the
function $F$ is computable and is not in the range of $\phi$. ∎

Proposition 4.2 implies that the computable functions from $\mathcal{N}$ to
$\mathbf{Y}$ are not $\Sigma^{0}_{1}$-enumerable, as the subsets of
$\mathbb{N}$ that are computable images of $\mathcal{N}$ are the
$\Sigma^{0}_{1}$-sets. However one would expect the much stronger result that
they are not $\Sigma^{1}_{1}$-enumerable. It is possible to obtain such a
result under a mild assumption on $\delta_{Y}$, usually satisfied in practice.

######  Definition 4.2.

We say that $A\subseteq\mathcal{N}$ is _computably separable_ if $A$ contains
a computable sequence that is dense in $A$.

If $A$ is computably separable then the set of cylinders intersecting $A$ is
c.e., and there is a computable function mapping any cylinder intersecting $A$
to an element of $A$ in that cylinder. This property has the following
interesting consequence.

######  Lemma 4.2.

Assume that $\text{dom}(\delta_{Y})$ is computably separable. Every computable
function from a $\Pi^{0}_{1}$-subset of $\mathcal{N}$ to $\mathbf{Y}$ has a
total computable extension.

###### Proof.

Let $P$ be a $\Pi^{0}_{1}$-subset of $\mathcal{N}$, $\phi:P\to\mathbf{Y}$ be
computable and $\Phi:P\to\mathcal{N}$ be a computable realizer for $\phi$. We
define a total computable extension $\phi^{\prime}$ of $\phi$ be defining a
computable realizer of $\phi^{\prime}$ as follows. Given $f$, run two
algorithms in parallel. On the one hand, start computing $\Phi(f)$ and output
the result as long as it is compatible with (i.e. has an extension in)
$\text{dom}(\delta_{Y})$. On the other hand, test whether $f\notin P$. If one
eventually discovers that $f\notin P$, then extend the current output with
some canonical element of $\text{dom}(\delta_{Y})$. ∎

We now get the effective version of Proposition 4.1.

######  Proposition 4.3.

Assume that $\text{dom}(\delta_{Y})$ is computably separable and $\mathbf{Y}$
admits a computable fixed-point free multifunction. The computable functions
from $\mathcal{N}$ to $\mathbf{Y}$ are not $\Sigma^{1}_{1}$-enumerable.

###### Proof.

Every $\Sigma^{1}_{1}$-subset of $\mathbb{N}$ is a computable image of a
$\Pi^{0}_{1}$-subset of $\mathcal{N}$, so it is sufficient to prove that the
computable elements of $\mathcal{C}(\mathcal{N},\mathbf{Y})$ is not a
computable image of such a set.

Let $P$ be a $\Pi^{0}_{1}$-subset of $\mathcal{N}$ and
$\delta:P\to\mathcal{C}(\mathcal{N},\mathbf{Y})$ be computable. The computable
separability of the domain of $\delta_{Y}$ enables one to extend $\delta$
outside $P$. Indeed, $\delta$ is equivalently seen as a computable function
from $P\times\mathcal{N}$ to $\mathbf{Y}$, and $P\times\mathcal{N}$ is a
$\Pi^{0}_{1}$-set, so Lemma 4.2 can be applied. We now apply Proposition 4.2.
∎

######  Example 4.1.

There is a strong contrast between the two following cases:

  * •

The left-c.e. functions from $\mathcal{N}$ to $[0,1]$ can be effectively
enumerated (from $\mathbb{N}$). Indeed, if $q_{n}$ is a computable enumeration
of the rational numbers in $[0,1]$ then from any computable sequence
$(U_{n})_{n\in\mathbb{N}}$ of open subsets of $\mathcal{N}$ (those sequences
can be effectively enumerated), one can build the left-c.e. function
$F(f)=\sup\\{q_{n}:f\in U_{n}\\}$ (with $\sup\emptyset=0$).

  * •

However the left-c.e. functions from $\mathcal{N}$ to $[0,1)$ are not
$\Sigma^{1}_{1}$-enumerable. Indeed, the computable function
$h:[0,1)_{<}\to[0,1)_{<}$ mapping $x$ to $(1+x)/2>x$ is fixed-point free, and
the representation of $[0,1)_{<}$ has a computably separable domain (a real
number $x\in[0,1)_{<}$ is represented by a non-decreasing sequence of
rationals converging to $x$).

#### Oracles.

So far we have measured the complexity of parametrizing points by measuring
the descriptive complexity of the domain of a computable enumeration. A
different but related approach is to measure the complexity of an oracle
computing an enumeration.

######  Corollary 4.1.

Assume that $\text{dom}(\delta_{Y})$ is computably separable and $\mathbf{Y}$
admits a computable fixed-point free multifunction. There is no
$\Delta^{1}_{1}$-oracle enumerating a list of indices of all the computable
points of $\mathcal{C}(\mathcal{N},\mathbf{Y})$.

###### Proof.

If there is such an oracle then the set of enumerated indices is also a
$\Delta^{1}_{1}$-subset of $\mathbb{N}$, and the function mapping an index in
that set to the corresponding point is a computable onto function with a
$\Delta^{1}_{1}$ domain, contradicting Proposition 4.3. ∎

However it may happen that a $\Delta_{1}^{1}$-oracle enumerates all the
computable points, producing names rather than indices. Again this is not
possible under the same assumptions.

######  Proposition 4.4.

Assume that $\text{dom}(\delta_{Y})$ is computably separable and $\mathbf{Y}$
admits a computable fixed-point free multifunction. There is no
$\Delta^{1}_{1}$-oracle enumerating all the computable points of
$\mathcal{C}(\mathcal{N},Y)$.

###### Proof.

Let $A\in\Delta^{1}_{1}(\mathbb{N})$ and
$\phi:\mathbb{N}\to\mathcal{C}(\mathcal{N},\mathbf{Y})$ be computable with
oracle $A$. The set $\\{A\\}$ is a $\Delta^{1}_{1}$-subset (hence a
$\Sigma^{1}_{1}$-subset) of $\mathcal{N}$ so it is a computable image of a
$\Pi^{0}_{1}$-subset $P$ of $\mathcal{N}$. As a result, the function
$\phi^{\prime}:P\times\mathbb{N}\to\mathcal{C}(\mathcal{N},\mathbf{Y})$
mapping $(f,n)$ to $\phi(n)$ is a computable function defined on a
$\Pi^{0}_{1}$-subset of $\mathcal{N}\times\mathbb{N}\cong\mathcal{N}$. As in
the proof of Propostion 4.3, $\phi^{\prime}$ has a total computable extension,
which cannot contain all the computable elements in its range. ∎

##  5 Applications to open sets

Let $\mathbf{X}$ be a represented space. $\mathbf{Y}:=\mathcal{O}(\mathbf{X})$
is a represented space with a computably separable representation (every
cylinder contains a representation of $X\in\mathcal{O}(\mathbf{X})$ consisting
of a covering of $\mathcal{N}$, and that can be computed from the cylinder).
In [dBSS16], a represented space $\mathbf{X}$ is called $\mathcal{N}$-based if
there is a continuous function from $\mathcal{N}$ to $\mathcal{O}(\mathbf{X})$
whose image is a basis of the topology on $\mathbf{X}$. This is equivalent to
saying that $\mathcal{O}(\mathbf{X})$ itself is a continuous image of
$\mathcal{N}$.

######  Lemma 5.1.

A represented space $\mathbf{X}$ is $\mathcal{N}$-based iff
$\mathcal{O}(\mathbf{X})$ is a continuous image of $\mathcal{N}$.

###### Proof.

The space $\mathbf{X}$ is hereditarily Lindelöf, i.e. every open cover
contains a countable subcover (simply because $\mathcal{N}$ and its subspaces
satisfy this property and taking the final topology of the representation
preserves this property). Now assume that $\mathbf{X}$ is $\mathcal{N}$-based
and let $\Phi:\mathcal{N}\to\mathcal{O}(\mathbf{X})$ be continuous, such that
$\Phi[\mathcal{N}]$ is a basis. We can easily modify $\Phi$ so that the empty
set is in its image. A function $f:\mathbb{N}\to\mathbb{N}$ can equivalently
be seen as a sequence of functions $f_{i}:\mathbb{N}\to\mathbb{N}$. Let
$\Psi(f)=\bigcup_{i}\Phi(f_{i})$. The function
$\Psi:\mathcal{N}\to\mathcal{O}(\mathbf{X})$ is continuous and onto, as every
open subset of $\mathcal{O}(\mathbf{X})$ is a countable union of elements of
the basis. ∎

Observe that
$\mathcal{C}(\mathcal{N},\mathcal{O}(\mathbf{X}))\cong\mathcal{O}(\mathcal{N}\times\mathbf{X})$,
hence Propositions 4.1, 4.3, and 4.4 immediately give the following results.

######  Theorem 5.1.

  1. 1.

If $\mathcal{O}(\mathbf{X})$ admits a continuous fixed-point free
multifunction then $\mathcal{N}\times\mathbf{X}$ is not $\mathcal{N}$-based.

  2. 2.

If $\mathcal{O}(\mathbf{X})$ admits a computable fixed-point free
multifunction then the computable open subsets of
$\mathcal{N}\times\mathbf{X}$:

     * •

Are not $\Sigma^{1}_{1}$-enumerable,

     * •

Are not enumerable relative to any $\Delta_{1}^{1}$ oracle.

Observe that by the Kleene fixed-point theorem, every continuous function from
$\mathcal{O}(\mathbf{X})$ to $\mathcal{O}(\mathbf{X})$ has a fixed-point, so
we really need to consider multifunctions rather than functions.

Also note that if $\mathbf{X}$ is a countably-based space with its standard
representation then $\mathcal{O}(\mathbf{X})$ has no continuous fixed-point
free multifunction, because $\mathcal{N}\times\mathbf{X}$ is countably-based
hence $\mathcal{O}(\mathcal{N}\times\mathbf{X})$ is a continuous imageof
$\mathcal{N}$.

###  5.1 Product space

Let us consider again the admissibly represented space
$\mathbf{X}=\mathcal{N}\times\mathcal{O}(\mathcal{N})$. Its topology is not
the product topology and contrary to the product topology it is not
$\mathcal{N}$-based as shown below.

######  Lemma 5.2.

The space $\mathcal{O}(\mathcal{O}(\mathcal{N}))$ admits a computable fixed-
point free multifunction.

###### Proof.

Given a name of $\mathcal{U}\in\mathcal{O}(\mathcal{O}(\mathcal{N}))$, we
build a function $g:\mathbb{N}\to\mathbb{N}$ and define
$\mathcal{V}=\\{O\in\mathcal{O}(\mathcal{N}):g\in O\\}$. The function $g$ is
defined as follows. Start describing the function $g$ mapping everything to
$0$. If eventually one finds that $\mathcal{U}\neq\emptyset$ then do as
follows. So far, $g$ belongs to some cylinder $[0^{n}]$. As
$\mathcal{U}\neq\emptyset$, $\mathcal{N}\in\mathcal{U}$ so any enumeration of
$\mathcal{N}$ is accepted by the name of $\mathcal{U}$. Enumerate
$\mathcal{N}$ in such a way that $[0^{n}]$ is not covered in finite time. When
this enumeration is accepted by $\mathcal{U}$, let $g$ be an element of
$[0^{n}]$ that is not yet covered by the enumeration of $\mathcal{N}$.

If $\mathcal{U}=\emptyset$ then $g=0$ and $\mathcal{V}$ is non-empty so
$\mathcal{V}\neq\mathcal{U}$. If $\mathcal{U}\neq\emptyset$ then
$\mathcal{N}\setminus\\{g\\}$ belongs to $\mathcal{U}$ but not to
$\mathcal{V}$, so $\mathcal{V}\neq\mathcal{U}$. ∎

One can apply Theorem 5.1.

  * •

$\mathcal{N}\times\mathcal{O}(\mathcal{N})$ is not $\mathcal{N}$-based,

  * •

The computable open subsets of $\mathcal{N}\times\mathcal{O}(\mathcal{N})$ are
neither $\Sigma^{1}_{1}$-enumerable nor enumerable relative to a
$\Delta^{1}_{1}$ oracle.

However,

######  Proposition 5.1.

$\mathcal{N}\times\mathcal{O}(\mathcal{N})$ is $\mathbb{N}{\langle
2\rangle}$-based.

###### Proof.

$\mathcal{O}(\mathcal{O}(\mathcal{N}))$ admits a total representation
$\delta:\mathcal{N}\to\mathcal{O}(\mathcal{O}(\mathcal{N}))$, equivalent to
the canonical representation. Therefore the function
$\mathcal{C}(\mathcal{N},\mathcal{N})\to\mathcal{C}(\mathcal{N},\mathcal{O}(\mathcal{O}(\mathcal{N}))$
mapping $f$ to $\delta\circ f$ is continuous and onto. Observe that
$\mathcal{C}(\mathcal{N},\mathcal{N})\cong\mathbb{N}{\langle 2\rangle}$ and
$\mathcal{C}(\mathcal{N},\mathcal{O}(\mathcal{O}(\mathcal{N}))\cong\mathcal{O}(\mathcal{N}\times\mathcal{O}(\mathcal{N}))$.
∎

Moreover $\mathcal{O}(\mathcal{N}\times\mathcal{O}(\mathcal{N}))$ is a
computable image of a $\Pi^{1}_{1}$-subset of $\mathcal{N}$, so the computable
open subsets of $\mathcal{N}\times\mathcal{O}(\mathcal{N})$ are
$\Pi^{1}_{1}$-enumerable and enumerable relative to a $\Delta^{1}_{2}$-oracle.

###  5.2 Space of clopens

Let $\mathbf{X}=\mathcal{C}(\mathcal{N},2)$ be the space of clopen subsets of
the Baire space.

######  Theorem 5.2.

The space $\mathcal{C}(\mathcal{N},2)$ is not $\mathcal{N}$-based. Its
computable open sets are not $\Sigma^{1}_{1}$-enumerable and are not
enumerable relative to any $\Delta^{1}_{1}$ oracle.

To prove the theorem we need the following lemma.

######  Lemma 5.3.

The space $\mathcal{O}(\mathcal{C}(\mathcal{N},2))$ admits a computable fixed-
point free multifunction.

The proof is almost identical to the proof of Lemma 5.2.

###### Proof.

Given a name of $\mathcal{U}\in\mathcal{O}(\mathcal{C}(\mathcal{N},2))$, start
computing a function $g\in\mathcal{N}$ as explained below, and output
$\mathcal{V}=\\{C\in\mathcal{C}(\mathcal{N},2):g\in
C\\}\in\mathcal{O}(\mathcal{C}(\mathcal{N},2))$.

Start defining $g=0$ on the first inputs. At the same time, wait to see
whether $\mathcal{U}$ is non-empty. If eventually $\mathcal{U}\neq\emptyset$
then at that point $g$ is defined up to input $n$. One can find some
$C\in\mathcal{U}$ and $[0^{n}]\nsubseteq C$. Indeed, start from some
$A\in\mathcal{U}$ and generate a name of $A$ which does not cover $[0^{n}]$ in
finite time. This name is eventually accepted by the name of $\mathcal{U}$.
Once $C$ is found, let $g\in[0^{n}]\setminus C$.

We now check that $\mathcal{V}\neq\mathcal{U}$. If $\mathcal{U}$ is empty then
$\mathcal{V}\neq\mathcal{U}$ as $\mathcal{V}$ is non-empty (and in that case,
$g=0$). If $\mathcal{U}$ is non-empty then one finds $C\in\mathcal{U}$ and
$g\notin C$, so $C\notin\mathcal{V}$ hence $\mathcal{V}\neq\mathcal{U}$. ∎

###### Proof of Theorem 5.2.

Let $\mathbf{X}=\mathcal{C}(\mathcal{N},2)$. Lemma 5.3 and Theorem 5.1 imply
the result for the space $\mathcal{N}\times\mathbf{X}$.

We know from Lemma 2.3 that $\mathcal{N}$ is a computable retract of
$\mathbf{X}$, so $\mathcal{N}\times\mathbf{X}$ is a computable retract of
$\mathbf{X}\times\mathbf{X}\cong\mathbf{X}$. As a result Lemma 2.1 implies
that $\mathcal{O}(\mathcal{N}\times\mathbf{X})$ is a computable retract, hence
a computable image of $\mathcal{O}(\mathbf{X})$, so the negative results about
$\mathcal{O}(\mathcal{N}\times\mathbf{X})$ immediately apply to
$\mathcal{O}(\mathbf{X})$. ∎

Observe that Theorem 5.2 immediately applies to the space $\mathbb{N}{\langle
2\rangle}=\mathcal{C}(\mathcal{N},\mathbb{N})$, as
$\mathcal{C}(\mathcal{N},2)$ is a computable retract of $\mathbb{N}{\langle
2\rangle}$.

We will now prove the stronger result that $\mathcal{C}(\mathcal{N},2)$ and
$\mathbb{N}{\langle 2\rangle}$ are not even $\mathbb{N}{\langle
2\rangle}$-based (Theorem 6.3 below), and more generally $\mathbb{N}{\langle
k\rangle}$ is not $\mathbb{N}{\langle k\rangle}$-based for $k\geq 2$. For
this, we need to refine our techniques, as we explain now.

##  6 Canonicity of names

The proof of Proposition 4.1 works because $\mathcal{N}$ has a particular
property: every element $f\in\mathcal{N}$ has a canonical name (which is $f$
itself). This property has the consequence that every continuous (resp.
computable) multifunction $F:\mathcal{N}\rightrightarrows\mathbf{X}$ has a
continuous (resp. computable) choice function
$F^{\prime}:\mathcal{N}\to\mathbf{X}$, such that $F^{\prime}(f)\in F(f)$ for
all $f\in\mathcal{N}$. So the multifunction built using the diagonal argument
and the fixed-point free multifunction is actually a single-valued function.

The spaces having this canonicity property are exactly the subspaces of
$\mathcal{N}$. The proof of Proposition 4.1 does not carry over to spaces
without this canonicity property, like $\mathbb{R}$ or $\mathbb{N}{\langle
2\rangle}$ for instance. However we provide a technique to overcome this
problem.

######  Definition 6.1.

A represented space $\mathbf{X}$ is _canonizable_ if there exists a subset
$P\subseteq\mathbf{X}$ such that:

  * •

$P$ is closed,

  * •

$\mathbf{X}$ is a continuous image of $P$,

  * •

$P$ is homeomorphic to some subspace of $\mathcal{N}$.

The first property implies that $P$ as a represented subspace of $\mathbf{X}$
has the subspace topology. The third property exactly says that $P$ has the
canonicity property, i.e. that there is a continuous function mapping every
$x\in P$ to a name of $x$.

######  Example 6.1.

$\mathbb{R}$ is canonizable, because it is a continuous image of
$\mathbb{N}\times 2^{\mathbb{N}}$ which embeds as a closed set in
$\mathbb{R}$.

When a space is canonizable, the diagonal argument can be applied.

######  Theorem 6.1.

Let $\mathbf{X}$ be a canonizable space. If $\mathcal{O}(\mathbf{Y})$ admits a
continuous fixed-point free multifunction then
$\mathcal{O}(\mathbf{X}\times\mathbf{Y})$ is not a continuous image of
$\mathbf{X}$.

###### Proof.

Let $P$ make $\mathbf{X}$ canonizable, and let $Q\subseteq\mathcal{N}$ be
homeomorphic to $P$. Proposition 4.1 implies that
$\mathcal{O}(Q\times\mathbf{Y})\cong\mathcal{C}(Q,\mathcal{O}(\mathbf{Y}))$ is
not a continuous image of $Q$, hence $\mathcal{O}(P\times\mathbf{Y})$ is not a
continuous image of $P$. As $P$ is a closed subset of $\mathbf{X}$,
$\mathcal{O}(P\times\mathbf{Y})$ is a continuous retract, hence a continuous
image of $\mathcal{O}(\mathbf{X}\times\mathbf{Y})$. As $\mathbf{X}$ is a
continuous image of $P$, one concludes by transitivity that
$\mathcal{O}(\mathbf{X}\times\mathbf{Y})$ is not a continuous image of
$\mathbf{X}$. ∎

This result has a computable version. We say that $\mathbf{X}$ is _computably
canonizable_ if the set $P$ is a $\Pi^{0}_{1}$-subset of $\mathbf{X}$, if
$\mathbf{X}$ is a computable image of $P$ and $P$ is computably homeomorphic
to some subspace of $\mathcal{N}$. In that case, the same proof shows that
there is no computable function from $\mathbf{X}$ to
$\mathcal{O}(\mathbf{X}\times\mathbf{Y})$ containing all the computable open
sets in its range.

###  6.1 Kleene-Kreisel functionals as parameters

The notion of a canonizable space enables us to extend Theorem 5.1 from
$\mathcal{N}=\mathbb{N}{\langle 1\rangle}$ to the whole hierachies functionals
of finite and countable type.

Observe that for $\alpha\geq 1$ a space $\mathbf{X}$ is
$\mathbb{N}{\langle\alpha\rangle}$-based if and only if
$\mathcal{O}(\mathbf{X})$ is a continuous image of
$\mathbb{N}{\langle\alpha\rangle}$, because as in the proof of Lemma 5.1, a
continuous function from $\mathbb{N}{\langle\alpha\rangle}$ to a basis of the
topology on $\mathbf{X}$ can be extended to a continuous surjection from
$\mathcal{C}(\mathbb{N},\mathbb{N}{\langle\alpha\rangle})\cong\mathbb{N}{\langle\alpha\rangle}$
to $\mathcal{O}(\mathbf{X})$.

######  Theorem 6.2.

  1. 1.

If $\mathcal{O}(\mathbf{X})$ admits a continuous fixed-point free
multifunction then for each countable ordinal $\alpha$,
$\mathbb{N}{\langle\alpha\rangle}\times\mathbf{X}$ is not
$\mathbb{N}{\langle\alpha\rangle}$-based.

  2. 2.

If $\mathcal{O}(\mathbf{X})$ admits a computable fixed-point free
multifunction then for each $k\in\mathbb{N}$ the computable open subsets of
$\mathbb{N}{\langle k\rangle}\times\mathbf{X}$:

     * •

Are not $\Sigma^{1}_{k}$-enumerable,

     * •

Are not enumerable relative to any $\Delta^{1}_{k}$ oracle.

The proof essentially follows the same argument as the proof of Theorem 5.1,
but we first need to show that the spaces $\mathbb{N}{\langle\alpha\rangle}$
are canonizable.

######  Lemma 6.1.

For every countable ordinal $\alpha$, $\mathbb{N}{\langle\alpha\rangle}$ is
canonizable.

###### Proof.

The proof is inspired by a construction appearing in the proof of Theorem 7.2
in [SS15a].

We first prove the result for all successor ordinals. $D_{\alpha+1}$ is a
$\boldsymbol{\boldsymbol{\Pi}}^{1}_{\alpha}$-set, so there exists a continuous
surjective function $f:\mathbb{N}{\langle\alpha\rangle}\to\mathcal{N}\setminus
D_{\alpha+1}$. We define
$\psi:D_{\alpha+1}\to\mathbb{N}{\langle\alpha+1\rangle}$ as follows. For $x\in
D_{\alpha+1}$ and $y\in\mathbb{N}{\langle\alpha\rangle}$, let
$\psi(x)(y)=\min\\{n\in\mathbb{N}:x_{n}\neq f(y)_{n}\\}$. $\psi$ is
continuous, let $\Psi:D_{\alpha+1}\to\mathcal{N}$ be a continuous realizer of
$\psi$. Let $P\subseteq\mathcal{N}\times\mathbb{N}{\langle\alpha+1\rangle}$ be
the graph of $\psi$. $P$ is homeomorphic to the graph of $\Psi$ which is a
subset of $\mathcal{N}\times\mathcal{N}\cong\mathcal{N}$. $P$ is a closed
subset of $\mathcal{N}\times\mathbb{N}{\langle\alpha+1\rangle}$. Indeed, a
pair $(x,F)$ belongs to $P$ iff for all
$y\in\mathbb{N}{\langle\alpha\rangle}$, if $n=F(y)$ then $x_{n}\neq f(y)_{n}$
and $x_{m}=f(y)_{m}$ for all $m<n$, which can be checked for $y$ in some
countable dense subset of $\mathbb{N}{\langle\alpha\rangle}$. If this is not
true then one can eventually see it. Finally,
$\mathbb{N}{\langle\alpha+1\rangle}$ is a continuous image of $D_{\alpha+1}$
which is the first projection of $P$.

For limit ordinals, we prove the result by induction. Let $\lambda$ be a limit
ordinal. For each each $\beta<\lambda$, let $P_{\beta}$ witness that
$\mathbb{N}{\langle\beta\rangle}$ is canonizable. By definition,
$\mathbb{N}{\langle\lambda\rangle}=\prod_{i\in\omega}\mathbb{N}{\langle\beta(\lambda,i)\rangle}$
for some numbering $\beta(\lambda,i)$ of the ordinals smaller than $\lambda$,
and one can easily check that $\prod_{i\in\omega}P_{\beta(\lambda,i)}$ makes
$\mathbb{N}{\langle\lambda\rangle}$ canonizable. ∎

For the finite levels of the hierarchy we can prove an effective version.

######  Lemma 6.2.

For $k\geq 1$, $\mathbb{N}{\langle k\rangle}$ is computably canonizable.

###### Proof.

From Theorem 4.1, as $D_{k}\in\Pi^{1}_{k-1}$ there exists a computable
predicate $R\subseteq\mathcal{N}\times\mathbb{N}{\langle
k-1\rangle}\times\mathbb{N}$ such that $x\in D_{k}\iff\forall
y\in\mathbb{N}{\langle k-1\rangle},\exists n,R(x,y,n)$. We define a computable
function define $\psi:D_{k}\to\mathbb{N}{\langle k\rangle}$ by
$\psi(x)(y)=\min\\{n:R(x,y,n)\\}$ for $x\in D_{k},y\in\mathbb{N}{\langle
k-1\rangle}$. Let $P$ be the graph of $\psi$. First, $P$ is a
$\Pi^{0}_{1}$-subset of $\mathcal{N}\times\mathbb{N}{\langle k\rangle}$.
Indeed, $(x,H)$ belongs to the graph if and only if for all
$y\in\mathbb{N}{\langle k-1\rangle}$, if $n=H(y)$ then $R(x,y,n)$ and $\neg
R(x,y,i)$ for all $i<n$, but this can be checked for all $y$ in a computable
dense sequence in $\mathbb{N}{\langle k-1\rangle}$ (which exists by Lemma
4.1).

As $\psi$ is computable, its graph is computably isomorphic to the graph of a
computable realizer of $\psi$, which is a subset of
$\mathcal{N}\times\mathcal{N}\cong\mathcal{N}$. Finally, $\mathbb{N}{\langle
k\rangle}$ is a computable image of $D_{k}$ which is the first projection of
$P$. ∎

It may possible to extend the result to the constructive ordinals, however we
do not address this question in this article.

###### Proof of Theorem 6.2.

In the first case, as $\mathbb{N}{\langle\alpha\rangle}$ is canonizable we can
apply Theorem 6.1.

In the second case, as $\mathbb{N}{\langle k\rangle}$ is computably
canonizable there is no computable function from $\mathbb{N}{\langle
k\rangle}$ to $\mathcal{O}(\mathbb{N}{\langle k\rangle}\times\mathbf{Y})$
containing all the computable open sets in its range, therefore there is no
such computable function defined on some $\Pi^{0}_{1}$-subset of
$\mathbb{N}{\langle\alpha\rangle}$. We can conclude as every set in
$\Sigma^{1}_{k}(\mathbb{N})$ is a computable image of some set in
$\Pi^{0}_{1}(\mathbb{N}{\langle\alpha\rangle})$, and for every set
$A\in\Delta^{1}_{2}(\mathbb{N})$, $\\{A\\}$ is a computable image of some set
in $\Pi^{0}_{1}(\mathbb{N}{\langle\alpha\rangle})$. ∎

###  6.2 Applications

We now apply Theorem 6.2 to particular spaces.

#### Back to the space of clopens.

We saw in Theorem 5.2 that $\mathcal{C}(\mathcal{N},2)$ is not
$\mathcal{N}$-based, i.e. that $\mathcal{O}(\mathcal{C}(\mathcal{N},2))$ is
not a continuous image of $\mathcal{N}$. We can now apply Theorem 6.2 to
improve that result.

######  Theorem 6.3.

The space $\mathcal{C}(\mathcal{N},2)$ is not $\mathbb{N}{\langle
2\rangle}$-based.

The computable open subsets of $\mathcal{C}(\mathcal{N},2)$ are not
$\Sigma^{1}_{2}$-enumerable and not enumerable relative to any
$\Delta^{1}_{2}$ oracle.

#### The Kleene-Kreisel functionals.

######  Theorem 6.4.

For every countable ordinal $\alpha\geq 2$, $\mathbb{N}{\langle\alpha\rangle}$
is not $\mathbb{N}{\langle\alpha\rangle}$-based.

For every $k\geq 2$, the computable open subsets of $\mathbb{N}{\langle
k\rangle}$ are not $\Sigma^{1}_{k}$-enumerable and not enumerable relative to
any $\Delta^{1}_{k}$ oracle.

We just have to prove that $\mathcal{O}(\mathbb{N}{\langle\alpha\rangle})$ has
continuous fixed-point free multifunction and $\mathcal{O}(\mathbb{N}{\langle
k\rangle})$ has a computable one. They can be easily derived from the
computable fixed-point free multifunction on
$\mathcal{O}(\mathcal{C}(\mathcal{N},2))$ (Lemma 5.3) thanks to the following
observation.

######  Lemma 6.3.

Let $\mathbf{X}$ be a continuous (resp. computable) retract of $\mathbf{Y}$.
If $\mathbf{X}$ admits a continuous (resp. computable) fixed-point free
multifunction then so does $\mathbf{Y}$.

###### Proof.

Let $r:\mathbf{Y}\to\mathbf{X}$ and $s:\mathbf{X}\to\mathbf{Y}$ be continuous
such that $r\circ s=\text{id}$, and let $R,S$ be continuous realizers. Let
$h:\mathbf{X}\rightrightarrows\mathbf{X}$ be fixed-point free and $H$ be a
continuous realizer. The multifunction $k=s\circ h\circ r$ (defined by
$k(y)=\\{s(x):x\in h(r(y)\\}$) is continuous as it is realized by the
continuous function $S\circ H\circ R$. Moreover it is fixed-point free, as if
$y\in k(y)$ then $y=s(x)$ for some $x\in h(r(y))$, so $r(y)$ is a fixed-point
for $h$, as $r(y)=r\circ s(x)=s\in h(r(y))$, contradicting the assumption
about $h$. Everything works the same in the computable case. ∎

Theorem 6.4 follows as $\mathcal{C}(\mathcal{N},2)$ is a computable retract of
$\mathbb{N}{\langle 2\rangle}$ which is a computable retract of each
$\mathbb{N}{\langle k\rangle}$ (Lemma 7.4 in [SS15a]), $k\geq 2$, and a
continuous retract of each $\mathbb{N}{\langle\alpha\rangle}$, $\alpha\geq 2$.

#### Implications on the hyperprojective base-hierarchy.

In [dBSS16] the hierachy $\text{Based}(\mathbb{N}{\langle\alpha\rangle})$ is
introduced: a space is in $\text{Based}(\mathbb{N}{\langle\alpha\rangle})$ if
it is $\mathbb{N}{\langle\alpha\rangle}$-based. That hierarchy is related to
another hierarchy called
$\mathsf{QCB}_{0}(\boldsymbol{\boldsymbol{\Pi}}^{1}_{\alpha})$. The following
results are proved in [dBSS16]:

  * •

Proposition 2.9:
$\mathbb{N}{\langle\alpha+1\rangle}\in\mathsf{QCB}_{0}(\boldsymbol{\boldsymbol{\Pi}}^{1}_{\alpha})$,

  * •

Proposition 6.11:
$\mathsf{QCB}_{0}(\boldsymbol{\boldsymbol{\Pi}}^{1}_{\alpha})\subseteq\text{Based}(\mathbb{N}{\langle\alpha+2\rangle})$,

  * •

Corollary 6.12: The inclusion
$\text{Based}(\mathbb{N}{\langle\alpha\rangle})\subset\text{Based}(\mathbb{N}{\langle\alpha+3\rangle})$
is proper.

It is asked:

  * •

Problem 6.2: for which $\alpha$ does the inclusions
$\mathsf{QCB}_{0}(\boldsymbol{\boldsymbol{\Pi}}^{1}_{\alpha})\subseteq\text{Based}(\mathbb{N}{\langle\alpha+1\rangle})$
and
$\mathsf{QCB}_{0}(\boldsymbol{\boldsymbol{\Pi}}^{1}_{\alpha})\subseteq\text{Based}(\mathbb{N}{\langle\alpha\rangle})$
hold?

  * •

Is the inclusion
$\text{Based}(\mathbb{N}{\langle\alpha\rangle})\subset\text{Based}(\mathbb{N}{\langle\alpha+1\rangle})$
proper?

Theorem 6.4 gives answers to these questions:

######  Corollary 6.1.

  1. 1.

For all countable ordinals $\alpha\geq 1$,
$\mathsf{QCB}_{0}(\boldsymbol{\boldsymbol{\Pi}}^{1}_{\alpha})\nsubseteq\text{Based}(\mathbb{N}{\langle\alpha+1\rangle})$.

  2. 2.

For all countable ordinals $\alpha$, the inclusion
$\text{Based}(\mathbb{N}{\langle\alpha\rangle})\subset\text{Based}(\mathbb{N}{\langle\alpha+1\rangle})$
is proper (witnessed by $\mathbb{N}{\langle\alpha\rangle}$),

###### Proof.

  1. 1.

The first assertion is witnessed by $\mathbb{N}{\langle\alpha+1\rangle}$
(Theorem 6.4).

  2. 2.

The second assertion is witnessed by $\mathbb{N}{\langle\alpha\rangle}$ for
$\alpha\geq 2$ (Theorem 6.4), by $\mathcal{N}\times\mathcal{O}(\mathcal{N})$
for $\alpha=1$ (see Section 5.1) and by $\mathcal{O}(\mathcal{N})$ for
$\alpha=0$.∎

###  6.3 Markov computability

Let $\mathbf{X}_{M}$ be the set of computable elements of $\mathbf{X}$ with
the Markov representation mapping an index of a computable name of
$x\in\mathbf{X}$ to $x$ (an index $i\in\mathbb{N}$ can be identified with the
constant function with value $i$, so that the domain of the representation is
a subset of $\mathcal{N}$). Note that the identity from $\mathbf{X}_{M}$ to
$\mathbf{X}_{c}$ is computable, but its inverse is not computable in general.

While the spaces $\mathcal{N}$ and $\mathcal{N}_{c}$ have the canonicity
property, $\mathcal{N}_{M}$ does not: it is not possible to associate to each
computable function a canonical index that could be uniformly computed from
any other index.

However,

######  Lemma 6.4.

$\mathcal{N}_{M}$ is computably canonizable.

###### Proof.

Let $(\varphi_{i})_{i\in\mathbb{N}}$ be a canonical enumeration of the partial
computable functions from $\mathbb{N}$ to $\mathbb{N}$. Let
$\text{Tot}=\\{i:\varphi_{i}\text{ is total}\\}$. If $i\in\text{Tot}$, then
let $t_{i}:\mathbb{N}\to\mathbb{N}$ map $n$ to the halting time of
$\varphi_{i}(n)$.

Let $P=\\{(i,t):\varphi_{i}\text{ is total and }t=t_{i}\\}$, where $(i,t)$ is
understood as the function $f$ mapping $0$ to $i$ and $n+1$ to $t(n)$. $P$ is
a $\Pi^{0}_{1}$-subset of $\mathcal{N}_{M}$ (and even of $\mathcal{N}_{c}$).
Indeed, given $f$, let $i=f(0)$: one has $f\notin P\iff\exists
n,\varphi_{i}(n)$ does not halt in exactly $f(n)$ steps, which can be
eventually discovered.

On $P$, the standard representation and the Markov representation are
computably equivalent: given $f\in P$, one can compute an index of $f$, as one
can compute an index of $t_{i}$ where $i:=f(0)$, so $P\subseteq\mathbf{X}_{M}$
is computably isomorphic to $P\subseteq\mathcal{N}$.

Finally, $\mathcal{N}_{M}$ is a computable image of the first projection of
$P$. ∎

######  Lemma 6.5.

$\mathcal{O}(\mathcal{N}_{M})$ admits a computable fixed-point free
multifunction.

###### Proof.

One can think of a name of an element $\mathcal{W}$ of
$\mathcal{O}(\mathcal{N}_{M})$ as an enumeration of a set
$W\subseteq\mathbb{N}$ containing the indices of the computable functions in
$\mathcal{W}$ (and possibly indices of partial functions). Given an
enumeration of a set of indices $W$, we enumerate another set $W^{\prime}$
coding some $\mathcal{W}^{\prime}\in\mathcal{O}(\mathcal{N}_{M})$ such that
$\mathcal{W}^{\prime}\neq\mathcal{W}$.

Let $f_{\infty}$ be the null function, and $f_{k}(n)=0$ if $n\neq k$,
$f_{k}(k)=1$.

Given an enumeration of $W$, we enumerate $W^{\prime}$ as follows. Start
enumerating all the natural numbers. In parallel, test whether
$f_{\infty}\in\mathcal{W}$. If it eventually happens, let $n$ be larger than
all the numbers enumerated so far in $W^{\prime}$. Look for $n+1$ values of
$k$ such that $f_{k}\in\mathcal{W}$, and let $K$ be larger than all of them.
Now enumerate in $W^{\prime}$ all the numbers $j$ such that $\varphi_{j}$
coincides with some $\varphi_{l}$, $l<n$, on inputs $0,1,\ldots,K$.

Now we check that the construction fulfills the conditions.

  * •

If $f_{\infty}\notin\mathcal{W}$ then $W^{\prime}=\mathbb{N}$ and
$\mathcal{W}^{\prime}=\mathcal{N}_{c}$, so
$f_{\infty}\in\mathcal{W}^{\prime}\setminus\mathcal{W}$.

  * •

If $f_{\infty}\in\mathcal{W}$ then there exist infinitely many $k$’s such that
$f_{k}\in\mathcal{W}$, so the algorithm will eventually find $K$, and
$\mathcal{W}^{\prime}=\bigcup_{l<n}[\varphi_{l}\mathop{\upharpoonright_{K}}]$
(with the convention that
$[\varphi_{l}\mathop{\upharpoonright_{K}}]=\emptyset$ if $\varphi_{l}$ is not
defined up to $K$). As there are at least $n+2$ values of $k<K$ such that
$f_{k}\in\mathcal{W}$, and all these functions differ on some input $<K$, one
of them does not belong to $\mathcal{W}^{\prime}$ which a union of $n$
cylinders of length $K$. As result,
$f_{k}\in\mathcal{W}\setminus\mathcal{W}^{\prime}$.∎

The computable elements of $\mathcal{O}(\mathcal{N}_{M})$ are also called the
Markov semidecidable properties. They correspond to the c.e. subsets of
$\mathbb{N}$ that are extensional w.r.t. the indices of total computable
functions (for each total function, an extensional set contains all its
indices or none of them). With the tools we have developed, we can resolve a
question left open in [Hoy16].

######  Corollary 6.2.

The computable open subsets of $\mathcal{N}_{M}$ are not
$\Sigma^{0}_{3}$-enumerable.

###### Proof.

One has
$\mathcal{O}(\mathcal{N}_{M}\times\mathcal{N}_{M})\cong\mathcal{O}(\mathcal{N}_{M})$
so $\mathcal{O}(\mathcal{N}_{M})$ is not a computable image of
$\mathcal{N}_{M}$. The computable images of $\mathcal{N}_{M}$ are exactly the
$\Sigma^{0}_{3}$-sets. ∎

Finally, the computable open subsets of $\mathcal{N}_{M}$ are
$\Pi^{0}_{3}$-enumerable, simply because the domain of the representation of
$\mathcal{O}(\mathcal{N}_{M})$ is $\Pi^{0}_{3}$ (said differently, for a c.e.
set, being extensional is a $\Pi^{0}_{3}$-property).

##  7 Discussion and results

The main results presented in this article are:

  * •

There exists of a $\Sigma^{0}_{2}$-subset of $\mathcal{O}(\mathcal{N})$ that
is not Borel (Theorem 3.1),

  * •

For each countable ordinal $\alpha\geq 2$, there is no continuous surjection
from $\mathbb{N}{\langle\alpha\rangle}$ to
$\mathcal{O}(\mathbb{N}{\langle\alpha\rangle})$ or, equivalently, there is no
$\mathbb{N}{\langle\alpha\rangle}$-universal open set for
$\mathbb{N}{\langle\alpha\rangle}$ (Theorem 6.4),

  * •

For $k\in\mathbb{N}$, $k\geq 2$, there is no computable enumeration of the
computable open subsets of $\mathbb{N}{\langle k\rangle}$ from a
$\Sigma^{1}_{k}$-subset of $\mathbb{N}$, or relative to a $\Delta^{1}_{k}$
oracle (Theorem 6.4),

  * •

There is no computable enumeration of the Markov semidecidable subsets of
$\mathcal{N}$ from any $\Sigma^{0}_{3}$-subset of $\mathbb{N}$ (Corollary
6.2).

These results are obtained by building fixed-point free multi-valued functions
and applying the diagonal argument. In several cases one has to be careful
about extensionality issues, and we introduce the notion of a canonizable
space (Definition 6.1) to overcome this problem. These techniques might be
useful for other investigations.

These results are negative results that help locating the complexity of
describing sets in some pointclasses. An interesting direction would be to
obtain positive answers to questions like: What do the
$\boldsymbol{\boldsymbol{\Sigma}}^{0}_{2}$-subsets and
$\Sigma^{0}_{2}$-subsets of $\mathcal{O}(\mathcal{N})$ look like? What do the
open subsets of $\mathbb{N}^{\mathbb{N}^{\mathbb{N}}}$ look like? How to build
them from simpler objects?

## Acknowledgments

The author would like to thank Arno Pauly for suggesting the investigation of
the $\Sigma^{0}_{2}$-subsets of $\mathcal{O}(\mathcal{N})$ and the
$\Sigma^{0}_{1}$-subsets of $\mathcal{C}(\mathcal{N},2)$, as well as Matthias
Schröder for discussions on this topic.

## References

  * [dB13] Matthew de Brecht.  Quasi-polish spaces.  Ann. Pure Appl. Logic, 164(3):356–381, 2013.
  * [dBSS16] Matthew de Brecht, Matthias Schröder, and Victor Selivanov.  Base-complexity classifications of qcb0-spaces.  Computability, 5(1):75–102, 2016.
  * [EH02] Martin Escardó and Reinhold Heckmann.  Topologies on spaces of continuous functions.  Topology Proceedings, 26(2):545–564, 2001-2002.
  * [Hoy16] Mathieu Hoyrup.  The decidable properties of subrecursive functions.  In ICALP 2016, July 11-15, 2016, Rome, Italy, volume 55 of LIPIcs, pages 108:1–108:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016.
  * [Kec95] Alexander S. Kechris.  Classical Descriptive Set Theory.  Springer, January 1995.
  * [Kle59] S.C. Kleene.  Countable functionals.  Constructivity in Mathematics, pages 81–100, 1959.
  * [Kre59] G. Kreisel.  Interpretation of analysis by means of functionals of finite type.  Constructivity in Mathematics, pages 101–128, 1959.
  * [Law69] F. William Lawvere.  Diagonal arguments and cartesian closed categories, pages 134–145.  Springer Berlin Heidelberg, Berlin, Heidelberg, 1969.
  * [Nor80] D. Normann.  Recursion on the Countable Functionals.  Lecture Notes in Mathematics. Springer Berlin Heidelberg, 1980.
  * [NV97] Tommy Norberg and Wim Vervaat.  Capacities on non-Hausdorff spaces.  Probability and Lattices, 110:133–150, 1997.
  * [Pau15] Arno Pauly.  On the topological aspects of the theory of represented spaces.  Computability, 5(2):159–180, 2015.
  * [PdB15] Arno Pauly and Matthew de Brecht.  Descriptive set theory in the category of represented spaces.  In 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, July 6-10, 2015, pages 438–449. IEEE Computer Society, 2015.
  * [Sel04] V. L. Selivanov.  Difference hierarchy in $\varphi$-spaces.  Algebra and Logic, 43(4):238–248, Jul 2004.
  * [SS15a] Matthias Schröder and Victor Selivanov.  Some hierarchies of qcb${}_{\mbox{0}}$-spaces.  Mathematical Structures in Computer Science, 25(8):1799–1823, 2015\.
  * [SS15b] Matthias Schröder and Victor L. Selivanov.  Hyperprojective hierarchy of qcb${}_{\mbox{0}}$-spaces.  Computability, 4(1):1–17, 2015.
  * [Wei00] Klaus Weihrauch.  Computable Analysis.  Springer, Berlin, 2000.


# Galaxy rotation curves in the light of the Spinor Theory of Gravity

M. Novello<EMAIL_ADDRESS>Centro de Estudos Avançados de Cosmologia
(CEAC/CBPF)
Rua Dr. Xavier Sigaud, 150, CEP 22290-180, Rio de Janeiro, Brazil.  A. E. S.
Hartmann<EMAIL_ADDRESS>Dipartamento di Scienza e Alta
Tecnologia, Università degli Studi dell’Insubria,
Via Valleggio 11, 22100 Como, and INFN Sez di Milano, Italy.  E. Bittencourt
<EMAIL_ADDRESS>Universidade Federal de Itajubá, Av. BPS 1303,
Itajubá-MG, 37500-903, Brazil

###### Abstract

We analyze the recently obtained static and spherically symmetric solution of
the Spinor Theory of Gravity (STG) which, in the weak field limit, presents an
effective Newtonian potential that contains an extra logarithmic behavior. We
apply this solution to the description of the galaxy rotation curves finding
an interesting analogy with the dark matter halo profile proposed by Navarro,
Frenk and White.

###### pacs:

95.30.Sf, 04.20.-q, 98.80.-k

Recently novhart20a ; novhart20b , some of us have analyzed the hypothesis
according to which gravity is controlled by spinor fields that combine in an
effective metric. In that proposal, the main hypothesis of General Relativity
(GR) that states that gravity may be interpreted as nothing but a modification
of the geometry of the underlying space-time is followed. However, the further
hypothesis of GR that states that the metric satisfies an independent
dynamical equation controlling the action of matter on the modifications of
the geometry is avoided. In STG, it is assumed that the geometry is an
efficient way to describe the gravitational interaction between bodies, but it
should not have a dynamical equation by its own; the space-time geometry
should be interpreted as an effective metric in the way considered by Ref.
novellovisservolovik . In other words, we are assuming that the geometry that
represents the gravitational interaction is not a fundamental object by
itself, but instead it is the result of the behavior of other existing fields
founded in Nature. In the past, different authors have considered gravity in
terms of a spin-2 field in a non-observable auxiliary Minkowski space-time
structure (see, for instance, Ref. feynman ). In novhart20a ; novhart20b , a
new program to consider an intimate connection between gravity and Fermi
(weak) interaction has begun. As previously discussed in these papers, the
main hypothesis of the Spinor Theory of Gravity relies upon a suggested
connection between weak interactions and gravity, namely their high degree of
universality, and the dimensional equivalence of their coupling constants in
natural units system. The same hypothesis has been also analyzed in distinct
contexts, as for instance in onofrio1 ; onofrio2 .

The general framework of the STG concerns two spinor fields (which we shall
call gravitational-neutrinos or g-neutrinos, for short). Here, we shall limit
our analysis to the case in which one of these fields is absent, but the
remaining spinor field possesses self-interaction provided by the Heisenberg
potential heisenberg ; heisenberg2 ; nambu . Thus, the Dirac-Heisenberg
equation satisfied by the g-neutrino takes the form

$i\gamma^{\mu}\nabla_{\mu}\,\Psi\,-\,2s\,(A+iB\gamma_{5})\,\Psi=0,$ (1)

with $A\equiv\overline{\Psi}\,\Psi$ and $B\equiv
i\,\overline{\Psi}\gamma_{5}\,\Psi$. The coupling constant $s$ has, in the
natural units system $c=\hbar=1$, dimesion of lenght squared. The associated
gravitational effective metric novhart20a  exhibits an intimate connection
between weak interaction and gravity and it is given by

$g_{\mu\nu}=\eta_{\mu\nu}-\kappa\,\Delta_{\mu}\,\Delta_{\nu},$ (2)

where $\kappa$ is the Einstein’s gravitational constant. The point of contact
between Fermi’s interaction and gravity comes through the weak current
$\Delta_{\mu}$ defined as

$\Delta_{\mu}=(J_{\mu}-I_{\mu})\left(\frac{g_{w}}{J^{2}}\right)^{1/4}\,.$ (3)

The vector and axial currents of $\Psi$ are, respectively, represented by
$J_{\mu}$ and $I_{\mu}$. We also denote $J^{2}=J_{\mu}\,J^{\mu}$ and $g_{w}$
is the weak constant. In natural units, both $g_{w}$ and $\kappa$ have
dimesion of lenght squared.

In the search of a static and spherically symmetric solutions of STG, we set
for a self-interacting g-neutrino, (see Ref. novhart20a )
$\Psi(r)=f(r)\,\Psi^{0},$ such that the constant spinor can be decomposed as

$\displaystyle\Psi^{0}$ $\displaystyle=\left(\begin{array}[]{l}\phi\\\ \eta\\\
\end{array}\right)\,.$

Moreover, we consider the case in which $\sigma_{1}\phi=\phi,$ and
$\sigma_{1}\eta=\eta.$ Thus, after a change of coordinates, it follows for the
light-like vector $\Delta_{\mu}$ that $\Delta_{2}=\Delta_{3}=0$ (see details
in Ref. novhart20a ). Finally, we arrive at the effective gravitational metric
– experienced by all kind of matter in the case of a spherically symmetric and
time-independent configuration – expressed in terms of the infinitesimal line
element

$ds^{2}=\left[1-\frac{1}{ra_{0}-2r\,\lambda\,\ln\left(\frac{r}{r_{0}}\right)}\right]\,dT^{2}-\left[1-\frac{1}{ra_{0}-2r\,\lambda\,\ln\left(\frac{r}{r_{0}}\right)}\right]^{-1}\,dr^{2}-r^{2}\,d\Omega^{2},$
(4)

where $a_{0}$, $\lambda$ and $r_{0}$ are parameters depending on the self-
coupling constant $s$ and on the solution $\Psi^{0}$ of the g-neutrino
novhart20a . In the absence of self-interaction ($\lambda\rightarrow 0$), this
reduces to the Schwarzschild metric of GR through the identification
$a_{0}=1/2m$, where $m$ is the object mass. In the weak field limit, we can
read out the effective gravitational potential as

$\Phi_{{\rm
STG}}(r)=-\frac{Gm}{r\left[1-4Gm\lambda\,\ln\left(\frac{r}{r_{0}}\right)\right]}.$
(5)

Thus, the galaxy rotation curves can be obtained through the virial theorem as

$V^{2}_{{\rm STG}}=r\frac{d\Phi_{{\rm STG}}}{dr}.$ (6)

In general, the expression for $V^{2}_{{\rm STG}}$ is rather complicate and,
on top of that, its correct behavior near the origin $r=0$ is still under
investigation, since the baryonic mass has independent components like bulge,
disk, gas, etc and each of them has a collection of possible profiles
according to the literature gilmore . However, the behavior of $V^{2}_{{\rm
STG}}$ far from the origin can roughly provide the pattern of the rotation
curves if the baryonic mass is constant. Furthermore, we expect that the
coupling constant $\lambda$ be small in order to recover the particle physics
results when the gravitational effects are negligible. Together, these
hypotheses lead Eq. (5) to the following approximation

$\Phi_{{\rm
STG}}(r)\approx-\frac{Gm}{r}\left[1+4Gm\lambda\,\ln\left(\frac{r}{r_{0}}\right)\right].$
(7)

The substitution of this expression into Eq. (6) yields

$V^{2}_{STG}\approx\frac{Gm}{r}+\frac{4G^{2}m^{2}\lambda}{r}\left[-1+\ln\left(\frac{r}{r_{0}}\right)\right].$
(8)

At this point, it is worth to mention that some phenomenological approaches
used to describe the circular velocities of stars around the host galaxy
assuming a dark matter component also gives a logarithmic leading term at
large values of the radial coordinate bajkova . One of the most accepted dark
matter halo profile showing this behavior is the model due to Navarro, Frenk &
White (NFW) navarroetal , for which the rotation velocity becomes

$V^{2}=\frac{GM(r)}{r}+\frac{4\pi
Gr_{s}^{3}\rho_{s}}{r}\left[-\frac{r}{r+r_{s}}+\ln\left(1+\frac{r}{r_{s}}\right)\right],$
(9)

where $M(r)$ is the baryonic mass enclosed within a sphere with radius $r$.
The free parameters of this model are the scale radius and the characteristic
density, here denoted by $r_{s}$ and $\rho_{s}$, respectively.

For large enough radius such that $r\gg r_{s}$, a straightforward comparison
between Eq. (8) and the approximate version of Eq. (9) gives the same
Newtonian component, besides the identification

$r_{0}=r_{s}\quad\mbox{and}\quad\lambda=\frac{\pi r_{s}^{3}\rho_{s}}{Gm^{2}}.$
(10)

This means that the phenomenological behavior observationally tested given by
Eq. (9) can also be reproduced from a more fundamental theory if one
understands the geometrical manifestation of gravity as a consequence of the
self-interacting spinor field in the lines of STG.

For the sake of illustration, let us consider the case of Milky Way, which is
a relative normal spiral galaxy, whose the baryonic mass is approximately
$6\times 10^{10}M_{\odot}$. In order to reproduce its rotation curve using the
NFW profile, the total mass of the dark matter halo is assumed to be of the
order $\sim 10^{12}{\rm M}_{\odot}$ (see Ref. wang  and references
therein)111Although the error bars can be large, we are only interested in the
magnitude of the free parameters in this preliminary analysis.. For
convenience, the astrophysicists usually rewrite the scale radius and the
characteristic density in terms of $M_{200}$ (the total mass of the particles
within a sphere with virial radius $r_{200}$ , which in turn is defined such
that the density of the dark matter halo is 200 times the critical density of
the universe $\rho_{\rm crit}$ ) and the halo concentration parameter $c\equiv
r_{200}/r_{s}$ through the formulas mo ; alefe

$r_{s}=28,8\left(\frac{{\rm M}_{200}}{10^{12}\,h^{-1}\,{\rm
M}_{\odot}}\right)^{0,43}\,{\rm
kpc},\quad\mbox{and}\quad\rho_{s}=\frac{200}{3}\frac{c^{3}\rho_{{\rm
crit}}}{\ln(1+c)-\frac{c}{1+c}},$ (11)

where h is the reduced Hubble constant. The concentration parameter can also
be given by dutton ; alefe

$c=10^{0,905}\left(\frac{{\rm
M}_{200}}{10^{12}h^{-1}M_{\odot}}\right)^{-0,101}.$ (12)

If we adopt ${\rm M}_{200}$ at the order of the dark matter halo mass, using
$\rho_{{\rm crit}}=143,84M_{\odot}/kpc^{3}$ and $h=0,671$ planck  into Eqs.
(12) and (11), we get $r_{s}\sim 24.2\,\mbox{kpc}$. By substitution of this
result into Eq. (10), we determine immediately $r_{0}$ and also obtain

$\lambda\sim 2.8\times 10^{-8}\,\mbox{eV},$ (13)

where we used the conversion factor $1\,\mbox{pc}^{-1}\sim 2.6\times
10^{-11}\,\mbox{eV}$. Of course, it is a first attempt to explain the galaxy
rotation curve in the realm of the STG, but this works as a consistency test
for our model. In fact, we see that these values are in agreement with the
assumptions made before about the domain of validity of Eq. (8) and, in
particular, it does not alter the particle physics once energy scale of self-
interaction is very small and, consequently, hard to be detected nowadays.
Notwithstanding, the most adequate procedure to find the values for the best
fit of $r_{0}$ and $\lambda$ is taking a large sample of galaxies (or doing
numerical simulations, and then) confronting the results with other dark
matter profiles and the particle physics, but this is left for further
investigation.

We conclude that in the realm of the STG there may be room for the explanation
of the observed profile of the galaxy rotation curves with no need of assuming
the hypothesis of the existence of a new unknown form of invisible matter in
the universe. Of course, the hypothesis of a dark matter component in the
context of RG concerns other effects like the gravitational lensing and the
growth of large scale structure, which have not been claimed to be solved
solely with the discussion developed along this letter and should be matter
for future work. However, the possibility of having an alternative way to
describe part of such weird component of the universe in terms of a
gravitational theory grounded upon particle physics should be taken into
account seriously.

## Acknowledgements

M. Novello thanks a fellowship from CNPq and FAPERJ.

## References

  * (1) M. Novello and A. E. S. Hartmann. Int. J. of Mod. Phys. A 36, 7 (2021) 2150051; ArXiv: gr/qc 2006.16810v03.
  * (2) M. Novello and A. E. S. Hartmann. Mod. Phys. Lett. A 36, 2 (2021) 2150003. ArXiv: gr/qc 2007.14393v2.
  * (3) Artificial Black Holes. Ed. M. Novello, M. Visser and G. Volovik. World Scientific, 2002.
  * (4) R. Feynman, F. Morinigo, D. Pines, Lectures on Gravitation. Westview Press, 2002.
  * (5) R. Onofrio, Mod. Phys. Lett. A 28, 7 (2013) 1350022.
  * (6) R. Onofrio, EuroPhys. Lett. 104 (2013) 20002.
  * (7) W. Heisenberg, Rev Mod Phys 29 (1957) 269.
  * (8) H.-P. Dürr, W. Heisenberg, H. Mitter, S. Schlieder and K. Yamazaki, Z. Nat. A 14 (1959) 441.
  * (9) Y. Nambu and G. Jona-Lasinio, Phys. Rev. D 122, 1 (1961) 345.
  * (10) G. Gilmore (Ed.), Galactic Structure and Stellar Populations, vol. 5, In Planets, Stars and Stellar Systems, T.D. Oswalt (Editor-in-Chief), Springer Science+Business Media Dordrecht 2013.
  * (11) A.T. Bajkova and V.V. Bobylev, Astron. Lett. 42, 9 (2016), 567-582.
  * (12) J. F. Navarro, C. S. Frenk and S. D. M. White, Astrophys. J. 462 (1996) 563-575.
  * (13) Wenting Wang, Jiaxin Han, Andrew P. Cooper, Shaun Cole, Carlos Frenk, Ben Lowing, Month. Not. R. Astron. Soc. 453, 1 (2015), 377-400.
  * (14) H. Mo, F. Van den Bosch and S. White, Galaxy formation and evolution. Cambridge University Press, 2010.
  * (15) A. de Almeida, L. Amendola, Viviana Niro, J. Cosm. Astrop. Phys. 08 (2018) 012.
  * (16) A. A. Dutton and A. V. Macciò, Mon. Not. Roy. Astron. Soc. 441 (2014) 3359.
  * (17) Planck Collaboration, P. A. R. Ade, N. Aghanim, M. Arnaud, M. Ashdown, J. Aumont et al., Planck 2015 results. XIII. Cosmological parameters, Astron. Astrophys. 594 (2016) A13.