monthyeardate[],

# Generalized fusible numbers and their ordinals

Alexander I. Bufetov  CNRS, Aix-Marseille Université, Centrale Marseille,
Institut de Mathématiques de Marseille, UMR7373, 39 Rue F. Joliot Curie 13453,
Marseille, France;
Steklov Mathematical Institute of RAS, Moscow, Russia;
Institute for Information Transmission Problems, Moscow, Russia.
<EMAIL_ADDRESS><EMAIL_ADDRESS>,  Gabriel Nivasch  Ariel
University, Ariel, Israel<EMAIL_ADDRESS>and  Fedor Pakhomov  Ghent
University, Ghent, Belgium;
Steklov Mathematical Institute of RAS, Moscow, Russia.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract.

Erickson defined the _fusible numbers_ as a set $\mathcal{F}$ of reals
generated by repeated application of the function $\frac{x+y+1}{2}$. Erickson,
Nivasch, and Xu showed that $\mathcal{F}$ is well ordered, with order type
$\varepsilon_{0}$. They also investigated a recursively defined function
$M\colon\mathbb{R}\to\mathbb{R}$. They showed that the set of points of
discontinuity of $M$ is a subset of $\mathcal{F}$ of order type
$\varepsilon_{0}$. They also showed that, although $M$ is a total function on
$\mathbb{R}$, the fact that the restriction of $M$ to $\mathbb{Q}$ is total is
not provable in first-order Peano arithmetic $\mathsf{PA}$.

In this paper we explore the problem (raised by Friedman) of whether similar
approaches can yield well-ordered sets $\mathcal{F}$ of larger order types. As
Friedman pointed out, Kruskal’s tree theorem yields an upper bound of the
small Veblen ordinal for the order type of any set generated in a similar way
by repeated application of a monotone function
$g:\mathbb{R}^{n}\to\mathbb{R}$.

The most straightforward generalization of $\frac{x+y+1}{2}$ to an $n$-ary
function is the function $\frac{x_{1}+\ldots+x_{n}+1}{n}$. We show that this
function generates a set $\mathcal{F}_{n}$ whose order type is just
$\varphi_{n-1}(0)$. For this, we develop recursively defined functions
$M_{n}\colon\mathbb{R}\to\mathbb{R}$ naturally generalizing the function $M$.

Furthermore, we prove that for any _linear_ function
$g:\mathbb{R}^{n}\to\mathbb{R}$, the order type of the resulting $\mathcal{F}$
is at most $\varphi_{n-1}(0)$.

Finally, we show that there do exist continuous functions
$g:\mathbb{R}^{n}\to\mathbb{R}$ for which the order types of the resulting
sets $\mathcal{F}$ approach the small Veblen ordinal.

##  1\. Introduction

Jeff Erickson [Eri] defined the set $\mathcal{F}\subset\mathbb{R}$ of _fusible
numbers_ the following way: Let $g:\mathbb{R}^{2}\to\mathbb{R}$ be given by
$g(x,y)=(x+y+1)/2$. Then let $\mathcal{F}\subset\mathbb{R}$ be the inclusion-
least set that satisfies $0\in\mathcal{F}$ and $g(x,y)\in\mathcal{F}$ whenever
$x,y\in\mathcal{F}$ and $g(x,y)>\max{\\{x,y\\}}$. In other words,
$\mathcal{F}$ is constructing iteratively by initially inserting $0$ into
$\mathcal{F}$, and inserting $g(x,y)$ into $\mathcal{F}$ whenever $x$ and $y$
are previously constructed elements smaller than $g(x,y)$. Erickson claimed in
presentation [Eri] that $\mathcal{F}$ is well-ordered with order type
$\varepsilon_{0}$. Although, as pointed by Junyan Xu [Xu12], Erickson’s sketch
was faulty, the claim itself is correct: The fact that $\mathcal{F}$ is a
well-order of type $\geq\varepsilon_{0}$ was proved by Xu [Xu12], and the fact
that the order type of $\mathcal{F}$ is exactly $\varepsilon_{0}$ was proved
by Erickson, Nivasch, and Xu [ENX22].

Also, the following recursive algorithm defining a function
$M\colon\mathbb{R}\to\mathbb{R}$ goes back to Erickson’s presentation [Eri]:

$M(x)=\begin{cases}-x,&\text{if $x<0$}\\\
\frac{M(x-M(x-1))}{2},&\text{otherwise.}\end{cases}$

The function $M$ was further researched in [Xu12, ENX22]. It has been
established that $M$ terminates on all real inputs, and that the set
$\mathcal{F}^{\prime}=\\{x+M(x)\mid x\in\mathbb{R}\\}$ coincides with the set
of all points of discontinuity of $M$ and is a subset of $\mathcal{F}$ with
order type $\varepsilon_{0}$. Finally, in [ENX22] it was established that
although $M$ is a total function on $\mathbb{R}$, its restriction to
$\mathbb{Q}$ is a total computable function whose totality cannot be proved in
the first-order Peano arithmetic $\mathsf{PA}$.

Friedman [Fri20] then pointed out the following: Let
$G=\\{g_{1},\ldots,g_{k}\\}$ be any finite set of monotone functions of the
form $g_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}$ (meaning
$g(x_{1},\ldots,x_{n_{i}})\leq g(y_{1},\ldots,y_{n_{i}})$ whenever $x_{j}\leq
y_{j}$ for every $1\leq j\leq n_{i}$), and let $P\subset\mathbb{R}$ be any
finite initial set. Let $\mathcal{F}=\mathcal{F}(G,P)\subset\mathbb{R}$ be the
inclusion-least set that satisfies $P\subseteq\mathcal{F}$ and
$g_{i}(x_{1},\ldots,x_{n_{i}})\in\mathcal{F}$ whenever
$x_{1},\ldots,x_{n_{i}}\in\mathcal{F}$ with
$g_{i}(x_{1},\ldots,x_{n_{i}})>\max{\\{x_{1},\ldots,x_{n_{i}}\\}}$. Then
Kruskal’s tree theorem [Kru60] implies that $\mathcal{F}$ is well ordered.
Hence, the order type of $\mathcal{F}$ can be upper-bounded using known bounds
on the order types of linearizations of certain well partial orders of trees
[RW93, Sch79, Sch20]. For example, if $G=\\{g\\}$ has a single function, and
$g$ is $n$-ary, $n\geq 3$, then the order type of the resulting set
$\mathcal{F}$ is at most
$\varphi(1,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize{$n$ times}}})$,
where $\varphi$ is the $(n+1)$-ary Veblen function. The limit of
$\varphi(1,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize{$n$ times}}})$
as $n\to\infty$ is known as the _small Veblen ordinal_. Hence, the question
arises whether there exist natural functions $g$ for which the resulting sets
$\mathcal{F}(\\{g\\},\\{0\\})$ have order types approaching the small Veblen
ordinal. There is one particularly well-known ordinal
$\Gamma_{0}=\varphi(1,0,0)$ that lies between $\varepsilon_{0}$ and the small
Veblen ordinal (it is also called Feferman-Schütte ordinal and is known to be
the proof theoretic ordinal of the system $\mathrm{ATR}_{0}$ of second-order
arithmetic [FMS82]), so in particular it would be interesting to find a
natural function $g$ on reals giving rise to this ordinal.

Perhaps the most straightforward generalization of the function
$g_{2}(x,y)=(x+y+1)/2$ are the functions
$g_{n}(x_{1},\ldots,x_{n})=(x_{1}+\cdots+x_{n}+1)/n$. We note that the
function $g_{2}$ and set
$\mathcal{F}=\mathcal{F}_{2}=\mathcal{F}(\\{g_{2}\\},\\{0\\})$ has a natural
motivation in terms of fuses that goes back to Erickson [Eri]. If $x,y$,
$|x-y|<1$ are moments in time measured in minutes, and we are given a fuse
that burns off completely in exactly one minute if ignited from one end, then
$g_{2}(x,y)$ is the moment of time when the fuse burns off if it is ignited
from one end at moment $x$ and from the other end at moment $y$. Then
$\mathcal{F}_{2}$ is the set of time durations that could be measured by a
procedure involving only ignition of such fuses. This motivation for $g_{2}$
has a natural analogue for the case of other functions $g_{n}$. Suppose we
have a finite collection of water tanks, where each water tank has $n$
faucets. Each faucet, on its own, can empty the water tank in $1$ hour. A
faucet can only be opened at time $0$ or at the moment another tank has become
completely empty. We are interested in the set of times $t$ for which there is
a way to make a tank empty precisely at time $t$ according to these rules.
Since a tank whose faucets are opened at times $x_{1},\ldots,x_{k}$ becomes
empty at time $(x_{1}+\cdots x_{k}+1)/k$, the corresponding set is
$\mathcal{F}_{\leq n}=\mathcal{F}(\\{g_{1},\ldots,g_{n}\\},\\{0\\})$. If we
require that all of a tank’s faucets must be opened before the tank empties,
then the set we obtain is $\mathcal{F}_{n}=\mathcal{F}(\\{g_{n}\\},\\{0\\})$.
Thus we have natural questions to determine the order types of these sets
$\mathcal{F}_{n}$ and $\mathcal{F}_{\leq n}$. We call the elements of
$\mathcal{F}_{n}$ _$n$ -fusible numbers_.

###  1.1. Our results

In this paper we prove that the order type of the above-mentioned sets
$\mathcal{F}_{n}$ and $\mathcal{F}_{\leq n}$ is $\varphi_{n-1}(0)$. The lower
bound is achieved by considering variants of the algorithm $M$:

######  Theorem 1.1.

Let $n\geq 2$ be fixed, and consider the algorithm $M_{n}$ given by:

$M_{n}(x)=\begin{cases}-x,&\text{if $x<0$};\\\
\underbrace{M_{n}(x-M_{n}(x-M_{n}(\cdots M_{n}(x-1)\cdots)))}_{\text{$n$
instances of $M_{n}$}}/n,&\text{otherwise.}\end{cases}$

Then $M_{n}$ terminates on all real inputs. Furthermore,
$\mathcal{F}^{\prime}_{n}=\\{x+M_{n}(x)\mid x\in\mathbb{R}\\}$ is a subset of
$\mathcal{F}_{n}$ with order type $\varphi_{n-1}(0)$.

We prove that $\varphi_{n-1}(0)$ is not only a lower bound for the order type
of $\mathcal{F}_{n}$, but also an upper bound. Furthermore $\varphi_{n-1}(0)$
is an upper bound on the order type of any set generated by one linear $n$-ary
function.

######  Theorem 1.2.

Let $g:\mathbb{R}^{n}\to\mathbb{R}$ be a monotone linear function, and let
$P\subset\mathbb{R}$ be finite. Then the order type of
$\mathcal{F}(\\{g\\},P)$ is at most $\varphi_{n-1}(0)$.

This upper bound is somewhat disappointing, since it was reasonable to expect
to get order types approaching the small Veblen ordinal.

We prove that as long as we consider arbitrary continuous functions, we get
the optimal ordinals prescribed by the bounds for Kruskal tree theorem (for
the bounds see [Sch79, Sch20]):

######  Theorem 1.3.

For each $n\geq 3$ there exists a continuous monotone function
$g:\mathbb{R}^{n}\to\mathbb{R}$ such that
$\mathcal{F}=\mathcal{F}(\\{g\\},\\{0\\})$ has order type
$\varphi(1,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize{$n$ times}}})$.

The function $g$ of Theorem 1.3, however, is quite artificial, since is built
‘‘backwards’’. Namely we first build a certain monotone bijection on ordinals
$\bar{\varphi}^{\star}\colon\Lambda^{n}\to\Lambda\setminus\\{0\\}$, where
$\Lambda=\varphi(1,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize{$n$
times}}})$. Then we embed $\Lambda$ into the reals, and finally we find a
continuous $g$ whose restriction to the image of $\Lambda$ agrees with
$\bar{\varphi}^{\star}$.

Finally, we make some progress on the computational problem of deciding
whether a given $z\in\mathbb{R}$ belongs to $\mathcal{F}(G,P)$ or not:

######  Theorem 1.4.

Let $g:\mathbb{R}^{n}\to\mathbb{R}$ be a monotone linear function, let $P$ be
a finite set, and let $\mathcal{F}=\mathcal{F}(\\{g\\},P)$. Then there exists
an algorithm deciding whether a given $x\in\mathbb{R}$ belongs to the closure
$\overline{\mathcal{F}}$ or not.

The question of whether there exists an algorithm that decides whether
$x\in\mathcal{F}$ or not is still open.

This paper is organized as follows: Section 2 introduces notation and presents
some basic properties of the sets $\mathcal{F}$. Section 3 gives some
background on ordinals below the small Veblen ordinal. Section 4 gives
background on well partial orders. Sections 5, 6, 7, 9 contain the proof of
Theorems 1.1, 1.2, 1.3, 1.4 respectively. Section 8 contains a result needed
for Section 9.

##  2\. Notation and basic properties

Throughout this paper, given a set $G$ of monotone functions
$g:\mathbb{R}^{k_{g}}\to\mathbb{R}$ and a set $P\subseteq\mathbb{R}$, we
denote as $\mathcal{F}(G,P)=\mathcal{F}$ the inclusion-least set such that
$P\subseteq\mathcal{F}(G,P)$ and for any $g\in G$,
$x_{1},\ldots,x_{k_{g}}\in\mathcal{F}$ we have

$g(x_{1},\ldots,x_{k_{g}})>\max\limits_{1\leq i\leq k_{g}}x_{i}$ $\Rightarrow$
$g(x_{1},\ldots,x_{k_{g}})\in\mathcal{F}$.

In other words $\mathcal{F}(G,P)$ is the set of values of all closed terms $t$
built from constants from $P$ and functions from $G$, such that for any
subterm $g(u_{1},\ldots,u_{k_{g}})$ of $t$, the value of
$g(u_{1},\ldots,u_{k_{g}})$ is greater than the values of
$u_{1},\ldots,u_{k_{g}}$. We call such terms _monotone_ terms.

For the specific functions $g_{n}:\mathbb{R}^{n}\to\mathbb{R}$ given by
$g_{n}(x_{1},\ldots,x_{n})=(x_{1}+\cdots+x_{n}+1)/n$, we let
$\mathcal{F}_{n}=\mathcal{F}(\\{g_{n}\\},\\{0\\})$ and $\mathcal{F}_{\leq
n}=\mathcal{F}(\\{g_{1},\ldots,g_{n}\\},\\{0\\})$.

We are primarily interested in cases where $G$ is finite. However, in our
arguments we will also have to consider cases in which $G$ is infinite.

Friedman noted that the following proposition can be proved using Kruskal’s
theorem.

######  Proposition 2.1.

Suppose $G$ is a finite set of functions and $P$ is a well-ordered set of
constants. Then $\mathcal{F}(G,P)$ is well-ordered.

Below is a more direct proof of Proposition 2.1 that uses only the infinite
Ramsey theorem.

###### Proof.

We split the set $\mathcal{F}(G,P)$ into the well-founded part $W$ and the
ill-founded part $I$: $a\in\mathcal{F}(G,P)$ is in $I$ if there is an infinite
descending sequence starting from $a$, otherwise it is in $W$. For a
contradiction assume that $I$ is not empty.

Consider $\ell=\inf I$; note that it exists since any $a\in\mathcal{F}(G,P)$
is bounded from below by $\inf P$. Clearly
$I=\mathcal{F}(G,P)\cap(\ell,+\infty)$ and
$W=\mathcal{F}(G,P)\cap(-\infty,\ell]$. For each $g\in G$, let $I_{g}\subseteq
I$ be the set of all $a\in I$ that are of the form $g(\vec{p})$, $\vec{p}\in
W^{k}$, where $k$ is the arity of $g$. For any $a\in I$ there is a monotone
term $t$ whose value is $a$, and there is a shortest subterm $t^{\prime}$ of
$t$ such that its value $a^{\prime}$ lies in $I$. We observe that
$a^{\prime}\leq a$ and either $a^{\prime}\in P$ or $a^{\prime}\in I_{g}$ for
some $g\in G$. Thus $\inf(\bigcup\limits_{g\in G}I_{g}\cup(P\cap I)))=\ell$.
Since $P$ is well-founded, either $P\cap I$ is empty or $\inf(P\cap I)>\ell$.
Hence for some $g\in G$ we have $\inf I_{g}=\ell$. Further we fix $g$ with
this property and denote its arity as $k$.

We consider a strictly decreasing sequence $x_{1}>x_{2}>\ldots$ of elements of
$I_{g}$ converging to $\ell$. For all $n$ we choose $y_{n,1},\ldots,y_{n,k}\in
W$ such that $g(y_{n,1},\ldots,y_{n,k})=x_{n}$. Observe that by the infinite
Ramsey Theorem there exists an infinite set $A\subseteq\mathbb{N}$ such that
for each $1\leq i\leq n$ the sequence $\langle y_{n,i}\mid n\in A\rangle$ is
either increasing, or constant, or decreasing. Indeed, we consider the
coloring of increasing pairs of naturals
$h\colon[\mathbb{N}]^{2}\to\\{<,=,>\\}^{k}$, where for each $n<m$ the value
$h((n,m))$ is the tuple $(c_{1},\ldots,c_{k})$, where each $c_{i}$ is the
result of comparing $y_{n,i}$ with $y_{n,j}$. Clearly, any infinite
monochromatic set for this coloring indeed can serve as the desired $A$.

However none of the sequences $\langle y_{n,i}\mid n\in A\rangle$ can be
decreasing, since this would contradict the assumption that all $y_{n,i}\in
W$. Hence by the monotonicity of $g$, the sequence $\langle
g(y_{n,1},\ldots,y_{n,k})\mid n\in A\rangle$ is non-decreasing. But it is a
subsequence of our decreasing sequence, contradiction.∎

##  3\. Background on ordinals

###  3.1. Ordinals below $\varphi_{\omega}(0)$

A function $f$ from ordinals to ordinals is called _normal_ if it is strictly
monotone (meaning $\alpha<\beta$ implies $f(\alpha)<f(\beta)$) and continuous
(meaning for every limit ordinal $\lambda$ we have
$f(\alpha)=\lim_{\alpha<\lambda}f(\alpha)$). Given a normal function $f$ the
_derivative_ $f^{\prime}$ of $f$ is the normal function enumerating all the
fixed points of $f$ in the increasing order. Alternatively $f^{\prime}$ can be
defined by transfinite recursion as

  1. (1)

$f^{\prime}(0)=\sup_{k\in\mathbb{N}}f^{k}(0)$;

  2. (2)

$f^{\prime}(\alpha+1)=\sup_{k\in\mathbb{N}}f^{k}(f^{\prime}(\alpha)+1)$;

  3. (3)

$f^{\prime}(\lambda)=\sup_{\alpha<\lambda}f^{\prime}(\alpha)$, for limit
ordinals $\lambda$.

The _Veblen functions_ $\varphi_{n}$, $n\in\mathbb{N}$ are a sequence of
normal functions defined by starting with
$\varphi_{0}(\alpha)=\omega^{\alpha}$, and for each $n\in\mathbb{N}$, letting
$\varphi_{n+1}=\varphi_{n}^{\prime}$. These functions can be defined more
succintly by letting $\varphi_{n}(\alpha)$ be the least ordinal $\beta$ of the
form $\omega^{\gamma}$ such that $\beta>\varphi_{n}(\alpha^{\prime})$ for all
$\alpha^{\prime}<\alpha$, and such that $\beta>\varphi_{m}(\alpha^{\prime})$
for all $m<n$ and $\alpha^{\prime}<\beta$.

Denote $\varphi_{\omega}(0)=\lim_{n\in\mathbb{N}}\varphi_{n}(0)$. Then
$\varphi_{\omega}(0)$ is the smallest ordinal that cannot be constructed by
starting from $0$ and repeatedly applying ordinal addition and the functions
$\varphi_{n}$, $n\in\mathbb{N}$ on previously constructed ordinals. The
ordinals below $\varphi_{\omega}(0)$ are used in Sections 5 and 6 of this
paper.

###  3.2. The $n$-ary Veblen functions

Fix $n\geq 3$. The $n$-ary Veblen function
$\varphi\colon\mathsf{On}^{n}\to\mathsf{On}$ is a generalization of the Veblen
function described above, with $\varphi_{m}(\alpha)$ now denoted
$\varphi(0,\ldots,0,m,\alpha)$. The $n$-ary function $\varphi$ is defined by
ordinal induction, by letting the function
$\beta\mapsto\varphi(\alpha_{1},\ldots,\alpha_{k},\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize$n-k-1$}},\beta)$,
where $\alpha_{k}>0$, enumerate the common fixed points of the functions

$\bigl{\\{}\gamma\mapsto\varphi(\alpha_{1},\ldots,\alpha_{k-1},\alpha^{\prime}_{k},\gamma,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize$n-k-1$}}):\alpha^{\prime}_{k}<\alpha_{k}\bigr{\\}}.$

The following proposition can serve as an equivalent definition of $\varphi$:

######  Proposition 3.1.

$\varphi(\alpha_{1},\ldots,\alpha_{n})$ is the least ordinal $\beta$ of the
form $\omega^{\gamma}$ such that

$\varphi(\alpha_{1},\ldots,\alpha_{k-1},\alpha^{\prime}_{k},\alpha^{\prime}_{k+1},\ldots,\alpha^{\prime}_{n})<\beta,$

for all $1\leq k\leq n$, $\alpha^{\prime}_{k}<\alpha_{k}$, and
$\alpha^{\prime}_{k+1},\ldots,\alpha^{\prime}_{n}<\beta$.

In particular, the Feferman–Schütte ordinal is
$\Gamma_{0}=\varphi(0,\ldots,0,1,0,0)=\varphi(1,0,0)$ (since leading zeros can
be ignored). The limit of
$\varphi(1,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize$n$}})$ as
$n\to\infty$ is known as the _small Veblen ordinal_ , and is the smallest
ordinal that cannot be constructed by starting from $0$ and repeatedly
applying Veblen functions of any finite arity to the previously constructed
ordinals.

###  3.3. Removing limit elements

We will use several times the following simple observation:

######  Proposition 3.2.

Let $S$ be a nonempty well-ordered set, and let $S^{\prime}$ be obtained from
$S$ by removing the elements at limit positions. Then
$\mathsf{ot}(S)=\mathsf{ot}(S^{\prime})$ if $\mathsf{ot}(S)$ is a limit
ordinal; otherwise $\mathsf{ot}(S)=\mathsf{ot}(S^{\prime})+1$.

##  4\. Well partial orders

A partial order $X=(D,\preceq)$ is said to be a _well partial order_ (wpo) if
for every infinite sequence $a_{0},a_{1},a_{2},\ldots$ of elements of $X$
there are naturals $i<j$ such that $a_{i}\preceq a_{j}$. A _linearization_ of
a partial order $\preceq$ is a linear order $\leq$ on the same domain $D$ such
that $a\preceq b$ implies $a\leq b$ for all $a,b\in X$. A partial order is a
wpo iff all its linearizations are well-orders [Hig52]. For a wpo set $X$, the
expression $o(X)$ denotes the supremum of the order types of all the
linearizations of $X$. A classical theorem of de Jongh and Parikh [dJP77]
states that for every well-partially ordered set $X$ there exists a
linearization $\leq$ whose order type is precisely $o(X)$.

There are a few standard constructions of new wpo’s from given ones, which we
will use in this paper. For wpo’s $X$ and $Y$, both their disjoint union
$X\sqcup Y$ and their product $X\times Y$ are wpo’s.

Recall that $\oplus$ is the _natural addition_ of ordinals and $\otimes$ is
the _natural product_ of ordinals, which are defined as follows: Given
ordinals $\alpha,\beta$ with Cantor normal forms

$\displaystyle\alpha$
$\displaystyle=\omega^{\alpha_{1}}+\ldots+\omega^{\alpha_{n}},\qquad\text{
with $\alpha_{1}\geq\ldots\geq\alpha_{n}$},$ $\displaystyle\beta$
$\displaystyle=\omega^{\beta_{1}}+\ldots+\omega^{\beta_{m}},\qquad\text{ with
$\beta_{1}\geq\ldots\geq\beta_{m}$};$

their natural sum $\alpha\oplus\beta$ is the ordinal $\gamma$ with the Cantor
normal form $\omega^{\gamma_{1}}+\ldots+\omega^{\gamma_{n+m}}$, where
$\gamma_{1},\ldots,\gamma_{n+m}$ are
$\alpha_{1},\ldots,\alpha_{n},\beta_{1},\ldots,\beta_{m}$ sorted in
nonincreasing order. The natural product of $\alpha,\beta$ is given by

$\alpha\otimes\beta=\mathop{\bigoplus\limits_{1\leq i\leq n}}\limits_{1\leq
j\leq m}\omega^{\alpha_{i}\oplus\beta_{j}}.$

De Jongh and Parikh [dJP77] proved that $o(X\sqcup Y)=o(X)\oplus o(Y)$ and
$o(X\times Y)=o(X)\otimes o(Y)$.

For a partially ordered set $X$, denote by $X^{\star}$ the set of all finite
sequences of elements of $X$, partially ordered by
$(a_{1},...,a_{n})\preceq(b_{1},\ldots,b_{m})$ if and only if there is a
strictly monotone function $f\colon\\{1,\ldots,n\\}\to\\{1,\ldots,m\\}$ such
that $a_{i}\preceq b_{f(i)}$, for all $1\leq i\leq n$. Higman’s Lemma [Hig52]
states that if $X$ is wpo, then $X^{\star}$ is wpo as well. Schmidt [Sch79]
(see also [Sch20]) proved that $o(W^{\star})\leq\omega^{\omega^{o(W)+1}}$.

There is a variant of Kruskal’s tree theorem that is relevant for this paper,
where instead of trees the order is defined on terms. Suppose we are given
sets $W_{0},\ldots,W_{n}$ of function symbols, where the functions symbols in
each $W_{i}$ are $i$-ary, and where each $W_{i}$ is endowed with a partial
order $\preceq_{W_{i}}$. Let us define the partial order
$T(W_{0},\ldots,W_{n})$. The domain of the order is the least set of terms $K$
such that

$t_{1},\ldots,t_{k}\in K$ and $a\in W_{k}$, where $0\leq k\leq n$
$\Rightarrow$ $a(t_{1},\ldots,t_{k})\in K$.

The comparison relation $\preceq_{T}$ is defined recursively as follows: Let
$x,y\in K$ be two terms, where $x=a(t_{1},\ldots,t_{k})$, $a\in W_{k}$,
$t_{1},\ldots,t_{k}\in K$, and $y=b(u_{1},\ldots,u_{\ell})$, $b\in W_{\ell}$,
$u_{1},\ldots,u_{\ell}\in K$. Then we let $x\preceq_{K}y$ if
$x\preceq_{K}u_{i}$ for some $1\leq i\leq\ell$, or $k=\ell$ and
$a\preceq_{W_{k}}b$ and $t_{i}\preceq_{K}u_{i}$ for every $1\leq i\leq k$.

The variant of Kruskal’s theorem that we need states that for any wpo’s
$W_{0},\ldots,\allowbreak W_{n}$ the order $T(W_{0},\ldots,W_{n})$ is a wpo.
Schmidt [Sch79, Sch20] extensively studied the bounds for
$o(T(W_{0},\ldots,W_{n}))$. She mostly done it in terms of labeled trees, but
also she discusses the term order [Sch20, Section 4].

This version of Kruskal theorem allows an easy alternative proof of
Proposition 2.1; we note that this observation is already contained in an
e-mail by Friedman [Fri20]. Consider finite set of monotone functions on reals
$G$ and a well-ordered set of constants $P$. We split $G$ into sets
$G_{0},\ldots,G_{n}$, where each $G_{i}$ consists only of functions of the
arity $i$. We endow $G_{0},\ldots,G_{n}$ with the discrete orders and $P$ with
the standard orders on reals. Clearly, the set of monotone terms for the pair
$G,P$ is a subset of $T(P\sqcup G_{0},G_{1},\ldots,G_{n})$ and for any
monotone terms $t,u$ if $t\preceq_{T}u$, then the value of $t$ is smaller than
the value of $u$. Thus $\mathcal{F}(G,P)$ is a lineariazation of a suborder of
$T(P\sqcup G_{0},G_{1},\ldots,G_{n})$ and thus is well-ordered. The
construction above also shows that $\mathsf{ot}(\mathcal{F}(G,P))\leq
o(T(P\sqcup G_{0},G_{1},\ldots,G_{n}))$.

##  5\. Monotone functions on reals that lead to ordinals below
$\varphi_{\omega}(0)$

In this section we prove Theorem 1.2.

For a monotone function $g\colon\mathbb{R}\to\mathbb{R}$ we denote as
$A(g)\subseteq\mathbb{R}\cup\\{+\infty\\}$ the set of limit points

$\\{\lim\limits_{n\to\infty}g^{n}(x)\mid x\in\mathbb{R}\text{ and }g(x)>x\\}.$

For a family of monotone functions $\langle
h_{\vec{p}}\colon\mathbb{R}\to\mathbb{R}\mid\vec{p}\in\mathbb{R}^{n}\rangle$
and a set $P\subseteq\mathbb{R}$ we put

$A(h;P)=\bigcup\limits_{\vec{p}\in P^{n}}A(h_{\vec{p}}).$

For a monotone function $g\colon\mathbb{R}^{n}\to\mathbb{R}$,
$u\subseteq\\{1,\ldots,n\\}$, and
$\vec{p}=(p_{1},\ldots,p_{n-|u|})\in\mathbb{R}^{n-|u|}$ we denote as
$g_{u,\vec{p}}\colon\mathbb{R}^{|u|}\to\mathbb{R}$ the result of substitution
of parameters $\vec{p}$ instead of the arguments with indices from
$\\{1,\ldots,n\\}\setminus u$. Formally the function $g_{u,\vec{p}}$ is the
function that maps $(x_{1},\ldots,x_{|u|})$ to $g(y_{1},\ldots,y_{n})$, where
for each $i$-th element $j$ of $u$ the number $y_{j}$ is equal to $x_{i}$ and
for each $i$-th element $j$ of $\\{1,\ldots,n\\}\setminus u$ the number
$y_{j}$ is equal to $p_{i}$. We denote as
$\dot{g}_{u,\vec{p}}\colon\mathbb{R}\to\mathbb{R}$ the function

$\dot{g}_{u,\vec{p}}(x)=g_{u,\vec{p}}(\underbrace{x,\ldots,x}\limits_{\mbox{\scriptsize$|u|$
times}}).$

Hence, $A(\dot{g}_{u},P)$ is the set of limit points of the functions
$\dot{g}_{u,\vec{p}}$ for $\vec{p}\in P^{n-|u|}$.

We call a monotone function $g\colon\mathbb{R}^{n}\to\mathbb{R}$ _tame_ if
there is $k$ such that for any $u\subsetneq\\{1,\ldots,n\\}$, any well-ordered
set $P\subseteq\mathbb{R}$, and any well-ordered subset $B\subseteq
A(\dot{g}_{u},P)$, we have

$\mathsf{ot}(B)<\varphi_{0}^{k}({\mathsf{ot}(P)+1}).$

As we will show below, linear functions are tame.

######  Theorem 5.1.

Suppose $g\colon\mathbb{R}^{n}\to\mathbb{R}$, $n\geq 2$ is a monotone tame
function. Then
$\mathsf{ot}(\mathcal{F}(\\{g\\},\\{0\\}))\leq\varphi_{n-1}(0)$.

###### Proof.

Let the function $g$ be fixed. For $m\leq n$ and $P\subseteq\mathbb{R}$ we
denote as $G_{m}(P)$ the set of multi-variate monotone functions on
$\mathbb{R}$ consisting of all functions $g_{u,\vec{p}}$, where
$u\subseteq\\{1,\ldots,n\\}$ is of cardinality $m$ and $\vec{p}\in P^{n-|u|}$.
We put $G_{\leq m}(P)=\bigcup\limits_{m^{\prime}\leq m}G_{m^{\prime}}(P)$, and
$\mathcal{F}_{\leq m}(P)=\mathcal{F}(G_{\leq m}(P),P)$. Hence,
$\mathcal{F}_{\leq m}(P)\subseteq\mathcal{F}(\\{g\\},P)$ is the set of reals
that can be constructed by starting from $P$ and repeatedly applying $g$ on at
least $n-m$ elements of $P$ and at most $m$ other previously constructed
elements.

As was noted in Section 4, it follows from Kruskal’s theorem that for any
$0\leq m\leq n$ and any well-ordered set $P$, the set $\mathcal{F}_{\leq
m}(P)$ is well-ordered.

For $1\leq m<n$ we will prove by induction on $m$ that there is a natural
number $k_{m}$ such that for any well-ordered $P$ we have

(1) $\mathsf{ot}(\mathcal{F}_{\leq
m}(P))\leq\varphi_{m-1}^{k_{m}}(\mathsf{ot}(P)+1).$

First consider the case of $m=1$. Consider the wpo $W=\bigsqcup\limits_{1\leq
i\leq n}(P,<)^{n-1}$. We put in correspondence to each unary function
$h=g_{\\{i\\},\vec{p}}\in G_{1}(P)$ the element $e(h)$ of $W$ that is the
tuple $\vec{p}$ from the $i$-th copy of $(P,<)^{n-1}$. Observe that if
$e(h_{1})\preceq_{W}e(h_{2})$ then $h_{1}$ is pointwise less than or equal to
$h_{2}$. Now considering the definition of $\mathcal{F}_{\leq
1}(P)=\mathcal{F}(G_{1}(P),P\cup G_{0}(P))$ as the set of values of monotone
terms, we observe that it is isomorphic to a linearization of a subset of
$T((G_{0}(P),<)\sqcup(P,<),W)$. Hence $\mathsf{ot}(\mathcal{F}_{\leq
1}(P))\leq o(T((G_{0}(P),<)\sqcup(P,<),W))$. Notice that in general
$T(W_{0},W_{1})$ is isomorphic to $W_{1}^{\star}\times W_{0}$. Thus

$\mathsf{ot}(\mathcal{F}_{\leq 1}(P))\leq o(((G_{0}(P),<)\sqcup(P,<))\times
W^{\star}).$

Now let us apply results about upper bounds for the order types of
linearizations of wpo’s. Observe that the set $G_{0}(P)$ is the set of reals
consisting of values of the form $g(\vec{p})$, where $\vec{p}\in P^{n}$. Thus
$(G_{0}(P),<)$ is isomorphic to a linearization of a subset of $(P,<)^{n}$.
Hence

$\mathsf{ot}(G_{0}(P)\sqcup P))\leq
o((P,<)\sqcup(P,<)^{n})<(\mathsf{ot}(P,<)+1)^{\omega}.$

In the same manner it is easy to see that $o(W)<(\mathsf{ot}(P)+1)^{\omega}$.
Notice that

$\displaystyle(\mathsf{ot}(P)+1)^{\omega}$
$\displaystyle\leq(\varphi_{0}(\mathsf{ot}(P)+1))^{\omega}=\varphi_{0}((\mathsf{ot}(P)+1)\omega)\leq\varphi_{0}(\varphi_{0}(\mathsf{ot}(P)+1)\varphi_{0}(1))$
$\displaystyle=\varphi_{0}(\varphi_{0}((\mathsf{ot}(P)+1)+1))\leq\varphi_{0}(\varphi_{0}(\varphi_{0}(\mathsf{ot}(P)+1)))=\varphi_{0}^{3}(\mathsf{ot}(P)+1).$

By the upper bound for Higman’s Lemma we know that

$o(W^{\star})\leq\varphi_{0}^{2}(o(W)+1)<\varphi_{0}^{2}(\varphi_{0}^{3}(\mathsf{ot}(P)+1))=\varphi_{0}^{5}(\mathsf{ot}(P)+1).$

Thus

$\displaystyle\mathsf{ot}(\mathcal{F}_{\leq 1}(P))$ $\displaystyle\leq
o(((G_{0,P},<)\sqcup(P,<))\times W^{\star})\leq$
$\displaystyle\varphi_{0}^{3}(\mathsf{ot}(P)+1)\otimes\varphi_{0}^{5}(\mathsf{ot}(P)+1)$
$\displaystyle=\varphi_{0}(\varphi_{0}^{4}(\mathsf{ot}(P)+1)+\varphi_{0}(\mathsf{ot}(P)+1))\leq\varphi_{0}^{6}(\mathsf{ot}(P)+1).$

Now we assume that $m>1$. Let us consider the set of limit points

$A=\bigcup\limits_{u\in\mathcal{P}^{=m}(\\{1,\ldots,n\\})}A(g_{u},P)$

and its subset

$\displaystyle A^{\prime}=\\{a\in A\mid
a=\lim_{i\to+\infty}\dot{g}^{i}_{u,\vec{p}}(b)$ $\displaystyle\text{, for some
}b\in\mathcal{F}_{\leq m}(P)\text{, }u\in\mathcal{P}^{=m}(\\{1,\ldots,n\\}),$
$\displaystyle\text{and }\vec{p}\in P^{n-m}\text{ such that
}\dot{g}_{u,\vec{p}}(b)>\max(\vec{p},b)\\}.$

Since
$\bigsqcup\limits_{u\in\mathcal{P}^{=m}(\\{1,\ldots,n\\}}\mathcal{F}_{\leq
m}(P)\times P^{n-m}$ is a wpo, the set $A^{\prime}$ is well-ordered. Using the
tameness of $g$, we conclude that
$\mathsf{ot}(A^{\prime})<\varphi_{0}^{k}(\mathsf{ot}(P)+1)\binom{n}{m}$, where
$k$ is the tameness constant of $g$. We further consider the set
$A^{\prime\prime}=A^{\prime}\cup\\{\pm\infty\\}$.

Let $\Lambda=\mathsf{ot}(A^{\prime\prime})$ and $\langle
a_{\alpha}\mid\alpha<\Lambda\rangle$ be enumeration of elements of
$A^{\prime\prime}$ in increasing order. Our goal will be to show by
transfinite induction on $\alpha<\Lambda$ that

(2) $\mathsf{ot}(\mathcal{F}_{\leq
m}(P)\cap(-\infty,a_{\alpha}))\leq\varphi_{m-1}(\mathsf{ot}(P)+\alpha+1).$

The case $\alpha=0$ follows since $a_{0}=-\infty$, so suppose $\alpha>0$. We
put $b_{0}=\sup\limits_{\beta<\alpha}a_{\beta}$ and define
$b_{i+1}\in\mathbb{R}\cup\\{+\infty\\}$ recursively as follows:

$\displaystyle b_{i+1}=\min\\{g_{v,\vec{r}}(\vec{d})\mid$ $\displaystyle
v\in\mathcal{P}^{=m}(\\{1,\ldots,n\\}),\;\vec{r}\in P^{n-m},$
$\displaystyle\vec{d}\in(\mathcal{F}_{\leq m}(P)\cap(b_{i},\infty))^{m}\text{,
and }g_{v,\vec{r}}(\vec{d})>\max(\vec{d},\vec{r}).\\}$

Since $b_{i+1}$ is defined as the minimum of a subset of $\mathcal{F}_{\leq
m}(P)$ it could be undefined only if the corresponding set is empty; in this
case we put $b_{i+1}=+\infty$.

We claim that $\lim_{i\to+\infty}b_{i}\geq a_{\alpha}$. If some $b_{i}$ is
equal to $+\infty$, then the claim is trivially true. Hence we assume without
loss of generality that all $b_{i}$ are below $+\infty$. For each $i$ we fix
$v_{i}\in\mathcal{P}^{=n-m}(\\{1,\ldots,n\\})$, $\vec{r}_{i}\in P^{n-m}$, and
$\vec{d}_{i}\in(\mathcal{F}_{\leq m}(P)\cap(b_{i},\infty))^{m}$ such that
$b_{i+1}=g_{v_{i},\vec{r}_{i}}(\vec{d}_{i})$ and $\max(\vec{d}_{i})<b_{i+1}$.
We fix an infinite set of naturals $I_{0}$ such that there is a fixed $v$ such
that $v_{i}=v$, for all $i\in I_{0}$. Since $P^{n-m}$ is a wpo, there is an
infinite set of naturals $I_{1}\subset I_{0}$ such that the sequence
$\langle\vec{r}_{i}\mid i\in I_{1}\rangle$ is either pointwise monotone
increasing or constant.

Let $k=k_{0}<k_{1}<k_{2}<\ldots$ be the sequence enumerating the set $I_{1}$.
By induction on $i$ we prove that
$\dot{g}_{v,\vec{r}_{k}}^{i}(\max(\vec{d}_{k}))\leq b_{k_{i}+1}$. Indeed, the
base of the induction holds since $\max(\vec{d}_{k})<b_{k+1}=b_{k_{0}+1}$ and
the induction step follows since

$\dot{g}_{v,\vec{r}_{k}}^{i+1}(\max(\vec{d}_{k}))\leq\dot{g}_{v,\vec{r}_{k}}(b_{k_{i}+1})\leq\dot{g}_{v,\vec{r}_{k}}(b_{k_{i+1}})\leq\dot{g}_{v,\vec{r}_{k_{i+1}}}(b_{k_{i+1}})\\\
\leq g_{v,\vec{r}_{k_{i+1}}}(\vec{d}_{k_{i+1}})=b_{k_{i+1}+1}.$

Thus
$c=\lim_{i\to\infty}\dot{g}_{v,\vec{r}_{k}}^{i}(\max(\vec{d}_{k}))\leq\lim_{i\to\infty}b_{i}$.
Since $\dot{g}_{v,\vec{r}_{k}}(\max(\vec{d}_{k}))>\max(\vec{d}_{k})$, we have
$c\in A$. Furthermore, since $\max(\vec{d}_{k})\in\mathcal{F}(G_{\leq
m}(P),P)$, we have $c\in A^{\prime}$. Therefore, since $a_{\alpha}$ is the
least element of $(A^{\prime}\cup\\{+\infty\\})\cap[b_{0},+\infty]$ and
$c>b_{0}$, we have $a_{\alpha}\leq c\leq\lim_{i\to\infty}b_{i}$. This
concludes the proof that $\lim_{i\to+\infty}b_{i}\geq a_{\alpha}$.

Let $U_{i}=\mathcal{F}_{\leq m}(P)\cap(-\infty,b_{i})$. Since
$U_{0}=\mathcal{F}_{\leq
m}(P)\cap(-\infty,\sup\limits_{\beta<\alpha}a_{\beta})$, from the transfinite
induction hypothesis (2) it follows that

$\mathsf{ot}(U_{0})=\sup\limits_{\beta<\alpha}\mathsf{ot}(\mathcal{F}_{\leq
m}(P)\cap(-\infty,a_{\beta}))\leq\sup\limits_{\beta<\alpha}\varphi_{m-1}(\mathsf{ot}(P)+\beta+1)\\\
=\varphi_{m-1}(\mathsf{ot}(P)+\alpha).$

From the definition of $b_{i+1}$ it immediately follows that

$U_{i+1}\subseteq\mathcal{F}(G_{\leq m-1}(U_{i}),U_{i}\cup
P)\subseteq\mathcal{F}_{\leq m-1}(U_{i}\cup P).$

Applying the induction assumption (1) for $m-1$, we obtain

$\mathsf{ot}(U_{i+1})\leq\varphi_{m-2}^{k_{m-1}}(\mathsf{ot}(U_{i}\cup
P)+1)\leq\varphi^{k_{m-1}}_{m-2}(\mathsf{ot}(P)\oplus\mathsf{ot}(U_{i})+1).$

It follows by induction on $i$ that
$\mathsf{ot}(U_{i})\leq\varphi_{m-2}^{i(k_{m-1}+1)}(\mathsf{ot}(U_{0}))$.
Therefore,

$\mathsf{ot}(\mathcal{F}_{\leq
m}(P)\cap(\\-\infty,a_{\alpha}))\leq\sup\limits_{i\in\mathbb{N}}\mathsf{ot}(U_{i})\\\
\leq\sup\limits_{i\in\mathbb{N}}\varphi_{m-2}^{i}(\varphi_{m-1}(\mathsf{ot}(P)+\alpha)+1)=\varphi_{m-1}(\mathsf{ot}(P)+\alpha+1),$

concluding the inductive proof of (2).

Now let us use (2) to finish the inductive proof of (1). We simply use (2) for
the case of $a_{\Lambda-1}=+\infty$:

$\mathsf{ot}(\mathcal{F}_{\leq
m}(P))\leq\varphi_{m-1}(\mathsf{ot}(P)+\Lambda)<\varphi_{m-1}(\varphi_{0}^{k+1}(\mathsf{ot}(P)+1))\leq\varphi_{m-1}^{2}(\mathsf{ot}(P)+1).$

Hence we have (1) with $k_{m}=2$.

Finally, let us use (1) to give a bound for $\mathcal{F}(\\{g\\},\\{0\\})$.
Let $a_{0}=0$ and $a_{i+1}=g(a_{i},\ldots,a_{i})$. We prove by induction on
$i$ that for $U_{i}=\mathcal{F}(\\{g\\},\\{0\\})\cap(-\infty,a_{i}]$ we have
$\mathsf{ot}(U_{i})<\varphi_{n-1}(0)$. It is obviously the case for $i=0$. For
the step of induction we observe that $U_{i+1}\subseteq\mathcal{F}_{\leq
n-1}(U_{i})$ which allows us to prove the step of induction using (1) for
$m=n-1$. Thus $\mathcal{F}(\\{g\\},\\{0\\})\leq\varphi_{n-1}(0)$. ∎

######  Lemma 5.2.

For any $\alpha_{1},\ldots,\alpha_{n}\geq 0$ the linear function
$g(x_{1},\ldots,x_{n})=\alpha_{1}x_{1}+\ldots+\alpha_{n}x_{n}+C$ is tame.

###### Proof.

Observe that for any $u\subsetneq\\{1,\ldots,n\\}$ and
$\vec{p}\in\mathbb{R}^{n-|u|}$ the set $A(g_{u,\vec{p}})$ consists of a single
point. We denote this point as $h_{u}(\vec{p})$. Notice that
$h_{u}\colon\mathbb{R}^{n-|u|}\to\mathbb{R}$ is monotone. Consider well-
ordered $P\subseteq\mathbb{R}$. Observe that $A(g_{u};P)$ is isomorphic to a
linearization of a suborder of the wpo $P^{n-|u|}$. Hence

$\displaystyle\mathsf{ot}(A(g_{u};P))$ $\displaystyle\leq$ $\displaystyle
o(P^{n-|u|})$ $\displaystyle\leq$
$\displaystyle\underbrace{\mathsf{ot}(P)\otimes\ldots\otimes\mathsf{ot}(P)}\limits_{\mbox{\footnotesize$n-|u|$-times}}$
$\displaystyle\leq$
$\displaystyle\varphi_{0}(\underbrace{\mathsf{ot}(P)\oplus\ldots\oplus\mathsf{ot}(P)}\limits_{\mbox{\footnotesize$n-|u|$-times}})$
$\displaystyle\leq$ $\displaystyle\varphi_{0}(\mathsf{ot}(P)\omega)$
$\displaystyle\leq$ $\displaystyle\varphi_{0}(\varphi_{0}(\mathsf{ot}(P)+1)).$

∎

Theorem 5.1 and Lemma 5.2 together imply Theorem 1.2.

##  6\. Functions $M_{n}$

In this section we prove Theorem 1.1. Recall that for $n\geq 2$ the function
$M_{n}$ is a partial function given by the following recursive algorithm:

$M_{n}(x)=\begin{cases}-x,&\text{if $x<0$};\\\
\underbrace{M_{n}(x-M_{n}(x-M_{n}(\cdots M_{n}(x-1)\cdots)))}_{\text{$n$
instances of $M_{n}$}}/n,&\text{otherwise.}\end{cases}$

In other words, given $x\geq 0$ algorithm $M_{n}$ lets $t_{0}(x)=1$, then lets
$t_{i}(x)=M_{n}(x-t_{i-1}(x))$ for $i=1,\ldots,n$, and then it outputs
$t_{n}(x)/n$.

######  Remark 6.1.

Although not that much relevant to our paper, there is a question of what
precisely is an algorithm working with arbitrary real numbers. For
definiteness we will assume that our model of computation over reals is
$\Sigma$-definability in the structure $\mathbb{HF}(\mathbb{R},0,1,+,\times)$,
see [MK08, EPS11]. Alternatively, the function $M_{n}$ can be computed over
$\mathbb{Q}$ by a standard Turing machine.

It is not clear a priori that $M_{n}$ terminates for all inputs
$x\in\mathbb{R}$. But clearly, whenever $M_{n}$ terminates on an input $x$,
the value $M_{n}(x)$ that it returns is positive.

For the rest of the section we will assume that $n$ is fixed and we will
denote $M_{n}$ simply as $M$.

######  Lemma 6.2.

Suppose $M(x)$ terminates. Then:

  1. (1)

For $0\leq d<M(x)$, $M(x+d)$ terminates and satisfies $M(x+d)=M(x)-d$.

  2. (2)

If $x\geq 0$,then $t_{i}(x)\geq iM(x)$ for each $0\leq i\leq n$.

###### Proof.

We prove both claims jointly by induction on the depth of the recursive calls.
Suppose $M(x)$ terminates, and suppose the claims hold for all recursive calls
made by $M(x)$.

We start by proving the second claim. We fix $x\geq 0$ and prove that
$t_{i}(x)\geq iM(x)$ by induction on $0\leq i<n$, in decreasing order. The
case $i=n$ is trivial. Hence, suppose $i<n$. By induction assumption
$t_{i+1}(x)\geq(i+1)M(x)$. Since $M(x)>0$, if
$t_{i}(x)\geq\frac{i}{i+1}t_{i+1}(x)$ we are done. Therefore, suppose
$t_{i}(x)<\frac{i}{i+1}t_{i+1}(x)$. By induction assumption for the recursive
calls, we have $M(x-t_{i}(x)+d)=t_{i+1}(x)-d$ for all $0\leq
d<M(x-t_{i}(x))=t_{i+1}(x)$, so in particular we have

$M(x)=M(x-t_{i}(x)+t_{i}(x))=M(x-t_{i}(x))-t_{i}(x)\\\
=t_{i+1}(x)-t_{i}(x)\geq(i+1)M(x)-t_{i}(x),$

which implies that $t_{i}(x)\geq iM(x)$, as desired.

We now prove the first claim. If $x<0$, then the claim immediately follows
from the definition of the function $M$. Suppose $x\geq 0$. We show by
induction on $i$ that $t_{i}(x+d)=t_{i}(x)-id$, for any non-negative $d<M(x)$.
The case $i=0$ is trivial, so let $i\geq 1$. By induction on the recursive
calls, we have $M(x-t_{i-1}(x)+z)=t_{i}(x)-z$ for all $z<t_{i}(x)$. In
particular, since $id<iM(x)\leq t_{i}(x)$, we have

$t_{i}(x+d)=M(x-t_{i-1}(x+d)+d)=M(x-t_{i-1}(x)+id)\\\
=M(x-t_{i-1}(x))-id=t_{i}(x)-id.$

Therefore, for any $0\leq d<M(x)$ we have
$M(x+d)=t_{n}(x+d)/n=(t_{n}(x)-nd)/n=M(x)-d$, as desired. ∎

######  Proposition 6.3.

Algorithm $M$ terminates on all real inputs.

###### Proof.

Let $S\subset\mathbb{R}$ be the set of all inputs on which $M$ does not
terminate, and suppose for a contradiction that $S\neq\emptyset$. Let $x=\inf
S$. Since $M(x-\varepsilon)$ terminates for all $\varepsilon>0$, and since $M$
outputs a positive value whenever it terminates, it follows that
$M(x-t_{i}(x))$ terminates for all $i\leq n$. Hence, $M(x)$ itself terminates.
But then Lemma 6.2 implies that $M(x+d)$ terminates for all $0\leq d<M(x)$,
yielding a contradiction to the definition of $x$. ∎

######  Lemma 6.4.

For every $x\leq y$ we have $x+M(x)\leq y+M(y)$, with equality if and only if
$y<x+M(x)$.

###### Proof.

Let $d=y-x$. If $d<M(x)$, then Lemma 6.2 implies
$y+M(y)=y+M(x+d)=y+M(x)-d=x+M(x)$. Otherwise, we have $y+M(y)>y=x+d\geq
x+M(x)$. ∎

Define the set

$\mathcal{F}^{\prime}_{n}=\\{x+M(x):x\in\mathbb{R}\\}.$

Then Lemma 6.4 implies:

######  Corollary 6.5.

$\mathcal{F}^{\prime}_{n}$ is the set of points at which $M$ tends to zero
from the left:

$\mathcal{F}^{\prime}_{n}=\\{x\in\mathbb{R}:\lim_{y\to x^{-}}M(y)=0\\}.$

######  Lemma 6.6.

$\frac{t_{i}(x)}{i}\geq\frac{t_{i+1}(x)}{i+1}\text{, for each $x\geq 0$ and
$1\leq i\leq n-1$.}$

###### Proof.

By Lemmas 6.2 and 6.4 we have

$\frac{t_{i}(x)}{i}\geq M(x)\geq M(x-t_{i}(x))-t_{i}(x)=t_{i+1}(x)-t_{i}(x),$

which implies the claim. ∎

######  Lemma 6.7.

Every element of $\mathcal{F}^{\prime}_{n}$ is an $n$-fusible number, meaning
$\mathcal{F}^{\prime}_{n}\subseteq\mathcal{F}_{n}$.

###### Proof.

By induction on the depth of the recursive calls in the computation of $M(x)$
we show that if $M(x)$ terminates, then $x+M(x)$ is an $n$-fusible number. In
the base case, when $x<0$ we have $x+M(x)=0$ which is an $n$-fusible number.
Consider the case $x\geq 0$. For each $1\leq i\leq n$ we put
$z_{i}=x-t_{i-1}(x)+t_{i}(x)$. Since $z_{i}=x-t_{i-1}(x)+M(x-t_{i-1}(x))$, by
the induction hypothesis they are $n$-fusible numbers. By Lemma 6.4 we have
$z_{i}\leq x+M(x)$. Finally, observe that $x+M(x)=f_{n}(z_{1},\ldots,z_{n})$,
so $x+M(x)$ is $n$-fusible. ∎

All that remains is to prove that
$\mathsf{ot}(\mathcal{F}^{\prime}_{n})\geq\varphi_{n-1}(0)$.

######  Lemma 6.8.

For every $1\leq i\leq n$, every $x$, and every $0\leq d<t_{i}(x)/i$ we have
$t_{i}(x+d)=t_{i}(x)-di$.

###### Proof.

By induction on $i$. First let $i=1$. Since $0\leq d<t_{1}(x)=M(x-1)$, Lemma
6.4 implies that $t_{1}(x+d)=M(x+d-1)=M(x-1)-d=t_{1}(x)-d$.

Now let $2\leq i\leq n$. By Lemma 6.6 we have $0\leq d<t_{i}(x)/i\leq
t_{i-1}(x)/(i-1)$, so by applying induction on $i$ and then Lemma 6.4, we have
$t_{i}(x+d)=M(x+d-t_{i-1}(x+d))=M(x+d-t_{i-1}(x)+d(i-1))=M(x-t_{i-1}(x)+di)=M(x-t_{i-1}(x))-di=t_{i}(x)-di$.
∎

######  Lemma 6.9.

For every $1\leq i\leq n$, every $x$, and every $0\leq d\leq x$ we have
$t_{i}(x-d)\leq t_{i}(x)+di$.

###### Proof.

Indeed, if $d<t_{i}(x-d)/i$, then we have $t_{i}(x-d)=t_{i}(x)+di$ by Lemma
6.8. Otherwise $t_{i}(x-d)\leq di$ and hence $t_{i}(x-d)<t_{i}(x)+di$ ∎

For $x\geq 0$ and $0<i<n$ let $U_{i}(x)=t_{i}(x)/i$. We also put
$U_{0}(x)=+\infty$.

######  Lemma 6.10.

For every $0\leq i<n$ and $x\geq 0$ we have $U_{i}(x)>M(x)$.

###### Proof.

In view of Lemma 6.6 it is enough to prove that $U_{n-1}(x)>M(x)$, for $x\geq
0$. Suppose for a contradiction that there exists $x$ such that
$U_{n-1}(x)=M(x)$ (by Lemma 6.2 we cannot have $U_{n-1}(x)<M(x)$). Take a
recursion-minimal such $x$. Let $y=x-t_{n-1}(x)=x-(n-1)M(x)$, and note that
$M(x)$ is recursively computed as $M(x)=M(y)/n$. By the recursion-minimality
of $x$, we have either $y\geq 0$ and $t_{n-1}(y)>(n-1)M(y)$, or $y<0$. We
cannot have $y\geq 0$ and $t_{n-1}(y)>(n-1)M(y)$, since by Lemma 6.9 we have
$t_{n-1}(y)=t_{n-1}(x-(n-1)M(x))\leq
t_{n-1}(x)+(n-1)^{2}M(x)=n(n-1)M(x)=(n-1)M(y)$. On the other hand, if $y<0$,
then $nM(x)=M(y)=-y=(n-1)M(x)-x$, so $M(x)=-x\leq 0$, contradicting the fact
that values of $M$ are always positive. ∎

For $x\geq 0$ and $0\leq i<n$ define the interval

$J_{i}(x)=[x-t_{i}(x),x+U_{i}(x)),$

and define the linear transformation

$l_{i}^{x}(y)=\frac{ix}{i+1}+\frac{t_{i}(x)}{i+1}+\frac{y}{i+1}.$

Note that each $l_{i}^{x}$ maps $J_{i}(x)$ onto $[x,x+U_{i}(x))$.

######  Lemma 6.11.

For any $x\geq 0$, $0\leq i<n$, and $y\in J_{i}(x)$ we have

$t_{i+1}(l^{x}_{i}(y))=M(y).$

###### Proof.

If $i=0$ then

$t_{1}(l^{x}_{0}(y))=t_{1}(y+1)=M(y+1-t_{0}(y+1))=M(y+1-1)=M(y).$

Now assume that $i>0$. Let $x_{0}=x-t_{i}(x)$ and $d=y-x_{0}$. Thus

$l_{i}^{x}(y)=\frac{i(x_{0}+t_{i}(x))}{i+1}+\frac{t_{i}(x)}{i+1}+\frac{x_{0}+d}{i+1}=x_{0}+t_{i}(x)+\frac{d}{i+1}.$

Notice that

$d/(i+1)=\frac{y-x_{0}}{i+1}=\frac{y-x+t_{i}(x)}{i+1}<\frac{x+t_{i}(x)/i-x+t_{i}(x)}{i+1}=t_{i}(x)/i.$

Hence by Lemma 6.8

$t_{i}(l_{i}^{x}(y))=t_{i}\Bigl{(}x_{0}+t_{i}(x)+\frac{d}{i+1}\Bigr{)}=t_{i}\Bigl{(}x+\frac{d}{i+1}\Bigr{)}=t_{i}(x)-\frac{id}{i+1}.$

Therefore

$t_{i+1}(l^{x}_{i}(y))=M(l^{x}_{i}(y)-t_{i}(l^{x}_{i}(y)))=M\Bigl{(}x_{0}+t_{i}(x)+\frac{d}{i+1}-t_{i}(x)+\frac{id}{i+1}\Bigr{)}\\\
=M(x_{0}+d)=M(y).$

∎

For $x\in\mathbb{R}$, denote
$o_{\mathit{lim}}(x)=\inf_{\varepsilon>0}\mathsf{ot}(\mathcal{F}_{n}^{\prime}\cap(x-\varepsilon,x))$.
Also denote
$o_{\mathit{lim}}(+\infty)=\inf_{x>0}\mathsf{ot}(\mathcal{F}_{n}^{\prime}\cap[x,+\infty))$.
Hence, if $x$ is not a limit point of $\mathcal{F}_{n}^{\prime}$ then
$o_{\mathit{lim}}(x)=0$, while if $x$ is a limit point of
$\mathcal{F}_{n}^{\prime}$ and
$\mathsf{ot}(\mathcal{F}_{n}^{\prime}\cap(-\infty,x))=\omega^{\alpha_{1}}+\cdots+\omega^{\alpha_{k}}$
in Cantor Normal Form, then $o_{\mathit{lim}}(x)=\omega^{\alpha_{k}}$.

For an ordinal $\alpha$ and $i\geq 0$ let $\eta_{i}(\alpha)$ be the least
limit ordinal of the form $\varphi_{i}(\beta)$, such that
$\varphi_{i}(\beta)>\alpha$.

######  Lemma 6.12.

For any $0\leq i<n$ and $x\geq 0$ we have

$o_{\mathit{lim}}(x+U_{i}(x))\geq\eta_{n-i-1}(o_{\mathit{lim}}(x)).$

###### Proof.

We prove by induction on $0\leq i<n$ in decreasing order that the lemma holds
for all $x\geq 0$.

Since $\mathcal{F}_{n}^{\prime}$ is well-ordered its closure
$\overline{\mathcal{F}}_{n}^{\prime}$ is also well-ordered. Let
$\Lambda=\mathsf{ot}(\overline{\mathcal{F}}_{n}^{\prime}\cap J_{i}(x))$, and
let $\langle a_{\alpha}\mid\alpha<\Lambda\rangle$ be an enumeration of
elements of $\overline{\mathcal{F}}_{n}^{\prime}\cap J_{i}(x)$ in increasing
order. Observe that by Lemma 6.8, for any $x\leq y<x+U_{i}(x)$ we have
$y+U_{i}(y)=x+U_{i}(x)$. Since by Lemma 6.10 $y+M(y)<y+U_{i}(y)$ we see that
there are elements of $\mathcal{F}^{\prime}_{n}$ in any left neighbourhood of
$x+U_{i}(x)$. In other words, $x+U_{i}(x)$ is a limit point of
$\mathcal{F}^{\prime}_{n}$. In particular this implies that both $\Lambda$ and
$o_{\mathit{lim}}(x+U_{i}(x))$ are limit ordinals.

In the case of $i=n-1$, by Lemma 6.11 we have

(3) $M(l^{x}_{n-1}(y))=\frac{M(y)}{n}\text{, for $y\in J_{i}(x)$}.$

Therefore, Corollary 6.5 implies that, for every $y\in J_{i}(x)$, we have
$y\in\mathcal{F}^{\prime}_{n}$ iff
$l^{x}_{n-1}(y)\in\mathcal{F}^{\prime}_{n}$. Consider the points $x_{0}=x$,
$x_{j+1}=l_{n-1}^{x}(x_{j})$. We have
$o_{\mathit{lim}}(x_{j+1})=o_{\mathit{lim}}(x_{j})$. Since
$\lim_{j\to\infty}x_{j}=x+U_{n-1}(x)$, we conclude that
$o_{\mathit{lim}}(x+U_{i}(x))\geq o_{\mathit{lim}}(x)\omega$. In general, for
every ordinal $\alpha>0$, the ordinal $\alpha\omega$ is a power of $\omega$,
so $\alpha\omega\geq\eta_{0}(\alpha)$. Hence, in our case

$o_{\mathit{lim}}(x+U_{i}(x))\geq
o_{\mathit{lim}}(x)\omega\geq\eta_{0}(o_{\mathit{lim}}(x)).$

Now consider the case of $i<n-1$. By Lemma 6.11 we have

(4) $U_{i+1}(l^{x}_{i}(y))=\frac{M(y)}{i+1}\text{, for $y\in J_{i}(x)$}.$

We prove by induction on $\alpha$ that

(5) $o_{\mathit{lim}}(l_{i}^{x}(a_{1+\alpha}))\geq\varphi_{n-i-2}(\alpha).$

Clearly

$a_{1+\alpha}=\sup\\{a_{\beta}+M(a_{\beta})\mid\beta<1+\alpha\\}.$

Hence by (4) we have

$\displaystyle l_{i}^{x}(a_{1+\alpha})$ $\displaystyle=$
$\displaystyle\sup\\{l_{i}^{x}(a_{\beta}+M(a_{\beta}))\mid\beta<1+\alpha\\}$
$\displaystyle=$
$\displaystyle\sup\\{l_{i}^{x}(a_{\beta})+\frac{M(a_{\beta})}{i+1}\mid\beta<1+\alpha\\}$
$\displaystyle=$
$\displaystyle\sup\\{l_{i}^{x}(a_{\beta})+U_{i+1}(l_{i}^{x}(a_{\beta}))\mid\beta<1+\alpha\\}.$

Therefore

$\displaystyle o_{\mathit{lim}}(l_{i}^{x}(a_{1+\alpha}))$ $\displaystyle\geq$
$\displaystyle\sup\\{o_{\mathit{lim}}(l_{i}^{x}(a_{\beta})+U_{i+1}(l_{i}^{x}(a_{\beta})))\mid\beta<1+\alpha\\}$
$\displaystyle\geq$
$\displaystyle\sup(\\{\eta_{n-i-2}(0)\\}\cup\\{\eta_{n-i-2}(\varphi_{n-i-2}(\beta))\mid\beta<\alpha\\})$
$\displaystyle=$ $\displaystyle\varphi_{n-i-2}(\alpha).$

Now we use (5) to show that $\Lambda$ is a fixed point of $\varphi_{n-i-2}$.
Since $\varphi_{n-i-2}$ is a normal function and $\Lambda$ is a limit ordinal,
it is enough to show that for any $\alpha<\Lambda$ we have
$\varphi_{n-i-2}(\alpha)\leq\Lambda$. Consider $\alpha<\Lambda$. Since
$\Lambda\geq\omega$, we have $1+\alpha<\Lambda$. And since
$x<l_{i}^{x}(a_{1+\alpha})<x+U_{i}(x)$, we conclude that
$\Lambda>o_{\mathit{lim}}(l_{i}^{x}(a_{1+\alpha}))$. Thus by (5) we have
$\Lambda\geq\varphi_{n-i-2}(\alpha)$.

Given that $\Lambda>o_{\mathit{lim}}(x)$ and is a fixed point of
$\varphi_{n-i-2}$ we conclude that
$\Lambda\geq\eta_{n-i-1}(o_{\mathit{lim}}(x))$. Since $x+U_{i}(x)$ is a limit
point of $\mathcal{F}^{\prime}_{n}$, we have
$o_{\mathit{lim}}(x+U_{i}(x))=\Lambda$. Thus
$o_{\mathit{lim}}(x+U_{i}(x))\geq\eta_{n-i-1}(o_{\mathit{lim}}(x))$.∎

Applying Lemma 4 in the case of $i=0$ we see that

$\mathsf{ot}(\mathcal{F}^{\prime}_{n})\geq
o_{\mathit{lim}}(U_{0}(0))\geq\eta_{n-1}(0)=\varphi_{n-1}(0).$

Thus taking into account Theorem 5.1 and Lemma 6.7 we have

$\varphi_{n-1}(0)\geq\mathsf{ot}(\mathcal{F}_{n})\geq\mathsf{ot}(\mathcal{F}^{\prime}_{n})\geq\varphi_{n-1}(0),$

as desired.

##  7\. Functions generating sets of high order type

In this section we prove Theorem 1.3. The first step is to build a suitable
function on ordinals:

######  Lemma 7.1.

Let $n\geq 3$, and let
$\Lambda=\varphi(1,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize$n$
times}})$. Then there exists a bijection
$\bar{\varphi}^{\star}:\Lambda^{n}\to\Lambda\setminus\\{0\\}$ that is monotone
(meaning,
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})\leq\bar{\varphi}^{\star}(\beta_{1},\ldots,\beta_{n})$
whenever $\alpha_{i}\leq\beta_{i}$ for all $1\leq i\leq n$), and such that
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})>\max\\{\alpha_{1},\ldots,\alpha_{n}\\}$.

Transfinite induction then implies that every ordinal in $\Lambda$ can be
constructed by starting from $0$ and repeatedly applying
$\bar{\varphi}^{\star}$ on previously constructed ordinals.

The idea of our construction of $\bar{\varphi}^{\star}$ is to start from a
fixed-point free variant $\bar{\varphi}$ of the $n$-ary Veblen function, and
then contracting its range to remove gaps. To analyze the resulting function
$\bar{\varphi}^{\star}$, we make use of a simple comparison criterion
(Proposition 7.3 below) that exactly mirrors the criterion for $\bar{\varphi}$
(Proposition 7.2 below). This comparison criterion makes our construction very
similar to the tree-based ordinal notation by Jervell [Jer05, Jer06], though
Jervell only provides a rough proof sketch of the connection between his tree-
based notation and the standard Veblen function $\varphi$. We also note that a
somewhat different function generating $\Lambda$ was constructed by Schmidt
[Sch20, Theorem 4.8].

###### Proof of Lemma 7.1.

First for $n\geq 2$ we define a fixed-point-free variant $\bar{\varphi}$ of
the $n$-ary Veblen function. Let

$C(\alpha_{1},\ldots,\alpha_{n-1})=\\{\varphi(\alpha_{1},\ldots,\alpha_{n-1},\beta)\mid\beta\in\mathsf{On}\\}.$

Let

$C^{-}(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1})=\\\
C(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1})\setminus(C(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1}+1)\cup\\{\alpha_{1},\ldots,\alpha_{n-1}\\}).$

The fixed-point free $n$-ary Veblen function
$\bar{\varphi}\colon\mathsf{On}^{n}\to\mathsf{On}$ is defined as follows

$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})=\text{``$\alpha_{n}$-th element
of $C^{-}(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1})$''}.$

######  Lemma 7.2.

For any ordinals $\alpha_{1},\ldots,\alpha_{n},\beta_{1},\ldots,\beta_{n}$ we
have
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})<\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$
if and only if at least one of the following conditions holds:

  1. (1)

for some $1\leq i\leq n$ we have
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})\leq\beta_{i}$;

  2. (2)

for some $1\leq i\leq n$ we have $\alpha_{1}=\beta_{1}$, $\ldots$,
$\alpha_{i-1}=\beta_{i-1}$, $\alpha_{i}<\beta_{i}$, and
$\alpha_{i+1},\ldots,\alpha_{n}<\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$.

###### Proof.

Observe that $C(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1}+1)$ is precisely
the set of all fixed points of the function
$x\mapsto\varphi(\alpha_{1},\ldots,\alpha_{n-1},x)$. The value
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n-1},\alpha_{n})$ is $\alpha_{n}$-th
element of $C^{-}(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1})$, i.e. it is
$\alpha_{n}^{\prime}$-th element of
$C(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1})$, for certain
$\alpha_{n}^{\prime}\geq\alpha_{n}$, $\alpha_{n}^{\prime}\not\in
C(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1}+1)$. Therefore

(6)
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n-1},\alpha_{n})=\varphi(\alpha_{1},\ldots,\alpha_{n-1},\alpha_{n}^{\prime})>\alpha_{n}^{\prime}\geq\alpha_{n}.$

It is fairly easy to see that

(7)
$\varphi(\alpha_{1},\ldots,\alpha_{n-1},\alpha_{n})\geq\\{\alpha_{1},\ldots,\alpha_{n}\\}$

and hence

$\min
C(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1})\geq\max\\{\alpha_{1},\ldots,\alpha_{n-1}\\}.$

Therefore

$\min
C^{-}(\alpha_{1},\ldots,\alpha_{n-2},\alpha_{n-1})>\max\\{\alpha_{1},\ldots,\alpha_{n-1}\\}$

and hence

(8)
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n-1},\alpha_{n})>\alpha_{i}\text{,
for $1\leq i<n$}.$

Combining (6) and (8) we see that

(9)
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n-1},\alpha_{n})>\alpha_{i}\text{,
for $1\leq i\leq n$}.$

Therefore if $\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})\leq\beta_{i}$, then
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})<\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$.

Suppose we have $\alpha_{1}=\beta_{1},\ldots,\alpha_{i-1}=\beta_{i-1}$,
$\alpha_{i}<\beta_{i}$, and
$\alpha_{i+1},\ldots,\alpha_{n}<\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$. We
claim that
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})<\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$.
By definition
$\bar{\varphi}(\alpha_{1},\ldots,\allowbreak\alpha_{n})=\varphi(\alpha_{1},\ldots,\alpha_{n-1},\alpha_{n}^{\prime})$
and
$\bar{\varphi}(\beta_{1},\ldots,\beta_{n})=\varphi(\beta_{1},\ldots,\beta_{n-1},\beta_{n}^{\prime})$,
for some $\beta_{n}^{\prime}$. Proposition 3.2 implies that
$\alpha_{n}^{\prime}<\alpha_{n}+\omega$ and
$\beta_{n}^{\prime}<\beta_{n}+\omega$. Hence
$\alpha_{n}^{\prime}<\varphi(\beta_{1},\ldots,\beta_{n-1},\beta_{n}^{\prime})$.
Therefore by the the definition of $\varphi$ we will have
$\varphi(\alpha_{1},\ldots,\allowbreak\alpha_{n-1},\alpha_{n}^{\prime})<\varphi(\beta_{1},\ldots,\beta_{n-1},\beta_{n}^{\prime})$,
which concludes the proof of the claim.

We have proven that that if either condition (1) or condition (2) holds, then
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})<\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$.
Now suppose that neither (1) nor (2) holds. If
$(\alpha_{1},\ldots,\alpha_{n})=(\beta_{1},\ldots,\beta_{n})$ then trivially
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})=\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$,
and the claim follows. Hence, assume $\alpha_{i}\neq\beta_{i}$ for some $i$.
Let $i$ be the minimal such index. If
$\alpha_{j}\geq\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$ for some $j$, then
(9) implies
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})>\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$,
so the claim follows as well. Hence, suppose
$\alpha_{j}<\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$ for every $j$. Since
(2) does not hold, we must have $\beta_{i}<\alpha_{i}$. Furthermore, since (1)
does not hold, we must have
$\beta_{j}<\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})$ for every $j$, in
particular for $j>i$. Hence, (2) holds with $\alpha_{1},\ldots,\alpha_{n}$ and
$\beta_{1},\ldots,\beta_{n}$ switched. As we have shown, this implies
$\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})>\bar{\varphi}(\beta_{1},\ldots,\beta_{n})$.
∎

Continuing the proof of Lemma 7.1, let $A$ be the well-ordering consisting of
all closed terms built from the constant $0$ and the $n$-ary function
$\bar{\varphi}$, where elements of $A$ are compared according to their ordinal
values. Let $\Lambda$ be the order type of $A$. Let
$\bar{\varphi}^{\star}\colon\Lambda^{n}\to\Lambda\setminus\\{0\\}$ be the
following function. Given ordinals $\alpha_{1},\ldots,\alpha_{n}<\Lambda$ such
that terms $t_{1},\ldots,t_{n}\in A$ lie in the positions
$\alpha_{1},\ldots,\alpha_{n}$ respectively, the value
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})$ is the position of the
term $\bar{\varphi}(t_{1},\ldots,t_{n})$. Notice that immediately from Lemma
7.2 it follows that $\bar{\varphi}^{\star}$ is a strictly monotone bijection
between $\Lambda^{n}$ and $\Lambda\setminus\\{0\\}$, for which the analogue of
Lemma 7.2 holds:

######  Proposition 7.3.

For any ordinals $\alpha_{1},\ldots,\alpha_{n},\beta_{1},\ldots,\beta_{n}$ we
have
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})<\bar{\varphi}^{\star}(\beta_{1},\ldots,\beta_{n})$
iff at least one of the following conditions holds:

  1. (1)

for some $1\leq i\leq n$ we have
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})\leq\beta_{i}$;

  2. (2)

for some $1\leq i\leq n$ we have $\alpha_{1}=\beta_{1}$, $\ldots$,
$\alpha_{i-1}=\beta_{i-1}$, $\alpha_{i}<\beta_{i}$, and
$\alpha_{i+1},\ldots,\alpha_{n}<\bar{\varphi}^{\star}(\beta_{1},\ldots,\beta_{n})$.

Since $\bar{\varphi}^{\star}$ is a bijection between $\Lambda^{n}$ and
$\Lambda\setminus\\{0\\}$, Proposition 7.3 implies the following (compare with
Proposition 3.1):

######  Lemma 7.4.

For every $\alpha_{1},\ldots,\alpha_{n}$, the value
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})$ is the least ordinal
$\gamma$ strictly above $\alpha_{1},\ldots,\alpha_{n}$ such that for any
$1\leq i\leq n$, $\beta_{i}<\alpha_{i}$ and
$\beta_{i+1},\ldots,\beta_{n}<\gamma$:

$\gamma>\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{i-1},\beta_{i},\beta_{i+1},\ldots,\beta_{n}).$

The definition of $\bar{\varphi}^{\star}$ immediately implies
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})\leq\bar{\varphi}(\alpha_{1},\ldots,\alpha_{n})$.
On the other hand, we have the following lower bounds for
$\bar{\varphi}^{\star}$ in terms of $\varphi$:

######  Lemma 7.5.

For every $\alpha_{1},\ldots,\alpha_{n}<\Lambda$ we have:

  1. (1)

$\bar{\varphi}^{\star}(0,\ldots,0,\alpha_{n})=\alpha_{n}+1$.

  2. (2)

$\bar{\varphi}^{\star}(0,\ldots,0,\alpha_{n-1},\alpha_{n})\geq\alpha_{n}+\omega^{\alpha_{n-1}}$.

  3. (3)

If $\alpha_{i}>0$ for some $i<n-1$ then
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})$ is an
$\varepsilon$-number.

  4. (4)

$\bar{\varphi}^{\star}(0,\ldots,0,1+\alpha_{n-2},\alpha_{n-1},\alpha_{n})\geq\varphi(0,\ldots,0,\alpha_{n-2},\alpha_{n-1},\alpha_{n})$.

  5. (5)

If $\alpha_{i}>0$ for some $i<n-2$ then
$\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})\geq\varphi(\alpha_{1},\ldots,\alpha_{n})$.

###### Proof.

We proceed by transfinite induction on the lexicographic order of
$\Lambda^{n}=\Lambda\times\cdots\times\Lambda$.

For item (1), suppose
$\gamma=\bar{\varphi}^{\star}(\beta_{1},\ldots,\beta_{n})<\bar{\varphi}^{\star}(0,\ldots,0,\alpha_{n})$.
We will show that $\gamma\leq\alpha_{n}$. Proposition 7.3 implies that either
$\gamma\leq\alpha_{n}$, or else $\beta_{1}=\cdots=\beta_{n-1}=0$ and
$\beta_{n}<\alpha_{n}$. In the latter case, transfinite induction implies
$\gamma=\beta_{n}+1\leq\alpha_{n}$ again.

For item (2), let
$\beta=\bar{\varphi}^{\star}(0,\ldots,0,\alpha_{n-1},\alpha_{n})$, and note
that $\beta>\alpha_{n}$. If $\beta\geq\alpha_{n}+\omega^{\alpha_{n-1}}$ we are
done. Otherwise, there exist $\gamma<\alpha_{n-1}$ and $m\in\mathbb{N}$ such
that $\alpha_{n}+\omega^{\gamma}m<\beta\leq\alpha_{n}+\omega^{\gamma}(m+1)$.
Transfinite induction and Proposition 7.3 imply

$\beta\leq\alpha_{n}+\omega^{\gamma}(m+1)\leq\bar{\varphi}^{\star}(0,\ldots,0,\gamma,\alpha_{n}+\omega^{\gamma}m)<\bar{\varphi}^{\star}(0,\ldots,0,\alpha_{n-1},\alpha_{n})=\beta,$

contradiction.

For item (3), let $\beta=\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})$
where $\alpha_{i}>0$ for some $i<n-1$. It is enough to show that
$\beta>\omega^{\gamma}$ for every $\gamma<\beta$, since this implies
$\beta\geq\omega^{\beta}$. Let $\gamma<\beta$. Then Proposition 7.3 and item
(2) imply
$\beta>\bar{\varphi}^{\star}(0,\ldots,0,\gamma,0)\geq\omega^{\gamma}$, as
desired.

For item (4), let
$\beta=\bar{\varphi}^{\star}(0,\ldots,0,1+\alpha_{n-2},\alpha_{n-1},\alpha_{n})$.
Transfinite induction and Proposition 7.3 imply the following:

  * •

For every $\alpha^{\prime}_{n}<\alpha_{n}$ we have
$\varphi(0,\ldots,0,\alpha_{n-2},\alpha_{n-1},\alpha^{\prime}_{n})\leq\bar{\varphi}^{\star}(0,\ldots,0,1+\alpha_{n-2},\alpha_{n-1},\alpha^{\prime}_{n})<\beta$.

  * •

For every $\alpha^{\prime}_{n-1}<\alpha_{n-1}$ and $\alpha^{\prime}_{n}<\beta$
we have
$\varphi(0,\ldots,0,\alpha_{n-2},\alpha^{\prime}_{n-1},\alpha^{\prime}_{n})\leq\bar{\varphi}^{\star}(0,\ldots,0,1+\alpha_{n-2},\alpha^{\prime}_{n-1},\alpha^{\prime}_{n})<\beta$.

  * •

For every $\alpha^{\prime}_{n-2}<\alpha_{n-2}$ and
$\alpha^{\prime}_{n-1},\alpha^{\prime}_{n}<\beta$ we have
$\varphi(0,\ldots,0,\alpha^{\prime}_{n-2},\alpha^{\prime}_{n-1},\allowbreak\alpha^{\prime}_{n})\leq\bar{\varphi}^{\star}(0,\ldots,0,1+\alpha^{\prime}_{n-2},\alpha^{\prime}_{n-1},\alpha^{\prime}_{n})<\beta$.

Furthermore, by item (3), $\beta$ is of the form $\omega^{\gamma}$. Hence,
Proposition 3.1 implies that
$\varphi(0,\ldots,0,\alpha_{n-2},\alpha_{n-1},\alpha_{n})\leq\beta$, as
desired.

Finally, for item (5), let
$\beta=\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n})$, where
$\alpha_{i}>0$ for some $i<n-2$. Let $1\leq j\leq n$, and suppose
$\alpha^{\prime}_{j}<\alpha_{j}$ and
$\alpha^{\prime}_{j+1},\ldots,\alpha^{\prime}_{n}<\beta$. We claim that
$\gamma=\varphi(\alpha_{1},\ldots,\alpha_{j-1},\alpha^{\prime}_{j},\ldots,\alpha^{\prime}_{n})<\beta$.
If the first $n-3$ elements among
$\alpha_{1},\alpha_{j-1},\alpha^{\prime}_{j},\ldots,\alpha^{\prime}_{n}$ are
not all $0$, then transfinite induction on item (5), together with Proposition
7.3, imply that
$\gamma\leq\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{j-1},\alpha^{\prime}_{j},\ldots,\alpha^{\prime}_{n})<\beta$.
Otherwise, by item (4) and Proposition 7.3 we have

$\gamma=\varphi(0,\ldots,0,\alpha^{\prime}_{n-2},\alpha^{\prime}_{n-1},\alpha^{\prime}_{n})\leq\bar{\varphi}^{\star}(0,\ldots,0,1+\alpha^{\prime}_{n-2},\alpha^{\prime}_{n-1},\alpha^{\prime}_{n})<\beta$

(because $1+\alpha^{\prime}_{n-1}<\beta$, since $\beta$ is an
$\varepsilon$-number). Hence, Proposition 3.1 implies that
$\varphi(\alpha_{1},\ldots,\alpha_{n})\leq\beta$, as desired. ∎

Lemma 7.5 implies that
$\Lambda=\varphi(1,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize$n$
times}})$, as desired. ∎

The next step in proving Theorem 1.3 is to embed $\Lambda$ into the reals.

######  Lemma 7.6.

There exists an order preserving embedding $e$ of $\Lambda$ into $\mathbb{R}$
such that $\sup\limits_{\alpha<\lambda}e(\alpha)<e(\lambda)$, for any limit
ordinal $\lambda<\Lambda$.

###### Proof.

It is easily shown by ordinal induction that any countable ordinal has an
order-preserving embedding into $\mathbb{R}$, and Proposition 3.2 allows us to
remove any limit elements.

For the sake of completeness, we also offer an explicit embedding (which also
works for any countable ordinal). Fix an enumeration
$\alpha_{0},\alpha_{1},\ldots$ (indexed by natural numbers) of elements of
$\Lambda$ such that $\alpha_{0}=0$. We define values $e(\alpha_{i})$ by
induction on $i$. We put $e(\alpha_{0})=0$. To define $e(\alpha_{i+1})$ we
find $0\leq k\leq i$ such that $\alpha_{k}=\max\\{\alpha_{j}\mid j\leq i\text{
and }\alpha_{j}<\alpha_{i+1}\\}$ and next we put
$e(\alpha_{i+1})=e(\alpha_{k})+3^{-k}+3^{-i}$.

By induction on $n$ we simultaneously prove the following two claims:

  1. (1)

$e$ is order preserving on the set $\\{\alpha_{0},\ldots,\alpha_{n}\\}$;

  2. (2)

for any $i,j\leq n$, if $\alpha_{i}<\alpha_{j}$ and $\alpha_{i},\alpha_{j}$
are neighbours in $\\{\alpha_{0},\ldots,\alpha_{n}\\}$, then
$e(\alpha_{j})-e(\alpha_{i})\geq 3^{-i}+2\cdot 3^{-n}+3^{-j}$.

The base holds for trivial reasons. Let us prove the induction step for $n+1$.
If $\alpha_{n+1}>\max\\{\alpha_{0},\ldots,\alpha_{n}\\}$, then both the claims
follow immediately from the definition of $e$ and the induction hypothesis.
Now let $k,l\leq$ be such that $\alpha_{k}<\alpha_{l}$ are neighbours in
$\\{\alpha_{0},\ldots,\alpha_{n}\\}$ and $\alpha_{n+1}$ lies in the interval
$(\alpha_{k},\alpha_{l})$. By the definition of $e$ we have
$e(\alpha_{n+1})=e(\alpha_{k})+3^{-k}+3^{-n}$. Hence we have

$e(\alpha_{n-1})-e(\alpha_{k})=3^{-k}+3^{-n}=3^{-k}+2\cdot
3^{-(n+1)}+3^{-(n+1)}\text{ and}$ $\displaystyle
e(\alpha_{l})-e(\alpha_{n+1})$
$\displaystyle=(e(\alpha_{l})-e(\alpha_{k}))-(e(\alpha_{n+1})-e(\alpha_{k}))$
$\displaystyle\geq 3^{-k}+2\cdot 3^{-n}+3^{-l}-(3^{-k}+3^{-n})$
$\displaystyle=3^{-n}+3^{-l}$ $\displaystyle=3^{-(n+1)}+2\cdot
3^{-(n+1)}+3^{-l}$

Of course this two (in)equalities imply that
$e(\alpha_{k})<e(\alpha_{n+1})<e(\alpha_{l})$ and the whole claim 1. Also they
give us the claim 2. for neighbouring ordinals $\alpha_{k},\alpha_{n+1}$ and
$\alpha_{n+1},\alpha_{l}$. Which finishes induction proof, since for all the
other neighbouring ordinals the claim 2. follows immediately from induction
hypothesis.

Hence $e$ is order preserving. And for any natural $i$, the $3^{-i}$
neighbourhood of $e(\alpha_{i})$ contains no values $e(\beta)$,
$\beta<\Lambda$ other than $e(\alpha_{i})$ itself. Thus
$\sup\limits_{\alpha<\lambda}e(\alpha)<e(\lambda)$, for any limit ordinal
$\lambda<\Lambda$. ∎

The next lemma allows us to extend functions defined on well-orderedered sets
of reals to continuous functions.

######  Lemma 7.7.

Let $W$ be a well-ordered subset of the real line endowed with its natural
order. Assume that $W$ does not contain any of its limit points. Let
$g_{0}\colon W^{n}\to\mathbb{R}$ be a nondecreasing function bounded on
precompact sets. Then there exists a continuous nondecreasing function
$g:\mathbb{R}^{n}\to\mathbb{R}$ such that $g|_{W^{n}}=g_{0}$.

###### Proof.

It is convenient to prove a slightly more general statement: Namely, let us
make the weaker assumption that $W$ is well-ordered in restriction to every
half-line of the form $[a,+\infty)$. Without losing generality, we may now
assume that $W$ contains a point in every unit interval: Indeed, if the given
set $W^{\prime}$ does not satisfy this property, then we can let

$W=W^{\prime}\cup\\{n\in\mathbb{Z}:[n-1/2,n+1/2]\cap W^{\prime}=\emptyset\\}.$

If $W^{\prime}$ is well-ordered in restriction to every half-line of the form
$[a,+\infty)$, then so is $W$. The function $g_{0}$ is extended to the
additional points by setting, for $\vec{m}\in W^{n}\setminus(W^{\prime})^{n}$,
the value $g_{0}(\vec{m})$ to coincide with the value of $g_{0}$ at the
smallest element of $(W^{\prime})^{n}$ exceeding $\vec{m}$ coordinate-wise; if
such an element does not exist, then the function $g_{0}$ must be bounded, and
we set $f(\vec{m})$ to be the supremum of its values.

Let $\overline{W}$ be the closure of $W$. The set $\overline{W}$ is countable.
We extend the function $g_{0}$ onto $\overline{W}^{n}$ by continuity: for
$q\in\overline{W}^{n}$ let $q_{r}\in W^{n}$ be an increasing sequence
converging to $q$ and set $g(q)=\lim_{r\to\infty}g_{0}(q_{r})$. We start by
observing that the monotonicity of $g_{0}$ and the absence of limit points of
$W$ in $W$ together imply that the resulting extension to $\overline{W}^{n}$
is continuous. Indeed, let $q\in\overline{W}^{n}$ be a limit point. One
directly checks that a sufficiently small neighbourhood of $q$ only contains
points from ${W}^{n}$ that are comparable to $q$ and in fact smaller than $q$.
Choosing an arbitrary $\varepsilon>0$ and a point $q_{0}\in W^{n}$ such that
$g(q)<g_{0}(q_{0})+\varepsilon$, we note that in a sufficiently small
neighbourhood of $q$ all points from ${W}^{n}$ will be strictly greater than
$q_{0}$, and the desired continuity follows.

Next, let $p=(p_{1},\dots,p_{n})\in\mathbb{R}^{n}\setminus\overline{W}^{n}$.
Write

$\displaystyle p_{0}(i)$ $\displaystyle=\sup\\{t\in W:t\leq p_{i}\\},$
$\displaystyle p_{1}(i)$ $\displaystyle=\inf\\{t\in W:t\geq p_{i}\\},\quad
i=1,\dots,n.$

Then $p_{i}=\alpha_{0}(i)p_{0}(i)+\alpha_{1}(i)p_{1}(i)$, where
$\alpha_{0}(i),\alpha_{1}(i)\in[0,1]$, $\alpha_{0}(i)+\alpha_{1}(i)=1$,
$i=1,\dots,n$. (If $p_{i}\in\overline{W}$ then $p_{0}(i)=p_{1}(i)=p_{i}$, so
$\alpha_{0}(i),\alpha_{1}(i)$ are not uniquely defined. In that case we can
let, say, $\alpha_{0}(i)=\alpha_{1}(i)=1/2$.) For each
$\vec{\epsilon}=(\epsilon_{1},\dots,\epsilon_{n})\in\\{0,1\\}^{n}$, set

$\alpha_{\vec{\epsilon}}=\alpha_{\epsilon_{1}}(1)\cdots\alpha_{\epsilon_{n}}(n),\quad
p_{\vec{\epsilon}}=(p_{\epsilon_{1}}(1),\dots,p_{\epsilon_{n}}(n)).$

Then we have $\sum_{\vec{\epsilon}\in\\{0,1\\}^{n}}\alpha_{\vec{\epsilon}}=1$,
and

$p=\sum_{\vec{\epsilon}\in\\{0,1\\}^{n}}\alpha_{\vec{\epsilon}}p_{\vec{\epsilon}}.$

Set

$g(p)=\sum_{\vec{\epsilon}\in\\{0,1\\}^{n}}\alpha_{\vec{\epsilon}}g_{0}(p_{\vec{\epsilon}}).$

Since $g|_{{\overline{W}}^{n}}=g_{0}$, the desired extension is constructed.

We now need to check the continuity of the function $g$.

Recall that a uniformly continuous function $f$ on a metric space $(E,d)$ has
a modulus of continuity $\omega$ if

$|f(t_{1})-f(t_{2})|\leq\omega(d(t_{1},t_{2}))$

whenever $d(t_{1},t_{2})\leq 1$. For our purposes, it is convenient to metrize
$\mathbb{R}^{n}$ by $d(\vec{t}(1),\vec{t}(2))=\max_{i}|t_{i}(1)-t_{i}(2)|$. In
this case, a linear function on an axis-parallel box $C$ of diameter not more
than $1$ has modulus of continuity $\omega(t)=At$ where $A$ is the maximum of
the difference of values of our function in the vertices of our box.

We proceed with our argument. Let $B\subset\mathbb{R}^{n}$ be a compact set,
so the restriction of $g_{0}$ to $B$ is uniformly continuous. It suffices to
check the continuity of $g$ in restriction to $B$. Let $\omega$ be the modulus
of continuity of $g_{0}|_{B}$. Assume for simplicity that $B$ is an axis-
parallel box with vertices in $\overline{W}^{n}$.

An axis-parallel box $C\subset\mathbb{R}^{n}$ will be called admissible if it
is of the form $C=[p_{1},q_{1}]\times\cdots\times[p_{n},q_{n}]$ where, for
each $1\leq i\leq n$, $p_{i},q_{i}$ are adjacent elements of $\overline{W}$.
Informally speaking, our aim now is to extend the modulus of continuity first
to the interior of admissible boxes and then to the whole of $B$.

We have the following immediate

######  Lemma 7.8.

Let $t(1),t(2)$ be such that their coordinates either coincide or belong to
$\overline{W}$. Assume that $d(t(1),t(2))\leq 1$ Then

$|g(t(1))-g(t(2))|\leq\omega(d(t(1),t(2))).$

###### Proof.

Indeed, by definition we have

$t(1)=\sum_{\vec{\epsilon}\in\\{0,1\\}^{n}}\alpha_{\vec{\epsilon}}t_{\vec{\epsilon}}(1);\qquad
t(2)=\sum_{\vec{\epsilon}\in\\{0,1\\}^{n}}\alpha_{\vec{\epsilon}}t_{\vec{\epsilon}}(2),$

where $t_{\vec{\epsilon}(1)},t_{\vec{\epsilon}(2)}\in\overline{W}^{n}$: Note
that the coefficients $\alpha_{\vec{\epsilon}}$ are the same for $t(1),t(2)$
and also that $d(t(1),t(2))=d(t_{\vec{\epsilon}}(1),t_{\vec{\epsilon}}(2))$
for all $\vec{\epsilon}\in\\{0,1\\}^{n}$. Since by definition

$g(t(1))=\sum_{\vec{\epsilon}\in\\{0,1\\}^{n}}\alpha_{\vec{\epsilon}}g(t_{\vec{\epsilon}}(1));\qquad
g(t(2))=\sum_{\vec{\epsilon}\in\\{0,1\\}^{n}}\alpha_{\vec{\epsilon}}g(t_{\vec{\epsilon}}(2)),$

the statement follows. ∎

Next, in restriction to an admissible box of diameter $\rho\leq 1$, our
function has modulus of continuity at most $\omega_{1}(s)=s\omega(\rho)/\rho$,
$s\leq\rho$. Hence, let

(10)
$\tilde{\omega}(t)=t\cdot\max_{\rho\in[t,1]}\Bigl{(}\frac{\omega(\rho)}{\rho}\Bigr{)}.$

We claim that $\tilde{\omega}(t)\to 0$ as $t\to 0$. Indeed, let $\rho(t)$ be
the value of $\rho$ that gives the maximum for a given $t$ in (10), and note
that $\rho(t)$ is nonincreasing in $t$. If $\rho(t)\to 0$ as $t\to 0$, then
the fact that $\tilde{\omega}(t)\leq\omega(\rho(t))$ implies that
$\tilde{\omega}(t)\to 0$. Otherwise, let $c>0$ be the limit of $\rho(t)$ as
$t\to 0$. Then $\tilde{\omega}(t)\leq t\omega(1)/c$, which again tends to zero
with $t$.

Hence, $\tilde{\omega}$ can be chosen as the modulus of continuity of our
function restricted to each admissible box within $B$. Furthermore,
$\tilde{\omega}(t)\geq\omega(t)$.

Finally, let $t(1),t(2)\in B$ be two arbitrary points. Consider each
coordinate $i=1,\dots,n$ in turn. Say that $t_{i}(1)<t_{i}(2)$, and consider
the closed interval $I_{i}=[t_{i}(1),t_{i}(2)]$. If $I_{i}$ contains points of
$\overline{W}$ then let $u_{i}(1),u_{i}(2)$ be the minimum and maximum
elements of $I_{i}\cap\overline{W}$, respectively. Otherwise, let
$u_{i}(1)=u_{i}(2)=t_{i}(1)$. By construction, $u(1)$ belongs to the same
admissible box as $t(1)$, and $u(2)$ belongs to the same admissible box as
$t(2)$. Furthermore, none of the distances

$d(t(1),u(1)),d(u(1),u(2)),d(u(2),t(2))$

exceed $d(t(1),t(2))$. We consequently have $|g(t(1))-g(t(2))|\leq
3\tilde{\omega}(d(t(1),t(2)))$, and the desired continuity is established. ∎

Now we finish the proof of Theorem 1.3. Consider $e$ provided by Lemma 7.6.
Consider $W=e[\Lambda]$. Clealry $W$ contains none of its limit points.
Consider the unique $g_{0}\colon W^{n}\to W$ such that
$g_{0}(e(\alpha_{1}),\ldots,e(\alpha_{n}))=e(\bar{\varphi}^{\star}(\alpha_{1},\ldots,\alpha_{n}))$.
Applying Lemma 7.7 we get a function $g\colon\mathbb{R}^{n}\to\mathbb{R}$ such
that its restriction to $W$ coincides with $g_{0}$. From construction it is
obvious that $\mathcal{F}(\\{g\\},\\{0\\})$ coincides with $W$ and hence has
the order type
$\varphi(1,\underbrace{0,\ldots,0}\limits_{\mbox{\footnotesize$n$ times}})$.

######  Remark 7.9.

As we already pointed out before $\mathsf{ot}(\mathcal{F}(G,P))\leq
o(T(P\sqcup G_{0},G_{1},\ldots,\allowbreak G_{n}))$. Schmidt [Sch79, Sch20]
gives certain lower bounds $\Lambda$ for $o(T(W_{1},\ldots,W_{n}))$. For this
she provides a family of monotone functions

$\langle
f_{i,\alpha}\colon\underbrace{\Lambda\times\ldots\times\Lambda}\limits_{\mbox{\scriptsize$i$
times}}\to\Lambda\mid 0\leq i\leq n\text{ and }\alpha<o(W_{i})\rangle,$

where $f_{i,\alpha}(\vec{\beta})\leq f_{i,\alpha^{\prime}}(\vec{\beta})$ for
any number $0\leq i\leq n$, ordinals $\alpha<\alpha^{\prime}<o(W_{i})$, and
$\vec{\beta}\in\underbrace{\Lambda\times\ldots\times\Lambda}\limits_{\mbox{\scriptsize$i$
times}}$. The family additionally has the property that any ordinal $<\Lambda$
is a value of a closed term built from functions from this family. Although we
haven’t checked the details, it looks like that in fashion of our proof of
Theorem 1.3 one could start with this functions and then obtain monotone
continuous functions on reals. In particular this would be sufficient to
construct the following examples. Suppose we are give natural numbers
$k_{0},\ldots,k_{n}$ such that for at least one $i\geq 2$ we have $k_{i}>0$.
Then there are sets $F_{1},\ldots,F_{n}$ of continuous monotone functions on
reals, where each $F_{i}$ is a set of $i$-ary functions and $|F_{i}|=k_{i}$
such that

$\mathsf{ot}(\mathcal{F}_{F_{0}\cup\ldots\cup
F_{n}})=o(T(F_{0},\ldots,F_{n})).$

##  8\. Generating the closure of $\mathcal{F}(G,P)$

In this section we study the closure of the set $\mathcal{F}(G,P)$ in the case
when $P$ is well-ordered and closed and $G$ consists of finitely many linear
functions. We use this analysis later in Section 9.

Given finite sets $G$ and $P$, the set $\mathcal{F}(G,P)$ is not always
closed. For example, the set
$\mathcal{F}_{3}=\mathcal{F}(\\{g_{3}\\},\\{0\\})$ does not contain $1/2$,
since every element of $\mathcal{F}_{3}$ is a fraction whose denominator in
reduced form is a power of $3$. Nevertheless, $\mathcal{F}_{3}$ contains the
numbers $a_{n}=(1-3^{-n})/2$ for $n\in\mathbb{N}$, since
$g_{3}(0,0,a_{n})=a_{n+1}$, and these numbers converge to $1/2$.

As we will show, for every $n$ we have
$\overline{\mathcal{F}_{n}}=\mathcal{F}_{\leq
n}=\mathcal{F}(\\{g_{1},\ldots,g_{n}\\},\\{0\\})$, which, together with
Proposition 3.2, implies $\mathsf{ot}(\mathcal{F}_{\leq n})=\varphi_{n-1}(0)$.
As we will see, this is due to the fact that for every $m\leq n$ the value
$g_{m}(a_{1},\ldots,a_{m})$ is equal to the unique $x$ that satisfies the
equation $x=g_{n}(a_{1},\ldots,a_{m},x,\ldots,x)$. We now develop this idea in
more generality.

Given a monotone unary linear function $h(x)=ax+b$, $0\leq a<1$, let
$\mathsf{fix}(h)=b/(1-a)$ be the fixed point of $h$. Note that for every
$x<\mathsf{fix}(h)$, the sequence $x,h(x),h(h(x)),h^{(3)}(x),\ldots$ is
increasing and converges to $\mathsf{fix}(h)$.

Recall the definition of $\dot{g}_{u,\vec{p}}(x)$ from Section 5. Let us
define the set of functions $\mathsf{cl}(g)$ for a linear function $g$. The
set $\mathsf{cl}(g)$ consists of $g$ itself and certain additional functions
$g_{u}\colon\mathbb{R}^{n-|u|}\to\mathbb{R}$, for some subsets
$u\subsetneq\\{1,\ldots,n\\}$. Consider some $u\subsetneq\\{1,\ldots,n\\}$. If
the unary linear function $\dot{g}_{u,\vec{x}}$ is of the form $ax+b$, where
$a\geq 1$, then we do not define $g_{u}$ and don’t have it in
$\mathsf{cl}(g)$. Otherwise we put
$g_{u}(\vec{y})=\mathsf{fix}(\dot{g}_{u,\vec{y}})$ and add it to
$\mathsf{cl}(g)$.

For a finite set of linear functions $G$ we put
$\mathsf{cl}(G)=\bigcup\limits_{g\in G}\mathsf{cl}(g)$.

######  Proposition 8.1.

Suppose $G$ is a finite set of linear functions and $P$ is a well-ordered and
closed set of constants such that for any $g\in G$ there is $p_{g}\in P$ such
that $g(p_{g},\ldots,p_{g})>p_{g}$. Then
$\overline{\mathcal{F}(G,P)}=\mathcal{F}(\mathsf{cl}(g),P)$.

###### Proof.

First let us prove that
$\mathcal{F}(\mathsf{cl}(G),P)\subseteq\overline{\mathcal{F}(G,P)}$. By
transfinite induction on $a\in\mathcal{F}(\mathsf{cl}(G),P)$ we show that
$a\in\overline{\mathcal{F}(G,P)}$. If $a\in P$, then there is nothing to
prove. Further assume that $a$ is of the form $f(\vec{p})$, for some
$f\in\mathsf{cl}(G)$, $\vec{p}=(p_{1},\ldots,p_{k})$, $\max(\vec{p})<a$,
$\vec{p}\in\mathcal{F}(\mathsf{cl}(G),P)^{k}$. Since by the induction
assumption, $\vec{p}\in\bigl{(}\overline{\mathcal{F}(G,P)}\bigr{)}^{k}$, we
can choose an infinite coordinate-wise non-decreasing sequence
$\vec{s}_{0},\vec{s}_{1},\ldots$ such that each
$\vec{s}_{i}=(s_{i,1},\ldots,s_{i,k})\in(\mathcal{F}(G,P))^{k}$, and such that
the limit of the sequence is $\vec{p}$. We now define a sequence
$q_{0},q_{1},\ldots$ of elements of $\mathcal{F}(G,P)$ that converges to $a$.
If $f$ is some $g\in G$, then we put $q_{i}=g(\vec{s}_{i})$, for all $i$. If
$f$ is $g_{u}$, for some $n$-ary $g\in G$ and $u\subseteq\\{1,\ldots,n\\}$,
then we put $q_{0}=p_{g}$ and $q_{i+1}=\dot{g}_{u,\vec{s}_{i}}(q_{i})$. In
either case, it is easy to see that $q_{i}$’s indeed are elements of
$\mathcal{F}(G)$ and that $\lim_{i\to\infty}q_{i}=a$.

Since $\mathcal{F}(G,P)$ is well-ordered, the set
$\overline{\mathcal{F}(G,P)}$ is also well-ordered. By transfinite induction
on $a\in\overline{\mathcal{F}(G,P)}$ we now prove that
$a\in\mathcal{F}(\mathsf{cl}(G),P)$. If $a$ is not a limit of an infinite
increasing sequence of elements of $\mathcal{F}(G,P)$, then
$a\in\mathcal{F}(G,P)\subseteq\mathcal{F}(\mathsf{cl}(G),P)$. So further we
assume that $a$ is a limit of an infinite increasing sequence
$s_{0}<s_{1}<\ldots$ of elements of $\mathcal{F}(G,P)$. By switching to a
subsequence if necessary, we can assume without loss of generality that either
(1) all $s_{i}$ are in $P$, or (2) for some fixed $g\in G$ and all $i$ the
numbers $s_{i}$ are of the form $g(\vec{p}_{i})$, where
$\vec{p}_{i}=(p_{i,1},\ldots,p_{i,n})\in(\mathcal{F}(G,P))^{n}$. In case (1),
$a=\lim_{i\to\omega}s_{i}\in P$ since $P$ is closed and hence
$a\in\mathcal{F}(G,P)$. Now consider case (2). By applying the infinite
Ramsey’s Theorem if necessary, we can assume that for any $1\leq j\leq n$ the
sequence $p_{0,j},p_{1,j},\ldots$ is either strictly increasing, or constant,
or strictly decreasing. Since $\mathcal{F}(G,P)$ is well-ordered, these
sequences cannot be strictly decreasing. Let $u$ be the set of all indexes
$1\leq j\leq n$ such that $\lim_{i\to\infty}p_{i,j}=r_{j}<a$. Let $\vec{r}$ be
the vector of all $r_{j}$’s, for $j\in u$. By transfinite induction assumption
$\vec{r}\in\mathcal{F}(\mathsf{cl}(G),P)^{|u|}$. By continuity of $g$ we have

$a=g(\lim_{i\to\infty}p_{i,1},\ldots,\lim_{i\to\infty}p_{i,n})=\dot{g}_{u,\vec{r}}(a)=g_{u}(\vec{r})\in\mathcal{F}(\mathsf{cl}{G},P).$

∎

##  9\. Computational aspects

In this section we prove Theorem 1.4. Recall Remark 6.1 on the models of
computation over the reals and the rationals. Let $P$ be a finite set of
initial elements, let $g:\mathbb{R}^{n}\to\mathbb{R}$ be a monotone linear
function, and let $\mathcal{F}=\mathcal{F}(\\{g\\},P)$. Table 1 shows four
interdependent procedures:

  * •

$\textsc{Succ}(r)$ returns the smallest element of $\mathcal{F}$ larger than
$r$.

  * •

$\textsc{BuiltSucc}(r,(y_{1},\ldots,y_{k}))$, when given
$y_{1},\ldots,y_{k}\leq r$, returns the smallest number $s>r$ of the form
$s=g(y_{1},\ldots,y_{k},x_{k+1},\ldots,x_{n})$ for
$x_{k+1},\ldots,x_{n}\in\mathcal{F}\cap(-\infty,r]$.

  * •

$\textsc{Pred}(r)$ returns the predecessor in $\overline{\mathcal{F}}$ of a
given successor element $r\in\overline{\mathcal{F}}$. (If $r$ is not a
successor element in $\overline{\mathcal{F}}$ then Pred runs forever.) Recall
that, by Proposition 8.1, we have
$\overline{\mathcal{F}}=\mathcal{F}(\mathsf{cl}(g),P)$.

  * •

$\textsc{WeakPred}(r)$ is similar to Pred, and returns the unique element
$x\in\overline{\mathcal{F}}$ such that $x\leq r$ and the successor of $x$ is
larger than $r$. (If $r<\min P$ then WeakPred returns $-\infty$.) Unlike Pred,
WeakPred halts on all inputs.

These four procedures call one another recursively (see Figure 1).

Algorithm 1

$\triangleright$ Here $g(x_{1},\ldots,x_{n})=a_{1}x_{1}+\cdots+a_{n}x_{n}+b$

procedure Succ($r$)

$m\leftarrow$BuiltSucc($r$,$()$)

5: $m^{\prime}\leftarrow\min{(P\cap(r,\infty))}$

return $\min{\\{m,m^{\prime}\\}}$

procedure BuiltSucc($r$, $(y_{1},\ldots,y_{k})$)

if $k=n$ then

return $g(y_{1},\ldots,y_{n})$

10: $x_{k+1}\leftarrow$WeakPred($r$)

$m\leftarrow\infty$

while $g(y_{1},\ldots,y_{k},x_{k+1},r,\ldots,r)>r$ do

$s\leftarrow$BuiltSucc($r$, $(y_{1},\ldots,y_{k},x_{k+1})$)

$x^{\prime}\leftarrow x_{k+1}-(s-r)/a_{k+1}$

15: $x^{\prime\prime}\leftarrow$Succ($x^{\prime}$)

$m^{\prime}\leftarrow r+a_{k+1}(x^{\prime\prime}-x^{\prime})$

if $m^{\prime}<m$ then

$m\leftarrow m^{\prime}$

$x_{k+1}\leftarrow$Pred($x^{\prime\prime}$)

20: return $m$

procedure Pred($r$)

$\triangleright$ Let $z_{1},z_{2},z_{3},\ldots$ be an enumeration of the
elements of $\overline{\mathcal{F}}$

if $r\leq\min{P}$ then

return $-\infty$

25: for $i=1,2,3,\ldots$ do

if $z_{i}<r$ and Succ($z_{i}$)${}=r$ then

return $z_{i}$

procedure WeakPred($r$)

$\triangleright$ Let $z_{1},z_{2},z_{3},\ldots$ be an enumeration of the
elements of $\overline{\mathcal{F}}$

30: if $r<\min{P}$ then

return $-\infty$

for $i=1,2,3,\ldots$ do

if $z_{i}=r$ or ($z_{i}<r$ and Succ($z_{i}$)${}>r$) then

return $z_{i}$

Table 1. Inter-dependent recursive algorithms for computational problems
related to $\mathcal{F}(\\{g\\},P)$ for a linear function $g$. Figure 1.
Interdependence between the procedures of Table 1.

Procedures Pred and WeakPred rely on the fact that the set
$\overline{\mathcal{F}}=\mathcal{F}(\mathsf{cl}(g),P)$ is computably
enumerable: For example, one can list its elements by increasing number of
function applications needed to construct them, breaking ties somehow.

We now prove correctness of all four procedures. The following proposition is
self-evident:

######  Proposition 9.1.

Procedures Succ and WeakPred terminate and return the correct value under the
assumption that all the procedure calls made by them terminate and return the
correct values. For a successor element $r\in\overline{\mathcal{F}}$,
procedure $\textsc{Pred}(r)$ terminates and returns the correct value under
the assumption that all its procedure calls terminate and return the correct
values.

######  Lemma 9.2.

Procedure BuiltSucc terminates and returns the correct value under the
assumption that all its procedure calls terminate and return the correct
values.

###### Proof.

Procedure BuiltSucc searches for the optimal value of $x_{k+1}$ in decreasing
order, by starting with the weak predecessor of $r$, and stopping when
$x_{k+1}$ is too small to yield values larger than $r$. At the beginning of
the while loop on line 11, the value of $x_{k+1}$ always belongs to
$\overline{\mathcal{F}}$, and $m$ always holds the smallest value of the form
$s=g(y_{1},\ldots,y_{k},x^{\star},x_{k+2},\ldots,x_{n})$ with $s>r$ and
$x^{\star}\in\mathcal{F}\cap(x_{k+1},r]$ and $x_{k+2},\ldots
x_{n}\in\mathcal{F}\cap(-\infty,r]$.

The value of $s$ on line 12 equals
$g(y_{1},\ldots,y_{k},x_{k+1},x_{k+2},\ldots,x_{n})$ for some optimal choice
of $\bar{x}=(x_{k+2},\ldots,x_{n})$. This choice of $\bar{x}$ is also optimal
if we replace $x_{k+1}$ by any
$x^{\star}\in\mathcal{F}\cap(x^{\prime},x_{k+1})$ for the value of
$x^{\prime}$ computed on line 13, since changing $x_{k+1}$ by an amount $u$
changes the output of $g$ by $a_{k+1}u$. Hence, the best value to give
$x_{k+1}$ under the choice of $\bar{x}$ is $x^{\prime\prime}$ as computed on
line 14. Note that $x^{\prime\prime}$ will never be larger than $x_{k+1}$.

The while loop will always terminate after a finite number of iterations,
since at the top of the loop $x_{k+1}$ always belongs to
$\overline{\mathcal{F}}$ and decreases from one iteration to the next. ∎

######  Lemma 9.3.

Procedures Succ, WeakPred, and BuiltSucc terminate and return the correct
value. For a successor element $r\in\overline{\mathcal{F}}$, procedure
$\textsc{Pred}(r)$ terminates and returns the correct value.

###### Proof.

All we need to do is rule out the possibility of an infinite chain of
procedure calls. So suppose for a contradiction that
$P_{1},P_{2},P_{3},\ldots$ is an infinite chain of procedure calls, where each
$P_{i}$ is one of our four procedures, and each $P_{i}$ was called with
$r=r_{i}$ and it in turn called $P_{i+1}$. We have $r_{1}\geq r_{2}\geq
r_{3}\geq\cdots$. For each $i\in\mathbb{N}$ let
$\sigma_{i}=\min(\overline{\mathcal{F}}\cap[r_{i},\infty))$. Hence,
$\sigma_{1}\geq\sigma_{2}\geq\sigma_{3}\geq\cdots$. Since
$\overline{\mathcal{F}}$ is well ordered, there exist only finitely many
indices $i$ for which $\sigma_{i}>\sigma_{i+1}$. Let $i^{\star}$ be the index
at which $\sigma_{i}$ reaches its minimum value $\sigma^{\star}$. Whenever
$P_{i}$ is Pred or WeakPred we have $\sigma_{i}>\sigma_{i+1}$. Hence, for all
$i\geq i^{\star}$, $P_{i}$ is either Succ or BuiltSucc.

Since BuiltSucc, when given a sequence $(y_{1},\ldots,y_{k})$ of length $k$,
only calls itself on sequences of length $k+1$, we cannot have
$P_{i}=\textsc{BuiltSucc}$ more than $n$ times in a row. Hence, there exist
infinitely many indices $i\geq i^{\star}$ for which $P_{i}=\textsc{BuiltSucc}$
and $P_{i+1}=\textsc{Succ}$, in which case BuiltSucc called Succ on line $14$.
For these indices $i$, the value of $s$ calculated on line $13$ is at least as
large as $\sigma^{\star}$. Hence, the distance between $r_{i+1}$ and
$s^{\star}$ is larger than the distance between $r_{i}$ and $s^{\star}$ by a
factor of at least $(1+1/\max\\{a_{1},\ldots,a_{n}\\})$. Hence,
$\lim_{i\to\infty}r_{i}=-\infty$. However, when BuiltSucc is given $r<\min P$,
it sets $x_{k+1}$ to $-\infty$ on line $9$, and then the condition of the
while loop on line $11$ does not hold, so no call is made to Succ.
Contradiction. ∎

Theorem 1.4 now follows, since $r\in\overline{\mathcal{F}}$ if and only if
$\textsc{WeakPred}(r)=r$. As mentioned, we do not know whether there exists an
algorithm that decides whether $r\in\mathcal{F}$ or not.

## References

  * [dJP77] Dick H. J. de Jongh and Rohit Parikh.  Well-partial orderings and hierarchies.  Indagationes Mathematicae, 39:195–206, 1977.
  * [ENX22] Jeff Erickson, Gabriel Nivasch, and Junyan Xu.  Fusible numbers and Peano arithmetic.  Logical Methods in Computer Science, 18(3):6:1–6:26, 2022.
  * [EPS11] Yuri L. Ershov, Vadim G. Puzarenko, and Alexey I. Stukachev.  $\mathsf{HF}$-computability.  Computability in Context. Computation and Logic in the Real World, 169, 2011.
  * [Eri] Jeff Erickson.  Fusible numbers.  https://www.mathpuzzle.com/fusible.pdf.
  * [FMS82] Harvey M Friedman, Kenneth McAloon, and Stephen G Simpson.  A finite combinatorial principle which is equivalent to the 1-consistency of predicative analysis.  In Studies in Logic and the Foundations of Mathematics, volume 109, pages 197–230. Elsevier, 1982.
  * [Fri20] Harvey Friedman.  857: Finite increasing reducers/2, 2020.  FOM mailing list, https://cs.nyu.edu/pipermail/fom/2020-June/022218.html.
  * [Hig52] Graham Higman.  Ordering by divisibility in abstract algebras.  Proceedings of the London Mathematical Society, 3(1):326–336, 1952\.
  * [Jer05] Herman Ruge Jervell.  Finite trees as ordinals.  In S. Barry Cooper, Benedikt Löwe, and Leen Torenvliet, editors, New Computational Paradigms. CiE 2005, volume 3526 of Lecture Notes in Computer Science, pages 211–220, Berlin, Heidelberg, 2005. Springer.
  * [Jer06] Herman Ruge Jervell.  Constructing ordinals.  Philosophia Scientiæ, CS6:5–20, 2006.
  * [Kru60] Joseph B. Kruskal.  Well-quasi-ordering, the tree theorem, and Vazsonyi’s conjecture.  Transactions of the American Mathematical Society, 95(2):210–225, 1960.
  * [MK08] Andrei S. Morozov and Margarita V. Korovina.  $\sigma$-definability of countable structures over real numbers, complex numbers, and quaternions.  Algebra and Logic, 47(3):193–209, 2008.
  * [RW93] Michael Rathjen and Andreas Weiermann.  Proof-theoretic investigations on Kruskal’s theorem.  Annals of Pure and Applied Logic, 60(1):49–88, 1993.
  * [Sch79] Diana Schmidt.  Well-partial orderings and their maximal order types.  Habilitation, Heidelberg, 1979.
  * [Sch20] Diana Schmidt.  Well-partial orderings and their maximal order types.  In Peter M. Schuster, Monika Seisenberger, and Andreas Weiermann, editors, Well-Quasi Orders in Computation, Logic, Language and Reasoning: A Unifying Concept of Proof Theory, Automata Theory, Formal Languages and Descriptive Set Theory, pages 351–391. Springer International Publishing, Cham, 2020.
  * [Xu12] Junyan Xu.  Survey on fusible numbers, 2012.  arXiv e-prints, math.CO, 1202.5614.