\documentclass[10pt]{amsart}
\usepackage[OT1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage{amssymb,amsfonts}
\usepackage{graphicx}
\usepackage{tikz}

\newcommand{\reals}{\mathbf{R}}
\newcommand{\baire}{\omega^\omega}
\newcommand{\DX}{\mathcal{D}_c(X)}
\newcommand{\metx}{M(\mathbf{X})}
\newcommand{\MX}{\mathcal{M}_c(\mathbf{X})}
\newcommand{\CMX}{\mathcal{CM}_c(\mathbf{X})}
\newcommand{\concat}{\mathbin{^\frown}}
\newcommand{\abd}{\mathbf{a}}

\DeclareMathOperator{\id}{id}

\theoremstyle{plain}
\newtheorem{thm}{Theorem}
\newtheorem{lem}{Lemma}
\newtheorem{prp}{Proposition}
\newtheorem{cor}{Corollary}

\theoremstyle{definition}
\newtheorem{rem}{Remark}

\numberwithin{equation}{section}

\title[Maximality of degrees of metrics under computable reducibility]{On the maximality of degrees of metrics under computable reducibility}
\author{Ruslan Kornev}
\address{Sobolev Institute of Mathematics, 4 Acad. Koptyug Av., Novosibirsk, 630090, Russia}
\email{kornevrus@gmail.com}
\thanks{The reported study was funded by RFBR and JSPS, project number 20-51-50001.}


\begin{document}
\begin{flushright}
	UDC 510.5

	MSC 03F60
\end{flushright}
\begin{abstract}
  We study the semilattice $\CMX$ of degrees of computable metrics on a Polish space $\mathbf{X}$ under computable reducibility. It is proved that this semilattice does not have maximal elements if $\mathbf{X}$ is a noncompact space. It is also shown that the degree of the standard metric on the unit interval is maximal in the respective semilattice.

	\medskip
	\noindent \textsc{Keywords:} computable metric space, Cauchy representation, reducibility of representations, computable analysis
\end{abstract}
\maketitle

The present paper is a sequel to the article~\cite{K21a} in which the author started the investigation of the first-order properties of the degree structure of metrics on a Polish space under computable reducibility $\leq_c$. All necessary definitions, notations and preliminary results can be found there, below we briefly recall some of them.

We regard Polish spaces as structures of the kind $\mathbf{X}=(X,\tau,W,\nu)$, where $(X,\tau)$ is a Polish space in the classical sense (i.\,e., a separable completely metrizable space), $W$ is some countable dense subset of $X$, and $\nu$ is a numbering of $W$. Under this approach, it is natural to study a reducibility of complete metrics on $\mathbf{X}$ induced by computable reducibility of their respective Cauchy representations.

Recall that the \emph{Cauchy representation} of a Polish metric space $(X,\rho,W,\nu)$ with a distinguished dense subset $W$ and its numbering $\nu$ is a partial mapping $\delta_\rho$ from the Baire space $\baire$ onto $X$ that puts points $x\in X$ into correspondence with sequences of elements of $W$ quickly converging to $x$, in other words, for $f\in\baire$ and $x\in X$,
\begin{equation*}
	\delta_\rho(f)=x\text{ if }w_{f(n)}\to x\text{ and }\rho(w_{f(n)},x)<2^{-n}\text{ for all }n,
\end{equation*}
where $w_k=\nu k$ is the $k$th point in $W$. Every $f\in\baire$ with the above property is called a \emph{Cauchy name} for $x$.

More generally, a \emph{representation} of a set $X$ is a partial surjection $\delta\colon\baire\to X$. This notion generalizes the notion of a numbering of a countable set. Theory of representations and computability theory on represented spaces were studied by Kreitz and Weihrauch (see~\cite{KW85,W00}). Computable reducibility of representations was introduced in~\cite{KW85}, it is an analogue of the notion of reducibility of numberings. Representation $\delta_1$ of a set $X$ is said to be \emph{computably reducible} to a representation $\delta_2$ of $X$, $\delta_1\leq_c\delta_2$, if there is a Turing functional $\Phi_e$ such that
\begin{equation*}
	\delta(f)=\delta'\circ\Phi_e(f)\text{ for }f\in\mathrm{dom}(\delta).
\end{equation*}
If $\delta_X$ and $\delta_Y$ are representations of sets $X$ and $Y$, then we say that a partial function $F\colon X\to Y$ is $(\delta_X,\delta_Y)$-\emph{computable} if there is a Turing functional $\Phi_e$ such that
\begin{equation*}
	F\circ\delta_X(f)=\delta_Y\circ\Phi_e(f)\text{ for }f\in\mathrm{dom}(F\circ\delta_X).
\end{equation*}
It is clear that for representations $\delta_1,\delta_2$ of $X$ it holds $\delta_1\leq_c\delta_2$ iff the identity function $\id_X$ is $(\delta_1,\delta_2)$-computable.

Let $\mathbf{X}=(X,\tau,W,\nu)$ be a Polish space. The set of all complete metrics on $X$ compatible with topology $\tau$ is denoted by $\metx$. Having fixed $W$ and $\nu$, we can define the notion of computable reducibility of metrics on $\mathbf{X}$: for $\rho_1,\rho_2\in\metx$, we say that $\rho_1\leq_c\rho_2$ if $\delta_{\rho_1}\leq_c\delta_{\rho_2}$; in other words, reducibility of metrics is induced by reducibility of their Cauchy representations. Computable reducibility of metrics in $\metx$ leads to the degree structure $\MX$. The subordering of $\MX$ consisting of $c$-degrees of computable metrics on $\mathbf{X}$ is denoted by $\CMX$.

In~\cite{K21a} it was shown that $\CMX$ is a lower semilattice for any space $\mathbf{X}$. It was also proved that the degree of a metric $\rho$ such that the computable space $(X,\rho,W,\nu)$ contains a computable limit point is not minimal in $\CMX$. Main result of the present article is dual to the second mentioned result: we show that the degree of any metric on a noncompact space $\mathbf{X}$ is not maximal in $\CMX$. In other words, our main result can be stated as follows.

\begin{thm}\label{thm:1}
  Let $\mathbf{X}$ be a noncompact Polish space. Then $\CMX$ has no maximal elements.
\end{thm}

It is worth noting that this result is a direct generalization of a result from~\cite{K21} that shows that the degree of the standard metric $\rho_R(x,y)=\lvert x-y\rvert$ on the space $\mathbf{R}$ of real numbers is not maximal in the ordering of $c$-degrees of computable metrics on $\mathbf{R}$. Theorem~\ref{thm:1} can be fully relativized to the case of metrics of arbitrary complexity. In other words, the following holds.

\begin{thm}\label{thm:2}
	Let $\mathbf{X}$ be a noncompact Polish space. Then $\MX$ has no maximal elements.
\end{thm}

Although this result is obtained by a straightforward relativization, the very possibility of this relativization is a nontrivial fact which is based on a few important observations made throughout the proof of Theorem~\ref{thm:1}.

The following theorem is related to lattice embeddings into $\CMX$ and is again a direct generalization of a result from~\cite{K21}.

\begin{thm}\label{thm:3}
	Let $\rho$ be a computable metric on a noncompact space $\mathbf{X}$. Then the countable atomless Boolean algebra $\mathrm{Int}(1+\eta)$ embeds into $\CMX$ above $\deg_c(\rho)$ with preservation of joins and meets.
\end{thm}

Theorem~\ref{thm:1} does not necessarily hold in compact spaces, as the following counterexample shows: it turns out that $c$-degree of the standard metric on the unit interval $\mathbf{I}$ is maximal in $\mathcal{CM}_c(\mathbf{I})$. More formally, consider the Polish space $\mathbf{I}=(I,\tau_I,\mathbb{Q},\nu_\mathbb{Q})$, where $\tau_I$ is the usual topology on the unit interval $I=[0,1]$, $\mathbb{Q}$ is the set of rational numbers in $I$ and $\nu_\mathbb{Q}$ is a G\"odel numbering of $\mathbb{Q}$. Let $\rho_R$ also denote the restriction of the usual real metric to the unit interval. Then the following result holds. %Then $\deg_c(\rho_R)$ is a maximal element of $\mathcal{CM}_c(\mathbf{I})$, where $\rho_R$ also denotes the restriction of the usual real metric to the unit interval.

\begin{prp}\label{prp:1}
	$\deg_c(\rho_R)$ is a maximal element of $\mathcal{CM}_c(\mathbf{I})$.
\end{prp}

However, the following proposition shows that $\deg_c(\rho_R)$ is not a maximal element of $\mathcal{M}_c(\mathbf{I})$, that is, there exists a noncomputable metric strictly above $\rho_R$.

\begin{prp}\label{prp:2}
	There exists a $\mathbf{0'}$-computable metric $\rho^*$ on $\mathbf{I}$ such that $\rho_R<_c\rho^*$.
\end{prp}

The paper is organized as follows. Section~\ref{sec:1} contains the proofs of Theorems~\ref{thm:1} and~\ref{thm:2}. Section~\ref{sec:2} consists of the proof of Theorem~\ref{thm:3}. In the last section we prove the two results regarding the unit interval.

\section{Proof of Theorem~\ref{thm:1}}\label{sec:1}
\subsection{Proof idea}\label{subsec:idea}
Suppose $\mathbf{X}=(X,\tau,W,\nu)$ is a noncompact space and let $\rho\in\metx$ be a computable metric on $\mathbf{X}$. We need to construct a computable metric $\rho'\in\metx$ such that $\rho'>_c\rho$. More specifically, metric $\rho'$ should satisfy the following requirements for $e\in\omega$:
\begin{itemize}
	\item[$\mathcal{R}_e$:\enspace] $\rho'\not\leq_c\rho$ via $\Phi_e$,
	\item[$\mathcal{S}$:\enspace] $\rho\leq_c\rho'$.
\end{itemize}

Our proof is based on a generalization of the construction of Theorem 1 from~\cite{K21}. In that theorem the analogues of the above requirements were satisfied to obtain a computable metric (indeed, countably many pairwise nonequivalent computable metrics) strictly above the standard metric $\rho_R$ on the space of real numbers. Later, in Theorem 4.1 of~\cite{K21a}, it was shown that the strategy for negative requirements $\mathcal{R}_e$ can be generalized to the case of an arbitrary computable metric space with a computable limit point.

Let us briefly discuss the strategy for an isolated requirement $\mathcal{R}_e$. Recall that a metric space is compact if and only if it is complete and totally bounded. Since we only work with complete metric spaces, it is clear that the noncompact space $(X,\rho)$ must not be totally bounded, that is, there exists a rational number $r\in (0,\tfrac{1}{3})$ such that there is no finite $3r$-net in $(X,\rho)$. Since we do not know this $r$ in advance, our proof will be non-uniform. For the rest of the proof, fix such a number $r$. Fix also a $k\in\omega$ such that $2^{-k}<r$. For natural numbers $a,b,n$, denote
\begin{equation*}
	\bar{a}=(a,\ldots,a,\ldots)\in\baire,\ a^n\bar{b}=(a,\ldots,a,b,b,\ldots)\in\baire\text{ ($a$ repeated $n$ times)}.
\end{equation*}
Now back to the strategy for $\mathcal{R}_e$. We pick a special point $y=w_a\in W$ and wait until $\Phi_e(\bar{a})(k+1)\downarrow=u$. When it happens, we pick another special point $x=w_b$ such that $\rho(x,w_u)>3r$ (it is possible by the choice of $r$). Consider the sequence $a^p\bar{b}\in\baire$, where $p=\varphi_e(\bar{a})(k+1)$. By the Use Principle we have $\Phi_e(a^p\bar{b})(k+1)=\Phi_e(\bar{a})(k+1)=u$, thus, if we arrange our construction so that $a^p\bar{b}$ is a $\rho'$-name for $w_b$, then $\rho(w_u,w_b)>3r>r$ implies that $\Phi_e(a^p\bar{b})$ is not a $\rho$-name for $w_b$, which means that $\mathcal{R}_e$ is satisfied. In order to make $a^p\bar{b}$ a $\rho'$-name for $w_b$, it is sufficient to ensure that $\rho'(x,y)<2^{-p+1}$. This can be done by means of a continuous deformation of a small neighbourhood $B_\rho(x,r)$ of $x$ that makes $x$ close to $y$. A construction of such a deformation is described in~\cite{K21a}: we embed the metric space $(X,\rho,W)$ into the Banach space $\ell^\infty$ via the Fr\'echet embedding $F$ defined by
\begin{equation*}
	(F(x))_i=\rho(x,w_i)-\rho(w_i,w_0),
\end{equation*}
then the deformation in question is given by
\begin{equation*}
	\Gamma(z)=\bigl(\tfrac{r-\rho(x,z)}{r}\,h\bigr)\concat \bigl(F(y)-\tfrac{\rho(x,z)}{r}(F(y)-F(z))\bigr)
\end{equation*}
for $z\in B_\rho(x,r)$, where $h<2^{-p+1}$ and $\concat$ stands for the concatenation of a real and an infinite sequence of reals. Mapping $\Gamma$ can be extended to a map $\gamma\colon X\to\ell^\infty$ by letting $\gamma(z)=0\concat F(z)$ for $z\not\in B_\rho(x,r)$. Letting $\rho_1(z,v)=\lVert\gamma(z)-\gamma(v)\rVert$, we obtain a deformed metric $\rho_1$ carrying the topology $\tau$ (see Proposition 5.1 of~\cite{K21a}) and such that $\rho_1(x,y)=h$. Thus, $\rho_1$ satisfies $\mathcal{R}_e$. The following formulas express $\rho_1$ in terms of $\rho$; these are exactly Formulas (5.1)--(5.3) of~\cite{K21a}.

Let $z,v$ be points of $X$; assume that $\rho(x,z)\leqslant\rho(x,v)$. Then, if $\rho(x,z)<r$ and $\rho(x,v)\geqslant r$, we have
\begin{equation}\label{eq:1}
	\rho_1(z,v)=\max\bigl(\tfrac{r-\rho(x,z)}{r}\,h,\ \tfrac{\rho(x,z)}{r}\rho(z,v)+\tfrac{r-\rho(x,z)}{r}\rho(v,y)\bigr);
\end{equation}
if $\rho(x,v)<r$,
\begin{equation}\label{eq:2}
	\rho_1(z,v)=\max\bigl(\tfrac{\rho(x,v)-\rho(x,z)}{r}\,h,\ \tfrac{\rho(x,z)}{r}\rho(z,v)+\tfrac{\rho(x,v)-\rho(x,z)}{r}\rho(v,y)\bigr);
\end{equation}
and if $\rho(x,z)\geqslant r$, then
\begin{equation}\label{eq:3}
	\rho_1(z,v)=\rho(z,v).
\end{equation}

Metric $\rho'$ satisfying all requirements $\mathcal{R}_e$ will be a pointwise limit of metrics $\rho_s$ defined at stages of the construction. At each stage $s$ we also output a finite set $A_s\subseteq W$ such that:
\begin{enumerate}
	\item $\rho_s(z,v)=\rho_{s+1}(z,v)=\ldots=\rho'(z,v)$ for all $z,v\in A_s$,
	\item $A_s\subseteq A_t$ for $s\leqslant t$,
	\item $\bigcup_{i\in\omega}A_s=W$.
\end{enumerate}
This will imply that $\rho'$ is computable: informally speaking, we can compute the distance $\rho'(z,v)$ between two given special points $z$ and $v$ as soon as they both are contained in a set $A_s$.

Strategy for the global positive requirement $\mathcal{S}$ is also the same as in~\cite{K21}. In a nutshell, strategy from~\cite{K21} is based on the fact that the space $(\reals,\rho_R)$ is unbounded, thus we can choose balls of the same radius to be deformed in each $\mathcal{R}_n$-strategy, which gives us an algorithm of $c$-reduction of $\rho_R$ to the metric under construction. The same idea works here: by the choice of $r$, there exists an infinite sequence of nonintersecting balls $B_n$ of the same radius $r$. These balls can be used in the respective $\mathcal{R}_n$-strategies. The fact that the balls $B_n$ possess the same radius will permit us to prove Lemma~\ref{lem:lip} that asserts that $\rho'(z,v)\leqslant C\cdot\rho(z,v)$ for all $z,v\in X$ and some real number $C$. From the following basic lemma it then follows that $\rho\leq_c\rho'$.

\begin{lem}[\cite{D12}]\label{lem:bound}
	Let $d,d'\in\metx$. If there is a $C>0$ such that $d'(x,y)\leqslant C\cdot d(x,y)$ for all $x,y\in X$, then $d\leq_c d'$.
\end{lem}
% $(\tilde{x}_n)_{n\in\omega}$ such that $\rho(\tilde{x}_n,\tilde{x}_m)>2r$ for $n\neq m$. Moreover, such a sequence can be found effectively, given $r$ as a parameter. However, as we do not know the appropriate value of $r$ in advance, our proof will be non-uniform. For the rest of the proof, fix such a number $r$.

%We will see why this strategy succeeds later on in Lemma~\ref{lem:lip}. Meanwhile, we will explain the analytical reasoning behind the construction of $\rho'$ that is very similar to the one in Section 5 of~\cite{K21a}.

\subsection{Analytical reasoning}
In this subsection we explain the analytical reasoning behind the construction of $\rho'$ that is very similar to the one in Section 5 of~\cite{K21a}. Throughout the subsection, we often refer to Section 5 of~\cite{K21a} and use various results from there.

First of all, without loss of generality we will assume that the metric $\rho$ is bounded by 1: if this is not the case, then letting $\hat{\rho}(x,y)=\min(\rho(x,y),1)$ produces a computable metric $\hat{\rho}$ that is $c$-equivalent to $\rho$. This is an important detail. Later on we will see why it is convenient to bound the metric from above.

By the choice of the number $r$, there exists an infinite sequence $(\tilde{x}_n)_{n\in\omega}$ such that $\rho(\tilde{x}_n,\tilde{x}_m)>3r$ for $n\neq m$. Moreover, such a sequence can be found effectively, given $r$ as a parameter. We have $B_\rho(\tilde{x}_n,r)\cap B_\rho(\tilde{x}_m,r)=\varnothing$ for $m\neq n$. Denote $x_n=\tilde{x}_{2n}$, $y_n=\tilde{x}_{2n+1}$. Points $x_n$ and $y_n$ are used in the strategy for requirement $\mathcal{R}_n$. Let $h_n$ be a suitable small positive number defined in the strategy. Similarly to the proof of Theorem~4.1 of~\cite{K21a}, we build a sequence of metrics $\rho_n$ as follows. Let $\rho_0=\rho$. Suppose that the metric $\rho_n$ has already been defined. Define a map $\Gamma_{n+1}\colon B_{\rho_n}(x_n,r)\to\ell^\infty$ by
\begin{equation*}
  \Gamma_{n+1}(z)=\bigl(\tfrac{r-\rho_n(x_n,z)}{r}\,h_n\bigr)\concat \bigl(F_n(y_n)-\tfrac{\rho_n(x_n,z)}{r}(F_n(y_n)-F_n(z))\bigr),
\end{equation*}
where $F_n$ is the Fr\'echet embedding of $(X,\rho_n,W)$ into $\ell^\infty$. Extend $\Gamma_{n+1}$ to a mapping $\gamma_{n+1}\colon X\to\ell^\infty$ by putting $\gamma_{n+1}(z)=0\concat F_n(z)$ for $z\not\in B_{\rho_n}(x_n,r)$. Let $\rho_{n+1}(z,v)=\lVert\gamma_{n+1}(z)-\gamma_{n+1}(v)\rVert$.

Metric $\rho_{n+1}$ can be expressed in terms of $\rho_n$ by Formulas~\eqref{eq:1}--\eqref{eq:3}. The following lemma is an analogue of Proposition~5.4 of~\cite{K21a} and is proved in the same way.

\begin{lem}\label{lem:sec}
  For all $n\in\omega$, the following hold:
	\begin{enumerate}
		\item $\rho_n$ is a well-defined complete metric inducing topology $\tau$ on $X$;
    \item $\rho_n(z,v)=\rho_{n-1}(z,v)$ for all $z,v\not\in B_{\rho_{n-1}}(x_{n-1},r)$;
		\item\label{enum:series} The identity map $\id_X$ induces a series of surjective isometries $B_{\rho_0}[x_n,r]\to B_{\rho_1}[x_n,r]\to\ldots\to B_{\rho_n}[x_n,r]$.
	\end{enumerate}
  \begin{proof}
    Proceed as in the proof of Proposition~5.4 of~\cite{K21a}. The last clause follows from Propositions~5.2 and~5.3 of~\cite{K21a} and the fact that $\rho_0(x_n,\tilde{x}_m)>3r$ for all $\tilde{x}_m\neq x_n$, thus $\min(\rho_0(x_n,x_i)-r,\rho_0(x_n,y_i))>2r>r$ for $i<n$.
  \end{proof}
\end{lem}

\begin{cor}\label{cor:1}
  For all $z,v\in X$, there are at most two $n\in\omega$ such that $\rho_{n+1}(z,v)\neq\rho_n(z,v)$.
  \begin{proof}
    If $z,v\not\in\bigcup_{n\in\omega} B_{\rho_0}(x_n,r)$, then $\rho_n(z,v)=\rho_0(z,v)$ for all $n$. If $z\in B_{\rho_0}(x_n,r)$ for some $n$, then we may have $\rho_{n+1}(z,v)\neq\rho_n(z,v)$. A similar change may happen if $v\in B_{\rho_0}(x_m,r)$ for some $m$. Other than that, no changes will occur.
  \end{proof}
\end{cor}

Corollary~\ref{cor:1} implies that there exists a pointwise limit $\rho'$ of metrics $\rho_n$ that also is a metric on $X$.

\begin{lem}
  $\rho'$ is a complete metric inducing topology $\tau$ on $X$.
  \begin{proof}
    Repeat the proof of Proposition~5.5 of~\cite{K21a}.
  \end{proof}
\end{lem}

\begin{lem}\label{lem:lip}
  There exists a constant $C>0$ such that $\rho'(z,v)\leqslant C\cdot\rho_0(z,v)$ for all $z,v\in X$.
  \begin{proof}
    First of all we show that $\rho_1(z,v)\leqslant \tfrac{2}{r}\cdot\rho_0(z,v)$ for all $z,v\in X$. Fix arbitrary points $z,v\in X$. By symmetry we will assume that $\rho_0(x_0,z)\leqslant\rho_0(x_0,v)$. The following three possibilities can occur.

    \emph{Case 1.} $\rho_0(x_0,z)<r$ and $\rho_0(x_0,v)\geqslant r$. Then
    \begin{align*}
      \rho_1(z,v)
      &=\max\bigl(\tfrac{r-\rho_0(x_0,z)}{r}\,h_0,\ \tfrac{\rho_0(x_0,z)}{r}\rho_0(z,v)+\tfrac{r-\rho_0(x_0,z)}{r}\rho_0(y_0,v)\bigr)\\
      &\leqslant \max\bigl(\tfrac{\rho_0(x_0,v)-\rho_0(x_0,z)}{r}\,h_0,\ \tfrac{\rho_0(x_0,z)}{r}\rho_0(z,v)+\tfrac{\rho_0(x_0,v)-\rho_0(x_0,z)}{r}\rho_0(y_0,v)\bigr)\\
      &\leqslant \max\bigl(\tfrac{\rho_0(z,v)}{r}\,h_0,\ \tfrac{\rho_0(x_0,z)}{r}\rho_0(z,v)+\tfrac{\rho_0(z,v)}{r}\rho_0(y_0,v)\bigr)\\
      &=\max\bigl(\tfrac{h_0}{r},\ \tfrac{\rho_0(x_0,z)+\rho_0(y_0,v)}{r}\bigr)\cdot\rho_0(z,v).
    \end{align*}

    \emph{Case 2.} $\rho_0(x_0,v)<r$. One can obtain the same boundary in the same manner.

    \emph{Case 3.} $\rho_0(x_0,z)\geqslant r$. In this case, $\rho_1(z,v)=\rho_0(z,v)$.

    By construction, $h_0\leqslant 1$. We also have $\rho_0(x_0,z)+\rho_0(y_0,v)\leqslant 2$; this is the moment when we see why it was important to bound the metric $\rho_0$ from above. Since $r<1$, the claim follows.

    To prove the statement of the lemma, fix arbitrary $z,v\in X$ and consider the following possibilities.

    \emph{Case 1.} $z,v\not\in\bigcup_{n\in\omega} B_{\rho_0}(x_n,r)$. Then $\rho'(z,v)=\rho_0(z,v)$.

    \emph{Case 2.} $z\in B_{\rho_0}(x_n,r)$ and $v\in B_{\rho_0}(x_m,r)$, $n\neq m$ (say $n<m$). We have
    \begin{gather*}
      \rho_0(z,v)=\rho_1(z,v)=\ldots=\rho_n(z,v),\\
      \rho_0(z,x_n)=\rho_1(z,x_n)=\ldots=\rho_n(z,x_n),\\
      \rho_0(y_n,v)=\rho_1(y_n,v)=\ldots=\rho_n(y_n,v).
    \end{gather*}
    Then, arguing as above, we obtain $\rho_{n+1}(z,v)\leqslant\tfrac{2}{r}\cdot\rho_n(z,v)$. Similarly, we have $\rho_{n+1}(v,x_m)\leqslant\tfrac{2}{r}\cdot\rho_n(v,x_m)$ and $\rho_{n+1}(y_m,z)\leqslant\tfrac{2}{r}\cdot\rho_n(y_m,z)$. Then
    \begin{gather*}
      \rho_{n+1}(z,v)=\rho_{n+2}(z,v)=\ldots=\rho_m(z,v),\\
      \rho_{n+1}(v,x_m)=\rho_{n+2}(v,x_m)=\ldots=\rho_m(v,x_m),\\
      \rho_{n+1}(y_m,z)=\rho_{n+2}(y_m,z)=\ldots=\rho_m(y_m,z),
    \end{gather*}
    and after several careful substitutions we have
    \begin{align*}
      \rho_{m+1}(z,v)&\leqslant \max\bigl(\tfrac{h_m}{r},\ \tfrac{\rho_m(v,x_m)+\rho_m(y_m,z)}{r}\bigr)\cdot\rho_m(z,v)\\
      &\leqslant \max\bigl(\tfrac{h_m}{r},\ \tfrac{1}{r}\,\bigl(\tfrac{2}{r}\rho_0(v,x_m)+\tfrac{2}{r}\rho_0(y_m,z)\bigr)\bigr) \cdot\rho_m(z,v)\\
      &\leqslant \max\bigl(\tfrac{1}{r},\ \tfrac{4}{r^2}\bigr)\cdot\tfrac{2}{r}\cdot\rho_0(z,v)\\
      &=\tfrac{8}{r^3}\cdot\rho_0(z,v).
    \end{align*}
    After that, the distance between these points will never change, and $\rho'(z,v)=\rho_{m+1}(z,v)$.

    \emph{Case 3.} There is only one $n$ such that $z$ or $v$ (or both) is contained in $B_{\rho_0}(x_n,r)$. A similar boundary can be obtained in this case as well.

    Now, $C=\tfrac{8}{r^3}$ can serve as the constant from the statement of the lemma.
  \end{proof}
\end{lem}

We will also need the following observation.

\begin{lem}\label{lem:gtr}
	The following hold:
	\begin{enumerate}
		\item\label{enum:ball1} If $z\not\in\bigl(\bigcup_{n\in\omega} B_{\rho_0}[x_n,r]\bigr)\cup\{y_n\mid n\in\omega\}$, then for all $n\in\omega$
		\begin{equation*}
			\rho'(z,B_{\rho_0}[x_n,r])=\inf_{v\in B_{\rho_0}[x_n,r]}\rho'(z,v)\geqslant\min(\rho_0(x_n,z)-r,\rho_0(y_n,z)).
		\end{equation*}
		\item\label{enum:ball2} Let $B_1=B_{\rho_0}[x_n,r]$, $B_2=B_{\rho_0}[x_m,r]$ for $m\neq n$. Then
		\begin{equation*}
			\rho'(B_1,B_2)=\inf_{z\in B_1,v\in B_2}\rho'(z,v)\geqslant r.%\min(\rho_0(x_n,x_m)-2r,\rho_0(y_n,x_m)-r).
		\end{equation*}
	\end{enumerate}
	\begin{proof}
		\eqref{enum:ball1}. For all $v\in B_{\rho_0}[x_n,r]$ we have $\rho_0(z,v)=\rho_1(z,v)=\ldots=\rho_n(z,v)$, and after that $\rho_{n+1}(z,v)\geqslant\min(\rho_n(x_n,z)-r,\rho_n(y_n,z))=\min(\rho_0(x_n,z)-r,\rho_0(y_n,z))$ by the consideration before Proposition~5.2 of~\cite{K21a}. After that, distance between these points never changes, and $\rho'(z,v)=\rho_{n+1}(z,v)$.

		\eqref{enum:ball2}. Fix $m<n$ and fix two points $z\in B_{\rho_0}[x_n,r],v\in B_{\rho_0}[x_m,r]$. As above, we have  $\rho_0(x_n,v)=\rho_1(x_n,v)=\ldots=\rho_m(x_n,v)$, and after that $\rho_{m+1}(x_n,v)\geqslant\min(\rho_m(x_m,x_n)-r,\rho_m(y_m,x_n))=\min(\rho_0(x_m,x_n)-r,\rho_0(y_m,x_n))>2r$. Similarly, $\rho_{m+1}(y_n,v)\geqslant\min(\rho_0(x_m,y_n)-r,\rho_0(y_m,y_n))>2r$. Afterwards, we have $\rho_{m+1}(z,v)=\ldots=\rho_n(z,v)$ and $\rho_{n+1}(z,v)\geqslant\min(\rho_n(x_n,v)-r,\rho_n(y_n,v))>r$.
		%As above, we have  $\rho_0(x_n,v)=\rho_1(x_n,v)=\ldots=\rho_m(x_n,v)$, and after that $\rho_{m+1}(x_n,v)\geqslant\min(\rho_m(x_m,x_n)-r,\rho_m(y_m,x_n))=\min(\rho_0(x_m,x_n)-r,\rho_0(y_m,x_n))>2r$. Similarly, $\rho_{m+1}(y_n,v)\geqslant\min(\rho_0(x_m,y_n)-r,\rho_0(y_m,y_n))$. Afterwards, we have $\rho_{m+1}(z,v)=\ldots=\rho_n(z,v)$ and $\rho_{n+1}(z,v)\geqslant\min(\rho_n(x_n,v)-r,\rho_n(y_n,v))\geqslant\min(\rho_0(x_n,x_m)-2r,\rho_0(y_n,x_m)-r)$ by the same consideration.
	\end{proof}
\end{lem}

\subsection{Construction}
At the start of the construction, we are given a computable metric $\rho\in\metx$. We have fixed a rational $r\in (0,\tfrac{1}{3})$ such that the space $(X,\rho)$ does not have a finite $3r$-net and have chosen a $k\in\omega$ such that $2^{-k}<r$.

\emph{Stage $0$.} Let $A_0=\varnothing$, $\rho_0=\rho$.

\emph{Stage $s+1$.} Appoint a follower to requirement $\mathcal{R}_s$ as follows. Since $A_s$ is not a $3r$-net in $(X,\rho_0)$, we can find a special point $y_s$ such that $\rho_0(y_s,w)>3r$ for all $w\in A_s$. Let $A=A_s\cup\{w_s,y_s\}$. Let $e\leqslant s$ be the least number such that the requirement $\mathcal{R}_e$ has not been met yet and $\Phi_e(\bar{a})(k+1)\downarrow=u$ in $s+1$ steps, where $w_a=y_e$ is the follower of $\mathcal{R}_e$. If no such $e$ exists, end the stage. Otherwise, choose an element $x_e=w_b$ such that $\rho_0(x_e,w)>3r$ for all $w\in A\cup\{w_u\}$. Let $\rho_{s'}$ be the metric most recently defined in the construction. Proceed as described in Subsection~\ref{subsec:idea} with $\rho_{s'}$ in place of $\rho$ and obtain a new metric $\rho_{s+1}$. Let $A_{s+1}=A\cup\{w_u,x_e\}$.

\subsection{Verification}
Define $\rho'$ to be the pointwise limit of metrics defined in the construction. As in Subsection 6.2 of~\cite{K21a} it can be shown that $\rho'$ is a computable metric. By construction, $\rho_0(x_i,x_j)>3r$ for all $i\neq j$ and $\rho_0(x_i,y_j)>3r$ for all $i,j$. From the discussion in Subsection~\ref{subsec:idea} it is not hard to see that all requirements $\mathcal{R}_e$ are satisfied. By Lemmas~\ref{lem:bound} and~\ref{lem:lip}, $\rho\leq_c\rho'$.

\subsection{Proof of Theorem~\ref{thm:2}}
Suppose that $\rho\in\metx$ is an arbitrary metric on $\mathbf{X}$. We can carry out the construction from Theorem~\ref{thm:1} to obtain a metric $\rho'$ satisfying all negative requirements $\mathcal{R}_e$, then Lemmas~\ref{lem:bound} and~\ref{lem:lip} guarantee that $\rho\leq_c\rho'$. It remains to note that Lemma~\ref{lem:bound} holds in arbitrary metric spaces, not necessarily computable.

\section{Proof of Theorem~\ref{thm:3}}\label{sec:2}
As mentioned in the introduction, this theorem is a generalization of a result from~\cite{K21}, namely of Theorem 3 of that paper. The idea of the proof is the same as in~\cite{K21}: we embed the Boolean algebra $\mathcal{P}_{\mathrm{Comp}}(\omega)$ of computable subsets of $\omega$ into $\CMX$ and use the fact that $\mathrm{Int}(1+\eta)$ is embeddable into $\mathcal{P}_{\mathrm{Comp}}(\omega)$. Below we explain how to embed the 4-element Boolean algebra into $\CMX$, and then we give a hint how to generalize this construction to obtain the embedding of $\mathcal{P}_{\mathrm{Comp}}(\omega)$.% $(\mathcal{P}_{Comp}(\omega),\subseteq)$

To show that the 4-element Boolean algebra embeds into $\CMX$, we construct metrics $d_0,d_1$ and $d_{01}$ such that $\deg_c(d_{01})=\sup(\deg_c(d_0),\deg_c(d_1))$ and $\deg_c(\rho)=\inf(\deg_c(d_0),\deg_c(d_1))$ in $\CMX$. Metrics $d_0$ and $d_1$ will be built in a single construction and will satisfy the following requirements:
\begin{itemize}
	\item[$\mathcal{R}_{ie}$:] $d_i\nleq_c d_{1-i}$ via $\Phi_e$, for $i=0,1$ and $e\in\omega$,
	\item[$\mathcal{S}$:] $\rho\leq_c d_0,d_1$.
\end{itemize}

Fix a rational number $r\in (0,\tfrac{1}{3})$ such that there is no finite $3r$-net in $(X,\rho)$. Requirements $\mathcal{R}_{ie}$ and $\mathcal{S}$ are satisfied in the exact same manner as in Theorem~\ref{thm:1}.

Metric $d_{01}$ contains all deformations defined in the course of the construction of both $d_0$ and $d_1$. More formally, at stage 0 we initially define $d_{0,0},d_{1,0},d_{01,0}=\rho$. Suppose that at stage $s$ we finish the $\mathcal{R}_{0e}$-strategy and introduce a deformation $\Gamma\colon B_{d_{0,s'}}(x_{0e},r)\to\ell^\infty$:
\begin{equation*}
  \Gamma(z)=\bigl(\tfrac{r-d_{0,s'}(x_{0e},z)}{r}\,h_{0e}\bigr)\concat \bigl(F_{s'}(y_{0e})-\tfrac{d_{0,s'}(x_{0e},z)}{r}(F_{s'}(y_{0e})-F_{s'}(z))\bigr),
\end{equation*}
where $d_{0,s'}$ is the most recently defined approximation of the metric $d_0$ and $F_{s'}$ is the Fr\'echet embedding of $(X,d_{0,s'},W)$ into $\ell^\infty$. We add an analogue of $\Gamma$ to $d_{01}$ as follows. Let $\tilde{F}_{s''}$ be the Fr\'echet embedding of $(X,d_{01,s''},W)$ into $\ell^\infty$, where $d_{01,s''}$ is the most recently defined approximation of the metric $d_{01}$. Let
\begin{equation*}
  \tilde{\Gamma}(z)=\bigl(\tfrac{r-d_{0,s''}(x_{0e},z)}{r}\,h_{0e}\bigr)\concat \bigl(\tilde{F}_{s''}(y_{0e})-\tfrac{d_{0,s''}(x_{0e},z)}{r}(\tilde{F}_{s''}(y_{0e})-\tilde{F}_{s''}(z))\bigr),
\end{equation*}
Extend $\tilde{\Gamma}$ to a mapping $\tilde{\gamma}\colon X\to\ell^\infty$ in the usual way and let $d_{01,s}(z,v)=\lVert\tilde{\gamma}(z)-\tilde{\gamma}(v)\rVert$. In a similar way we incorporate into $d_{01}$ every deformation defined for the metric $d_1$.

To see that the $\mathcal{R}_{0e}$-strategy succeeds, let $y_{0e}=w_a$ and $x_{0e}=w_b$ be the points used in the strategy. When $\mathcal{R}_{0e}$ requires attention, say at stage $s$, let $u=\Phi_e(\bar{a})(k+1)$. Points $y_{0e}$ and $x_{0e}$ uniquely correspond to the requirement $\mathcal{R}_{0e}$, thus $y_{0e}$ is not used in the construction of $d_1$. In particular, $y_{0e}$ does not belong to any ball $B_\rho(x_{1e'},r)$, and by Lemma~\ref{lem:gtr} we have $d_1(y_{0e},w_u)>r$ regardless of where $w_u$ is located. This guarantees the success of diagonalization against $\Phi_e$.

Observe that $\deg_c(\rho)$ is the greatest lower bound of $\deg_c(d_0)$ and $\deg_c(d_1)$. To prove this, it suffices to show that, given a $d_0$-name and a $d_1$-name for $z\in X$, we can effectively construct a $\rho$-name for $z$. Fix a $d_0$-name $f_0$ and a $d_1$-name $f_1$ for $z$. Let $S=\{x_{ie},y_{ie}\mid i=0,1,e\in\omega\}$ and $T=\{x_{ie}\mid i=0,1,e\in\omega\}$. The construction appoints followers $v\in S$ in such a way that for each $n$ it holds $\rho(v,w_n)>3r$ for all followers $v$ appointed after stage $n+1$. Among the remaining (finitely many) followers, we are able to find such a $v^*$ that $\rho(v,w_n)>\tfrac{3r}{2}$ for all $v\neq v^*$. Clearly, this $v^*$ may be defined ambiguously, but there is a uniform computable way to find this element for each $w_n$. Consider the point $w_{f_0(k+2)}$ and find the corresponding $v^*$. We split the proof into the following three cases.% we have $\rho(w_{f_0(k+2)},v)>\tfrac{3r}{2}$ for all points $v\in S$ except at most one $v^*$, whose indices can be found effectively. The following three cases can occur.

\emph{Case 1.} $v^*=x_{1e^*}$ or $v^*=y_{1e^*}$ for some $e^*\in\omega$. Then by Lemma~\ref{lem:gtr}\eqref{enum:ball1} we have $d_0(w_{f_0(k+2)},B_\rho[x_{0e},r])>\tfrac{r}{2}$ for all $e$. Since $d_0(w_{f_0(k+2)},w_{f_0(n)})<\tfrac{r}{2}$ for $n\geqslant k+2$, then $w_{f_0(n)}\not\in\bigcup_{e\in\omega} B_\rho[x_{0e},r]$ for $n\geqslant k+2$, which means that $d_0(w_{f_0(m)},w_{f_0(n)})=\rho(w_{f_0(m)},w_{f_0(n)})$ for all $m,n\geqslant k+2$, thus
\begin{equation*}
	\bigl(f_0(k+2),f_0(k+3),\ldots\bigr)
\end{equation*}
is a $\rho$-name for $z$.

\emph{Case 2.} $v^*=y_{0e^*}$ for some $e^*\in\omega$. Then $d_0(w_{f_0(k+2)},B_\rho[x_{0e},r])>\tfrac{r}{2}$, thus $d_0(z,B_\rho[x_{0e},r])>\tfrac{r}{4}$ for all $e\neq e^*$. The following possibilities can then hold:
\begin{enumerate}
	\item $z\in B_\rho[x_{0e^*},r]$. Then clearly $\rho(z,v)>2r$ for all $v\in S-\{x_{0e^*}\}$.
	\item $z\not\in\bigcup_{e\in\omega} B_\rho[x_{0e},r]$. In this case, $\rho(z,w_{f_0(k+2)})=d_0(z,w_{f_0(k+2)})<\tfrac{r}{4}$ by~\eqref{eq:3} and $\rho(z,v)>\tfrac{5r}{4}$ for all $v\in S-\{x_{0e^*}\}$.
\end{enumerate}

By Lemma~\ref{lem:gtr}\eqref{enum:ball1}, in both of these cases for all $e\in\omega$ we have $d_1(z,B_\rho[x_{1e},r])>\tfrac{r}{4}$, i.\,e., $z$ is far from all balls used in the construction of $d_1$. Then, similarly to the above, $d_1(w_{f_1(m)},w_{f_2(n)})=\rho(w_{f_1(m)},w_{f_1(n)})$ for all $m,n\geqslant k+2$, and
\begin{equation*}
	\bigl(f_1(k+2),f_1(k+3),\ldots\bigr)
\end{equation*}
is a $\rho$-name for $z$.

\emph{Case 3.} $v^*=x_{0e^*}$, $e^*\in\omega$. We break this case into the following subcases:
\begin{enumerate}
	\item $w_{f_0(k+2)}\not\in B_\rho[x_{0e^*},r]$. As above, we have $d_0(z,B_\rho[x_{0e},r])>\tfrac{r}{4}$ for all $e\neq e^*$, thus $z\in B_\rho[x_{0e^*},r]$ or $z\not\in\bigcup_{e\in\omega} B_\rho[x_{0e},r]$.
	\item $w_{f_0(k+2)}\in B_\rho[x_{0e^*},r]$. Since $d_0(w_{f_0(k+2)},z)<\tfrac{r}{4}$, by Lemma~\ref{lem:gtr} we must have $\rho(z,x_{0e^*})<\tfrac{5r}{4}$ or $\rho(z,y_{0e^*})<\tfrac{r}{4}$.
\end{enumerate}
In any of these subcases, arguing as in Case 2, we obtain that $d_1(z,B_\rho[x_{1e},r])>\tfrac{r}{4}$ for all $e\in\omega$. As a result, $\bigl(f_1(k+2),f_1(k+3),\ldots\bigr)$ is a $\rho$-name for $z$.

Note that we can effectively decide which of the cases 1--3 occurs. It implies that some $\rho$-name for $z$ can be computed, using $f_0$ and $f_1$.

It is not hard to see that $d_0,d_1\leq_c d_{01}$. To prove that $\deg_c(d_{01})$ is the least upper bound of $\deg_c(d_0)$ and $\deg_c(d_1)$, it suffices to show that every $d_{01}$-name $f$ can be translated into a $d_0$-name or a $d_1$-name for the same element $z$. Fix $z\in X$ and a $d_{01}$-name $f$ for $z$. As earlier, we can compute the indices $i,e$ of a $v^*\in S$ such that $\rho(w_{f(k+2)},v)>\tfrac{3r}{2}$ for all $v\in S-\{v^*\}$. Suppose that $v^*=x_{ie}$. Then Lemma~\ref{lem:gtr} readily implies that
\begin{equation*}
	B_{d_0}[w_{f(k+2)},\tfrac{r}{2}]\cap\bigcup_{x\in T-\{v^*\}} B_\rho[x,r]=\varnothing.
\end{equation*}
Similarly, if $v^*$ is a follower $y_{ie}$, then $B_{d_0}[w_{f(k+2)},\tfrac{r}{2}]\cap\bigcup_{x\in T-\{x_{ie}\}} B_\rho[x,r]=\varnothing$. Now, suppose that $i=0$, i.\,e., $v^*=x_{0e}$ or $v^*=y_{0e}$. By the above, we have $w_{f(n)}\not\in\bigcup_{v\in T-\{x_{0e}\}} B_\rho[v,r]$ for all $n\geqslant k+2$. Since we add the same deformation $\Gamma$ of the ball $B_\rho(x_{0e},r)$ to both metrics $d_0$ and $d_{01}$, then by induction on $s$ it is not hard to show that $d_{01,s}(w_{f(n)},w_{f(m)})=d_{0,s}(w_{f(n)},w_{f(m)})$ for all $n,m\geqslant k+2$ and all $s$, thus $d_{01}(w_{f(n)},w_{f(m)})=d_0(w_{f(n)},w_{f(m)})$ for these $n,m$, and $\bigl(f(k+2),f(k+3),\ldots\bigr)$ is a $d_0$-name for $x$. We argue in the same manner in case $i=1$.

To show that $\mathcal{P}_{\mathrm{Comp}}(\omega)$ embeds into $\CMX$, construct an infinite sequence of metrics $d_{\{i\}}$, $i\in\omega$, similarly to the above, and for any computable set $A$ construct the metric $d_A$ that contains all deformations defined for the metrics $d_i$ for all $i\in A$. Then $\deg_c(d_{A\cap B})$ will be the greatest lower bound of $\deg_c(d_A)$ and $\deg_c(d_B)$, and $\deg_c(d_{A\cup B})$ will be the least upper bound of $\deg_c(d_A)$ and $\deg_c(d_B)$, for arbitrary computable sets $A$ and $B$.

\section{The unit interval}%\label{sec:2}
\subsection{Proof of Proposition~\ref{prp:1}}
We will need the following facts.

\begin{lem}[\cite{W00}, Corollary 6.2.5]
	Let $f$ be a continuous real function defined on a compact set $K\subseteq\reals$. Then $\max_{x\in K}f(x)$ and $\min_{x\in K}f(x)$ are computable uniformly in $f$ and $K$.
\end{lem}

\begin{lem}\label{lem:rc}
	Let $\mathbf{X}$ be a Polish space and let $\rho,\rho'\in\metx$ be computable metrics on $\mathbf{X}$ such that $\rho\leq_c\rho'$. Then $\rho'$ is a $(\rho,\rho,\rho_R)$-computable function.%, where $\rho_R$ is the standard representation of the reals.
	\begin{proof}
		Immediate.
	\end{proof}
\end{lem}

Suppose that $\rho\in M(\mathbf{I})$ is a computable metric on $\mathbf{I}$ such that $\rho_R\leq_c\rho$. We need to prove that $\rho\leq_c\rho_R$. By Lemma~\ref{lem:rc}, $\rho$ is $(\rho_R,\rho_R,\rho_R)$-computable. Then the projection functions $\rho_q(x)=\rho(q,x)$ are $(\rho_R,\rho_R)$-computable uniformly in $q\in\mathbb{Q}$. Denote $q_n=\nu_\mathbb{Q} n$.

Let $f$ be a $\rho$-name for $x\in I$. We want to compute a $\rho_R$-name for $x$. This can be done as follows: for $n\in\omega$, we will progressively compute rational $a_n,b_n$ such that $B_\rho[q_{f(k)},2^{-k}]\subseteq [a_n,b_n]$ for some $k$ and the length of intervals $[a_n,b_n]$ tends to zero. Since $\bigcap_k B_\rho[q_{f(k)},2^{-k}]=x$, in the end we obtain a $\rho_R$-name for $x$.

At stage $n$, for each $k>0$ proceed as follows. Let $0=c_0,c_1,\ldots,c_{kn}=q_{f(k)}$ be rational points forming a partition of interval  $[0,q_{f(k)}]$ into $kn$ even subintervals. For $i\leqslant kn$, compute $\min_{y\in [0,c_i]}\rho_{q_{f(k)}}(y)$ with precision $2^{-kn}$. If for some $i$ we are able to see that $\min_{y\in [0,c_i]}\rho_{q_{f(k)}}(y)>2^{-k}$ with said precision, pick the rightmost $c_i$ with this property and denote it by $a_n^k$, otherwise let $a_n^k=0$. By construction, $a_n^k$ bounds $B_\rho[q_{f(k)},2^{-k}]$ from below. Similarly, obtain a $b_n^k$ that bounds $B_\rho[q_{f(k)},2^{-k}]$ from above. Continue this process until we find such a $k$ that $b_n^k-a_n^k\leqslant 2^{-n}$; this will eventually happen since the balls $B_\rho[q_{f(k)},2^{-k}]$ converge to $x$. This gives us the $a_n,b_n$ satisfying the properties described above. %, or $b_n^k\leqslant 2^{-n}$, or $1-a_n^k\leqslant 2^{-n}$

\subsection{Proof of Proposition~\ref{prp:2}}
$\mathbf{0'}$-computable metric $\rho^*>_c\rho_R$ will have the form
\begin{equation*}
	\rho^*(x,y)=\lVert \gamma(x)-\gamma(y)\rVert,
\end{equation*}
where $\gamma\colon I\to I^2$ is a polygonal curve defined as follows. Consider the sequence $\abd_0=0,\abd_1=2^{-1},\ldots,\abd_n=1-2^{-n},\ldots$ We diagonalize against the $e$th functional $\Phi_e$ on the interval $[\abd_e,\abd_{e+1}]$ of length $2^{-e-1}$. Suppose that $\abd_e=q_a$. Use $\mathbf{0'}$ to figure out whether the computation $\Phi_e(\bar{a})(e+3)$ ever halts. If it does, let $u=\Phi_e(\bar{a})(e+3)$, then it must hold $\rho_R(q_u,q_a)\leqslant 2^{-e-3}$, otherwise we immediately win, keeping the interval $[\abd_e,\abd_{e+1}]$ undeformed in the metric $\rho^*$. Let $x_e$ be the midpoint of $[\abd_e,\abd_{e+1}]$ and let $y_e=x_e-2^{-e-3},z_e=x_e+2^{-e-3}$. In the spirit of the proof of Theorem~\ref{thm:1}, add to $\gamma$ a deformation $\Gamma_e$ of the subinterval $[y_e,z_e]\subseteq[\abd_e,\abd_{e+1}]$ that makes $x_e$ close to $\abd_e$, so we also win against $\Phi_e$. More precisely, define a piecewise linear map $\Gamma_e\colon[y_e,z_e]\to I^2$ by its action on the following points:
\begin{equation*}
	\Gamma_e(y_e)=(y_e,0),~\Gamma_e(x_e)=(\abd_e,h_e),~\Gamma_e(z_e)=(z_e,0),
\end{equation*}
where $h_e<\min(2^{-e},2^{-\varphi_e(\bar{a})(e+3)})$ (see Fig.~\ref{fig:1}).
\begin{figure}[h!]
	\begin{tikzpicture}[scale=1.5]
		\draw (0,0) node[anchor=north] {$\abd_0$} -- (2,0) node[anchor=north] {$y_0$} -- (0,0.5) node[anchor=east] {$h_0$} -- (3,0) node[anchor=north] {$z_0$} -- (4,0) node[anchor=north] {$\abd_{1}$} -- (5,0) node[anchor=north] {$y_{1}$} -- (4,0.25) node[anchor=east] {$h_{1}$} -- (5.5,0) node[anchor=north] {$z_{1}$} -- (6,0) node[anchor=north] {$\abd_{2}$} -- (6.5,0) node[anchor=south] {$\ldots$} -- (7,0) node[anchor=north] {1};
		\draw[fill] (0,0) circle[radius=0.025] (2,0) circle[radius=0.025] (0,0.5) circle[radius=0.025] (3,0) circle[radius=0.025] (4,0) circle[radius=0.025] (5,0) circle[radius=0.025] (4,0.25) circle[radius=0.025] (5.5,0) circle[radius=0.025] (6,0) circle[radius=0.025] (7,0) circle[radius=0.025];
	\end{tikzpicture}
	\caption{First few steps of the construction.}
	\label{fig:1}
\end{figure}

To see why $\rho_R\leq_c\rho^*$, notice that, since the height $h_e$ of the deformation $\Gamma_e$ is bounded by $2^{-e}$ and at each step $e$ we define $\Gamma_e$ in a uniform way, only scaling the length of the interval $[y_e,z_e]$ and distance to the point $\abd_e$ down by 2, then all the deformations $\Gamma_e$ actually share the same computable modulus of continuity $m$. Thus, $m$ is also a modulus of continiuty of the whole curve $\gamma$. Then one can effectively translate any $\rho_R$-name $f$ into a $\rho^*$-name $g$ for the same point by letting $g=f\circ m$, which means that $\rho_R\leq_c\rho^*$.


\begin{thebibliography}{99}
	\bibitem{K21a} R. Kornev, A semilattice of degrees of computable metrics, Sib. Math. J., 62 (2021), 5, 822--841
	\bibitem{KW85} Ch. Kreitz, K. Weihrauch, Theory of representations, Theoret. Comput. Sci., 38 (1985), 35--53
	\bibitem{W00} K.~Weihrauch, Computable analysis. An introduction (Texts Theoret. Comput. Sci. EATCS Ser.), Springer, Berlin, 2000. MR1795407
  \bibitem{K21} R. Kornev, Computable metrics above the standard real metric, Sib. Electron. Math. Rep., 18 (2021), 1, 377--392
  \bibitem{D12} R. Dillhage, Computable functional analysis. Compact operators on computable Banach spaces and computable best approximation, PhD Thesis, Fak. Math. Inform., FernUniversit\"at Hagen, 2012
\end{thebibliography}
\end{document}
