On subrecursive representability of irrational numbers

Abstract

We consider various ways to represent irrational numbers by subrecursive functions: via Cauchy sequences, Dedekind cuts, trace functions, several variants of sum approximations and continued fractions. Let $S$ be a class of subrecursive functions. The set of irrational numbers that can be obtained with functions from $S$ depends on the representation. We compare the sets obtained by the different representations.

Keywords

Computable analysis subrecursive functions honest functions irrational numbers

1. Introduction

Dedekind cuts yield information about real numbers that cannot been retrieved from Cauchy sequences if we are not allowed to carry out unbounded search. This is true even if the Cauchy sequence has a known modulus of convergence. Assume we have access to a Cauchy sequence C for an irrational number α (so we know that α is irrational). Assume also that $\begin{matrix} | α - C (n) | < \frac{1}{2^{n}} . \end{matrix}$ How can you decide if $α < 1$ ? Consider C as an oracle. If we ask the oracle for $C (17)$ and get the answer 1, then we know that the distance between α and 1 is less than $2^{- 17}$ , but we do not know if α lies below or above 1. The only way to decide if $α < 1$ is by unbounded search. We have to ask the oracle for $C (n)$ for larger and larger values of n. Sooner or later the oracle will give an answer which allows you to conclude if α is less than 1 or not, but there is obviously no way to predict when this will happen. In contrast, if we have access to the Dedekind cut of α, we can easily determine if α is less than 1. The Dedekind cut can be viewed as a function $D : Q \to {0, 1}$ where $D (q) = 0$ if and only if $q < α$ . Thus, we can simply ask for the value of $D (1)$ . We can conclude that $1 < α$ if $D (q) = 0$ , and we can conclude that $α < 1$ if $D (q) = 1$ (since α is irrational). Just one question is needed. No unbounded search is required.

Computations where unbounded search do not occur are called subrecursive computations. When we compute subrecursively we have to determine the maximum number of times the body of a loop should be executed before the execution of the loop starts. The considerations above show that we cannot compute a Dedekind cut subrecursively in a Cauchy sequence. Can a Cauchy sequence be computed subrecursively in a Dedekind cut? Well, Cauchy sequences yield some information that cannot be retrieved from Dedekind cuts without unbounded search. If we have a Cauchy sequence for an irrational number α, then we can subrecursively compute an integer a such that $a < α < a + 2$ . We cannot compute such an a from a Dedekind cut without carry out unbounded search. However, if we assume that we know this a, then we can compute a Cauchy sequence for α subrecursively in the Dedekind cut of α (see the proof of Theorem 4.2). A Cauchy sequence for α is non-uniformly – but not uniformly – subrecursively computable in the Dedekind cut of α.

Irrational numbers may be traced by functions from rational numbers into rational numbers. A function $T : Q \to Q$ is a trace function for α if $T (q)$ lies strictly closer to α than q. It is easy to see that the Dedekind cut of α can be computed subrecursively in a trace function for α: we have $q < α$ if $q < T (q)$ , and we have $q > α$ if $q > T (q)$ . But can we compute a trace function for α subrecursively in the Dedekind cut of α (we assume that α is irrational)? Let us say that we want to determine a value for $T (1)$ . Any value closer to α than 1 will do. We ask the Dedekind cut which tells us that $1 < α$ . Now we know that $T (1)$ should be strictly greater than 1. But how much greater? We may ask the Dedekind cut if $1 + \frac{1}{2}$ is above or below α. If $1 + \frac{1}{2}$ is below α, we are done. Then, we have a possible value for $T (1)$ as $1 + \frac{1}{2}$ has to lie closer to α than 1. But what if $1 + \frac{1}{2}$ is above α? Then we cannot conclude that $1 + \frac{1}{2}$ is closer to α than 1. That might be the case, but we cannot know. Thus, we have to consult the Dedekind cut again and ask if, e.g., $1 + \frac{1}{4}$ is above or below α? If the number is below, we are done. If the number is above, we have we have to consult the Dedekind cut yet another time. The process will terminate sometimes as α is irrational, but we cannot predict when as α may lie arbitrarily close to 1. Unbounded search for an n such that $1 + \frac{1}{n} < α$ is required.

Let $S$ be a sufficiently large natural subrecursive class, e.g., the class of Kalmár elementary functions, the class of primitive recursive function or the class of functions provably total in Peano Arithmetic. Let $S_{C}$ , $S_{D}$ and $S_{T}$ denote the irrational numbers representable by, respectively, Cauchy sequences, Dedekind cuts and trace functions in $S$ . The naive considerations above indicates that $\begin{matrix} S_{T} \subset S_{D} \subset S_{C} . \end{matrix}$ These inclusions are strict – and they will be strict for any $S$ which is contained in an efficiently enumerable class of total computable functions (this will be proved in Section 8). We cannot turn a Cauchy sequence into a Dedekind cut by subrecursive means, and we cannot turn a Dedekind cut into a trace function by subrecursive means. This requires unbounded search, that is, full Turing computability. On the other hand, a Cauchy sequence can be subrecursively computed in a Dedekind cut, and a Dedekind cut can subrecursively computed in a trace function. Thus, it makes perfectly good sense to talk about three different levels of subrecursive representability of irrational numbers: the T-level, the D-level and the C-level.

Continued fractions belongs at the T-level. Let $S_{[]}$ denote the irrationals represented by continued fractions in subrecursive class $S$ . We will prove that $S_{[]} = S_{T}$ for any $S$ that is closed under primitive recursive operations. For a number of representations that belong at the C-level and the D-level, see Ko [5,6].

The three levels discussed above are definitely natural. Are there more natural levels? Results of Specker [25] and Lehman [15] indicate that there is a level between the D-level and the C-level. An irrational number may be represented by its binary expansion (which again may be represented by, e.g., a 0–1-valued function). Let $S_{B}$ denote irrational numbers representable by binary expansions in $S$ . Then, we will have $\begin{matrix} S_{D} \subset S_{B} \subset S_{C} \end{matrix}$ for a sufficiently large natural subrecursive class $S$ . We are not going to undertake any technical discussions of the B-level in the current paper, but we will introduce four more levels of subrecursive representability: the ↑-level, the ↓-level, the $g ↑$ -level and the $g ↓$ -level.

Any irrational number α can be written of the form $\begin{matrix} α = a + \frac{1}{2^{k_{0}}} + \frac{1}{2^{k_{1}}} + \frac{1}{2^{k_{2}}} + \dots \end{matrix}$ where $k_{0}, k_{1}, k_{2}, \dots$ is a strictly monotone increasing sequence of natural numbers and a is an integer. Let $A : N \to N$ be a strictly monotone function. We will say that A is a sum approximation from below of the real number α if there exists $a \in Z$ such that $\begin{matrix} α = a + \sum_{i = 0}^{\infty} \frac{1}{2^{A (i) + 1}} . \end{matrix}$ Any real number can also be written as a difference between an integer and an infinite sum, and we will say that A is a sum approximation from above of the real number α if there exists $a \in Z$ such that $\begin{matrix} α = a - \sum_{i = 0}^{\infty} \frac{1}{2^{A (i) + 1}} . \end{matrix}$ Let $S_{↑}$ and $S_{↓}$ denote irrational numbers have sum approximations from, receptively, below and above in $S$ . We will see that $\begin{matrix} S_{↑} ⊈ S_{↓} and S_{↓} ⊈ S_{↑} \end{matrix}$ whenever $S$ is a sufficiently large natural subrecursive class. To put it slightly differently: the ↑-level and the ↓-level are incomparable levels.

Now, how do these two incomparable levels relate to the other levels? Well, it is obvious that both levels are above the B-level. We do not need unbounded search to compute a binary expansion from a sum approximation (from below or above). Moreover, since the levels are incomparable they have to be strictly above the B-level, that is, we have $\begin{matrix} S_{↑} \subset S_{B} and S_{↓} \subset S_{B} \end{matrix}$ whenever $S$ is a sufficiently large subrecursive class. How the ↑-level and the ↓-level relate to the D-level and the T-level is a somewhat longer story. Let $S$ be a subrecursive class that is closed under primitive recursive operations. We will prove that we have $\begin{matrix} S_{T} \subseteq S_{↑} \cap S_{↓} \cap S_{D} \end{matrix}$ and we believe – but we have no proof – that this inclusion is strict. Furthermore, we will prove that $\begin{matrix} (S_{↑} \cap S_{D}) ∖ S_{↓} \neq \emptyset and (S_{↓} \cap S_{D}) ∖ S_{↑} \neq \emptyset . \end{matrix}$ We believe that also the set $(S_{↑} \cap S_{↓}) ∖ S_{D}$ is nonempty, and we have a pretty good idea of how to prove that, but we will not present the proof in this paper. Figure 1 gives an overview that is partly based on our beliefs.

Figure 1.

Overview: the C-level, the B-level, the D-level, the ↑-level, the ↓-level and the T-level.

The sum approximations discussed above can be considered as sum approximations in base 2. In general, we can sum-approximate any irrational number α in base b when b is an arbitrary natural number strictly greater than 1, that is, we can write α of the form $\begin{matrix} (from below) & α = a + \frac{d_{0}}{b^{k_{0}}} + \frac{d_{1}}{b^{k_{1}}} + \frac{d_{2}}{b^{k_{2}}} + \dots \end{matrix}$ and of the form $\begin{matrix} (from above) & α = a - (\frac{d_{0}}{b^{k_{0}}} + \frac{d_{1}}{b^{k_{1}}} + \frac{d_{2}}{b^{k_{2}}} + \dots) \end{matrix}$ where $k_{0}, k_{1}, k_{2}, \dots$ is a strictly monotone increasing sequence of natural numbers and a is an integer and $d_{i} \in {1, \dots, b - 1}$ .

It turns out that the computational complexity of a sum approximation for an irrational number depends significantly on the base of the approximation. A general sum-approximation from below (above) of an irrational number is a function that yields a representation of the number as a sum approximation from below (above) in any base strictly greater than 1 (the exact definition of a general sum-approximation can be found in Section 6). Let $S_{g ↑}$ and $S_{g ↓}$ denote the irrational numbers representable by general sum-approximations from, respectively, below and above in the subrecursive class $S$ . Obviously, we have $S_{g ↑} \subseteq S_{↑}$ and $S_{g ↓} \subseteq S_{↓}$ . We will prove that we have $\begin{matrix} S_{g ↑} \subset S_{D} and S_{g ↓} \subset S_{D} \end{matrix}$ when $S$ is closed under elementary operations, and we will prove that we have $\begin{matrix} S_{g ↑} \cap S_{g ↓} = S_{T} \end{matrix}$ when $S$ is closed under primitive recursive operations.

Figure 2 gives an overview of how we believe the $g ↑$ -level and the $g ↓$ -level relate to the other levels. We emphasize that the Venn diagrams in our figures show what we believe is the case and not necessarily what will proved to be case, e.g., we will not prove anything that excludes that both ↑-level and the ↓-level are strictly included in the D-level.

Figure 2.

Overview: D-level, the ↑-level, the ↓-level, the $g ↑$ -level, the $g ↓$ -level and the T-level.

We glimpse the contours of a strange animal in Fig. 2. We believe in the existence of the creature, but we have not yet proved this existence. It remains to prove that the following sets are nonempty

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

$(S_{g ↑} \cap S_{↓}) ∖ S_{T}$ ,

$(S_{↑} \cap S_{g ↓}) ∖ S_{T}$ ,

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

when

S

is a class closed under primitive recursive operations.

The research presented in this paper is related to research of Specker [25], Lehman [15], Ko [5,6] and a line of research by Georgiev, Skordev and Weiermann, see [3,23,24]. For more on computable analysis, see Aberth [1] or Weihrauch [27].

Many results presented in this paper overlap with results published elsewhere, e.g., it is well known that the inclusions $S_{[]} \subset S_{D} \subset S_{C}$ hold when $S$ is a natural subrecursive class. As far as the author know, sum approximations and trace functions are not studied elsewhere (he will not be surprised if he knows too little). Our proofs will be based on the theory of honest functions. This theory makes some of our proofs concise and transparent and helps us to avoid classical diagonalisation arguments.

2. Preliminaries

2.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 [21] or [22]. Here we just state some important basic facts and definitions, see [21] and [22] 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 [14].

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 characterisation 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))$ .

2.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 e.g. addition, subtraction and multiplication – will obviously be elementary.

Occasionally we will have to explicitly consider the size of the encoding of a rational number: we use ${[q]}_{N}$ to denote the natural number that encodes the rational number q. Thus, given a reasonable coding, we have that, e.g., $\frac{1}{314} > 1$ is false, whereas ${[\frac{1}{314}]}_{N} > 1$ is true.

2.3. Honest functions and degrees

The theory of honest functions will help us to make some of our proofs concise and transparent.

Definition 2.1.
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 2.2.
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.

We define the relation $\equiv_{E}$ by $f \equiv_{E} g \Leftrightarrow f ⩽_{E} g \land g ⩽_{E} f$ . Now, $\equiv_{E}$ is an equivalence relation on the honest functions.

The $\equiv_{E}$ -equivalence classes of honest functions are the honest elementary degrees. Honest elementary degrees will normally just be called degrees, and following the tradition of classical computability theory, we use boldface lowercase Latin letters $a, b, c, \dots$ to denote our degrees.

We will use $deg (f)$ denote the degree of the honest function f, that is, $\begin{matrix} deg (f) = {g ∣ g \equiv_{E} f} . \end{matrix}$

We define the relation $<_{E}$ by $f <_{E} g \Leftrightarrow f ⩽_{E} g \land g ≰_{E} f$ ; We will use <, ⩽ to denote the relations induced on the degrees by respectively $<_{E}$ , $⩽_{E}$ .

The structure of honest elementary degrees is a lattice with very strong density properties. For more on this structure and the theory of honest functions, see [12] or [13] (here we will just introduce what we need to prove our results on representability of irrational numbers).
Definition 2.3.
We define the subrecursive class $⩽ (a)$ by $\begin{matrix} ⩽ (a) = {ψ ∣ there exists f such that a = deg (f) and ψ ⩽_{E} f} . \end{matrix}$

The standard notation is really $⩽_{E} (a)$ and not $⩽ (a)$ , but we skip the E in order to improve the readability.
Lemma 2.4.
Let $a = deg (f)$ where f is an honest function. For any $ψ \in ⩽ (a)$ , 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.
Let $ψ \in ⩽ (a)$ . Then, we have $ψ ⩽_{E} f$ , that is, ψ 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 f to prove that the lemma holds. Use that f is monotone and dominates $2^{x}$ . □

We will now define an operator $\cdot^{'}$ transforming an honest function f into a faster increasing honest function $f^{'}$ . This operator will be called the jump operator.
Definition 2.5.
For any honest function f, we define the jump of f, written $f^{'}$ , by $f^{'} (x) = f^{x + 1} (x)$ .
Lemma 2.6.
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{matrix} () & (\exists s ⩽ ψ (x, y)) [{(s)}_{0} = f (x) \land (\forall i < x) [{(s)}_{i + 1} = f ({(s)}_{i})] \land {(s)}_{x} = y] . \end{matrix}$ 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 2.7.
Let f and g be honest functions. Then, we have* $\begin{matrix} g ⩽_{E} f \Rightarrow g^{'} ⩽_{E} f^{'} . \end{matrix}$
Proof.
Suppose $g ⩽_{E} f$ . By Lemma 2.4, we have a fixed k such that $g (x) ⩽ f^{k} (x)$ . Now $\begin{matrix} g^{'} (x) = g^{x + 1} (x) ⩽ {(f^{k})}^{x + 1} (x) ⩽ f^{(k x + k) + 1} (k x + k) = f^{'} (k x + k) ⩽ {(f^{'})}^{2 k} (x) . \end{matrix}$ Thus $\begin{matrix} g^{'} (x) = μ y ⩽ {(f^{'})}^{2 k} (x) [g^{'} (x) = y] . \end{matrix}$ The relation $g^{'} (x) = y$ is elementary by Lemma 2.6. The functions elementary in $f^{'}$ is closed under composition and the bounded μ-operator. Thus, we have $g^{'} ⩽_{E} f^{'}$ . □

Lemma 2.7 entails that $f^{'} \equiv_{E} g^{'}$ whenever f and g are honest functions such that $f \equiv_{E} g$ . Hence, the jump operator on the honest functions induces an operator on the honest elementary degrees.
Definition 2.8.
For any honest elementary degree a, we define the jump of a, written $a^{'}$ , by $a^{'} = deg (f^{'})$ where f is some honest function such that $a = deg (f)$ . Furthermore, we define the zero degree, written $0$ , by $0 = deg (2^{x})$ .
Lemma 2.9.
Let $a = deg (f)$ where f is an honest function. Then, $f^{'} \notin ⩽ (a)$ .
Proof.
Assume for the sake of a contradiction that $f^{'} \in ⩽ (a)$ . By Lemma 2.4, we have a fixed k such that $f^{'} (x) ⩽ f^{k} (x)$ . But $f^{'} (x) = f^{x + 1} (x)$ , and we cannot have $f^{x + 1} (x) ⩽ f^{k} (x)$ when f is honest. For $x ⩾ k$ , we have $f^{'} (x) = f^{x + 1} (x) > f^{k} (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 [7]. A more detailed proof can be found in Kristiansen [8].
Theorem 2.10 (Normal Form Theorem).

Let $a = deg (f)$ where f is an honest function. Let ϕ be any (Turing) computable function. Then, $ϕ \in ⩽ (a)$ 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.

Lemma 2.11.
One application of primitive recursion over functions in $⩽ (a)$ yields a function in $⩽ (a^{'})$ , that is, if $\begin{matrix} ϕ (\vec{x}, 0) = ξ (\vec{x}) and ϕ (\vec{x}, y + 1) = ψ (\vec{x}, y, ϕ (\vec{x}, y)) \end{matrix}$ where $ξ, ψ \in ⩽ (a)$ , then we have $ϕ \in ⩽ (a^{'})$ .
Proof.
Let f be an honest function such that $a = deg (f)$ . By Lemma 2.4, we have $k_{0}, k_{1} \in N$ such that $ξ (\vec{x}) ⩽ f^{k_{0}} (max (\vec{x}))$ and $ψ (\vec{x}, z_{1}, z_{2}) ⩽ f^{k_{1}} (max (\vec{x}, z_{1}, z_{2}))$ . A straightforward induction on y shows that $\begin{matrix} ϕ (\vec{x}, y) ⩽ f^{k_{1} y + k_{0}} (max (\vec{x}, y)) . \end{matrix}$ Thus, as f is monotone and dominates $2^{x}$ , we have $\begin{array}{l} ϕ (\vec{x}, y) & ⩽ f^{k_{1} y + k_{0}} (max (\vec{x}, y)) ⩽ f^{k_{1} y + k_{0}} (f^{'} (max (\vec{x}, y))) \\ = f^{'} (k_{1} y + k_{0} + max (\vec{x}, y)) ⩽ {(f^{'})}^{k_{1} + k_{0} + 1} (max (\vec{x}, y)) . \end{array}$ This shows that ϕ can be defined by composition and bounded primitive recursion over elementary functions and the function $f^{'}$ . Hence, we have $ϕ \in ⩽ (a^{'})$ . □

Let us study a couple of examples: $⩽ (0)$ is the class of elementary functions. Let $a_{0} = 0$ , and let $a_{i + 1} = a^{'}$ . Then, we have $a_{0} < a_{1} < a_{2} < \dots$ , and the hierarchy $\begin{matrix} ⩽ (a_{0}) \subset ⩽ (a_{1}) \subset ⩽ (a_{2}) \subset \dots \end{matrix}$ matches the Grzegorczyk hierarchy from stage 3 and upwards, that is, the Grzegorczyk class $E^{i + 3}$ equals the class $⩽ (a_{i})$ . Let $g (x) = max (2^{x}, A (x, x))$ where A is the Ackermann function. The function g is honest, and we have $a_{i} < deg (g)$ for all $i \in N$ . The subrecursive class $⩽ (deg (g))$ contains all the primitive recursive functions. The jump of g, the function $g^{'}$ , is not elementary in the Ackermann function.

We finish off this section with a few historical remarks: The theory of honest functions and degrees has its roots in subrecursion theory developed in the 1970s, see, e.g., Meyer and Ritchie [19], Machtey [16–18] and Verbeek [26]. The theory was systematically developed by the author in the late 1990s, see Kristiansen [7–11]. The definition of honest function given above (Definition 2.1) is due to the author and occurs for the first time in Kristiansen [7]. We refer the reader to [13] (or to the related [12]) for more details.
3. $S$ -irrational numbers

Definition 3.1.
Let $S$ be a class of functions. A real number α is $S$ -irrational if there is $ν : N \to N$ in $S$ such that for any $m \in Z$ and $n \in N ∖ {0}$ , we have $\begin{matrix} | α - \frac{m}{n} | > \frac{1}{ν (n)} . \end{matrix}$

Let $P$ denote the class of primitive recursive functions. Lehman [15] proves that a $P$ -irrational number has a primitive recursive Cauchy sequence iff it has a primitive recursive continued fraction. A similar, but stronger result, is proved by Georgiev [3]. These results will be corollaries of our theorems. Lemma 3.2.
Let $S$ be a class closed under elementary operations. The following three assertions are equivalent:
α is $S$ -irrational.

There is $ψ : Q \to N$ in $S$ such that for any $q \in Q$ , we have $\begin{matrix} | α - q | > \frac{1}{ψ (q)} . \end{matrix}$

There is $ψ : Q \to Q$ in $S$ such that for any $q \in Q$ , we have $\begin{matrix} | α - q | > ψ (q) . \end{matrix}$

Proof.
Assume that α is $S$ -irrational. Then, we have ν in $S$ such that $\begin{matrix} | α - \frac{m}{n} | > \frac{1}{ν (n)} \end{matrix}$ (for any $m \in Z$ and $n \in N ∖ {0}$ ). Let $N (q)$ , where $q \in Q$ , equal the least $n \in N$ such that we have $q = \frac{m}{n}$ for some $m \in Z$ . The function N is elementary. Let $ψ (q) = ν (N (q))$ . Now we have $ψ \in S$ and $\begin{matrix} | α - q | > \frac{1}{ψ (q)} . \end{matrix}$ Thus, (2) holds. This proves that (1) implies (2).

We prove that (2) implies (1). Let $a < α < a + 1$ where $a \in Z$ . Let $\begin{matrix} ν (n) = \sum_{i = 0}^{3 n} ψ ((a - 1) + \frac{i}{n}) \end{matrix}$ where $ψ : Q \to N$ is given by (2). Let $m \in Z$ and $n \in N$ . Assume $\frac{m}{n}$ is in the interval $[a - 1, \dots, a + 2]$ . Then we have $\frac{m}{n} = (a - 1) + \frac{i}{n}$ for some $i \in {0, \dots, 3 n}$ . Hence $\begin{matrix} | α - \frac{m}{n} | = | α - ((a - 1) + \frac{i}{n}) | > \frac{1}{ψ ((a - 1) + \frac{i}{n})} > \frac{1}{\sum_{i = 0}^{3 n} ψ ((a - 1) + \frac{i}{n})} = \frac{1}{ν (n)} . \end{matrix}$ If $\frac{m}{n}$ is not in the interval $[a - 1, \dots, a + 2]$ , we have $\begin{matrix} | α - \frac{m}{n} | > 1 > \frac{1}{ν (n)} . \end{matrix}$ The function ν is in $S$ when ψ is in $S$ . This proves that (2) implies (1).

It is straightforward to prove that (2) and (3) are equivalent, and we omit the details. □
Lemma 3.3.
Let $a = deg (f)$ where f is an honest function. A real number α is $⩽ (a)$ -irrational iff there is $k \in N$ such that for any $m \in Z$ and any $n \in N ∖ {0}$ , we have $\begin{matrix} | α - \frac{m}{n} | > \frac{1}{f^{k} (n)} . \end{matrix}$
Proof.
This follows straightforwardly from Definition 3.1 and Lemma 2.4. □

4. Cauchy sequences, Dedekind cuts and trace functions

Definition 4.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 < α$ .

A function $T : Q \to Q$ is a trace function for the irrational number α when $\begin{matrix} | α - q | > | α - T (q) | . \end{matrix}$

For any class of functions $S$ , let $S_{C}$ denote the set of irrational numbers that have a Cauchy sequence in $S$ ; let $S_{D}$ denote the set of irrational numbers that have a Dedekind cut in $S$ ; let $S_{T}$ denote the set of irrational numbers that have a trace function in $S$ .
Theorem 4.2.
Let α be an irrational number. (1) The Dedekind cut of α is elementary in a trace function for α. (2) A Cauchy sequence for α is elementary in the Dedekind cut of α. Thus, $⩽ {(a)}_{T} \subseteq ⩽ {(a)}_{D} \subseteq ⩽ {(a)}_{C}$ .
Proof.
Assume that T is a trace function for α. Let $D (q) = 0$ if $q < T (q)$ , else let $D (q) = 1$ . Then, D is the Dedekind cut for α. Moreover, D is obviously elementary in T.

Assume that D is the Dedekind cut of α. We can w.l.o.g. assume $0 < α < 1$ . We define the Cauchy sequence C by $C (0) = 0$ and $\begin{matrix} C (n + 1) = \{\begin{matrix} C (n) + \frac{1}{2^{n + 1}} & if D (C (n) + \frac{1}{2^{n + 1}}) = 0, \\ C (n) & otherwise . \end{matrix} \end{matrix}$ It is obvious that C is a Cauchy sequence for α. Furthermore, C is defined by primitive recursion. It is easy to see that we have ${[C (n)]}_{N} ⩽ 2_{k}^{n}$ for some fixed $k \in N$ . This shows that we can define C by bounded primitive recursion over elementary functions and the Dedekind cut D. □

The proof of the next theorem is a standard diagonalisation argument. Still, the proof might be hard to follow, and we will prepare the reader a little bit.

Assume that $α \in ⩽ {(a)}_{D}$ where $a = deg (f)$ and f is honest. Let $D_{α}$ be the Dedekind cut of α. By the Normal Form Theorem (Theorem 2.10), we have a computable index e and a natural number k such that $\begin{matrix} D_{α} (x) = U (μ t ⩽ f^{k} (x) [T_{1} (e, x, t)]) . \end{matrix}$ This implies that $\begin{matrix} D_{α} (x) = U (μ t ⩽ f^{k} (i) [T_{1} (e, x, t)]) \end{matrix}$ for every $i ⩾ x$ . Recall that the functions in the class $⩽ {(a)}_{D}$ formally are functions from natural numbers into natural numbers and that ${[q]}_{N}$ denotes one of the natural numbers that encodes the rational number q. Thus it might be more illuminating to say that we have $\begin{matrix} () & D_{α} ({[x]}_{N}) = U (μ t ⩽ f^{k} (i) [T_{1} (e, {[x]}_{N}, t)]) \end{matrix}$ for every $i ⩾ {[x]}_{N}$ .

Now, imagine that you have undertaken the never-ending task of writing up a Cauchy sequence of an irrational number. Along the way you are not allowed to carry out non-elementary computations, that is, all the functions you compute have to be in the class $⩽ (0)$ . You are done with the elements $C (0), C (1), \dots, C (n)$ , and now you want to extend the sequence by finite number of elements such that it will not converge to the number α given by the Dedekind cut in (∗). If you manage to this, you can go on and consider an another irrational number given a by an another Dedekind cut and ensure the Cauchy sequence does not converge to that number either. Indeed, you may work way through all the numbers in the class $⩽ {(a)}_{D}$ and ensure that your Cauchy sequence does not converge to a single one of them.

So how can you ensure that your sequence will not converge to α? Well, you search for a natural number i such that $\begin{matrix} ( ) & n + 1 = f^{k} (i) and i ⩾ {[C (n)]}_{N} . \end{matrix}$ Such a search can be carried out with elementary means. If you find the i you are looking for, you can check if $C (n)$ lies strictly below or strictly above α (recall that α is irrational). You can check this because $\begin{matrix} D_{α} ({[C (n)]}_{N}) = U (μ t ⩽ f^{k} (i) [T_{1} (e, {[C (n)]}_{N}, t)]) = U (μ t ⩽ n + 1 [T_{1} (e, {[C (n)]}_{N}, t)]) \end{matrix}$ and hence you can compute $D_{α} ({[C (n)]}_{N})$ elementarily in n and ${[C (n)]}_{N}$ . If it turns out that $C (n)$ lies strictly below α, extend your sequence by the rational number $C (n + 1)$ where $C (n + 1) = C (n) - \frac{1}{2^{n + 1}}$ . Then, what you have written up so far, that is, the sequence $C (0), C (1), \dots, C (n), C (n + 1)$ , is still the start of a Cauchy sequence, moreover, it is the start of a sequence that cannot converge to α. The Cauchy sequence you have started has to converge to a number strictly smaller than α. If it turns out that $C (n)$ lies strictly above α, let $C (n + 1)$ be $C (n) + \frac{1}{2^{n + 1}}$ and your Cauchy sequence will converge to a number strictly greater than α.

What should you do if there is no i such that (∗∗) holds? If this should be the case, just let $C (n + 1)$ equal $C (n)$ , and then you increase the value of n by one. Repeat doing this until (∗∗) holds. So just extend your sequence over and over again by the same rational number until (∗∗) holds – it will still be a Cauchy sequence. You cannot increase n forever and ever without making (∗∗) true. When (∗∗) eventually becomes true, you set $C (n + 1)$ to a value that ensures your Cauchy sequence will not converge to α.

We hope the considerations above will help the reader to digest the proof of Theorem 4.4.
Lemma 4.3.
Let f be an honest function, let $deg (f) = a$ , and let D be a Dedekind cut in $⩽ (a)$ . There exist $e \in N$ such that $\begin{matrix} D (x) = U (μ t ⩽ f^{'} (x) [T_{1} (e, x, t)]) \end{matrix}$ for all sufficiently large x.
Proof.
By the Normal Form Theorem (Theorem 2.10), we have $e, k \in N$ such that $\begin{matrix} D (x) = U (μ t ⩽ f^{k} (x) [T_{1} (e, x, t)]) . \end{matrix}$ When $x ⩾ k$ , we have $f^{k} (x) < f^{x + 1} (x) = f^{'} (x)$ (the inequality holds as $f (x) ⩾ 2^{x}$ ; the equality holds by the definition of $f^{'}$ ). Thus, the lemma holds. □
Theorem 4.4.
For any honest degree a , there exists a real number α such that $α \in ⩽ {(0)}_{C}$ and $α \notin ⩽ {(a)}_{D}$ .
Proof.
Let f be an honest function such that $a = deg (f)$ . Let $π : N \to N$ be an elementary function such that for any e there exist infinitely many i such that $π (i) = e$ . We will now define a Cauchy sequence C and a function $κ : N \to N$ by simultaneous recursion. Recall that ${[q]}_{N}$ denotes the natural number encoding the rational number q.

Let $C (0) = κ (0) = 0$ , and let $\begin{matrix} C (n + 1) = \{\begin{matrix} C (n) - \frac{1}{2^{n + 1}} & if (\exists i ⩽ n) [n + 1 = f^{'} (i) \land i ⩾ {[C (n)]}_{N}] and \\ U (μ t ⩽ n + 1 [T_{1} (π (κ (n)), {[C (n)]}_{N}, t)]) = 0, \\ C (n) + \frac{1}{2^{n + 1}} & if (\exists i ⩽ n) [n + 1 = f^{'} (i) \land i ⩾ {[C (n)]}_{N}] and \\ U (μ t ⩽ n + 1 [T_{1} (π (κ (n)), {[C (n)]}_{N}, t)]) \neq 0, \\ C (n) & otherwise \end{matrix} \end{matrix}$ and $\begin{matrix} κ (n + 1) = \{\begin{matrix} κ (n) & if C (n) = C (n + 1) and \\ κ (n) + 1 & otherwise . \end{matrix} \end{matrix}$ It is easy to see that C is a Cauchy sequence. Moreover, C (viewed as a function into $N$ ) and κ are slow-growing functions defined by simultaneous recursion over elementary functions and elementary relations (the relation $f^{'} (i) = n$ is elementary since $f^{'}$ is honest). We have $κ (x) ⩽ x$ , and it is easy to see that we have ${[C (n)]}_{N} ⩽ 2_{k}^{n}$ for some fix k. So C can be defined by bounded simultaneous recursion over elementary functions and, thus, C is an elementary function.

Let $α = {lim}_{n \to \infty} C (n)$ . We have $α \in ⩽ {(0)}_{C}$ since C is in $⩽ (0)$ . Now, let β be any irrational number in $⩽ {(a)}_{D}$ . We need to prove that $α \neq β$ .

Let D be a Dedekind cut for β. By Lemma 4.3, we have $e \in N$ such that $\begin{matrix} (†) & D (x) = U (μ t ⩽ f^{'} ({[x]}_{N}) [T_{1} (e, {[x]}_{N}, t)]) \end{matrix}$ for all sufficiently large ${[x]}_{N}$ .

Pick a sufficiently large n such that $π (κ (n)) = e$ and $κ (n) < κ (n + 1)$ (there are infinitely many such n). Since $κ (n) < κ (n + 1)$ , we have i such that $i ⩾ {[C (n)]}_{N}$ and $f^{'} (i) = n + 1$ . Now, we have $\begin{array}{l} U (μ t ⩽ n + 1 [T_{1} (π (κ (n)), {[C (n)]}_{N}, t)]) & = U (μ t ⩽ f^{'} (i) [T_{1} (e, {[C (n)]}_{N}, t)]) \\ () & = U (μ t ⩽ f^{'} ({[C (n)]}_{N}) [T_{1} (e, {[C (n)]}_{N}, t)]) = D ({[C (n)]}_{N}) . \end{array}$ The first equality of (∗) holds by the choice of i and n; the second equality holds since $i ⩾ {[C (n)]}_{N}$ ; the third equality holds by (†) since n, and thus ${[C (n)]}_{N}$ , is large. By (∗) and our definition of C we have $\begin{matrix} C (n + 1) = \{\begin{matrix} C (n) - \frac{1}{2^{n + 1}} & if C (n) < β, \\ C (n) + \frac{1}{2^{n + 1}} & if β < C (n) . \end{matrix} \end{matrix}$ This proves that $β \neq {lim}_{n \to \infty} C (n) = α$ and, thus, we have $α \notin ⩽ {(a)}_{D}$ . □
Lemma 4.5.
Let T be a trace function for the irrational number α. Then, there exists a trace function $T_{0}$ for α such that for all $q \in Q$ we have
$q < T_{0} (q) < α$ if $q < α$ ,

$α < T_{0} (q) < q$ if $α < q$ .
Moreover, $T_{0}$ is elementary in T.
Proof.
Let $T_{0} (q) = \frac{1}{2} (q + T (q))$ . Then, $T_{0}$ is elementary in T. Assume $q < α$ . Then, since $T (q)$ lies closer to α than q, we either have $q < T (q) < α$ or $q < α < T (q)$ . In the case when $q < T (q) < α$ , we obviously have $q < \frac{1}{2} (q + T (q)) < α$ . In the case when $q < α < T (q)$ , we have $q < \frac{1}{2} (q + T (q)) < α$ as α lies closer to $T (q)$ than to q. In either case we have $q < \frac{1}{2} (q + T (q)) < α$ . A symmetric argument shows that we have $α < T_{0} (q) < q$ when $α < q$ . □
Lemma 4.6.
Let $S$ be a class of functions closed under elementary operations, and let $α \in S_{T}$ . Then, α is $S$ -irrational.
Proof.
By Lemma 3.2, it is sufficient to prove that there exists $ψ : Q \to Q$ in $S$ such that $\begin{matrix} () & | α - q | > ψ (q) . \end{matrix}$

Let $T \in S$ be a trace function for α. Let $ψ (q) = | T_{0} (q) - q |$ where $T_{0}$ is the trace function for α given by Lemma 4.5. We have ψ in $S$ since $S$ closed under elementary operations.

If $q < α$ , we have $q < T_{0} (q) < α$ , and thus $| α - q | > | T_{0} (q) - q | = ψ (q)$ . If $α < q$ , we have $α < T_{0} (q) < q$ , and thus $| α - q | > | T_{0} (q) - q | = ψ (q)$ . This proves that (∗) holds. □

Let $a = deg (f)$ where f is an honest function. Lemma 3.3 states that a real number α is $⩽ (a)$ -irrational if and only if there exists $k \in N$ such that $\begin{matrix} () & | α - \frac{m}{n} | > \frac{1}{f^{k} (n)} \end{matrix}$ holds for any $m \in Z$ and any $n \in N ∖ {0}$ . This yields a recipe for constructing irrational numbers which are not $⩽ (a)$ -irrational: Take a sufficiently fast increasing sequence of positive natural numbers $a_{0}, a_{1}, a_{2}, \dots$ , and let $α = \sum_{i = 0}^{\infty} \frac{1}{a_{i}}$ . Make sure that the numbers in the sequence increase so fast that the distance between α the rational number $\sum_{i = 0}^{ℓ} \frac{1}{a_{i}}$ is too small to satisfy (∗) when ℓ is large. Then, α will not be $⩽ (a)$ -irrational.

In the proof of the next lemma we will use this recipe to construct a number which is not $⩽ (a)$ -irrational. Moreover, we will pick the elements of the fast increasing sequence $a_{0}, a_{1}, a_{2}, \dots$ such that the Dedekind cut of the number becomes elementary. Lemma 4.7.
Let a be an arbitrary honest degree. Some numbers in $⩽ {(0)}_{D}$ are not $⩽ (a)$ -irrational.
Proof.
Let f be an honest function such that $a = deg (f)$ . Furthermore, let $d_{0} = 17$ , and let $d_{i + 1} = f^{'} (2^{d_{i}})$ where $f^{'}$ is the jump of f. The function $f^{'}$ is honest by Lemma 2.6. Thus, $d_{i} = y$ is an elementary relation.

Let $\begin{matrix} α_{n} = \sum_{i = 1}^{n} \frac{1}{2^{d_{2 i}}} and α = lim_{n \to \infty} α_{n} . \end{matrix}$

This example may help the reader: $\begin{matrix} α_{3} = \frac{1}{2^{d_{2}}} + \frac{1}{2^{d_{4}}} + \frac{1}{2^{d_{6}}} and α - α_{3} = \frac{1}{2^{d_{8}}} + \frac{1}{2^{d_{10}}} + \frac{1}{2^{d_{12}}} + \dots < \frac{1}{2^{d_{7}}} . \end{matrix}$

First we prove that α is not $⩽ (a)$ -irrational. Pick an arbitrary $k \in N$ . Then, pick $n \in N$ such that $n ⩾ k$ and $n = 2^{d_{2 ℓ}}$ (for some ℓ). Let $m \in N$ be such that $\frac{m}{n} = α_{ℓ}$ (it is easy to see that such an m exists). Now, we have $\begin{matrix} () & | α - \frac{m}{n} | = α - α_{ℓ} = \sum_{i = ℓ + 1}^{\infty} \frac{1}{2^{d_{2 i}}} < \frac{1}{2^{d_{2 ℓ + 1}}} \end{matrix}$ and $\begin{matrix} ( *) & 2^{d_{2 ℓ + 1}} = 2^{f^{'} (2^{d_{2 ℓ}})} > f^{'} (2^{d_{2 ℓ}}) = f^{'} (n) = f^{n + 1} (n) > f^{k} (n) . \end{matrix}$ By (∗) and (∗∗), we have $| α - \frac{m}{n} | < \frac{1}{f^{k} (n)}$ . This proves that there for any k exists n such that $| α - \frac{m}{n} | < \frac{1}{f^{k} (n)}$ . By Lemma 3.3, we conclude that α is not $⩽ (a)$ -irrational.

We will now prove that α is in $⩽ {(0)}_{D}$ . For any $q \in Q$ , we have $q < α$ iff $\begin{matrix} (†) & q ⩽ α_{1} \lor (\exists i) [α_{i} ⩽ q < α_{i + 1}] . \end{matrix}$ Write q of the form $\frac{m}{n}$ where $m \in Z$ and $n \in N$ . Now, if $α_{i} ⩽ \frac{m}{n} < α_{i + 1}$ , then i will be (much) smaller than n and, thus, we can turn the unbounded quantifier in (†) into a bounded one. Moreover, since $d_{x} = y$ is an elementary relation, the relation $α_{i} ⩽ q < α_{i + 1}$ will also be elementary. It follows that (†) is an elementary predicate. The predicate gives the Dedekind cut for α and, thus, α has an elementary Dedekind cut. We conclude that α is in $⩽ {(0)}_{D}$ . □
Theorem 4.8.
For any honest degree a , there exists an irrational number α such that $α \in ⩽ {(0)}_{D}$ and $α \notin ⩽ {(a)}_{T}$ .
Proof.
Let α be a number in $⩽ {(0)}_{D}$ which is not $⩽ (a)$ -irrational. Such an α exists by Lemma 4.7. By Lemma 4.6, we have $α \notin ⩽ {(a)}_{T}$ . □

5. Sum approximations

Definition 5.1.
A strictly monotone increasing function $A : N \to N$ is a sum approximation from below of the real number α if there exists $a \in Z$ such that $\begin{matrix} α = a + \sum_{i = 0}^{\infty} \frac{1}{2^{A (i) + 1}} . \end{matrix}$

A strictly monotone increasing function $A : N \to N$ is a sum approximation from above of the real number α from above if there exists $a \in Z$ such that $\begin{matrix} α = a - \sum_{i = 0}^{\infty} \frac{1}{2^{A (i) + 1}} . \end{matrix}$

If A is a sum approximation of α from below (above), we say that A approximates α from below (above).

For any class of functions $S$ , let $S_{↑}$ denote the class of irrational numbers that have a sum approximation from below in $S$ ; let $S_{↓}$ denote the class of irrational numbers that have a sum approximation from above in $S$ .

Let $f : N \to N$ be a strictly monotone function that increases too fast to be elementary. Now, f approximates a real number α from below. No elementary function can approximate α from below as α only has one sum approximation from below. However, the sum approximation of α from above may very well be elementary since this will not be a very fast-increasing function. The one an only function that approximates α from above is the strictly monotone increasing function with range $N ∖ rng (f)$ . This function will be elementary when f is honest: The graph of an honest function is elementary, that is, the relation $f (x) = y$ is elementary. Thus, we can elementarily decide if $y \in rng (f)$ , and then we can also elementarily compute the sum approximation from above.
Theorem 5.2.
For any honest degree a there exits α such that (a) $α \notin ⩽ {(a)}_{↑}$ , (b) $α \in ⩽ {(0)}_{↓}$ and (c) $α \in ⩽ {(0)}_{D}$ .
Proof.
Let $a = deg (f)$ , and let $\begin{matrix} α = 0 + \sum_{i = 0}^{\infty} \frac{1}{2^{f^{'} (i) + 1}} \end{matrix}$ where $f^{'}$ is the jump of f. Now, there is only one monotone increasing function that approximates α from below, namely $f^{'}$ . Thus, if $α \in ⩽ {(a)}_{↑}$ , we will also have $f^{'} \in ⩽ (a)$ . But that contradicts Lemma 2.9. We conclude that $α \notin ⩽ {(a)}_{↑}$ . This proves (a).

We turn to the proof of (b). Let $A (0) = 0$ and let $\begin{matrix} A (x + 1) = \{\begin{matrix} A (x) + 2 & if A (x) + 1 \in rng (f^{'}), \\ A (x) + 1 & otherwise . \end{matrix} \end{matrix}$ It is obvious that A is a strictly monotone function. In order to conclude that $α \in ⩽ {(0)}_{↓}$ , we have to prove that A is elementary and that A approximates α from above.

First we argue that A is elementary. By Lemma 2.6, $f^{'}$ is an honest function. Thus, $y \in rng (f^{'})$ is an elementary predicate. We also have $A (x) ⩽ 2 x$ . Thus, A can be defined by bounded primitive recursion over elementary functions. The class of elementary functions is closed under such recursion. Hence, A is an elementary function.

Finally, we argue that A approximates α from above. We have $f (x) ⩾ 2^{x}$ since f is honest. Now, $f^{'} (x) = f^{x + 1} (x)$ and, thus, $0 \notin rng (f^{'})$ and, for any $x \in N$ , at most one of x, $x + 1$ and $x + 2$ is in the range of $f^{'}$ . Hence, $rng (A) = N ∖ rng (f^{'})$ . It follows that $α = 1 - \sum_{i = 0}^{\infty} \frac{1}{2^{A (i) + 1}}$ . Thus, A approximates α from above.

In order to prove (c), let $α_{k} = 0 + \sum_{i = 0}^{k} \frac{1}{2^{f^{'} (i) + 1}}$ . Then, we have $\frac{m}{n} ⩽ α$ iff $\begin{matrix} \frac{m}{n} ⩽ α_{1} \lor (\exists i) [α_{i} ⩽ \frac{m}{n} < α_{i + 1}] . \end{matrix}$ Now, if $α_{i} ⩽ \frac{m}{n} < α_{i + 1}$ , then i will be (much) smaller than n. Hence, we have $\begin{matrix} (†) & \frac{m}{n} ⩽ α_{1} \lor (\exists i ⩽ n) [α_{i} ⩽ \frac{m}{n} < α_{i + 1}] \end{matrix}$ and, thus, the predicate (†) is the Dedekind cut for α. The predicate is elementary when $f^{'}$ is an honest function. Hence, we have $α \in ⩽ {(0)}_{D}$ . □
Theorem 5.3.
For any honest degree a there exits α such that (a) $α \notin ⩽ {(a)}_{↓}$ , (b) $α \in ⩽ {(0)}_{↑}$ and (c) $α \in ⩽ {(0)}_{D}$ .
Proof.
This proof is symmetric to the proof of Theorem 5.2 □
Theorem 5.4.
$\begin{matrix} ⩽ {(a)}_{T} \subseteq ⩽ {(a^{'})}_{↑} . \end{matrix}$
Proof.
Let $T \in ⩽ (a)$ be a trace function for α. We can w.l.o.g. assume $0 < α < 1$ . We will prove that there is a function $ψ : N \to Q$ in $⩽ (a^{'})$ such that $\begin{matrix} (†) & lim_{n \to \infty} ψ (n) = α \end{matrix}$ and, for each $n > 0$ , we have $k_{n} \in N$ and $b_{1}, \dots, b_{k_{n}} \in {0, 1}$ such that $\begin{matrix} (‡) & ψ (n) = {(0 . b_{1} b_{2} \dots b_{k_{n}})}_{2} and b_{k_{n}} = 1 and 1 < k_{n} < k_{n + 1} . \end{matrix}$ The function A that approximates α from below is elementary in ψ: The natural number $k_{n}$ can easily be computed from the rational number $ψ (n)$ . Let $A (n) = k_{n + 1} - 1$ . It is obvious that A is elementary in ψ. Moreover, A is a strictly monotone function which approximates α from below, that is $\begin{matrix} α = 0 + \sum_{i = 0}^{\infty} \frac{1}{2^{A (i) + 1}} . \end{matrix}$ Thus, in order to complete our proof, it is sufficient to prove that the function ψ which satisfies (†) and (‡) is in $⩽ (a^{'})$ .

We will now give an algorithm for computing a function ψ. It will be obvious from the way the algorithm works that this ψ indeed satisfies (†) and (‡).

Let $ψ (0) = 0$ . Assume that we have determined $ψ (n)$ and that $ψ (n) = {(0 . b_{1} \dots b_{k})}_{2}$ . By Lemma 4.5, we have $T_{0} : Q \to Q$ in $⩽ (a)$ such that $ψ (n) < T_{0} (ψ (n)) < α$ . Hence, there exists a unique $m \in N$ such that $T_{0} (ψ (n))$ can be written of the form $\begin{matrix} T_{0} (ψ (n)) = {(0 . b_{1} \dots b_{k})}_{2} + \frac{1}{2^{k + m}} + ε < α \end{matrix}$ where $ε < \frac{1}{2^{k + m}}$ . We compute this m (this can be done elementary in the rational number $T_{0} (ψ (n))$ ). Now, for some $i \in {1, \dots, m}$ we have $\begin{matrix} {(0 . b_{1} \dots b_{k})}_{2} + \frac{1}{2^{k + i}} < α \end{matrix}$ and $\begin{matrix} {(0 . b_{1} \dots b_{k})}_{2} + \frac{1}{2^{k + j}} > α \end{matrix}$ for all $j \in {1, \dots, i - 1}$ . We can find this i by using the Dedekind cut of α maximum m times (thus, we can find i by bounded primitive recursion). Now we can determine $ψ (n + 1)$ since $\begin{matrix} ψ (n + 1) = {(0 . b_{1} \dots b_{k})}_{2} + \frac{1}{2^{k + i}} . \end{matrix}$

The algorithm above shows that there exists a function $ϕ \in ⩽ (a)$ such that $ψ (n + 1) = ϕ (ψ (n))$ and $ψ (0) = 0$ . The algorithm consults the Dedekind cut of α. By Theorem 4.2, the Dedekind cut of α is in $⩽ (a)$ since α is in $⩽ {(a)}_{T}$ . The algorithm uses the function for $T_{0}$ . We have $T_{0} \in ⩽ (a)$ by Lemma 4.5. All other functions applied by the algorithm are elementary. Hence, the function ψ can be defined by a single application of primitive recursion over functions in $⩽ (a)$ . By Lemma 2.11, we have $ψ \in ⩽ (a^{'})$ . □

It is an open problem if the preceding theorem can be strengthen. We conjecture that the inclusion $\begin{matrix} ⩽ {(a)}_{T} \subseteq ⩽ {(a)}_{↑} \end{matrix}$ does not hold. Theorem 5.5.
$\begin{matrix} ⩽ {(a)}_{T} \subseteq ⩽ {(a^{'})}_{↓} . \end{matrix}$
Proof.
This is proof is symmetric to the proof of Theorem 5.4. □

6. General sum-approximations

An example that might help the reader to understand the next definition, follows immediately after the definition.

Definition 6.1.
Let $G : N \times N \to Q$ be such that, for each $b > 1$ , we have $\begin{matrix} G (b, i) = \frac{d_{i}}{b^{k_{i}}} \end{matrix}$ where $d_{i} \in {1, \dots, b - 1}$ and $k_{i} \in N$ and $0 < k_{i} < k_{i + 1}$ (for all $i \in N$ ). We say that G is a general sum-approximation from below of the real number α if there exists $a \in Z$ such that for all $b > 1$ we have $\begin{matrix} α = a + \sum_{i = 0}^{\infty} G (b, i) . \end{matrix}$ We say that G is a general sum-approximation from above of the real number α if there exists $a \in Z$ such that for all $b > 1$ we have $\begin{matrix} α = a - \sum_{i = 0}^{\infty} G (b, i) . \end{matrix}$

Let us study an example. The base 10 expansion of the well know number π starts by $3.1415926535897 \dots$ . Let $\hat{G}$ be the general sum-approximation of π from below, and let $\overset{ˇ}{G}$ be the general sum-approximation of π from above. Then, we have $\begin{array}{l} π & = 3 + \hat{G} (10, 0) + \hat{G} (10, 1) + \hat{G} (10, 2) + \hat{G} (10, 3) + \hat{G} (10, 4) + \hat{G} (10, 5) + \hat{G} (10, 6) + \dots \\ = 3 + \frac{1}{10^{1}} + \frac{4}{10^{2}} + \frac{1}{10^{3}} + \frac{5}{10^{4}} + \frac{9}{10^{5}} + \frac{2}{10^{6}} + \frac{6}{10^{7}} + \dots \end{array}$ and $\begin{array}{l} π & = 4 - \overset{ˇ}{G} (10, 0) - \overset{ˇ}{G} (10, 1) - \overset{ˇ}{G} (10, 2) - \overset{ˇ}{G} (10, 3) - \overset{ˇ}{G} (10, 4) - \overset{ˇ}{G} (10, 5) - \overset{ˇ}{G} (10, 6) - \dots \\ = 4 - \frac{8}{10^{1}} - \frac{5}{10^{2}} - \frac{8}{10^{3}} - \frac{4}{10^{4}} - \frac{7}{10^{6}} - \frac{3}{10^{7}} - \frac{4}{10^{8}} - \dots . \end{array}$ The base 3 expansion of π starts by $10.0102110122220102 \dots$ , and we have $\begin{array}{l} π & = 3 + \hat{G} (3, 0) + \hat{G} (3, 1) + \hat{G} (3, 2) + \hat{G} (3, 3) + \hat{G} (3, 4) + \hat{G} (3, 5) + \hat{G} (3, 6) + \hat{G} (3, 7) + \dots \\ = 3 + \frac{1}{3^{2}} + \frac{2}{3^{4}} + \frac{1}{3^{5}} + \frac{1}{3^{6}} + \frac{1}{3^{8}} + \frac{2}{3^{9}} + \frac{2}{3^{10}} + \frac{2}{3^{11}} + \dots \end{array}$ and $\begin{array}{l} π & = 3 - \overset{ˇ}{G} (3, 0) - \overset{ˇ}{G} (3, 1) - \overset{ˇ}{G} (3, 2) - \overset{ˇ}{G} (3, 3) - \overset{ˇ}{G} (3, 4) - \overset{ˇ}{G} (3, 5) - \overset{ˇ}{G} (3, 6) - \overset{ˇ}{G} (3, 7) - \dots \\ = 4 - \frac{2}{3^{1}} - \frac{1}{3^{2}} - \frac{2}{3^{3}} - \frac{1}{3^{5}} - \frac{1}{3^{6}} - \frac{2}{3^{7}} - \frac{1}{3^{8}} - \frac{2}{3^{13}} - \dots . \end{array}$
Definition 6.2.
For any class of functions $S$ , let $S_{g ↑}$ denote the class of irrational numbers that have a general sum-approximation from below in $S$ ; let $S_{g ↓}$ denote the class of irrationals number that have a general sum-approximation from above in $S$ .

This proof of the next theorem is straightforward, and we omit the details. Theorem 6.3.
A sum approximation from below (above) of irrational number α is elementary in a general sum-approximation from below (above) of α. Thus $\begin{matrix} ⩽ {(a)}_{g ↑} \subseteq ⩽ {(a)}_{↑} and ⩽ {(a)}_{g ↓} \subseteq ⩽ {(a)}_{↓} . \end{matrix}$
Theorem 6.4.
The Dedekind cut of an irrational number α is elementary in a general sum-approximation (from above or below) of α. Thus $\begin{matrix} ⩽ {(a)}_{g ↑} \subseteq ⩽ {(a)}_{D} and ⩽ {(a)}_{g ↓} \subseteq ⩽ {(a)}_{D} . \end{matrix}$
Proof.
Assume that $\begin{matrix} α = a + \sum_{i = 0}^{\infty} G (b, i) \end{matrix}$ where G is a general sum-approximation from below. We can w.l.o.g. assume $0 < α < 1$ , that is, we assume that $a = 0$ . We define the function $ψ : N \to N$ by $ψ (b) = d$ where d is the unique natural number such that we have $\begin{matrix} α = \frac{d}{b + 2} + α^{'} and α^{'} < \frac{1}{b + 2} \end{matrix}$ for some $α^{'} \in R$ (thus, $ψ (b)$ yields the first digit in the base $b + 2$ expansion of the fractional part of α). It is easy to see that ψ can be computed elementary in G: simply use the rational number $G (b + 2, 0)$ to find $ψ (b)$ . Now, for any rational number $\frac{m}{n}$ where $m \in Z$ and $n \in N$ let $\begin{matrix} D (\frac{m}{n}) = \{\begin{matrix} 0 & if \frac{m}{n} ⩽ 0, \\ 1 & if \frac{m}{n} ⩾ 1, \\ 0 & if m ⩽ ψ (n - 2) and 0 < \frac{m}{n} < 1, \\ 1 & otherwise (that is, if m > ψ (n - 2) and 0 < \frac{m}{n} < 1) . \end{matrix} \end{matrix}$ Now, D is the Dedekind cut for α, and D is elementary in G. The proof that a Dedekind cut is elementary in a general sum-approximation from above is symmetric. □
Theorem 6.5.
Let $\hat{G}$ and $\overset{ˇ}{G}$ be general sum-approximations, respectively form below and above, of α. There exists a trace function T for α that is elementary in ${\hat{G}, \overset{ˇ}{G}}$ . Hence, we have $\begin{matrix} ⩽ {(a)}_{g ↑} \cap ⩽ {(a)}_{g ↓} \subseteq ⩽ {(a)}_{T} . \end{matrix}$
Proof.
We can w.l.o.g. assume $0 < α < 1$ , that is, we assume that $\begin{matrix} α = 0 + \sum_{i = 0}^{\infty} \hat{G} (b, i) and α = 1 - \sum_{i = 0}^{\infty} \overset{ˇ}{G} (b, i) \end{matrix}$ for any $b > 1$ . Let D be the Dedekind cut for α. For any rational number $\frac{m}{n}$ where $m \in Z$ and $n \in N$ let $\begin{matrix} T (\frac{m}{n}) = \{\begin{matrix} \hat{G} (2 n, 0) + \hat{G} (2 n, 1) & if D (\frac{m}{n}) = 0, \\ 1 - (\overset{ˇ}{G} (2 n, 0) + \overset{ˇ}{G} (2 n, 1)) & otherwise . \end{matrix} \end{matrix}$ We know by Theorem 6.4 that D is elementary in ${\hat{G}, \overset{ˇ}{G}}$ . Thus, it is obvious that also T is elementary in ${\hat{G}, \overset{ˇ}{G}}$ . It remains to argue that T is a trace function for α.

Let a be an integer and let b be a natural number strictly greater than 1. If $\frac{a}{b} > \hat{G} (b, 0)$ , the we will also have $\frac{a}{b} > α$ . Hence, we have $\begin{matrix} \frac{a}{b} < α \Rightarrow \frac{a}{b} ⩽ \hat{G} (b, 0) \end{matrix}$ for any $b > 1$ . By a symmetric argument, we have $\begin{matrix} \frac{a}{b} > α \Rightarrow \frac{a}{b} ⩾ 1 - \overset{ˇ}{G} (b, 0) \end{matrix}$ for any $b > 1$ . Now, let $\frac{m}{n}$ be a rational number where $m \in Z$ and $n \in N$ (so n is different from 0 but may be 1). If $\frac{m}{n} < α$ , we have $\begin{matrix} \frac{m}{n} = \frac{2 m}{2 n} ⩽ \hat{G} (2 n, 0) < \hat{G} (2 n, 0) + \hat{G} (2 n, 1) = T (\frac{m}{n}) < α . \end{matrix}$ If $\frac{m}{n} > α$ , we have $\begin{matrix} \frac{m}{n} = \frac{2 m}{2 n} ⩾ 1 - \overset{ˇ}{G} (2 n, 0) > 1 - (\overset{ˇ}{G} (2 n, 0) + \overset{ˇ}{G} (2 n, 1)) = T (\frac{m}{n}) > α . \end{matrix}$ This shows that T is a trace function for α. □
Theorem 6.6.
$\begin{matrix} ⩽ {(a)}_{T} \subseteq ⩽ {(a^{'})}_{g ↑} . \end{matrix}$
Proof.
This proof is a straightforward generalisation of the proof of Theorem 5.4.

The proof of Theorem 5.4 describes an algorithm that computes a sum approximation in base 2 from a given trace function. Just observe that this algorithm easily can be modified to compute a sum approximation in an arbitrary base b (where b is input). Such a modification will not increase the computational complexity of the algorithm significantly and, thus, a general sum-approximation of an irrational number α can be defined by one application of (unbounded) primitive recursion over a trace function for α. □
Theorem 6.7.
$\begin{matrix} ⩽ {(a)}_{T} \subseteq ⩽ {(a^{'})}_{g ↓} . \end{matrix}$
Proof.
This proof is symmetric to the proof of Theorem 6.6. □

7. Continued fractions

We repeat some standard definitions. For more on continued fractions, see Khintchine [4] or Olds [20].

Definition 7.1.
Let $a_{0}, a_{1}, a_{2}, \dots$ be a sequence of integers where $a_{i} > 0$ when $i > 0$ (thus $a_{0}$ is the only number in the sequence that may be something else than a positive integer). We define the continued fraction $[a_{0}; a_{1}, a_{2}, \dots]$ by $\begin{matrix} [a_{0}; a_{1}, a_{2}, \dots] = a_{0} + \frac{1}{a_{1} + \frac{1}{a_{2} + \frac{1}{\dots}}} . \end{matrix}$ We define the nth convergent $[a_{0}; a_{1}, \dots, a_{n}]$ of the continued fraction $[a_{0}; a_{1}, a_{2}, \dots]$ by $\begin{matrix} [a_{0}; a_{1}, \dots, a_{n}] = a_{0} + \frac{1}{a_{1} + \frac{1}{\dots + \frac{1}{a_{n}}}} . \end{matrix}$

Each irrational number has one, and only one, continued fraction, and obviously we have $\begin{matrix} [a_{0}; a_{1}, a_{2}, \dots] = lim_{n \to \infty} [a_{0}; a_{1}, \dots, a_{n}] . \end{matrix}$

The next lemma states some basic facts. The proofs can be found in any elementary textbook on continued fractions.
Lemma 7.2.
Let $α = [a_{0}; a_{1}, \dots]$ be an irrational number, and let the sequences (of natural numbers) $p_{- 1}, p_{0}, p_{1}, p_{2}, \dots$ and $q_{- 1}, q_{0}, q_{1}, q_{2}, \dots$ be given by the equations
$p_{- 1} = 1$ and $p_{0} = a_{0}$ and $p_{k + 1} = a_{k + 1} p_{k} + p_{k - 1}$ (for $k ⩾ 0$ ),

$q_{- 1} = 0$ and $q_{0} = 1$ and $q_{k + 1} = a_{k + 1} q_{k} + q_{k - 1}$ (for $k ⩾ 0$ ) .
Then
$\begin{matrix} \frac{p_{i}}{q_{i}} = [a_{0}; a_{1}, \dots, a_{i}], \end{matrix}$

if $k + 1$ is even, then $\begin{matrix} a_{k + 1} = (μ a) [\frac{p_{k - 1} + (a + 1) p_{k}}{q_{k - 1} + (a + 1) q_{k}} > α], \end{matrix}$

if $k + 1$ is odd, then $\begin{matrix} a_{k + 1} = (μ a) [\frac{p_{k - 1} + (a + 1) p_{k}}{q_{k - 1} + (a + 1) q_{k}} < α], \end{matrix}$

$\begin{matrix} \frac{p_{0}}{q_{0}} < \frac{p_{2}}{q_{2}} < \frac{p_{4}}{q_{4}} < \dots < α < \dots < \frac{p_{5}}{q_{5}} < \frac{p_{3}}{q_{3}} < \frac{p_{1}}{q_{1}}, \end{matrix}$

$\begin{matrix} \frac{1}{q_{i} (q_{i} + q_{i + 1})} < | α - \frac{p_{i}}{q_{i}} | < \frac{1}{q_{i} q_{i + 1}}, \end{matrix}$

for any $k ⩾ 0$ , we have $\begin{matrix} q_{k} ⩾ k, \end{matrix}$

$\frac{p_{k}}{q_{k}}$ is a best approximation to α, that is, for any $n \in N ∖ {0}$ and any $m \in Z$ $\begin{matrix} n < q_{k} \Rightarrow | α - \frac{p_{k}}{q_{k}} | < | α - \frac{m}{n} | . \end{matrix}$

Definition 7.3.
Let $λ x . a_{x}$ denote the function that yields the xth element of the continued fraction $[a_{0}; a_{1}, \dots]$ (thus, we have e.g. $(λ x . a_{x}) (17) = a_{17}$ ). We will identify $λ x . a_{x}$ with the continued fraction $[a_{0}; a_{1}, \dots]$ , and we call $λ x . a_{x}$ a continued fraction.

For any class of functions $S$ , let $S_{[]}$ denote the class of irrational numbers that have a continued fraction in $S$ .
Theorem 7.4.
A trace function for an irrational number α is elementary in a continuous fraction for α. Thus $\begin{matrix} ⩽ {(a)}_{[]} \subseteq ⩽ {(a)}_{T} . \end{matrix}$
Proof.
Let $[a_{0}; a_{1}, \dots]$ be the continued fraction for α, and let $T : Q \to Q$ be the function $\begin{matrix} T (w) = [a_{0}; a_{1}, \dots, a_{N (w) + 1}] \end{matrix}$ where $N (w)$ denotes the least $n \in N$ such that w can be written of the form $w = \frac{m}{n}$ (for some $m \in Z$ ). We will prove that T is a trace function for α and that T is elementary in $λ x . a_{x}$ .

Let $p_{0}, p_{1}, p_{2}, \dots$ and $q_{0}, q_{1}, q_{2}, \dots$ be given by the equations in Lemma 7.2. We will prove by induction on k that we have $\begin{matrix} () & p_{k} < 2^{k} \prod_{i ⩽ k} (| a_{i} | + 1) and q_{k} ⩽ 2^{k} \prod_{i ⩽ k} (| a_{i} | + 1) \end{matrix}$ for any $k ⩾ 0$ . We have $\begin{matrix} p_{0} = a_{0} < 2^{0} \prod_{i ⩽ 0} (| a_{i} | + 1) \end{matrix}$ and $\begin{matrix} p_{1} = a_{1} p_{0} + p_{- 1} = a_{1} a_{0} + 1 < 2^{1} \prod_{i ⩽ 1} (| a_{i} | + 1) . \end{matrix}$ Furthermore, by our induction hypothesis, we have $\begin{array}{l} p_{k + 1} & = a_{k + 1} p_{k} + p_{k - 1} < a_{k + 1} 2^{k} \prod_{i ⩽ k} (| a_{i} | + 1) + 2^{k - 1} \prod_{i ⩽ k - 1} (| a_{i} | + 1) \\ < 2^{k} \prod_{i ⩽ k + 1} (| a_{i} | + 1) + 2^{k} \prod_{i ⩽ k + 1} (| a_{i} | + 1) = 2^{k + 1} \prod_{i ⩽ k + 1} (| a_{i} | + 1) . \end{array}$ A similar induction yields $q_{k} ⩽ 2^{k} \prod_{i ⩽ k} (| a_{i} | + 1)$ . This proves (∗).

By Lemma 7.2(1), we have $\begin{matrix} T (w) = [a_{0}; a_{1}, \dots, a_{N (w) + 1}] = \frac{p_{N (w) + 1}}{q_{N (w) + 1}} . \end{matrix}$ The function $2^{k} (\prod_{i ⩽ k} | a_{i} | + 1)$ is elementary in $λ x . a_{x}$ . Thus, by the equations in Lemma 7.2 and (∗), we can compute T by bounded simultaneous recursion over functions elementary in $λ x . a_{x}$ . Bounded simultaneous recursion can be reduced to bounded primitive recursion (modulo elementary operations). Thus, T is elementary in $λ x . a_{x}$ .

It remains to prove that T is a trace function for α. Let n be the least natural number such that the rational number w can be written of the form $w = \frac{m}{n}$ where $m \in Z$ . Then we have $T (w) = \frac{p_{n + 1}}{q_{n + 1}}$ . By Lemma 7.2(6), we have $n < n + 1 ⩽ q_{n + 1}$ , and then, by Lemma 7.2(7), we have $\begin{matrix} | α - T (w) | = | α - \frac{p_{n + 1}}{q_{n + 1}} | < | α - \frac{m}{n} | = | α - w | . \end{matrix}$ Thus, T is a trace function for α. □
Theorem 7.5.
$\begin{matrix} ⩽ {(a)}_{T} \subseteq ⩽ {(a^{'})}_{[]} . \end{matrix}$
Proof.
Let $α \in ⩽ {(a)}_{T}$ . We can w.l.o.g. assume $0 < α < 1$ . We will prove that $α \in ⩽ {(a^{'})}_{[]}$ .

Let f be an honest function such that $a = deg (f)$ . Let $n, \hat{n}, m, \hat{m} \in N$ be such that $\begin{matrix} \frac{m}{n} < α < \frac{\hat{m}}{\hat{n}} . \end{matrix}$ We will prove that there exist $a, ℓ \in N$ such that $a ⩽ f^{ℓ + 1} (max (n, \hat{n}, m, \hat{m}))$ and $\begin{matrix} () & \frac{m}{n} < \frac{\hat{m} + a m}{\hat{n} + a n} < α < \frac{m + a \hat{m}}{n + a \hat{n}} < \frac{\hat{m}}{\hat{n}} . \end{matrix}$

By Lemma 4.6, α is $⩽ (a)$ -irrational. Thus, by Lemma 3.3 we have $ℓ \in N$ such that $\begin{matrix} | α - \frac{\hat{m}}{\hat{n}} | > \frac{1}{f^{ℓ} (\hat{n})} . \end{matrix}$ Let $a = f^{ℓ + 1} (max (n, \hat{n}, m, \hat{m}))$ . Then $\begin{array}{l} \frac{\hat{m}}{\hat{n}} - \frac{m + a \hat{m}}{n + a \hat{n}} & = \frac{\hat{m} (n + a \hat{n}) - \hat{n} (m + a \hat{m})}{\hat{n} (n + a \hat{n})} = \frac{\hat{m} n - \hat{n} m}{\hat{n} (n + a \hat{n})} \\ < \frac{\hat{m} n - \hat{n} m}{a} = \frac{\hat{m} n - \hat{n} m}{f^{ℓ + 1} (max (n, \hat{n}, m, \hat{m}))} \\ < \frac{\hat{m} n - \hat{n} m}{(\hat{m} n - \hat{n} m) f^{ℓ} (max (n, \hat{n}, m, \hat{m}))} \\ = \frac{1}{f^{ℓ} (max (n, \hat{n}, m, \hat{m}))} ⩽ \frac{1}{f^{ℓ} (\hat{n})} < \frac{\hat{m}}{\hat{n}} - α . \end{array}$ This shows that $\frac{m + a \hat{m}}{n + a \hat{n}}$ lies between α and $\frac{\hat{m}}{\hat{n}}$ . A symmetric argument will show that $\frac{\hat{m} + a m}{\hat{n} + a n}$ lies between α and $\frac{m}{n}$ . This concludes the proof of (∗).

Let $α = [a_{0}; a_{1}, a_{2}, \dots]$ . When we know the numbers in the sequence $a_{0}, a_{1}, a_{2}, \dots, a_{n}$ , we can use the recursive equations in Lemma 7.2 to compute $p_{k}$ and $q_{k}$ for any $k ⩽ n$ . Moreover, by clause (2) and (3) of Lemma 7.2, we have $\begin{matrix} (* *) & a_{k + 1} = \{\begin{matrix} (μ a) [\frac{p_{k - 1} + (a + 1) p_{k}}{q_{k - 1} + (a + 1) q_{k}}] > α & if k + 1 is even, \\ (μ a) [\frac{p_{k - 1} + (a + 1) p_{k}}{q_{k - 1} + (a + 1) q_{k}}] < α & if k + 1 is odd . \end{matrix} \end{matrix}$ Let D be the Dedekind cut for α. By (∗) and (∗∗), we have $\begin{matrix} a_{k + 1} = \{\begin{matrix} (μ a ⩽ f^{ℓ + 1} (max (p_{k - 1}, q_{k - 1}, p_{k}, q_{k}))) \\ [D (\frac{p_{k - 1} + (a + 1) p_{k}}{q_{k - 1} + (a + 1) q_{k}}) = 1] if k + 1 is even, \\ (μ a ⩽ f^{ℓ + 1} (max (p_{k - 1}, q_{k - 1}, p_{k}, q_{k}))) \\ [D (\frac{p_{k - 1} + (a + 1) p_{k}}{q_{k - 1} + (a + 1) q_{k}}) = 0] if k + 1 is odd . \end{matrix} \end{matrix}$ The Dedekind cut D is in $⩽ (a)$ by Theorem 4.2. Moreover, $⩽ (a)$ is closed under the bounded μ-operator. Thus, by the equations for $p_{k}$ , $q_{k}$ in Lemma 7.2 and the equation above for $a_{k + 1}$ , we can compute the function $λ x . a_{x}$ by one application of (unbounded) simultaneous recursion over functions in $⩽ (a)$ . One application of simultaneous recursion can be reduced to one application of primitive recursion (modulo elementary operations). Thus, by Lemma 2.11, $λ x . a_{x}$ is in $⩽ (a^{'})$ . Thus, $α \in ⩽ {(a^{'})}_{[]}$ . □

It is an open problem if the preceding theorem can be strengthen. We conjecture that the inclusion $\begin{matrix} ⩽ {(a)}_{T} \subseteq ⩽ {(a)}_{[]} \end{matrix}$ does not hold.
8. The big picture

Definition 8.1.

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 2.10).

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.)

Lemma 8.2.

For any subrecursive class $S$ , there exists an honest degree a such that $S \subseteq ⩽ (a)$ .

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. Let $a = deg (f)$ . Then, a is an honest degree. $\begin{matrix} (Claim) & x ⩾ e \Rightarrow f (x) ⩾ μ t [T_{1} (σ (e), x, t)] . \end{matrix}$

We prove the claim. Assume $x ⩾ e$ . Then, we have $\begin{array}{l} μ t [T_{1} (σ (e), x, t)] & = μ t [(\exists t_{1}) [T_{1} (e_{σ}, e, t_{1}) \land T_{1} (U (t_{1}), x, t)]] \\ ⩽ μ t [(\exists t_{1} ⩽ t) [T_{1} (e_{σ}, e, t_{1}) \land (\exists t_{2} ⩽ t) T_{1} (U (t_{1}), x, t_{2})]] \\ ⩽ μ t [(\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})]]] \\ ⩽ f (x) . \end{array}$ This proves the claim.

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. Thus, $S$ is a subset of $⩽ (a)$ . □

Corollary 8.3.

For any subrecursive class $S$ that is closed under elementary operations, we have $\begin{matrix} S_{T} \subset S_{D} \subset S_{C} . \end{matrix}$

Proof.

We have $S_{T} \subseteq S_{D} \subseteq S_{C}$ by Theorem 4.2.

We prove that $S_{C} ⊈ S_{D}$ . By Lemma 8.2, we have an honest degree a such that $\begin{matrix} ⩽ (0) \subseteq S \subseteq ⩽ (a) . \end{matrix}$ By Theorem 4.4, we have α such that $α \in ⩽ {(0)}_{C}$ and $α \notin ⩽ {(a)}_{D}$ . It follows that $α \in S_{C}$ and $α \notin S_{D}$ and, thus, $S_{C}$ cannot be a subset of $S_{D}$ . The proof that $S_{D} ⊈ S_{T}$ is similar. Use Theorem 4.8 in the place of Theorem 4.4. □

Corollary 8.4.

Let $S$ be any subrecursive class that is closed under the elementary operations. We have $\begin{matrix} (S_{↓} \cap S_{D}) ∖ S_{↑} \neq \emptyset and (S_{↑} \cap S_{D}) ∖ S_{↓} \neq \emptyset \end{matrix}$ and, thus, we also have $\begin{matrix} S_{D} ⊈ S_{↑} and S_{D} ⊈ S_{↓} and S_{↑} ⊈ S_{↓} and S_{↓} ⊈ S_{↑} . \end{matrix}$

Proof.

By Lemma 8.2, we have an honest degree a such that $\begin{matrix} ⩽ (0) \subseteq S \subseteq ⩽ (a) . \end{matrix}$ By Theorem 5.2, we have α such that $α \notin ⩽ {(a)}_{↑}$ and $α \in ⩽ {(0)}_{↓} \cap ⩽ {(0)}_{D}$ . Thus, $α \notin S_{↑}$ and $α \in S_{↓} \cap S_{D}$ . A symmetric argument shows that there exists α such that $α \notin S_{↓}$ and $α \in S_{↑} \cap S_{D}$ . Use Theorem 5.3 in place of Theorem 5.2. □

Corollary 8.5.

For any subrecursive class $S$ that is closed under primitive recursive operations, we have $\begin{matrix} S_{g ↓} \cap S_{g ↑} = S_{T} = S_{[]} . \end{matrix}$

Proof.

Every class closed under primitive recursive operations is also closed under elementary operations. Hence, by Theorem 6.5, we have $S_{g ↓} \cap S_{g ↑} \subseteq S_{T}$ and, by Theorem 7.4, we have $S_{[]} \subseteq S_{T}$ .

If we look at the proof of Theorem 7.5, we see that a continuous fraction for an irrational number α can be defined primitive recursively over a trace function for α. So, the proof of Theorem 7.5 shows that $S_{T} \subseteq S_{[]}$ . Likewise, the proofs of Theorem 6.6 and Theorem 6.7 show that $S_{T} \subseteq S_{g ↑} \cap S_{g ↓}$ . □

We leave the proof of the next two corollaries to the reader.

Corollary 8.6.

For any subrecursive class $S$ that is closed under elementary operations, we have $\begin{matrix} S_{g ↓} \subseteq S_{↓} and S_{g ↑} \subseteq S_{↑} . \end{matrix}$

Corollary 8.7.

For any subrecursive class $S$ that is closed under primitive recursive operations, we have $\begin{matrix} S_{T} \subseteq S_{↓} \cap S_{↑} \cap S_{D} . \end{matrix}$

Corollary 8.8.

For any subrecursive class $S$ that is closed under elementary operations, we have $\begin{matrix} S_{g ↓} \subset S_{D} and S_{g ↑} \subset S_{D} . \end{matrix}$

Proof.

By Theorem 6.4, we have $\begin{matrix} S_{g ↓} \subseteq S_{D} and S_{g ↑} \subseteq S_{D} . \end{matrix}$

Assume $S_{D} \subseteq S_{g ↓}$ . Then, by Corollary 8.6, we have $S_{D} \subseteq S_{↓}$ . This contradicts Corollary 8.4. Thus, we conclude that $S_{g ↓} \subset S_{D}$ . A symmetric argument shows that $S_{g ↑}$ is a strict subset of $S_{D}$ . □

There is a lot of open problems present. For our conjectures on some of these problems, see the Venn diagram in Fig. 2.

Finally, we will see that our landscape looks very different if we restrict our attention to the $S$ -irrational numbers. Then the strange animal in Fig. 2 degenerates to what appears to be its nose.

Theorem 8.9.

Let $S$ be a subrecursive class that is closed elementary operations. Let α be an $S$ -irrational number in $S_{C}$ . Then, we have $α \in S_{T}$ .

Proof.

Let $ν : N \to N$ be such that $\begin{matrix} (†) & | α - \frac{m}{n} | > \frac{1}{ν (n)} \end{matrix}$ for any $m \in Z$ and $n \in N ∖ {0}$ . There is such a ν in $S$ since α is $S$ -irrational. Let $C \in S$ be a Cauchy sequence for α. Then, we have $\begin{matrix} (*) & | α - C (ν (n)) | < \frac{1}{2^{ν (n)}} < \frac{1}{ν (n)} < | α - \frac{m}{n} | . \end{matrix}$ The first inequality of (∗) holds since C is a Cauchy sequence; the last inequality of (∗) holds by (†). Now, (∗) states that $C (ν (n))$ lies strictly closer to α than $\frac{m}{n}$ (for any $m \in Z$ ). Thus, let $T (q) = C (ν (n))$ where n is the least natural number such that $q = \frac{m}{n}$ (for some $m \in Z$ ). Then, T is a trace function for α. It is easy to see that T is in $S$ when C and ν are in $S$ . Hence, we conclude that $α \in S_{T}$ . □

The next couple of corollaries follow straightforwardly from the preceding theorem, Lemma 4.6 and Corollary 8.5.

Corollary 8.10.

Let $S$ be a subrecursive class $S$ that is closed under elementary operations, and let $α \in S_{C}$ . Then, α is $S$ -irrational iff $α \in S_{T}$ .

Corollary 8.11.

Let $S$ be a subrecursive class $S$ that is closed under primitive recursive operations, and let $α \in S_{C}$ . Then, α is $S$ -irrational iff $α \in S_{T}$ iff $α \in S_{[]}$ iff $α \in S_{g ↑} \cap S_{g ↓}$ .

Definition 8.12.

Let $S$ be a subrecursive class, and let $S_{∙}$ be a class of real numbers. Then, $\begin{matrix} S_{∙}^{i} = {α ∣ α \in S_{∙} and α is S -irrational} . \end{matrix}$

Corollary 8.13.

Let $S$ be a subrecursive class that is closed under elementary operations. Then, $S_{C}^{i} = S_{D}^{i} = S_{T}^{i}$ .

Proof.

We know that $S_{C} \subseteq S_{D} \subseteq S_{T}$ . Hence, $S_{C}^{i} \subseteq S_{D}^{i} \subseteq S_{T}^{i}$ . By Theorem 8.9, $S_{T}^{i} \subseteq S_{C}^{i}$ . Hence, $S_{C}^{i} = S_{D}^{i} = S_{T}^{i}$ . □

Corollary 8.14.

Let $S$ be a subrecursive class that is closed under the primitive recursive operations. Then, $S_{C}^{i} = S_{D}^{i} = S_{T}^{i} = S_{↑}^{i} = S_{↓}^{i} = S_{g ↑}^{i} = S_{g ↓}^{i} = S_{[]}^{i}$ .

Proof.

Each of the classes $S_{C}$ , $S_{D}$ , $S_{T}$ , $S_{↑}$ , $S_{↓}$ , $S_{g ↑}$ , $S_{g ↓}$ , $S_{[]}$ is a subset of $S_{C}$ and a superset of $S_{T}$ . By Theorem 8.9, $S_{C}^{i}$ is contained in $S_{T}^{i}$ . □

References

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

S.B.

Cooper, Computability Theory, CRC Press, Boca Raton, 2004.

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

A.Y.

Khintchine, Continued Fractions, P. Noordhoff, Ltd, Groningen, The Netherlands, 1963. (Translated by Peter Wynn.)

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, A jump operator on honest subrecursive degrees, Archive for Mathematical Logic 37 (1998), 105–125. doi:10.1007/s001530050086.

10.

Kristiansen, Low_n, high_n, and intermediate subrecursive degrees, in: Combinatorics, Computation and Logic,

C.S.

Calude and

M.J.

Dinneen, eds, Springer, Singapore, 1999, pp. 286–300.

11.

Kristiansen, Subrecursive degrees and fragments of Peano arithmetic, Archive for Mathematical Logic 40 (2001), 365–397. doi:10.1007/PL00003845.

12.

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), 2012, pp. 255–279.

13.

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.

14.

Leary and

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

15.

R.S.

Lehman, On primitive recursive real numbers, Fundamenta Mathematica 49(2) (1961), 105–118.

16.

Machtey, Augmented loop languages and classes of computable functions, Journal of Computer and System Sciences 6 (1972), 603–624. doi:10.1016/S0022-0000(72)80032-1.

17.

Machtey, The honest subrecursive classes are a lattice, Information and Control 24 (1974), 247–263. doi:10.1016/S0019-9958(74)80039-2.

18.

Machtey, On the density of honest subrecursive classes, Journal of Computer and System Sciences 10 (1975), 183–199. doi:10.1016/S0022-0000(75)80039-0.

19.

A.R.

Meyer and

D.M.

Ritchie, A classification of the recursive functions, Zeitschrift für mathematische Logik und Grundlagen der Mathematik 18 (1972), 71–82. doi:10.1002/malq.19720180405.

20.

C.D.

Olds, Continued Fractions, New Mathematics Library, Mathematical Association of America, Random House, 1963.

21.

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

22.

H.E.

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

23.

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.

24.

Skordev,

Weiermann and

Georgiev,

M^{2}

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

25.

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

26.

Verbeek, Primitiv-rekursive Grzegorczyk-Hierarchien, Dissertation, Bonn University, 1978.

27.

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