On subrecursive representability of irrational numbers,part II

Abstract

We consider various ways to represent irrational numbers by subrecursive functions. An irrational number can be represented by its base-b expansion; by its base-b sum approximation from below; and by its base-b sum approximation from above. Let $S$ be a class of subrecursive functions, e.g., the class the primitive recursive functions. The set of irrational numbers that can be obtained by functions from $S$ depends on the representation and the base b. We compare the sets obtained by different representations and bases. We also discuss how representations by base-b expansions and sum approximations relate to representations by Cauchy sequences and Dedekind cuts.

Keywords

Computable analysis subrecursive functions honest functions irrational numbers

1. Introduction

The first n digits of a decimal expansion suffice to determine the first n digits of a binary expansion of the same number (we are talking about the digits after the period). On the other hand, any fixed number of digits of a binary expansion are not sufficient to determine the first digit of the decimal expansion of the same number. For example, consider the following two binary expansions $\begin{array}{rcl} α & = & 0.0 {(0011)}^{n} 0010 \dots, \\ β & = & 0.0 {(0011)}^{n} 0100 \dots . \end{array}$ The decimal expansion of α and β start with $0.0 \dots$ and $0.1 \dots$ , respectively. In other words, to determine the first digit after the period, we possibly need to read $4 n + 1$ digits of a binary expansion where n can be arbitrary large.

Unbounded search cannot occur in subrecursive algorithms. The example above shows that unbounded search is required to convert a binary representation into a decimal representation. In contrast, unbounded search is not required to convert a binary representation into a hexadecimal representation. We can compute the first fractional digit of the hexadecimal representation from the first four fractional digits of the binary representation. Then, we can compute the next fractional digit of the hexadecimal representation from the next four fractional digits of the binary representation, and so on.

We can represent the base-b expansion1

¹
Base-b expansions are often called b-adic expansions or b-adic representations in the literature.

of an irrational number α between 0 and 1 by a function

E_{b}^{α}

where

E_{b}^{α} (n)

yields the nth digit of the base-b expansion of α. Let

S

be a sufficiently large natural class of subrecursive functions, e.g., the class of elementary functions, the class of primitive recursive functions or the class of functions that we can prove is total in Peano Arithmetic, and let

S_{b E}

denote the set of irrational numbers between 0 and 1 that have a base-b expansion in

S

, that is,

α \in S_{b E}

if and only if

E_{b}^{α} \in S

. The informal considerations above indicate that

S_{b E}

will depend on b: we should expect that

S_{2 E} \subseteq S_{16 E}

, and we should expect that

S_{10 E} ⊈ S_{2 E}

. For which bases a and b do we, or do we not, have

S_{b E} \subseteq S_{a E}

? It turns out that the inclusion

S_{b E} \subseteq S_{a E}

holds if and only if every prime factor of a is a prime factor of b. We will prove this equivalence for any subrecursive class

S

closed under elementary operations (a subrecursive class will be formally defined as an efficiently enumerable set of computable total functions).

Sum approximations form below and above were introduced in Kristiansen [8]. Let α be an irrational number between 0 and 1. We can uniquely write α as an infinite sum of the form $\begin{matrix} α = 0 + \frac{D_{1}}{b^{k_{1}}} + \frac{D_{2}}{2^{k_{2}}} + \frac{D_{3}}{2^{k_{3}}} + \dots, \end{matrix}$ where

$b \in N ∖ {0, 1}$ and $D_{i} \in {1, \dots, b - 1}$ (note that $D_{i} \neq 0$ for all i),

$k_{i} \in N ∖ {0}$ and $k_{i} < k_{i + 1}$ .

Let

{\hat{A}}_{b}^{α} (i) = D_{i} b^{- k_{i}}

when

i > 0

, and let

{\hat{A}}_{b}^{α} (0) = 0

. The rational number

\sum_{i = 0}^{n} {\hat{A}}_{b}^{α} (i)

is an approximation of α that lies below α, and we will say that the function

{\hat{A}}_{b}^{α}

is the base-b sum approximation from below of α. The base-b sum approximation from above of α is a symmetric function

{\overset{ˇ}{A}}_{b}^{α}

such that

1 - \sum_{i = 0}^{n} {\overset{ˇ}{A}}_{b}^{α} (i)

is an approximation of α that lies above α (and we have

\sum_{i = 0}^{\infty} {\hat{A}}_{b}^{α} (i) + \sum_{i = 0}^{\infty} {\overset{ˇ}{A}}_{b}^{α} (i) = 1

). Let

S_{b ↑}

denote the set of irrational numbers that have a base-b sum approximation from below in a sufficiently large subrecursive class

S

, and let

S_{b ↓}

denote the set of irrational numbers that have a base-b sum approximation of from above in

S

. An interesting fact about sum approximations is that

S_{b ↑}

and

S_{b ↓}

are incomparable classes, that is,

S_{b ↑} ⊈ S_{b ↓}

and

S_{b ↓} ⊈ S_{b ↑}

(and thus it follows rather straightforwardly that

S_{b E} \subset S_{b ↓}

and

S_{b E} \subset S_{b ↑}

). This is really what to expect from results already proven in Kristiansen [8], but we give detailed and neat proofs in this paper.

This paper’s main result on sum approximations is that $S_{b ↓} \subseteq S_{a ↓}$ if and only if $S_{b ↑} \subseteq S_{a ↑}$ if and only if every prime factor of a is a prime factor of b. We prove these equivalences for any $S$ closed under primitive recursion (it is an open problem if it suffices to assume that $S$ is closed under elementary operations). We will also discuss the relationship between sum approximations and Dedekind cuts, and we will prove, or at least sketch proofs of, a number of results conjectured in Kristiansen [8].

The research presented in this paper continues the research presented in Kristiansen [8]. Although this paper is meant to be self-contained, the reader may in several respects benefit from being familiar with [8] before reading this paper. In [8] we treat a number of notions, e.g., continued fractions, trace functions, general sum approximations and $S$ -irrational numbers, that are closely related to base-b sum approximations. We also provide some intuition that might helpful when reading technical parts of this paper. The research presented in this paper is also related to research of Specker [19], Mostkowski [14], Lehman [13], Ko [4,5], Labhalla and Lombardi [11] and a line of research by Georgiev, Skordev and Weiermann, see [3,17,18]. For more on computable real numbers, see Aberth [1] or Weihrauch [21].

2. Notation and terminology

Definition 2.1.
A base is a natural number strictly greater than 1, and a base-b digit is a natural number in the set ${0, 1, \dots, b - 1}$ .

Let M be an integer, let b be a base, and let $D_{1}, \dots, D_{n}$ be base-b digits. We will use ${(M . D_{1} D_{2} \dots D_{n})}_{b}$ to denote the rational number $M + \sum_{i = 1}^{n} D_{i} b^{- i}$ .

Let M be an integer, and let $D_{1}, D_{2}, \dots$ be an infinite sequence of base-b digits. We say that ${(M . D_{1} D_{2} \dots)}_{b}$ is the base-b expansion of the real number α if we have $\begin{matrix} {(M . D_{1} D_{2} \dots D_{n})}_{b} ⩽ α < {(M . D_{1} D_{2} \dots D_{n})}_{b} + b^{- n} \end{matrix}$ for all $n ⩾ 1$ . Moreover, we say that the base-b expansion of α is finite if there exists k such that $α = {(M . D_{1} D_{2} \dots D_{k})}_{b}$ , and we say that the base-b expansion of α is infinite if no such k exists.

We will use $prim (b)$ denote the set of prime factors of the base b, that is, $prim (b) = {p ∣ p is a prime and p | b}$ . We will use $D_{1} \dots D_{j} {(D_{j + 1} \dots D_{k})}^{ω}$ to denote the infinite sequence $\begin{matrix} D_{1} \dots D_{j} D_{j + 1} \dots D_{k} D_{j + 1} \dots D_{k} D_{j + 1} \dots D_{k} \dots . \end{matrix}$ If $D$ is a base-b digit, then $\overline{D}$ denotes the complement digit of $D$ , that is, $\overline{D} = (b - 1) - D$ .

It is easy to verify the following claims:
Any real number has a unique base-b expansion: E.g., ${(0.0 {(9)}^{ω})}_{10}$ is not a base-10 expansion of $10^{- 1}$ according to the definition above. The one and only base-10 expansion of $10^{- 1}$ is ${(0.1 {(0)}^{ω})}_{10}$ .

When ${(M . D_{1} D_{2} \dots)}_{b}$ is the base-b expansion of the real number α, we have $α = {lim}_{n \to \infty} {(M . D_{1} D_{2} \dots D_{n})}_{b}$ , moreover, if the base-b expansion of α is infinite, we have $\begin{matrix} {(M . D_{1} D_{2} \dots D_{n})}_{b} < α < {(M . D_{1} D_{2} \dots D_{n})}_{b} + b^{- n} \end{matrix}$ for all $n ⩾ 1$ .

The base-b expansion of the real number α is finite iff the kth digit of the expansion is 0 for all sufficiently large k.

For any $M \in Z$ and any base-b digits $D_{1}, \dots, D_{n}$ , there exists $m \in Z$ such that ${(M . D_{1} \dots D_{n})}_{b} = m b^{- n}$ .

For any $m \in Z$ , there exist $M \in Z$ and base-b digits $D_{1}, \dots, D_{n}$ such that $m b^{- n} = {(M . D_{1} \dots D_{n})}_{b}$ .

Assume that the base-b expansion of the rational number q is infinite. Then, the base-b expansion of q will be of the form $\begin{matrix} {(M . D_{1} D_{2} \dots D_{j} {(D_{j + 1} \dots D_{s})}^{ω})}_{b}, \end{matrix}$ where $j < s$ and at least one of the digits $D_{j + 1} \dots D_{s}$ is different from 0, moreover, at least one of the digits $D_{j + 1} \dots D_{s}$ is different from $\overline{0}$ , and if $q = m n^{- 1}$ where $m, n \in N$ , then $s < n$ .

If $\begin{matrix} {(M . D_{1} D_{2} \dots D_{n})}_{b} ⩽ α < {(M . D_{1} D_{2} \dots D_{n})}_{b} + b^{- n} \end{matrix}$ then $\begin{matrix} {(M . D_{1} D_{2} \dots D_{j})}_{b} ⩽ α < {(M . D_{1} D_{2} \dots D_{j})}_{b} + b^{- j} \end{matrix}$ for all $j \in {1, \dots, n - 1}$ .

For any base b and any base-b expansion ${(0 . D_{1} D_{2} \dots)}_{b}$ , we have $\begin{matrix} {(0 . D_{1} D_{2} D_{3} \dots)}_{b} + {(0 . {\overline{D}}_{1} {\overline{D}}_{2} {\overline{D}}_{3} \dots)}_{b} = 1 . \end{matrix}$

3. The base transition factor

If we consider the first four fractional digits of the base-10 expansion of a real number, we have enough information to determine the first fractional digit of the base-16 expansion of the number. If the base-10 expansion starts with $0.0624 \dots$ , the base-16 expansion will start with $0.0 \dots$ , and if the base-10 expansions starts with $0.0625 \dots$ , the base-16 expansion will start with $0.1 \dots$ . Thus, we have to consider at least four fractional digits, but four will be enough. We never have to consider the fifth fractional digit to determine the first fractional digit of the base-16 expansion. If we want to determine the first two fractional digits of the base-16 expansion, we have to consider the first 8 fractional digits of the base-10 expansion, in general, if we want to determine the first k fractional digits of the base-16 expansion, we have to consider the first $4 k$ fractional digits of the base-10 expansion.

The base transition factor from base a to base b will be formally defined below. The factor tells us how many digits we have to consider when we want to convert a real from base b to base a. The base transition factor from base 16 to base 10 is 4. (It might sound a bit backwards that we are talking about the base transition factor from base 16 to base 10 and about converting reals from base 10 to base 16, but the terminology makes sense when you read on.) The base transition factor from base 2 to base 10 is 1. It is possible to determine k fractional digits of a base-2 expansion by considering k fractional digits of the base-10 expansion.

The base transition factor from base 10 to base 2 is not defined. This coincides with the fact that we cannot convert an irrational number from base 2 to base 10 without carrying out an unbounded search, see the example at the start of Section 1.

Definition 3.1.
Let a and b be bases such that $prim (a) \subseteq prim (b)$ . We will now define the base transition factor from a to b.

Let $b = p_{1}^{k_{1}} p_{2}^{k_{2}} \dots p_{n}^{k_{n}}$ , where $p_{i}$ is a prime and $k_{i} \in N ∖ {0}$ (for $i = 1, \dots, n$ ), be the prime factorization of b. Then, a can be written of the form $a = p_{1}^{j_{1}} p_{2}^{j_{2}} \dots p_{n}^{j_{n}}$ where $j_{i} \in N$ (for $i = 1, \dots, n$ ). The base transition factor from a to b is the natural number k such that $\begin{matrix} k = max {⌈ \frac{j_{i}}{k_{i}} ⌉ | 1 ⩽ i ⩽ n} . \end{matrix}$

The base transition factor from a to b is not defined if $prim (a) ⊈ prim (b)$ . When we assume that the base transition factor from a to b exists, it is understood that we have $prim (a) \subseteq prim (b)$ .

Clause (3) of the next lemma justifies our terminology. If k is the base transition factor from a to b, then a number of the form $M . D_{1} \dots D_{n}$ in base a can be written of the form $M . D_{1} \dots D_{k n}$ in base b.
Lemma 3.2.
Let k be the base transition factor from a to b. Then
there exists $\hat{m} \in N$ such that $a^{- 1} = \hat{m} b^{- k}$ ,

for any $m \in Z$ and any $n \in N$ , there exists $\hat{m} \in Z$ such that $m a^{- n} = \hat{m} b^{- k n}$ ,

for any $n \in N$ and any base-a digits $D_{1}, \dots, D_{n}$ , there exists $\hat{m} \in N$ such that ${(0 . D_{1} \dots D_{n})}_{a} = \hat{m} b^{- k n}$ (and thus there exists base-b digits ${\dot{D}}_{1}, \dots, {\dot{D}}_{k n}$ such that ${(0 . D_{1} \dots D_{n})}_{a} = {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b}$ ).

Proof.
Let $\begin{matrix} b = p_{1}^{k_{1}} \dots p_{n}^{k_{n}} and a = p_{1}^{j_{1}} \dots p_{n}^{j_{n}} \end{matrix}$ where $p_{i}$ is a prime and $k_{i} \in N ∖ {0}$ and $j_{i} \in N$ (for $i = 1, \dots, n$ ). It is easily seen from the definition of k that $k ⩾ ⌈ \frac{j_{i}}{k_{i}} ⌉$ , and thus we have $k_{i} k - j_{i} ⩾ 0$ (for $i = 1, \dots, n$ ). Furthermore, we have $\begin{array}{l} a^{- 1} = & {(p_{1}^{j_{1}} \dots p_{n}^{j_{n}})}^{- 1} \\ = & (p_{1}^{(k_{1} k - j_{1})} \dots p_{n}^{(k_{n} k - j_{n})}) {(p_{1}^{j_{1} + (k_{1} k - j_{1})} \dots p_{n}^{j_{n} + (k_{n} k - j_{n})})}^{- 1} \\ = & (p_{1}^{(k_{1} k - j_{1})} \dots p_{n}^{(k_{n} k - j_{n})}) {(p_{1}^{k_{1} k} \dots p_{n}^{k_{n} k})}^{- 1} \\ = & (p_{1}^{(k_{1} k - j_{1})} \dots p_{n}^{(k_{n} k - j_{n})}) {(p_{1}^{k_{1}} \dots p_{n}^{k_{n}})}^{- k} \\ = & (p_{1}^{(k_{1} k - j_{1})} \dots p_{n}^{(k_{n} k - j_{n})}) b^{- k} . \end{array}$ Hence, let $\hat{m} = p_{1}^{(k_{1} k - j_{1})} \dots p_{n}^{(k_{n} k - j_{n})}$ and (1) holds.

We turn to the proof of (2). By (1), we have $t \in N$ such that $m a^{- n} = m {(a^{- 1})}^{n} = m {(t b^{- k})}^{n} = m t^{n} b^{- k n}$ . Thus, let $\hat{m} = m t^{n}$ , and (2) holds.

Now it is easy to see that (3) holds. By our definitions, we have ${(0 . D_{1} \dots D_{n})}_{a} = \sum_{i = 1}^{n} D_{i} a^{- i}$ . Thus, we have ${(0 . D_{1} \dots D_{n})}_{a} = m a^{- n}$ for some $m \in N$ . By (2), we have $\hat{m} \in N$ such that ${(0 . D_{1} \dots D_{n})}_{a} = \hat{m} b^{- k n}$ . □
Theorem 3.3 (The Base Transition Theorem).

Let k be the base transition factor from a to b, and let ${(M . D_{1} D_{2} \dots)}_{a}$ and ${(M . {\dot{D}}_{1} {\dot{D}}_{2} \dots)}_{b}$ be, respectively, the base-a and base-b expansion of an arbitrary real number α. Then, for all $n \in N$ , we have $\begin{matrix} {(M . D_{1} \dots D_{n})}_{a} ⩽ {(M . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} ⩽ α < {(M . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} + b^{- k n} ⩽ {(M . D_{1} \dots D_{n})}_{a} + a^{- n} . \end{matrix}$

Proof.
We can w.l.o.g. assume $0 < α < 1$ . By Definition 2.1, we have $\begin{matrix} (†) & {(0 . D_{1} \dots D_{i})}_{a} ⩽ α < {(0 . D_{1} \dots D_{i})}_{a} + a^{- i} \end{matrix}$ and $\begin{array}{l} (‡) & {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{i})}_{b} ⩽ α < {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{i})}_{b} + b^{- i} \end{array}$ for all $i \in N$ . Claim I.
For all $n \in N$ , we have ${(0 . D_{1} \dots D_{n})}_{a} ⩽ {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b}$ .

Assume that the claim does not hold. Then, for some n we have ${(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} < {(0 . D_{1} \dots D_{n})}_{a}$ . By Lemma 3.2, we have $m_{1}, m_{2} \in N$ such that $m_{1} b^{- k n} = {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} < {(0 . D_{1} \dots D_{n})}_{a} = m_{2} b^{- k n}$ . Thus, ${(0 . D_{1} \dots D_{n})}_{a} - {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} > b^{- k n}$ , and then, by (†), we have ${(M . D_{1} \dots D_{k n})}_{b} + b^{- k n} < {(M . D_{1} \dots D_{n})}_{a} ⩽ α$ . This contradicts (‡). This proves Claim I. Claim II.
For all $n \in N$ , we have ${(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} + b^{- k n} ⩽ {(0 . D_{1} \dots D_{n})}_{a} + a^{- n}$ .

It follows straightforwardly from (†) and (‡) that ${(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} < {(0 . D_{1} \dots D_{n})}_{a} + a^{- n}$ . Thus, $\begin{matrix} 0 < {(0 . D_{1} \dots D_{n})}_{a} + a^{- n} - {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} . \end{matrix}$ By Lemma 3.2, we have $m_{1}, m_{2} \in N$ such that $\begin{matrix} 0 < {(0 . D_{1} \dots D_{n})}_{a} + a^{- n} - {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} = m_{1} b^{- k n} - m_{2} b^{- k n} \end{matrix}$ (thus $m_{1}$ has to be strictly greater than $m_{2}$ ). It follows that ${(0 . D_{1} \dots D_{n})}_{a} + a^{- n} - {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} ⩾ b^{- k n}$ . Hence, ${(0 . D_{1} \dots D_{n})}_{a} + a^{- n} ⩾ {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} + b^{- k n}$ . This completes the proof of Claim II.

Now it is easy to see that our theorem holds. By Claim I and (‡), we have $\begin{matrix} {(0 . D_{1} \dots D_{n})}_{a} ⩽ {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} ⩽ α < {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} + b^{- k n} \end{matrix}$ and then the theorem follows by Claim II. □

The next corollary will be needed in the proof of one of our main results.
Corollary 3.4.
Let k be the base transition factor from a to b, and let ${(M . D_{1} D_{2} \dots)}_{a}$ and ${(M . {\dot{D}}_{1} {\dot{D}}_{2} \dots)}_{b}$ be, respectively, the base-a and base-b expansion of an arbitrary real number α. Then, for all $n, ℓ \in N$ , we have $\begin{matrix} {(M . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} < {(M . {\dot{D}}_{1} \dots {\dot{D}}_{ℓ})}_{b} \Rightarrow {(M . D_{1} \dots D_{n})}_{a} < {(M . D_{1} \dots D_{m ℓ})}_{a}, \end{matrix}$ where $m = ⌈ {log}_{a} b ⌉$ .
Proof.
Assume ${(M . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} < {(M . {\dot{D}}_{1} \dots {\dot{D}}_{ℓ})}_{b}$ . By the Base Transition Theorem, we have $\begin{matrix} {(M . D_{1} \dots D_{n})}_{a} ⩽ {(M . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} < {(M . {\dot{D}}_{1} \dots {\dot{D}}_{ℓ})}_{b} < α . \end{matrix}$ Hence $\begin{array}{l} () & α - {(M . D_{1} \dots D_{n})}_{a} > b^{- ℓ} . \end{array}$

Assume for the sake of contradiction that ${(M . D_{1} \dots D_{n})}_{a} ⩾ {(M . D_{1} \dots D_{m ℓ})}_{a}$ . Then we have $\begin{matrix} α - {(M . D_{1} \dots D_{n})}_{a} ⩽ α - {(M . D_{1} \dots D_{m ℓ})}_{a} < a^{- m ℓ} = {(a^{m})}^{- ℓ} = {(a^{⌈ {log}_{a} b ⌉})}^{- ℓ} ⩽ b^{- ℓ} . \end{matrix}$ This contradicts (), and thus we conclude that ${(M . D_{1} \dots D_{n})}_{a} < {(M . D_{1} \dots D_{m ℓ})}_{a}$ . (Note that we by our definitions have $α - {(M . D_{1} \dots D_{n})}_{a} < a^{- n}$ for all n. See Definition 2.1.) □

We round off the section with another theorem on the base transition factor. The theorem is a kind of converse version of Theorem 3.3. We will not need this theorem later, but we will need the lemma leading up to the theorem. Lemma 3.5.
Let a and b be bases, let $p \in prim (a) ∖ prim (b)$ , and let $m \in Z$ and $n \in N$ be such that $m p^{- n} \notin Z$ . Then, the rational number $m p^{- n}$ has a finite base-a and an infinite base-b expansion.
Proof.
There is a base-a digit $D_{1}$ such that $a = p \times D_{1}$ . Thus, we have $p^{- 1} = {(0 . D_{1})}_{a}$ . The product of two numbers with a finite base-a expansion has a finite base-a expansion. Thus, $m p^{- n}$ has a finite base-a expansion as $m p^{- n}$ can be written of the form $m \times {(0 . D_{1})}_{a} \times \dots \times {(0 . D_{1})}_{a}$ .

Assume that $m p^{- n}$ has a finite base-b expansion (and recall that $m p^{- n}$ is not an integer). Then there exist $\hat{m} \in Z$ and $\hat{n} \in N$ such that $m p^{- n} = \hat{m} b^{- \hat{n}}$ . But p does not occur in the prime factorization of b. Thus, the equality $m p^{- n} = \hat{m} b^{- \hat{n}}$ contradicts that every base has a unique prime factorization. □
Theorem 3.6.
Assume that k is a natural number such that for every $α \in R$ and every $n \in N ∖ {0}$ , we have $\begin{matrix} {(M . D_{1} \dots D_{n})}_{a} ⩽ {(M . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} ⩽ α < {(M . {\dot{D}}_{1} \dots {\dot{D}}_{k n})}_{b} + b^{- k n} ⩽ {(M . D_{1} \dots D_{n})}_{a} + a^{- n}, \end{matrix}$ where ${(M . D_{1} D_{2} \dots)}_{a}$ and ${(M . {\dot{D}}_{1} {\dot{D}}_{2} \dots)}_{b}$ are, respectively, the base-a and base-b expansion of α. Then we have $prim (a) \subseteq prim (b)$ . Moreover, the base transition factor from a to b is the least k with this property.
Proof.
It follows from Lemma 3.5 that $prim (a) \subseteq prim (b)$ . We leave to the reader to check that there cannot be a natural number less than the base transition factor from a to b that possesses the property. □

4. Subrecursion theory

4.1. General preliminaries

We assume acquaintance with subrecursion theory and, in particular, with the elementary functions. An introduction to this subject can be found in [15] or [16]. Here we just state some important basic facts and definitions, see [15] and [16] for proofs. We will also assume that the reader is familiar with basic concepts of computability theory, e.g., Kleene’s T-predicate and computable indexes. An introduction to elementary computability theory can be found in, e.g., [2] or [12].

The initial elementary functions are the projection functions ( $I_{i}^{n}$ ), the constants 0 and 1, addition (+) and modified subtraction ( $\dot{}$ ). The elementary definition schemes are composition, that is, $f (\vec{x}) = h (g_{1} (\vec{x}), \dots, g_{m} (\vec{x}))$ and bounded sum and bounded product, that is, respectively $f (\vec{x}, y) = \sum_{i < y} g (\vec{x}, i)$ and $f (\vec{x}, y) = \prod_{i < y} g (\vec{x}, i)$ . A function is elementary if it can be generated from the initial elementary functions by the elementary definition schemes. A relation $R (\vec{x})$ is elementary when there exists an elementary function f with range ${0, 1}$ such that $f (\vec{x}) = 0$ iff $R (\vec{x})$ holds. Relations may also be called predicates, and we will use the two words interchangeably. A function f has elementary graph if the relation $f (\vec{x}) = y$ is elementary.

The definition scheme $(μ z ⩽ x) [\dots]$ is called the bounded μ-operator, and $(μ z ⩽ y) [R (\vec{x}, z)]$ denotes the least $z ⩽ y$ such that the relation $R (\vec{x}, z)$ holds. Let $(μ z ⩽ y) [R (\vec{x}, z)] = y + 1$ if no such z exists. The class of elementary functions is closed under the bounded μ-operator. The definition scheme $\begin{matrix} f (\vec{x}, 0) = g (\vec{x}) and f (\vec{x}, y + 1) = h (\vec{x}, y, g (\vec{x}, y)) \end{matrix}$ is called primitive recursion. If f is defined by a primitive recursion over g and h and $f (\vec{x}, y) ⩽ j (\vec{x}, y)$ , then f is defined by bounded primitive recursion over g, h and j. The class of elementary functions is closed under bounded primitive recursion, but not under primitive recursion. Moreover, the class of elementary relations is closed under the operations of the propositional calculus and under bounded quantification.

Let $2_{0}^{x} = x$ and $2_{n + 1}^{x} = 2^{2_{n}^{x}}$ , and let s denote the successor function. The class of elementary functions equals the closure of ${0, s, I_{i}^{n}, 2^{x}, max}$ under composition and bounded primitive recursion. Given this characterization of the elementary functions, it is easy to see that for any elementary function f, we have $f (\vec{x}) ⩽ 2_{k}^{max (\vec{x})}$ for some fixed k.

We will say that a class of functions is closed under the elementary operations when the class contains all the elementary functions and is closed under composition and bounded primitive recursion. We will say that a class of functions is closed under the primitive recursive operations when the class contains all the elementary functions and is closed under composition and (unbounded) primitive recursion.

Uniform systems for coding finite sequences of natural numbers are available inside the class of elementary functions. Let $\overline{f} (x)$ be the code number for the sequence $⟨ f (0), f (1), \dots, f (x) ⟩$ . Then $\overline{f}$ belongs to the elementary functions if f does. We will indicate the use of coding functions with the notations $⟨ \dots ⟩$ and ${(x)}_{i}$ where ${(⟨ x_{0}, \dots, x_{i}, \dots, x_{n} ⟩)}_{i} = x_{i}$ . (So $(x, i) \mapsto {(x)}_{i}$ is an elementary function.) Our coding system is monotone, that is, $⟨ x_{0}, \dots, x_{n} ⟩ < ⟨ x_{0}, \dots, x_{n}, y ⟩$ holds for any y, and $⟨ x_{0}, \dots, x_{i}, \dots, x_{n} ⟩ < ⟨ x_{0}, \dots, x_{i} + 1, \dots, x_{n} ⟩$ . All the closure properties of the elementary functions can be proved by using Gödel numbering and standard coding techniques.

We use $f^{k}$ to denote the kth iterate of the function f, that is, $f^{0} (x) = x$ and $f^{k + 1} (x) = f (f^{k} (x))$ .

4.2. Coding of rationals

Subrecursive functions in general, and elementary functions in particular, are formally functions over natural numbers ( $N$ ). We assume some coding of integers ( $Z$ ) and rational numbers ( $Q$ ) into the natural numbers. We consider such a coding to be trivial. Therefore we allow for subrecursive functions from rational numbers into natural numbers, from pairs of rational numbers into rational numbers, etc., with no further comment.

As seen above, uniform systems for coding finite sequences of natural numbers are available inside the class of elementary functions. Hence, for any reasonable coding, basic operations on rational numbers – like addition, subtraction and multiplication – will obviously be elementary. We also consider the next lemma to be obvious, and we skip its proof.

Lemma 4.1.
Let ${(M . D_{1}^{q} D_{2}^{q} \dots)}_{b}$ denote base-b expansion of the rational number q. There exists an elementary function $digit : N \times Q \times N \to N$ such that for any rational number q, we have ${digit}_{n} (q, b) = D_{n}^{q}$ .

4.3. Honest functions and subrecursive classes

The proof of our main results are based on the theory of honest functions. In this subsection, we state and prove lemmas and theorems on honest functions that will be needed later. For more on honest functions, see [9] or [10].

Definition 4.2.
A function $f : N \to N$ is honest if it is monotone ( $f (x) ⩽ f (x + 1)$ ), dominates $2^{x}$ ( $f (x) ⩾ 2^{x}$ ) and has elementary graph.

From now on, we reserve the letters $f, g, h, \dots$ to denote honest functions. Small Greek letter like $ϕ, ψ, ξ, \dots$ will denote number-theoretic functions not necessarily being honest.
Definition 4.3.
A function ϕ is elementary in a function ψ, written $ϕ ⩽_{E} ψ$ , if ϕ can be generated from the initial functions ψ, $2^{x}$ , max, 0, s (successor), $I_{i}^{n}$ (projections) by composition and bounded primitive recursion.
Lemma 4.4.
Let $ψ ⩽_{E} f$ where f is an honest function. Then there exists $k \in N$ such that $\begin{matrix} ψ (x_{1}, \dots, x_{n}) ⩽ f^{k} (max (x_{1}, \dots, x_{n})) . \end{matrix}$
Proof.
The function ψ can be generated from the initial functions f, $2^{x}$ , max, 0, s, $I_{i}^{n}$ by composition and bounded primitive recursion. Use induction on such a generation of ψ to prove that the lemma holds. Use that f is monotone and dominates $2^{x}$ . □

Let $T_{n}$ denote the Kleene T-predicate, and let $U$ denote the decoding function known from Kleene’s Normal Form Theorem. We have $\begin{matrix} ϕ (x_{1}, \dots, x_{n}) = {e} (x_{1}, \dots, x_{n}) = U (μ t [T_{n} (e, x_{1}, \dots, x_{n}, t)]) \end{matrix}$ when e is a computable index for ϕ. We will need the next theorem which is superficially proved in Kristiansen [6]. A more detailed proof can be found in Kristiansen [7]. Theorem 4.5 (Normal Form Theorem).

Let f be an honest function. Let ϕ be any (Turing) computable function. Then, $ϕ ⩽_{E} f$ iff there exists a computable index e for ϕ and a fixed $k \in N$ such that $\begin{matrix} ϕ (x_{1}, \dots, x_{n}) = {e} (x_{1}, \dots, x_{n}) = U (μ t ⩽ f^{k} (max (x_{1}, \dots, x_{n})) [T_{n} (e, x_{1}, \dots, x_{n}, t)]) . \end{matrix}$ Moreover, $U$ is an elementary function, and $T_{n}$ is an elementary predicate.

Definition 4.6.
For any honest function f, we define the jump of f, written $f^{'}$ , by $f^{'} (x) = f^{x + 1} (x)$ .
Lemma 4.7.
Let f be an honest function. Then, $f^{'}$ is an honest function.
Proof.
It is obvious that $f^{'}$ is monotone and dominates $2^{x}$ . Let $ψ (x, y)$ be an elementary function that places a bound on the code number for the sequence $⟨ y, y, \dots, y ⟩$ of length $x + 1$ . Then, $f^{'} (x) = y$ is equivalent to $\begin{array}{l} () & (\exists s ⩽ ψ (x, y)) [{(s)}_{0} = f (x) \land (\forall i < x) [{(s)}_{i + 1} = f ({(s)}_{i})] \land {(s)}_{x} = y] . \end{array}$ Thus, the relation $f^{'} (x) = y$ is elementary since all the functions, relations and operations involved in () are elementary. This proves that $f^{'}$ has elementary graph. □
Lemma 4.8.
Let f be an honest function, and let ψ be a unary function such that $ψ ⩽_{E} f$ . Then we have $ψ (x) < f^{'} (x)$ for all sufficiently large x.
Proof.
By Lemma 4.4, we have $k \in N$ such that $ψ (x) ⩽ f^{k} (x)$ . Let $x ⩾ k$ . Then we have $ψ (x) ⩽ f^{k} (x) < f^{x + 1} (x) = f^{'} (x)$ . □
Definition 4.9.
Let $σ : N \to N$ be a total function, and let $\begin{matrix} {[e]}^{σ} (x) = U (μ t [T_{1} (σ (e), x, t)]), \end{matrix}$ where $T_{1}$ and $U$ are the elementary functions from Kleene’s Normal Form Theorem (see Theorem 4.5).

A set $S$ of functions over the natural numbers is a subrecursive class when there exists a total computable function $σ : N \to N$ such that
the function ${[e]}^{σ}$ is total,

for every $ϕ \in S$ there exists $e \in N$ such that $ϕ (x_{1}, \dots, x_{n}) = {[e]}^{σ} (⟨ x_{1}, \dots, x_{n} ⟩)$ .
We say that the function σ generates the class $S$ . (So, a subrecursive class is a subset of an efficiently enumerable class of total functions.)
Theorem 4.10.
For any subrecursive class $S$ , there exists an honest function f such that $\begin{matrix} ψ \in S \Rightarrow ψ ⩽_{E} f . \end{matrix}$
Proof.
Assume that $S$ is generated by the total computable function σ. Let $e_{σ}$ be a computable index for σ, and let $\begin{matrix} f (x) = μ t [t ⩾ 2^{x} \land (\forall i ⩽ x) (\exists t_{1} ⩽ t) [T_{1} (e_{σ}, i, t_{1}) \land (\forall j ⩽ x) (\exists t_{2} ⩽ t) [T_{1} (U (t_{1}), j, t_{2})]]] . \end{matrix}$ Now, f is a total computable function as σ and ${[e]}^{σ}$ are total computable functions. The graph of f is elementary, moreover, f is monotone and dominates $2^{x}$ . Thus, f is honest. A proof of the claim below can be found in Section 8 of Kristiansen [8]. Claim.
If $x ⩾ e$ , then $f (x) ⩾ μ t [T_{1} (σ (e), x, t)]$ .

Now, let ψ be any function in $S$ . Then, we have e such that $ψ (\vec{x}) = {[e]}^{σ} (⟨ \vec{x} ⟩)$ . Let $d = σ (e)$ . By the claim, we have $\begin{matrix} ψ (\vec{x}) = {[e]}^{σ} (⟨ \vec{x} ⟩) = U (μ t [T_{1} (d, ⟨ \vec{x} ⟩, t)]) = U (μ t ⩽ f (⟨ \vec{x} ⟩) [T_{1} (d, ⟨ \vec{x} ⟩, t)]) \end{matrix}$ whenever $⟨ \vec{x} ⟩ ⩾ e$ . Thus, we have $\begin{matrix} ψ (\vec{x}) = U ((μ t ⩽ f (⟨ \vec{x} ⟩ + e)) [T_{1} (d, ⟨ \vec{x} ⟩, t)]) \end{matrix}$ for all $\vec{x}$ . This proves that ψ is elementary in f. □
Lemma 4.11.
Let ψ be any function over the natural numbers. For any honest function g, there exists an honest function f such that $\begin{matrix} ψ ⩽_{PR} g \Rightarrow ψ ⩽_{E} f . \end{matrix}$
Proof.
Let $S = {ψ ∣ ψ ⩽_{PR} g}$ . It is easy to see that $S$ is a subrecursive class in the sense of Definition 4.9. Assume $ψ ⩽_{PR} g$ . Then, $ψ \in S$ . By Theorem 4.10, we have f such that $ψ ⩽_{E} f$ . □

5. Base-b expansions

From now on we will restrict our attention to irrational numbers between 0 and 1. This entails no loss of generality.

Definition 5.1.
Let ${(0 . D_{1} D_{2} \dots)}_{b}$ be the base-b expansion of the real number α. We define the function $E_{b}^{α} : N \to {0, \dots, b - 1}$ by $E_{b}^{α} (0) = 0$ and $E_{b}^{α} (i) = D_{i}$ (for $i ⩾ 1$ ). For any class of functions $S$ , let $S_{b E} = {α ∣ E_{b}^{α} \in S}$ .

We will occasionally identify the function $E_{b}^{α}$ with the base-b expansion of α, and we may, e.g., say that $S_{b E}$ is the set of irrational numbers with a base-b expansion in $S$ .
Theorem 5.2.
Let a and b be bases such that $prim (a) \subseteq prim (b)$ . For any real number $α \in [0, 1)$ , we have $E_{a}^{α} ⩽_{E} E_{b}^{α}$ .
Proof.
Let ${(0 . D_{1} D_{2} \dots)}_{b}$ be the base-b expansion of α, and let k be the base transition factor from a to b. By the Base Transition Theorem, we have $\begin{matrix} E_{a}^{α} (n) = {digit}_{n} ({(0 . D_{1} \dots D_{k n})}_{b}, a), \end{matrix}$ where $digit$ is the elementary function given by Lemma 4.1. Moreover $\begin{matrix} {(0 . D_{1} \dots D_{k n})}_{b} = \sum_{i = 1}^{k n} E_{b}^{α} (i) b^{- i} . \end{matrix}$ Thus, $E_{a}^{α}$ is elementary in $E_{b}^{α}$ . □

The preceding theorem says that we can compute $E_{a}^{α}$ elementarily in $E_{b}^{α}$ if $prim (a)$ is a subset of $prim (b)$ . We cannot in general compute $E_{a}^{α}$ elementarily in $E_{b}^{α}$ if $prim (a)$ is not a subset of $prim (b)$ . This is a consequence of the next theorem. In the proof of the theorem we construct a sequence of rationals $q_{0}, q_{1}, q_{2}, \dots$ that converges to an irrational number α. The sequence is constructed such that α becomes different from every real whose base-a expansion is elementary in a given honest function f. Still, it turns out that α has an elementary base-b expansion. It is possible to construct the sequence $q_{0}, q_{1}, q_{2}, \dots$ for any honest function f and any bases a and b where $prim (a) ⊈ prim (b)$ . We will explain some of the ideas behind the construction such that it becomes easier for the reader to follow the technical proof.

We start the construction by picking a sequence $d_{0}, d_{1}, d_{2}, \dots$ of natural numbers. We set $d_{0}$ to some suitable number, and then we define $d_{i + 1}$ by $d_{i + 1} = f^{'} (d_{i})$ where $f^{'}$ is the jump of f. There are two reasons why we use $f^{'}$ to determine the elements of the sequence. One reason is that $d_{i}$ and $d_{i + 1}$ must be very far apart from each other. For any fixed k, it must be the case $f^{k} (d_{i}) < d_{i + 1}$ when i is large. If this is not the case, we will not be able to force the sequence $q_{0}, q_{1}, q_{2}, \dots$ to converge to a desired limit, that is, a limit whose base-a expansion is not elementary in f. When $d_{i + 1} = f^{'} (d_{i})$ , the distance between $d_{i}$ and $d_{i + 1}$ will be big enough. Another reason is that $f^{'}$ has elementary graph ( $f^{'}$ is honest since f is honest, and thus the graph of $f^{'}$ is elementary, see Lemma 4.7). This entails that we given x elementarily can decide if there is i such that $d_{i} = x$ . This will help us to pick $q_{0}, q_{1}, q_{2}, \dots$ such that the base-b expansion of the limit becomes elementary.

Now we are ready to explain the definition of $q_{0}, q_{1}, q_{2}, \dots$ . The first element in the sequence $q_{0}$ is some suitable rational that has finite base-a expansion and infinite base-b expansion. In order to avoid confusing and annoying indexes, every second element of the sequence is just a copy of the preceding one, more precisely, $q_{2 i + 1}$ equals $q_{2 i}$ for all $i \in N$ . Thus, $q_{2}, q_{4}, q_{6}, \dots$ are the essential elements of the sequence. For any $i \in N$ , we determine the value of $q_{2 i + 2}$ by the following scheme:

Step 1. Pick a real number γ whose base-a expansion is elementary in f.

Comments to step 1. The number i tells us how to pick γ, more precisely, the number i yields a computable index that tells us how to compute the function $E_{a}^{γ}$ . If the base-a expansion of a real is elementary in f, we will eventually come across an i that tells us to pick that real (we will indeed encounter infinitely many such i’s).

Step 2. Compute the rational number $q_{γ}$ such that $\begin{matrix} q_{γ} = \sum_{j = 0}^{d_{2 i + 1}} E_{a}^{γ} (j) . \end{matrix}$

Comments to step 2. The rational number $q_{γ}$ lies close to γ (it lies slightly below). In the next step, we use $q_{γ}$ to force the sequence $q_{0}, q_{1}, q_{2}, \dots$ to converge to something else than γ.

Step 3. Let $\begin{array}{l} (†) & q_{2 i + 2} = \{\begin{matrix} q_{2 i + 1} - ϵ_{0} & if q_{γ} ⩾ q_{2 i + 1}, \\ q_{2 i + 1} + ϵ_{1} & if q_{γ} < q_{2 i + 1}, \end{matrix} \end{array}$ where $ϵ_{0}$ and $ϵ_{1}$ are suitable rational numbers.

Comments to step 3. The rationals $ϵ_{0}$ and $ϵ_{1}$ are suitable when

$ϵ_{0}$ and $ϵ_{1}$ are so small that the first $d_{2 i + 2}$ digits of the base-b expansion of $q_{2 i + 2}$ coincide with the first $d_{2 i + 2}$ digits of the base-b expansion of $q_{2 i + 1}$ (and thus with the first $d_{2 i + 2}$ digits of the base-b expansion of $q_{2 i}$ ). This will ensure that the sequence converges. Moreover, the first $d_{2 i + 2}$ digits of the base-b expansion of $q_{2 i}$ will coincide with the first $d_{2 i + 2}$ digits of the base-b expansion of the sequence’s limit.

$ϵ_{0}$ guarantees that ${lim}_{i \to \infty} q_{i} < γ$ .

$ϵ_{1}$ guarantees that ${lim}_{i \to \infty} q_{i} > γ$ .

$ϵ_{0}$ and $ϵ_{1}$ ensure that $q_{2 i + 2}$ has a finite base-a expansion and infinite base-b expansion. It is essential that all the rationals $q_{0}, q_{1}, q_{2} \dots$ have finite base-a expansions and infinite base-b expansions. When we set $q_{2 i + 2}$ to something smaller than $q_{2 i + 1}$ , we need a huge initial segment of the base-b expansion of that something smaller to coincide with a huge initial segment of the base-b expansion of $q_{2 i + 1}$ . That would not be possible if the base-b expansion of $q_{2 i + 1}$ were finite (e.g., the first digit of the base-10 expansion of $10^{- 1}$ is different from the first digit of the base-10 expansion of $10^{- 1} - ϵ$ for any small $ϵ > 0$ ). Moreover, we have to determine if γ is above or below $q_{2 i + 1}$ by examine a bounded segment of the base-a expansion of γ. That would not be possible if the base-a expansion of $q_{2 i + 1}$ were infinite.

So far we have explained why the base-a expansion of the limit of $q_{0}, q_{1}, q_{2}, \dots$ is not elementary in f. We have not yet explained why the base-b expansion of this limit is elementary. Well, this is the reason: Recall that we used a function with elementary graph to define the sequence $d_{0}, d_{1}, d_{2}, \dots$ . This entails that we given n easily can find i such that $d_{i} ⩽ n < d_{i + 1}$ . It is easy in the sense that i can be computed elementarily in n. Now, i is very small compared to n. Thus, we can compute $q_{i}$ elementarily in n. We cannot compute $q_{i}$ elementarily in i, but we can do it elementarily in n since n is very much bigger than i. Finally, when $q_{i}$ is available, we can elementarily compute the nth digit of the base-b expansion $q_{i}$ . But then we have elementarily computed the nth digit of the base-b expansion of α as the nth digit of the base-b expansion of α is the same as nth digit of the base-b expansion of $q_{i}$ .

This concludes our intuitive explanation of the proof of Theorem 5.3.
Theorem 5.3.
Let a and b be bases such that $prim (a) ⊈ prim (b)$ , and let f be any honest function. There exists an irrational number α such that (i) $E_{b}^{α}$ is elementary, and (ii) $E_{a}^{α} ≰_{E} f$ .
Proof.
Let $p \in prim (a) ∖ prim (b)$ . We define the sequence of natural numbers $d_{0}, d_{1}, d_{2}, \dots$ by $d_{0} = max (p, b)$ and $d_{i + 1} = f^{'} (d_{i})$ where $f^{'}$ is the jump of f.

Recall that $U$ and $T_{1}$ are the elementary function and the elementary predicate from Theorem 4.5, furthermore, $digit$ is the elementary function given by Lemma 4.1. We define the sequence of rational numbers $q_{0}, q_{1}, q_{2}, \dots$ by $q_{0} = p^{- 1}$ and $q_{2 i + 1} = q_{2 i}$ and $\begin{array}{l} (†) & q_{2 i + 2} = \{\begin{matrix} q_{2 i + 1} - p^{- b k} & if U (μ t ⩽ d_{2 i + 2} [T_{1} ({(i)}_{1}, d_{2 i + 1}, t)]) ⩾ q_{2 i + 1}, \\ q_{2 i + 1} + p^{- b ℓ} & otherwise, \end{matrix} \end{array}$ where
k is the least natural number greater than or equal to $d_{2 i + 2}$ such that ${digit}_{k} (q_{2 i + 1}, b) \neq 0$ ,

ℓ is the least natural number greater than or equal to $d_{2 i + 2}$ such that ${digit}_{ℓ} (q_{2 i + 1}, b) \neq \overline{0}$ .
Let $α = {lim}_{n \to \infty} q_{n}$ . Claim I.
For any $i \in N$ , there exists $m \in N$ such that $q_{2 i} = m p^{- d_{2 i + 1}}$ .

We prove Claim I by induction on i. It is easy to see that the claim holds when $i = 0$ . Assume by induction hypothesis that we have $\hat{m}$ such that $q_{2 i} = \hat{m} p^{- d_{2 i + 1}}$ (we will prove that there is m such that $q_{2 i + 2} = m p^{- d_{2 i + 3}}$ ).

We can w.l.o.g. assume that $q_{2 i + 2} = q_{2 i + 1} - p^{- b k}$ (the case when $q_{2 i + 2} = q_{2 i + 1} + p^{- b ℓ}$ is similar). Now, k is the least natural number greater than or equal to $d_{2 i + 2}$ such that ${digit}_{k} (q_{2 i + 1}, b) \neq 0$ . We need to find an upper bound for k.

By our induction hypothesis and the definition of $q_{2 i + 1}$ we have $q_{2 i + 1} = q_{2 i} = \hat{m} p^{- d_{2 i + 1}}$ where $p \in prim (a) ∖ prim (b)$ . Thus, the base-b expansion of $q_{2 i}$ is infinite by Lemma 3.5. Since $q_{2 i}$ is rational, its base-b expansion will be of the form $\begin{matrix} {(0 . D_{1} D_{2} \dots D_{j} {(D_{j + 1} \dots D_{s})}^{ω})}_{b}, \end{matrix}$ where $j < s$ and at least one of the digits in the sequence $D_{j + 1} \dots D_{s}$ will be different from 0 (if they all were zeros, the base b expansion $q_{2 i}$ would be finite). Now, $q_{2 i} = \hat{m} p^{- d_{2 i + 1}}$ where $\hat{m}$ and $p^{d_{2 i + 1}}$ are natural numbers. Thus, we have $s < p^{d_{2 i + 1}}$ . Hence, we have $k < d_{2 i + 2} + p^{d_{2 i + 1}}$ .

Now, since f is an honest function and $d_{j} ⩾ max (p, b) ⩾ 2$ (for any $j \in N$ ), we have $\begin{array}{l} b k & < b (d_{2 i + 2} + p^{d_{2 i + 1}}) ⩽ b (d_{2 i + 2} + 2^{⌈ {log}_{2} p ⌉ d_{2 i + 1}}) ⩽ b (d_{2 i + 2} + f (⌈ {log}_{2} p ⌉ d_{2 i + 1})) \\ ⩽ b (d_{2 i + 2} + f f (d_{2 i + 1})) < b (d_{2 i + 2} + f^{'} (d_{2 i + 1})) = b (d_{2 i + 2} + d_{2 i + 2}) < f^{'} (d_{2 i + 2}) = d_{2 i + 3} . \end{array}$ This proves that $d_{2 i + 3}$ is greater than $b k$ . Now it is easy to see that there exists $m \in N$ such that $\begin{matrix} q_{2 i + 2} = q_{2 i} - p^{- b k} = \hat{m} p^{- d_{2 i + 1}} - p^{- b k} = m p^{- d_{2 i + 3}} . \end{matrix}$ This completes the proof of Claim I. Claim II.
For any $j \in N$ , we have $\begin{matrix} q_{j + 1} > q_{j} \Rightarrow lim_{n \to \infty} q_{n} > q_{j} \end{matrix}$ and $\begin{matrix} q_{i + j} < q_{j} \Rightarrow lim_{n \to \infty} q_{n} < q_{j} . \end{matrix}$

For each i we have $m_{1}, \dots, m_{i} \in {- 1, 1}$ and a very fast increasing sequence of natural numbers $k_{1}, k_{2}, \dots, k_{i}$ such that $\begin{matrix} q_{2 i} = q_{2 i + 1} = p^{- 1} + m_{1} p^{- b k_{1}} + m_{2} p^{- b k_{2}} + \dots + m_{i} p^{- b k_{i}} . \end{matrix}$ Thus, it is easy to see that Claim II holds.

We are now prepared to prove clause (ii) of the theorem. Let $α_{n}$ denote the sum $\sum_{i = 0}^{n} E_{a}^{α} (n) a^{- n}$ . Then, we have $\begin{array}{l} (*) & lim_{n \to \infty} q_{n} = α = lim_{n \to \infty} α_{n} . \end{array}$

Assume for the sake of a contradiction that $E_{a}^{α} ⩽_{E} f$ . Thus, $α_{n} ⩽_{E} f$ (view $α_{n}$ as a function of n). By Theorem 4.5, we have $e, k \in N$ such that $\begin{matrix} α_{n} = U (μ t ⩽ f^{k} (n) [T_{1} (e, n, t)]) . \end{matrix}$ Pick i, j such that $i = ⟨ e, j ⟩$ and $d_{2 i + 1} ⩾ k$ (there are infinitely many such i and j) and recall that $f^{'} (x) = f^{x + 1} (x)$ . Then, we have $\begin{array}{l} α_{d_{2 i + 1}} & = U (μ t ⩽ f^{k} (d_{2 i + 1}) [T_{1} (e, d_{2 i + 1}, t)]) = U (μ t ⩽ f^{k} (d_{2 i + 1}) [T_{1} ({(i)}_{1}, d_{2 i + 1}, t)]) \\ (**) & = U (μ t ⩽ f^{'} (d_{2 i + 1}) [T_{1} ({(i)}_{1}, d_{2 i + 1}, t)]) = U (μ t ⩽ d_{2 i + 2} [T_{1} ({(i)}_{1}, d_{2 i + 1}, t)]) . \end{array}$

Now our proof splits into the cases $α_{d_{2 i + 1}} ⩾ q_{2 i + 1}$ and $α_{d_{2 i + 1}} < q_{2 i + 1}$ . In both cases we will deduce a contradiction. Thus, we can conclude that $E_{a}^{α}$ is not elementary in f.

The case $α_{d_{2 i + 1}} ⩾ q_{2 i + 1}$ . By (**) and (†), we have $α_{d_{2 i + 1}} ⩾ q_{2 i + 1} > q_{2 i + 2}$ . By Claim II, we have $q_{2 i + 1} > {lim}_{n \to \infty} q_{n}$ . Since $α_{0}, α_{1}, α_{2}, \dots$ is an increasing sequence, we have $\begin{matrix} lim_{n \to \infty} α_{n} ⩾ α_{d_{2 i + 1}} ⩾ q_{2 i + 1} > lim_{n \to \infty} q_{n} . \end{matrix}$ This contradicts ().

The case* $α_{d_{2 i + 1}} < q_{2 i + 1}$ . By the definition of $q_{2 i + 1}$ and Claim I, we have $q_{2 i + 1} = q_{2 i} = m p^{- d_{2 i + 1}}$ for some $m \in N$ . Since $p \in prim (a)$ , we also have $q_{2 i + 1} = m_{0} a^{- d_{2 i + 1}}$ for some $m_{0} \in N$ . Furthermore, it is easy to see that we have $α_{d_{2 i + 1}} = m_{1} a^{- d_{2 i + 1}}$ for some $m_{1} \in N$ . Thus, as $α_{d_{2 i + 1}} < q_{2 i + 1}$ , we have $q_{2 i + 1} - α_{d_{2 i + 1}} ⩾ a^{- d_{2 i + 1}}$ . Since $α_{0}, α_{1}, α_{2}, \dots$ converges to an irrational number, we conclude that ${lim}_{n \to \infty} α_{n} < q_{2 i + 1}$ . By (**) and (†), we have $q_{2 i + 1} < q_{2 i + 2}$ . By Claim II, we have $q_{2 i + 1} < {lim}_{n \to \infty} q_{n}$ . Hence, ${lim}_{n \to \infty} α_{n} < {lim}_{n \to \infty} q_{n}$ , and this contradicts ().

This concludes the proof of clause (ii) of the theorem. It remains to prove that clause (i) also holds. To this end we need the next claim. Claim III.
Let* ${(0 . D_{1} D_{2} \dots)}_{b}$ be the base-b expansion of $q_{2 i}$ . Then, for any natural number j, we have $\begin{matrix} 1 ⩽ j < d_{2 i + 2} \Rightarrow {(0 . D_{1} D_{2} D_{3} \dots D_{j})}_{b} < q_{2 i + 2} < {(0 . D_{1} D_{2} D_{3} \dots D_{j})}_{b} + b^{- j} . \end{matrix}$

By Claim I and Lemma 3.5, $q_{2 i}$ has an infinite base b expansion. Thus, we have $\begin{matrix} {(0 . D_{1} D_{2} D_{3} \dots D_{s})}_{b} < q_{2 i} < {(0 . D_{1} D_{2} D_{3} \dots D_{s})}_{b} + b^{- s} \end{matrix}$ for any $s ⩾ 1$ . We may w.l.o.g. assume that $q_{2 i + 2} = q_{2 i} - p^{- b k}$ where k is the least natural number k such that $k ⩾ d_{2 i + 2}$ and $D_{k} \neq 0$ (the proof when $q_{2 i + 2} = q_{2 i} + p^{- b ℓ}$ is symmetric). Now, $p^{b k} = {(p^{b})}^{k} > b^{k}$ . Hence $\begin{matrix} q_{2 i + 2} = q_{2 i + 1} - p^{- b k} = q_{2 i} - p^{- b k} > q_{2 i} - b^{- k} . \end{matrix}$ Now, since $D_{k} \neq 0$ , we have $\begin{matrix} {(0 . D_{1} D_{2} D_{3} \dots D_{k - 1})}_{b} < q_{2 i + 2} < q_{2 i} < {(0 . D_{1} D_{2} D_{3} \dots D_{k - 1})}_{b} + b^{- (k - 1)} . \end{matrix}$ As $k ⩾ d_{2 i + 2}$ , we have $\begin{matrix} {(0 . D_{1} D_{2} D_{3} \dots D_{j})}_{b} < q_{2 i + 2} < {(0 . D_{1} D_{2} D_{3} \dots D_{j})}_{b} + b^{- j} \end{matrix}$ when $1 ⩽ j < d_{2 i + 2}$ . This completes the proof of the Claim III.

The next claim follows easily from Claim III. We have $α = {lim}_{i \to \infty} q_{i}$ , and then, by Claim III, the first $d_{2 i + 2}$ digits of the base-b expansion of α will coincide with the first $d_{2 i + 2}$ digits of the base-b expansion of $q_{2 i}$ . Hence, Claim IV holds. Claim IV.
Let $d_{i} ⩽ n < d_{i + 1}$ . Then, the nth digit of the base-b expansion of α is the same as the nth digit of the base-b expansion of $q_{i}$ , that is $E_{b}^{α} (n) = {digit}_{n} (q_{i}, b)$ .

We are now ready to prove clause (i) of our theorem. We have $d_{i + 1} = f^{'} (d_{i})$ . The function $f^{'}$ is the jump of f, and $f^{'}$ is honest when f is, see Lemma 4.7. It follows that $d_{z} = y$ is an elementary relation. Let $\begin{matrix} ψ (i, n) = \{\begin{matrix} d_{i} & if d_{i} ⩽ n, \\ n & otherwise. \end{matrix} \end{matrix}$ It is not hard to see that ψ is an elementary function when we know that the relation $d_{z} = y$ is elementary. We will now define the function $ϕ (i, n)$ by course-of-values recursion on i. Let $ϕ (0, n) = p^{- 1}$ , let $ϕ (2 i + 1, n) = ϕ (2 i, n)$ , and let $\begin{matrix} ϕ (2 i + 2, n) = \{\begin{matrix} ϕ (2 i + 1, n) - p^{- b k} & if U (μ t ⩽ ψ (2 i + 2, n) [T_{1} ({(i)}_{1}, ψ (2 i + 1, n), t)]) ⩾ ϕ (2 i + 1, n), \\ ϕ (2 i + 1, n) + p^{- b ℓ} & otherwise, \end{matrix} \end{matrix}$ where
k is the least natural number greater than or equal to $d_{2 i + 2}$ such that ${digit}_{k} (q_{2 i + 1}, b) \neq 0$ ,

ℓ is the least natural number greater than or equal to $d_{2 i + 2}$ such that ${digit}_{ℓ} (q_{2 i + 1}, b) \neq \overline{0}$ .
We observe that ϕ is defined by course-of-values recursion over elementary functions. More careful, but very tedious, considerations will show that this course-of-values recursion over elementary functions can be reduced to bounded primitive recursion over elementary functions. Thus, as the elementary functions are closed under bounded primitive recursion, ϕ is an elementary function.

It follows straightforwardly from the definition of the sequence $q_{0}, q_{1}, q_{2}, \dots$ that we have $ϕ (i, n) = q_{i}$ when $d_{i} ⩽ n$ . We can compute the i such that $d_{i} ⩽ n < d_{i + 1}$ elementarily in n. Thereafter, we can compute $q_{i}$ elementarily by computing $ϕ (i, n)$ . By Claim IV we have $E_{b}^{α} (n) = {digit}_{n} (q_{i}, b)$ , and the function $digit$ is elementary. This proves that the function $E_{b}^{α}$ is elementary. □

An anonymous referee has remarked that Theorem 5.3 can be strengthen. Minor modifications of the proof given above will yield a small polynomial $p (n)$ such that we have: For any time constructible function $t (n)$ there exists α such that (i) $E_{b}^{α}$ is computable by a Turing machine working in time $O (p (n))$ and (ii) $E_{a}^{α}$ is not computable by a Turing machine working in time $O (t (n))$ (where n denotes the length of the input). The referee claims that the polynomial $p (n)$ may be as small as $n^{2}$ . It should also be possible to strengthen several other results proved in this paper along the same lines. However, a fine-grained complexity analysis of algorithms and constructions is beyond the scope of this paper.
Corollary 5.4.
Let $S$ be any subrecursive class which is closed under elementary operations. For any bases a and b, we have $\begin{matrix} prim (a) \subseteq prim (b) \Leftrightarrow S_{b E} \subseteq S_{a E} . \end{matrix}$
Proof.
Assume $prim (a) \subseteq prim (b)$ . Let $α \in S_{b E}$ . Thus, $E_{b}^{α}$ is in $S$ . By Theorem 5.2, $E_{a}^{α}$ will also be in $S$ . Thus, $α \in S_{a E}$ . Thus, $S_{b E} \subseteq S_{a E}$ .

Assume $prim (a) ⊈ prim (b)$ . Let f be an honest function such that $ψ ≰_{E} f$ implies $ψ \notin S$ . Such an f exists by Theorem 4.10. By Theorem 5.3, we have α such that $E_{b}^{α}$ is elementary and $E_{a}^{α} ≰_{E} f$ . Thus, $E_{b}^{α}$ is in $S$ whereas $E_{a}^{α}$ is not. This shows that $S_{b E} ⊈ S_{a E}$ . □

Mostowski [14] proves (a theorem obviously equivalent to) the left-right implication of Corollary 5.4 and poses the right-left implication as an open problem (Mostowski’s $S$ is the class of primitive recursive functions).

Some of the results in Weihrauch [20] seem to be connected to the results proved above. Weihrauch proves that $prim (a) \subseteq prim (b)$ if and only if a base-b representation of a real can be continuously translated to a base-a representation of the same real, see Corollary 9 in [20].
6. Base-b expansions, Cauchy sequences and Dedekind cuts

Definition 6.1.
A function $C : N \to Q$ is a Cauchy sequence for the real number α when $\begin{matrix} | α - C (n) | < \frac{1}{2^{n}} . \end{matrix}$ A function $D : Q \to {0, 1}$ is the Dedekind cut of the real number α when $D (q) = 0$ iff $q < α$ .

For any class of functions $S$ , let $S_{C}$ denote the set of irrational numbers (between 0 and 1) that have Cauchy sequences in $S$ ; let $S_{D}$ denote the set of irrational numbers (between 0 and 1) that have Dedekind cuts in $S$ .

Let $S$ be a sufficiently large and natural subrecursive class. If ${(0 . D_{1} D_{2} \dots)}_{b}$ is the base-b expansion of the irrational number α, then C where $\begin{matrix} C (n) = \sum_{i = 0}^{n + 1} E_{b}^{α} (i) \end{matrix}$ is a Cauchy sequence for α. Thus, we have a Cauchy sequence for α in $S$ if the base-b expansion of α is in $S$ , and the inclusion $S_{b E} \subseteq S_{C}$ holds for any base b. It is also easy to see that the inclusion $S_{D} \subseteq S_{b E}$ holds for any base b. Assume that the Dedekind cut of α is in $S$ . Then, the base-b expansion ${(0 . D_{1} D_{2} \dots)}_{b}$ of α will also be in $S$ because we can compute $D_{n + 1}$ by the following procedure: First we compute ${(0 . D_{1} \dots D_{n})}_{b}$ . Then, we use ${(0 . D_{1} \dots D_{n})}_{b}$ and the Dedekind cut of α to determine $D_{n + 1}$ by searching for a base-b digit $X$ such that $\begin{matrix} {(0 . D_{1} \dots D_{n} X)}_{b} < α < {(0 . D_{1} \dots D_{n} X)}_{b} + b^{- (n + 1)} . \end{matrix}$ No unbounded search is required. Thus, the base-b expansion of α is in $S$ if the Dedekind cut of α is in $S$ , and we have $S_{D} \subseteq S_{b E}$ .

Let b be an arbitrary base. Pick a base a such that $prim (a) ⊈ prim (b)$ and $prim (b) ⊈ prim (a)$ . By Corollary 5.4, we have $S_{b E} ⊈ S_{a E}$ and $S_{a E} ⊈ S_{b E}$ . So, $S_{b E}$ and $S_{a E}$ are incomparable sets, and by the considerations above both of them are subsets of $S_{C}$ and supersets of $S_{D}$ , that is, $S_{D} \subseteq S_{b E} \subseteq S_{C}$ and $S_{D} \subseteq S_{a E} \subseteq S_{C}$ . This implies that we have $\begin{array}{l} () & S_{D} \subset S_{b E} \subset S_{C} \end{array}$ for any base b. More careful considerations will show that () holds for any $S$ which is closed under elementary operations.

Kristiansen [8] proves the inclusion $S_{D} \subset S_{C}$ by a direct diagonalization argument, that is, without considering base-b expansions and the class $S_{b E}$ . Specker [19] was the first to prove that we have $S_{D} \subset S_{C}$ for a subrecursive class $S$ (Specker’s $S$ is the class of primitive recursive functions). He proves (*) with $b = 10$ by constructing α such that $α \in S_{10 E}$ and $3 \times α \notin S_{10 E}$ . Thus, $S_{10 E}$ is not closed under multiplication by natural numbers, but it is rather obvious that both $S_{D}$ and $S_{C}$ are. Hence, $S_{10 E}$ is different from both $S_{D}$ and $S_{C}$ . Since $S_{10 E}$ is a subset of $S_{C}$ and superset of $S_{D}$ , it follows that $S_{10 E}$ is a strict subset of $S_{C}$ and strict superset of $S_{D}$ .
7. Sum approximations

Sum approximations from below and above are explained in Section 1. We will now give our formal definitions.

Definition 7.1.
Let ${(0 . D_{1} D_{2} \dots)}_{b}$ be the base-b expansion of an irrational number α. The base-b sum approximation from below of α is the function ${\hat{A}}_{b}^{α} : N \to Q$ defined by ${\hat{A}}_{b}^{α} (0) = 0$ and ${\hat{A}}_{b}^{α} (n + 1) = E_{b}^{α} (m) b^{- m}$ where m is the least m such that $\begin{matrix} \sum_{i = 0}^{n} {\hat{A}}_{b}^{α} (i) < {(0 . D_{1} \dots D_{m})}_{b} . \end{matrix}$ The base-b sum approximation from above of α is the function ${\overset{ˇ}{A}}_{b}^{α} : N \to Q$ defined by ${\overset{ˇ}{A}}_{b}^{α} (0) = 0$ and ${\overset{ˇ}{A}}_{b}^{α} (n + 1) = \overline{E_{b}^{α} (m)} b^{- m}$ where m is the least m such that $\begin{matrix} 1 - \sum_{i = 0}^{n} {\overset{ˇ}{A}}_{b}^{α} (n) > 1 - {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{m})}_{b} \end{matrix}$ (recall that $\overline{D}$ is the complement digit of $D$ ).

For any class of functions $S$ , let $S_{b ↑} = {α ∣ {\hat{A}}_{b}^{α} \in S}$ and $S_{b ↓} = {α ∣ {\overset{ˇ}{A}}_{b}^{α} \in S}$ .

The functions ${\hat{A}}_{b}^{α}$ and ${\overset{ˇ}{A}}_{b}^{α}$ are not defined if α is rational. When we use the notation it is understood that α is irrational.
Lemma 7.2.
Let ${(0 . D_{1} D_{2} \dots)}_{b}$ be the base-b expansion of the irrational number α. For any $n \in N$ , there exist $k, ℓ ⩽ n$ such that $\begin{array}{l} () & \sum_{i = 0}^{k} {\hat{A}}_{b}^{α} (i) = {(0 . D_{1} \dots D_{n})}_{b} and \sum_{i = 0}^{ℓ} {\overset{ˇ}{A}}_{b}^{α} (i) = {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{n})}_{b} . \end{array}$
Proof.
We prove () by induction on n. We have ${(0 .)}_{b} = 0$ and ${\hat{A}}_{b}^{α} (0) = {\overset{ˇ}{A}}_{b}^{α} (0) = 0$ . Thus, () holds with $k = ℓ = 0$ when $n = 0$ .

Assume that () holds for n (we prove that () holds with $n + 1$ for n). Consider ${(0 . D_{1} \dots D_{n} D_{n + 1})}_{b}$ . Now, $D_{n + 1}$ might be the digit 0, and $D_{n + 1}$ might be the digit $\overline{0}$ , and $D_{n + 1}$ might be neither 0 nor $\overline{0}$ . We split the proof into three cases.

The case when* $D_{n + 1} = 0$ . We have $\begin{array}{l} (†) & 1 - \sum_{i = 0}^{ℓ} {\overset{ˇ}{A}}_{b}^{α} (i) = 1 - {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{n})}_{b} > 1 - {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{n} {\overline{D}}_{n + 1})}_{b} . \end{array}$ Thus, by the definition of ${\overset{ˇ}{A}}_{b}^{α} (ℓ + 1)$ , we have $\begin{matrix} \sum_{i = 0}^{ℓ + 1} {\overset{ˇ}{A}}_{b}^{α} (i) = \sum_{i = 0}^{ℓ} {\overset{ˇ}{A}}_{b}^{α} (i) + {\overset{ˇ}{A}}_{b}^{α} (ℓ + 1) = {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{n})}_{b} + {\overline{D}}_{n + 1} b^{- (n + 1)} = {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{n + 1})}_{b} . \end{matrix}$ Furthermore, we have $\begin{matrix} \sum_{i = 0}^{k} {\hat{A}}_{b}^{α} (i) = {(0 . D_{1} \dots D_{n})}_{b} = {(0 . D_{1} \dots D_{n} D_{n + 1})}_{b} . \end{matrix}$ Thus, () holds with $n + 1$ for n.

The case when* $D_{n + 1} = \overline{0}$ . Now we have $\begin{array}{l} (‡) & \sum_{i = 0}^{k} {\hat{A}}_{b}^{α} (i) < {(0 . D_{1} \dots D_{n} D_{n + 1})}_{b} . \end{array}$ By the definition of ${\hat{A}}_{b}^{α} (k + 1)$ , we have $\begin{matrix} \sum_{i = 0}^{k + 1} {\hat{A}}_{b}^{α} (i) = \sum_{i = 0}^{k} {\hat{A}}_{b}^{α} (i) + {\hat{A}}_{b}^{α} (k + 1) = {(0 . D_{1} \dots D_{n})}_{b} + D_{n + 1} b^{- (n + 1)} = {(0 . D_{1} \dots D_{n + 1})}_{b} . \end{matrix}$ Furthermore, since the complement digit of $\overline{0}$ is the digit 0, we have $\begin{matrix} \sum_{i = 0}^{ℓ} {\overset{ˇ}{A}}_{b}^{α} (i) = {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{n})}_{b} = {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{n} {\overline{D}}_{n + 1})}_{b} . \end{matrix}$ Thus, () holds with $n + 1$ for n.

The case when* $D_{n + 1} \neq 0$ and $D_{n + 1} \neq \overline{0}$ . In this case both (†) and (‡) hold, and we get $\begin{matrix} \sum_{i = 0}^{k + 1} {\hat{A}}_{b}^{α} (i) = {(0 . D_{1} \dots D_{n + 1})}_{b} and \sum_{i = 0}^{ℓ + 1} {\overset{ˇ}{A}}_{b}^{α} (i) = {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{n + 1})}_{b} . \end{matrix}$ □
Theorem 7.3.
For any irrational number α and any base b, we have $\begin{matrix} \sum_{i = 0}^{\infty} E_{b}^{α} (i) b^{- i} = \sum_{i = 0}^{\infty} {\hat{A}}_{b}^{α} (i) = 1 - \sum_{i = 0}^{\infty} {\overset{ˇ}{A}}_{b}^{α} (i) . \end{matrix}$
Proof.
The first equality follows straightforwardly from Lemma 7.2. It also follows from Lemma 7.2 that $\begin{matrix} \sum_{i = 0}^{\infty} {\hat{A}}_{b}^{α} (i) + \sum_{i = 0}^{\infty} {\overset{ˇ}{A}}_{b}^{α} (i) = 1 \end{matrix}$ and thus the second equality holds. □
Lemma 7.4.
(i) Let α be an irrational number, and let $p (x)$ be a polynomial such that $\begin{matrix} \exists i [x ⩽ i ⩽ p (x) \land E_{b}^{α} (i) \neq 0] \end{matrix}$ for all $x \in N$ . Then, ${\hat{A}}_{b}^{α} ⩽_{E} E_{b}^{α}$ . (ii) Let α be an irrational number and let $p (x)$ be a polynomial such that $\begin{matrix} \exists i [x ⩽ i ⩽ p (x) \land E_{b}^{α} (i) \neq \overline{0}] \end{matrix}$ for all $x \in N$ . Then, ${\overset{ˇ}{A}}_{b}^{α} ⩽_{E} E_{b}^{α}$ .
Proof.
We prove (i). Assume ${\hat{A}}_{b}^{α} (n) = D b^{- m}$ where $D$ is some nonzero base-b digit. We know that ${\hat{E}}_{b}^{α} (i) \neq 0$ for some i between $m + 1$ and $p (m + 1)$ . Hence, we can compute ${\hat{A}}_{b}^{α} (n + 1)$ from the rational number $\sum_{i = 1}^{p (m + 1)} E_{b}^{α} (i) b^{- i}$ . Such a computation of ${\hat{A}}_{b}^{α} (n + 1)$ requires one application of primitive recursion, but more careful considerations will show that this application of primitive recursion can be reduced to bounded primitive recursion. The set of functions elementary in ${\hat{E}}_{b}^{α}$ is closed under bounded primitive recursion. Hence, ${\hat{A}}_{b}^{α} ⩽_{E} {\hat{E}}_{b}^{α}$ . The proof of (ii) is similar. □
Lemma 7.5.
Let f be an honest function, and let $f^{'}$ be the jump of f. (i) Let α be an irrational number such that we have $\begin{matrix} \forall i [x ⩽ i < f^{'} (x) \to E_{b}^{α} (i) = 0] \end{matrix}$ for infinitely many $x \in N$ . Then, ${\hat{A}}_{b}^{α} ≰_{E} f$ . (ii) Let α be an irrational number such that we have $\begin{matrix} \forall i [x ⩽ i < f^{'} (x) \to E_{b}^{α} (i) = \overline{0}] \end{matrix}$ for infinitely many $x \in N$ . Then, ${\overset{ˇ}{A}}_{b}^{α} ≰_{E} f$ .
Proof.
We prove (i). Let x be such that we have $E_{b}^{α} (i) = 0$ when $x ⩽ i < f^{'} (x)$ (there are infinitely many such x). Then there exists $m < x$ such that ${\hat{A}}_{b}^{α} (m + 1) ⩽ (b - 1) b^{- f^{'} (x)}$ . Let $ψ (z) = y$ if ${\hat{A}}_{b}^{α} (z + 1) = m_{0} b^{- y}$ for some $m_{0}$ . Now, ψ is a total function. Moreover, $ψ ⩽_{E} {\hat{A}}_{b}^{α}$ . We have $ψ (m) ⩾ f^{'} (x)$ for some $m < x$ . Since ψ is strictly increasing, we have $ψ (x) > f^{'} (x)$ . Thus, there are infinitely many x such that $ψ (x) > f^{'} (x)$ .

Assume for the sake of a contradiction that ${\hat{A}}_{b}^{α} ⩽_{E} f$ . Then, $ψ ⩽_{E} f$ . This contradicts Lemma 4.8. Thus we conclude that ${\hat{A}}_{b}^{α} ≰_{E} f$ . This completes the proof of (i). The proof of (ii) is symmetric. □
Theorem 7.6.
For any honest function f there exist irrational numbers α and β such that such that (i) ${\overset{ˇ}{A}}_{b}^{α}$ is elementary and ${\hat{A}}_{b}^{α} ≰_{E} f$ , and (ii) ${\hat{A}}_{b}^{β}$ is elementary and ${\overset{ˇ}{A}}_{b}^{β} ≰_{E} f$ . Moreover, (iii) α and β have elementary Dedekind cuts.
Proof.
We prove (i). Let $d_{0} = 0$ and $d_{i + 1} = f^{'} (d_{i})$ where $f^{'}$ is the jump of f. Let α be the irrational number given by the base-b expansion $\begin{matrix} E_{b}^{α} (x) = \{\begin{matrix} \overline{0} & if there exists i such that d_{i} = x, \\ 0 & otherwise. \end{matrix} \end{matrix}$ Since $f^{'}$ is honest, it is possible to check elementarily in x if there is i such that $d_{i} = x$ . Hence, $E_{b}^{α}$ is elementary. By Lemma 7.4(ii), ${\overset{ˇ}{A}}_{b}^{α}$ is elementary. By Lemma 7.5(i), we have ${\hat{A}}_{b}^{α} (n) ≰_{E} f$ . This proves (i). The proof of (ii) is symmetric: Use Lemma 7.4(i) in place of Lemma 7.4(ii), use Lemma 7.5(ii) in place of Lemma 7.5(i), and let $E_{b}^{β} (x) = 0$ if there exists i such that $d_{i} = x$ , otherwise, let $E_{b}^{β} (x) = \overline{0}$ .

The proof of (iii) is rather straightforward, and we omit the details. The reader that wants more details may consult the proof of Theorem 5.2 in Kristiansen [8]. □
Corollary 7.7.
Let $S$ be a subrecursive class closed under elementary operations. For any base b, we have $\begin{matrix} S_{b ↑} ⊈ S_{b ↓} and S_{b ↓} ⊈ S_{b ↑} . \end{matrix}$
Proof.
Pick an honest f such that ${\overset{ˇ}{A}}_{b}^{α} \in S$ implies ${\overset{ˇ}{A}}_{b}^{α} ⩽_{E} f$ . Such an f exists by Theorem 4.10. By Theorem 7.6(ii), we have α such that ${\hat{A}}_{b}^{α} \in S$ and ${\overset{ˇ}{A}}_{b}^{α} ≰ f$ . Thus, $S_{b ↑} ⊈ S_{b ↓}$ . A symmetric argument yields $S_{b ↓} ⊈ S_{b ↑}$ . Use clause (i) of Theorem 7.6 in place of clause (ii). □
Theorem 7.8.
We have $E_{b}^{α} ⩽_{E} {\hat{A}}_{b}^{α}$ and $E_{b}^{α} ⩽_{E} {\overset{ˇ}{A}}_{b}^{α}$ (for any irrational α between 0 and 1).
Proof.
Let ${(0 . D_{1} D_{2} \dots)}_{b}$ be the base-b expansion of α. It is trivial that we have $\sum_{i = 0}^{n} {\hat{A}}_{b}^{α} (i) = {(0 . D_{1} \dots D_{m})}_{b}$ for some $m ⩾ n$ . Let $digit$ be the elementary function given by Lemma 4.1. Then we have $\begin{matrix} E_{b}^{α} (n) = {digit}_{n} (\sum_{i = 0}^{n} {\hat{A}}_{b}^{α} (i), b) . \end{matrix}$ Thus, $E_{b}^{α} ⩽_{E} {\hat{A}}_{b}^{α}$ . Furthermore, by Lemma 7.2, we have $m ⩾ n$ such that $\begin{matrix} 1 - \sum_{i = 0}^{n + 1} {\overset{ˇ}{A}}_{b}^{α} (i) = 1 - {(0 . {\overline{D}}_{1} \dots {\overline{D}}_{m} {\overline{D}}_{m + 1})}_{b} = {(0 . D_{1} \dots D_{m} (D_{m + 1} + 1))}_{b} . \end{matrix}$ Thus, we have the equality $\begin{matrix} E_{b}^{α} (n) = {digit}_{n} (1 - \sum_{i = 0}^{n + 1} {\overset{ˇ}{A}}_{b}^{α} (i), b) \end{matrix}$ and we conclude that $E_{b}^{α} ⩽_{E} {\overset{ˇ}{A}}_{b}^{α}$ . □
Theorem 7.9.
Let $prim (a) \subseteq prim (b)$ . Then we have ${\hat{A}}_{a}^{α} ⩽_{PR} {\hat{A}}_{b}^{α}$ and ${\overset{ˇ}{A}}_{a}^{α} ⩽_{PR} {\overset{ˇ}{A}}_{b}^{α}$ (for any irrational α between 0 and 1).
Proof.
We prove that ${\hat{A}}_{a}^{α} ⩽_{PR} {\hat{A}}_{b}^{α}$ . Let ${(0 . D_{1} D_{2} \dots)}_{a}$ and ${(0 . {\dot{D}}_{1} {\dot{D}}_{2} \dots)}_{b}$ be, respectively, the base-a and base-b expansion of α.

Assume that we have computed ${\hat{A}}_{a}^{α} (0), \dots, {\hat{A}}_{a}^{α} (n)$ (the computation of ${\hat{A}}_{a}^{α} (0)$ is trivial). Then we can compute ${\hat{A}}_{a}^{α} (n + 1)$ by the following procedure:
Compute the least s such that $\begin{matrix} \sum_{i = 0}^{n} {\hat{A}}_{a}^{α} (i) = {(0 . D_{1}, \dots D_{s})}_{a} . \end{matrix}$

Use s and search for the least t such that ${(0 . D_{1} \dots D_{s})}_{a} < {(0 . D_{1} \dots D_{t})}_{a}$ , and then let ${\hat{A}}_{a}^{α} (n + 1) = D_{t} a^{- t}$ .

First we will argue that we can compute a certain bound for the search in the second step of the procedure. Let k be the base transition factor from a to b, and let ℓ be such that $\begin{matrix} \sum_{i = 0}^{k s + 1} {\hat{A}}_{b}^{α} (i) = {(M . {\dot{D}}_{1} \dots {\dot{D}}_{ℓ})}_{b} . \end{matrix}$ Obviously, there is a function ψ such that $ψ ⩽_{PR} {\hat{A}}_{b}^{α}$ and $ψ (s) = ℓ$ . It is also obvious that we have $\begin{matrix} {(M . {\dot{D}}_{1} \dots {\dot{D}}_{k s})}_{b} < {(M . {\dot{D}}_{1} \dots {\dot{D}}_{ℓ})}_{b} . \end{matrix}$ Then, by Corollary 3.4, we have $\begin{matrix} {(M . D_{1}, \dots D_{s})}_{a} < {(M . D_{1}, \dots D_{m l})}_{a}, \end{matrix}$ where $m = ⌈ {log}_{a} b ⌉$ . Thus, we have a bound for the number t computed in the second step of the procedure: $t ⩽ ⌈ {log}_{a} b ⌉ ℓ = ⌈ {log}_{a} b ⌉ ψ (s)$ . This bound is primitive recursive in ${\hat{A}}_{b}^{α}$ , and the unbounded search in the second step can be turned into a bounded search when we compute primitive recursively in ${\hat{A}}_{b}^{α}$ .

By Theorem 5.2, we have $E_{a}^{α} ⩽_{E} E_{b}^{α}$ . By Theorem 7.8, we have $E_{b}^{α} ⩽_{E} {\hat{A}}_{b}^{α}$ . By the transitivity of $⩽_{E}$ , we have $E_{a}^{α} ⩽_{E} {\hat{A}}_{b}^{α}$ , and thus, we also have $E_{a}^{α} ⩽_{PR} {\hat{A}}_{b}^{α}$ .

This proves that we for any n can compute ${(M . D_{1} \dots D_{n})}_{a}$ primitive recursively in ${\hat{A}}_{b}^{α}$ . Thus, it follows by the straightforward algorithm above that ${\hat{A}}_{a}^{α} ⩽_{PR} {\hat{A}}_{b}^{α}$ . The proof that ${\overset{ˇ}{A}}_{a}^{α} ⩽_{PR} {\overset{ˇ}{A}}_{b}^{α}$ is symmetric. □

It is an open problem if the previous theorem holds with $⩽_{E}$ for $⩽_{PR}$ . Theorem 7.10.
Let a and b be bases such that $prim (a) ⊈ prim (b)$ , and let f be any honest function. There exists an irrational number α such that (i) ${\hat{A}}_{b}^{α}$ and ${\overset{ˇ}{A}}_{b}^{α}$ are elementary, and (ii) ${\hat{A}}_{a}^{α} ≰_{PR} f$ and ${\overset{ˇ}{A}}_{a}^{α} ≰_{PR} f$ .
Proof.
Let f be any honest function. By Lemma 4.11, we have an honest function g such that $\begin{array}{l} () & ψ ≰_{E} g \Rightarrow ψ ≰_{PR} f \end{array}$ for all functions ψ. Let α be such that $E_{b}^{α}$ is elementary and $E_{a}^{α} ≰_{E} g$ . Such an α exists by Theorem 5.3. By (), we have $E_{a}^{α} ≰_{PR} f$ . By Theorem 7.8, we have ${\hat{A}}_{a}^{α} ≰_{PR} f$ and ${\overset{ˇ}{A}}_{a}^{α} ≰_{PR} f$ (if ${\hat{A}}_{a}^{α}$ or ${\overset{ˇ}{A}}_{a}^{α}$ were primitive recursive in f, then so would $E_{a}^{α}$ be). This proves (ii).

To prove that (i) holds, we have to study the construction of α in the proof of Theorem 5.3. We know that $E_{b}^{α}$ is elementary, and it is easy to see that the distance from one nonzero digit to the next nonzero digit in the base-b expansion of α is small. There will definitely be a polynomial $p (x)$ such that we have $\begin{matrix} \exists i [x ⩽ i ⩽ p (x) \land E_{b}^{α} (i) \neq 0] \end{matrix}$ for all $x \in N$ . Hence, by Lemma 7.4(i), we have ${\hat{A}}_{b}^{α} ⩽_{E} E_{b}^{α}$ , and then ${\hat{A}}_{b}^{α}$ is elementary since $E_{b}^{α}$ is elementary. The proof that ${\overset{ˇ}{A}}_{a}^{α}$ is elementary is similar. Use clause (ii) of Lemma 7.4 in place of clause (i). □
Corollary 7.11.
Let $S$ be a subrecursive class closed under primitive recursive operations. For any bases a and b, we have $\begin{matrix} prim (a) \subseteq prim (b) \Leftrightarrow S_{b ↑} \subseteq S_{a ↑} \Leftrightarrow S_{b ↓} \subseteq S_{a ↓} . \end{matrix}$
Proof.
Assume $prim (a) \subseteq prim (b)$ . Let $α \in S_{b ↑}$ . Thus, the function ${\hat{A}}_{b}^{α}$ is in $S$ . By Theorem 7.9, the function ${\hat{A}}_{a}^{α}$ is in $S$ . Thus, $α \in S_{a ↑}$ . Thus, $S_{b ↑} \subseteq S_{a ↑}$ .

Assume $prim (a) ⊈ prim (b)$ . Let f be an honest function such that $ψ ≰_{PR} f$ implies $ψ \notin S$ . Such an f exists by Theorem 4.10. By Theorem 7.10, we have α such that ${\hat{A}}_{b}^{α}$ is primitive recursive and ${\hat{A}}_{a}^{α} ≰_{PR} f$ . Thus, $S$ contains the function ${\hat{A}}_{b}^{α}$ but not the function ${\hat{A}}_{a}^{α}$ , and we can conclude that $S_{b ↑} ⊈ S_{a ↑}$ .

This proves that we have $prim (a) \subseteq prim (b)$ if and only if $S_{b ↑} \subseteq S_{a ↑}$ . A very similar argument will show that we have $prim (a) \subseteq prim (b)$ if and only if $S_{b ↓} \subseteq S_{a ↓}$ . □

8. Sum approximations and Dedekind cuts

Figure 1.

The relationship between Dedekind cuts, sum approximations from below and sum approximations from above.

The Venn diagram in Fig. 1 gives a complete description of the relationship between subrecursive Dedekind cuts and subrecursive sum approximations. The diagram was partly conjectured in Kristiansen [8]. Now we are able to prove that the diagram indeed is correct, that is, for any base b and any subrecursive class $S$ closed under elementary operations, we can prove that the following sets are nonempty:

$S_{b ↑} \cap S_{b ↓} \cap S_{D}$ ,

$(S_{b ↑} \cap S_{D}) ∖ S_{b ↓}$ ,

$(S_{b ↓} \cap S_{D}) ∖ S_{b ↑}$ ,

$(S_{b ↓} \cap S_{b ↑}) ∖ S_{D}$ ,

$S_{b ↑} ∖ (S_{b ↓} \cup S_{D})$ ,

$S_{b ↓} ∖ (S_{b ↑} \cup S_{D})$ ,

$S_{D} ∖ (S_{b ↑} \cup S_{b ↓})$ .

The set $S_{b ↑} \cap S_{b ↓} \cap S_{D}$ is nonempty. This is obvious. See Kristiansen [8] for more on what we find inside this set, e.g., every irrational whose continued fraction is in $S$ , will be in the set.

The sets $(S_{b ↑} \cap S_{D}) ∖ S_{b ↓}$ and $(S_{b ↓} \cap S_{D}) ∖ S_{b ↑}$ are nonempty. It follows from Theorem 7.6 that these sets are nonempty.

The set $(S_{b ↓} \cap S_{b ↑}) ∖ S_{D}$ is nonempty. Consider the irrational number α constructed by diagonalization in proof of Theorem 5.3. The function f that appears in the construction may be any honest function, and the base a that appears in the construction may be any a such that $prim (a) ⊈ prim (b)$ . Pick an f that grows sufficiently fast, and pick a such that $prim (a) ⊈ prim (b)$ . Then the construction guarantees that $E_{a}^{α}$ not in $S$ . It follows that the Dedekind cut of α is not in $S$ (if the Dedekind cut of α were in $S$ , then so would the base-a expansion be; see the discussion in Section 6).

The construction also guarantees that $E_{b}^{α}$ is elementary. Hence, $E_{b}^{α}$ is in $S$ . If we take a closer look at the construction, it is not hard to see that there will be a polynomial $p (x)$ such that we have $\begin{matrix} \exists i [x ⩽ i ⩽ p (x) \land E_{b}^{α} (i) \neq 0] and \exists i [x ⩽ i ⩽ p (x) \land E_{b}^{α} (i) \neq \overline{0}] \end{matrix}$ for all $x \in N$ . Thus, by Lemma 7.4, we have ${\hat{A}}_{b}^{α} ⩽_{E} E_{b}^{α}$ and ${\overset{ˇ}{A}}_{b}^{α} ⩽_{E} E_{b}^{α}$ , and we can conclude that ${\hat{A}}_{b}^{α}$ and ${\overset{ˇ}{A}}_{b}^{α}$ are in $S$ . Thus, both ${\hat{A}}_{b}^{α}$ and ${\overset{ˇ}{A}}_{b}^{α}$ are in $S$ , but the Dedekind cut of α is not, and thus, α is in the set $(S_{b ↓} \cap S_{b ↑}) ∖ S_{D}$ .

The sets $S_{b ↑} ∖ (S_{b ↓} \cup S_{D})$ and $S_{b ↓} ∖ (S_{b ↑} \cup S_{D})$ are nonempty. Again we will consider the construction of the irrational number α in the proof of Theorem 5.3. In the previous paragraph we saw that α will be in both $S_{b ↑}$ and $S_{b ↓}$ , but not in $S_{D}$ , if we base the construction on a suitable base a and a suitable honest function f. Now, α is in $S_{b ↑}$ since there is a polynomial $p (x)$ such that we have $\begin{array}{l} (†) & \exists i [x ⩽ i ⩽ p (x) \land E_{b}^{α} (i) \neq 0] \end{array}$ for all $x \in N$ , and α is in $S_{b ↓}$ since we also have $\begin{array}{l} (‡) & \exists i [x ⩽ i ⩽ p (x) \land E_{b}^{α} (i) \neq \overline{0}] \end{array}$ for all $x \in N$ .

It is possible to modify the construction of α such that the base-b expansion of α will contain infinitely many very long sequences the digit 0, more precisely, we construct α such that we have $\begin{array}{l} (*) & \forall i [x ⩽ i < f^{'} (x) \to E_{b}^{α} (i) = 0] \end{array}$ for infinitely many $x \in N$ . The diagonalization will still takes place and assure that α is not in $S_{D}$ , and (‡) will still hold and assure that α is in $S_{b ↓}$ , but (†) will not hold anymore. Instead (*) holds, and when (*) holds we have $α \notin S_{b ↑}$ by clause (i) of Lemma 7.5. Thus α is in the set $S_{b ↓} ∖ (S_{b ↑} \cup S_{D})$ .

A symmetric argument shows that set $S_{b ↑} ∖ (S_{b ↓} \cup S_{D})$ is nonempty: Construct α such that the base-b expansion of α contains infinitely many very long sequences of the digit $\overline{0}$ and apply clause (ii) of Lemma 7.5.

The set $S_{D} ∖ (S_{b ↑} \cup S_{b ↓})$ is nonempty. Let f be an honest function such that $ψ \in S$ implies $ψ ⩽_{E} f$ (for any function ψ). Such an f exists by Theorem 4.10. Furthermore, let $d_{0} = 0$ and $d_{i + 1} = f^{'} (d_{i})$ where $f^{'}$ is the jump of f, and let α be the real number given by the base-b expansion $\begin{matrix} E_{b}^{α} (x) = \{\begin{matrix} 0 & if there exists i such that d_{2 i} ⩽ x < d_{2 i + 1}, \\ \overline{0} & otherwise (there exists i such that d_{2 i + 1} ⩽ x < d_{2 i + 2}). \end{matrix} \end{matrix}$ Then, we have $α \notin (S_{b ↑} \cup S_{b ↓})$ by Lemma 7.5.

We will now argue that the Dedekind cut of α is elementary (and thus in $S$ ). Since $f^{'}$ is honest, we can elementarily in x compute i such that $d_{i} ⩽ x < d_{i + 1}$ . This makes it easy to see that $E_{b}^{α}$ is elementary.

Now, how can we elementarily decide if a rational number q lies below or above the irrational number α? Let ${(0 . {\dot{D}}_{1} {\dot{D}}_{2} \dots)}_{b}$ be the base-b expansion of q. Since q is rational, this expansion will be of the form $0 . {\dot{D}}_{1} \dots {\dot{D}}_{j} {({\dot{D}}_{j + 1} \dots {\dot{D}}_{n})}^{ω}$ (the expansion is finite if $j = n$ ). Let ${(0 . D_{1} D_{2} \dots)}_{b}$ be the base-b expansion of α. We invite the reader to check that $\begin{array}{l} (*) & q < α \Leftrightarrow {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{j} {\dot{D}}_{j + 1} \dots {\dot{D}}_{n} {\dot{D}}_{j + 1} \dots {\dot{D}}_{n})}_{b} ⩽ {(0 . D_{1} \dots D_{n + (n - j)})}_{b} . \end{array}$ Thus, we can decide if $q < α$ by the following procedure:

compute j, n and the rational number $q_{0}$ such that $\begin{matrix} q_{0} = {(0 . {\dot{D}}_{1} \dots {\dot{D}}_{j} {\dot{D}}_{j + 1} \dots {\dot{D}}_{n} {\dot{D}}_{j + 1} \dots {\dot{D}}_{n})}_{b}, \end{matrix}$

compute $\begin{matrix} q_{α} = {(0 . D_{1} \dots D_{n + (n - j)})}_{b} = \sum_{i = 0}^{n + (n - j)} E_{b}^{α} (i), \end{matrix}$

check if $q_{0} ⩽ q_{α}$ .

The first step and the third step of this procedure involve only elementary computations. So does the second step as

E_{b}^{α}

is an elementary function. Hence, we can decide elementarily in q if q lies below or above α, and we conclude that the Dedekind cut of α is elementary.

The readers that want to check that (*) indeed holds should note the following: (i) If the base-b expansion of q is finite, then (*) holds since α is irrational. (ii) If the base-b expansion of q is infinite, then the period ${\dot{D}}_{j + 1} \dots {\dot{D}}_{n}$ of the expansion cannot contain only 0’s or only $\overline{0}$ ’s. It follows that the first $n + (n - j)$ digits of the base-b expansion of q do not coincide with first $n + (n - j)$ digits of the base-b expansion of α.

Footnotes

Acknowledgement

The author wants to thank one of the referees for valuable advice regarding the presentation.

References

Aberth, Computable Analysis, MacGraw-Hill, New York, 1980.

S.B.

Cooper, Computability Theory, Chapman and Hall/CRC, Boca Raton, FL 2003.

Georgiev, Continued fractions of primitive recursive real numbers, Mathematical Logic Quarterly 61(4–5) (2015), 288–306. doi:10.1002/malq.201400013.

Ko, On the definitions of some complexity classes of real numbers, Mathematical Systems Theory 16 (1983), 95–109. doi:10.1007/BF01744572.

Ko, On the continued fraction representation of computable real numbers, Theoretical Computer Science 47 (1986), 299–313. doi:10.1016/0304-3975(86)90154-4.

Kristiansen, Information content and computational complexity of recursive sets, in: Gödel ’96,

Hajek, ed., Springer Lecture Notes in Logic, Vol. 6, Springer-Verlag, Heidelberg, 1996, pp. 235–246.

Kristiansen, Papers on subrecursion theory, Dr Scient Thesis, Research Report 217, Department of Informatics, University of Oslo, 1996. ISSN 0806-3036, ISBN 82-7368-130-0.

Kristiansen, On subrecursive representability of irrational numbers, Computability 6 (2017), 249–276. doi:10.3233/COM-160063.

Kristiansen,

Lubarsky,

J.-C.

Schlage-Puchta and

Weiermann, On the structure of honest elementary degrees, in: The Infinity Project,

Friedman,

Koerwinen and

Müller, eds, CRM Documents, Vol. 11, CRM (Centre de Recerca Matematica), Bellaterra (Barcelona), 2012, pp. 255–279.

10.

Kristiansen,

J.-C.

Schlage-Puchta and

Weiermann, Streamlined subrecursive degree theory, Annals of Pure and Applied Logic 163 (2012), 698–716. doi:10.1016/j.apal.2011.11.004.

11.

Labhalla and

Lombardi, Real numbers, continued fractions and complexity classes, Annals of Pure and Applied Logic 50 (1990), 1–28. doi:10.1016/0168-0072(90)90052-4.

12.

Leary and

Kristiansen, A Friendly Introduction to Mathematical Logic, 2nd edn, Milne Library, SUNY Geneseo, Geneseo, NY, 2015.

13.

R.S.

Lehman, On primitive recursive real numbers, Fundamenta Mathematica 49 (1961), 105–118. doi:10.4064/fm-49-2-105-118.

14.

Mostowski, Computable sequences, Fundamenta Mathematica 44 (1957), 37–51.

15.

Péter, Rekursive Funktionen, Verlag der Ungarischen Akademie der Wissenschaften, Budapest, 1957, English translation: Academic Press, New York, 1967.

16.

H.E.

Rose, Subrecursion. Functions and Hierarchies, Clarendon Press, Oxford, 1984.

17.

Skordev, Computability of real numbers by using a given class of functions in the set of the natural numbers, Mathematical Logic Quarterly 48 (2002), 91–106. doi:10.1002/1521-3870(200210)48:1+<91::AID-MALQ91>3.0.CO;2-L.

18.

Skordev,

Weiermann and

Georgiev,

M^{2}

-computable real numbers, Journal of Logic and Computation 22 (2008), 899–925. doi:10.1093/logcom/exq050.

19.

Specker, Nicht Konstruktiv Beweisbare Satze Der Analysis, Journal of Symbolic Logic 14 (1949), 145–158. doi:10.2307/2267043.

20.

Weihrauch, The degrees of discontinuity of some translators between representations of real numbers, Informatik Berichte 129, Fern Universität Hagen, 1992.

21.

Weihrauch, Computable Analysis, Springer-Verlag, Berlin, 2000.