RECURSIVE ANALYSIS
BY
R. L. GOODSTEIN
The University of Leicester
1961
NORTH-HOLLAND PUBLISHING COMPANY
AMSTERDAM

No part of this book may be reproduced in any
form by print, microfilm or any other means
without written permission from the publisher
PBINTED IN THE NETHERLANDS

PREFACE
There are several systems of constructive function theory; some,
like intuitionist analysis are based on a new logic, some study
constructive objects, recursive real numbers for example, by the
methods of classical analysis, and some seek to translate a portion
of classical analysis into free variable formulae by means of
functional. The system described in this book differs from all of these.
It is based on primitive recursive arithmetic and seeks to build
up a function theory of the rational field which in some respects
closely resembles classical analysis and in others is closer to
intuitionist analysis. All proofs in recursive analysis are formalisable
in the equation calculus, the system of recursive arithmetic described
in my book Recursive Number Theory, but the present work may
be read without a detailed knowledge of recursive arithmetic.
I am again deeply indebted to Professor Heyting for his very
kind encouragement, to Mr. John Hooley for generous help in
reading the proofs, and to the compositors and printers of the North
Holland Publishing Company for the pleasure they have given me
by the excellence of their work.
R. L. Goodstein
The University, Leicester, England

SYMBOLS
c, Cf, ci 39 N(k),Nf(k) 9
c*» 61 Nf(k,m) 10
C(k,x,y) 39 N(k, x), Nf(k, x) ... 41
cos (n, x) 99 (i 3
d, df 57 0(k) 8
^ 3 (p,q)lr 5
E{n,x) 96 [pjq] 7
Z1 57 Bf 10
{f(n)} 23 sin (n, x) 99
q>r{n) 33 T 4
If(n, a,b) 88 tan (n, x) 104
log (n, x) 97 Tba 107
M{k),Mt{k) 9 co 106

Chapter I
RECURSIVE CONVERGENCE
Primitive and general recursive functions. Recursive arithmetic
and its extensions. Recursive convergence and relative convergence.
The reduced sequence. Recursive limits and tests for recursive
convergence. Primitive and general recursive real numbers.
1 Recursive analysis is a free variable theory of functions in
a rational field, founded on recursive arithmetic. It involves no
logical presuppositions and proceeds from definition to theorem
by means of derivation schemata alone.
The elementary formulae of recursive arithmetic are equations
between terms, and the class of formulae is constructed from the
elementary formulae by the operations of the propositional calculus.
The terms are the free numeral variables, the sign 0 and the signs
for functions. The function signs include the sign S(x) for the
successor function (so that S(x) plays the part of x + 1 in elementary
algebra) and signs for functions introduced by recursion. The
derivation rules are taken to be sufficient to establish the universally
valid sentences of the propositional calculus, and include a schema
permitting the substitution of terms for variables, the schema
for equality
o = 6-*{j/(o)-*j/(6)},
and the induction schema
j/(0), sf(n) -» sf{S{n))
the schemata for explicit definition of functions for any number
of arguments, and finally schemata for definition by recursion.
The simplest definition schema for recursion, the schema of
primitive recursion, is
f(0,a) = »(a), f{S{n),a) = p{n,a, f(n, a)).
1

2
RECURSIVE CONVERGENCE
Specifically this schema defines f(n, a) by primitive recursion from
the functions a and (S. We take as initial primitive recursive
functions the successor function S(x), the identity function I(x), defined
explicitly by the equation I(x) = x, and the zero function Z(x)
defined by Z(x) = 0. A function is said to be primitive recursive if
it is an initial function or is defined from primitive recursive
functions by substitution or by primitive recursion.
1,1 In this work we shall be principally concerned with primitive
recursive functions. Without changing the character of the system
we shall build, the class of functions could be enlarged to include
for instance multiply recursive functions and even certain ordinal
recursive functions (of ordinal not exceeding a)a'a' at the present
state of knowledge). The system could not however be enlarged to
admit the class of functions which has played so important a part
in foundation researches, the class of quasi- (or general) recursive
functions, without changing the character of the system entirely.
A quasi-recursive function is defined by a system of equations (on
the right hand sides of which we may suppose only numerals or
primitive recursive functions appear) from which, by substitution,
the value of the defined function may be derived for each assigned
set of values of the arguments. The left-hand side of the equations
may contain, however, in addition to the function being defined,
auxiliary functions, about which we may have only incomplete
information. Consider for instance the set of equations x)
rt*, y) = U x(x>n)
n<y
r(Sz, 0,y) = y
f{x) = r{n{x, y), n{x, Sy), y),
where
IT x(x> n)=l, IT X(x> n) = (TI X(z> n)}-X(x, y) and x(x, n)
n<0 n<Sv n<v
is a primitive recursive function for which (in some sense which
remains to be considered) it is known that for each x there is a
y for which %{x, y) = 0. Then these equations define f(x) as a quasi-
x) cf. S. C. Kleene [2] pp. 279-280.

RECURSIVE CONVERGENCE
3
recursive function. To show this we have to consider the way in
which the values of f(x) may be derived from the equations. For
the purpose of illustration let us suppose that for some given value
of x, say x = 3, the first value of y for which x(x> y) vanishes is
y = 7. Then, keeping x=3, we see that
«(3,0), w(3, 1), n(3, 2), ...,w(3, 7)
are all greater than zero, but n(3, 8) = 0. The auxiliary function
r(u, v, y) is defined only for values of u greater than zero and for
v = 0; thus /(3) can be evaluated only when we find a y for which
n(x, y)>0 and n{x, Sy) = 0 and, as we have supposed, this occurs
when y= 7 (and not for any other value of y), showing that /(3)= 7.
This illustrates the fact that to determine the value of f(x), we
must first find the value of y for which %(x, y) = 0.
In the definition of a quasi-recursive function no limitation is
imposed upon the way in which we show that, for each x, there
is a y for which %(x, y) = 0; we may for instance establish the
existence of y by a proof in some formal system that the assumption
that x(x, y)>0 for all y leads to a contradiction. Such a proof may
provide us with no means of finding the y in question and therefore
no means of finding f(x); we may go on calculating the values of
X(x, y) for greater and greater values of y for untold time without
finding the y for which %(x, y) = 0. By confining our considerations
to primitive recursive functions we are assured that the values
of all functions in the system may be determined in a preassignable
number of steps.
The most appropriate system for utilising quasi-recursive
functions would be, not a free variable system, but one which contained
an existential operator "3"", and a minimal operator "ft" which
selected the least of a given set of values. From an existential
theorem
(Sy) B(x, y)
the minimal operator derives a function f(x) such that
f(x) = (fty) R(x, y).
If B(x, y) is a primitive recursive relation then f(x), defined by

4
RECURSIVE CONVERGENCE
the minimal operator may be shown to be quasi-recursive; in
fact the system of equations considered above is an instance of
this. For future reference we list some further important properties
of quasi-recursive functions and relations. x)
There is a primitive recursive function T(z, x, y) such that for
z=0, 1, 2, ..., (Sy)T(z, x, y) is an enumeration of all predicates of
the form (Sy)R(x, y) with recursive R. It follows that the class
of predicates of the form {Sy)R(x, y) is the same whether R is
quasi-recursive, or restricted to primitive recursive relations.
For any given R let r be a value of z for which
(Zy)R(x,y)^(Zy)T(r,x,y)
(where <—> denotes equivalence of relations) and therefore
(Sy)R(r,y)^(Sy)T(r,r,y)
and therefore (Sy)R(r, y) is not equivalent to (y) ~T(r, r, y), and
(taking ~ 8 for R, and s for r)
(y)S(s, y) <-> (y) ~ T(s, s, y)
so that
(y)S(s, y) is not equivalent to (Sy)T(s, s, y).
Given any quasi-recursive predicate R(x) let R(x, y) denote the
predicate R(x) &y = y so that R(x, y) is also quasi-recursive and
R(x) <-> (Sy)R(x, y) <-> (y)R(x, y)
whence it follows that there are numbers r, s for which
R(r) differs from (y) ~ T(r, r, y)
and
R{s) differs from {Hy)T{s, s, y)
and therefore, neither (Hy)T(x, x, y) nor (y) ~ T(x, x, y) are
recursive. In other words {Hy)T(x, x, y) is an example of a predicate
of the form (Hy)R(x, y), with primitive recursive R, which is not
quasi-recursive.
!) Vide Kleene [2] pp. 281-282, 288.

RECURSIVE CONVERGENCE
5
Another important enumeration theorem runs as follows:
For a certain primitive recursive function U(t) all quasi-recursive
functions (of one variable) may be enumerated in the form
U(ftyT(n,x,y)), n = 0, 1, 2, ...
and with the same U, and a corresponding T(n, x\, xi, ..., xjc, y)
all quasi-recursive functions of k variables may be enumerated
in the form
U(/j,yT(n,xi,x2, ...,xk,y)), w = 0, 1, 2, ...
To return to primitive recursive functions we may remark that
there are many definition schemata which though seemingly very
different from that of primitive recursion are known to define
only primitive recursive functions. We shall not enter into a
consideration of these schemata here but we shall have occasion in
the sequel to note instances of such schemata. For an account of
the forms of recursive definition reference may be made to the
author's 'Recursive Number Theory' where it is shown that
recursive arithmetic may be formalised in a system in which the axioms
of the propositional calculus and the derivation schemata referred
to above are all demonstrable.
1, 2 The development of recursive analysis from recursive
arithmetic involves the introduction of rational numbers and functions.
A rational number may be defined to be an ordered triplet (p, q)/r,
of natural numbers, with r>0.
We define
(P, ?)/»" % (P'> ?')/»"' <-> W' + q'r % p'r + qr'
where '<->' is the sign for equivalence; thus for instance the equation
(P>9)lr==(p'>9')lr' holds if, and only if, pr' + q'r=p'r + qr', and in
particular (p, q)lr=(kp + n, kq + n)lkr, where k>0.
A recursive function of one (or more) variables (p, q)jr is a triplet
of recursive functions of natural numbers
{P(p, q, r), Q(p, q, r)}IS(p, q, r)

6 RECURSIVE CONVERGENCE
with R(p, q, r)>0, and such that (writing P for P(p, q, r), P' for
P{p', q', r') and so on)
(p', q')lr' = (p, q)\r -> (P', Q'W = (P, Q)IB.
For example the sum of two rational numbers is denned by
(Pi, ?i)/»"i + (P2, q2)\r2 = (pirz+ptn, q\T2 + q&i)ltir2',
if
{Pi,qi)ln = {pi,qi)lr\ and {P2,q2)\r2 = {p2,q2)\r2
then it is readily verified that
{pir2+P2n, gir2 + g2ri)/nr2 = (pi'r2' +pz'r\ , qi'r2' + g2 Vi')/riV2''.
The product of (pi, q\)lr\ and (p2, qz)jrz is denned to be
(piP2 + qiq2, Piq2+P2qi)lrir2
and again we may readily verify that if
(Pi, qi)ln = {pi, qi')lri and (p2, qz)lr2 = (p2', qz')lrz'
then
(pi, qijjn ■ (p2, ?2)/r2 = (pi, qi')jri ■ (pz, qz')lr2'.
Defining subtraction in terms of addition we have
(Pi> q\)ln ~ (P2, q2)lr2 = (pa, qa)lra <-> (pi, gi)/ri = (p2, qdfo + (pa, qa)lra
so that
(Pi, qi)ln - (P2, q2)/r2 = (pi, qi)ln + (q2, p^fo,
and for division we have, if p2^q2,
(Pi, qi)ln 4- (P2, qz)lrz = (pa, qa)jra <-> (p\, qi)ln = (p2, q2)fc ■ (pa, qa)lra
so that
(pi, qi)ln 4- (P2, q2)\r2 = (pi, qi)lri ■ (p<nn, q^Wp^, ^l2
where \p, q\ is the positive difference of p and q.
The familiar abbreviations +sjr, —sjr are introduced by the
equations
+ sjr=(p + s,p)jr, -s/r = (p,p + s)lr

RECURSIVE CONVERGENCE
7
and as usual +p/l, — p/l are denoted by +p, —p respectively
and (p, p)\r, which is equal both to + 0/r and to — 0/r, is denoted
simply by 0.
We shall use the letters k, m, n, p, q, r, with or without suffixes
to denote natural numbers; x and y stand for rational numbers.
We shall be chiefly concerned with functions of a rational variable
x, denoted by f(x), g(x) etc., and with functions of a rational variable
x and a natural number variable n, denoted by f(n, x), g(n, x) etc.
1, 2. 1 It might be thought that the class of rational recursive
functions could be increased by applying the original recursion
schema to rational recursive functions of a natural number
argument, but this is not the case.
For instance, if we define the rational f(n, x) by the recursion
/(0, x) = 0, f(Sn, x) = <p(n, x, f(n, x)) (i)
where
y{n,{p,q)\r, (u, w)/w) = (a, 6)/c,
a, b and c being recursive functions of n, p, q, r, u, v, w, then we
can find recursive functions un(p, q, r), vn(p, q, r), wn(p, q, r) such
that
f(n, (p, q)/r) = (un, vn)\wn (ii)
It suffices to define un,vn, wn by the simultaneous recursions
uq = vq = Q, wo= 1 and
un+i(p, q, r) = a(n, un, vn, wn)
vn+i(p, q, r) = b(n, un, vn, wn)
Wn+l(p, q, r) = c(w, Un, Vn, Wn)\
then un, vn, wn are recursive, and therefore f(n, x) defined by (ii)
is recursive, and satisfies the recursion (i).
1, 3 Notation
For natural numbers p,q with q>0, we denote by [p/q] the
quotient of p divided by q; for integers i, j with ?V0, we define
[*77'] = [l*l/l7l] if *7>0
= -[|*'l/l7'l] if *7<0.

8 RECURSIVE CONVERGENCE
If for some integer k and rational x, [10%] = 0 we write x=0(k)
so that x = 0(k) is equivalent to the recursive relation |a;|<l/10*.
1, 3. 1 A relation which holds for all sufficiently great values of
n is said to hold for majorant n. More specifically a relation
R(n, m\, mi, ..., mp)
holds for majorant n if there is a recursive function M(m\, mi, ..., mp)
such that
w>Jf(rai, mi, ..., mp) -> R(n, mh mi, ..., mp)
with free variables mi, mi, ..., mp, where M reduces to a constant
if there are no variables in R beyond n.
More generally, R(m, n, r\, n, ..., rp) holds for majorant m, n, (the
order of m, n being material) if there are recursive functions
M(n, r2, ..., rp), N{m, n, n, ..., rp)
such that
m>if(n, r2, ..., rp)&n>N(m, n, r2, ..., rp) -+R{m,n,n,ri, ...,rP).
1, 3. 2 Relative equality
If f(n)—g(n) = 0(k) for majorant n, we say that f(n) is equivalent
to g(n) and write
f(n) = g(n), relative to n.
Similarly if f(n)> —10_& for majorant n, we write
/(w)>0, relative to n
and if /(w)<10~* for majorant n, then
/(w)<0, relative to n.
Furthermore if
f(m, n)-g{m, n) = 0(k)
for majorant m, n then we write
f(m,n) = g(m,n), relative to m,n.
1, 3. 3 Recursive convergence
A primitive (general) recursive function f(n) is primitively

RECURSIVE CONVERGENCE 9
(general) recursively convergent if there is a primitive (general)
recursive function N(k) such that N(k+ l)>iV(4)>4 and
N > n > N(k) -> f(N) - /(») = 0(4).
When it is necessary to emphasize the connection of N with / we
attach / to N as a suffix. We follow this practice systematically
in the sequel, both in relation to the N of this definition and
functions c(k), d(k) we meet later. Any parameters in / may also appear
in N.
A recursive function f(n, x) of a positive integral variable n and
rational variable x, is recursively convergent in an interval a < x < b
if there is a recursive function N(k, x) such that
a<x<,b&N>n^N{k, x) -> f{N, x)-f(n, x) = 0(k).
If there is a recursive function N(k), independent of x, such that
a<x<b&N>n>N(k) -> f(N, x)-f(n, x) = 0(k)
then f(n, x) is said to be uniformly recursively convergent in (a, b).
In particular if N(k) = k, f(n, x) is uniformly recursively convergent
in standard form.
Since
f(N(k),x)-f(n,x) = 0(k) for n>N(k)
therefore f(N(k), x) is equivalent to f(n, x) and since
p>q -* f(N(p), x)-f(N(q), a:) = 0(4)
it follows that f(N(k), x) is a standard form equivalent of the
uniformly recursively convergent function f(n, x).
1, 3. 4 Relative convergence
A recursive function f(m, n) is said to be convergent in m, relative
to n, if there is a recursive M{k) with M(k+ 1)>M(k) such that,
mi> M(k) & m2 > M(k) -> /(mi, n) - f(m2, n) = 0(4),
for majorant n.
A function /(m, n), convergent in m, relative to n, is not neces-

10 RECURSIVE CONVERGENCE
sarily convergent for any fixed value of n. For instance m\n is
convergent in m, relative to n, since
(mi — im)ln = 0(k)
if rai = ra2, and if mi^m2 and n>\W\m\ — ra2|; but for fixed n,
and any m,
(M-m)ln>l if Jf>ra + w,
so that ra/w is not convergent for fixed n.
1, 3. 5 The reduced sequence
Given any recursive function f(m, n), recursively convergent in
n and convergent in m relative to n, we can find a recursively
convergent Rf(m) such that
f(m,n) = Bf(m), relative to m,n.
Since f(m, n) is convergent in n, there is a recursive function N(1c, m)
such that
n*>n>N(h, m) -> f(m, n*) — f(m, n) = 0{k),
and since f(m, n) converges relative to n, there is a recursive M(k)
such that
ra*>ra>Jf(&) -> /(m*, n)—f(m, w)=0(&),
for majorant n.
Let Bf(p) = f(M(p), N(p, M(p))); R/(p) is called the reduce of f(m,n).
We show first that the reduce is recursively convergent.
For majorant n, we have
f(M(p), N(p, M{p)))-f{M{p), n) = 0(p),
f(M(q), N(q, M(q)))-)(M(q), n) = 0(q)
and, if q>p,
f(M(p),n)-f(M(q),n) = 0(p)
so that, for q>p,
Rf(p)-Rf(q) = 3-0(p)
which proves convergence. It remains to show that
f(m, n)=Bf (m), relative to m,n.

RECURSIVE CONVERGENCE
11
We observe that
f(m, n)— f(M{m), n) = 0(k), for majorant m, n,
and
f(M(m),n)-f(M{m), N{m, Jf(ra))) = 0(ra), for majorant n,
whence f(m,n) — Bf(m) = 2-0(k), for majorant m,n as was to be
shown.
1, 4 The familiar theorem of classical analysis that a monotone
bounded sequence is convergent does not hold in recursive analysis.
To prove this we shall utilise an important theorem in the meta-
mathematics of arithmetic; this theorem affirms that there can be
no effective procedure for deciding of any primitive recursive
function f(n) whether there is value for n of which f(n)>0, or
f(n) = 0 for all n. A proof of this theorem is given in the Hilbert-
Bemays Grundlagen (Ref. 3 Vol. 2, p. 417-8).
Let f(n) be any primitive recursive function and let
F(0) = 0, F(n+l) = F(n) + [l - {F(n) + (l -^ /(«))}]
so that F(n) takes only the values 0,1 and is non-decreasing. If
it were true that a monotone bounded sequence were recursively
convergent then there would be a primitive recursive N(1c) such
that
n>N(k)-+ F(n) - F{N(k)) = 0(4),
and in particular
n>N(l)-+\F(n)-F(N(l))\<l,
so that, since F(n) is an integer, F(n) = F(N(l)) for n>N(\). If
F(N(1)) = 0 it follows that F(n) = 0 for n>N(l) and since F(n)
is non-decreasing, therefore F(n) = 0 also for n<N(l). Thus if
F(N(1)) = 0, then F(n) = 0 for all n; however if f(n)=l for some n
then F(n+l) = l, and if f(n) = 0 for all n then F(n) = 0 for all n.
It follows that if F(N( 1)) = 0 then f(n) = 0 for all n and if F(N( 1)) = 1
then f(n) = \ for some w<iV(l). Since F(n) and N(k) are recursive,
the value of F(N(1)) is computable in a finite number of steps and
provides therefore an effective procedure for deciding whether

12 RECURSIVE CONVERGENCE
f(n) = 0 for all n, or not. Since no effective decision procedure is
possible the hypothesis that F(n) is recursively convergent is
untenable. Many of the classical tests for convergence are, however,
valid tests for recursive convergence, as we shall show.
1, 4. 1 Limits
A rational number I is the recursive limit of the recursively
convergent sequence s(n), and s(n) is said to tend recursively to
the limit I if there is a recursive function n(k) such that
n>n(k) -> l — s(n) = 0(k).
It follows, of course, that if s(n) tends recursively to a limit, then
s(n) is recursively convergent.
A recursive function s(n) is recursively divergent if there is a recursive
d(n) and an integer k such that
\s(n + d(n))-s(n)\>10k.
The condition for a sequence s(n) not to tend recursively to a
limit is that there should be recursive functions
v{p, q, r), n(p, q, r, k) such that n(p, q, r, k)p*k
and
n = n(P) q, r, k) -> \s(n)-(p, q)l(r+ 1)|> lO"***".
To illustrate this condition we prove that the sequence s(n) = u(n)/n\,
where w(0)= 1, u(n+ l) = (n+ l)u(n)+ 1, is recursively convergent,
but does not tend recursively to a limit. For
n>q -> 0<s(n) — s(q)<llq(q\)
so that s(n) is recursively convergent; but (ignoring, as we may,
negative rationals)
{s(q)-plq}q\ = u(q)-p{(q-l)\}
= q(q-l)u(q-2)~p{(q-l)\} + q+l
= 2(mod q— 1), gr>4.
Thus
\s(n)-plq\>(l-llqW,

RECURSIVE CONVERGENCE 13
for all n such that w>gr>4; in the cases q=l, 2, 3, with w>4,
the difference \s(n) —pjq\ is least for p = 8, q = 3 and \s{n) — 8/3| > 1/24,
which completes the proof that s(n) does not tend recursively to
p/q for any p, q.
1, 4. 2 Tests for recursive convergence
We commence by proving the recursive convergence of the
geometric series Zxn for 0<£<1. From
nxn< ^ xr=(l-xn+1)l(l-x)<ll(l-x)
it follows that xn< l/n(l— x) and so xn tends recursively to zero
and J & tends recursively to 1/(1—a;).
If £>1, J xT~ 2 £r=#r+1>l, so that J & is recursively
divergent. And similarly if a(n) does wo£ tend recursively to zero,
so that a(w+l)>10-*(0-0-0) when n + l=n(0, 0, 0, &), then
2 a(r) - J a(r) = a(n+l)>10-«0-°-0)
r<n+l r<n
when n+1 = w(0, 0, 0, k), showing that J a(r) is recursively
r ^n
divergent. Furthermore if J a(r) is recursively divergent, and
a(r)>0, then, for any fixed m, 1/ ^ a(r) tends recursively to
zero; let s(n)= J a(r) and e(0) = 0, e(w+l) = e(w)+d(e(w)), so
that s{e{n+l)) — s{e{n))>10k, by hypothesis, from which it follows
that s(e(n))>n-10* and therefore
p > e(w) -> l/s(p) < l/s(e(w)) < 10-*/n
showing that s(n) is recursively convergent to zero.
1,4. 3 The comparison tests for positive series are obviously
valid for recursive convergence, for if u(n)<,kv(n) then
2 u(r) <k J v(r)
and so if Zv(r) is recursively convergent then so is £u{r), and if
Zu(r) is recursively divergent so too is Zv(r).

14 RECURSIVE CONVERGENCE
Moreover, from the inequality
u(n+ l)lu(n)<v(n+ l)lv(n)
follows u(n)^{u(0)lv(0)}v(n) so that the recursive convergence of
Ev{n) entails that of Zu(n), and Zv(n) is recursively divergent
with Su{n).
1, 4. 4 For Cauchy's test, we observe that if for some fixed k
u(n) <kn<l
then Zu(n) is recursively convergent by the foregoing tests, and
if w(w)>l for n = n(r), where n(r) is strictly increasing, then it
follows in turn that u(n) does not tend recursively to zero and
Zu(n) diverges.
1, 4. 5 For D'Alembert's test, we note that from
u(n+l)lu(n)<k<l
for a fixed k, follows u(n+ l)/w(w)<&™+1/&™, proving that Zu(n)
converges recursively, and from
w(w+l)/w(w)> 1
follows the recursive divergence of Su(n), since w(w)>w(0).
1, 4. 6 Kummer's test requires closer consideration. The original
form of the test is valid for recursive convergence, for if there is
a constant a>0 such that
c(n){u{n)lu(n+l)}-c(n+ \)><x
and if c(n)u(n) tends recursively to zero, then Eu(r) converges
recursively since
a 2 u(r)<,c{n)u{n)~ c(N)u(N)<c(n)u(n).
Dini's form of the test, which omits the condition that c(n)u(n)
tends recursively to zero, is not valid, since it is equivalent to
asserting the recursive convergence of a monotone bounded
sequence; for if s(n) is any strictly increasing recursive function
bounded above by an integer B and if
u(n) = s(n) — s{n— 1), v(n) = B— J u(r)
Kr<n

RECURSIVE CONVERGENCE 15
and c{n) = v{n)ju{n) then
c{n){u{n)/u{n+ l)}-c(n+ 1)= 1.
1, 4. 7 We consider next Cauchy's condensation test.
Denote £ f(r) by /(™, n); then if f(r) is steadily decreasing,
/(2», 2»+i-l)<2»/(2»), and therefore
/(2»,2*+i-l)< J 2r/(2r).
n<r<JV
whence it follows that, if 2*+i > if +1,
I /(r)< I 2^/(20.
Similarly, if 2»+l>ra,
I /(r)> I 2r/(2r+i).
These inequalities show that the condensation test is valid for
recursive convergence and divergence. We deduce that 27 \jr is
recursively divergent so that 1/ J (Vr) tends recursively to
zero, for any fixed ra. Furthermore 271/r2 is recursively convergent
with 271/2'.
1, 4. 8 Raabe's tests for recursive convergence and divergence
take the form:
If for some k> 1,
u(n)lu(n + 1) > 1 + &/»
then Zu(n) is recursively convergent, and if
«(»)/«(»+l)<l + l/n+l/n J (1/r)
Kr<n
then Z u(n) is recursively divergent.
For the convergence test we observe that the given inequality
implies that
{n-u(n)lu(n + 1)} - (n+ 1) > k - 1 > 0;
from this we deduce that
n-u(n)l(n+l)-u(n +1)>1 + (k- !)/(»+1)

16 RECURSIVE CONVERGENCE
and hence, by multiplication,
(using a>0&6>0-> (l+a)(l+b)>a + b)
we find
N-u(N)<n-u(n)l(k-l) £ (Vr)
n+l<r<JV
so that, keeping n fixed, N-u(N) tends recursively to zero, and
Zu(n) converges recursively, by Kummei's test. For the divergence
test we start by proving that if
»(!■)= 1/r 2 (l/2>)
then Zv(r) is recursively divergent. For l/2nw(2n)<w+1, so that
Z2nv(2n) diverges, by comparison with Zll(n+1), and hence, by
the condensation test, Zv(r) itself is recursively divergent. Since
»(»)/»(»+l) = {l + (n+l) 2 (1lr)}ln I (VO
= 1 + 1/m+1/m J (1/r) >«(»)/«(»+1),
Kr<n
therefore 27w(w) is recursively divergent.
In preparation for a proof of the Gauss test for recursive
convergence we shall prove
1, 4. 9 If Zu(r) is recursively convergent, and n-u(n) is steadily
decreasing and tends recursively to zero, then { J 1/»"}»•«(»)
tends recursively to zero. i<r<n
For n~>r we have
n ■ u{n)fr = {n ■ u(n)jr • u(r)}u(r) < u(r)
and since Zu(r) is recursively convergent there is a recursive n(k)
such that, writing h(m, n) for J (l/r)>
n>n(k) -> A(n(&) + 1, n)-nu(n)<l/2k.
Further, since n-u(n) tends recursively to zero there is a recursive
r(k) such that A(l, n(k))-nu{n)< 1 /2&, for w>r(&), whence it follows
that
w>raaa;(w(&), r{k)) -> A(l, w)-ww(w)< 1/&.

RECURSIVE CONVERGENCE 17
The foregoing tests may be summarised in
The Gauss test. If there are constants a, (S, M and a recursive d(n)
such that \0(n)\<M and
u(n)lu(n+l) = ix + Pln + d(n)ln2
then
a>l, or a=l and /S>1, implies Zu(n) is recursively convergent
and
a<l, or a=l and /S<1, implies Su(n) is recursively divergent.
The case a=l,/?<1 alone requires further consideration. By the
previous theorem (taking 1/w2 for u(n)) we know that (1/w) J (Vr)
tends recursively to zero, and so there is a recursive N(k) such
that
,...., 0(n) 1
n > N(M) -> -V <
n2 n 2 (I/O
Kr<n
which shows that a= 1, /S< 1 suffices to ensure the recursive
divergence of Zu(r).
1, 5 We turn to consider the tests for relative convergence.
Relative convergence has already been denned. A recursive
function s(m, n) is said to divergent in n, relative to m, if there is
a constant &>1, and a recursive function X(n) such that
\s(m, n + X{n)) — s{m, w)[> \jk,
for major ant n, m.
s(m, n) is said to tend to zero, relative to m, if
s(m, n) = 0(k)
for major ant n, m.
In the following theorems a(m, n), b(m, n), c(m, n) are positive,
non-zero, recursive functions.
Theorem 1 // for some fixed k, and majorant m,
a(m, n)<k< 1
then J {a(m> r)}r is convergent in n, relative to m.
0<r<n

18 RECURSIVE CONVERGENCE
For J {a{m,r)}r< J &*", for majorantm. If i(r+l)>r + t(r)
n<r<JV n<r<JV
and if a(m, i(r))>l for majorant ra, then ^ {«(m, ?")}r diverges
0<r<n
relative to ra. For
2 {o(m, r)}'- 2 W»». r)}r>l,
0<r<t(n + l) 0<r<n
for majorant ra.
Theorem 1,1 If for a fixed A>0,
a(ra, w) < A o(ra, w)
/or majorant ra, then the convergence of Z b(m, r) relative to m,
entails that of Z a(m, r) relative to ra, and the relative divergence of
he latter entails that of the former.
For
2 a(m, r)<X £ Hm>r)
n<r<JV n<r<JV
for majorant m.
Theorem 1, 1. 1 // there are constants h,H such that
0<A<a(ra, <))<#, h<,b(m, 0)<H
and a(m, n+ l)/a(ra, w)<o(ra, n+ l)/o(ra, n), for majorant m, then
the relative convergence of J b(m, r) entails that of J a(m> r)> an(^
the relative divergence of the latter entails that of the former.
For a(m, n)^(H/h) b(m, n), for majorant m.
Theorem 1,1.2 The condition a(ra, w+l)/a(ra, w)<&< 1, for
majorant m, is sufficient for relative convergence of Sa{m, n), since
a(m, n+l)la(m, n)<,kn+1lkn, for majorant m.
The condition a(m, n+ l)/a(ra, »)>1, for majorant m, suffices for
relative divergence, since ^ 1 diverges.
Theorem 1, 1. 3 // there is a constant /?>0 such that
c(m, n){a(m, n)ja(m, n+1)} — c(m, w+!)>/?,

RECURSIVE CONVERGENCE 19
for majorant m, and if c(m, n)a(m, n) tends to zero in n, relative
to m, then ^ a(m> r) converges relative to m.
For P J a(m,r)<c(m,n)a(m,n), m majorant.
Theorem 1, 1. 4 // there is a constant p>l such that
a(m, n)la(m, n+ 1)> 1+p/n,
for majorant m, then J «(wi, r) converges relative to m.
We readily prove n-a(m,n) tends to zero in n, relative to m,
and the result then follows from the previous theorem.
n
Theorem 1, 1. 5 // a(m, n)la(m, w + l)< 1 + ljn + l/n £ (l/r)> for
r-l
majorant m, then J aim> r) diverges relative to m.
(The proof is the same as for recursive divergence.)
Theorem 1, 1. 6 // f(m, n) is monotonic decreasing in n, relative
to m, i.e. if f(m, N)<f(m, n), for N>n, and majorant m, then
I f(m, r), 2 2r/(™> 2r)
converge and diverge together, relative to m.
(The proof is the same as for recursive convergence.)
Theorem 1,1.7 // a{m,n)\a{m, w+l) = a + /?/w + 0(ra, w)/w2, for
majorant m, and if \d(m, n)\<M, then a>l, or a=l,/?>l, are
sufficient conditions for relative convergence, and «<1, or a= 1, /?< 1
are sufficient for relative divergence of J a(m> n).
This follows from Theorems 1, 1.2; 1, 1.4; 1, 1. 5.
We proceed next to sharpen Theorem 1, 1. 7, proving first a
series of preparatory theorems.
Theorem 1, 1. 8 If a>b, and w>2, then
nbn-1<(an — bn)l(a — b)<nan-1.
Proof. If x>l, n>l, then J xr>n+\, and therefore
(xn+1-l)l(x-l)>n+l,

20 RECURSIVE CONVERGENCE
whence, taking x = ajb,
(Bn+i _ 6»+i)/(0 -6) >{n + 1)6".
Similarly, if x<l,n>l, then J xr<(n+\) and therefore
(l-xn+1)l{l-x)<n+l,
and the second half of the theorem follows by taking x=b/a.
We note that since #- 1 = { £ ^}(f — !)» it follows that if t> 0,
r<«-l
then £ ^ 1 according as ti ^ 1.
Theorem 1, 1. 8. 1 If /x is positive, and p, q are positive integers,
p>q, then {l+<x)P>{l + (plq)<x}v.
This is a simple consequence of a special case of the famous
theorem of the means, viz. {(ma + nb)l(m + n)}m+n>ambn, a^b,
m, n positive, non-zero integers. (There are several algebraic proofs
of the theorem of the means which are valid in the present system.)
Take m = q, m + n=p, a= l + (plq)<x, 6= 1 and the theorem
follows. Similarly, if p<q, taking m=p, m + n = q, b= 1, a=l+tx, we
have {l + a.)P<{l + (plq)/x}«.
Theorem 1,1.9 // p,q,x are integers, x>\,q>\,p>\, and if
Xk is the greatest integer such that (xk)a <xv ■ 2ki, then x„l2n is
recursively convergent.
Proof. Since (2^)«<^-2(*+1)«, therefore Xk+\>2xk and so a;*/2*
is monotonic increasing, and since xo is the greatest integer such
that (x0)Q<;XP, and \i<xP, then xo> 1 and so Xk>2k. From
{XlcY < XP ■ 2*1 < XPI ■ 2*4
it follows that xn<xP-2k. Hence
0 < xP - (xk/2k)« < {(xk + 1)« - (z&)«}/2*« < q(xk +1 )«-i/2*«
(by Theorem 1, 1. 8)
<q{xP+ l/2*}«-i/2*<g'{^+ l}«-!/2*
and so (^/2*)« converges recursively to xP.

RECURSIVE CONVERGENCE 21
Writing xicl2k = yk, so that yk is mono tonic increasing and ykq
converges recursively, then
{(2/*+r)« - (y*)«}/{y*4r - yk] > qiykY'1 > q,
i.e. yk+r — Vk< {(yk+r)a- (yk)a}lq, so that yk is recursively convergent,
which completes the proof.
1, 5. 1 We define, for £>> 1, q> 1, x> 1, %{x, p, q, A;) = ^/2* (where
xk is given above) and %{l,p, q, k) = % (0,p, q, k)=l.
Theorem 1,2 ^ ^lx(r>P>9'^) iS convergent in n, relative to k,
if p>q and divergent in n, relative to k, if p<q.
Since {x(x, p, q, &)}« converges recursively to x?, therefore,
writing ak = %{x+l,p, q, k)\%{x,p, q, k), we have if p>q, («*)«
converges recursively to (1 + 1 /x)p > (1 +plqx)i by Theorem 1,1.8.1;
the recursive convergence of aki determines a recursive function
Q(x) such that |(1 + 1/x)p - {ak)i\ < (1 + 1/x)p- (1 +plqx)i for k> Q(x),
and therefore («#)«> (l+£>/<£*;)«, so that ak>l+plqx for k>Q(x).
It follows, by Theorem 1,1.4, that J l/#(r> P> 1-> &) converges
relative to k, if p>q. ,<n
If p = q, x(n, p, q, k) = n, and so £ ^lx(r> P> 1> k) diverges. If
p<q, ak<l+plqx for k>Q*{x), whence, by Theorem 1,1.5,
2 ^lx(r>P> 1> &) diverges relative to A;.
r =gn
Theorem 1,2.1 // q>(n, p, q, k) = nl%(n,p, q, k) then, for p>q,
<p{n, p, q, k) is monotonic decreasing to zero, relative to k.
For
<f{n,p, q, k)l<p(n+l,p, q, k)>{nj{n+\)}{\+pjqn}
= l + ((plq)-l)l(n+l)
if k>Q(n), p>q, so that <p(n,p,q,k) is monotonic decreasing,
relative to k, and further, if N>n,
<p(N,p,q,k)l<p(n,p,q,k)<ll ft {1 + ((p/g)- l)/r}
JV>r>n
< l/Hplq)— 1) J (1/r) for majorant &,
JV>r>n
which shows that q?(iV, £>, <?, A;) tends to 0 relative to k.

22 RECURSIVE CONVERGENCE
Theorem 1,2.2 // p>q, { £ (Vr)} nlx(n'P> 1> &) tends to 0,
relative to k. i<r=g»
If n>r, by Theorem 1, 2. 1
<p(w, p, ?, k)l(p{r, p, q, k)x{r, p, q, k) < l/x(r, p, q, k)
for majorant k. Since ^ ^lx(r> P> 1> &) converges relative to £,
if ^»>gr, given £> 1, we can determine n(x) such that
I 1/*(»". 2». ?, *) < l/2a;,
for w>w(a;), and majorant A;. Furthermore, since <p(n,p, q, k) tends
to 0, relative to k,
{ I (llr)}<p(n,p,q,k)<ll2x,
for majorant n, k. Hence
{ I (llr)}<p(n,p,q,k)<llx,
for majorant n, k, proving that { J (l/r)} <p{n->V-> <Z> &) tends to 0
relative to jfc. 1<r<n
1, 5. 2 We are now in a position to state the analogue, for relative
convergence, of the Gauss test.
Theorem 1, 3 // for majorant k, and p>q,
a(n, k)/a(n+l, k) = <x + pin + 6(n, k)/x(n,p, q, k),
and \6{n, k)\<M, then a>l or x=l,j3>l are sufficient conditions
for the convergence of ^ a(r> &) relative to k, and «< 1 or a= 1, /?< 1
are sufficient conditions for relative divergence.
We have to consider only the cases a=l,/?>1; a=l,/?<1. If
fi> 1, since d(n, k)q>(n, p, q, k) tends to 0 relative to k, we can find
No, such that
\nO(n,k)lX(n,p,q,k)\<(ll2)(p-l),
for n>No, and majorant &, and so
a{n, 4)/o(»+ 1, 4)> 1 + (1/2)(j8+ l)/»,

RECURSIVE CONVERGENCE
23
for n'^No, and majorant k, which suffices for relative convergence,
by Theorem 1, 1. 4.
Similarly, if /?< 1, a(n, k)ja(n + 1, k)< l + (l/2)(/S+l)/w, which
proves relative divergence, by Theorem 1, 1. 5.
If/?=1, since { J (^lr)}<p(n>P> <7> k) tends to 0, relative to k,
Kragn
therefore we can find n0 such that
\e(n,k)lX(n,P,q,k)\<lln £ (I/O,
Kr<n
for n > no, and majorant k, whence J a(r> &) is divergent, relative
to k, by Theorem 1, L 5. r<n
1, 6 Recursive real numbers
A primitive recursive function f(n) which is primitive recursively
convergent is called a primitive recursive real number. A general
recursive function f(n) which is general recursively convergent is
called a general recursive real number. When the distinction between
primitive and general recursion is irrelevant (in the sense that the
context allows either) we shall speak of a recursive real number.
If f(n) and g(n) are recursive real numbers and f(n) = g(n), relative
to n, we say that the recursive real numbers f(n), g(n) are equal,
and write
{/(»)} = {?(»)}•
If for some constant c>0, f(n)>c for majorant n, we say that
the recursive real number f(n) is positive and write
{/(»)}> 0.
Similarly, if for a constant c>0, f(n)< —c for majorant n, then
the recursive real number f(n) is said to be negative and we write
{/(»)}< 0.
Two recursive real numbers f(n), g(n) are said to be recursively
unequal if there is a constant k>0, and a recursive A(w)>w, such
that
\f(X(n))-g(X(n))\>k.

24 RECURSIVE CONVERGENCE
1, 6. 1 Arithmetic of recursive real numbers
If s{n), t(n) are recursively convergent then, patently, s(n) + t(n)
and s(n) — t(n) are recursively convergent. The recursive real number
s(n) + t(n) is called the sum of the recursive real numbers s(n) and
t(n) and we write
{s(n)} + {t(n)}={s(n) + t(n)}.
The recursive real number s(n) — t(n) is called the difference of
{s(n)} and {t(n)} and we write
{*(»)}-{*(»)} = {*(n)-*(»)}.
A recursively convergent sequence is bounded, because there is a
constant no such that \s(n) — s(no)\<l, and so if
M = max \s(n)\
r<n0
and S = M+1, then \s(n)\<S.
If s(n) is recursively convergent then s(n)2 is recursively convergent
for
\s(Nf-s(n)2\ = \s(N)-s(n)\ - \s(N) + s(n)\ < 2S- \s(N)-s(n)\.
It follows that if s(n) and t(n) are recursively convergent then so is
^)-^)-{S(W)^(W)f-{S(W)^(W)f.
The recursive real number s(n) ■ t(n) is called the product of {s(n)}
and {t(n)} and we write
{s(n)}^{t(n)}={s(n)-t(n)}.
If s(n) is recursively convergent, and is recursively different
from 0 and if s(n) # 0, then
l/s(w) is recursively convergent.
For there is a constant k > 0 and a recursive X{n) > n, such that
\s(X(n))\>k
and a constant v such that
w>v&m> v -> |s(w) —s(wi)| <£&

RECURSIVE CONVERGENCE 25
whence, since A(wi)>wi it follows that
w>wi -> \s(n)\>^k.
Since s(w)#0, min \s(n)\=m>0, and so, if s = min(ra, \k), then
|s(m)|>«.
It follows that l/s(n) is recursively convergent for
1 1
s(n) s(N)
^\s(N)-s(n)\
the recursive real number l/s(n) is called the reciprocal of {s(n)}
and we write
1/{*(»)} = {1/*(»)}.
For recursive real numbers {s(n)}, {t(n)} we define the quotient
{s(n)}I{t(n)} to be the real number {s(n)} ■l/{t(n)} when {t(n)} is
recursively different from zero.
Theorem 1, 4 There is no effective procedure for deciding of two
recursive real numbers whether they are equal or not.
Let f(n) be any primitive recursive function, let s(n) = 0 and
((0) = /(0), t(n+l) = t(n) + f(n + 1). Then t(n) = 0 if and only if f{r) = 0
for all r<w. Both {s(n)} and {t(n)} are primitive recursive real
numbers. If there is an effective procedure for deciding whether
{s(n)} = {t{n)}, or not, there is an effective procedure for deciding
for an arbitrary f(n), whether f(n)=0 for all n, or there is an n
for which f(n)>0, and this we know to be impossible.
We define
{/(»)} > {g(n)} <-> {/(»)} - {g(n)} > 0.
Theorem 1, 5 // {f(n)} and {g(n)} are recursively unequal then
either {f(n)}>{g(n)} or {g(n)}> {/(»)}.
For there is a constant k and a strictly increasing recursive X(n)
such that
\f{X{n))-g{X{n))\>k;
by recursive convergence we can find N such that
m>n>N -> |/(m)- f{n)\<\kk\g{m)-g(n)\<\k.

26 RECURSIVE CONVERGENCE
Hence if f(A(N))>g(X(N)) then
f(X(N))-g(X(N))>k
and so
f(n)-g(n)>ik,
for n>N proving that
{/(»)}>{?(»)}•
Similarly, if f(A(N))<g(X(N)), then
{g(n)}>{f(n)}.
Theorem 1, 5. 1 // {f(n)}, {g{n)} are unequal general recursive real
numbers then they are general-recursively unequal.
For if {f(n)}, {g(n)} are unequal there is a constant k and, given
any n, an integer N such that,
N>n8c\f(N)-g(N)\>k; (1)
let h(ri) be the least value of N for which these inequalities hold
then X(n) is general recursive, X(n)>n, and \f(h(n))—g(h{n))\>k,
so that {/(w)} and (<7(w)} are general-recursively unequal. It is
important to observe that we have established only general-recursive
inequality; even if {/(w)} and {g{n)} are unequal primitive recursive
real numbers, we cannot prove primitive recursive inequality,
since the existence of an N for which the inequalities (1) hold is
no evidence for the existence of a primitive recursive X(n) for which
X(n) >n&\ /(A(»)) - g(X{n)) \ > k.
A recursive real number {/(w)} is rational if there is a rational
number I such that f(n) tends recursively to I, that is to say
f{n)-l = 0(k)
for major ant n.
A recursive real number {/(w)} is recursively irrational if there
are recursive functions v(p, q, r)> 1, n(p, q, r) such that
n>n(p, q, r) -> \f(n)-(p, g)/(r+l)|>l/v(2>, q, r).

RECURSIVE CONVERGENCE
27
If the functions concerned are all primitive-recursive then {/(w)}
is primitive recursively irrational.
Theorem 1, 6 If a recursive real number f(n) is irrational, that is
to say if for any p, q, r, there exist k and m such that
n>m ->- \f(n)-(p,q)l{r+l)\>10-k
for all n, then f(n) is general-recursively irrational.
For there is a recursive n(s) such that,
n>n{s) ->- \f(n)-f{n{s))\ < 10-(*+D,
and so by the irrationality of {f(n)}, there is a & such that
\f(n(k))-(p,q)l(r+l)\>9-10-V<+»,
let <p(p, q, r) be the least s such that
!/(»(«))-(!», ?)/(r+1)1 > 9-10-C+w
and let N(p, q, r) = n{qj(p, q, r)), so that q>(p, q, r) and N(p, q, r) are
general recursive and
n>N{p, q, r) -> \f{n)-{p, g)/(r+ 1)|> 10-toto.Q,r)+i)
which proves that {/(w)} is general recursively irrational.
Theorem 1, 6. 1 There is no effective procedure for deciding whether
any general recursive real number is rational or irrational.
Let s(0)=l, s(n+l)=l+(n+l)s(n) so that {s(w)/w!} is the
primitive recursive real number e, which of course is irrational.
Let f(n) be any primitive recursive function and let t(n) = s(n) if
/(r) = 0 for all r<w, and t{n) = s(k) if k is the first value of r<w for
which /(r)>0; for N>n,t(N)fN\-t(n)ln\<s(N)fN\-s(n)fn\ so that
t(n)jn\ is primitive-recursively convergent.
If there exists an eifective procedure for deciding whether {£(w)/w!}
is rational or irrational then there is an effective procedure for
deciding whether or not there is an n for which f(n)^0.

28 RECURSIVE CONVERGENCE
1, 7 Recursive polynomials
If a„ is a (primitive) recursive function,
X arxr
is called a (primitive) recursive polynomial of degree n, with
coefficients ar,r<n.
If Y, artn = 0 for a certain t, then t is called a zero of the poly-
nomial J a^cr-
If f(x)= J a^r has no rational zero and ar, r<w, are integers,
then r<n
l/(#z)l>i/r-
For qnf(p/q) = 2 arprqn'r, and since /(^/gO ^ 0 and J «rPrg,"_r is
an integer, therefore
| J arprq"-r\ > 1
whence it follows that
l/(2>/?)l>l/3".
If J °r#r has a rational zero p\q (p, q having no common factor)
then p is a factor of «o an<i ^ is a factor of an; for
0 = ^" J ar{plq)r=arlpn + q £ arprqn-r-i
so that a„ is divisible by q, and
0 = 2" J Or(PlQ)r=aoQn+P Z arPr"19'"_r
so that «o is divisible by p.
Theorem 1, 7 // fn(x) is the polynomial J arXr, Mn = max |ar|
and z is at least as great as \x\,\y\ and unity, then
fn(x)-fn{y)
x-y
<in{n+l)Mnz"-K (1)

RECURSIVE CONVERGENCE
For
/o(«0 - My)
z-y
and if (1) holds for n=k then
fk+i(x)-fk+i(y)
x-y
< \k{k+ 1) Mk zk-i + (4+1) Mt+i z><
<{|4(i+l) + (4+l)} Jffc+iz*=i(i+l)(i + 2) Jft+iz*
so that (1) holds also for n = &+l, and therefore by induction (1)
holds for all n.
Theorem 1, 7. 1 // f(x) is a primitive recursive polynomial of
degree n with integral coefficients ar and no rational zeros, and if {s„}
is a primitive recursive zero of f(x), that is to say {sn} is a primitive
recursive real number and f(sn) tends primitive recursively to zero
then {s„} is primitive recursively irrational.
Since sn is recursively convergent we can find S such that \s„\ <#
for any n. Let
z = max (\plq\,S, 1),
h = max \ar\, and M = ^n(n+ l)Az™_1,
then, by the previous theorem, \f(p/q)~-f{sm)\<M-\plq — sm\.
Since f(sm) tends recursively to zero we can find k so that
ra>&-> |/(sm)|<l/2?»;
however,
l/(2>/?)l>l/9",
and therefore
l/(2>/?)-/(«»)l>W,
whence
ra>&-> \p\q-sm\-^\\1Mqn
which proves that {sm} is primitive recursively irrational.
fk(x)-fk(y)
y.k+1.
ijk+1
x-y
<*>k+l ■
x-y

30 RECURSIVE CONVERGENCE
1, 7. 1 Recursive expansions
If {s„} is a (primitive) recursive real number and if a„ is a
(primitive) recursive sequence such that
0<a„+i<r-l,r>2,
and
{sn}={ I apr~p}
then the real number {s„} is said to have the (primitive) recursive
expansion Sapr~~P in the scale of r.
Theorem 1, 7. 2 // {s„} is a recursively irrational recursive real
number then {s„} has a recursive expansion in any scale r>2.
Since {s„} is a recursive real number there is a strictly increasing
recursive function n(k) such that
w>w(&)-> |s»-s„<*)|<l/r*+1,
and since s„ is recursively irrational, there are recursive functions
i(p, q), N(p, q) such that for any integers p, q, with q>0,
n>N(p,q)-+ \sn-plq\>r-i(i>'Vh
Taking p=0, q= 1 we see that for all large enough /, k
\s}-sk\<r-i<o,i)
and
|s;|>r-«(o,D, \sk\>r-«o,n
so that Sj, s/c are of the same sign. Without loss of generality we
may therefore suppose that all sn are positive.
Let [x] denote the greatest integer contained in x, and let
Pk=[rksn(ic)]; then either
0<rksn(k)-pic<% (i)
or
rkSn(k)-pk>£
so that
0<pk+l-rksn(k)<h (ii)
We consider first case (i).

RECURSIVE CONVERGENCE 31
For n>n(k),
1 1
< rksn-rksn(IC)<-
r r
and so, by (i),
\rksn-<pk\<\;
but
n>N(pk, rk) -> \sn-pklrk\>r-i(i>*>'r*\
and therefore, for n > N(pk, rk),
l>\rksn-pk\>dk=rk-i(n,<*\
Taking ra(&) = max (n{k), N(pk, rk)), it follows that, for n>m(k),
each rksn lies either in the open interval (pk + dk, Pk+l) or in the
open interval (pk—l,Pk — dk)-
Writing fi(k) = n{i(pk, rk)), we have
n> n(k) -> \rksn - rksm\ < dk
which shows that all rksn, for w>max {(i{k), m(k)}=M(k), lie in
one or other of these intervals and therefore
either [rksn] = Pk, for all n>M(k),
or [rksn]=pk— 1, for all n>M{k),
and so [rksn]=[rkSM(k)], for n>M(k).
In case (ii) the same result holds for n>M*(k), where
M*{k) = ma,x {n(i(pk+ 1, rk)), n(k), N(pk+ 1, rk)}
and so if
v(0) = max{Jf(0), Jf*(0)}
and
v(k+ l) = max {M(k+ 1), M*{k+ 1), v{k)+1},
then
w > v(&) -> [r*s„] = [r^tj;)],
and v(k) is strictly increasing.
It follows that
0<sn-[rksvWHrk<llrk
for n>v(k).

32 RECURSIVE CONVERGENCE
Let
«o = [s,(o)]> «n+i = [rn+1 *,(„+!,]- r[r» «„<„,]
then
I o*r-*=[r»^„]/r".
fc<n
Now for any rational a;,
0<ra;—r[a;]<r
and
— 1 < [rx]—rx<0
so that
— l<[rx] — r[x]<r;
taking rnsv{n+l) for x, it follows, since [r»s„(B)] = [rnsvin+l)], that
0<a„+i<r,.
It remains to prove that the real numbers {sn} and {[rnsvin)]/rn}
are equal, for then Zaicr~k is a primitive recursive expansion of
{s„} in the scale of r.
For n>n(k+\),
|s»-s,(„)l<l/r*+1
and
0<svM - [!■"*„»,]/!■"< 1/r"< l/f*+1,
and therefore
l«»-[r"^»)]/r"l<l/f*
for n^n(k+l), which completes the proof.
In preparation for the last theorem of this chapter, that there
is a primitive recursive real number whose decimal expansion is
not primitive recursive, we recall some results from the theory
of recursive functions.
By a theorem of Rosza Peter, all primitive recursive functions
of one argument can be enumerated in the form
7>o(n), <pi(n), q>2(n), ...
where
(pQ(n) = 0, q>i(n) = n + l, (f2{n) = n— [|/w]2, ... .

RECURSIVE CONVERGENCE
33
In this enumeration each function of <pm{n) recurs infinitely often,
the function <pP(n) and <pm(n) being identical for p = 3m • 7 • 1 lx,
where x is any non-negative integer, and the function
<Pm((pm{n)) = <pp(n),
for p = 2-3m-5m, so that <pm{n) and q>p(n) are different functions
for ra > 0. It follows that the function d(n) = <pn(n) is not primitive
recursive for if d(n) were primitive recursive then so would d(n) + 1
be, and therefore there would be a p such that
(pp(n) = d(n)+l
identically, whence <Pp(p) = d(p) + l = <pp(p)+ 1, which is impossible.
The function d(n) is however general recursive (being in fact
definable by a double recursion) and so by the Kleene Normal Form
Theorem, there is a primitive recursive function <p(n) and a primitive
recursive predicate R(m, n) such that
d(n) = <p{nxR{n, x)}
where (ixR{n, x) denotes the least value of x for which R(n, x)
holds.
(The argument may be adapted to construct a function d(n) which
is general recursive but is not definable by multiple recursions
of any finite order.)
By means of this function d(n) we can now prove an important
theorem due to E. Specker.
Theorem 1, 8 There is a primitive recursive predicate P(x), and
a primitive recursive function y(n) which takes only the values 0,1
such that the general recursive function
y{/j,x(x>n&P(x))}
is not primitive recursive.
Let <x(n), fi(n) be the primitive recursive functions with the
properties
«(0) = 0,«(w+l)=l; ^(0)=1,/S(n+1) = 0;

34 RECURSIVE CONVERGENCE
and let i(m, n), j(m, n) be the representing functions of the primitive
recursive predicates
(3z){w=3m-7-ll*}, (Hx){x<n&R(m, x)}.
Thus i(m,n) and j(m,n) take only the values 0,1 and i(m,n)
vanishes only if the functions cpm{t), <pn(t) are identical. In terms
of i and j we define functions a(n), b(n), c(n) by simultaneous
recursion as follows:
a(0) = 6(0)=c(0) = 0;
if a(n) = 0 then
a(» + l) = j8(*(6(»),»+l))
b(n+l) = b(n)+a(n+l)
c(n+l) = n+ 1;
if a(n) = 1 then
a(n+l) = a(7'(c(n), n+1))
b(n+l) = b(n)
c(n+l) = c(n).
The functions a(n), b(n), c(n) are primitive recursive; a(n) takes
only the values 0,1 since a and /? take only these values. We shall
show now that a(n) vanishes infinitely often.
For suppose that, for certain n and p,
a(n) = 0, a(n+l) = a(n + 2)= ... =a(n+p)=l;
then
c(n + r+l) = n+l, 0<r<p,
and
b(n + r+l) = b(n)+l, 0<r<^,
and
i(b(n)+l,n + r+l) = 0,0<r<p,
so that the functions <pn+r+\{i), 0<r<p. are all identical. However
the functions <pn+i{t), <pn+p+i(f) are not identical if
w+^+l = 2-3»+1-5»+1
and so, for a large enough p, a(n+p+l) = 0.

RECURSIVE CONVERGENCE 35
On the other hand a(n) = 1 for infinitely many n, for if
a(n) = a(n+l)=a(n + 2)= ... =a(n+p) = 0
then
b(n + r+l) = b(n), 0<r<p,
and
i(b(n), n + r+l)=l, 0<r<p,
so that none of the functions q>n+r+i{t), 0<r<£>, is identical with
q>b(n){t). Since however, if m = 36(")-7-ll&, then q>m(t) is identical
with <pb(n)(t), and since 36<™> • 7 • 11*> 7 • 11*>n for a large enough k,
therefore a(n+p+l)=l for a large enough value of p.
It follows that, for infinitely many values of n,
a(n) = 0 and a(n + l)=l
and so
b(n+l) = b(n)+l;
since b(n) is non-decreasing, and changes by a unit at a time, this
shows that the values of b(n) comprise all the non-negative integers.
Let
rp(n) = (p{fix{x<n&E(c(n), x))}
and
y(n) = P(y>(n))-
We shall prove that the function
g(n) = y{/ix(a(x) = 0&x>n)}
is not primitive recursive.
For if g(n) were primitive recursive we could find m so that
g(n) = <pm(n)
identically; then since m+1 is a value of b(t) for a suitable t, we
can find a least t, n+1 say, such that b(n+ l) = ra+1 and therefore
b(n) = m.
For this value of n we have
a(n) = 0, a(n+l)=l, c(w + l) = w+l

36 RECURSIVE CONVERGENCE
and i(m, w+l) = 0; this last equation shows that the functions
(pm{t) and (pn+i{t) are identical and therefore, by hypothesis
g(n + l) = (pn+i(n + l) = d(n+l).
We have seen that there is necessarily an JV > n for which a(N) = 0;
let n+p+ 1 be the least value (above n) for which a(n+p + l) = 0,
so that a(n + r)=l for l<r<p. Accordingly
fix(a(x) = 0&x>n+l) = n+p+l,
c(n + r+l) = n+l, for 0<r<£>,
and
f(n+p+l) = q>{fix(x<n+p+l&R(c(n+p+l), x))}
= <p{/j,x(x<n+p+l&R(n + l,x))}.
However, since a(n+p)=l and a(n+p + l) = 0, therefore
j(c(n +p), n +p +1) = 1,
whence
j(n+l,n+p+l)=l,
which shows that there is a value of x such that x<n+p+l and
R(n+1, x), and therefore
ip(n+p + l) = <p{/j,xR(n+l,x)} = d(n+l).
It follows that
g(n+l) = P{f(/ix(a(x) = 0&x>n+l))}
= {l{rp(n+p + \)} = {l{a(n+\)}
and this contradiction establishes the Theorem.
Theorem 1, 9 There is a primitive recursive real number with a
decimal expansion which is not primitive recursive.
Let a(n), y(n) be the functions denned in the previous section,
and let
r(») = 4y(»)+l
<p(n) = 3 • <x(a(n)) + fi(a(n)) ■ r(n).
Since y{n) takes only the values 0, 1 therefore r(n) takes only

RECURSIVE CONVERGENCE
37
the values 1, 5 and <p{n) takes only the values 1, 3, 5. Furthermore
since a(n) = 0 for infinitely many n, therefore there are infinitely
many values of n for which q>(n) # 3. We observe that the condition
q>(n) # 3 is equivalent to a(n) = 0. It follows that
q>{fix(<p(x) ^3&x>n)} = (p{fix{a{n) = 0&x>n)}
= r{fix{a{n) = 0&x^n)} = q(n), say.
Denoting by r(n) the remainder when n is divided by 10, and by
s(n) the quotient {n — r(w)}/10, we define
f(n+l) = r{3-(p{n) + s[3-q{n+l)]}
so that xp{n +1) is formed by multiplying q>(n) by 3 and then adding
1 or 0 according as the first q>{k), for &>w+ 1, which is not 3, has
the value 5 or 1.
The significance of this definition is best understood by
considering the carrying figures when a decimal with digits 1, 3, 5 only
is multiplied by 3.
We prove first that the recursive real numbers
w(lc-\- 1)
Now J infc is the decimal expansion to n places of the
fc<« 10
w(k)
number 3 J \kt f°r a large enough value of N. Thus
but
and therefore
0,or#)_v f(k+l) 1
*£.io* *£. io* <io»'
0<\lw
*£. iofc io»
„ y(fc+l) „ <p(&)
*£. io* *£.10*
<
10"
which proves the equality of the real numbers in question. The

38
RECURSIVE CONVERGENCE
following table shows the values of %p{n+\) for all possible
combinations of values of q>(n) and q(n+l).
<p(n)
1
3
5
1
3
5
fl(
n + 1)
1
1
1
5
5
5
V(w + 1)
3
9
5
4
0
0
Hence if we define t(n) to take the value 1 for odd values of n,
and the value 5 for even n, we have
q(n+l) = t(f(n+l)).
If therefore rp(n) were primitive recursive, then q(n) would be
primitive recursive, and by the previous theorem we know that
this is not the case.
In classical analysis an expansion like Zf(n+ 1)-10_™ in which
rp(n)=t9 for infinitely many n, is unique, but the classical proof
of this is not valid in recursive analysis. The above example does
not therefore answer conclusively the question whether there is
a primitive recursive real number which cannot have a primitive
recursive expansion.

Chapter II
RECURSIVE AND RELATIVE CONTINUITY
Uniform and doubly uniform equivalents of a relatively
continuous recursive function. Upper and lower bounds and the
impossibility of their attainment. Conditions which ensure that a
relatively continuous function vanishes if it changes sign and the
nonexistence of a recursive root in the general case.
In this chapter we study the properties of recursive continuity
and relative continuity, the former a property of single recursive
functions and the latter a property of convergent sequences of
recursive functions. We define, first, recursive continuity at a
point and in an interval.
2. Recursive continuity
2, 0. 1 A recursive function f(x) is recursively continuous at x\ if
there is a recursive function C\(k) such that, for all x,
x-xi = 0(ci(4)) -> f(x) - f{xi) = 0(4).
2,0. 2 f(x) is uniformly (or interval) recursively continuous for
a<x<b if there is a c(k) such that, for all x, X, a<x<X<b,
x-X = 0(c(k)) -* f{x)-f(X) = 0(k).
Thus, for instance, the function x2 is uniformly recursively
continuous in any interval (—lO, lO) since x2 — X2 = 0(k) if
x-X = 0(k+p+l).
If f(x), g(x) are recursively continuous at x\ (in an interval i)
then so of course are f(x) ± g(x), f(x)>g{x) and also f(x)lg(x),
provided that g{xi)=£0 {\g{x)\> 10" in i).
2, 1 Relative continuity
If f(n, x) is recursively convergent for a<x<b and if there is
a strictly increasing recursive function c(k) and a recursive C(k, x, y)
39

40
RECURSIVE AND RELATIVE CONTINUITY
such that for all x, X satisfying a<,x<X<b and x — X=0(c(k)),
f(n, x)-f(n, X) = 0{k), for all n>C(k, x, X), then we say that f(n, x)
is continuous for a<x<b, relative to n. (We observe that relative
continuity is a uniform property). A function f(n, x) which is
continuous relative to n is not necessary continuous for any
particular values of n. Thus for instance if (p{p/q) = Q, where Q = q/{p, q)
and (p, q) is the highest common factor of p and q then <p(x) is not
continuous for any rational value of x, for if p\q and p\\q\ are in
their lowest terms with 0<\plq—2>i/<Zi|< l/tyi2 then q>2qi and so
<P(pl<l) — <p{Villi) = 1 — ?i>?i> 1; hence if f{n, x) = (p{x)/n, then f(n, x)
is not continuous for any n, but
l/(». 2>i/?i)-/(». 1*2/32)1 < |?i -?2|/»= 0(4)
for n> \q\ — 32110*, so that f{n,x) is relatively continuous.
Like continuity, relative continuity is preserved under addition,
subtraction and multiplication; furthermore if g(n, x) is relatively
continuous for a<x<b and if for some integer »,\g(n, x)\> 10"
for a<x<b and majorant n, then l/g(n, x) is relatively continuous
for a<x<b.
Theorem 2, 1 Relative continuity is an invariant of the equivalence
relation.
For if g(n, x) is equivalent to f(n, x) and if f(n, x) is continuous
for a<x<b, relative to n, then, for all x\, x2 satisfying
a < x\ < X2 < b, x\ — x2 = 0(cf(k +1))
and n majorant, we have
g(n, xi) — f(n, xi) = 0(k+ 1), g(n, x2)-f(n, x2) = 0(k+ 1)
f(n, xi}—f{n, X2)=0(k+ 1)
so that
g(n, xi)-g(n, x2) = 0{k),
which proves that g(n, x) is continuous, relative to n.
Theorem 2, 1. 1 // f(n, x) is relatively continuous for a<a;<6, and
\f(n, x)\ > 10-'' for majorant n, then either f(n, #)> 10-'' for all x in
(a, b), or f(n, x)< — 10"'' for all x in (a, b), with n majorant.

RECURSIVE AND RELATIVE CONTINUITY 41
For if x\, X2 are any two points in (a, b), we may divide (x\, X2)
into a finite number of parts such that the values of f(n, x) at any
two points in the same part differ by less than 10-''-1, for majorant
n, and therefore f(n, x\), f(n, X2) have the same sign, for majorant n.
Theorem 2, 2 A relatively continuous function has a uniformly
convergent relatively continuous equivalent.
For if f(n,x) is relatively continuous for «<#<&, there are
recursive functions N(k, x) and c(k) such that, for all x, X satisfying
a<x<tX<sb,x — X = 0(c(k))
we have
f(n,X)-f(n,x) = 0(k),
for majorant n, and
N>n>N(k, x) -> f(N, x)-f(n, x)=0(k).
Let cp(k, x)=f(N(k, x), x), then
p>q-+<p(p,x)-<p{q, x) = 0(q)
and
tp(k, X)-tp(k, x) = f(N(k, X), X)-f(m, X)
+ f(m, X) - f(m, x) + f(m, x) - f(N(k, x), x)
= 3-0(&), for majorant m,
which shows that (p(n, x) is uniformly convergent and relatively
continuous.
Since
<p(n, x) — f(n, x)= <p(n, x) — f(m, x) + f{m, x) — f(n,x)
= 2-0(&), for majorant n,
therefore y{n, x) is equivalent to f(n, x).
We observe further that, for w>&, and X— x=0{c{k)),
(p(n, X) — y(n, x) = 5 • 0(k)
for <p(n, X) — <p(k, X) = 0(k) and y(n, %) — <p(k, x) = 0(k) if n>k, and
(p{k, X)-(p(k,x)=3-0(k), if X-x = 0(c(k)).
2, 2 In virtue of Theorem 2, 2 we may, without loss of generality

42 RECURSIVE AND RELATIVE CONTINUITY
suppose any relatively continuous function f(n, x) to be in standard
form, so that p>q-^~ f(p,x) — f(q,x) = 0(q).
Theorem 2, 2. 1 // f(n, x) is relatively continuous for a<x<,b and
if s(n) is recursively convergent to a rational x*, a<x*<b, then
f(n, s(n)) and f(n, x*) are equivalent.
Since s(n) is recursively convergent to x*, there is a recursive,
strictly increasing function v(k) such that
n > v(k) -> s(n) — x* = 0(k)
and therefore
n > v(c(k)) -> s(n) — x* = 0(c(k))
whence it follows that
n> v(c(k)) -> f(n, s(n)) - f(n, x*) = 5- 0(k)
and so f{n, s(n)) and f(n, x*) are equivalent.
In particular if f(x) is recursively continuous for a<x<,b, and
s(n) is recursively convergent to x*, a<x* <b, then f{s(n)) is
recursively convergent to f(x*).
2, 2. 1 Whether the sequence s(n) has a rational limit or not, the
following form of Theorem 2, 2. 1 holds.
Theorem 2,2.2 // f(n,x) is continuous for a<x<b relative to
n and if s(n) is recursively convergent, a<s(w)<6, then f(n, s(n)) is
recursively convergent.
Since s(n) is recursively convergent there is a recursive function
N(k) such that
N>n>N(k) -> s(N)-s(n) = 0(k),
and by relative continuity,
{x-X = 0{c(k))}&n>k->f(n,x)-f{n, X)=5^0{k)
and therefore, if N > n > N(c(k)),
f(n,s(N))-f(n,s(n)) = 5.0(k).
Hence f(N, s(N))-f(n, s(n))
= f(N, s(N))-f(n, s(N)) + f(n, s(N))-f(n, s(n))
= 6-0{k) if N>n>N{c{k)), since N{c{k))>N(k)>k,
which completes the proof.

RECURSIVE AND RELATIVE CONTINUITY
43
In particular if f(x) is uniformly recursively continuous for
a<x<b, then f(s(n)) is recursively convergent.
Theorem 2, 2. 2. 1 // f(n, x) is continuous for a<x<b, relative to n,
and if s(n),t(n) are equivalent recursive real numbers, a<s(w)<6,
a<t(n)^b, then f(n, s(n)) and f(n, t(n)) are equivalent recursive real
numbers.
For
s(n) — t(n) = 0(c(k)), for majorant n,
and
X-x=0(c(k)) -^ f(n, x)-f(n, X) = 0(k), for n>k,
and so
f(n, s(n)) — f(n,t(n)) = 0(k), for majorant n.
We note again the particular case:
If f(x) is uniformly recursively continuous for a<x<b and s(n), t(n)
are equivalent recursive real numbers satisfying a<s(w)<6,
a<<(w)<6, then f(s(n)) and f(t(n)) are equivalent recursive real
numbers.
2, 2. 2 The recursive real number f(n, s(n)) may be considered to
be the value of the relatively continuous function f(n, x) for the
recursive real number argument s(n). Thus the value of a relatively
continuous (recursively continuous) function for a recursive real
argument is constructed, not denned.
Such a definition as
f(x) = 0 if x is rational
= 1 if x is irrational
finds no place in recursive analysis. A recursive function is
necessarily continuous for a recursive irrational real argument.
2, 2. 3 If f(n, x) is relatively continuous for a<x<b and g(n, t)
is uniformly convergent for a<<</?, both functions in standard
form, and if a<g(n, t)<b for a<£</3 then
f(k+l,g(cf(k+l),t))
is called the application of / to g or the result of substituting
g in / and is denoted by fg{k, t).

44 RECURSIVE AND RELATIVE CONTINUITY
Theorem 2,2.3 For w>&+1, ra>c/(&+1) and <%<£</?,
fg(lc,t)-f(n,g(m,t)) = 0(lc).
In fact, since
g(m,t)-g(cf(k+l),t)=0(cf(k+l) for rn>cf(k+l)
therefore
fg(k, t)-f(k+ 1, g(m, t))=3-0(k+ 1)
and since, for n > k + 1,
/(n, g(m, t))-f(k+ 1, sr(m, 0) = 0(&+ 1)
therefore
fg(k,t)-f(n,g(m,t)) = 4.0(k+l).
Theorem 2, 2. 4 /<7(&, £) is recursively uniformly convergent in
standard form.
For if q>p,
fg(Q, t)- fg(p, t) = f(q+l, g(cf(q + 1), 0)- f(p + 1, !7(c/(<Z + !),«))
+ /(3»+1, <7(c/(?+1), t))-f(p + l, g(cf(p+1), *))
= 0(2> + l)+3-0(p+l) = 0(2J).
Theorem 2, 2. 5 // q>(n, x), y(n, t) are equivalents of a relatively
continuous f(n, x) and uniformly convergent g(n, t), all in standard
form then cpy(k, t) is equivalent to fg(k, t).
Since g(m, t) and y{m, t) are equivalent there is a recursive M(k, t)
such that
m > M(k, t) -+ g(m, t) - y{m, t) = 0(k),
and therefore
n>Jc&m>M(cf(k), t) -> f(n, g(m, t))-f(n, y(m, t)) = 5- 0(k).
But by the equivalence of f(n, x) and q>(n, x)
f(n,y(m,t)) — (p(n,y(m,t)) = 0(k), for majorant n,
and therefore
f(n,g(m,t)) — (p(n,y(m,t)) = 0(k), for majorant m, n,
and the result now follows from Theorem 2, 2. 3.

RECURSIVE AND RELATIVE CONTINUITY 45
2, 2. 4 If f(n, x) is relatively continuous and g(n, t) is uniformly
recursively convergent, neither necessarily in standard form, and
if F(n, x), G(n, t) are standard form equivalents then we define
fg{n, t) to be FG(n, t).
Theorem 2, 2. 6 // f(n, x) is relatively continuous for «<£<& and
if g(n, t) is relatively continuous for <%<£</?, with a<g(n, t)<b, for
majorant n and <%<£</?, then fg(n,t) is relatively continuous for
oc<t<p.
We may, without loss of generality suppose that / and g are in
standard form since any equivalent G of g also satisfies
a<G(n,t)<b, for majorant n, and a<£</?.
Then, if
<x<t<T<p, and T-t=0(cg(cf(k+l)+l))
fg(n,T)-fg(n,t) = f(n+l,g(cf(n+l),T))-
-f(n+l,g(Cf(n+l),t))^0(1c),
for w>&.
Theorem 2, 3 A relatively continuous function is absolutely bounded.
Let f(n, x) be relatively continuous in (a, b); divide (a, b) into p
parts each of length 0(c(l)) so that, for any two x, X in the same
part, and w> 1, f(n, x) — f(n, X) = 5-0(l). It follows that for any
x in (a, b) and »>1,
\f{n,x)-f{n,a)\<\p,
and, of course, since f(n, a) is recursively convergent in standard
form, f(n, a) — f(1, a) = 0(1), for »>1.
2, 3 Theorem 2, 3 is a consequence of the uniformity of relative
continuity. We shall illustrate this by constructing a recursive
function f(n, x) which is recursively convergent, and continuous
for each n, but unbounded. Let a„ be the decimal expansion of
j/2 to n decimal places, ao=l and bn = an+ 10"™, w>0. Further,
let f(0,x) = 0 and
f(r+ 1, x) = f(r, x), if ao<,x<ar or br<x<bo,
= r + (x — ar)l(ar+i-ar), if ar<x<Or+i,
= r + (x-br)l(br+l-br), if br+l<X<br,
= r+\, if ar+i<z<&r+i.

46 RECURSIVE AND RELATIVE CONTINUITY
Let x lie in (a, b); if x2 < 2, let ar+i be the first a for which x<ar+i,
then f(n, x) is constant for w>r. Similarly if x2> 2 and 6r+i is the
first b for which 6r+i < x, then /(w, a;) is constant for n > r. Thus
/(w, a;) is recursively convergent, and obviously f(n, x) is continuous
for each fixed n. But f(n, x) is not absolutely bounded, for f(r, ar) = r,
and so f(n, x) is not relatively continuous, as may also be seen by
noting that f(r + 1, ar+i)< f(r+l,Or)=l while Or+i — aT may be made
as small as we please.
Theorem 2, 4 // f(n, x) is relatively continuous in (a, b) then there
is a recursively convergent h(n) such that, for a<x<b, f(n,x)<h(n)
relative to n.
The inequality f(n,x)<h(n) holds relative to n if
f(n, x)<h(n)+10~k
for majorant n.
Let 10A be the smallest power of 10 which exceeds b — a,
ar" = a + (6-a)r/10c""+A,
h(n) = max f(n, arn),
0<r<(Xn)+A
and let lc{n) be the least r for which f(n, arn) = h(n), and «» = «£(„;.
We prove that h(n) is recursively convergent.
Since an = apN, for some p, if iV>w, therefore
h(N)-h(n) = f(N, aN)-f(N, a») + f{N, a»)-/(w, a»)
>/(iV, an)-f(n, an)> - 10~», for N>n;
let <t be the greatest integer for which aan < aN, then aN < aj+1 and so
h(N) -h{n) = f(N, a*) - f(n, a*) + f(n, a") - f(n, a„») + f(n, a„») - f(n, a»)
<{f(N, a")-f(n, o*)}+ {/(», o*)-/(», «„»)}
<6/10*+1, for N>n>k+\,
whence it follows that, for N>n>k+l,h(N) — h(n) = 0(k).
Take any x in (a, b) and let r be the greatest integer for which
arn<x, so that x lies between aT™ and a?+1 and therefore
/(n,z)-/(n,aT») = 0(£)

RECURSIVE AND RELATIVE CONTINUITY
47
for w>&+1. It follows that
f(n,x)<h(n)+10-*
for n > k + 1.
In a similar way we may determine the lower bound l(n).
2, 4 If the sequence an were recursively convergent then since
f(n,an) = h(n) we could say that the function f(n,x) attains its
maximum, the recursive real number h(n), for the recursive real
value an of its argument. The following example shows, however,
that a proof of the recursive convergence of an is impossible.
Let g(n) be any primitive recursive function and let y(n) be the
primitive recursive function which takes the value n if g(r) = 0
for all r<n, and takes the value p if p is the first value of r<n
for which g(r) > 0. Thus y(ri) < n for all n, and y(n) < n for some n
only if there is a value of n for which g(n) > 0. We shall show that
a proof of the recursive convergence of an constitutes a decision
procedure for the equation
g(n)=0
but as we have observed the existence of such a decision procedure
would entail a contradiction in recursive arithmetic.
Let
f(n,x) = (l-2-*»))x, if 0<z<l,
= -(l-2i-»)z, if -l<z<0.
Then, if y(n) = n, the greatest value of f(n,x) occurs when x—1,
but if y(n)<n the greatest value of f(n, x) occurs when x= — 1.
Let an be the value of x for which f(n, x) takes its greatest value;
if an is recursive convergent there is a recursive function njc such
that
n^nk -*■ an — ank=0(k)
and so for »>»i, \an — an^\ < 1/10, and therefore, since an is an
integer, an = ani for all n.
Accordingly, if a"i = l then an=l for all w>wi and so y(n) = n
for all n and g(n)=0 for all n; but if a"i= — 1 then y{ni)<ni and
there is a value of r < n\ for which g(n) ^ 0, showing that a proof

48 RECURSIVE AND RELATIVE CONTINUITY
of recursive convergence for an would constitute a decision procedure
for the equation g(n)=0. The sequence an is of course classically
convergent and is an example of a convergent sequence which is
not recursively convergent.
2, 4. 1 Although Theorem 2, 2 suffices for all our purposes the
following result shows how much that theorem may be
strengthened.
Theorem 2, 5 Every relatively continuous function has a doubly
uniformly continuous equivalent.
More precisely, if f(n, x) is recursively convergent in n and
continuous relative to n for a<x<b, then there are recursive functions
F(n, x), and Cf(Jc) such that
1. F(n,x) is equivalent to f{n,x) for a<x<b.
2. a<x<y<b&x-y = 0{cF{k))-+ F(n,x)-F(n,y) = 0(k)
for all n.
3. a<x<b and ra>w>& + l -*■ F(m, x) — F(n, x)=0(k).
Let q>(n,x) = f(N(n,x),x) then
ra>w>& -> cp{m, x) — cp{n, x) = 0(k)
and
n^N(k, x) -*■ q>(n, x) — f(n, x) = 0(k).
Denoting the greatest of N(k, x), N(k, y), C{k, x, y) by M{k, x, y),
we have
<p(n, x)-<p(n, y) = f{N{n, x), x)-f(M{k, x, y), x) + f(M(k, x, y),x)~
-f(M(k, x, y), y) + f(M(k, x, y), y)-f(N(n, y), y)
= 3*0(&), for each n>k and x — y = 0(Cf(k)).
If y is the least integer, positive or negative, such that 10y exceeds
b — a, and if l(k) = Cf(k) + y we define
Jr = (6-o)10-»«
and
arn = a + r-An
so that An = 0(Cf(k)) for n>k and since Cf(k+ l)>C/(&), Jn+i<Zln/10.

RECURSIVE AND RELATIVE CONTINUITY 49
It follows that
n>k -> <p(n, a?+1) — f(n, aTn) = 3• 0(&).
We define next a polygonal approximation to (p(n, z); let
F(n, z) = tp(n, arn) + {<p(n, a?+1)-<p(n, a,")} {x-a^)jAn
for
arn<z<a?+l and l<r+ 1<10*(»>,
so that F(n, z) is recursive and F(n, arn) = <p(n, arn), and for w>&,
and arn<z<a%+1,
F(n, z) - F{n, a,») = 3 • 0(k), F(n, z) - F(n, a?+l) = 3 • 0(4).
Consider now any two z, y in (a, b), z<y, satisfying z — y = 0(cf(k));
let w>& and let fi, v be the greatest and least values of r such
that z<Orn and arn<y respectively. Then since avn — a/U" = 0(c/(fe))
it follows that
F(n, z) - F(n, y) = F(n, z) - F(n, o„») + -F(w, o„") -
- #(w, avn) + #(w, a„«) - F(n, y)
= 9-0(4).
Consider now values of n less than k; since c/(&) > C/(n) +1 therefore
z-y < l/10c/« < l/10c/<">+1.
But
<+1-Or">l/10c/(")+1
and therefore at most one arn lies between z and y. If a; and y lie
in the same closed subinterval (arn, a"+1), since F(n, z) is linear
in z in each subinterval
F(n,z)-F(n,y) F(n,arn)-F(n,a?+1) _ 3 = _3_
z-y arn-<+1 An ' Ak ''
and if z, y lie in adjacent intervals with common end point arn then
F(n,x)-F(n, or*) 3 ^(n, o^) - ^(n, y) 3

50 RECURSIVE AND RELATIVE CONTINUITY
whence, since
F(n, x) - F(n, y)
x-y
lies between F{n, x)-F{n,ar«) ^ F(n, ar»)-F(n,y)
x — arn arn — y
therefore
F(n,x)-F(n,y) = _3_
x-y Ak
whether x, y lie in the same subinterval or not, from which it
follows that
\F(n,x)~F(n,y)\<3-10cfW+r-10-cfW-10-kl(b-a)<3-10->c+1.
Thus, for all values of n,
F(n,x)-F(n,y) = 0(k)
provided that x — y — 0(Cf(k+2)), which proves (2) with
cF(k) = cf(k+2).
Since, for arn<x<a?+1,
F(n, x)-f(n, x) = {F(n, x)-F{n, arn)} + {y{n, arn)-cp{n, x)} +
+ {(p(n,x)-f(n,x)}
= l-0(k)
for n>N(k, x), therefore F(n, x) is equivalent to f(n, x).
Finally, if m > n > k, for any x in (a, b) we can choose r, s so that
a," < asm < x < a?+1 < a?+1
and therefore
F(m, x) - F(n, x) = {F(m, x) - F(m, agm)} + {F(n, arn) - F{n, x)}
+ {(p(m, a3™)-(p(n, asm)} +{tp(n, asm)-<p{n, arn)}
= 10-0(&)
which proves (3).

RECURSIVE AND RELATIVE CONTINUITY
51
2, 5 We come now to consider the fundamental property of
continuous functions. We shall see that the classical property of
continuous functions, that a continuous function vanishes if it changes
sign, remains valid for uniform recursive continuity but not for
relative continuity. We prove first
Theorem 2, 6 // f(x) is uniformly recursively continuous for
a<x<b and f(a)-f(b)<0 then there is a recursive real number s(n)
in (a, b) such that f(s(n)) = 0, relative to n.
We may, without loss of generality suppose that f(a) <0, /(6)>0.
Let ao = a, b0 = b', if /(—— j >0 we define ai = «o, &i=—x— and
if /(£+*) <0 we define oi = 2£+$5, b^b0. Further if /(^±^) > 0
we define an+i = an, 6n+i=——
^ and tff(*Lg!l\<0 then
Cln + bn , ,
Q-n+1— X > °»+l — °»
so that a„ and bn are recursively convergent, and since bn — a„ -*■ 0,
an and bn are equivalent recursive real numbers. It is readily seen
that /(«»)< 0 and f(b„)>0, for this is true with n = 0, and if it is
true for n — k, then since /(a*+i) =/(a*) and /(fefc+i) = /( * k) if
/(^)>0;and/(a,+1) = /(^),/(6,+1) = /(6,)if/(^)<0)
it holds also for n = k+l, and therefore for all n.
Since f(x) is uniformly recursively continuous, /(«„) and f(bn) are
equivalent, that is
\f{bn) —f(an)\< I/I0k, for majorant n,
and so
/(«») = f(bn) = 0, relative to w.
2, 5. 1 A similar argument may be applied to a relatively
continuous function provided that the function satisfies some additional
restriction. We prove

52
RECURSIVE AND RELATIVE CONTINUITY
Theorem 2, 6. 1 // f(n, x) is continuous for a<,x<,b, relative to n,
and f(n, a) < 0, f(n, b) > 0, for all n, and if there are recursive functions
g, h such that, for «<#<&, n^h(x) -> \f(n, x)\ > lO-"^* then there
is a recursive real number sn such that f(n, s«) = 0, relative to n.
Let m(x)=max (g(x),h(x)) and F(x)=f{m(x), x). As in
Theorem 2, 6 there are equivalent recursive real numbers an, bn such
that
F(an)<0, F(bn)>0,
that is,
f(m(an), an)<0, so that f(m(an), a«)< — l/10»(°n>
and similarly,
f(m(bn), an)>l/10»(V.
Since
\f(p, x) — f(m(x), x)\ <l/10m(a:), for p>m(x),
therefore
f(p,an)<0 for p>ra(a„),
and similarly
f(P, bn)>0 for p>m(bn).
However, since bn = an, relative to n,
f(k,bn) — f(k,an) = 3*0(k), for majorant n,
and so
f(k,bn) = 3-0(k), f(k, an) = 3-0(k), for majorant n,
whence it follows that f(n, an) = 0, relative to n.
2, 6 We consider next the general case of a relatively continuous
function, without additional restriction, and prove
Theorem 2, 6. 2 // f(n, x) is continuous for «<#<&, relative to n,
then there are recursive functions a„, bn such that a»<a»+i <bn+\ <6»
and for all x,ak<x<bk-+ f(k + 2, x) = 0(k).
For any rational x let [x] denote the whole part of x and let
{z}*=[10%]/10*. Further let
ar* = a + (&-a)r/10c(*+1>+>'

RECURSIVE AND RELATIVE CONTINUITY
53
(where 10v is the smallest power of 10 which exceeds b — a). Then
for l<r+l<10=(*+1)+»')
/(4+l,o*+l)-/(4+l, ar*) = 3-0(fc+l)
and therefore
|{/(4+ 1, af+l)}t- {f(k+1, ark)}k\ < 1/10*,
which shows that the integers 10*{/(&+1, ark)}k are equal or
consecutive for consecutive values of r. Thus as r varies from
0 to \&><*+V+Y,{i{lc+\,af)}t
takes every value n/10k between any two of its values, and this is the
essential property which a relatively continuous function has in
common with a recursively continuous function. In particular, from
f{n, a) < - lO-'' follows f{k+1, a) <l0~!c+1 for k>fi, and so
{f(k+ 1, «)}*< - 10-*+! < - 10-*; similarly from f(n, b) > 10~"
follows {f(k+ 1, b)}k> 10_&, for k>fi, and therefore there is a least v,
v=vk say, such that {f(k+ 1, «£)}*= 0, that is, f(k+l, a*) = 0(k).
We shall subsequently show by an example that in general the
sequence a\t is not recursively convergent. First however we shall
analyse the position a little more exactly by showing that there
are recursive functions a„,b„ such that an<an+i<6n+i<6„ and
f(k + 2,x) = 0(k),
for all x, ak < x < 6*.
We recall first that from f(k +1, x) < — 1/10* follows
f(k + 2, x)<-lll0k+\ since f(k+2, x)-f(k+l, x) = 0(k+l).
Let ar* = a + (&-a)r/10c«+>', then since f(/j,+ 1, a)< - 1/10'' and
f(/i+l, 6)>1/10'' there is a first r, say r — r^ such that
/Cu+1,<+1)>1/10",
and a greatest s+l<r/J, say s+l = s , such that
/(^+l,a/)<-l/10^,
so that
-l/10"</(^+l)a„")<l/l(y

54 RECURSIVE AND RELATIVE CONTINUITY
for all n from s^ to r^ inclusive. We now define rn, s„, for n^fi,
recursively as follows: suppose that, for some k,
- l/10*</(& + 1, ank) < 1/10*
for all n from Sk to m, and that
f(k+1, <)< - i/io*, f(k+1, «y > i/io*.
Then
f(k + 2, aJJ < - l/l0*+i, /(&+ 2, a£) > l/10*+i.
Let rk+i be the first r greater than 10c(*+1>-c(*>-Sjfc such that
/(&+ 2, «*+!)> l/10*+i
and let Sk+i be the greatest s+l<rk+i such that
/(4 + 2,o,*+i)<-l/10»+i,
so that
-l/10*+1</(A+2, a„*+i)< 1/10*+!
for all n from Sk+i to rk+i inclusive, which completes the definition.
Let aji = «fc, a* =6&. By definition of m, s^, we have, for all A>/a,
- l/10*</(& + 1, a**) < 1/10*
for all n from Sk to » inclusive.
If an*<£<a„+i then /(&+1, a;)— /(&+1, ank) = 5-0(k) so that
/(4+l,a;) = 6-0(4).
Thus for all x, ak<x<bk, we have f(k+l, x) = 6-0(k), and
Although the sequence ak is non-decreasing and bounded above,
and bk is non-increasing and bounded below, nevertheless, as we
shall see, neither a,k nor bk is necessarily recursively convergent,
and it is not possible to decide in general whether bk = a,k relative
to k, or not. However if f(n, x) satisfies some suitable additional
condition we can prove that ak and bk are equivalent recursive
real numbers. Specifically we prove

RECURSIVE AND RELATIVE CONTINUITY
55
Theorem 2, 6. 3 // f(n, x) is continuous for «<#<&, relative to n
f{n,x)-f(n,y)
>1,
and if there is a constant q such that, for a<x<y<b,
for majorant n, then there is a recursively convergent sequence an
such that f(n, an) = 0, relative to n.
By the previous theorem, we can find recursive sequences a^, b^
such that,
Uk <«&+!< bic+i < bjc
and
ciic<x<bic and n^k + 2 -> f(n, x) = 0(k).
But, by hypothesis
0<bk-at<(llq)\f(n, bk)-f(n, ak)\, for majorant n,
and therefore
0<bk-ak<(2lq)-0(Jc)
which proves that ak and bk are recursively convergent.
2. 6. 1 We show now that the sequences ak) bk introduced in
Theorem 2, 6. 2 are not necessarily recursively convergent. As in
§ 2. 4 let g(n) be any primitive recursive function and y(n) the
recursive function which takes the value n if g(r) = 0 for all r < n
and takes the value p if p is the first r < n for which g(r) > 0, so
that y(n) = n unless there is a value p for which g(p)>0, when
y(n)<n for n^p. We define f(n, x) in the range 0<z<3 as follows:
If y(n) = n,
f(n, x) = x— 1, for 0<z<l,
= 0, for l<z<2,
= x — 2, for 2<z<3;
if y{n)=p<n,
f(n,x) = x—l, for 0<z<1-1/(2>+1),
=-1/(^ + 1), for l-ll(p+l)<x<2-ll(p+l),
= x-2, for 2-l/(p+l)<z<3.

56
RECURSIVE AND RELATIVE CONTINUITY
The function f(n, x) so defined is obviously recursively convergent
and continuous for 0<£<3, relative to n. For if N^n then
y{N) = N or y{N)^p<n -> f(N, z)-f(n, x) = 0
and
n < y(N) < N -> 0 < f(n, x) - f(N, x) < l/(w + 1);
moreover
X - x = 0(4) -> /(n, X) ~ /(», z) = 0(4)
for all values of n.
Let «£ denote the first point, and b^ the last, between 0 and 3
where /(4, x) vanishes. Then, if g(n) — 0 for all n, an = 1 but if p
is the first n for which g(n) > 0 then a„ = 2, w > ^». Accordingly if
an were recursively convergent we should have a decision procedure
for the equation g(n) = 0, for we should have an integer n\ such
that a(n) — a(ni) = 0(l) for all n~>n\ and therefore a(ni)<,\\ would
prove g(n) = 0 for all n and a(m)>\\ would prove that there is
an n for which g(n)>0.
We have at the same time shown that it is impossible to decide
whether f(n, x) = 0 relative to n for a single value of x or for an
interval of values, since if we could decide this we should again
have a decision procedure for the equation g(n) = 0.

Chapter III
RECURSIVE AND RELATIVE DIFFERENTIABILITY
The mean value inequalities. Doubly uniform equivalent of a
relatively differentiable function. The mean value theorem. Taylor's
theorem. The uniform mean value theorem. The existence of
relatively differentiable functions not satisfying the uniform mean
value theorem.
3. Differentiability
3, 0. 1 A recursive function f(x) is said to be recursively
differentiable at xq if there is a recursive d(1c) and a number A such that
x-xo*r0(d(k)) -+ f(x)-f(xo) = (x-xo)(A + 0(k)).
3,0.2 f(x) is uniformly recursively differentiable for a<£<& if
there are recursive functions P(x), d(k) such that
a<x<X<b&x-X = 0(d(4)) -> f(x)-f(X) =(x-X)(Hx) + 0(4)).
Pix) is called the recursive derivative in (a, b). In general the
functions d(k), ^(x) will contain any parameter in f(x).
3, 0. 3 A recursively convergent function f(n, x) of an integral
variable n and rational variable x is said to be differentiable for
a<x<b, relative to n if there are recursive functions /*(», x), d(k)
such that, for majorant n,
a<x<X<b & x-X = 0(d(k)) -> f(n, x)~f(n, X)
= (x-X)(fHn,x) + Q(k)).
/1(w, x) is called a relative derivative of f(n, x) in (a, b).
Theorem 3, 0. 1 // f(n, x) is relatively differentiable in (a, b) with
relative derivative ^(n, x) and if <p{n, x), ^(n, x) are equivalent to
f(n, x), /1(w, x) respectively, then <p(n, x) is relatively differentiable in
(a, b) with relative derivative ^(n, x).
57

58 RECURSIVE AND RELATIVE DIFFERENTIABILITY
For, if z<X,
f(n, z)-f(n,X) (p{n, z)-(p{n, X)
z — X z — X
= f{n,z)-(p{n,z) <p{n,X)-f{n,X)
z — X z — X
= 0(4), for majorant n,
and
f1(n,z) = <p1{n,z) + Q(k), for majorant n,
and therefore
a<x<X<b& z—X = 0{d(1c)) -> <p{n, z) — (p(n, X) =
= (z — X)(q>l(n, #) + 3-0(4)) for majorant n.
We note that, in particular, ^{n, z) is a relative derivative of
f(n, z) and /1(w, z) is a relative derivative of <p(n, z).
Theorem 3, 0. 2 // f(n, z) is relatively differentiate in (a, b) with
relative derivative /1(w, z) then f(n, z) and /1(w, z) are continuous for
«<#<&, relative to n.
From
f(n, z)-f(n, X) = (z-X){/i(n, a:)+ 0(4)},
for z—X=0(d(k)) and majorant n, follows, interchanging z, X
f(n,X)-f(n,z) = (X-z){f1(n,X) + 0(k)}, for majorant n,
whence
P-(n, X)—^(w, z) = 2*0(4), for majorant n,
proving that /1(w, z) is relatively continuous.
Since f^n, z) is relatively continuous, \f1{n, z)\ is bounded, by
10A say.
Let
c(4) = max {d{k), 4 + A+l}
then
X — z = 0(c(k)) -*■/(», z) — f(n, X) = 0(4), for majorant n,
which proves that f(n, z) is relatively continuous.

RECURSIVE AND RELATIVE DIFFERENTIABILITY 59
3, 1 Recursive differentiability for all rational x in some interval
does not of course entail uniform recursive differentiability. For
instance if f(x) is denned for z>0 by the conditions
x2 < 2 -> j(x) — — x
x2>2 -> f(x)= + a;
then f(x) is recursive and recursively differentiable for each fixed
rational z>(L But f(x) is not uniformly recursively differentiable
for l<z<2, for if x2<2 and X2>2 then
f(X)~f(,)^X±x>2>2NiiXN
X — x X—x X—x
., . f(X)-f(x) . , , ,
so that —^—i-i-i is unbounded.
X—x
Moreover a function f(n, x) may be relatively differentiable in some
interval without being uniformly differentiable for any fixed value
of n. For suppose that
f(n,plq) = q, if q>n
= 0, if q<n;
then f(n, p/q) is recursively convergent since f(N, p/q) — f(n, p/q) = 0
for N > w > q, and /(w, ^/g) is relatively differentiable in any interval
since
f{n,p\q)-f{n,p'\q') . ,
, — ,, , = 0 for n > max (a, q ).
Plq-p/q
But for any fixed w, and q>n
/(n,l/g)-/(n,l/(g+l))_ , .,,
l/?-l/(?+l) ?l?+ '
which is unbounded, showing that /(w, a;) is not uniformly recursively
differentiable for fixed n.
Theorem 3, 1 // f(x) is recursively differentiable with derivative
Pix) for «<£<&, and if f1(x) = 0, then, for a<x<b, f(x)=f(a).

60 RECURSIVE AND RELATIVE DIFFERENTIABILITY
Let the points ark, 0 < r < i(k) divide (a, b) into equal parts of
length Ak = 0(d(k)), so that, for Ork<x<a*+l, l<r+ l<i(k),
{/(*) —f(<*>rk)}l(x-ark) = 2 >0(k), for majorant n,
whence
f(x)-f(a) = 0
for any x in (a, 6).
Theorem 3, 1. 1 // f(n, x) is differentiable, with relative derivative
^(n, x), for a^x<b, and if g(n,t) is differentiable with relative
derivative g1(n,t)for<x<t</3, and if further a<g(n, t)<b for <x<t</3,
then fg(n,t) is relatively differentiable for a<£</? with relative
derivative fxg{n, t)*gx{n, t).
Consider any two t, T such that a<f<T</3; let e(t,T) be the
exponent of the least power of 10 which exceeds \j{T — t), and let
d(k) = max {dg(k), cg(df(k))).
Then for T-t=0(d(k)),
f(n,g(m,T))-f(n,g(m,t)) ... ... .
LLj-2i %_t ~ Hn, g(m, t))-gl(m, t) =
= {f1(n,g(m,t))+g1(m,t) + 0(k)}-0(k) for majorant m, n.
But, for p>k + e(t, T),
f9(P,T)-fg(p,t) _ f(n,g(m,T))-f(n,g(m,t))
T=i ~f=i + °w
for majorant m, n, and
MP, t)-9HP, t)-Hn, g{m, t))-g^m, 0 =
= {f1(n,g(m,t)) + g1(m,t) + 0(k)}*0(k), for majorant m,n,
whence Theorem 3, 1. 1 follows since fi(n, x) and g1(m, t) are
bounded.
Theorem 3, 2 // f(n, x) is differentiable in (a, b), relative to n,
with relative derivative fl(n, x), and if /1(w, x) = 0, relative to n, for
all x in (a, b) then f(n, x)=f(n, a), relative to n, for all x in (a, b).

RECURSIVE AND RELATIVE DIFFERENTIABILITY 61
Let ark=a + (b — a)r/10d*)+r, where y is the index of the smallest
power of 10 which exceeds b—a, so that
flf+l-ar* = 0(d(i)).
For any x in (a, b), let ask<x<aks+1, then
2S + 1"
■ = /^w, .r) + 0(&), for majorant n,
= 2 •()(&), for majorant n,
and for each r, 0<r<s,
fl", «?+i) -/(». «>*) = /1(n> ^ + Q(jfc)> for ma-orant n>
— 2-0(k), for majorant n,
whence
f(n,x)~f(n,a)
= 2-0(k) for majorant n
x — a
and so f(n, x) = f(n, a), relative to n.
3, 2 The mean value inequalities
Theorem 3, 2. 1 //, for each value of n, f(n, x) is uniformly
recursively differentiable for a<x<b, with recursive derivatives /1(w, x)
then there is a recursive Ckn such that a<Ckn<b and
f(n, b)—f(n, a) „, , „,..
/v 'b /v ' < Pin, e*») + 0(fc)
for each value of n.
Let fin(x, y) denote {f(n, x)—f(n, y)}l(x~y), x<y; if z is the mid
point of (x, y) then [in{x, y) lies between /j,n(x, z) and fin{z, y) and
so fin(x, y) is exceeded by one of fin(x, z), /in(z, y); thus we may bisect
(a, b) repeatedly, choosing a succession of intervals (a, b), («in, b\n),
[a2n, bz11), ..., say, each of which is half its predecessor, and such
that [in{o-rn, brn) is non-decreasing in r.
For a suitable value of r, however,
Marn, brn) = f1(n, ck«) + 0(k),

62 RECURSIVE AND RELATIVE DIFFERENTIABILITY
where we take Ckn to be either Or11, or brn, whichever is in the
interior of (a, b).
The same argument also proves
Theorem 3, 2. 2 Under the conditions of Theorem 3, 2. 1 we can
find a recursive c^™ in (a, b) such that
{/(», b) - f(n, a)}/(b-a)> fi(n, c*») + 0(4),
for each value of n.
3, 2. 1 The mean value inequalities hold also for relative
differentiability. For if iin{arn, brn) is determined as above, and if f(n, x)
is differentiate for «<£<&, relative to n, then for an r satisfying
(6-a)/2»-=0(d(Jfc)) we have
li*{flr%, 6r") = /1(»» C*») + 0(&)
for majorant n, where Ckn is either arn or brn. Thus we have
Theorem 3, 2. 3 // f(n, x) is relatively difjerentiable for a<x<b,
with relative derivative /1(w, x), then there is a recursive Ckn in (a,b)
such that
{/(», b) - f(n, o)}/(6 - a) < /i(n, c*») + 0(4)
/or majorant n,
and the corresponding result with the inequality reversed.
3, 3 We can however prove a far stronger result t han Theorem 3,2.3
as we shall subsequently show (Theorem 3, 3 below).
Theorem 3,2.4 //, for a<x<b, s(n, x) is uniformly recursively
difjerentiable for each fixed n, with derivative a(n, x), and if a(n, x)
is uniformly recursively convergent, then s(n, x) is difjerentiable
relative to n, with relative derivative a(n, x).
It follows from definition 3, 0. 2 that there is a recursive d(n, k)
such that
a<x<y<b&x — y=0(d(n, k)) -> a(n, x) — a{n, y) = 0(k),
and since a(n, x) is uniformly recursively convergent there is an
N(k) such that
a{n, x)-a(N(k), x) = 0(k), for n>N{k).

RECURSIVE AND RELATIVE DIFFERENTIABILITY 63
By Theorem 3, 2. 1 there is a c^™ such that a<x<C]cn<y<b and
s(n, x) — s(n,y) , , „,,,
Jl.L-1 \-lll < a(n, ckn) + 0(4),
x-y
and therefore, for n^N(k) and x—y = 0(d(N(k), k)),
s(n, x) — s(n, y) , , , ,,,.,,> ,-,
-i-i-i -^ - a(n, x)<{a(n, ck")-o(N(k), c*» }
3/ — If
+ {o(N(k),ck*)-o(N(k),x)}
+ {o{N(k), x) - o(n, x)} + 0(k) = 4-0(4),
and similarly, by Theorem 3, 2. 2, for the same n, x, y,
s(n, x) — s(n, y) , .,«,,.
v ' \-±JLL - a(n, x)>±- 0(4),
x-y
which completes the proof.
Theorem 3, 2. 5 //
(i) for «<#<&, g(m, x) is continuous relative to m, and
tx = g(m, a)<gr(ra, x)<8, for majorant m,
(ii) for a < t < (S, f(n, t) is differentiable relative to n and
|/1(w, <)|> 10-'' for majorant n, and f(n,ot) = a,
(iii) for a<,x<b,fg(n,x) = x, relative to n,
then
gf(n, t) = t, relative to n,
for any t such that, for an x<b, <x<t<g(m, x) for majorant m.
It follows from condition (ii) that /1(w, t) is of constant sign, for
a<<</3 and majorant n, and so we may, without loss of generality,
suppose that f\n, £)>10-'' for <%<£</? and majorant n. From (iii)
it follows that f(n, g(m, x)) = x + 0(4), for majorant m, n.
We commence by proving that, if <x^t<g(m, x) for majorant m
and some x<b, then a<f(n,t)<b, for majorant n.
For the inequality which /*(«, t) satisfies shows, by Theorem 3, 2.3

64 RECTTRSIVE AND RELATIVE DIFFERENTIABILITY
that f(n, t) is strictly increasing (for majorant n), and so by (iii)
if « < t < g(m, x), for majorant ra, and x < b, then
a = f(n, a)< f(n, t)< f(n, g(m, x)) = x + 0(k)<b
for a large enough k, and majorant ra, n.
Using the uniform convergence of f(n, x), g(n, x) and the relative
continuity of f(n, x), it follows from (iii) that
f(n, g(m, x)) = x + 5-0(k)
for ra>C/(&), np*k and «<#<&, and therefore, for the same ra, n
and for p>k
f(n,g(m,f(p,t)) = f(n,t) + 6-0(k)
for a<t<g(m, x) and x<b.
However, by Theorem 3, 2. 2, there is a recursive c^™ such that,
writing g for short for g(m, f(p, t)),
\f(n, g)-f(n, t)\ >\g-t\- {P(n, ck«)+0(k)}
for majorant n, and therefore,
9(m,f(p,t))-t = 0(k-/t-l)
for ra>Cf(k), p>k, whence it follows that
gf(n,t) = t, relative to n.
Theorem 3, 3 The Mean Value Theorem. // f(n, x) is differentiable
for a<x<b, relative to n, then we can determine c^, depending only
upon k, such that a<Ck<b and
fin,b)-Jin,a) = HnCk)+m
for majorant n.
Let ar» = a + (6-a)r/10c/'""+'', where (&-«)< lCF, and
and define
g(n, x) = P(n, arn)+fZ^fl {/i(n> a»+1)_/i(w, „,»)}

RECURSIVE AND RELATIVE DIFFERENTIABILITY 65
for arn < x < a?+1, 0 < r < tn = lO-yo'+v, and
G(n,a) = f{n,a),
G(nix) = G(n>ar») + (x-arn)-f1{n,arn) +
for ar™<^<a"+i, 0<r<tn.
Since
S^ri, z) - /i(n, a:) = {/i(n, a,*) - />, a:)} + ^^ {fKn, a?+1) - Hn,a,")}
/in
= 6-0(&) for w>& and «<#<&,
therefore gr(w, a;) is equivalent to ^(n, x), so that g(n, x) is relatively-
continuous.
More precisely, if arn <x <y <a?+1
g(n,x)-g(n,y) = ^yl{fHn,a?+1)-fi(n,ar")} = 5-0(k) for n>k,
/in
and if
x<arn<y,y-x = 0(cfi(k)),
then
g(»,y)-g(»,or») = ^^{/i(»,a?+i)-/1(».«r")} = 6-0(i), for »>4,
/in
and
0(», *) - 9(n, «r") = ^r^ {/^w, Or") - /*(», «r+i)} = 5 • 0(i), for n > 4,
so that g(n, y)~g(n, x) = 0(k— 1), for w>& in both cases.
Furthermore, if arn<x<a£+1,
g(N, x)-g(n, x) = {g(N, x)-g(N, ar«)} + {g(N, ar«)~g(n, a,")} +
+ {g(n,ar")-g(n,x)}
= 2.0(k-l) + {f1(N,ar«)-p(n,ar")},N>n>k,
= 3-0(Jfc-l) for N^n>k.
proving that g(n, x) is uniformly convergent.
We prove next that G(n, x) is differentiable for «<£<&, relative
to n, with relative derivative g(n, x).

66 RECURSIVE AND RELATIVE DIFFERENTIABILITY
If a?_1<x<tarn<y<a"+i then
G(n, y)—G{n, arn) ,,, . y — arn,.,. „ , ... _.■>
y — «r AU n
and
G(n, or")-G(n,x)^
a.n — x ' v ' r "
arn — X
and since
G(n,y)-G(n,x) ^ G{n,y)-G(n,arn) and G(n,arn)-G(n,x)
y — x y — arn arn — x
therefore
G(n,y) — G(n,x) ... , _ „.., . ,
v "' y-±—- - fHn, arn) = 5-Oik), for n>k.
y-x
If on the other hand
arn<x<y<ta?+1
then
G(n,y) — G(n,x) ... , x + y — 2arn .
y — x zn n
so that, again
G(n,y)~G{n,x)_jl{n^n) = 5Q{kl ^ n>k
y-x
Thus for any x, y in (a, b) satisfying x — y=0(Cf1(k)) we have
G(n,y) — G(n,x) ,,, ... ,, r ,
v ,y'— v ' - Rii, x) = O(fc-l), for n^k,
y — x
proving that G(n, x) is relatively differentiable, with relative
derivative /1(w, x).

RECURSIVE AND RELATIVE DIFFERENTIABILITY 67
Hence G(n, x) — f(n, x) is relatively differentiate with derivative
which is zero relative to n, and since G(n, a) — f(n, a) = 0, therefore,
by theorem 3, 2, G(n, x) is equivalent to f(n, x).
We shall show next that, for any x, y in (a, b), x<y, there is a
(rational) z between x and y such that
0(n,x)-0(n,y) =
x-y yy >
If arn<ai<x2<a"+1(0<r<tn) then, clearly,
G(n, xi)—G(n,X2)
X\ — X<i
( Xl+X2\
and so, if p, q are respectively the least and the greatest integers
such that x^apn<aan<cy, then
G(n, x) — G(n, y)
x-y
lies between the least and the greatest of
/ x + apA ( agn + y\ ( arn + a%+1\
g\n,—"2—), g\n, 2 ) and 9\n, —~),P<r<q,
and so between the least and the greatest of g(n, x), g(n, y), and
g(n, Orn) for p^r^q; since g(n, x) is a broken line it follows that
there is a rational z between x and y such that
G(n, x) — G(n, y) , .
x-y =g{n>z)
(in fact if we rename the points x, arn, y as br, p—l<r<q+l, then
g(n, t) is linear in each interval 6r<<< br+i; let v be the least integer,
not less than p—1, such that g{n,bv)>{G(n,x) — G(n,y))l(x — y)
then (unless v = p — 1), {G(n, x) — G(n, y)}/{x — y) lies between
g(n, bv-i) and g(n, bv) and is therefore equal to g(n, z) for a rational
z between bv-\ and bv, and if v=p— 1, let [i be the least integer
above v for which g{n, b/J)<{G(n,x) — G(n,y)}l(x — y) then
{G(n,x)-G(n,y)}l(x-y)
lies between g(n, b^-x) and g(n, b^), etc.

68 RECURSIVE AND RELATIVE DIFFERENTIABILITY
Of course z depends on n. Since G(n, x) and f(n, x) are equivalent,
there is a recursive N(1c, x, y) such that, for x =£y,
Gin, x)—Gin, y) f{n,x)—fin,y) „.,, n ,T/7 ,
v ' ' K—L21- JV ' '—JV ,yj = oUc) for n>N(k,x,y);
x — y % — y
let Ck be the value of z which corresponds to the value n = N(1c, x, y)
then
fin, x) — fin, y) , ...,
x —y
for n>N(k, x, y). Since gr(w, x) is equivalent to /^n, x) we conclude
that
f(n,x)~f(n, y)
x-y
= /!(», Cfc) + 0(&), for majorant w.
It is important to note that the sequence Ck is not necessarily
convergent.
We mention one additional condition on f(n, x) which ensures the
convergence of c*.
If for some constant a>0, and a^x<y<b,
' v y>—' y ' ' > __, for maiorant n,
y — x 10"
then there is a convergent cn such that
/(w'fe^/(W'a) = Hn, cn), relative to n.
b — a
For, as we have seen, there is a recursive Ck such that
f(n,b)-f(n,a) = ^ ^ + Q(jfc^ for ma-orant n_
Hence for N>k, and majorant n,
fHn,cN)-fi(n,Ck) = 0(k),
and therefore
Cn—Ck=0(k~ a)

RECURSIVE AND RELATIVE DIFFERENTIABILITY 69
proving that cn is recursively convergent. Since
fHn, cn)-P(n, cm) = 0(k)
if ra>C/i(&) + a and n is majorant, and
f{n,b)-f(n,a) , . .
' — = /^w, cm) + 0(m), for majorant w,
it follows that
f(n,b)-f(n,a)
b — a
fHn, cn), relative to n.
The functions G(n, x), g(n, x) have further important properties
which we have not needed to bring out so far; they serve to prove
the following
Theorem 3, 3. 1 // f(n, x) is relatively differentiable for a<x<b
then it has an equivalent G(n, x) which is differentiable for a<a;<6
uniformly in x and n.
With the notation of the previous theorem, let p and q be the
least and greatest integers respectively such that if x<arn <«,"<?/,
then {g(n, x) — g(n, y)}l(x — y) lies between the least and greatest of
9(n, a?+1)-g(n, a^)
for p — 1 < r < q, and so, since fHn, a"+1) — fHn, Orn) •=» 3 ■ 0(w),
therefore
G(n,y) — G(n,x) ,»,.,.
>»1— i--g{n,x) = g{n,z)-g{n,x) =
y-x
if n<k, whence
G(n, y) — G(n, x)
An A*
— g(n, x) = 0(h), n < k, y — x = 0(c/i(&) + 2).
y—x

70 RECURSIVE AND RELATIVE DIFFERENTIABILITY
Moreover, from
G(n,y)-G(n,z) = ^ ^
since g{n, z) — g(n, z) = 0(k — 1), for n > k and y — z = 0(c/i(&)),
therefore
gfoy>-g(».»> _ y(B> x) = 0(i)
for aK n, and all a;, y in (a, b) satisfying z — y = 0(c/i(&) + 2), which
proves that G(n, x) is differentiable for a<,x<,b, uniformly in z
and n.
Since G(n, z) is relatively continuous, it has necessarily a
uniformly convergent equivalent, but in fact it is itself uniformly
convergent as we shall now show.
Since
G(n, o?+1) - G(n, arn) =\An {P(n, Or») + /i(», o?+1)}
therefore,
G(n, as) = /(», o) + id„ 'S {Wn, VJ+W", oj+i)}.
Denoting r-10c/1<m>_c/1<n> by a(r), it follows that, for m>n,
G(m, arn) - G(n, arn) = G(m, a%r)) - G(n, ar«)
r-l todi+1)-1
= {f(m,a)-f(n,a)} + lAm2\ £ [(/1(»A")-/1(». V)) +
+(/1("».or+i)-/1(».o;+i))]
= 0(w) + ^Zlm-8a(r)-0(w), for ra>w,
= 0(w) + 4(6 — a)-0(w), m>w.
However, for ar"<a;<a?+1,
{G(m, z)-G(w, a;)} - {G(m, arn)-G(n, Orn)}
' G(m, z) - G(m, arn) G(n, z) - G(n, arn)
■-(z — arn) ,
[ z — Orn z — arn
= (z — arn){g{m, zi) — g(n, z2)}, where z\, z2 both lie in (z, arn)
= 4:(z — arn)-0(n—l), for m>w,

RECURSIVE AND RELATIVE DIFFERENTIABILITY 71
and therefore
G(m, x) — G(n, x) = 0(&) for mp*n>k + y + 1.
Theorem 3, 3. 2 Rolle's Theorem. // f(n, a) = f(n, b), relative to n,
and if f(n, x) is differentiable in (a, b), relative to n, then we can
determine Ck, depending on k alone, such that a<Ck<b, and fx{n, Ck)
= 0(&), for majorant n.
For there is a recursive Ck such that
f(n, b)~Kn> a) = yi(W; Ck) + 0{k+l), for majorant n
and by hypothesis
f{n,b)b2a{n,a) = 0(k+l), for majorant n,
whence Rolle's theorem follows.
As with the mean value theorem, we can ensure the convergence
of Ck by the condition
fHn,x)-fi(n,y) 1
x-y " 10"'
and when this condition is satisfied, the conclusion in Rolle's
theorem takes the form:
/1(w, c„) = 0, relative to n.
Theorem 3, 3. 3 // f(n, x), g(n, x) are differentiable in (a, b),
relative to n, then there is a recursive Ck such that a<Ck<b and
{f(n, b) - f(n, a)} g*(n, ck) - {g(n, b) - g(n, a)} P(n, ck) = 0(k),
for majorant n.
We need only apply Rolle's Theorem to the function
H(n, x) = {f(n, b) - f(n, a)} g(n, x) - {g(n, b) - g(n, a)} f(n, x).
Theorem 3, 3. 4 Cauchy's Theorem. // f(n, x), g(n, x) are
differentiable for a<,x<,b, relative to n, and if there is a recursive «(m),
such that, for sufficiently great values of m,
a+l/m<a;<6— 1/ra -^-g1^, x)>10~xim)

72 RECURSIVE AND RELATIVE DIFFERENTIABILITY
then there is a recursive Ck such that a<Ck<b and
f(n,b)-f(n,a) fHn.c*)
g{n,b)-g{n,a) g\n,ck)
0(h), for majorant n.
Applying Theorem 3,3.3 to the interval (a + 1/m, b— 1/m) we
determine Ckm between a+l/m, b— 1/m such that
{/(», b- l/m)-/(», a + 1/m)} yi(», e*™)
— {gr(w, 6—1/m) —gr(w, a+l/m)}/1^, Cfcm) = 0(A;), for majorant n.
By the mean value Theorem, with lc = ot{m)+ 1, and m> 102-'',
a(w, b- \jm)-g(n, a+l/m) > \Qy-"^)-i
whence, writing akm for c%+2x{m)_y+3
f(n, b- iH-fjn, a + 1/m) = y, c»») for
g(n,b-llm)-g(n,a+llm) g\n,ckm) " J
It remains to prove that
f(n, b) — f(n, a) f(n, b~ 1/m) — f(n, a+l/m)
g(n, b)-g(n, a) g(n, b~ \jm)-g(n, a+l/m)
■0(4+1),
for a suitable choice of m, depending only on k, and for majorant n.
This will follow from the relative continuity of f(n, x) and g(n, x),
if we can find an absolute positive lower bound for g(n, b) — g(n, a).
Let ai, a2 be the points of trisection of (a, b) and write a=ao,
b=a,3; then by the mean value theorem
g(n,ar+i)-g(n,ar) = \(b-a){g\n, c*,r) + 0(&)}, r = 0, 1, 2
whence, by addition, taking & = a(mi) + l where mi is the least
integer which exceeds 3/(6 —a), we have
g(n, b)-g(n, a) = £(&-a) {gri(n, c*. i) +a1(w, c*. 2) + g\n, ck.3) + 3 • 0(&)}
>\{*>-a){gi{n,Ck,t) + Z-0{k)}
>l/milOa(mi)+1
which furnishes the required lower bound.

RECURSIVE AND RELATIVE DIFFERENTIABILITY 73
3, 3. 1 A function f(n, x) is said to be repeatedly differentiable
for a<x<b, relative to n, if there are recursive functions fr(n, x),
dr(k) such that f°(n, x) — f(n, x), and
(D) a<x<y<b&x-y=0(dr(k)) -> {/<"(», x)-f'{n, y)}j(x-y) =
= /'+i(z) + 0(&).
The function fr(n, x) is called the rth relative derivative of f(n, x).
For each fixed value of r, fr+1(n, x) is the derivative of fr(n, x)
relative to n.
If condition D holds only for r<A, then f(n, x) is said to be A +1
times relatively differentiable.
Theorem 3, 3. 5 Taylor's Theorem. // f(n, x) is repeatedly
differentiable for «<#<&, relative to n, and if g(n, x) satisfies the conditions
of Cauchy's Theorem, and if F(n, X, x, r) is defined by the recursive
equations F(n, X, x, 0) = f(n, x),
F(n, X, r + \)=F{n, X, x, r) + (^~^+1 /"•!(„, x)
then there is a recursive Ok in (x, X) such that
f(n, X) = Fin> X, x, r) + ^^ffi *> ■ ^^ /«<», <*) + 0(t),
for major ant n.
We observe first that
for writing
F^n, X, x, r) = ^—^ fi+i(n, x);
rpin, X, x, r) = H—^ f+Hn, x),
we have
F^n, X, x, 0)-f(n, X, x, 0) = 0
and since
F^n, X,x,r + 1) = F^n, X, x, r) +
^""'-^ /•"<->■

74 RECURSIVE AND RELATIVE DIFFERENTIABILITY
therefore
Fx{n, X, x,r + l)-f{n, X, x, r + 1) =#1(w, X, x,r) — f{n, X, x,r).
Furthermore
F(n, X, X, 0) = /(», X), F(n, X, X, r +1) = F(n, X, X, r)
and so
F(n, X, X, r) = f(n, X).
Apply Cauchy's theorem to the functions F(n, X, x, r), g(n, x)
in the interval (x, X), then Ck is determined so that
F(n, X, X, r)-F(n, X, x, r) _ (X-ctf f+Hn, ck)
g(n,X)-g(n,x) r\ gHn,ck)
for majorant n.
By relative continuity we can choose ko so that
\g{n, X)-g(n, x)\<10*;
and writing Ok=Ck+k<,, then
j{n, X) = F(n, X, x, r) + ^^^ ^^ M* <*) + 0(t),
for majorant n.
Taking g(n, x) = (X — x)p we obtain the Cauchy "remainder"
p(r<)
and with p = r + l, the Lagrange "remainder"
(X-XY+1 „^,
T+W* {n'ak)-
3, 4 In Rolle's theorem (and its consequences) the function Ck
determined by the theorem satisfies the inequality a<Ck<b and
we can determine a numeral ra^ such that a + l/m&<c&<6— l/ra^;
we cannot however determine an m independent of lc, such that
a + l/m<c&<6— 1/ra, for it may happen, for some function f(n, x),

RECURSIVE AND RELATIVE DIFFERENTIABILITY 75
as we shall subsequently prove, that however great an ra is chosen
there may be a value of k for which Cjc lies outside the interval
(a + l/m, b— 1/ra)
and yet the convergence of Ck to a or b is non-demonstrable.
We shall prove that the function Ck, determined by Rolle's
theorem, is uniformly contained in [a, b], i.e., that
a + l/m<Cifc<6— 1/ra,
for an ra independent of k, provided that the function f(n, x) is
effectively variable or effectively constant, relative to n.
3, 4. 1 A function f(n, x) is effectively variable in (a, b), relative
to n, if we can determine rationals a, c2 and a numeral a, such that
a<Ci<C2<6 and
\f(n, Ci) — f(n, c2)\ >1/10", for majorant n.
3, 4. 2 A function f(n, x) is effectively constant in (a, b), relative
to n, if a < a; < y < 6->-/(w, x)—f(n, y) = 0(k), for majorant n.
Theorem 3, 4 // f(n, x) is effectively variable in {a, b) relative to n,
then we can determine c in (a, b) and a numeral ft such that
\f(n, c) — f(n, a)\ > 1/10", for majorant n.
Since
\{f(p, ci)-f(p, a)}-{f(p, c2)-f(p, a)}\ = \f(p, ci)-f(p, ca)|>10-
therefore, either
l/(2». ci)-/(i», o)|> 1/10-+1 or |/(2J,ca)-/(3j,o)|>l/10-+1,
i.e.
|/(2»,c)-/(3»,o)|>l/10-+»
where c has the value Cj if the first inequality holds, and the value
C2 otherwise.
But, by convergence,
\f(P> c)~f(n> c)|<l/10a+2, n majorant.

76 RECURSIVE AND RELATIVE DIFFERENTIABILITY
and therefore
\f{n, c) — f(n, a)|> 1/10"+2, for majorant n.
The same argument shows also that \f(n, c) — f(n, 6)|> l/10a+2.
Theorem 3, 4. 1 // f(n, x) is difjerentiable in (a, b) relative to n,
and if we can determine 8, and c in (a, b), such that |/1(w, c)\ > 1/10'3,
for majorant n, then f(n, x) is effectively variable in (a, b), relative to n.
We determine c* in (a, b) so that [c*-c[ = l/10d<5+1)+1, then
f(n, c*)-f{n, c) = ^ c) + 0(/S+1); n majorant;
and so
|/(w)c*)-/(w)c)|>|c*-c|/10^+1=l/10d(,+1)+^+2) n majorant.
Theorem 3, 4. 2 // f(n, x) is effectively constant in (a, b), relative
to n, then f(n, x) is difjerentiable, relative to n, with derivative zero.
For any x, y such that a<,x<y<,b,
f(n> V) — f(n, x) ... . .
—— = 0(Jc), for majorant n.
Theorem 3, 5 The uniform rolle's theorem. // f(n, x) is
difjerentiable, and effectively variable, or effectively constant, in (a, b),
relative to n, and if f(n, a) = f(n, b), relative to n, then we can determine
cjc uniformly contained in the open interval [a, b] such that
f1(n,Ck)=0(k), for majorant n.
Suppose, first, that f(n, x) is effectively variable. By Theorem 3, 4
there is a c in (a, b) such that \f(n, c) — f(n, a)\ > 1/10'3 for majorant n;
since f(n, a) and f(n, b) are equal, relative to n, it follows that
a<c<b.
Without loss of generality we may suppose that
f(n,c) — f(n,a)>10~P for majorant n.
By the mean value theorem we can determine c^1, ce2 in [a, c],
[c, b] respectively, such that, for any q,

RECURSIVE AND RELATIVE DIFFERENTIABILITY 77
and
f(n, b)-f(n, c) = ^ Ce2) + 0(g); for maj0rant n.
o c
Let 0 be the greatest integer such that c— a< 10~e, b — c<10~e,
then, taking
Qo = max(P + l, p-d + l)
we have
/i(n, cJo)> lO6-^1, /i(w, <&)< - 10»-/»-i.
Denoting cJo by a + l/mi, c§o by b—1/1712 then, by the fundamental
theorem for relative continuity, Theorem 2, applied to the relatively
continuous function /1(w, x), we can determine Ck in
(a+l/rai, 6— l/ra2)
such that /!(», Cfc) = 0(&), w majorant.
If f{n, x) is effectively constant then, by Theorem 3, 4. 2, /i(n, a;)
is equivalent to zero and in particular f1(n,\(a + b)) = 0{lc), n
majorant.
Theorem 3, 5. 1 In Theorem 3. 5 the condition that f(n, x) be
effectively variable, or effectively constant, may be replaced by the
condition that ft(n, x) be effectively variable or effectively constant,
relative to n.
For if ^(n, x) is effectively variable, then, by Theorem 3, 4
l/Hw, c)|>l/10'3, n majorant,
and so, by Theorem 3, 4. 1, f(n, x) is effectively variable.
In particular |/1(w, c)\ > l/10fl, n majorant, is a sufficient condition
for the uniform Rolle's theorem.
On the other hand if /1(w, x) is effectively constant in (a, b),
relative to n, so that f1(n,x) — f1(n,a) = 0(lc) for n majorant, then
writing
F(n, x) = f(n, x) — xf1(n, a)
we have
Fx(n, x) = /*(«, x) — ^(n, a) = 0(k), n majorant,

78 RECURSIVE AND RELATIVE DIFFERENTIABILITY
and therefore, F(n,b)— F(n, a)=0(k), n majorant, whence since
f(n, b) = f(n, a), relative to n, we have
(b — a)f1(n,a) = f(n,b) — f(n,a) + 0(k) = 0(k—l), for majorant n.
Hence, for a<x<b,
f1(n,x) = Q(k), for majorant n.
Theorem 3, 5. 2 The uniform mean-value theorem. // f(n, x)
is differ entiable in (a, b) relative to n, and if /1(w, x) is effectively
variable or effectively constant, in (a, b), relative to n, then we can
determine Cjc such that
j{n>hlZa{n>a)=nn,ck)+m,
for majorant n, and Ck is uniformly contained in (a, b)
Write cP(n,x) = f(n,x)-xt[f{n'b)bZa(n'a)}.
If /1(n, x) is effectively variable then there are integers «, V
such that
|/i(w,ci)-/i(w,c2)|>l/10* for n>V,
and so
\^(n, ci)- (pHn, c2)\ > 1/10* for n > V. (i)
However
(p1(n,x)—<p1(m,x)=0(o<,+ \) for w>ra><x + l;
let /a = max (V, a + 1) then taking /j, for n in (i)
l^c)^ 1/2-10*,
where c has one of the values C\,c^, and therefore
\y\n, c)|>l/4'10" for n>p.
Thus, by Theorem 3, 5. 1, <p{n, x) satisfies a sufficient condition
for the uniform Rolle's theorem, and Theorem 3, 5. 2 follows.
If /1(w, x) is effectively constant, then, as in the proof of
Theorem 3, 5. 1
{f(n, b)-f(n,a)}(b-a) = fi(n,a) + 0(k) = Hn,x) + 0(k-l),
for majorant n.

RECURSIVE AND RELATIVE DIFFERENTIABILITY 79
Theorem 3, 5. 3 The uniform cauchy's theorem. // F(n, x),
G(n, x) are differentiable in {a, b), relative to n, with Gx(n, x)> l/10"(m)
for a+l/ra<£<6— 1/m, n>N{m), and if F1^, x)^1^, x) is
effectively variable, or effectively constant in the open interval [a, b], then
we can determine Ck such that
F(n,b)~F(n,a) ^(n, e*) , .... _
n. ' n, ( = 7^7 z + 0(k), for n majorant,
G(n, b)—G(n, a) G1^, ck) " ' '
and Ck is uniformly contained in the open interval [a, b].
Since Fx{n, x)^1^, x) is effectively variable, we can find Q, V
and Ci, c2 in [a, b] such that
Fi(n, a) Fi(n, c2)
> 1/10Q for n > V,
(?i(w, ci) Gi(w, c2)
and so, by uniform convergence, there is a W such that
F*{n, c) F(n,b)-F{n,a)
Gl{n,c) G(n,b)-G{n,a)
> 1/lOQ+i for n > W,
where c has one of the values C\, c2.
Since c lies in [a, b], therefore c lies in (a + l/fi, b— 1/^) for a
certain n; corresponding to fi we can find R, N such that
\Gl{n, x){F(n, b)-F(n, a)}|>l/10«, for n>N
and for a+l/fiKx^b—ll/n, and so in particular for x = c, and
therefore
\Fi(n, c){G{n, b)~G{n, a)}-G^{n, c){F{n, b)-F(n, a)}\ > l/10<2+«+i
for w>max (W, N), which proves that the function
F(n, x){G{n, b)-G{n, a)}-G(n, x){F(n, b)-F(n, a)}
satisfies a sufficient condition for the uniform Rolle's theorem.
Accordingly we can find Ok and Vk and, independent of k, an m
which we take to be not less than fi, such that a+ l/ra<o><6— 1/m
and
F*(n, Ok){G(n, b)-G(n, a)}-G^{n, ak){F(n, b)-F(n, a)}=0(k)

80 RECURSIVE AND RELATIVE DIFFERENTIABILITY
for n~>Vk. Hence writing ck = Ok+R we have, for n^v^+R,
F(n,b)-F(n,a)_Fi(n,Ct)
G(n,b)-G(n,a) G^{n,cky Kh
If on the other hand F1^, x)IG1(n, x) is effectively constant in
[a, b], then
Fi(n, x) F^n, c)
Gi{n, x) &(n, c)
= 0(4), for majorant n
and for any x, c in [a, b]. Since Gl(n, x) is continuous, and so
bounded above, relative to n,
F1(n,x)G1(n,c)-F1(n,c)G1(n,x) = 0(k), for majorant n;
this result holds for any x in [a, b], and so by continuity for any x
in the closed interval (a, b), for majorant n.
Hence
{F{n, b)- F{n, a)} G^{n, c) - {G{n, b)- G(n, a)} l*{n, c) = 0(4),
for majorant n, and therefore, taking any c in the interval
(a- \j[i,b+\f[i),
it follows that
F(n,b)-F(n,a) = F^(n, c)
G{n,b)-G{n,a) G\n,c) ( '
for majorant n, which completes the proof.
Theorem 3, 5. 4 The uniform Taylor's theorem. Since Taylor's
theorem is an immediate consequence of Cauchy's theorem for the
functions
F(n, X, x, r), g{n, x)
with derivatives {relative to n) (X — x)r /r+1(w, x)lr\, gx{n, x)
respectively, it follows from Theorem 3, 5. 3 that the uniform Taylor's
theorem holds provided that (X — x)rfr+1(n,x)lg1(n,x) is effectively
variable, or effectively constant. In particular for the Lagrange
remainder we have g(n, x) = (X — x)r+1, and the condition for the uniform

RECURSIVE AND RELATIVE DIFFERENTIABILITY 81
Taylor's theorem takes the especially simple form that /r+1(w, x)
should be effectively variable, or effectively constant.
3, 5 The uniform Rolle's theorem was established under the
additional condition that f(n, x) is effectively variable, relative to n,
or effectively constant relative to n, and we pointed out the need
for some condition additional to relative differentiability. We shall
now show that a proof of the uniform Rolle's theorem without
additional qualification, is impossible in recursive analysis. We
shall again use the method, which has served in previous chapters,
of showing that a proof in recursive analysis of the uniform Rolle's
theorem would provides a decision procedure for the class of
equations £(w) = 0, where q(n) is any primitive recursive function which
takes only the values 0,1.
Given any recursive Q(n), with g(0) = 0, we define
n
eo = 0, e»+i = e„ + XI (1 - Q(r))
do = 1, dn+i = l/e»+i
and for 0<£<1 and w<3
H \- dn^l-x)
nn,X)~dn2 + (l-2dn)x-
We observe first that if the equation
en = n
is provable, then so is the equation
e(n) - 0.
n
For from en = n follows e„+i = n + l and thence JJ (1 —g(r))=l,
from which we obtain r"°
e(») = e(»)f[(i-e(»-)) = o.
We prove readily that e„<w. For if there is an r<n such that
p(r)=l then e„ = er, but if p(r) = 0 for all r<n then en = n; hence

82 RECURSIVE AND RELATIVE DIFFERENTIABILITY
if there is an r<n for which Q(r)=l, and if ro is the first, then
e„ = n for w<ro and en=ro for w>ro.
It follows that if N > n > 1 then
0<<2„ — ijv<l/w.
For if <2„ > 1 /», then e„ < w and so ejy = e„ and dx = dn \ but if c£» = 1 /«,
then from dN<dn follows
0<<2» — <2jv<1/w.
The magnitude of <2» of course depends upon the existence or
non-existence of an n for which q(ti)=1. In fact we can prove
that if there is a recursive V(k) such that
w> V(k) -> dn=0(k), for all values of n,
then £(w)=0 for all n.
For if e„>10* for w>F(&), then
e»+F(»)>10">w;
since however
e»+i = e» -> e»+p<w
for any p, we have, taking V(n) for £>,
en+i>e„ for all n,
and therefore XI (1 — g(r))>0 f°r &U w> and finally
g(w) = 0 for all n.
We show next, that for w>3 and for 0<£<1.
0</(m, x)<dnA.
Writing, for short, A = i„2/(1 — 2dn), we have
f(n,x) = Mn*Ux+l-(x+X)-y£±p\
whence it follows that (for each n) the rational function f(n, x)
attains its maximum value <2„4 at x=dn-

RECURSIVE AND RELATIVE DIFFERENTIABILITY 83
Furthermore, if 3<n<N and 0<£<1, then
f(N, x)<f(n, x).
For
£ t* _ 2t3{t2+x(2-3t)}
dtt2 + (l-2t)x~ {t2 + {\~2t)xf > '
when 0<£<2/3, and dn is non-increasing.
It follows that, for 3<n<N and 0<z<l,
0</(w, x)-f(N, x)<\jn*.
For if i„>l/w then <2jv = d„ so that f(N, x) = f{n,x); and if
dn=l/n then 0</(w, x)-f(N, z)<<Z„4=l/w4.
Thus fin,x) converges uniformly in x for 0<£<1.
A simple calculation shows that, for 0<tx<X<l,
f(n,X)-fjn, x) _ w (A(A + 1) _ 1
X-x """' \(x + W
_jX-x)X2{X + \)dn2
{x+Xf{X+X)
<iX-x){\-dny<X-x
which proves that f(n, x) is recursively differentiable in x, uniformly
in x and n, and so differentiable relative to n, with derivative
/!(«, x) = Ai„2
(z+A)2
provided that ^(n, x) converges. However, for each w>3, as a;
increases from 0 to 1, fl(n, x) steadily decreases from dn2 to
— <2„4/(l — dn)2 and therefore, if N>n>3, and 0<z<l,
and
/i(iV, x)-fHn, x)<dN2+dnilil~dn)2<dN2 + Mn*
P(N, x)-/i(w, z)> ~dNil(l-dN)2-d„2> -4rfjv4-<42.

84 RECURSIVE AND RELATIVE DIFFERENTIABILITY
If dn> l/w then dx = dn and ^(N, a;) = /1(w, x); but if i„= 1/w then
<iiv<l/w, so that in either case
-4/w*- i/Mz</i(iV, a;)-/i(n, x)< 1/w2 + 4/W*
proving that /^w, a;) converges uniformly in £, 0<z<l.
Since /(w, 0) = /(w, 1) = 0, we have shown that f(n, x) satisfies the
conditions of RoUe's theorem.
We come now to the crux of the proof.
Let us assume that (for any Q(n)) the uniform Rolle's theorem
is provable for f(n, x). Then there is a recursive V(k), a recursive
Cic and an effectively determined integer p such that Cfc>l/p and
n>F(4)-»-/i(n,e*) = 0(4)
for all values of n.
Since
dnHdn -Ck){dn + {1- 2<Z„) Ck]
Hn, et) =
{dn2 + (l-2dn)Ck}2
and
dn + (l- 2dn)ck >d„2 + (l- 2d„)ck,
dn2+(l-2dn)ck<(l-dn)2<l,
it follows that
n> V(k) -> <44/(<2„-c*) = 0(&).
For the given integer p, either dp+l= l/(p + l) or dp+1> l/(p + l).
If dp+l=ll(p+l) then <Z„<l/(p + l) for n>(p + l) so that
|d»-Cifc|>l/p(p + l)
and therefore
n>V(4k+p)-+dn = 0(k)
for all n, from which it follows, as we have seen, that
e(») = o
for all values of n.
On the other hand, if dp+l> l/(p + l) then there is an r between
0 and p +1 for which p(r)= 1. Thus the hypothesis that the uniform
Rolle's theorem is provable for f(n, x) implies the existence of a

RECURSIVE AND RELATIVE DIFFERENTIABILITY 85
decision procedure for the undecidable class of equations g(w) = 0.
An important consequence is that there are recursive junctions
which are neither relatively variable nor relatively constant, since
we have established the uniform Rolle's theorem for function
which have either of these properties.
Of course, the uniform Rolle's theorem may be valid for a function
which is neither relatively constant, nor relatively variable.
Let
h(n, x) = x(l — x)d„.
Clearly h(n, x) is uniformly convergent in (0, 1) and
h(n>0) = h(n> 1) = 0;
moreover, for 0<£<X<1,
h(n, X) — h(n, x)
X — x
(l-2x)dn
= (X — x)dn<{X—x)
so that h(n, x) is differentiable in x, uniformly in x and n, with a
uniformly convergent derivative (1 — 2x)dn- Furthermore
^(n, |) = 0 for all n,
so that the existence of a Ck uniformly contained in (0, 1) is
established. However, if h(n, x) were relatively constant there would
be a recursive V(k, x) such that, in (0, 1),
h(n, x) = 0(k), for n>V(k, x)\
taking a; =1/2 we have
<Z„=4-0(&) for »>F(4,i),
from which it follows that Q(n) = 0 is provable for all n.
And if h(n, x) were relatively variable there is a c in (0, 1) and
integers p, q such that
h(n, c)>l/p for w>q
and so, since h(n, c) is the greatest value of h(n, x) in (0,1) we have
dn>4c/p for w>q;

86 RECURSIVE AND RELATIVE DIFFERENTIABILITY
let r be the greater of p, q then d, > 4/r so that there is an integer n
between 0 and r for which q{n) = 1.
Thus if h(n, x) were relatively variable or relatively constant for
every function q(n) we should again have a decision procedure for
the class of equations g(w) = 0.

Chapter IV
THE RELATIVE INTEGRAL
Ruled functions. Relatively integrable functions. Darboux's
Theorem. Continuity of, and derivative of, the relative integral.
Substitution in the relative integral.
4 Ruled functions
A recursive function f(n, x) is said to be ruled for a<,x<b if f(n, x)
is uniformly recursively convergent for a<x<,b, and if there are
recursive functions arn, vrn, b(n) and t(m, n, r) such that
ao" = a,a"(„)=fe, a?+i>Or", ar" = <m.„.r) for m>n,
and
f(n, x) = vrn, for arn<x<a?+1 and 0<r<6(w)— 1.
A ruled function is absolutely bounded, for if Mq is the greatest
of |/(0, 0,0)1, 0<r<6(0), and of \vr% 0<r<6(0), then |/(0, x)\<MQ
for a<x<b. But, (taking f(n, x) in standard form)
|/(»,ar)-/(0, x)!<l
and therefore \f{n, x)\ <Mo+l, for all n, and for all x in (a, b).
The property of being ruled is not, of course, an invariant of the
equivalence relation.
4, 0. 1 In the definition of a ruled function f(n, x) we require
f(n, x) to be uniformly convergent. Uniformity is needed to ensure
that f(n, xn) converges when xn converges, as the following example
shows. Let in be a nest of intervals whose rational end points tend
monotonely to l/|/2, so that for every rational x in (a, b) x lies
outside in from some n onwards. Further, let f(n, x) = n in the closed
interval i„, and let f(n, x) = 0 outside in; for each value of n, f(n, x)
is a step function, and for rational x, f(n, x) = 0 from some n
onwards, so that f{n, x) converges. But if xn is an end point of in,
87

88 THE RELATIVE INTEGRAL
then f(n, x„) = n so that f(n, xn) -> oo. Of course f(n, x) is not
uniformly convergent, since for any two p, q, with q>p, and x in iq
f(q,x)~f(p,x) = q~p>l.
Theorem 4, 1 The sum, difference, product and quotient of two
ruled functions are ruled functions.
For by combining the subdivisions on which the two functions
are based, we obtain (for each value of n) a subdivision in each
open subinterval of which both functions are constant.
Theorem 4, 1. 1 A relatively continuous function has a ruled
equivalent.
If f(n, x) is relatively continuous for a<x<b and if y is the
least integer such that b — a<t10y, let
ar» = a + (&-a)r/10>'+<,<re), b(n)= 10>'+<,("),
and
y{n, a) = f(n, a), y(n, x) = f(n, a?+1) for arn<x<a?+1,
then <p(n, x) is a ruled equivalent of f(n, x).
Theorem 4, 1. 2 // f(n, x) is relatively continuous for a<x<b and
g(n, t) is a ruled function for a<<</?, and a^g(n, t)<b for a<<</?,
then fg(n, t) is a ruled function for a<<</?.
For
fg(n,t) = f(n + l,g(Cf(n + l),f)).
4, 1 The relative integral
If f(n, x) is ruled in (a, b) then the sum
b(n)-l
2 *V"K+i-Or")
r-0
is called a relative integral of f{n, x) from a to b, (a < b), and is
denoted by If(n, a, b).
If a=b we define If(n,a, 6) = 0, and if a>b,
If(n, a,b)= — If(n, b, a).

THE RELATIVE INTEGRAL 89
The relative integral If(n, a, b) converges recursively. For if
N>n, and if t(N, n, r)<s<t{N> n, r + 1), then
vsN-vrn=0(n)
and therefore
6(n)-l UN.n.r+U-l
If(N,a,b)-If(n,a,b)= £ £ (vsN-vrn)(a?+1-as»)
r-0 s-UN.n,r)
= (b~a)-0(n),
which proves that If(n, a, b) converges recursively.
Theorem 4, 1. 3 // f(n, x), g{n, x) are equivalent ruled functions
then If(n, a, b), Ig{n, a, b) are equivalent.
By combining the subdivisions on which / and g are constant
for a given n, we determine a subdivision (cr™), say, such that both
f(n,x) and g{n,x) are constant in each subinterval (crn,c?+1); if
(irn denotes the mid-point of this subinterval, then
If(n, a, b)~Ig{n, a, b) = Z{f(n, /xrn)-g(n, /*rn)} (c?+1-cr»);
but, for N>n,
/(n,/Hr")-/(#./Kr"H0(n),
and
g(n, f*rn)-g{N, i«r") = 0(»),
and
f(N, /urn)-g(N, jUr»)=0(n), for majorant N,
so that
If(n, a, b) — Ig(n, a, b) = 3(6 — a) ■ 0(n).
4, 2 If a recursive function f(n, x) has a ruled equivalent F(n, x)
in (a, b), then f(n, x) is said to be relatively integrable, with a relative
integral 7f(w, a, b); the integral of f(n, x) may also be denoted by
If(n, a, b). In particular a relatively continuous function is relatively
integrable.
Theorem 4, 1. 3 shows that any two relative integrals of f(n, x)
are equivalent.
We note that a relatively integrable function is bounded; for if
f{n,x) has a ruled equivalent F(n,x), then we know that \F(n, x)\<M

90 THE RELATIVE INTEGRAL
for a certain M, and all x and n, and therefore \f(n, x)\ < M +1
for majorant n.
Theorem 4, 2 Darboux's theorem. // f(n, x) is relatively
integrate in (a, b) and if {xr), 0 < r < N, is a subdivision of (a, b) and
|r any point in (xr, xr+\), l<r + l<N, then
If(k, a, b) - 2 f(n' W (zr+i-*r) = 6(b-a)-0(k),
r-0
for majorant n, and any subdivision (xr) of sufficiently small sub-
intervals.
Let M be an absolute bound of a ruled equivalent F(n, x) of
f(n, x), in (a, b); by Theorem 4, 1. 3
If(k, a, b)-IF{k, a, b) = 3(6-a)-0(4);
since
*Z F(n, fr)(av+i-xr) ~Nf Kn, fr) (xr+1 ~xr) = 2(6-a)- 0(4)
r=0 r-0
for majorant n, it remains to prove that
IF{k, a, b) -Nf F(k, fr) (Xr+i-xr) = (6-o). 0(4),
r-0
for suitable subdivisions
Let (arn) be the subdivision corresponding to the ruled function
F(n, x) (in standard form), so that F(n, x) is constant for
arn<x<ari+l, 0<r<6(w),
for each value of n, and let vrn be the value of F(n, x) in the open
interval (arn,a^+1); then
If(k, a, 6)= J »r*(oJ+i-ar*).
r=0
Further let the length of any of the subintervals xr+i~xr,
0<r<iV—1, be less than a%+l~ark and also less than
(&-a)/2Jf.lO*-&(4).

THE RELATIVE INTEGRAL
91
Finally let cr, 0<r<p be the subdivision formed by combining
the two subdivisions (xr), (ask). In virtue of the limitation on the
lengths of the subintervals (xr, xr+i) at most one point ask falls
into any closed interval (xr, xr+i), 0<r<N~ 1.
Let OHk denote the value of F(k, x) in the open interval (ct, Ct+i).
Then
and
IF{k, a, b) = J <otk{ct+i-ct),
2 F(k, Sr) (xr+l~Xr) = "J ^(4, ^) (Cl+1 - Ct)
where rjt = £r if (ct, c*+i) is contained in (or coincides with) the
interval (xr, xr+\).
If rjt lies between Ct and ct+i then f(k, i]t) = cotk\ let < = <i, fe, ..., <<?
be the values of t for which (ct, Ct+i) does not contain rjt. Since
an interval (cj, Ct+i) which does not contain rjt can arise only when
an ask falls in an interval (xr, xr+i), it follows that q < b(k).
Thus
P— 1 J>— 1
J ^(4, r?«) (Ct+i-Cj) - J OHk(Ct+l-Ct)
(-0 «-0
I W, %,)-<} (c^-c,,)
-1
I-
< 2Mb(k) ■ (b - a)/2M • 10* • 6(4) = (b - a) ■ 0(k)
which completes the proof that
IF(k, a, b) ~Nf F(k, fr) (xr+i-xr) = (b-a)-0(4).
Theorem 4, 2. 1 // f(n, x) is relatively integrable in (a, b) then
\f(n, x)\ is relatively integrable in (a, b) and
\If{n, a, 6)| < I]f](n, a, 6), relative to n.
Since f{n, x) is relatively integrable, f(n, x) has a ruled equivalent

92 THE RELATIVE INTEGEAL
F(n,x), and so \f(n,x)\ has a ruled equivalent \F(n, x)\. Moreover
l^»r"(a?+i-Or")l < ^I^IK+i-ar")
whence the result follows.
Theorem 4, 2. 2 // f(n, x) is relatively integrable in (a, b) and if c
lies between a and b, then f(n, x) is relatively integrable in (a, c) and
(c, b) and
If(n, a, c) + If(n, c, b) = If(n, a, b), relative to n.
Let F(n, x) be a ruled equivalent of f(n, x) in (a, b); then of course
F(n, x) is a ruled equivalent of f(n, x) in (a, c) and (c, b). Since
lF{n, a, c) + IF(n, c, b) = Ip(n, a, b) therefore
If(n, a, c) + If(n, c, b)=If(n, a, b) + 9(b — a)-0(n).
Theorem 4, 2. 3 // f(n, x) and g(n, x) are relatively integrable in
(a,b), then f(n,x) + g(n, x) is relatively integrable and
If(n, a, b) + Ig(n, a, b) = If+g(n, a, b), relative to n.
Let F, G be ruled equivalents of /, g; then F + G is a ruled equivalent
of f + g and
7f(w, a, b) + lG{n, a, fe) = /F+G(w, a, b).
The difference between If(n, a,b) + Ig(n, a,b) and If+g(n, a,b) is
therefore 9(6— a)-0(n).
Theorem 4, 3 // f(n, x) = 0 for a<x<b and n>N, where N does
not depend on x, then lf(n,a,b) = 0 for np*N.
For f{n,x) is ruled and Z,iv»(a?+1 — ar») = 0 for w>iV.
Theorem 4, 3. 1 // f(n, x) is relatively integrable in (a, b) and
f(n,x)>0 in (a,b), then If(n, a, 6)>0, relative to n.
Let F(n, x) be a ruled equivalent of f(n, x), so that
F(n, x) > —10-&, for majorant n,
and therefore
F(k, x)> -2/10*

THE RELATIVE INTEGRAL 93
so that
IF(k, a, b)>-2(b-a)l 10*
and so
If(k,a,b)> ~5(b-a)ll0*.
Similarly if f(n, x) is relatively integrable and f(n, x) = 0(k) in (a, b),
for majorant n, then If(n, a, b) = 5(b — a)-0(k), for majorant n.
Theorem 4, 3. 2 // f(n, x) is relatively integrable in (a, b) then
If(n, a, x) is relatively continuous in (a, b).
If F(n, x) is a ruled equivalent of f(n, x) then \F(n, x)\ is bounded
by 10" say, and so for any x, X such that a<x<X<b, we have
\IF(n, x, X)\<10P{X-x) = 0(k), for X~x = 0(k+p);
but
If(n, a, X) — If(n, a,x) = If(n,x, X), relative to n,
= lF(n,x,X), relative to n,
= 2-Oik), relative to n,
for X-x = 0(k+p).
Theorem 4, 4 // f(n, x) is relatively continuous in (a, b) then
I/(n, a, x) is relatively differentiable in (a, b), with relative derivative
f(n, x).
Let a<t<T<b and q>(n, x) = f(n, x) — f(n,t), so that if T~t =
= 0(c(k)) and t<x<T then
(p(n, x) = 0(k), for majorant n,
and so
{If{n, a, T)-If{n, a, t)}l(T-t)-f(n, t)
= {I<p(n,t!T)+l&(b~a)-0(n)}l(T-t),
by Theorems 4, 2. 2 and 4, 2. 3,
= 5-0(k) + {lS{b-a)l{T-t)}-0(n)
= 6-0(k), for majorant n.
Theorem 4, 4. 1 // f(n, x) has a relative derivative /1(w, x) in (a, b)
then
Ifi(n,a,b) = f(n,b)~f(n,a), relative to n.
For
l}i(n,a,x) — f1(n,x) = 0, relative to n.

94
THE RELATIVE INTEGRAL
4. 3 Substitution in the relative integral
Theorem 4, 5 In the interval (to, h) the function g(n, t) is relatively
differentiable, with a relative derivative gx{n, t), and cx<,g(n, <)</? for
majorant n. If f(n,x) is relatively continuous for <%<£</?, and if
a = g(n, to),b = g(n,h) relative to n, then
If(n, a, b) = Ifg.gi(n, to, h), relative to n.
From the two conditions (i) g(n, to) = a, relative to n, (ii) g(n, to) > a,
it follows that axx,, and similarly that &</?, so that f(n,x) is
continuous in (a, b), relative to n, and I/(n, a, x) exists for a<x<b.
Since fg{n, t) and gx{n, t) are both relatively continuous in (to, h),
therefore the integral Ifg.gl{n,to,t) exists for fo<<<<i.
Writing F(n, x) for If(n, a, x), G(n, t) for Fg(n, t) and H(n, t) for
Ifg.gi(n, to, t), it is readily seen that
GP-(n,t)-H1(n,t) = 0, relative to n
and therefore
G(n,h) — G(n,to) = H(n,h), relative to n,
whence, since G(n, to) = F(n, a) and G(n, ti) = F(n, b), relative to n,
the theorem follows.
4. 4 Relatively inverse functions
Theorem 4,6 In the interval 0<x<b, g(m, x) is differentiable
relative to m, with a relative derivative lj(pg(m, x), and
g(m, 0) = a<gr(m, x)</3, for majorant m,
and in the interval <%<£</?, <p(n, t) is continuous relative to n and
q>{n, t)> 10"'', for majorant n. Then g(n, x) and I^n, a, t) are inverse
functions, relative to n.
Denote I^n, a, t) by f(n,t); then for 0<z<&, the relative
derivative of fg(k, x) is
<pg(k, *) • gHb x)

THE RELATIVE INTEGRAL 95
which by hypothesis is equal to unity, relative to k. Hence, for
0<£<&,
4, 4. 1 fg(k, x) = x, relative to k,
and therefore
f(n, g(m,x)) = x, relative to m,n;
by Theorem 3, 2. 5 it follows that, for ot<t<g(m, x), m majorant
and x<b,
4, 4. 2 gf{k, t) = t, relative to k.
Equations 4, 4. 1, 4, 4. 2 show that / and g are relatively inverse
functions.

Chapter V
THE ELEMENTARY FUNCTIONS
The relatively exponential, logarithmic and circular functions.
5 The relatively exponential function E(n, x) is denned by the
recursion
E(0,x)=l,E(n+l,x) = E(n,x) + xn+1l(n+iy.
The function E(n, x) is uniformly recursively convergent in any
interval, for if N is any positive integer, and if \x\ <N and w> 2N,
then
\E(n+r+l, x)-E(n+r, x)\ <{N"/n\} 2-0-+D
< {N2»l(2N)l} 2-0-2-W • 2-C+D
= {(2iV)2iv/(2iV)!} 2-»-2-C+i)
so that, for m>w>2iV,
\E(m, x)-E(n,x)\ <Z/2»,
5, 0. 1 where K = (2N)™I{2N)\.
Since, for \x\<.N, \X\<N, we have
X'-x'
5,0.2
therefore
5,0. 3
X-x
< rNr-i
X«+^-xn+1-(X-x)(n + l)xn
(X-xf
< 2 \x\n~r
Xr-af
X-x
r-1
It follows that
= w(w+l)(2iV)»-i/2».
(n + 1)!
X»+1 — xn+1
X-x
— (n+l)xn
<*\X-x\
2»
96

THE ELEMENTARY FUNCTIONS 97
since (2iV)r/H steadily increases with r up to a maximum for r = 2N
and then steadily decreases, and therefore if
JL — x
we have
\Fn-Fn-1\<2n\X-x\;
but Fo = 0 and therefore
5,1 \Fn\<K\X-x\
from which it follows that E(n, x) is differentiable relative to n,
with relative derivative E(n, x), in any interval —N^x<N.
Accordingly the relative derivative of
E(n, —x)-E{n, x + a)
is zero relative to n, and therefore
E(n, -x)-E(n,x+a) = E(n, 0)-E(n, a)=E(n, a)
relative to n; in particular
E(n, -x)-E(n,x)=l
relative to n, and so
5, 2 E(n, x) ■ E(n, a) = E(n, x + a)
relative to n, which is the familiar property of the exponential
function.
It follows also from 5, 1 that E(n, x) is continuous in x, uniformly
in x and n, in any interval —N<x<,N.
In the same interval
" " (2NY l
5, 2. 1 \E(n, x)\ < 2 Nr/rl = J i±li- -1 < 2K
=0 r-0 r■ &
where K is given by 5, 0. 1.
5, 3 Denoting the reciprocal function \fx by R{n, x), we define
the relatively logarithmic function iog(n, x) by the integral
log(w, x)=-IR(n, 1, x), x>0.

98 THE ELEMENTARY FUNCTIONS
The relative derivative of log (n, x) is therefore \jx.
By Theorem 4, 2. 2
Iii{n, l,a) + IR(n,a,ab) = Iii(n, l,ab), relative to n,
and by Theorem 4, 5, with at for gr(w, £) and R(n, x) for /(w, x)
Ir{ii, a, ab) = IR(n, 1, b), relative to n,
whence it follows that
5, 3. 1 log {n, a) + log (n, fe) = log (n, ab), relative to n.
5, 4 Since E(n, x) is its own relative derivative, and
llRE(n,x) = E{n,x),
therefore in any interval (0, N), E(m, x) has relative derivative
\jRE(m, x) and furthermore
E(m, 0) = 1 <E{m, x)<E(m, N)
and for l<t<E(m, N), R(n, t)> 1/2Z, so that, by Theorem 4,6,
E(m, x) and log(w, x) are relatively inverse functions, and for
0<x<N
5, 4. 1 log(w, E(m, x)) = x, relative to m, n
and, for l<t<E(m, N) with m majorant, we have
5, 4. 2 E(m, log(w, t)) = t, relative to n, m.
Since N is arbitrary, and E(m, N) is arbitrarily great with N,
therefore 4. 1 holds for all £> 0, and 4.2 holds for all <> 1. However
E(m, — x)=\\E(m, x) relative to m, and log(w, ljt)= — log(w, t)
relative to n, so that
log (n, E(m, —x))=— x, relative to m, n
for all £>0, and therefore 4. 1 in fact holds for all x, positive or
negative. Writing \ft for t in 4. 2, we see similarly that 4. 2 holds
also for t<\, and so for all positive values of t.

THE ELEMENTARY FUNCTIONS 99
5, 5 The relatively circular functions sin(w, x), cos(w, x) are of
course denned by the recursions
sin(0, x) = x, sin(w+l, x) = sm{n, x)+( — l)n+1x2n+3l(2n + 3)l,
cos(0, x)=l, cos(w+l, x) = cos(n, x) + (-l)n+1x2n+2l(2n+2y.;
clearly sin(w, 0) = 0, cos(w, 0) = 1 for all n.
The analysis we made of the function E(n, x) shows that sin(w, x)
and cos(w, x) are differentiate relative to n, with relative
derivatives cos(w, x) and — sin(w, x) respectively. One immediate
consequence is that
sin2(w, x) + cos2(w, x)
has relative derivative zero and therefore
sin2(w, x) + cos2(n, x)=l, relative to n,
for all x.
Another consequence is that a relative derivative of the function
cos(w, c — x) cos(w, x) — sin(w, c — x) sin(w, x)
is zero and therefore
cos(w, c) = cos(w, c — x) cos(w, x) — sin(w, c — x) sin(w, x)
relative to n, or, writing x+y for c,
5, 5. 1 cos(w, x + y) =cos(w, x) cos(n, y) — sm(n, x) sin(w, y)
relative to n. Differentiating both sides of this equation as functions
of x, we find
5, 5. 2 sin(w, x + y)=s,m (n, x) cos (n, y) + cos (n, x) sin (n, y)
relative to n, which proves the addition formulae.
5, 6 In preparation for later work we find rough bounds for
sin(w, x) and cos (n, x).
With 0<|a;|<4 and p>l, we have
{cos (p + 2, x)— cos (p, x)}/{cos (p + 2, a;) —cos (p+ 1, x)}
= 1 - (2p + 4)(2p + 3)jx2 < 0,

100 THE ELEMENTARY FUNCTIONS
which shows that cos(p+2, x) Ues between cos (p, x) and
cos (p+ 1, x), and therefore for n>p+ 1 > 2, and \x\ <4, all cos (n, x)
lie between cos (p, x) and cos (p+1, x).
Similarly since
{sin (p +2, a;) —sin (p, x)}l{sm {p+2, x)— sin (p+l, x)}
= l-(2^ + 4)(2^3+5)/a;2<o
for the same range of values of x and p, therefore sin(w, x) lies
between sin (p, x) and &m(p+\,x), for n>p+\>\ and |z|<4.
In particular for 0 < x < 1. 6, sin (n, x) lies between \x and x for w > 2.
In the interval 0<z<3. 2 we have
— 4.12<cos (1, x)<\, — 0.5<cos (2, x)<l
and therefore all cos (n, x), w>0, lie in the interval ( — 4.12,1).
Similarly, in the same interval, 0<sin (0, z)<3.2, and
-2.2<sin(l,z)<l,
and so all sin (n, x), w>0, lie in the interval ( — 2.2, 3.2). In the
interval 1<£<2, sin (0, x)>l and sin (1, x)>2/3 so that
sin (n, x) > 2/3 for all n.
Given any polynomial
2 arxr = g(x),
0<r<n
writing as usual
it follows from Theorems 3, 2. 1 and 3, 2. 2 that if
a<,x<b -> m<tDg(x)<M
then
b — a
(that gr(a;) is uniformly recursively differentiable follows readily
from 5, 0. 3).

THE ELEMENTARY FUNCTIONS 101
For fixed p, since D cos (p, £) = sin (p — 1, x) and D sin (p, x) =
= cos (p, x),
x2p+l
D {sin2 (p, x) + cos2 (p, x)} = (-1)? 2 cos (p, a;) • -
and so in the interval 0<£<3.2,
|D{sin2(p, £) + cos2(p, a;)} | < 10-(3.2)22>+i/(2p+1)!
< io-2j>+20;
for
(3.2)31_ 1 2155 _ 2 2 4 4 8 8 16 16 257 (gp i
~3lT ~ lpi'ITT ~ 2" 3'I'" 7" 8 ■" 15 ' 16 "" 3l' H)51 < TP" < IP
and so
(3.2)'_J_ (32)' ! (32)31
r! ~~ 10'" ~H~ < 10'' 31! ' >6 '
<l/10»-i9
(in fact (3.2)31/(31)! is much smaller than 10-i2 but this bound
amply suffices for our purpose), whence it follows that
|{cos2 (p, x) - l} + sin2 (p, x)\ < (3.2)/102p-2».
At z = 3.1, we have
sin (5, x) > (3.1) {1 - 1.602 + 1.769 - 0.176 + 0.023 - 0.002} =
= 3.1 x 0.012 >0
and so sin (4, 3. 1)>0 and therefore sin (n, 3.1) >0 for all w>4.
At a; = 3.2 we have
sin (4, x) < (3.2) {1 - 1.706 + 0.874 - 0.212 + 0.032} =
=-(3.2) x 0.012 < 0
and therefore sin (3,3.2) <0, and hence sin (n, 3.2)<0 for all w>3.
Between £=3.1 and £=3.2
cos (4, x) < (1 + 4.37 + 0.28)- (4.80+ 1.23) < - 1/3
whence cos (3, x) < — 1/3 and therefore cos (n, x)< —1/3 for all w> 3,

102 THE ELEMENTARY FUNCTIONS
which proves that for each n, sin (n, x) steadily decreases in the
interval (3.1, 3.2).
Let Ao = 3, Ai = 31, A2 = 314, A3 = 3141, and for w>4 let Xn be the
least integer between 31-10"-1 and 32-10™_1 such that
sin(», (2„ + l)10-»)<0
and sin (w, A» 10-™) > 0; A„ is primitive recursive. Writing nn = kn 10"™,
since D sin (n, x) = cos (n, x) and | cos (n, x)\ <5 for |a;|<3.2, we
have
0<sin (n, 7in)— sin {n, nn+ 10-»)<5-10_»
so that 0<sin (n, nn) <5-10~™, and therefore
- 1010-2»<sin (w+1, jt„)<5-10-»+lOis-S"
whence |sin (N, nn)\ < 1/10™-1 for all N, n such that iV>w>16.
Since |cos (n, a;)| > 1/3 for w>3 and 3.1<£<3.2, therefore
sin (N, tin) — sin (N, nn)
Tllf — ?ln
and so
|^iv-7i:»|<3(101-»+10i-^)<l/l0»-2
which proves that nn is primitively recursively convergent. The
inequality
ra>w>16 -> |sin (ra, n„)\ <1/10"~1
shows that sin (ra, nn) = 0, relative to n, ra and in particular
sin (n, Tin) = 0 relative to n.
From the relations
|{cos2(p, z)-l} + sin2(p, 3)1 <3.2/102p-20,
iV>w>16-> \sin(N,Tin)\<lllOn~1
follows
iV>w>16 -> |cos2 (N, 7r„)-l|<l/102»-2i
and therefore, since |1 —cos (N, ti„)\ > 1,
|l+cos(iV, 7r„)|<l/102»-2i.
1
>3

THE ELEMENTARY FUNCTIONS 103
5, 6. 1 From the addition formulae it follows that
2 cos2 (n, \nn)= 1 +cos (n, nn), relative to n,
= 0, relative to n,
so that
cos (n, \nn) = 0, relative to n,
and therefore, since sin (n, x) > 2/3 for 1 < x < 2, and
cos2 (n, x) +sin2 (n, x)= 1, relative to n,
we have
sin (n, 1ji:»)=1, relative to n.
Furthermore
sin (n, 2nn)= 2 sin (n, nn) cos (n, nn), relative to n,
= 0, relative to n,
cos (n, 2n„) = cos2(n, n„) — sin2(w, nn), relative to n,
= 1, relative to n,
whence we find
sin (n, x+ 2nn) = sin (n, x) cos (n, 2nn) + cos (n, x) sin (n, 2nn),
relative to n,
= sin(w, x), relative to n,
and
cos (n, x+ 2jr„) =cos (n, x) cos (n, 2nn) — sin (n, x) sin (n, 2nn),
relative to n,
= cos(w, x), relative to n,
proving that sin (n, x) and cos (n, x) are relatively periodic, with
relative period 2n„.
Since cos (n, \nn — z) = sin (n, x), relative to n, therefore if
0<£<1.6 we have cos (n, \nn — x)>\x for majorant n.
5, 7 It is proved, in the appendix, that the recursive real number

104 THE ELEMENTARY FUNCTIONS
(nn) is primitive recursively transcendental, from which it follows
that there is a primitive recursive np such that
7lp+np>7lp+lllOP+n"
and we shall use this result in the next section.
5, 7. 1 If |£|<£ji;jfc for some k, then
cos (n, z) = cos (n, ^nn—(^nn — x))>l(n„--nic)>lllOl,
for a certain I and majorant n.
Hence
tan (n, x) = sin (n, z)/cos (n, x)
is denned for \x\ < Injc, bounded above by 10' for an I which depends
primitively recursively upon k, and differentiable relative to n,
with relative derivative 1 + tan2 (n, x).
Writing y{n,t)= 1/(1 +t2), we see that q>(n, t) is relatively integrable
with a relative integral from 0 to t, denoted by arctan (n, t). By
Theorem 4,6 tan (n, t) and arctan (n, t) are relatively inverse
functions and for |£|<£ji;jfc
5, 7. 2 arctan (n, tan (m, x)) = x, relative to m, n
and
5, 7. 3 tan (m, arctan (n, t)) = t, relative to n, m,
with
0<£<tan (m, x), m majorant.
For 0<£<1, and majorant n,
cos (n, \nn — x) = sin (n, x) < 2x,
sin (n, \nn — x) = cos (n, x) > \
and so
tan (n, \nn — x) > \x;
in particular,
tan \n,-7in 1 tends to oo as n tends to oo,
\ 2 nj
so that 7.3 holds for all values of t.

THE ELEMENTARY FUNCTIONS 105
5, 8 The function arcsin (n, x) is denned by the recursion
arcsin (0, x) = x
arcsin {n, x) = arcsin (n-1, x) + j^m 2n+i' n>
The function arcsin (n, x) is recursively convergent for \x\ < 1, and
in any closed interval / inside the interval —1<£<1, the
derivative of arcsin (n, x) is uniformly convergent; we denote this
derivative by g(n, x) and observe that, in /, q(n, x) is also
differentiate with a uniformly convergent derivative a(n, x), say.
Since
x ■ e(n, x)-{\-x*)- a(n, x) = \^mJy *2n+1
therefore, for \x\ < 1,
x-Q(n, x) = (l — x2)-a(n, x), relative to n.
Let | a; | <,^nK for a certain K; then there is an N such that
N<^-l/2»+i
and so
| sin (N, x)\ < cos (N, l/2^+i), relative to N,
<1 -1/3-22^+2, for majorant N,
and therefore
sin (to, x)-q(n, sin (to, z)) = cos2(to, x)-a{n, sin (to, x))
relative to to, n;
from which it follows that
Q(n, sin (to, x)) cos (to, »)= 1, relative to to, w
for \x\ <%tik, and from this in turn that
arcsin (n, sin (to, a;)) = £, relative to to, w.
Since q{n, x)~>\ for £>0, it follows next from Theorem 3, 2. 5
that for \x\ < 1,
sin (to, arcsin (n, x)) = £, relative to n, to
which completes the proof that sin (to, x) and arcsin (w, £) are
relatively inverse functions.

Chapter VI
TRANSFINITE ORDINALS
In this chapter we construct a part of the theory of transfinite
ordinals within recursive arithmetic. The key notion is the
expression of an integer in a scale of notation. The sequence of natural
numbers, in the scale of 3 for instance,
0, 1, 2, 3, 3 + 1, 3 + 2, 2.3, 2.3+1, ..., 32, ..., 32-3+2, ..., 332, ..., 333, ...
has an obvious parallel with the sequence of transfinite ordinals
0, 1, ..., co, co + 1, ..., co2, ..., co2to+2, ..., co™2, ..., co'0'0, ...
which we exploit in the following definition.
By means of addition, multiplication and exponentiation any
positive integer n can be expressed uniquely in the form
CfcS0* + Cfc-xS0*-! + ... + C2S°2 + CiS°l + Co
where s > 2, 0 < Cq < s, 0 < C\, c2, ..., ck < s, 0 < at < az < ... < ajc and
each at is itself of this form. If i?s(w) denotes this representation
of n with scale symbol s then Rs(n) satisfies the recursive equation
Rs(n) = csR>W+Rs(n-csa)
where a is the exponent of the greatest power of s which does not
exceed n, and csa is the greatest multiple of s° not exceeding n.
We define Tmm(n) as the expression obtained by substituting 'co'
for 'm' in the representation of n in the scale of m. For example
TJ (103) is the ordinal co<»+i + 2ro2 +co+ 1 for 103 = 33+1+2.32 + 3+l.
Every ordinal less than the first e-number (an e-number satisfies
coe = e) is expressible in the form Tmm(n), m being any integer greater
than all the integers in the representation of the ordinal; for
instance starting with the ordinal
Q = co"2 + la>m +1 lco" + 21
106

TRANSFINITE ORDINALS
107
we may replace a> by any integer ra>21, forming
n = ram2 + 7ram+llrai7+21
and then Q = Tmm(n).
The familiar definition of inequality between ordinals makes
Q\ <Qz if and only if this inequality holds when, in Q\,Qz we
replace co by any sufficiently large integer.
It is not, however, the expression of a number in a scale itself
which is of importance in the sequel but the transformation from
one number to another by a change of scale. For instance the
number 34, expressed in the scale of 3, is 33 + 2.3 +1, and changing
the scale from 3 to 4 (leaving the digits 0, 1, 2 unchanged) yields
the number 44+2.4+1 = 265 so that under a change of scale from
3 to 4, 34 is transformed into 265. Formally we define Tba(n), the
transform of n under a change of scale from a to b, b > a, as follows.
Let q be the exponent of the greatest power of a contained in n,
and let paq be the greatest multiple of a« contained in n, so that
p and q are primitive recursive functions of a and n, a>2, w>l.
For 6>a>2, we define:
2V»(0) = 0,
Tb«(n) =pbTba(Q) +Tba{n-pa<i), n > 1;
this definition is a course-of-values recursion so that Tba(n) is a
primitive recursive function.
To form an ordinal greater than some Tmm(n), we take TmM(N)
such that the integers obtained by substituting sufficiently large
integers i for a>, say Tim(n) and T(M(N), satisfy
for i^,m,i>M; hence, if m>M, we see that Tam(n)<TmM(N) if
and only if TmM{N)>Tm™{n) = n, i.e. n<Tm^(N)
Thus a decreasing sequence of ordinals takes the form
where, for r> 1, rar+i>rar, and nr+\<T^iTT for)

108
TRANSFINITE ORDINALS
For a given sequence mi, m<i, m®, ... we obtain the longest
decreasing sequence of ordinals by taking nr+i=T^T (nr) — 1,
since To,™(n) = 0 if and only if n = 0, and T% X(n) <TZTT+l(N) if and
only if n<N.
It was proved by Gentzen that transfinite induction over
ordinals up to an e-number is not reducible to ordinary induction,
and therefore the decreasing ordinal theorem, which says that
every decreasing sequence of ordinals is finite, and which is
equivalent to transfinite induction, is not reducible, but transfinite
induction over ordinals less than the first e-number is reducible
to ordinary induction in a rich enough number system like system Z.
Whether or not this reduction can be carried out within some
formalisation of recursive arithmetic for all ordinals less than the
first e-number is still an open question but we shall establish this
result for ordinals not greater than a>t°t0.
In virtue of the relationship which have exhibited between
transfinite ordinals and the expression of numbers in a scale,
the decreasing ordinal theorem, for ordinals less than the first
e-number, is equivalent to the following proposition F*:
Given any non-decreasing function pr, with po > 2, an initial no, and
the function rir defined by the primitive recursion
nr+1=T£+i(nr)-l
then there is a value of r for which nr=0.
We start by observing that this proposition is a simple
consequence of theorem F:
If mr+i=T^T (mr— 1), then there is a value of r for which mr = 0.
For if rar>0, r<s, and raJ+i = 0, then taking no — mo— 1, if
nje = mic — 1 for some k, we find
nt+i = T*+l(nt) - l=T*+l(mt - 1) - l=ro*+i - 1,
whence by induction, nr = mr — 1 for all r, and therefore ns+i = 0.
We start by proving F for the case mo < pov», which is equivalent
to proving the ordinal theorem for ordinals <a>t0.
Let a(n) be a non-decreasing function, <x(w)>2; the system of

TRANSFTNITE ORDINALS 109
recursive arithmetic in which the following proof will be formalis-
able will depend upon the nature of a(n) and we shall therefore
suppose that a(n) is defined by multiple recursions or at worst by
a transfinite recursion of ordinal a>l)
Let the function y(a, b, c, n) be defined by the primitive recursion
y(a,b,c,0) = (a+l){a(c)}»
y{a, b, c, n+l)=T«»+«>+1){y(a, b, c, n) ^ 1},
and let f(x, p, n) be defined by the double recursion with parameter
substitution
/(0,0,n) = l (i)
f(x + 1, p, n) = <p(x, p, /(0, p, n), n) (ii)
f(0,p+l,n) = <p(o(n) - l,p, /(0, p, n), n) (iii)
where
<p(a, b, c, d) = c + f(a, b, c + d).
The function f(x, p, n) counts the number of terms in the
sequence y(x,p, n, r), r=0, 1, 2, ..., down to a (not necessarily first)
zero. We prove in fact:
for x, p<a(n) and k^f(x,p,n),
y(x,p,n, &) = 0.
Denote this proposition by $(x, p, n). By equation (i) g(0, 0, n)
holds, and in virtue of equation (ii)
g(0, p, n)&%(x, p, n + f(0, p, n)) -> %{x+\, p, n),
for starting from (x + 2){a{n)}P = (x + l){a(n)}v + {o{n)}v with
x + 2<a(n), we reach (x+ l){a(n + f(0, p, n))}? in f(0,p, n) steps and
thence we arrive at zero in a further f(x, p, n + f(0, p, n)) steps, by
hypothesis.
Moreover, starting from
{a(w)}P+i={a(w) - !}{a(n)}P + {a{n)}P,p+l<a(n),
1 See R. Peter, Rekursive Funktionen, Budapest 1957

110 TRANSFINITE ORDINALS
if i$(0,p, n) and %{a(n) — 1, p,n + f(0,p,n)) hold, then, in virtue
of equation (iii), g(0, p + l,n) holds. Hence
3(0, 0, n),
g(0, p, n)&%(x + 1, p, n + f(0, p, n)) -> %{x +1, p, w),
g(0,^,n)&g((7(n) - l,:p,rc + /(0,:p,?l))^g(0,:p + l,rc),
are provable, and from these we may derive %{x, p, n) by
generalised induction1), proving theorem F for mo<p0vo.
The extension to the case mo=pov,) is simple. Writing a for a(n),
(7i for a(n) — 1, since
Oa=OiOal+Oal
it follows that the sequence d(n, r), with
d(n, 0) = oa,
%n,r+l)=T%%?+l){d(n,r) - 1},
reaches zero in
/(0, (71, W) + /(<71, (71, W + /(0, (71, w))=/(0, (7, W)
steps at most, for /(0, <n, w) steps lead from
a^i + a"! to (7i{(7(w + /(0, (7i, w))}ai,
and a further /(<n, oi, »-1-/(0, <ti, w)) lead to a zero.
Consider next the sequence e(x, y, z, n, r) with
e(x, y, z, n, 0) = (a;-|-l){<7(n)}1'+zo(n)
e(x, y, z, n, r+ \)=T°a*X?+l){e{x, y, z, n, r) - 1}.
Define the function f(x, y, z, n) by the triple recursion with
parameter substitution:
/(0, 0, 0,w) = l (iv)
f(x + 1, y, z, n) = <p(z, y, z, /(0,«/, z, n), n) (v)
/(0, y +1, z, n) = tp(o(n) - 2,«/, z, /(0,«/, z, n), n) (vi)
/(0, 0, z+ 1, n)=v(«T(») -^ 2, <;(») -=-1,2, /(0, «r(») - 1, z, »), n) (vii)
x) For the formal details of the derivation see a proof due to P. Bernays
in the author's paper [1].

TRANSFINITE ORDINALS 111
where
tf(x, y, z, c, n) = c + f(x, y, z, c + n),
and let $(x, y, z, n) affirm:
if x, y, z<a(n) and k = f(x, y, z, n) then s(x, y, z, n, k) = 0.
Equation (iv) shows that $(0, 0, 0, n) holds.
Since (x+2)op = (x+ 1)gP + oP, if f(0,y,z,n) steps take one from
ay+za to zero and f(x, y, z, n) steps from (x+ l)oP to zero then by
equation (v) f(x+ 1, y, z, n) steps take one from (x+ 2)ay+za to zero,
proving
g(0, y, z, n)&%(x, y, z, w + /(0, y, z, n))
-^%{^+l,y,z,n). (viii)
Furthermore
a(v+D +w — aioy+za + ay+za
and so by equation (vi)
%(0,y,z,n)&%(<n ^ l,y,z,n + f(0,y,z,n))^%(0,y + l,z,n) (ix)
Finally from
and equation (vii) we deduce
%(0, (7i, z, w)&3((7i - 1, ai, z, n + /(0, (7i, z, n)) -> g(0, 0, z+ 1, n) (x)
From the proved formulae ^(0, 0, 0, n) and (viii), (ix), (x) we derive
%{x, y, z, n)
by an application of a generalised induction schema which is also
reducible to ordinary induction.
A similar proof1) establishes theorem F for a sequence with
initial term
(x+ l)(a(n)}v'+Vi''{n)+Vif-ain^'+---+1'}^n>^
for any definite integer j, and hence for a sequence with initial
term cf", which is equivalent to proving the decreasing ordinal
theorem for ordinals less than or equal to a>0,">. The method of proof
x) loc. cit p. 36.

112
TBANSFINITE ORDINALS
clearly extends beyond this ordinal but to reach a general ordinal
Qn, where Qq = oj, Qn+i = a>an, a quite different approach would
appear to be necessary.
If f(n) is an ordinal recursive function of ordinal Q, so that /(0)
is given and
/(») = ?(»./(*(»)))
where y is primitive recursive and X(n) is a predecessor of n in a
primitive recursive ordering of the natural numbers of ordinal Q,
then it seems likely that the following result holds (hypothesis T).
If B+ is a formalisation of recursive arithmetic which admits
definition by ordinal recursions of any ordinal Q less than the
first e-number, then the number of terms in a decreasing sequence
of ordinals less than or equal to co°, is given by an ordinal recursive
function of ordinal co" where x<Q.
The decreasing ordinal theorem is clearly immediately involved
in definition by ordinal recursion for the determination of
successive values of f(n) defined by
/(») = ?(»,/(*(»)))
requires that the sequence X(n), X(X(n)), A(A(A(w))), ... should reach 0
in an assignable number of steps, assignable of course by a function
which is either primitive recursive, or ordinal recursive for an ordinal
less than the ordinal of / itself.
A recentx), as yet unpublished, result of Alonzo Church, suggests
that hypothesis T may be false for certain ways of representing a
decreasing sequence of ordinals in recursive arithmetic, so that
the particular interpretation of the decreasing ordinal theorem
adopted above may prove to be indispensable for the truth of
hypothesis T.
We consider next the extension of the foregoing recursive
representation of ordinals beyond the first e-number. In chapter I
we introduced the idea of majorant variables, and relations which
held only for majorant variables, i.e. for sufficiently large values
!) Communicated to the International Congress of Mathematicians,
Edinburgh, 1958.

TRANSFINITE ORDINALS
113
of the variables. In this section we shall denote majorant variables
by co, cor, with r>l. We recall that a primitive recursive relation
R(no, n\, ..., nk) for which there exists a constant Cq and primitive
recursive functions
ct+i(no, ni, •■■»»r)»r = 0, 1, ..., k-l,
such that
R(n0, »i, ..., nr, ...,nk)
holds for all no, n\, ..., nk satisfying
no>Co, 7ir+i>cr+i(no, ti\, ..., nr), 0<r<k,
is said to hold for majorant no, n\, ..., nk.
If R(no, »i, ..., nk) holds for majorant Mo, mi, ..., nk we write
S((0, (Ml, C02, •■■, COk).
For example, given definite numerals a, b, c we have
co°>>acob+c
since nn > anb + c if n > max (a, b, c).
An example with two majorant variables is
a>i>a>°'
which holds since N>nnn, for all n and all N satisfying
iV>Ci(M) = M»".
Another example with two majorant variables is
cocoi°> + co°> + 5 > comcoi2 + co°>'°
which holds since
nNn + m» + 5 > nnN2 + nn",
for any m>3 and iV>M"n.
We start by generalising the concept of a number expressed
in a scale of notation with an assigned set of digits.
Let f(x) be a recursive function such that /(0) = 0,/(1)= 1 and
/(a;+1)>/(#) + ! for all x, and let (lc+l)a be the greatest power

114
TRANSFIKITE ORDINALS
of k + 1 which does not exceed n, and c(1c+ 1)° the greatest multiple
of (k+l)a which does not exceed n.
Then we define the function y1K<! by the following recursion:
These equations determine <p{i(,(n) as a function of
<T,/(0),/(l), ...,/(*)
which we call the representation of n with 'digits' f(r),0<r<k,
and base a. For example <p{_a(103) = f(3)o"+ ofW.
When the function / contains more than one argument place
the relevant variable for the construction of <p will be placed in
the last argument place. If i is the identity function i(x) = x, then
9k.k+i(n) is the familiar representation of n in the scale Jc+1 with
digits 0, 1, 2, .,., k.
We note first that
5,5 vUr) =/(»■). if r<4.
For r = r(i+1)0, and so <a(r) = /(r)X<'(0) +dU0)=/(r).
Similarly
5, 5. 1 For a fixed k>\ and a fixed «>/(&)+ 1, ^(m) is strictly
monotonic increasing with w. Write y{n) for 93^ s(w); then we have
to prove q>{n+ l)><p(w)+ 1.
If w<&, this follows from 5,5 since /(»+ l)>/(n) + l; suppose
that
93(71+1) > 93(71)+1
holds for w<m—1 where ra>&+ 1. Let c be the exponent of the
greatest power of k +1 which does not exceed m, b the greatest
integer such that 6(&+l)c<ra and let a = m — b(k+l)c, so that
0<a<(&+l)c, 1 <&<&+! and l<c. Then, by definition,
9j(to) = /(&)«*'(«) +95(a).

TRANSFINITE ORDINALS 115
We consider in turn the cases a = 0, 0<a<(k + 1)C— l,a+l = {k + l)c
and b+l<k+l and finally a+l = (k+l)c, b = k.
When a = 0, tp(a) = 0 and so
tp (m + 1) = j(b)sf^ +1 = <p (m) + 1.
When 0<a<(&+l)c-l then
<p(ra + 1) = f(b)sf^ + y{a + 1) > f(b)sv^ + <p(a) + 1 = <p(m) + 1,
since a + 1<(& + I)c<ra— 1 implies y(a+ 1)>93(a)+ 1 by hypothesis.
When a+l = (&+l)c and b+l<k+l,
<p(ra + 1 ) = /(&+ 1 )sv&) > /(feJs^C) + s^e) > f{b)sv(Q +tp{a) + \=<p{m)+\
for the inequality a + l = (&+l)c<ra implies 1 + 93(a) < q>(a +1) = 8*w.
Finally, when a+l = (/c+l)c and 6= & we have
^(m+1) = <?({&+l}c+1) = s*(c+1>>s*(c>-s>/(&)s''<c> +
+ <p(a) + 1 = <p(ra) +1
for ra>(&+l)c>l + c&>l + c so that by hypothesis
93(0 + 1) > 93(c) + 1,
and, moreover, s>f(b)+l and a+l = (& + l)c<m so that
s<p(c) = y(a _|_ i) ><p(a) + 1.
Thus the inequality holds for w < k, and if it holds for n = m — 1 it
holds also for n = m, and so by induction it holds for all n.
5,5.11 In particular, taking f(x) = i(x) = x, we have that, for
s>&>1, <pitS(n) is strictly increasing with n, and taking
/(*) = /*(*) =VM+l(s),
it follows that if gr>^>l and if s >/*(&) then 93^(71) is strictly
increasing with n.
5, 5. 2 If f(x) and gr(a;) are strictly monotonic increasing and if
h(x) = f(g(x)), p>g{q) and s>f(p) then for ^>1 and all w,
5,5-21 <.{0k+i(»)} = ?t.(»)

116 TRANSFINITE ORDINALS
For w = 0, both sides of equation 5.21 are zero; let us suppose that
the equation holds for n = 0, 1, ..., m — 1. Let a and c be the greatest
integers (a chosen first) such that c {q+l)a<m, and write
b = m-c(q+l)a;
it follows that c<q + 1, b<(q+l)a and m,<(q+\)a+l. Hence
&+iW=?(c)b+1)^+l(8)+C+i(i)
<g(c)(p+lf™+iW + (p+l)K.v+iia)+\
by 5.1, since b<(q+l)a,
= {0(e) + 1}(2» + lj^+i^ < (p+ l)^+i(0)+1,
since gr(c) <gr(g>) <^?+ 1.
This shows that <f>"q.v+l{a) is the exponent of the greatest power
of p+l, and g(c) the multiplier of the greatest multiple of this
power which does not exceed <p%+i(in)- Therefore
<,K„+i(™)}=Hc^vM.v+iW +^{if^+1(b)}
= h(c)st «■» + <p£s(&), by the induction hypothesis,
= <p£s(ra), since m = c(q+l)a + b,
which completes the proof of 5.21 by induction.
5, 5. 3 We define next a function X„(k) which depends upon two
functions p(n), n(n); p(n) and n(n) are arbitrary recursive functions
with p(n) > 1.
We define
X0(k) = k
Xn+l(k) = <PI)$l).xnMn)) + mn) + l(k)-
Writing p'(n) = Xn(p(n))+n(n), we have
^«+i(&) = 9>*W<»)+iW> for all n.
When it is necessary to show the dependance of X upon p, p'
explicitly we shall write X™'Qc) for Xn(k).

TRANSFIKITE ORDINALS 117
To justify the definition of Xn(k) we must show that for all w>0,
Xn(k) is monotonic increasing with k.
This is certainly true for w=0, since Xo(k) = k, and if it is true
for n = m, then it holds for n — m+1, by 5.1.
It follows that, for all n and k, Xn(k)>k.
5, 5. 31 We consider next the relationship between Xp>p', Xp>i
and X«>p'. We shall prove that, if p(r)>\,q{r)>\,
p'ir)* max {Xr™\p{r)), Xr«>P\q{r))},
and
q(r)>XrP«(p(r))
for all r, then
5, 5, 4 X„P-P'(k) = Xn«>P'{XnP><i{k))
for all n, k.
Since Xos>'(&) = k for anys, t therefore 5.4 holds for w = 0; if it holds
for n = m then
=«pxr' l&v tk))
= X™'1(&), by 5.21,
since, by the induction hypothesis,
XmP>P\x) = Xm«.z>'(Xmz>.*(*))-
Thus 5.4 holds for n = m+ 1, and so for any n.
5,5.5 The relationship which holds between XnP>r(p{n)) and
Xni'r(q(n)) persists for all sufficiently large r. More precisely if
P(k)>l, q(k)>l,
r(k)> max {X^{p{k)), Xk«s(q(k))}
and
s{k)> max {XkP.°(p(k)), Xk^(q(k))}
then, for w>&>0,
Xn^r(p(n)) | X„«^(^(n))

118 TRANSFINITE ORDINALS
according as
XnP>°(p(n)) | Xn«>'(q(n)).
Define
t(n), XnP>t, Xrflt, Xnr,t
and Xn*'* simultaneously by the recursions
X0p.t(k) = X0«.t(k) = X0r>t(k) = Xo'-W = Jc,
t(n)= max {XnPJ(p(n)), Xn*.<(?(n)), Xn^{r{n)), Xn^{s{n))}
and
wt X** vat _ Xv*
x:-{+1 = <px«{ , x»-'=<px«{ , .
"+1 *r(n).«n)+l ' "+1 rs(n).J(n) + l
Then, by 5.4,
X„^(X^.^(^(n)) = Xn'*(p(n)))
and
X„^(X„^(^(n)) = Xn«.t(q(n)))
and therefore by 5.3,
Xn*-*(p(n)) = *,.«•'(?(«))
according as
XnP>r{p{n)) | X„«-r(^(n)).
Similarly
X„*.<(p(rc)) | X„ff.*(g(n))
according as
X,.M2>(»))t-*>•(?(»))
from which 5.5 follows,
5,5.6 If p(n)>k>0, and for 0<r<»,2>(r)>l,2>'(r)>Xr».»'(2>(r)),
then
XnP>P\k) = X™\{k).
For Z**'1(4) = vgJ(B)+l(4) = ZS*'(4)> since k<(p(n)).
Hence if N>n and, for n<m<N, p(m)<,k, then
X,,».p'(4) = Xw».»'(4).

TRANSFINITE ORDINALS 119
5, 6 We define
Q0P(k) = k,
fiS+i(*) = ?SLw(*). with cuo = «o,
where co, a>r, r> 1, are majorant variables.
For given k, n and £> (r) these equations determine Qnp(k) as a
function of a>, a>i, ,.., a>«-i which we call a transfinite ordinal of
type n.
A transfinite ordinal of type n is equal to an ordinal of type n + 1
for, if p{n) > k, then
5.6.1 Ql+l{k) = <p^n)m{k) = Qnv{k).
It follows that if p(m)>k for w<m<iV—1 then
5.6.2 Qnv{k) = QNv{k).
In formulating the definition of Qnv(k) we have anticipated a
proof that Qnp{k) is strictly increasing with k; this follows from
Qop{k) = k and theorem 5. 1.
5, 6. 3 It is readily seen that there are ordinals of type n+1 which
are not of lower type. For if k>p(n)>m, then
Q>+1(k)>Q>+l(m) = Q1lP(m).
The relationship between ordinals of different types is given by
Theorem
5, 6. 4 if p(r)>\, q{r)>XrP>v(p(r)) for 0<r<w- 1, then
QnP(k) = Q,fl(XnPM(k)).
We proceed again by induction. For & = 0, the equality follows
immediately from the definitions; if it holds for n = m then
Ql+AX™Ak)) = wQm (aPm1 , <k))
■"sm+lV-"-m+lv II T/a(m).o)B,vr»(m).a(m) + lv ''
= «Pm (k),

120 TRANSFINITE ORDINALS
by hypothesis, and therefore
proving the equality for n = m+l, and so for all n.
5,6.5 If p(r)>\, q(r)>\, 0<r<w then
Gn»(p(n)) = Qj(q(n))
according as
5, 6. 51 X„P.r(p(n)) | Xn«s(q(n))
5, 6. 52 where r(&)>max {X]cP>r(p(k)), Xkv>r(q(k))} for n>k>0.
For, by 5, 6. 4,
®np(p(n)) = Qnr(Xn*s(p(n)))
and
Qnq{q{n)) = i3„r(X„«.'-(^(w))).
whence 6.5 follows from 6.3.
By 5, 5. 5 the relation 6.51 is independent of the choice of the
numbers r (k) when condition 6. 52 is satisfied.
5, 7 The result contained in 6.5 enables us to extend the statement
of the decreasing ordinal theorem to ordinals of any type. In terms
of a sequence of functions pn(k) we define
A*s{n) = XtPn,*{pn(i)).
The sequence of ordinals Qt^ipnii)), w=0, 1, 2, ... is steadily
decreasing if
Airn{n+\)<Airn{n)
where
r„(&)>max {Ar^{n), Arnk{n+\)}, 0<k<i.
Hence the theorem that a decreasing sequence of ordinals is
necessarily finite may be expressed in the form:
If for a given integer i, pn(i) > 0, and for 0 < k < i, pn(k) > 1 and if
r„(fc) = max {Art*(n), Arn*(n+1)}
and
ArnKn+\)<Arn\n)

TRANSFINITE ORDINALS 121
when p„(i)>0, then there exists a value of n for which pn(i) = 0
5, 8 By introducing additional operations, transcending
exponentiation, we may define ordinals of greater "complexity" than
Qnp(k). For instance if we define tetration ba so that °a=l,
(»+i)a = a(«o),
and so 1a = a, 2a = aa, 3a = aa<l, and so on,) then we may generalise
representation in a scale to four operations. Take, a, b, c in turn
to be the greatest integers such that (for &>1)
a(k+l)<,n,
{«(&+1)}»<w,
c{a(k+l)}b<n,
and define
+ <PikAn-c{a(]c+ l)}6). n>k+ 1.
The function <p{xs(n) determines the representation of n with
digits /(0), /(l), ...,/(&), base s, using four operations, addition,
multiplication, exponentiation and tetration.
Taking f(x) = x, we have for instance
<*..( iO3) = (<» + l){a+1co}a + (co + l){aco}{m+1co} + co{°>+ lco} + co{°>co},
(since 1000= (l + 2){222}2 + (l +2)22.222 + 2.222+ 2.22).
Using p operations instead of four we define,
G(k+ 1, a, n+ l) = G(k, a, G(k+ 1, a, n))
with G(3, a, 0)= 1, G(2, a, 0) = 0, G(l, a, 0) = a, G(0, a, ri) = n+\,
glJe(\) = G(p,k+\,h(\))
g$JC(m + l) = G(p-m,g$ik(m),h(m+l)), l<m<p-l;
next, for n>k+l, we determine a(r) so that for l<r<£>, a(r) is
the greatest integer such that, for 1 < s < r,
9lJc(s)<n>
(and therefore a(r)<n, l<r<£>).

122 TRANSFINITE ORDINALS
Finally we define
YUAl) = G{p,s, <*>(1))),
Y'PjcAm+ l) = G(p-m, Y'vX,(m), <pfv,k,M™+ !))), Km<p- 1,
and
<fv.k.M = Y'vMia{p), n>k+\.

Appendix
RECURSIVE IRRATIONALITY AND TRANSCENDENCE
Let Pn(x) be the nth polynomial in an enumeration of all
polynomials of a single variable x, with integral coefficients; let
||z|| = ||s+»y|| = M + |y|
and let s„ be a convergent sequence of rational real or complex
numbers. Then classically lims„ is transcendental if
1. (Vr)(Sk)(SN)(Vn){n>N ^ ||Pr(s„)||>2^}
The convergence of sn is expressed by the condition
2. (Vk){Sv){Vn){n>v-^ ||s„-s„||<2-*}.
Let v(k) be the least value of v, given by (2), such that
n>v(k)^ ||«„-*,(b||<2-<*-*)
and let kr, Nr be the least values of k, N given by (1) such that
3. n>2Vr-».||Pf.(*)l)||>2-*r.
If sn is quasi-recursive, and recursively convergent, so that v(k)
is recursive, and if further the functions Nr, kr in (3) are both quasi-
recursive then the recursive real (complex) number (s„) is said to
be quasi recursively transcendental.
If sn, v(k), Nr and kr are all primitive recursive then the primitive
recursive real number (s„) is said to be primitive recursively
transcendental.
In particular taking Pr{x) to be a linear function of x we obtain
the corresponding definitions of recursive irrationality.
For a quasi-recursive, recursively convergent sequence sn, the
number (sn) is quasi-recursively transcendental if and only if it
is classically transcendental.
123

124 RECURSIVE IRRATIONALITY AND TRANSCENDENCE
For if M = max ||sr|| +1 and if Pr*{x) is the sum of the positive
(Xr<f(l)
values of the terms of the derived polynomial Pr'{x) then
\\Pr(sm)-Pr(Sn)\\<\\sm-Sn\\-Pr*(M),
and calling cr the exponent of the least power of 2 which exceeds
Pr*(M) we have
4. m,n>v(k + cr)-^\\Pr(sm)-Pr(sn)\\<2-K
From (3) and (4) taking kr for k and Nr + v{kr + cr+2) for n, we
find, writing vr{k) for v{kr + cr + 2),
l|JM*„<*r))||>l/2*r+l
whence
5. (Fr)(ff4){||Pr(^»>)ll>l/2*+1}-
If It is the least value of k satisfying (5) then since v(k) is quasi-
recursive, so is %t, and
l|Pr(s^,)||> 1/2VU.
Using (4) again, with & = Ar+2, we have
n>Vr{h)^\\Pr{Sn)\\>M*^
which proves that (sn) is quasi-recursively transcendental. This
theorem does not of course remain true if we replace quasi by
primitive recursion.
For any rational x^O, ex=Z{x)nln\ is primitively recursively
convergent1 and so is n.2
Both e and n are in fact primitive recursively transcendental as we
shall now show.
The primitive recursive transcenpence of e
xp-l n g
Let y(x) = TwII (r — x)v = ^ c^> where q=pn+p— 1,
!) Vide R. L. Goodstein [3].
a) Fide R. L. Goodstein [12].

RECURSIVE IRRATIONALITY AND TRANSCENDENCE 125
and
V(x)= ^,a$%s>A= max \at\;
further let
Ttp(x) = J <p>(x)
where
«-s
(r + *)l
*(*) = Z j-Z-cr+gZr) 0<s<g'.
r=0
Then, by elementary algebra, we may readily show that
\tpP-i(0)\=(nl)P,
and that for r^p—1, qf(0) = 0 (mod p), and for l<ra<w, and
any r, qf(m) = 0 (mod p), so that if p is prime and greater than n,
then Tq>(0) is not divisible by p, but T<p(m) = 0 (mod £>), l<ra<n.
Nowlfy(0) = ^ (r0cr and so, writing EN(m) for 2,mr\r\,
Tcp{0)EN(m) = J (v{2Vnr + Wrra>-}, JV > g,
where
Trar=rar + rrar~1 + r(r— l)rar~2 + ... + r!
and
_ m m2 (r!)miV-r
^r = 7Tl + (»-+l)(r^2)+",+ tf! <3 '
/. , m m2 m» ( 1 1 1 )m
(for 1 + — + — +...H r < <1 + — + — +...+ —> , as may
\ 1! 2! n\ ( 1! 2! n\)
readily be shown by induction over m).
Hence
T<p(0)-EN(m) = Ttp(m) + 3m 2 crOrmr,
where
&r=Wr3-m, so that O<0r<l.

126 RECURSIVE IRRATIONAUTY AND TRANSCENDENCE
But
I 2 crermr\< 2 \cr\mr= _1v,IKr + wOp
MP
<(^ny!>1<m<w>
n
where ilf= IJ(r + w).
Now if p > 2 If
Jfl> (2jf)2M 1 1 (2if)2M
(p-1)! (2Jf-l)I 2*-1 3»(2Jf-l)I
and therefore, writing
H= J {3™am J (v©,^},
if
(21f)2M n
we have \H\ < 1/3.
Thus
I>(0) 2 amEN(m) = aoT(p(0)+ f T<p(m) + H,
where, if £> is a prime greater than max {P, |a0|}, we have
(i) «o?V(0) is an integer not divisible by p,
(ii) 2 amT<p{m) is an integer divisible by p,
(iii) |#|<l/3,
so that
|2V(0) | amEN(m)\>l
Since
~~ mr
therefore
(,?.*} <r?„T
ivir-iv^i ? m"+i
Ifo rlj " Ifo TTI < (n+1)1 ^ (2w^T)! 2»-i'
(2ra)2m 1
<

RECURSIVE IRRATIONALITY AND TRANSCENDENCE 127
and so
|2V(0)[ I am{EN(l)}™- | amEN(m)]\
<W0,L?IPTI)iw
< |?V(0)| -2^w^+2/(iV+1)!< |I>(0)| -A{2n)^l(2n- 1)!2^< 1/3
if iV>|3^Z>(0)|(2w)2»/(2w-l)! = .B, say.
Hence, for N>B and y>max {P, |ao|}, we have
I io,{W))»|>i/3|r^(0)|.
Since EN(1) is primitive recursively convergent (with classical
limit e) it follows that e is primitive recursively transcendental.
The primitive recursive transcendence of n
We preface the proof of the primitive recursive transcendence
of n by a list of the fundamental properties of the norm
\\x + iy\\ = \x\ + \y\
of a complex number, x + iy, with x, y rational.
Let x = x + iy, w = u + iv, then:
1. ||z + w||<||z|| + |H|, for \\x + u + i(y + v)\\ = \x + u\ + \y + v\
<IMI + IM|.
2. ||z±m>||> ||z||—||w||, for \\z — w + w||< \\z — w\\ + \\w\\.
3. ||zw||<||z||-||w||, since \\zw\\ = \xu — yv\ + \xv + yu\
<(M + lyl)(l«l + M).
4. |Z|2<||Z||2<2|Z|2.
5. ||ztt>||>t||z||-||tt>||, for ||zw||2>|z|2.|w|2>J||3||2.||w||2.
6. l/||z||<||l/z||<2/||z||, for \\llz\\ = {\z\ + \y\}Hz* + tP),
and x2 + y2<{\x\ + \y\}2<2(x2 + y2).
Let « be any algebraic number with associated polynomial
oqzcn + aixN-1 +... +aN

128 RECURSIVE IRRATIONALITY AND TRANSCENDENCE
and let the zeros of this polynomial be
Denote |ao|+ ... + \aN\ by -JA and 2 NA by B.
Further let /?2r-i = &«»•> /?&■= —i<Xr> r=l,2, ... N, so that for
Kk<2N,\\pt\\<A,
and let ys, l<s<,M=22N — 1, consist of the sums of the numbers
/?jt, l<,1c<2N, taken / at a time, l</<2iV, so that y,, l<s<M,
are the zeros of a polynomial
Q(z) = boxM + hx1*'1 +... + bM
with integral coefficients, and ||y#||<5.
We define
VW = ( -1)1 b%M iQW}* = cv-^p~1 + cpxP +■■■+ CpM+p-ix^+r-1
where p is a prime greater than |&o&m|,
L{xp{x))= fy,r(x)>K = L(y>(0)) = Zcr(r\),En(x)= f^/(r!)
and
Tn=(l + En{fi1))(l+En(pi)) ... (l+Entfur)).
The numbers yr(0), r =£ p — 1 are all integral multiples of p, but
\pP-1(0) = b%M biip, an integer not divisible by p.
Furthermore if a; is a zero of Q(x), iprix) = Q f°r r<p— 1> and for
if
r>P> X Vr(y™) *s an integer divisible by p.
m=-l
For fixed x, \p{x) -> 0 as £> -> oo, and si milarly
j |cr| |a;|r -4- 0 as y ^ oo,
if
Now T„=l+ J En(yr)+Vn, where, since
r = l
\\En(x)-En(y)-En(x + y)\\<2(\\x\\ + \\y\\)^l(n+l)\,

RECURSIVE IRRATIONALITY AND TRANSCENDENCE 129
for large enough n, and the corresponding inequality holds for
three or more factors, we have
\\V„\\<2MB^I(n+iy.
Bvit
K-E„(y) = L(f(y)) + ZciyiRYli
i
where
so that \\Brit\\<En(B)
and therefore
yi+l yi+2
(*+!)! ' (i+2)l+-
W^^dyiRy^W^M• EniB^ldlB* tends to 0 as p tends to oo.
V i
Thus
K-IEn(y) = L(ZW(y)) + ep
V V
where sp -> 0 as p -> oo, and L(Zrp(y)) is an integer divisible by p.
Hence KTn is the sum of an integer not divisible by p and a term
which tends to zero with p, and a term which, for fixed p, tends to
zero with n.
Choose p so that ||ep||<£, then since 2KMBn+1/{n +1)1 <£ for
n>6KMBB+1IB\, we have
\\Tn\\>ll3K.
However
and so
\\Tn\\<\\l+En(i<x)\\-4:(™-»A<\\l+En(i<x)\\±B
whence
||l+^„(t«)||>l/3^'-4J».
Let nn be the value of n to w places of decimals, then it may be
shown!) that
x) For details see the author's article "The recursive irrationality of n",
loc. cit. p. 269.

130 RECURSIVE IRRATIONALITY AND TRANSCENDENCE
(for w>14)
||l+#2»+i(wi„)||<l/10»-i<l/12ir-4*, for n>K-4B+1,
and so
\\E2n+i(i<x) — E2n+i(inn)\\> l/K-4:B+1, for w>c = max
{K-4B+1, 3 KM•5«+i/5!}
Since ||ot„|| <4^ and ||i«||<4^ therefore
\\E2n+i{ioc)-E2n+i(inn)\\<\\<x-nn\\E2n{±A)<\\<x-nn\\-3«A)
and so, for n>c,
||« —3r„||>l/JK"-4a-3<*^» ... (1)
whence ||« — ji||> l/iir-4B-3<4 >, showing by how much n diflfers
from «, at least.
Since (1) holds for each zero « of oqxn +... +aN therefore, for w>c,
\\avznN + a1nn"+1 + ...+aN\\>\\a0\\-\\nn-M1\\ ••• \\nn-<x„\\-2-M
>\\a0\\IK»-2VB+U 3»-*A
which proves that n is primitive recursively transcendental.

BIBLIOGRAPHICAL NOTES
Chapter I. Recursive arithmetic was introduced by Th. Skolem in
Skolem [1], Various formalisations of recursive arithmetic are given in
Curry [1], Goodstein [15] and Church [2]. For an account of the properties
of general recursive functions see Kleene [2] and Davis [1].
The notions of relative and recursive convergence, and the reduced sequence
were introduced in Goodstein [2]. Tests for recursive convergence were
first given in Goodstein [6].
For a different proof of Theorem 1, see Rice [1].
For the enumeration of primitive recursive functions see Peter [1] which
also contains a very good bibliography on recursive functions.
For Specker's Theorem see Specker [1].
The proof of Theorem 1 is also due to Specker. Recursive real numbers are
studied in Meschkowski [2].
Chapter II. The notions of recursive and relative continuity were
introduced in Goodstein [2], Theorem 2, 4 is due to Meschkowski and was
published in Meschkowski [1].
Theorem 2, 5 was proved by Specker and was first published in Goodstein [5].
Chapter III. The notions of recursive and relative differentiability were
introduced in Goodstein [2],
The classical Theorem that a function continuous in a closed interval has
a maximum value in the interval is not true in recursive analysis; for proofs
see Specker [2], Lacombe [1] and a review by Kreisel, in Kreisel [1] of
Meschkowski [1]. Markov, in Markov [1], gives a non-constructive proof
that for a recursive real function F(x) such that F(0) = — 1, F(l) = 1
there exists a recursive real number c, such that F(c) = 0; a constructive
proof of this result is impossible, for Specker has shown that there is a
recursive sequence Ft of recursive real functions such that F*(0) = — 1> ^"*(1) = 1
and for no rational recursive function s(k, n), recursively convergent in n
for each k, can lim F/c(s(k, n)) = 0 hold. This shows that we cannot identify
m->oo
recursive analysis with a classical study of recursive real numbers. For a
comparison of different levels of constructivist theories see Oonstructivity
in Mathematics, edited by A. Heyting (North-Holland Publishing Co. 1959)
Chapter IV. The relative integral was introduced in Goodstein [11], and
all the results of this chapter were first published in that paper.
131

132
BIBLIOGRAPHICAL NOTES
Chapter V. This theory of recursive ordinals was first developed in
Goodstein [1, 4],
Different constructivist treatments of ordinals are given in Ackermann [1],
Hilbert-Bernays [1], Church [1], Church and Kleene [1].
Appendix. The notion of recursive irrationality (in a different terminology)
was introduced in Goodstein [3], and a proof of the recursive irrationality
of eP for rational non-zero x was given in the same paper. A proof of the
recursive irrationality of n is given in Goodstein [12]. Recursive
transcendence was introduced in the author's paper to the Congress of Mathematicians
in Edinburgh, 1958.

BIBLIOGRAPHY
Ackebmann, W., [1] Zur Widerspruchsfreiheit der Zahlentheorie. Math.
Annalen 117 (1940) 162-194.
[2] Konstruktiver Aufbau eines Abschnitts der zweiten Cantorschen
Zahlenklasse. Math. Zeitschrift 53 (1951) 403-413.
Bebnays, P., [1 ] Uber das Induktionsschema in der rekursiven Zahlentheorie.
Kontrolliertes Denken, Untersuchungen zum Logikkalkul und zur
Logik der Einzelnwissenschaften. Kommissions-Verlag K. Alber,
Miinchen, (1951) 10-17.
Chubch, A., [1] The constructive second number class. Bulletin of the
American Math. Soc. 44 (1938) 224-232.
[2] Binary Recursive Arithmetic. J. de Math. 36 (1957), 39-55.
Church, A. and S. C. Kleene, [ 1 ] Formal definitions in the theory of ordinal
numbers. Fundamenta Mathematicae 28 (1936) 11-21.
Cubby, H. B., [1] A formalisation of recursive arithmetic. American Journal
of Math. 63 (1941) 263-282.
Davis, M., [1] Oomputability and Undecidability. New York 1958.
Good stein, R. L., [1] On the restricted ordinal theorem. The Journal of
Symbolic Logic 9 (1944) 33-41.
[2] Function theory in an axiom-free equation calculus. Proceedings of
London Math. Soc. (2) 48 (1945) 401-434.
[3] The strong convergence of the exponential function. Journal of the
London Math. Soc. 22 (1947) 200-205.
[4] Transfinite ordinals in recursive number theory. The Journal of
Symbolic Logic 12 (1947) 123-129.
[5] Mean value theorems in recursive functions theory. Part I.
Differential mean value theorems. Proceedings of the London Math, Soc, (2)
52 (1950) 81-106
[6] The Gauss test for relative convergence. Amer. J. Math. 72 (1950)
217-228.
[7] Constructive Formalism. Essays on the foundations of mathematics.
University College, Leicester. 1951.
[8] The foundations of mathematics. University College, Leicester.
(1951).
133

134
BIBLIOGRAPHY
[9] Permutation in recursive arithmetic. Math, Scand. 1 (1953) 222-226.
[10] A problem in recursive function theory. The Journal of Symbolic
Logic 12 (1953) 225-232.
[11] The relatively exponential, logarithmic and circular functions in
recursive function theory. Acta Mathematica 92 (1954) 171-190.
[12] The recursive irrationality of n. The Journal of Symbolic Logic 19
(1954) 267-274.
[13] Logic-free formalisations of recursive arithmetic. Math. Scand. 2
(1954) 247-267.
[14] A constructivist theory of plane curves. Fund. Math. 43 (1956)
23-35.
[15] Recursive Number Theory Amsterdam 1957.
[16] Models of prepositional calculi in recursive arithmetic Math. Scand.
6 (1958) 293-296
[17] Recursive Analysis, in Constructivity in Mathematics 37-42.
Gbzegobczyk, A., [1] On the definitions of computable real continuous
functions. Fund. Math. 44 (1947) 61-71.
Hilbebt, D. and P. Bebnays, [1] Orundlagen der Mathematik. Berlin 1934,
39.
Kxeene, S. C, [1 ] On notation for ordinal numbers. The Journal of Symbolic
Logic 3 (1938) 150-155.
[2] Introduction to Metamathematics. Amsterdam 1952.
Kreisel, G., [1] Review of Meschkowski [1], Math. Reviews 1958, 238.
Lacombe, D., [1] Extension de la notion de fonction recursive aux fonctions
d'une ou plusieurs variables reelles. Comptes Rendus 240, (1955)
2478-2480, 241 (1955) 13-14, 151-153.
Meschkowski, H., [1] Zur rekursiven Funktionentheorie. Acta Math. 95
(1956) 9-23.
[2] Rekursive reelle Zahlen. Math. Zeitschrift 66 (1956) 189-202.
Mabkov, A., [1] Uber die Stetigkeit der konstruktiven Funktionen. Ycnexn
Mat. Hayk CCCP 61 (1954) 226-230
M-vtttt.t,, J. R., [1] Criteria of constructibility for real numbers. The Journal
of Symbolic Logic 18 (1953) 7-10.
Peteb, R., [1] Rekursive Funktionen, Budapest 1957.
[2] Zum Begriff der rekursiven reellen Zahl. Acta Scient. Math., Szeged,
12/A. Leopoldo Fejer et Frederico Riesz LXX annos natis dedicatus.
(1950) 239-245.

BIBLIOGRAPHY
135
Rice, H. G., [1] Recursive real numbers. Proc, Amer. Math, Soc. 5 (1954)
784-791.
Skoubm, Th., [1] Begriindung der elementaren Arithmetik durch die rekur-
rierende Denkweise ohne Anwendung scheinbarer Veranderlichen
mit unendlichem Ausdehnungsbereich. Videnskapsselskapets Shrifter
1. Math-Naturv. Kl. 6 (1924) 3-38.
[2] Eine Bemerkung iiber die Induktionsschemata in der rekursiven
Zahlentheorie. Monatshefte fur Math, und Phys. 48 (1939) 268-276.
[3] A remark on the induction schema. Det Kongelige Norske Videnskabers
Selskab 22 (1950) 167-170.
Speckeb, E., [1] Nicht konstruktiv beweisbare Satze der Analysis. The
Journal of Symbolic Logic 14 (1949) 145-158.
[2] Der Satz von Maximum in der Rekursiven Analysis. In Constructivity
in Mathematics 254-265.

INDEX
Ackermann, W 132
Bernays, P. ... 11, 110, 131
bound, recursive 46
Cauchy's Theorem .... 71
— — uniform 79
Church, A 112, 131
circular functions 99
continuity, recursive ... 39
—, relative 39
convergence, recursive ... 8
—, relative 9
—, tests 13
— — Cauchy 15
— -, Gauss, 17, 22
— —, Kummer, 14
— —, Raabe 15
Curry, H. B 131
D'Alembert's test 14
Darboux 90
Davis, M 131
differentiability, recursive . 57
—, relative 57
effective procedure . . . 25, 27
— constant 75
— variable 75
enumeration theorem ... 5
— of primitive recursive
functions 32
equality, relative 8
equivalent 8
— doubly uniform .... 69
exponential, relatively ... 96
function, rational .... 5
—, step 53
Heyting, A 131
Hilbert, D 11, 132
inequalities, mean value 61, 62
integral, relative .... 87, 88
irrationality, recursive . . . 123
Kleene, S. C 2, 4, 131
Kreisel, G 131
Summer's test 14
Lacombe, D 131
Lagrange remainder .... 74
limit 12
logarithm, relative .... 96
majorant 8
Markov, A 131
mean value inequality . . 61
— theorem 64
— —, uniform 78
Meschkowski, H 131
number, rational 5
— recursively irrational . . 123
— — transcendental ... 123
operator, minimal .... 3
ordinal, transflnite .... 106
— of type n 119
Peter, Rosza ... 32, 109, 131
procedure, effective .... 25
recursive, analysis .... 1
—, arithmetic 1
—, convergence 8
—, divergence 12
—, expansion 30
—, function 1, 2
—, irrationality 26
—, polynomial 28
—, real number 23
—, transcendence 123
reduce 10
reduced sequence 10
relative integral 87
Rice, H. G 131
Rolle's theorem 71
— — uniform 76
137

138
INDEX
root, recursive 51
ruled function 87
— equivalent 88
scale of notation 113
Skolem, Th 131
Specker, E 33, 131
standard form 9
substitution 94
Taylor's Theorem 73
- —, uniform 80
transcendence, recursive . . 123
- of e 124
- of n 127
uniform equivalent .... 69
value, mean 61, 64
variable, effective 75
—, relative 85