# Notes on overt choice

Mathieu Hoyrup

► To cite this version:

Mathieu Hoyrup. Notes on overt choice. Computability, 2023, pp.1-19. 10.3233/COM-230458. hal-04164138v2

HAL Id: hal-04164138

https://inria.hal.science/hal-04164138v2

Submitted on 6 Sep 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Notes on overt choice

Mathieu Hoyrup*

September 6, 2023

## Abstract

Overt choice was recently introduced and thoroughly studied by de Brecht, Pauly and Schröder. They give estimates on the Weihrauch degree of overt choice on various spaces, and relate it to the topological properties of the space. In this article, we pursue this line of research, answering some of the questions that were left open. We show that overt choice on the rationals is not limit-computable. We identify the Weihrauch degree of overt choice on the space of natural numbers with the co-finite topology. We prove that the quasi-Polish spaces are the countably-based $T_0$-spaces on which a variant of overt choice, called $\Pi_2^0$ overt choice, is continuous. It extends a previous result that holds in the class of $T_1$-spaces. We also prove an effective version of this equivalence.

## Contents

<table><tr><td>1 Introduction</td><td>2</td></tr><tr><td>2 Background</td><td>3</td></tr><tr><td>2.1 Represented spaces</td><td>3</td></tr><tr><td>2.2 Weihrauch reducibility</td><td>3</td></tr><tr><td>2.3 The Scott domain P(N)</td><td>4</td></tr><tr><td>2.4 Overt choice</td><td>5</td></tr><tr><td>3 Overt choice on N<sub>cof</sub></td><td>6</td></tr><tr><td>4 Overt choice on Q</td><td>8</td></tr><tr><td>4.1 Comparison with lim</td><td>9</td></tr><tr><td>4.2 Lower bound on VC<sub>Q</sub></td><td>10</td></tr><tr><td>5 Characterization of quasi-Polish spaces</td><td>11</td></tr><tr><td>5.1 Π<sub>2</sub><sup>0</sup> overt choice</td><td>11</td></tr><tr><td>5.1.1 Subspaces of the lower reals</td><td>13</td></tr><tr><td>5.1.2 Removing compact points</td><td>13</td></tr></table>

<footnote>*Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy, France</footnote>
and prove the characterization of quasi-Polish spaces, and its effective versions.
We finish with Section 6, which contains a result about unique choice over $\mathcal{N}$.

# 2 Background

We briefly present the notions that are used throughout the article.

## 2.1 Represented spaces

Computations on various mathematical spaces are made possible by the use of
representations. More details can be found in [?, ?, ?].

The Baire space $\mathcal{N} = \mathbb{N}^\mathbb{N}$ is the space of infinite sequences of natural numbers, endowed with the product of the discrete topology on $\mathbb{N}$.

A **represented space** is a pair $(X, \delta)$ where $X$ is a set and $\delta : \subseteq \mathcal{N} \to X$ is a partial surjective function. A **name** of $x \in X$ is any $p \in \text{dom}(\delta)$ such that $\delta(p) = x$. A **multi-valued function** $f : \subseteq X \to Y$ assigns to each $x \in \text{dom}(f)$ a non-empty subset of $Y$. If $(X, \delta_X)$ and $(Y, \delta_Y)$ are represented spaces, then a partial function $F : \subseteq \mathcal{N} \to \mathcal{N}$ is a **realizer** of $f : \subseteq X \to Y$ if $F$ sends every name of every $x \in \text{dom}(f)$ to a name of some $y \in f(x)$. We say that $f : \subseteq X \to Y$ is **computable** if it has a computable realizer, and that $f$ is **continuous** if it has a continuous realizer.

An **effectively countably-based $T_0$-space** is a $T_0$ topological space $(X, \tau)$ coming with a countable basis $(B_i)_{i \in \mathbb{N}}$ and a c.e. set $E \subseteq \mathbb{N}^3$ such that $B_i \cap B_j = \bigcup_{(i,j,k) \in E} B_k$. An effectively countably-based $T_0$-space comes with its **standard representation** $\delta$ defined as follows: $p \in \mathcal{N}$ is a name of $x \in X$ if $p$ is an enumeration of the basic neighborhoods of $x$, i.e. if $\{i \in \mathbb{N} : x \in B_i\} = \{i \in \mathbb{N} : \exists n, p(n) = i+1\}$.

A subset $U$ of $X$ is an **effectively open set** if there exists a c.e. set $W \subseteq \mathbb{N}$ such that $U = \bigcup_{i \in W} B_i$. A set $A \subseteq X$ is $\Pi_2^0$ if it can be written as $A = \bigcap_{n \in \mathbb{N}} U_n \to V_n$, where $U_n, V_n$ are open sets and $U_n \to V_n = U_n^c \cup V_n$, where $U_n^c$ is the complement of $U_n$. A set $A$ is $\Pi_2^0$ if the sets $U_n, V_n$ are uniformly effectively open sets.

## 2.2 Weihrauch reducibility

The notion of Weihrauch reducibility is central in this article. It enables one to
measure the non-computability of multi-valued functions by comparing them.
We give the definition and refer to [?] for more details.

**Definition 2.1.** Let $f : \subseteq X \to Y$ and $g : \subseteq Z \to W$ be partial multi-valued functions between represented spaces. We say that $f$ is **Weihrauch reducible** to $g$, written $f \leq_W g$, if there exist computable functions $K : \subseteq \mathcal{N} \times \mathcal{N} \to \mathcal{N}$ and $H : \subseteq \mathcal{N} \to \mathcal{N}$ such that for every realizer $G$ of $g$, the function $p \mapsto K(p, G \circ H(p))$ is a realizer of $f$.

In particular, if $f \leq_W g$ and $g$ is computable, then $f$ is computable. We will
use the important limit operator.
**Definition 2.2.** The limit operator $\lim : \subseteq \mathcal{N}^{\mathbb{N}} \to \mathcal{N}$ sends a converging sequence to its limit.

## 2.3 The Scott domain $\mathcal{P}(\mathbb{N})$

The space $\mathcal{P}(\mathbb{N})$ is the space of subsets of $\mathbb{N}$. It comes with the inclusion ordering, denoted by $\leq$. For $x \in \mathcal{P}(\mathbb{N})$, we define $\uparrow x = \{y \in \mathcal{P}(\mathbb{N}) : x \leq y\}$ and $\downarrow x = \{y \in \mathcal{P}(\mathbb{N}) : y \leq x\}$.

$\mathcal{P}(\mathbb{N})$ is endowed with the Scott topology generated by the sets $\uparrow F$, where $F$ ranges over the finite subsets of $\mathbb{N}$. These basic open sets make $\mathcal{P}(\mathbb{N})$ an effectively countably-based $T_0$-space. For $x \in \mathcal{P}(\mathbb{N})$, $\uparrow x$ is $\Pi_2^0$ and $\downarrow x$ is closed.

Actually, the effectively countably-based $T_0$-spaces are, up to computable homeomorphisms, the subspaces of $\mathcal{P}(\mathbb{N})$. The embedding of an effectively countably-based $T_0$-space $X$ in $\mathcal{P}(\mathbb{N})$ sends $x \in X$ to the index set of its neighborhood basis $\{i \in \mathbb{N} : x \in B_i\}$.

A space is **quasi-Polish** if it embeds as a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$. An effectively countably-based $T_0$-space $X$ is a **precomputable quasi-Polish space** if there is a computable homeomorphism between $X$ and a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$. It is a **computable quasi-Polish** space if it is precomputable and the set $\{i \in \mathbb{N} : B_i^X \neq \emptyset\}$ is c.e., where $(B_i^X)_{i \in \mathbb{N}}$ is the basis of $X$. Equivalently, $X$ is computable if it embeds as a $\Pi_2^0$ subset $Y \subseteq \mathcal{P}(\mathbb{N})$ such that $\{i \in \mathbb{N} : B_i \cap Y \neq \emptyset\}$ is c.e., where $(B_i)_{i \in \mathbb{N}}$ is the basis of $\mathcal{P}(\mathbb{N})$.

We will use the next simple result, which is related to the fact that every quasi-Polish space is sober (see [?]). $\mathcal{P}(\mathbb{N})$ is endowed with the inclusion ordering, denoted $\leq$, and is a complete lattice.

**Lemma 2.1.** Let $X$ be a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$. If $(x_i)_{i \in \mathbb{N}}$ is a sequence in $X$ satisfying $x_i \leq x_{i+1}$, then $\sup x_i \in X$.

*Proof.* Let $U_n, V_n$ be open subsets of $\mathcal{P}(\mathbb{N})$ such that $X = \bigcap_n U_n \to V_n$. Let $n \in \mathbb{N}$. If $x = \sup x_i \in U_n$, there exists $i$ such that $x_i \in U_n$. As $x_i \in X$, one has $x_i \in V_n$. As $x_i \leq x$, $x \in V_n$ as well. $\square$

We will use the fact that the standard representation is precomplete [?].

**Lemma 2.2.** If $X$ is a represented space, $Y$ is an effectively countably-based $T_0$-space and $f : X \to Y$ is computable, then $f$ has a total computable realizer $F : \mathcal{N} \to \mathcal{N}$.

*Proof.* A proof can be found in [?]. The idea is simply that a partial realizer $F$ can be made total by inserting 0's in the output sequence to make sure that it is always infinite. By definition of the standard representation of $Y$, inserting 0's in a name of a point $y$ still yields a name of $y$. $\square$

We will use the following computable fixed-point theorem, similar to Kleene's second recursion theorem, and proved using a standard diagonalization. Let $\delta : \mathcal{N} \to \mathcal{P}(\mathbb{N})$ be the standard representation of $\mathcal{P}(\mathbb{N})$.
**Theorem 2.1.** Let $H: \mathcal{N} \times \mathcal{N} \to \mathcal{N}$ be computable. There exists a computable function $K: \mathcal{N} \to \mathcal{N}$ such that for all $p \in \mathcal{N}$, $\delta(H(p, K(p))) = \delta(K(p))$.

Intuitively, $K(p)$ is a fixed-point of the function $H(p, \cdot)$.

*Proof.* Let $\phi: \mathcal{N} \times \mathcal{N} \to \mathcal{P}(\mathbb{N})$ be a computable universal function, such that for every computable function $f: \mathcal{N} \times \mathcal{N} \to \mathcal{P}(\mathbb{N})$ there exists a computable function $s: \mathcal{N} \to \mathcal{N}$ satisfying $f(p, q) = \phi(s(p), q)$ for all $p, q \in \mathcal{N}$. Let $\Phi: \mathcal{N} \times \mathcal{N} \to \mathcal{N}$ be a computable realizer of $\phi$, which means that $\phi = \delta \circ \Phi$.

Let $F: \mathcal{N} \times \mathcal{N} \to \mathcal{N}$ be defined by $F(p, q) = H(p, \Phi(q, q))$. There exists a computable function $s: \mathcal{N} \to \mathcal{N}$ such that $\delta \circ F(p, q) = \phi(s(p), q)$. Let $K(p) = \Phi(s(p), s(p))$. One has $\delta \circ H(p, K(p)) = \delta \circ F(p, s(p)) = \delta(K(p))$. $\square$

In some results, we will need extra computability assumptions about the basis of the space.

**Definition 2.3.** Let $(X, \tau, (B_i)_{i \in \mathbb{N}})$ be an effectively countably-based space. We say that its basis $(B_i)_{i \in \mathbb{N}}$ is **co-overt** if the sets $X \setminus B_i$ are computably overt, uniformly in $i$.

In other words, the basis is co-overt if the set $\{(i, j) \in \mathbb{N}^2 : B_i \setminus B_j \neq \emptyset\}$ is c.e. We show that this property is preserved when embedding the space in $\mathcal{P}(\mathbb{N})$.

**Lemma 2.3.** Let $(X, \tau, (B_i^X)_{i \in \mathbb{N}})$ be an effectively countably-based space and $Y \subseteq \mathcal{P}(\mathbb{N})$ its canonical embedding. Let $(B_i)_{i \in \mathbb{N}}$ be the basis of $\mathcal{P}(\mathbb{N})$, defined as $B_i = \{A \subseteq \mathbb{N} : F_i \subseteq A\}$, where $(F_i)_{i \in \mathbb{N}}$ is a computable indexing of the finite subsets of $\mathbb{N}$. If the basis $(B_i^X)_{i \in \mathbb{N}}$ of $X$ is co-overt, then the basis $(B_i \cap Y)_{i \in \mathbb{N}}$ of $Y$ is co-overt as well.

*Proof.* Note that $B_i \cap Y$ is the image of $\bigcap_{j \in F_i} B_j^X$ via the embedding. There is a c.e. set $E \subseteq \mathbb{N}^2$ such that $\bigcap_{j \in F_i} B_j^X = \bigcup_{(i,k) \in E} B_k^X$. Therefore,

$$ \begin{align*} (B_i \cap Y) \setminus (B_j \cap Y) \neq \emptyset &\iff \bigcup_{(i,k) \in E} B_k^X \setminus \bigcap_{l \in F_j} B_l^X \neq \emptyset \\ &\iff \bigcup_{(i,k) \in E} \bigcup_{l \in F_j} B_k^X \setminus B_l^X \neq \emptyset \\ &\iff \exists k, l \text{ such that } (i,k) \in E, l \in F_j \text{ and } B_k^X \setminus B_l^X \neq \emptyset, \end{align*} $$

which is a c.e. condition. $\square$

## 2.4 Overt choice

To each space is associated a problem, introduced and thoroughly investigated in [?] and called overt choice. Overt choice takes as input a non-empty closed set $A$ presented via an enumeration of the basic open sets intersecting $A$, and outputs any element of $A$. Let us define it more precisely for the class of effectively countably-based $T_0$-spaces, although it can be defined with more generality in [?].
If $X$ is an effectively countably-based $T_0$-space, then $V(X)$ is the topological space of closed subsets of $X$ endowed with the topology generated by the sets

$$ \{A \in V(X) : B_i \cap A \neq \emptyset\}, $$

where $B_i$ is any basic open subset of $X$. These sets form a subbasis of the topology. The collection of finite intersections of these sets has a canonical effective numbering which makes $V(X)$ an effectively countably-based $T_0$-space.

An element $A \in V(X)$ is called an **overt closed** set, and is represented by enumerating the basic open sets $B_i$ intersecting $A$. Let $V_+(X)$ be the subspace of non-empty sets.

**Definition 2.4.** If $X$ is an effectively countably-based $T_0$-space, then **overt choice** on $X$ is $VC_X : V_+(X) \Rightarrow X$ defined by $x \in VC_X(A)$ iff $x \in A$.

Among the many results of [?], let us cite two results showing that overt choice behaves well on quasi-Polish spaces.

**Theorem 2.2** (Theorem 20 in [?]). If $X$ is quasi-Polish, then $VC_X$ is continuous. If $X$ is precomputably quasi-Polish, then $VC_X$ is computable.

**Theorem 2.3** (Theorem 22 in [?]). Let $X$ be a countably-based $T_1$-space. The following statements are equivalent:

* $VC_X$ is continuous,

* $X$ is quasi-Polish.

We will see in Section 5 that the equivalence breaks if one drops the $T_1$ assumption, but that it can be fixed by considering a stronger choice function, taking overt $\Pi_2^0$ sets rather than overt closed sets as inputs.

# 3 Overt choice on $N_{\text{cof}}$

The space $N_{\text{cof}}$ is the set of natural number $N$ endowed with the co-finite topology, generated by the complements of the finite subsets of $N$. The closed subsets of $N_{\text{cof}}$ are the finite sets and the whole set $N$. In [?] it is observed that this space is $T_1$ but not quasi-Polish, so overt choice is not continuous on $N_{\text{cof}}$. A more precise measure of its Weihrauch complexity is left open (Open Question 52 in [?]).

In this section, we identify the Weihrauch complexity of $VC_{N_{\text{cof}}}$. Let us reformulate what the task of $VC_{N_{\text{cof}}}$ is:

* $VC_{N_{\text{cof}}}$ takes as input a non-empty set $V \subseteq N$ which is either finite or all $N$, and which is described by an enumeration of the finite sets that do not contain $V$,

* $VC_{N_{\text{cof}}}$ should enumerate all the natural numbers except one element of $V$.
We will show that $VC_{N_{cof}}$ is Weihrauch equivalent to the following multifunction $H$.

**Definition 3.1.** Let $H: 2^\omega \to 2^\omega$ map an infinite binary sequence $s$ to any converging infinite binary sequence $t$ such that $\lim t_n = \limsup s_n \in \{0, 1\}$.

Said differently, $H$ takes the characteristic sequence of a set $A \subseteq \mathbb{N}$ and answers whether $A$ is infinite, with finitely many mind changes; $H$ is Weihrauch equivalent to the operator taking an enumeration of a set $E \subseteq \mathbb{N}$ and answering whether $E = \mathbb{N}$, with finitely many mind changes. Intuitively, $H$ transforms an instance of a $\Pi_2^0$ problem into an instance of a $\Delta_2^0$ problem. Another equivalent problem is the identity from the Sierpinski space to the 2 point discrete space, where each representation is replaced by its jump; the jump of a representation $\delta$ is a representation $\delta'$ such that a $\delta'$-name of a point is a sequence converging to a $\delta$-name of that point (see [?]).

As pointed out by a referee, $H$ is reducible to Sort but not to $C_{\mathbb{N}}$ (the latter is proved by observing that $H$ is a non-computable closed fractal, and applying Theorem 2.4 in [?]).

**Theorem 3.1.** $VC_{N_{cof}}$ is Weihrauch equivalent to $H$.

*Proof.* We first prove $VC_{N_{cof}} \leq_W H$. We are given a non-empty set $V \subseteq \mathbb{N}$, which is either finite or $\mathbb{N}$, presented via an enumeration of all the finite sets that do not contain $V$. Using $H$, we enumerate a set $S = \mathbb{N} \setminus \{a\}$ for some $a \in V$. $S$ will be defined as the union of a growing sequence of finite sets $S_i$. By induction, we will make sure that each $S_i$ does not contain $V$.

Whether $V = \mathbb{N}$ is equivalent to the condition that every finite set is enumerated in the overt presentation of $V$. Therefore, giving to $H$ the overt presentation of $V$, the output of $H$ tells us whether $V = \mathbb{N}$ with finitely many mind changes. More precisely, the output of $H$ is a binary sequence $t$ converging to 1 if $V = \mathbb{N}$, and to 0 if $V \neq \mathbb{N}$. We now explain the algorithm.

We start with $S_0 = \emptyset$, which indeed does not contain $V$. Once $S_i$ has been defined, let $a < b$ be the smallest two numbers that do not belong to $S_i$. We run the following two tests in parallel:

(a) $V \not\subseteq S_i \cup \{a\}$ and $\exists j \geq i, t_j = 0$,

(b) $V \not\subseteq S_i \cup \{b\}$.

One of them must succeed. Indeed, if (b) never succeeds, i.e. $V \subseteq S_i \cup \{b\}$, then $V \not\subseteq S_i \cup \{a\}$ (otherwise $V \subseteq S_i$, contradicting the induction hypothesis) and $V$ is finite, so $\lim t_j = 0$; therefore, the test (a) must succeed.

If test (a) succeeds first, then let $S_{i+1} = S_i \cup \{a\}$, if test (b) succeeds first, then let $S_{i+1} = S_i \cup \{b\}$. Note that $S_{i+1}$ does not contain $V$ by construction.

Let $S = \bigcup_{i \in \mathbb{N}} S_i$. We first show that $S$ does not contain $V$. If $V$ is finite, as the sets $S_i$ grow and do not contain $V$, their union does not contain $V$ either. If $V$ is infinite, then $\lim t_i = 1$ so there exists $i_0$ such that $t_j = 1$ for all $j \geq i_0$. For all $i \geq i_0$, test (a) does not succeed, so the minimal element outside $S_{i_0}$ is never added to $S_{i+1}$. Therefore, $S$ does not contain $a$, which belongs to $V = \mathbb{N}$.
We show that there is only one element outside $S$. If it is not so, then let $a < b$ be the two smallest such elements. Let $i$ be such that all the numbers smaller than $a$ or $b$ belong to $S_i$. By construction, one must have $S_{i+1} = S_i \cup \{a\}$ or $S_i \cup \{b\}$, contradicting the assumption that $a$ and $b$ are outside $S$. Therefore, we have shown that $S = \mathbb{N} \setminus \{a\}$ for some $a \in V$. It completes the proof of the Weihrauch reduction from $VC_{\mathbb{N}_{\text{cof}}}$ to $H$.

Conversely, we prove that $H \leq_W VC_{\mathbb{N}_{\text{cof}}}$. Given the characteristic function of a set $A \subseteq \mathbb{N}$, we first add 0 to $A$ to make sure that it is non-empty and define

$$V = \begin{cases} \mathbb{N} & \text{if } A \text{ is infinite,} \\ \{\max A\} & \text{if } A \text{ is finite.} \end{cases}$$

Let us first show that from $A$, we can compute an overt presentation of $V$.

*Claim 1.* A finite set $F$ does not contain $V$ if and only if $F \cap A = \emptyset$ or there exists $n \in A$ such that $n > \max(F \cap A)$.

*Proof of the claim.* One has the following equivalences:

$F$ contains $V$

$$\iff A \text{ is finite and } \max A \in F$$

$$\iff \text{there exists } k \in F \cap A \text{ such that there is no } n \in A \text{ satisfying } n > k$$

$$\iff F \cap A \neq \emptyset \text{ and there is no } n \in A \text{ satisfying } n > \max(F \cap A). \quad \square$$

The condition is c.e. relative to $A$, so one can enumerate the finite sets that do not contain $V$.

We give the overt presentation of $V$ to $VC_{\mathbb{N}_{\text{cof}}}$, which produces $n \in V$ given via an enumeration of $\mathbb{N} \setminus \{n\}$. Using this enumeration, we show how to decide with finite many mind-changes whether $A$ is finite or infinite. We can compute $n$ with finitely many mind changes, by guessing at each stage that $n$ is the smallest number that was not enumerated so far. Each time the value of $n$ changes, we start testing whether $A$ contains an element larger than $n$. As long as such an element is not found, we guess that $A$ is finite; when such an element is found, we guess that $A$ is infinite. Eventually, the value of $n \in V$ does not change any more so our guesses converge to the correct answer. $\square$

In particular, we easily obtain an upper bound on $VC_{\mathbb{N}_{\text{cof}}}$.

**Corollary 3.1.** $VC_{\mathbb{N}_{\text{cof}}}$ is Weihrauch reducible to $\text{lim}$.

*Proof.* It is easy to see that $H$ is reducible to $\text{lim}$. Given a binary sequence $s$, we define the binary sequence $t$ by $t_n = \sup_{p \geq n} s_p$. One has $\lim t_n = \lim \sup s_n$ so $t \in H(s)$, and $t$ can be computed from $s$ by applying $\text{lim}$. $\square$
# 4 Overt choice on $\mathbb{Q}$

Brattka [?] proved that overt choice on the space $\mathbb{Q}$ of rational numbers, endowed with the Euclidean topology, is not continuous. The results of [?] imply that the only subspaces of $\mathbb{R}$ on which overt choice is continuous are the Polish subspaces of $\mathbb{R}$, i.e. the $\Pi_2^0$ subsets of $\mathbb{R}$.

A more precise estimation of the Weihrauch degree of $VC_{\mathbb{Q}}$ was investigated in [?] and [?], and we contribute to this problem in this section.

## 4.1 Comparison with $\lim$

Whether $VC_{\mathbb{Q}}$ is Weihrauch reducible to $\lim$ is left as an open question (Open Question 50) in [?]. We show that the answer is negative.

**Theorem 4.1.** $VC_{\mathbb{Q}}$ is not Weihrauch reducible to $\lim$.

*Proof.* Similarly to [?], we work on the space $\mathbb{F}$ of finitary sequences $w1\bar{0}$ where $w \in \{0, 1\}^*$ (for some technical reason, we exclude the zero sequence). As $\mathbb{Q} \cap [0, 1]$ and $\mathbb{F}$ are easily computably homeomorphic, $VC_{\mathbb{Q}}$ is equivalent to $VC_{\mathbb{F}}$. We show that $VC_{\mathbb{F}}$ is not reducible to $\lim$ ($VC_{\mathbb{F}}$ is called ECP in [?]).

Observe that $VC_{\mathbb{F}}$ is reducible to $\lim$ iff $VC_{\mathbb{F}}$ is limit-computable, i.e. there is a computable procedure converting a name of a non-empty overt set $C \subseteq \mathbb{F}$ to a sequence of elements of $\mathbb{F}$ converging to an element of $C$ (the equivalence between reduction to $\lim$ and limit-computability can be found as Proposition 11.6.1 in [?]). We assume that $VC_{\mathbb{F}}$ is limit-computable and derive a contradiction. We build a name of an overt set $C \subseteq \mathbb{F}$, feed $VC_{\mathbb{F}}$ with that name and make sure that corresponding output sequence does not converge to an element of $C$. Note that we need to build a valid name of $C$ without assuming that the output sequence is well-defined and converges.

In other words, we are given a partial sequence $(x_p)_{p \in \mathbb{N}}$ of points of the Cantor space and build an overt set $C \subseteq \mathbb{F}$, such that if $x_p$ is total and converges to a finitary sequence, then that sequence is outside $C$. The sequence is partial, which means that the bits $x_p(i)$ may be undefined.

Let $u$ be a finite binary string. We say that $x_p$ extends $u$, written $x_p \succeq u$, if the prefix of length $|u|$ of $x_p$ is defined and coincides with $u$. We say that $x_p$ is incompatible with $u$, written $x_p \perp u$, if $x_p$ is defined at a position $i < |u|$ with $x_p(i) \neq u(i)$.

We introduce the following quantities, which can be infinite:

$$ \varphi^+(u) = \#\{p \in \mathbb{N} : x_p \succeq u\}, $$

$$ \varphi^-(u) = \#\{p \in \mathbb{N} : x_p \perp u\}. $$

The general idea is that if we observe that $x_p$ is more often extending $u$ than incompatible with $u$, i.e. if $\varphi^+(u) > \varphi^-(u)$, then $x_p$ might converge to $u\bar{0}$, so we remove $u\bar{0}$ from $C$. We need to do it carefully so that we can at the same time produce the overt information about $C$. We now give the details.
If $u, v$ are finite strings, then we also write $u \perp v$ if they are incomparable for the prefix ordering. Observe that if $u \perp v$, then $\varphi^+(v) \le \varphi^-(u)$, because each $x_p$ that extends $v$ is incompatible with $u$.

*Claim 2.* If $u \perp v$, then $\varphi^+(u) \le \varphi^-(u)$ or $\varphi^+(v) \le \varphi^-(v)$.

*Proof.* Indeed, if $\varphi^+(u) > \varphi^-(u)$, then $\varphi^+(v) \le \varphi^-(u) < \varphi^+(u) \le \varphi^-(v)$. $\square$

We define $\varphi_k^+(u) = \#\{p \in \mathbb{N} : x_p[k] \ge u\}$, where $x_p[k]$ is the part of $x_p$ computed at stage $k$. Note that $\varphi_k^+(u)$ is non-decreasing in $k$, and converges to $\varphi^+(u)$. We now define $C$:

$$A = \{w10^{k+2} : w \in 2^*, k \in \mathbb{N}, \varphi_k^+(w1) > \varphi^-(w1)\},$$

$$C = \mathbb{F} \setminus \bigcup_{\sigma \in A} [\sigma],$$

where $[\sigma]$ is the set of infinite sequences extending $\sigma$.

By definition, $C$ is closed. If $(x_p)_{p \in \mathbb{N}}$ is completely defined and converges to $w1\bar{0}$, then $\varphi^+(w1) = \infty$ and $\varphi^-(w1) < \infty$, so $w10^{k+2} \in A$ for some $k$, hence $w1\bar{0} \notin C$. It remains to show that we can compute an overt presentation of $C$.

*Claim 3.* Let $\sigma$ be a finite string. The cylinder $[\sigma]$ intersects $C$ iff no prefix of $\sigma$ belongs to $A$.

*Proof.* Of course, if $[\sigma]$ intersects $C$, then no prefix of $\sigma$ belongs to $A$. Conversely, assume that no prefix of $\sigma$ belongs to $A$. Let $u = \sigma 11$ and $v = \sigma 101$. These two words are incomparable, so by Claim 2, $\varphi^+(u) \le \varphi^-(u)$ or $\varphi^+(v) \le \varphi^-(v)$. In the first case, $u\bar{0} \in C$ because no prefix of this sequence belongs to $A$; in the second case, $v\bar{0} \in C$. In either case $[\sigma]$ intersects $C$. $\square$

Relative to the partial sequence $(x_p)_{p \in \mathbb{N}}$, the set $A$ is co-c.e., so the set of cylinders intersecting $C$ is c.e., which means that we can compute an overt presentation of $C$. $\square$

## 4.2 Lower bound on VC_Q

We also compare overt choice on $\mathbb{Q}$ with overt choice on $\mathbb{N}_{\text{cof}}$.

**Theorem 4.2.** $VC_{\mathbb{N}_{\text{cof}}}$ is strictly Weihrauch reducible to $VC_Q$.

*Proof.* We saw in Theorem 3.1 that $VC_{\mathbb{N}_{\text{cof}}}$ is Weihrauch equivalent to $\mathbb{H}$. We prove that $\mathbb{H}$ is reducible to $VC_{\mathbb{F}}$, which is equivalent to $VC_Q$. Given a set $A \subseteq \mathbb{N}$, we build an overt set $V_A \subseteq \mathbb{F}$ such that from any element of $V_A$ we can decide whether $A$ is infinite, with finitely many mind changes. We first add 0 to $A$ to make it non-empty.

If $A$ is infinite, then $V_A$ is the set of characteristic sequences of finite subsets of $A$. If $A$ is finite, then $V_A$ is the set of characteristic sequences of the (finite) subsets of $A$ containing $\max A$.
We show that from A one can uniformly compute an overt presentation of $V_A$. Let $\sigma$ be a finite binary string, $n = |\sigma|$ and F be the finite set of positions at which $\sigma$ has a 1.

*Claim 4.* The cylinder $[\sigma]$ intersects $V_A$ if and only if $F \subseteq A$ and $(\max(A \cap [0, n-1]) \in F$ or there exists $k \ge n$ such that $k \in A)$.

*Proof of the claim.* One has the following equivalences:

$[\sigma]$ does not intersect $V_A$

$$ \Leftrightarrow F \not\subseteq A \text{ or } (A \text{ is finite, } \max(A) < n \text{ and } \max(A) \notin F) $$

$$ \Leftrightarrow F \not\subseteq A \text{ or } (\max(A \cap [0, n-1]) \notin F \text{ and there is no } k \ge n \text{ in } A). \quad \square $$

The condition in the claim is c.e. relative to A, so $V_A$ is computably overt relative to A.

Given A, we feed $VC_F$ with $V_A$ which produces an element $x$ of $V_A$. Note that $x$ is the characteristic sequence of a finite set $F$. We show that using $x$, one can decide with finitely many mind changes whether A is infinite. Indeed, A is infinite iff there exists $n \in A$ such that $n > \max F$. From $x$, $\max F$ can be computed with finitely many mind changes, and then the existence of such an $n$ can be decided with one mind change.

We have shown that $VC_{N_{\text{cof}}}$ is reducible to $VC_Q$. Conversely, $VC_Q$ is not reducible to $VC_{N_{\text{cof}}}$ because $VC_{N_{\text{cof}}}$ is reducible to $\lim (\text{Corollary 3.1})$ while $VC_Q$ is not (Theorem 4.1). $\square$

# 5 Characterization of quasi-Polish spaces

In [?] it is proved that overt choice is continuous on quasi-Polish spaces, and among the $T_1$ countably-based spaces, the spaces on which overt choice is continuous are exactly the quasi-Polish spaces.

First, it is easy to see that the characterization fails for spaces that are not $T_1$. The following example is not quasi-Polish, but overt choice is continuous (and even computable) on that space.

*Example 5.1.* The space $N_\le$ is the set of natural numbers endowed with the lower topology, whose open sets are the sets $[n, +\infty)$. It is an effectively countably-based space which is not quasi-Polish. Indeed, it can be embedded in $P(N)$ by sending $n$ to the set $\{0, \dots, n\}$. The image of $N_\le$ under this embedding is not $\Pi_2^0$, because it does not satisfy Lemma 2.1.

However, overt choice on $N_\le$ is computable. Indeed, every non-empty closed subset of $N_\le$ contains 0, so the algorithm that immediately outputs 0 without even reading its input is a realizer of $VC_{N_\le}$.

We introduce a stronger variant of overt choice that does characterize the quasi-Polish spaces among the countably-based spaces. While overt choice only takes closed sets as inputs, this variant takes any $\Pi_2^0$ set as input.
## 5.1 $\Pi_2^0$ overt choice

Let $X$ be an effectively countably-based $T_0$-space.

**Definition 5.1.** $\mathcal{PV}(X)$ is the space of $\Pi_2^0$ subsets of $X$. A name of $A \in \mathcal{PV}(X)$ consists of a $\Pi_2^0$ presentation together with an overt presentation of $A$. $\mathcal{PV}_+(X)$ is the subspace of non-empty $\Pi_2^0$ subsets of $X$.

More precisely, if $(B_i)_{i \in \mathbb{N}}$ is the basis of $X$, then a name of $A \in \mathcal{PV}(X)$ is an enumeration of three sets $E, F, G \subseteq \mathbb{N}$ such that:

* $A = \bigcap_{n \in \mathbb{N}} U_n \to V_n$, where $U_n = \bigcup_{(i,n) \in E} B_i$ and $V_n = \bigcup_{(i,n) \in F} B_i$,

* $G = \{i \in \mathbb{N} : B_i \cap A \neq \emptyset\}$.

**Definition 5.2.** $\mathcal{PVC}_X \cdot \mathcal{PV}_+(X) \rightrightarrows X$ sends a non-empty $\Pi_2^0$ overt subset of $X$ to any element of that set.

We start with a few elementary facts about this choice principle. First, every closed set is $\Pi_2^0$, in a uniform computable way.

**Proposition 5.1.** If $X$ is an effectively countably-based $T_0$-space, then the inclusion map $I: \mathcal{V}(X) \to \mathcal{PV}(X)$ is computable.

*Proof.* If $A \subseteq X$ is closed, then $A = \bigcap_i B_i \to U_i$ where $U_i = \emptyset$ if $B_i \cap A = \emptyset$ and $U_i = B_i$ otherwise. The sets $U_i$ are uniformly effectively open from the overt presentation of $A$. $\square$

**Corollary 5.1.** If $X$ is an effectively countably-based $T_0$-space, then $\mathcal{VC}_X \leq_W \mathcal{PVC}_X$.

*Proof.* One has $\mathcal{VC}_X = \mathcal{PVC}_X \circ I$ which is reducible to $\mathcal{PVC}_X$ as $I$ is computable by Proposition 5.1. $\square$

**Proposition 5.2.** Let $Y$ be an effectively countably-based $T_0$-space. If $X \in \Pi_2^0(Y)$, then $\mathcal{PVC}_X \leq_W \mathcal{PVC}_Y$.

*Proof.* Every $\Pi_2^0$ subset of $X$ is a $\Pi_2^0$ subset of $Y$, and we show that the inclusion map $J: \mathcal{PV}(X) \to \mathcal{PV}(Y)$ is computable. First, a $\Pi_2^0(X)$ presentation of $A \subseteq X$ is a set $B \in \Pi_2^0(Y)$ such that $A = B \cap X$. Intersecting it with the $\Pi_2^0(Y)$ presentation of $X$ gives a $\Pi_2^0(Y)$ presentation of $A$. The basis of $X$ is given by $B_i^X = B_i^Y \cap X$, so the overt presentation of $A$ is the same in $X$ and in $Y$. As a result, $\mathcal{PVC}_X = \mathcal{PVC}_Y \circ J$ is reducible to $\mathcal{PVC}_Y$. $\square$

**Corollary 5.2.** If $X$ is quasi-Polish then $\mathcal{PVC}_X$ is continuous. If $X$ is a precomputable quasi-Polish space, then $\mathcal{PVC}_X$ is computable.

*Proof.* If $X$ is a precomputable quasi-Polish space, then $X$ embeds as a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$. By Proposition 5.2, $\mathcal{PVC}_X$ is reducible to $\mathcal{PVC}_{\mathcal{P}(\mathbb{N})}$ which is computable (which follows from [?] and [?]), so $\mathcal{PVC}_X$ is computable. The non-effective case is obtained by relativization. $\square$
We will see below that the first part of Corollary 5.2 is actually an equiv-
alence: X is quasi-Polish if and only if PVC<sub>X</sub> is continuous. In the next two
sections, we give examples showing that the second part of Corollary 5.2 is not
an equivalence, i.e. PVC<sub>X</sub> can be computable even though X is not precom-
putable.

**5.1.1 Subspaces of the lower reals**

We give a class of quasi-Polish spaces on which Π₂⁰ overt choice is computable,
without any computability assumption on the space.

We work in the computable quasi-Polish space [0, 1]≤, which is the unit
interval endowed with the lower topology whose open sets are ∅, [0, 1] and (x, 1]
for 0 ≤ x < 1.

**Proposition 5.3.** If $X \subseteq [0, 1] \leq$ is quasi-Polish, then $PVC_X$ is computable.

Proof. As $X$ is quasi-Polish, $X$ is a $\Pi_2^0$ subset of $[0, 1] \leq$. Given $A \in \mathcal{PV}(X)$ we can use the overt information about $A$ to compute $\sup A$. Here, “computing” $\sup A$ means enumerating the rational numbers $q < \sup A$, which can be done because $q < \sup A$ if and only if $(q, 1]$ intersects $A$. The same argument as in Lemma 2.1 shows that because $A$ is $\Pi_2^0$, it indeed contains $\sup A$. $\square$

In particular, if $X$ is a quasi-Polish space such that $PVC_X$ is computable,
then $X$ need not be precomputable.

**5.1.2 Removing compact points**

We give another way of obtaining quasi-Polish spaces on which PVC is com-
putable. It involves the *compact* points of the space, which play a particular
role in the computability of PVC.

**Definition 5.3.** Let $X$ be a topological space. We say that a point $x \in X$ is **compact** if the intersection of its neighborhoods is open.

In $\mathcal{P}(\mathbb{N})$, the compact points are the finite sets. In a $T_1$-space, the compact points are the isolated points.

**Proposition 5.4.** Let $X$ be a countably-based $T_0$-space. $X$ contains countably many compact points, and for each compact $x \in X$, the singleton $\{x\}$ is a difference of two open sets. Therefore, any set of compact points of $X$ is $\Sigma_2^0$.

*Proof.* To each compact point $x$ we associate a basic neighborhood $B_i$ of $x$ which is the intersection of the neighborhoods of $x$. This correspondence is one-to-one, because the space is $T_0$. For each compact $x$, one has $\{x\} = B_i \cap \text{cl}(x)$ which is a difference of two open sets. $\square$

We show that, assuming that the basis of the space $Y$ is co-overt (Definition 2.3), if $\Pi_2^0$ overt choice is computable on $Y$ then it is computable on any subspace $X$ obtained by removing a collection of compact elements of $Y$, with no effectiveness assumption on that collection.
**Theorem 5.1.** Let $Y$ be an effectively countably-based $T_0$-space whose basis is co-overt. Assume that $Y$ is quasi-Polish and $PVC_Y$ is computable.

If $X \subseteq Y$ contains all the non-compact elements of $Y$, then $PVC_X$ is computable.

The results of the next sections imply that the assumption that $Y$ is quasi-Polish is actually implied by the computability of $PVC_X$. Note that $X$ is automatically quasi-Polish, because it is a $\Pi_2^0$ subset of $Y$ (indeed, it is obtained from $Y$ by removing a set of compact elements, which is $\Sigma_2^0$ by Proposition 5.4).

Before presenting the proof of the theorem, let us formulate a particular case, which is another source of quasi-Polish spaces $X$ which are not precomputable, but such that $PVC_X$ is computable.

**Corollary 5.3.** Let $\mathcal{F}$ be a collection of finite subsets of $\mathbb{N}$, and let $X = \mathcal{P}(\mathbb{N}) \setminus \mathcal{F}$. $PVC_X$ is computable, although the quasi-Polish space $X$ need not be precomputable.

*Proof.* The space $Y = \mathcal{P}(\mathbb{N})$ satisfies all the assumptions of Theorem 5.1, and its compact elements are the finite sets. If we fix a computable bijection between $\mathbb{N}$ and the finite subsets of $\mathbb{N}$, and choose $\mathcal{F}$ so that the corresponding index set is not a $\Sigma_2^0$ subset of $\mathbb{N}$, then $X$ is not a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$. $\square$

*Proof of Theorem 5.1.* We assume that $X \subseteq Y \subseteq \mathcal{P}(\mathbb{N})$, so $Y$ is a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$. We are given a non-empty set $A \in \mathcal{PV}(X)$. The strategy is to define a non-empty set $B \subseteq A$ for which we can compute a description in $\mathcal{PV}(Y)$ (rather than $\mathcal{PV}(X)$). We then apply $PVC_Y$ to $B$ and compute an element of $B$, which will also belong to $A$. Let

$$K_A = \{x \in Y : x \text{ is a compact element of } Y \text{ and } \exists y \in A, y > x\}$$

and $B = A \setminus K_A$. In other words, $B$ is obtained by removing from $A$ the compact elements that are not isolated in $A$. An element $x \in A$ is isolated in $A$ if there exists an open set $U$ such that $U \cap A = \{x\}$. We show that one can compute a $\mathcal{PV}(Y)$-name of $B$.

**Claim 5.** One can compute a $\Sigma_2^0(Y)$ description of $K_A$ from the overt information about $A$.

*Proof.* To each basic open set $B_i^Y$ we associate the set $V_i$ of elements of $Y$ that are not lower bounds of $B_i^Y$. One has $V_i = \bigcup \{B_j^Y : B_j^Y \setminus B_i^Y \neq \emptyset\}$. Indeed,

$x$ is not a lower bound of $B_i^Y$

$\iff$ there exists $y \in B_i^Y$ such that $x \not\leq y$

$\iff$ there exists $y \in B_i^Y$ and $j$ such that $x \in B_j^Y$ and $y \notin B_j^Y$

$\iff$ there exists $j$ such that $x \in B_j^Y$ and $B_i^Y \setminus B_j^Y \neq \emptyset$.

Therefore, $V_i$ is effectively open, uniformly in $i$. We show that $K_A = \bigcup_{i \in E} B_i^Y \setminus V_i$ where $E = \{i \in \mathbb{N} : B_i^Y \cap V_i \text{ intersects } A\}$. As $E$ is c.e. relative to the overt description of $A$, it implies that $K_A$ is $\Sigma_2^0$ relative to $A$.
For each $i \in \mathbb{N}$, if $B_i^Y$ has a minimal element $x$ (i.e. an element which is also a lower bound of $B_i^Y$), then $B_i^Y \setminus V_i = \{x\}$ and $x$ is compact, otherwise $B_i^Y \setminus V_i$ is empty. Conversely, every compact element is the minimal element of some $B_i^Y$. If $B_i^Y \setminus V_i = \{x\}$, then $B_i^Y \cap V_i = \{y \in Y : y > x\}$. Therefore, $B_i^Y \cap V_i$ intersects $A$ iff there exists $y \in A, y > x$. $\square$

Note that $A \subseteq X \subseteq Y$, and from the overt information about $A$ as a subset of $X$ we can compute the overt information of $A$ as a subset of $Y$: an open set $U \subseteq Y$ intersects $A$ if and only if the $U \cap X$ intersects $A$.

From the overt information about $A$, which coincides with the overt information about $cl_Y(A)$, we can compute a $\Pi_2^0(Y)$ description of $cl_Y(A)$. The description of $A \in \tilde{\Pi}_2^0(X)$ is a set $G \in \tilde{\Pi}_2^0(Y)$ such that $A = G \cap X$.

*Claim 6.* One has $B = G \cap cl_Y(A) \setminus K_A$.

*Proof.* $B$ is clearly contained in the set on the right-hand side, because $B = A \setminus K_A \subseteq G \cap cl_Y(A) \setminus K_A$. The two sets coincide on the non-compact elements, because the non-compact elements belong to $X$, on which $G$ coincides with $A$. It remains to show that every compact element of $G \cap cl_Y(A) \setminus K_A$ belongs to $B$.

Let $x$ be a compact element of $cl_Y(A) \setminus K_A$ (we do not even need to assume $x \in G$). There exists $i$ such that $\{x\} = B_i^Y \setminus V_i$. As $x \in cl_Y(A)$, $B_i^Y$ intersects $A$. As $x \notin K_A$, $B_i^Y \cap V_i$ does not intersect $A$. As a result, $B_i^Y$ can only intersect $A$ at $x$, so $x \in A$. As $x \notin K_A$, $x \in B$. $\square$

Therefore, one can compute a $\Pi_2^0(Y)$-name of $B$.

*Claim 7.* $B$ is dense in $A$.

*Proof.* Assume that some open set $U$ intersects $A$ but not $B$. As $U \cap A$ is contained in $K_A$, it contains only compact elements that are not isolated in $A$. If $x \in A$ is compact and not isolated in $A$, then there exists $y \in A$ such that $x < y$. We start from some $x_0 \in U \cap A$; there exists $x_1 \in A$ such that $x_0 < x_1$. It implies that $x_1 \in U \cap A$, so we can iterate and build a sequence $x_0 < x_1 < x_2 < \dots$ in $U \cap A$. Note that $G$ is a $\Pi_2^0$ subset of $Y$, which is a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$, so $G$ is a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$. Each $x_i$ belongs to $G$, so $\sup x_i \in G$ by Lemma 2.1. $x$ is not compact because every neighborhood of $x$ contains some $x_i < x$, so $x \in X$. Therefore $x \in U \cap G \cap X = U \cap A$. It contradicts the fact that $U \cap A$ only contains compact elements. Therefore, $B$ is dense in $A$. $\square$

Therefore, $B$ is non-empty and the overt description of $A$ is also an overt description of $B$. All in all, we can compute a $\mathcal{PV}(Y)$ description of $B$ from a $\mathcal{PV}(X)$ description of $A$, and the proof is complete. $\square$

## 5.2 Characterization of quasi-Polish spaces

We now state and prove the characterization of quasi-Polish spaces in terms of $\tilde{\Pi}_2^0$ overt choice. The proofs will be given in the next section.

**Theorem 5.2.** Let $X$ be a countably-based $T_0$-space. The following statements are equivalent:
• $\mathrm{PVC}_X$ is continuous,

• $X$ is quasi-Polish.

At the same time, we prove effective versions of this result. In all the effective results, we assume that $X$ is computably overt, and that the complements of the basic open sets are uniformly computably overt.

The first result is the most general one, and implies Theorem 5.2 by relativization.

**Theorem 5.3 (Effective result, general case).** Let $X$ be an effectively countably-based $T_0$-space whose basis is co-overt. The following statements are equivalent:

• $\mathrm{PVC}_X$ is computable,

• $X$ is contained in a $\Pi_2^0$ space $Y$ whose basis is co-overt, and $X$ contains all the non-compact elements of $Y$.

Under certain assumptions, the statement can be simplified. The first case is when the space has no compact element.

**Theorem 5.4 (Effective result, no compact element).** Let $X$ be an effectively countably-based $T_0$-space whose basis is co-overt. If $X$ has no compact element, then the following statements are equivalent:

• $\mathrm{PVC}_X$ is computable,

• $X$ is a computable quasi-Polish space.

The second case is when the space is a subspace of a precomputable quasi-Polish space which is $T_1$. In that case, the compact elements need not be treated separately.

**Corollary 5.4 (Effective result, $T_1$-space).** Let $Z$ be a precomputable quasi-Polish space that is $T_1$. If $X \subseteq Z$ and the basis of $X$ is co-overt, then the following statements are equivalent:

• $\mathrm{PVC}_X$ is computable,

• $X$ is a computable quasi-Polish space.

*Proof.* Let $X \subseteq Z \subseteq \mathcal{P}(\mathbb{N})$, where $Z$ is $\Pi_2^0$ and $T_1$. First, the closure $\mathrm{cl}(X)$ of $X$ in $\mathcal{P}(\mathbb{N})$ is $\Pi_2^0$, because it is computably overt by assumption. Assume that $\mathrm{PVC}_X$ is computable. Let $Y \supseteq X$ be given by Theorem 5.3. The set $\mathrm{cl}(X) \cap Y \cap Z$ is $\Pi_2^0$ and contains $X$. Let us show that it actually coincides with $X$, implying that $X$ is $\Pi_2^0$ and therefore precomputable (it is then computable, as it is computably overt by assumption).

Assume that there exists $x \in \mathrm{cl}(X) \cap Y \cap Z \setminus X$. As $x \in Y \setminus X$, $x$ is a compact element of $Y$ so there exists $i$ such that $B_i \cap Y = B_i \cap \uparrow x$. As $Y$ is $T_1$ and $x \in Y$, one actually has $B_i \cap Y = \{x\}$. As $x \in \mathrm{cl}(X)$, $B_i$ intersects $X$. The only possible element of $B_i \cap X$ is $x$, so $x \in X$ which is a contradiction. Therefore, there is no such $x$, and $\mathrm{cl}(X) \cap Y \cap Z = X$. $\square$

The result applies in particular if $X$ is a subspace of a computable Polish space.
## 5.3 The proof

We give the rather involved proof of Theorem 5.3 and explain how Theorems 5.2 and 5.4 can be derived.

One direction is already proved: if $X$ and $Y$ satisfy the conditions of the Theorem, then $PVC_Y$ is computable (Corollary 5.1), so $PVC_X$ is computable by Theorem 5.1. We prove the other direction.

We assume that $X$ is embedded in $\mathcal{P}(\mathbb{N})$, and that $PVC_X$ is computable. Instead of basis $B_i^X$ we will use the basis induced by the basis $(B_i)_{i \in \mathbb{N}}$ of the Scott topology on $\mathcal{P}(\mathbb{N})$. Note that the set $\{(i, j) : B_i \setminus B_j \cap X \neq \emptyset\}$ is c.e. by Lemma 2.3. Let

$$N = \{x \in \mathcal{P}(\mathbb{N}) : x \in \mathrm{cl}(X \setminus \uparrow x)\}.$$

In the definition of $N$, the closure is taken in $\mathcal{P}(\mathbb{N})$ rather than $X$. Observe that $X \cap N$ is the set of non-compact elements of $X$. We know that $X \cap N$ is a $\Pi_2^0$ subset of $X$ (Proposition 5.4). Here we prove an effective version.

Claim 8. $N$ is a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$.

*Proof.* Let

$$V_i = \{x \in \mathcal{P}(\mathbb{N}) : x \text{ is not a lower bound of } X \cap B_i\}.$$

Let us show that $V_i = \bigcup\{B_j : B_i \setminus B_j \cap X \neq \emptyset\}$, which is effectively open by assumption about $X$. Indeed,

$x$ is not a lower bound of $X \cap B_i$

$$\iff \text{there exists } y \in X \cap B_i \text{ such that } x \not\leq y$$

$$\iff \text{there exist } y \in X \cap B_i \text{ and } j \text{ such that } x \in B_j, y \notin B_j$$

$$\iff \text{there exists } j \text{ such that } x \in B_j \text{ and } X \cap B_i \setminus B_j \neq \emptyset.$$

One has $N = \bigcap_i B_i \to V_i$, which is $\Pi_2^0$. Indeed,

$$
\begin{align*}
x \in \mathrm{cl}(X \setminus \uparrow x) &\iff [\forall i, x \in B_i \implies B_i \cap X \setminus \uparrow x \neq \emptyset] \\
&\iff [\forall i, x \in B_i \implies X \cap B_i \not\subseteq \uparrow x] \\
&\iff [\forall i, x \in B_i \implies x \text{ is not a lower bound of } X \cap B_i] \\
&\iff [\forall i, x \in B_i \implies x \in V_i]. \quad \square
\end{align*}
$$

The construction of the set $Y \subseteq \mathcal{P}(\mathbb{N})$ works in two steps:

* We build a set $Z \in \Pi_2^0(\mathcal{P}(\mathbb{N}))$ containing $X$ and such that $X \cap N = Z \cap N$,

* We then define $Y = Z \setminus \bigcup\{B_i \setminus B_j : B_i \setminus B_j \cap X = \emptyset\}$.

The construction of $Z$ uses the assumption that $PVC_X$ is computable. It may not be the case that $X$ contains all the non-compact elements of $Z$, and the definition of $Y$ fixes this problem. The core of the proof will be the construction of $Z$. Before, let us quickly explain how Theorems 5.4 and 5.2 follow.
Theorem 5.4 is a particular case: if $X$ contains no compact element, then $X = X \cap N = Z \cap N$ is $\Pi_2^0$, because $Z$ and $N$ are $\Pi_2^0$.

Theorem 5.2 is obtained by relativization to an oracle $A \subseteq \mathbb{N}$ that makes $\{(i, j) : B_i^X \setminus B_j^X \neq \emptyset\}$ c.e. and $\text{PVC}_X$ computable. The space $Y$ is quasi-Polish, and any subspace of $Y$ containing its non-compact elements is quasi-Polish as well.

**Building the set Z.** The set $Z$ will be built using the next result. In order to improve the readability, we denote $\delta(p)$ by $x_p$.

**Lemma 5.1.** Let $A, B$ be two disjoint subsets of $\mathcal{P}(\mathbb{N})$. If there exists a computable function $K : \mathcal{N} \to \mathcal{N}$ such that

$$x_{K(p)} = x_p \text{ if } x_p \in A,$$

$$x_{K(p)} \neq x_p \text{ if } x_p \notin B,$$

then there exists a $\Pi_2^0$ set $Z \subseteq \mathcal{P}(\mathbb{N})$ containing $A$ and disjoint from $B$.

*Proof.* Let $S = \{p \in \mathcal{N} : x_{K(p)} = x_p\}$. As $K$ is computable and equality on $\mathcal{P}(\mathbb{N})$ is $\Pi_2^0$, $S$ is a $\Pi_2^0$ subset of $\mathcal{N}$ which contains $\delta^{-1}(A)$ and is disjoint from $\delta^{-1}(B)$. A $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$ can be obtained by applying the Vaught transform to $S$: let

$$Z = \{x \in \mathcal{P}(\mathbb{N}) : S \text{ is co-meager in } \delta^{-1}(x)\},$$

which indeed contains $A$ and is disjoint from $B$. This transform was defined by Vaught in [?] and applied to representations of countably-based spaces in [?, ?, ?]. Let us prove that $Z$ is indeed $\Pi_2^0$, for the purpose of giving a self-contained presentation. Let $S_n \subseteq \mathcal{N}$ be uniformly effectively open sets such that $S = \bigcap_n S_n$. For each $x \in \mathcal{P}(\mathbb{N})$, $\delta^{-1}(x)$ is $\Pi_2^0$ hence Polish, so $S$ is co-meager in $\delta^{-1}(x)$ iff it is dense there, iff each $S_n$ is dense in $\delta^{-1}(x)$. Therefore, $x \in Z \iff$ for every $n \in \mathbb{N}$ and every finite sequence $\sigma \in \mathbb{N}^*$, if $[\sigma]$ intersects $\delta^{-1}(x)$ then $[\sigma] \cap S_n$ intersects $\delta^{-1}(x)$. In other words,

$$Z = \bigcap_{n, \sigma} \delta([\sigma]) \to \delta([\sigma] \cap S_n),$$

which is indeed a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$. $\square$

We now show that the computability of $\text{PVC}_X$ can be used to build a function $K$ satisfying the assumptions of Lemma 5.1.

**Lemma 5.2.** If $\text{PVC}_X$ is computable, then there exists a computable function $K : \mathcal{N} \to \mathcal{N}$ such that for all $p \in \mathcal{N}$,

$$x_{K(p)} = x_p \text{ if } x_p \in X, \qquad (1)$$

$$x_{K(p)} \neq x_p \text{ if } x_p \in N \setminus X. \qquad (2)$$

Lemma 5.1 then implies the existence of a $\Pi_2^0$ set $Z \subseteq \mathcal{P}(\mathbb{N})$ containing $X$ and disjoint from $N \setminus X$, as wanted.
Proof of Lemma 5.2. Let us start with an intuitive explanation of how K works.

For $x \in X \cup N$, let $S_x = (X \cap \downarrow x) \cup \mathrm{cl}_X(X \setminus \uparrow x)$. It is a closed subset of $X$, which is non-empty if $x \in X \cup N$. We build an algorithm that takes as input a name $p$ of $x \in X \cup N$, tries to produce a $\mathcal{PV}_+(X)$ name of $S_x$, feeds the computable realizer of $\mathcal{PVC}_X$ with that name, observe the output and use it to guide the construction of the name of $S_x$. The purpose is to force the realizer of $\mathcal{PVC}_X$ to output a name of $x$, when $x \in X$. We then define $K(p)$ as the output of the realizer of $\mathcal{PVC}_X$. If $x \in X$, then $x_{K(p)} = x_p$; if $x \in N \setminus X$, then $x_{K(p)} \neq x_p$ because $x_{K(p)}$ belongs to $S_x \subseteq X$.

Observe that the construction of the input of the realizer of $\mathcal{PVC}_X$ depends on its output, which itself depends on its input. We make the argument precise using the computable fixed-point theorem (Theorem 2.1).

We now give the details of how to build $K$.

Each $p \in \mathcal{N}$ induces a growing sequence $(x_p[n])_{n \in \mathbb{N}}$ of finite subsets of $\mathbb{N}$ whose union is $x_p \in \mathcal{P}(\mathbb{N})$. In the sequel, it may help the reader to think of $p$ as a name of $x \in X \cup N$ and of $q$ as the output of a realizer of $\mathcal{PVC}_X$ (however, for the moment $p$ and $q$ are arbitrary elements of $\mathcal{N}$). We first define a computable function $\eta: \mathcal{N} \times \mathcal{N} \to \mathbb{N}_<$ as follows:

$$ \eta(p, q) = \sup\{n \in \mathbb{N} : x_p[n] \leq x_q \text{ and } x_q[n] \leq x_p\}. \quad (3) $$

It is an equality testing function in the sense that $\eta(p, q) = \infty$ if and only if $x_p = x_q$. This function is computable (which means that there is an algorithm taking $p, q$ as inputs and computes a non-decreasing sequence of natural numbers converging to $\eta(p, q)$). Let

$$ D = \{(p, q) \in \mathcal{N} \times \mathcal{N} : x_p \in X \text{ or } x_p = x_q \in N\}. $$

We then define a function $\psi: D \to \mathcal{PV}_+(X)$ as follows:

$$ \psi(p, q) = \begin{cases} (X \cap \downarrow x_p \cap \uparrow x_p[n+1]) \cup (X \setminus \uparrow x_p[n]) & \text{if } n = \eta(p, q) < \infty, \\ (X \cap \downarrow x_p) \cup \mathrm{cl}_X(X \setminus \uparrow x_p) & \text{if } \eta(p, q) = \infty. \end{cases} $$

Note that when $\eta(p, q) = \infty$, $\psi(p, q)$ is $S_{x_p}$. We are now going to use the following properties of $\psi$:

* If $(p, q) \in D$ then $\psi(p, q) \neq \emptyset$,

* The function $\psi: D \to \mathcal{PV}_+(X)$ is computable.

They will be proved in Lemma 5.3, let us assume them for the moment.

The multifunction $\mathcal{PVC}_X \circ \psi: D \rightrightarrows X$ is computable. By Lemma 2.2, it has a total computable realizer $H: \mathcal{N} \times \mathcal{N} \to \mathcal{N}$. We write $H_p(q)$ for $H(p, q)$. By the computable fixed-point theorem (Theorem 2.1), a fixed-point of $H_p$ can be uniformly computed from $p$, i.e. there is a computable function $K: \mathcal{N} \to \mathcal{N}$ such that

$$ x_{H_p(K(p))} = x_{K(p)}. $$

We finally check that $K$ satisfies the sought conditions of Lemma 5.2. To lighten the notations, let us fix $p \in \mathcal{N}$ and put $q = K(p)$.
Claim 9. If $(p, q) \in D$, then $x_q \in \psi(p, q)$.

Proof of Claim 9. As $H$ is a realizer of $\mathbf{PVC}_X \circ \psi$, $x_{H_p(q)} \in \psi(p, q)$. As $q$ is a fixed-point of $H_p$, one has $x_q = x_{H_p(q)}$ so $x_q \in \psi(p, q)$. $\square$

Claim 10. If $x_p \in X$, then $x_q = x_p$.

Proof of Claim 10. As $x_p \in X$, one has $(p, q) \in D$, so $x_q \in \psi(p, q)$ by Claim 9.

Assume for a contradiction that $x_q \neq x_p$. It implies that $\eta(p, q)$ is a finite number $n$, so $x_q \in \uparrow x_p[n]$ by definition of $\eta$ (3). As $x_q \in \psi(p, q)$, one must have $x_q \in \downarrow x_p \cap \uparrow x_p[n+1]$. It implies that $\eta(p, q) \ge n+1$ which is a contradiction. Therefore, $x_q = x_p$. $\square$

Claim 11. If $x_p \in N \setminus X$, then $x_q \neq x_p$.

Proof of Claim 11. Equivalently, we show that if $x_p \in N$ and $x_q = x_p$, then $x_p \in X$. If $x_q = x_p \in N$, then $(p, q) \in D$, so $x_q \in \psi(p, q)$ by Claim 9. As $\psi(p, q) \subseteq X$, it implies that $x_p = x_q \in X$. $\square$

We have proved that if $x_p \in X$, then $x_{K(p)} = x_p$, and if $x_p \in N \setminus X$, then $x_{K(p)} \neq x_p$, which completes the proof of Lemma 5.2. $\square$

We now prove the computability of $\psi$.

**Lemma 5.3.** If $(p, q) \in D$ then $\psi(p, q) \neq \emptyset$, and the function $\psi: D \to \mathcal{PV}_+(X)$ is computable.

Proof of Lemma 5.3. We split $\psi$ into two parts and show that each part is computable.

Claim 12. The map $\psi_0: D \to \Pi_2^0(X)$ defined by

$$ \psi_0(p, q) = \begin{cases} X \cap \downarrow x_p \cap \uparrow x_p[n+1] & \text{if } n = \eta(p, q) < \infty, \\ X \cap \downarrow x_p & \text{if } \eta(p, q) = \infty, \end{cases} $$

is computable.

Proof of Claim 12. We need to show that $\psi_0(p, q)$ is a $\Pi_2^0$ subset of $X$, relative to and uniformly in $p, q$.

First, $\downarrow x_p$ is a $\Pi_2^0$ subset of $\mathcal{P}(\mathbb{N})$, relative to and uniformly in $p$. Indeed, one has $\downarrow x_p = \bigcap_{i \in \mathbb{N}} B_i \to W_i(p)$ where

$$ W_i(p) = \begin{cases} \mathcal{P}(\mathbb{N}) & \text{if } x_p \in B_i, \\ \emptyset & \text{if } x_p \notin B_i. \end{cases} $$

Next, let

$$ \psi'_0(p, q) = \begin{cases} \uparrow x_p[n+1] & \text{if } n = \eta(p, q) < \infty, \\ \mathcal{P}(\mathbb{N}) & \text{if } \eta(p, q) = \infty. \end{cases} $$
One then has $\psi_0'(p, q) = \bigcap_{n \in \mathbb{N}} U_n(p, q) \to V_n(p, q)$, where

$$ (U_n(p, q), V_n(p, q)) = \begin{cases} (\emptyset, \emptyset) & \text{if } \eta(p, q) < n, \\ (\mathcal{P}(\mathbb{N}), \uparrow x_p[n+1]) & \text{if } \eta(p, q) = n, \\ (\mathcal{P}(\mathbb{N}), \mathcal{P}(\mathbb{N})) & \text{if } \eta(p, q) > n. \end{cases} $$

The sets $U_n(p, q)$, $V_n(p, q)$ are effectively open relative to and uniformly in $n, p, q$ because they are increasing w.r.t. $\eta(p, q)$. Start with $(\emptyset, \emptyset)$, switch to $(\mathcal{P}(\mathbb{N}), \uparrow x_p[n+1])$ if the inequality $\eta(p, q) \ge n$ is eventually satisfied, and then switch to $(\mathcal{P}(\mathbb{N}), \mathcal{P}(\mathbb{N}))$ if $\eta(p, q) \ge n+1$ is eventually satisfied. $\square$

**Claim 13.** The map $\psi_1 : \mathcal{N} \times \mathcal{N} \to \mathcal{PV}(X)$ defined by

$$ \psi_1(p, q) = \begin{cases} X \setminus \uparrow x_p[n] & \text{if } n = \eta(p, q) < \infty, \\ \mathrm{cl}_X(X \setminus \uparrow x_p) & \text{if } \eta(p, q) = \infty, \end{cases} $$

is computable.

**Proof of Claim 13.** As it has closed images, it is sufficient to show that $\psi_1$ is computable when typed as $\psi_1 : \mathcal{N} \times \mathcal{N} \to \mathcal{V}(X)$. A basic open set $B_i$ intersects $\psi_1(p, q)$ iff there exists a finite number $n \le \eta(p, q)$ such that $B_i \setminus \uparrow x_p[n]$ intersects $X$, which is a c.e. condition by the co-overtness assumption about $X$. $\square$

We show that for $(p, q) \in D$, the closure in $\mathcal{P}(\mathbb{N})$ of $\psi(p, q)$ is $\downarrow x_p \cup \psi_1(p, q)$. It is clearly contained in that set. Let $U \subseteq \mathcal{P}(\mathbb{N})$ be an open set intersecting $\downarrow x_p$, i.e. containing $x_p$. First assume that $x_p \in X$. One has $x_p \in \psi_0(p, q)$ so $U$ intersects $\psi(x)$. Now assume that $x \in N \setminus X$. As $(p, q) \in D$, one has $\eta(p, q) = \infty$ so $\psi_1(p, q) = \mathrm{cl}_X(X \setminus \uparrow x_p)$. As $x_p \in N$, which means that $x_p \in \mathrm{cl}(X \setminus \uparrow x_p)$, $U$ intersects $X \setminus \uparrow x_p$ so $U$ intersects $\psi_1(p, q)$ hence $\psi(p, q)$.

Therefore, $\psi(p, q) = \psi_0(p, q) \cup \psi_1(p, q)$ is $\Pi_2^0$ relative to and uniformly in $(p, q) \in D$. We need to show that $\psi(p, q)$ is computably overt, relative to and uniformly in $(p, q) \in D$, which is implied by the following result.

**Claim 14.** For $(p, q) \in D$, $B_i$ intersects $\psi(p, q)$ if and only if $B_i$ intersects $\psi_1(p, q)$ or $x_p \in B_i$.

**Proof.** If $B_i$ intersects $\psi(p, q)$ but not $\psi_1(p, q)$, then $B_i$ intersects $\psi_0(p, q)$ which is contained in $\downarrow x_p$, therefore $x_p \in B_i$.

Conversely, assume that $x_p \in B_i$. If $x_p \in X$, then $x_p \in \psi_0(p, q)$ so $B_i$ intersects $\psi(x)$. If $x_p \in N \setminus X$, then $\eta(p, q) = \infty$ as $(p, q) \in D$, so $\psi_1(p, q) = \mathrm{cl}_X(X \setminus \uparrow x_p)$. As $x_p \in N$, which means that $x_p \in \mathrm{cl}(X \setminus \uparrow x_p)$, $U$ intersects $X \setminus \uparrow x_p$ so $U$ intersects $\psi_1(p, q)$ hence $\psi(p, q)$. $\square$

As a result, we have shown that the map $\psi : D \to \mathcal{PV}(X)$ is computable. Moreover, if $x_p \in X$ then $\psi_0(p, q) \ne \emptyset$, and if $x_p = x_q \in N$ then $\psi_1(p, q) \ne \emptyset$. Therefore, $\psi(p, q) \ne \emptyset$ for all $(p, q) \in D$. The proof of Lemma 5.3 is complete. $\square$

<figure><img src="image_2.png" /></figure>
**The set Y.** As announced, we define $Y = Z \cup \{B_i \setminus B_j : B_i \setminus B_j \cap X = \emptyset\}$. By definition, Y contains X. We need to show that:

1. Y is $\Pi_2^0$,

2. $\{(i,j) : B_i^Y \setminus B_j^Y \neq \emptyset\}$ is c.e.,

3. X contains all the non-compact elements of Y.

1. As Z is $\Pi_2^0$, it is sufficient to show that the set $\bigcup\{B_i \setminus B_j : B_i \setminus B_j \cap X = \emptyset\}$ is $\Sigma_2^0$. This set is $\bigcup_{i,j} B_i \setminus W_{i,j}$, where $W_{i,j} = B_j$ if $B_i \setminus B_j \cap X = \emptyset$, and $W_{i,j} = \mathcal{P}(\mathbb{N})$ otherwise. $W_j$ is effectively open, uniformly in i, j: we start enumerating $B_j$, and if we eventually see that $B_i \setminus B_j$ intersects X (a c.e. condition), then we enumerate $\mathcal{P}(\mathbb{N})$.

2. It is easy to see that $B_i \setminus B_j$ intersects Y if and only if it intersects X. One direction follows from the fact that Y contains X. In the other direction, if $B_i \setminus B_j$ intersects Y, then it was not removed from Z in the definition of Y, so it intersects X.

3. Let $x \in Y \setminus X$. We show that $x$ is compact in Y. As $x \notin N$, there exists $i$ such that $x \in B_i$ and $X \cap B_i = X \cap \uparrow x$. Let $y = \inf X \cap B_i$, we show that $x = y$. One has $x \le y$ and for every $j$,

$$ 
\begin{align*}
y \in B_j &\implies X \cap B_i \subseteq B_j && \text{because } X \cap B_i \subseteq \uparrow y \\
&\iff X \cap B_i \setminus B_j = \emptyset && \\
&\implies x \notin B_i \setminus B_j && \text{because } x \in Y \\
&\implies x \in B_j && \text{because } x \in B_i
\end{align*}
$$

so $y \le x$, therefore $y = x$.

Let $z \in Y \cap B_i$. If $z \in X$, then $x \le z$. If $z \notin X$, then by the previous argument applied to $z$, there exists $k$ such that $z \in B_k$ and $z = \inf X \cap B_k$. As $z \in B_i$, $X \cap B_k \subseteq X \cap B_i$ so $z = \inf X \cap B_k \ge \inf X \cap B_i = x$.

Therefore, $Y \cap B_i = Y \cap \uparrow x$, so $x$ is compact in Y and the proof is complete.

All in all, we have built the space Y satisfying all the conditions listed in Theorem 5.3.

# 6 Unique choice over the Baire space

The problem $\mathcal{U}\mathcal{C}_N$ is called unique choice over the Baire space and is defined as follows. It takes as input a singleton $\{p\} \subseteq \mathbb{N}$, given via an enumeration of a set E of finite sequences $\sigma$ of natural numbers such that $\{p\} = \mathcal{N} \setminus \bigcup_{\sigma \in E}[\sigma]$, and outputs p.

In [?] it is asked whether there exists an effectively countably-based space X which is effectively analytic, and such that $\mathcal{V}\mathcal{C}_X$ is not Weihrauch reducible to $\mathcal{U}\mathcal{C}_N$ (Open Question 49 in [?]). We answer positively.

We use the following result, which is Corollary 3.4 in [?]. We say that a point of a represented space is hyperarithmetical if it has a hyperarithmetical name.
**Lemma 6.1.** Let $X, Y$ be represented spaces and $f: X \to Y$. If $f \le_W UC_N$, then for every computable $x \in X$, $f(x)$ contains an hyperarithmetical element.

*Proof.* A computable name of $x$ is mapped to a $\Pi_1^0$ singleton in $N$. Its unique element is hyperarithmetical and computes (a name of) an element of $f(x)$. $\square$

**Proposition 6.1.** There exists a $\Sigma_2^0$ subspace $X \subseteq N$ such that $VC_X \not\le_W UC_N$.

*Proof.* We take $X$ such that $X$ is dense in $N$ and contains no hyperarithmetical element. It can be built as follows. Kleene [?] prove the existence of a non-empty set $P \in \Pi_1^0(N)$ containing no hyperarithmetical element. Let $X = \{\sigma \cdot p : \sigma \in N^* \text{ and } p \in P\}$. We apply Lemma 6.1 to $f = VC_X$. As $X$ is dense in $N$, $X$ is a computable element of $V(X)$. However, $VC_X(X) = X$ has no hyperarithmetical element, so $VC_X \not\le_W UC_N$. $\square$