Subrecursive analysis
Arne Tobias Malkenes Ødegaard
Master’s Thesis, Spring 2018
University of Oslo. The scope of the thesis is 60 credits.
The front page depicts a section of the root system of the exceptional Lie group E8, projected into the plane. Lie groups were invented by the Norwegian mathematician Sophus Lie (1842–1899) to express symmetries in differential equations and today they play a central role in various parts of mathematics.
Computable analysis is a well-established area of mathematics, but is mainly studied in the context of full Turing computability. This thesis builds up computable analysis using subrecursive classes of functions. We start with coding the integers and the rational numbers as equivalence classes of natural numbers. We define the real numbers as equivalence classes of Cauchy sequences, and show that they form an ordered field.
We then introduce sequences of real numbers and show results about bounded and monotone sequences which are not convergent. We also show the undecidability of certain properties of these real numbers, in particular whether two real numbers are equal or whether a real number equals some rational number. In addition, we prove results about which real numbers can be represented by Dedekind cuts, binary expansions and Cauchy sequences.
I am severly indebted to my advisor, Lars Kristiansen, for both introducing me to the field of mathematical logic, and for his great advice throughout the process of writing this thesis.
I wish to thank Sigurd Kittelsen and Juvenal Murwanashyaka for reading my thesis and giving invaluable feedback.
For his support and knowledge in all things LATEX, I am grateful to Martin Helsø, without whom this thesis would look substantially worse.
For allowing me to present parts of this work, and providing helpful com- ments, I wish to thank the participants in the Logic seminar at the Department of Mathematics.
For having someone to talk to and laugh with, I am grateful to Søren Gammelgaard, Paul Aleksander Maugesten and everyone else who once occupied study hall B601.
I would also like to thank my parents who have supported me throughtout my life, in all my endavours.
Arne Tobias Malkenes Ødegaard Oslo, May 2018
Abstract i
Acknowledgements iii
Contents iv
1 Introduction 1
1.1 Outline . . . 1
2 Preliminaries 3 2.1 Computability theory . . . 3
2.2 Pairing functions . . . 6
2.3 Subrecursion . . . 7
2.4 Semi-expressive classes of functions . . . 12
3 Coding of integers and rationals 15 3.1 Coding of the integers . . . 15
3.2 Coding of the rational numbers . . . 26
4 Defining the real numbers 39 4.1 ConstructingRS,r . . . 39
4.2 Algebraic properties . . . 41
4.3 Ordering . . . 49
4.4 Other results . . . 54
5 Undecidable properties of real numbers 57 5.1 Equality . . . 60
5.2 Inequality . . . 62
5.3 Rationality . . . 66
6 Sequences of real numbers 69 6.1 Convergence . . . 69
6.2 Arithmetic, comparison and sequences . . . 71
6.3 Bounded and monotone sequences . . . 73
7 Representations of real numbers 83
Bibliography 93
Introduction
The theory of computable analysis has its roots in the article [Tur36] by Alan Turing from 1936, where the concept of a computable real number is first introduced. Computable analysis concerns which aspects of the field of analysis is changed when the involved numbers and functions are computable.
There are various results about the undecidability of certain properties of the real numbers. One such example is that there is no computable function which can decide if two real numbers are equal.
One result in computable analysis which stands in stark contrast to ordi- nary analysis is the existence of Specker sequences, bounded and monotone computable sequences of computable real numbers which do not converge to a computable real number. Another such result is that all computable func- tions from the computable real numbers to the computable real numbers are continuous.
In this thesis we build up computable analysis using subrecursive classes of functions, classes where one does not have full Turing computability. We show that the real numbers defined in such a class form an ordered field, and show that certain properties of these real numbers are undecidable. We introduce sequences of real numbers, and show the existence of two types of Specker-like sequences in subrecursive classes. We also discuss various representations of real numbers, and show results about which real numbers can be represented by Dedekind cuts, binary expansions and Cauchy sequences in the Grzegorczyk classE2.
1.1 Outline
Chapter 2 presents a brief introduction to the theory of computable functions on the natural numbers, and introduces subrecursive classes of functions.
The concept of a semi-expressive class of functions is defined.
Chapter 3 gives codings of the integers and the rational numbers as equivalence classes of natural numbers. It is shown that these codings satisfy the expected properties of the integers and the rational numbers.
Chapter 4 defines the real numbers for semi-expressive classes of functions, and it is shown that the real numbers form an ordered field.
Chapter 5 discusses the decidability of properties of real numbers. It is proved that there is no computable function which decides whether two real
numbers are equal and that there is no computable function which decides whether a real number is equal to some rational number.
Chapter 6 defines sequences of functions, and discusses their convergence. It is shown that a sequence is convergent if and only if it is a Cauchy sequence, and the existence of two types of Specker sequences in certain subrecursive classes is established.
Chapter 7 discusses the relationship between various ways of representing real numbers in the Grzegorczyk classE2. It is shown that there are more real numbers which can be represented by Cauchy sequences than Dedekind cuts in this class.
Preliminaries
2.1 Computability theory
We assume, in this thesis, that the reader is familiar with basic computability theory via Kleene recursion, in the style of [LK15] or [Odi89].
In this section we state basic definitions and results of computability theory over the natural numbers and define notation we will use in this thesis. The definitions and theorems in this section are taken from [LK15], and the reader interested in further details is advised to consult any introductory book about computability theory.
The computable functions are defined, in Kleene recursion, by giving equa- tions which define the functions. The class of computable functions is con- structed by defining a small collection of initial functions, and defining other functions from these using definition schemes.
We first define some notation. The zero functionOis a function which takes no arguments and yields 0. The notation (µi)[g(x1, . . . , xn, i)] denotes the least natural numberisuch thatg(x1, . . . , xn, i) = 0. If there exists no suchithen (µi)[g(x1, . . . , xn, i)] is undefined.
The class of computable functions is defined by:
1. The zero functionO is computable.
2. The successor functionS defined byS(x) =x+ 1 is computable.
3. The projection functions Iin defined by Iin(x1, . . . , xn) = xi are com- putable.
4. If there are computable functionsg1, . . . , gmof aritynand a computable functionhof aritym, then the functionf defined by
f(x1, . . . , xn) =h(g1(x1, . . . , xn), . . . , gm(x1, . . . , xn)) for allx1, . . . xn∈Nis computable.
5. Ifg is a computable function of aritynandhis a computable function of arityn+ 2, then the functionf of arityn+ 1 defined by
f(x1, . . . , xn,0) =g(x1, . . . , xn)
f(x1, . . . , xn, y+ 1) =h(x1, . . . , xn, y, f(x1, . . . , xn, y)) for allx1, . . . , xn, y is computable.
6. Ifg is a computable function of arityn+ 1, then the functionf of arity n+ 1 defined by
f(x1, . . . , xn) = (µi)[g(x1, . . . , xn, i)]
for allx1, . . . , xn is computable.
The successor, zero and projection functions are called the initial functions.
The clauses 4, 5 and 6 are called the definition schemes. Clause 4 is called the scheme of composition. Clause 5 is called the scheme of primitive recursion.
Clause 6 is called the scheme of minimalisation.
A more compact way to state this definition of the computable functions is to define them as the class of functions containing the zero, successor and projection functions closed under composition, primitive recursion and minimalisation.
The class of all total computable functions is denoted by CT.
There is a method for associating finite sequences of natural numbers with one unique natural number. For a sequence (a1, . . . , an) ∈Nn, we define its sequence numberha1, . . . , ani=Qn
i=1paii+1. There are computable functions (x)i and|x|such that for every sequence (a1, . . . , an) we have|ha1, . . . , ani|=n
and (ha1, . . . , ani)i=ai fori= 1, . . . , n.
There is a method for associating natural numbers with computable functions according to how the functions are constructed. We say that the natural number eis a computable index for the functionf if
1. e=h0iandf =S.
2. e=h1, n, iiandf =Iin. 3. e=h2iandf =O.
4. e=h3, n, b1, . . . , bm, aiand
f(x1, . . . , xn) =h(g1(x1, . . . , xn), . . . , gm(x1, . . . , xn)) andb1, . . . , bm, aare indices for, respectively,g1, . . . , gm, h.
5. e=h4, n, a, biand
f(x1, . . . , xn,0) =g(x1, . . . , xn)
f(x1, . . . , xn, y+ 1) =h(x1, . . . , xn, y, f(x1, . . . , xn, y)) anda, bare indices for, respectively, g, h.
6. e=h5, n, aiand
f(x1, . . . , xn) = (µi)[g(x1, . . . , xn, i)]
andais an index forg.
Theorem 2.1.1(Kleene’s Normal Form Theorem). Letn∈N. Then there exists a total computable predicateTn and a total computable function U such that
i) Ifeis not an index for an n-ary function, thenTn(e, x1, . . . , xn, t) does not hold for anyx1, . . . , xn, t∈N.
ii) Ife is an index for then-ary functionf, then
f(x1, . . . , xn) =U((µt)[Tn(e, x1, . . . , xn, t)]).
Definition 2.1.2. WithTn andU as in the above theorem, we define thee-th computable function of arityn, written {e}n, by
{e}n(x1, . . . , xn) =U((µt)[Tn(e, x1, . . . , xn, t)]).
Remark. {e}n is always a computable function, but ifeis not the index of an n-ary function, then{e}n is nowhere defined.
Theorem 2.1.3(The Enumeration Theorem).
i) For eache∈N, the function {e}n is computable.
ii) For each computable function of arityn, there existsesuch that f(x1, . . . , xn) ={e}n(x1, . . . , xn).
Theorem 2.1.4(The S-m-n theorem for computable functions). Letm, n∈N. There exists a total computable functionSnm of arity n+ 1 such that
{Snm(e, x1, . . . , xn)}m(y1, . . . , ym) ={e}n+m(x1, . . . , xn, y1, . . . , ym).
Computable and semi-computable sets
For a setA⊆Nwe define itscharacteristic function χA by χA(x) =
(0 ifx∈A 1 ifx6∈A.
A set is computable if its characteristic function is a computable function.
We define the domain (dom) and range (ran) of a computable functionf as
• dom(f) ={x|there existsy∈Nsuch thatf(x) =y} and
• ran(f) ={y|there existsx∈Nsuch thatf(x) =y}.
A setA⊆Nis called semi-computable if there exists a computable function f such thatA= dom(f). The following conditions are equivalent:
• Ais semi-computable,
• A=∅or Ais the range of a total computable function,
• Ais finite orA is the range of a total computable 1-1 function.
Proposition 2.1.5. Any computable set is semi-computable.
Definition 2.1.6.K={x|x∈dom({x}1)}
Remark. By the Kleene Normal Form Theorem,K={x| ∃tT1(x, x, t)}.
Proposition 2.1.7. K is semi-computable, but not computable. K is neither semi-computable nor computable.
2.2 Pairing functions
In addition to the prime factorisation method mentioned above, there are other methods of coding pairs and sequences which will be more advantageous in certain circumstances. We wish to work with an encoding functionh·,·i:N2→N and decoding functions (·)1:N→Nand (·)2: N→Nsatisfying
i) (hx, yi)2=y, ii) (hx, yi)1=xand iii) h(x)1,(x)2i=x.
It will follow from these properties thath·,·iis a bijection between N2 andN. This gives us a way of encoding sequences of a fixed lengthkashx1, . . . , xki= hx1,hx2,h. . . ,hxk−1, xkii.
One way to define such an encoding function is by hx, yi=
x+y
X
i=0
i
!
+y= (x+y)2+ (x+y)
2 +y.
To define the decoding functions (·)1 and (·)2 for this encoding function we introduce two auxiliary functions. We defineT byT(n) =Pn
i=0i= n22+n. Note that this lets us defineh·,·iviahx, yi=T(x+y) +y. We definev by
v(x) = (µi≤x) [T(i)≤x∧T(i+ 1)> x], which allows us to define the decoding functions by
• (x)2=x´T(v(x))
• (x)1=v(x)´(x)2,
where the function ´, calledmodified subtraction, is defined by x´y=
(x−y ifx≥y 0 otherwise
where −here denotes usual subtraction. Note that (x´1) + 1 =xifx6= 0 and (x+ 1)´1 =xfor anyx.
To see a proof that these functions satisfy the desired properties, see [Ros84, pp. 8-9].
2.3 Subrecursion
We now wish to turn our attention to subrecursive classes of functions onN, classes which are subclasses of the class of total computable functions. We first give a general definition of a subrecursive class, and then give some examples.
Definition 2.3.1. For any total function σ: N →N, define [e]σ by [e]σ(x) = U((µt)[T1(σ(e), x, t)]).
A subrecursive class is a recursively enumerable set of total computable functions. More formally, let S be a set of total computable functions, and suppose there exists a total computable functionσ:N→Nsuch that
• [e]σ∈ S for alle.
• For allϕ∈ S, there existse∈Nsuch that
ϕ(x1, . . . , xn) = [e]σ(hx1, . . . , xni).
ThenS is a subrecursive class.
A functionσsatisfying these requirements is called anenumerator ofS. Theorem 2.3.2([Koz80, Theorem 5.1]).SupposeS is a subrecursive class with enumeratorσand that there exist total computable functions comp,pair and const which satisfy
• [comp(e1, e2)]σ(n) = [e1]σ([e2]σ(n))
• [pair(e1, e2)]σ(n) =h[e1]σ(n),[e2]σ(n)i
• [const(x)]σ(n) =x
for all n. Then there exist total computable functionsSnm such that [Snm(e, x1, . . . , xn)]σ(hy1, . . . , ymi) = [e]σ(hx1, . . . , xn, y1, . . . , ymi) for all n, m∈N.
This theorem is proved in a somewhat different form in [Koz80]. Here we give a proof for the case whenn=m= 1.
Proof. Leti11 be such that [i11]σ(n) =I11(n) =n. DefineS11 by S11(e, x) =comp(e,pair(const(x), i11)).
Note thatS11 is total and computable it is defined by composition over total computable functions. For anyxandy we have that
[S11(e, x)]σ(y) = [comp(e,pair(const(x), i11))]σ(y)
= [e]σ([pair(const(x), i11)]σ(y))
= [e]σ(h[const(x)]σ(y),[i11]σ(y)i)
= [e]σ(hx, yi).
Remark. One can get a stronger result by requiring thatcomp,pairandconst all belong to S, but the result we have given here will be what we require in this thesis.
Definition 2.3.3.For a subrecursive class S, we let S∗ denote the set of 0-1 valued functions inS. That is,S∗={f ∈ S |ran(f)⊆ {0,1}}.
Definition 2.3.4.A relationR onNn is said to be anS-relation if there exists a characteristic function forRin S.
We now give examples of subrecursive classes, some of which we will use in this thesis. It is worth mentioning that there are many others that we do not mention here, one of which is the class of functions which are computable by a Turing machine in polynomial time.
The subrecursive classes we define are given by various definition schemes, and we start by defining the ones we need. Let~xdenotex1, . . . , xn.
Iff is defined by
f(0, ~x) =g(~x)
f(n+ 1, ~x) =h(n, f(n, ~x), ~x) andf satisfies
f(n, ~x)≤j(n, ~x)
we say that f is defined fromg, handj bybounded recursion.
Iff is defined by
f(n, ~x) = (µt≤n)[g(t, ~x)]
we say that f is defined fromg bybounded minimalisation. Note that this is defined to be the smallestt≤nsuch thatg(t, ~x) = 0 andn+ 1 if there is no sucht.
The primitive recursive functions
The class of primitive recursive functions, denotedPR, is the class of functions containing the zero, successor and projection functions closed under composition and primitive recursion.
The Kalmár elementary functions
The class of Kalmár elementary functions, denoted E, is the class of functions containing the zero, successor, projection, maximum and 2x functions closed under composition and bounded recursion.
The Grzegorczyk hierarchy
The following definitions are taken from [Ros84]. The reader interested in more details is advised to consult that book.
Definition 2.3.5. The functionsEn are defined by E0(x, y) =x+y
E1(x) =x2+ 2 En+2(0) = 2
En+2(x+ 1) =En+1(En+2(x))
Definition 2.3.6. E0 is the class of functions containing the zero, successor and projection functions closed under composition and bounded recursion. En+1 is the class of functions containing the zero, successor, projection andEn functions closed under composition and bounded recursion. We say thatEn is then’th class in the Grzegorczyk hierarchy.
It is worth pointing out thatEnis also closed under bounded minimalisation for eachn, and that theEn-relations are closed under bounded quantification, that is ifP(x, y) is anEn-relation, then (∃i≤k)[P(i, y)] and (∀i≤k)[P(i, y)]
areEn-relations.
Proposition 2.3.7([Ros84, pp. 34–35]).The classes in the Grzegorczyk hierar- chy satisfy the following properties:
i) For anyn,En ⊂ En+1 ii) S
n∈NEn=PR.
Proposition 2.3.8([Ros84, p. 33]).The Grzegorczyk class E3 equals the class of Kalmár elementary functions.
Proposition 2.3.9([Rit63, Theorems 4 & 5]). The Grzegorczyk classE2 equals the class of functions which can be computed by a Turing machine using an amount of cells linear in the length of the input, in other words, the class of functions computable in space O(n), wherendenotes the length of the input.
Proposition 2.3.10 ([Grz53, Theorem 5.1]). The function U and the predi- cates Tn from Kleene’s Normal Form Theorem belong toE0, and hence to all Grzegorczyk classes.
The classE2
We will in certain specific cases use the classE2to prove statements, and for that reason we wish to give some results about this class. For the purposes of proving this, we use certain results about E2which is proved in Section 2.4.
Proposition 2.3.11.There exists a semi-computable set Asuch that Ais not computable and there exists an injective function r∈ E2 such thatA= ran(r).
Proof. LetB be a semi-computable set which is not computable. Then there exists an index esuch thatB= dom({e}1) ={x| ∃tT1(e, x, t)}. Definer by
r(n) =
(2(n)1 ifT1(e,(n)1,(n)2) and¬(∃t <(n)2)[T1(e,(n)1, t)]
2n+ 1 otherwise.
SinceE2 containsT1, (·)1 and (·)2and is closed under bounded quantification, we have thatr∈ E2. SetA= ran(r). Sinceris a computable function,Ais a semi-computable set.
It remains to show thatris injective and thatAis not computable.
We first show that n ∈ B ⇐⇒ 2n ∈ A. Suppose n ∈ B. Let tn = (µt)[T1(e, n, t)]. Then r(hn, tni) = 2n, so 2n ∈ A. Suppose 2n ∈ A. Then there existsksuch thatT1(e,(k)1,(k)2) holds and (k)1=n, which shows that there existst such thatT1(e, n, t) holds, from which we conclude thatn∈B.
Therefore, if Ais computable, we can define the characteristic function ofB, χB, byχB(n) =χA(2n), which shows thatB is a computable set. SinceB is not computable, this implies thatA is not computable.
To show that r is injective, suppose r(n) = r(m). If r(n) is odd, then 2m+ 1 = r(m) = r(n) = 2n+ 1, and thus n = m. If r(n) is even, then 2(n)1= 2(m)1, so (n)1 = (m)1. Suppose (n)2<(m)2. Then∃t <(m)2 such thatT1(e,(m)1, t) holds, namely (n)2, sor(m) = 2m+ 16= 2(m)1, which is a contradiction. The case when (m)2<(n)2is identical. Hence it must be the case that (n)2= (m)2, and thusn=m, which shows thatris injective.
We now wish to discuss exponentiation inE2. We first have the following result:
Proposition 2.3.12([Ros84, p. 35]). Iff ∈ E2, there exists a polynomialpin nvariables such that
f(x1, . . . , xn)≤p(x1, . . . , xn).
This shows that the functionf(x) = 2xdoes not belong toE2. However, we have certain results which shows how one can still work with 2xin E2. Proposition 2.3.13.
i) There existsf ∈ E2 such thatf(k, n) =
(2k if2k≤n 0 otherwise.
ii) {(k, n)|n= 2k} is an E2-relation.
iii) For n≥1, we define lg(n) as the unique k such that 2k ≤n < 2k+1. There exists a function h∈ E2 such thath(n) =lg(n)forn≥1.
iv) There exists a function j∈ E2 such thatj(n) = 2lg(n) forn≥1.
Proof. Definef by f(0, n) =
(1 ifn >0
0 ifn= 0 andf(k+ 1, n) =
(2f(k, n) if 2f(k, n)≤n
0 otherwise
Note that, by construction, f(k, n) ≤n for any k, n. Since f is defined by bounded recursion over functions and relations inE2,f belongs toE2.
To see that this definition off corresponds with the given one, observe that f(k, n) is multiplication by 2 iteratedktimes, hencef(k, n) = 2k, unless this results in a value larger than n, in which casef(k, n) = 0.
Defineg byg(k, n) =
(0 iff(k, n) =nandn >0 1 otherwise.
Since f belongs to E2, so does g. We now have that if 2k = n, then f(k, n) = 2k=nandn >0, so g(k, n) = 0. If 2k > n, thenf(k, n) = 0. Since it not possible forn= 0 and n >0, we must haveg(k, n) = 1. If 2k < n, then f(k, n) = 2k 6=n, sog(k, n) = 1. This shows thatg(k, n) = 0 ⇐⇒ n= 2k, which shows thatgis the characteristic function for then= 2k-relation.
Definehbyh(n) = (µi≤n)[f(i+ 1, n)].
Letn≥1. Sincef(0, n) = 1 and f(n, n) = 0, we have that f(h(n), n)6= 0 and f(h(n) + 1, n) = 0. Sincef(h(n), n)6= 0, we have 2h(n)≤n, and because f(h(n) + 1, n) = 0, we have 2h(n)+1> n. This shows thath(n) =lg(n) for n≥1.
Define j by j(n) = f(h(n), n). Since 2h(n) = 2lg(n) ≤n by definition of lg(n), we have j(n) = 2h(n)= 2lg(n)forn≥1.
Honest functions and elementary closure
The definitions, theorems and propositions below are taken from [Kri96]. The reader interested in more details is advised to consult that article.
Definition 2.3.14(Honest functions). A functionf:N→Nishonestif:
i) f is total and computable.
ii) f is monotone, that isf(x)≤f(x+ 1) for allx.
iii) f(x)≥2x for allx.
iv) The relation{(x, y)|f(x) =y}is anE-relation.
We use boldface letters to denote honest functions.
Definition 2.3.15.A functionϕis elementary in a functionψ, writtenϕ≤E ψ, if ϕ can be generated from the initial functions ψ, 2x, max, 0, S, Iin by composition and bounded recursion.
For a functionψ, we define E(ψ) to be the class of functions with initial functionsψ, 2x, max, 0,S,Iinclosed under composition and bounded recursion.
Note thatE(ψ) ={ϕ|ϕ≤Eψ}and thatE ⊆ E(ψ) for allψ.
It is worth pointing out thatE(ψ) is also closed under bounded minimalisa- tion for each total computable functionψ.
We will focus on the classesE(f) for honest functionsf.
It is worth pointing out thatE(f) is also closed under bounded minimalisation for each honest functionf, and that theE(f)-relations are closed under bounded quantification, that is if P(x, y) is anE(f)-relation, then (∃i≤k)[P(i, y)] and (∀i≤k)[P(i, y)] areE(f)-relations.
For a functionf, definefn byf0(x) =xandfn+1(x) =f(fn(x)). For an honest functionf definef0 byf0(x) =fx+1(x). It is possible to show thatf0 is also an honest function, and thatE(f)⊂ E(f0) for all honest functionsf. Theorem 2.3.16(Growth theorem).If f andgare honest functions, then
f ≤E g ⇐⇒ there existsk∈Nsuch that f(x)≤gk(x) for all x.
Theorem 2.3.17(Normal form theorem). Supposeϕ∈ E(f). Then there exist e, k∈Nsuch that
ϕ(x1, . . . , xn) =U((µt≤fk(max(x1, . . . , xn)))[Tn(e, x1, . . . , xn, t)]) for all x1, . . . , xn.
Proposition 2.3.18. For any total computable functionϕthere exists an honest function f such that ϕ∈ E(f).
Lemma 2.3.19. Supposeϕ andψ are total computable functions. Then there exists an honest functionf such that ϕ∈ E(f)andψ∈ E(f).
Proof. By Proposition 2.3.18 there exist honest functionsf1andf2 such that ϕ∈ E(f1) andψ∈ E(f2).
Define f byf(x) = max(f1(x),f2(x)). It is straightforward to show that f is an honest function, and then by the Growth theorem we havef1≤Ef and f2≤Ef. ThereforeE(f1)⊆ E(f) andE(f2)⊆ E(f). Thus we have that ϕ∈ E(f) andψ∈ E(f), which is what we wanted to prove.
Proposition 2.3.20. For any honest functions f and g, E(f) ⊆ E(g) ⇐⇒
E(f)∗⊆ E(g)∗.
Lemma 2.3.21. Supposef is an honest function. Then there exists a computable setA such that its characteristic functionχA does not belong toE(f).
Proof. Since we haveE(f)⊂ E(f0), by Proposition 2.3.20 we have thatE(f)∗⊂ E(f0)∗. LetAbe some set such thatχA∈ E(f0)∗\ E(f)∗. Since all functions in E(f0) are computable,A is a computable set, but we have thatχA6∈ E(f).
2.4 Semi-expressive classes of functions
A class S of total functions on N is semi-expressive if it contains the zero, successor, projection, addition and multiplication functions as well as encoding and decoding functions, and is closed under composition.
Proposition 2.4.1. LetS be a semi-expressive class. Then i) S contains all constant functions of any arity.
ii) If R(~x)andS(~x) areS-relations, then
a) ¬R(~x)is an S-relation.
b) R(~x)∨S(~x)is an S-relation.
c) R(~x)∧S(~x)is an S-relation.
iii) The comparison relations ≤, = and < on the natural numbers are S- relations.
iv) S is closed under definition by cases.
The proof of the first three statements are taken from [LK15, pp. 205–207], but modified for the constraints of the semi-expressive class S.
Proof.
i) Let cki be defined by cki(x1, . . . , xk) =i. We need to show thatcki ∈ S for any i, k. Since c00 = O, we have c00 ∈ S. For k > 0 we have that ck0 can be defined by composition by letting ck0(x1, . . . , xn) = O. Here the scheme of composition is applied with n = k and m = 0. This shows that ck0 ∈ S for any k. We now proceed to show that cki ∈ S for any i and k by induction. Let k ∈ N, and suppose cki ∈ S. Since cki+1(x1, . . . , xk) =S(cki(x1, . . . , xk)), we have thatcki+1∈ S. By induction we conclude thatcki ∈ S for anyi, k.
ii) SupposeR(~x) and S(~x) areS-relations with characteristic functionsχR
andχS. Then 1´χR(~x) is a characteristic function for¬R(~x), which shows that ¬R(~x) is an S-relation. χR(~x)·χR(~x) is a characteristic function forR(~x)∨S(~x), which shows thatR(~x)∨S(~x) is anS-relation.
SinceR(~x)∧S(~x)≡ ¬(¬R(~x)∨ ¬S(~x)), we have thatR(~x)∧S(~x) is an S-relation.
iii) 1´(1´(y´x)) is the characteristic function for the relationx≤y, which shows that≤ is an S-relation. Since x =y ⇐⇒ x≤y∧y ≤ xand x < y ⇐⇒ ¬(y≤x) and theS-relations are closed under propositional connectives, this shows that = and<areS-relations.
iv) Supposef is defined by f(x1, . . . , xn) =
(g1(x1, . . . , xn) ifh(x1, . . . , xn) = 0 g2(x2, . . . , xn) ifh(x1, . . . , xn)6= 0
where g1, g2, h ∈ S. Let ~x = x1, . . . , xn. We can define f by f(~x) = g1(~x)·(1´h(~x)) +g2(~x)·(1´(1´h(~x))) which is inS. Ifh(~x) = 0, then 1´h(~x) = 1 and 1´(1´h(~x)) = 0, sof(~x) =g1(~x). Ifh(~x)6= 0, then 1´h(~x) = 0 and 1´(1´h(~x)) = 1, and thus f(~x) =g2(~x). This shows thatf satisfies the definition by cases.
Proposition 2.4.2.
i) En is semi-expressive for each n≥2.
ii) E is semi-expressive.
iii) E(f)is semi-expressive for each honest function f. iv) PR is semi-expressive.
v) The class of total computable functions,CT, is semi-expressive.
Proof.
i) We start by showing thatE2is semi-expressive. By definition ofE2we have that it contains the zero, successor and projection functions. From [Ros84, pp. 116-117], we have that it contains the addition, multiplication and pairing functions as well. Furthermore,E2is closed under composition by definition, and thus E2 is semi-expressive. Since E2 ⊆ En for any n ≥ 2, and each En is closed under composition, we have that En is semi-expressive for eachn≥2.
ii) SinceE =E3 andE3 is semi-expressive,E is semi-expressive.
iii) SinceE ⊆ E(f) for any honest f, andE(f) is closed under composition, we have thatE(f) is semi-expressive.
iv) SinceE2⊆PR andPRis closed under composition, we have that PRis semi-expressive.
v) SinceE2⊆CTand the composition of two total computable functions is a total computable function, we have that CTis semi-expressive.
Coding of integers and rationals
We would like to discuss functions related to the integers and the rational numbers. Because the classes of functions introduced in Chapter 1 only contain functions on the natural numbers, we let natural numbers code integers and rational numbers, and we do so by constructing appropriate equivalence relations and showing that the resulting equivalence classes have the properties one would expect.
3.1 Coding of the integers
The standard way to construct the integers from the natural numbers is as tuples of natural numbers under an equivalence relation defined by (a, b)≡(c, d) iffa+d=c+b. The intuitive idea is that the tuple (a, b) represents the integer a−b, and our definitions are motivated by this. Using our system of coding, we will let the natural numberncode the integer (n)1−(n)2.
ConstructingZ
We will formalise this by definingZas a set of equivalence classes ofNunder an appropriate equivalence relation =Z. This relation is defined byn=Zm ⇐⇒
(n)1+ (m)2= (m)1+ (n)2. We first prove that =Z is an equivalence relation.
Proposition 3.1.1. The relation=Z is an equivalence relation onN.
Proof. We show that =Z satisfies the required conditions for an equivalence relation.
Reflexivity: For alln∈N, since (n)1+ (n)2 = (n)1+ (n)2, we haven=Z n, which means that =Zis reflexive.
Symmetry: Ifn=Zm, then (n)1+(m)2= (m)1+(n)2. Therefore (m)1+(n)2= (n)1+ (m)2, and thusm=Zn, which shows that =Zis symmetric.
Transitivity: Assume that both n =Z m and m =Z k. This means that (n)1+ (m)2 = (m)1+ (n)2 and (m)1+ (k)2 = (k)1+ (m)2. By adding together both sides of the preceding equalities, we get that (n)1+ (m)2+ (m)1+ (k)2= (m)1+ (n)2+ (k)1+ (m)2, and by cancelling (m)1+ (m)2 we get that (n)1+ (k)2 = (k)1+ (n)2, which shows thatn =Z k, from which we conclude that =Z is transitive.
Definition 3.1.2.Let [n]Z denote the equivalence class ofnunder =Z, that is [n]Z={m∈N|n=Zm}. Then we define the integers, Z, as
Z={[n]Z|n∈N}.
Notation for integers
In order to make our arguments more readable we introduce a notation for integers. For natural numbersaand b, we definea−b= [ha, bi]Z.
Proposition 3.1.3. For anyr∈Zthere exista, b∈Nsuch that r=a−b.
Proof. Let r ∈ Z. Let n be such that r = [n]Z. Then (n)1 −(n)2 = [h(n)1,(n)2i]Z= [n]Z=r.
Remark. This proposition shows that in order to prove a statement for all integers it will suffice to prove the statement for all integers of the forma−b for natural numbersaandb.
Proposition 3.1.4.For anya−b, c−d∈Zwe havea−b=c−d ⇐⇒ a+d= c+b.
Proof. For anya−b, c−d∈Zwe have a−b=c−d ⇐⇒ [ha, bi]Z= [hc, di]Z
⇐⇒ ha, bi=Zhc, di
⇐⇒ (ha, bi)1+ (hc, di)2= (hc, di)1+ (ha, bi)2
⇐⇒ a+d=c+b.
Algebraic operations onZ
We will define the basic arithmetic functions on the integers. We first define functions +Zand·Z onN, and show that these respect the equivalence relation
=Z. They are defined by
n+Zm=h(n)1+ (m)1,(n)2+ (m)2i and
n·Zm=h((n)1·(m)1) + ((n)2·(m)2),((n)1·(m)2) + ((m)1·(n)2)i.
We now show that these functions respect the equivalence relation =Z. Proposition 3.1.5. Supposen=Zn0 andm=Zm0. Then n+Zm=n0+Zm0 andn·Zm=n0·Zm0.
Proof. Leta, b, a0, b0, c, d, c0, d0 be such thatn=ha, bi, n0=ha0, b0i, m=hc, di andm0 =hc0, d0i.
We start by showing the statement about +Z. Sincen=Zn0 andm=Zm0, a+b0 =a0+bandc+d0=c0+d. Adding together both sides of these equations gives us
a+b0+c+d0=a0+b+c0+d. (∗) In order to check that (n+Zm) =Z (n0+Zm0), we need to check whether (n+Zm)1+ (n0+Zm0)2= (n0+Zm0)1+ (n+Zm)2. Sincen+Zm=ha+c, b+di andn0+Zm0=ha0+c0, b0+d0i, we need to check thata+c+b0+d0=a0+c0+b+d, which is the case as this equality is a straightforward rearrangement of (∗).
We now wish to show the statement about·Z. Sincen=Zn0 andm=Zm0, a+b0=a0+b andc+d0 =c0+d. From this we have
c(a+b0)+d(a0+b)+a0(c+d0)+b0(c0+d) =c(a0+b)+d(a+b0)+a0(c0+d)+b0(c+d0) By multiplying this out and cancelling all terms which occur on both sides of the equality, one gets
ca+db+a0d0+b0c0=cb+da+a0c0+b0d0. (†) In order to check thatn·Zm=Zn0·Zm0, we must show that (n·Zm)1+ (n0·Zm0)2= (n0·Zm0)1+ (n·Zm)2. By the definition of·Z, we must show that ac+bd+a0d0+c0b0=a0c0+b0d0+ad+bc, but this equality is true as it is a straightforward rearrangement of (†).
Definition 3.1.6.The above proposition shows that the functions +Z and·Z induce well-defined functions + and· onZ, which can be defined as
[n]Z+ [m]Z= [n+Zm]Z and
[n]Z·[m]Z= [n·Zm]Z. Proposition 3.1.7. For anya−b, c−d∈Z we have
i) (a−b) + (c−d) = (a+c)−(b+d) ii) (a−b)·(c−d) = (ac+bd)−(ad+cb) Proof. For anya−b, c−d∈Zwe have
(a−b) + (c−d) = [ha, bi]Z+ [hc, di]Z
= [ha, bi+Zhc, di]Z
= [ha+c, b+di]Z
= (a+c)−(b+d)
and
(a−b)·(c−d) = [ha, bi]Z·[hc, di]Z
= [ha, bi ·Zhc, di]Z
= [hac+bd, ad+cbi]Z
= (ac+bd)−(ad+cb).
Now that we have defined the addition and multiplication functions onZ, we wish to show that they satisfy the expected properties of these functions.
Proposition 3.1.8. Zforms a commutative ring under +and·.
Proof. We check that all the required properties of a commutative ring are satisfed.
Commutativity of+: For anya−b, c−d∈Zwe have
(a−b) + (c−d) = (a+c)−(b+d) = (c+a)−(d+b) = (c−d) + (a−b), which shows that + is commutative.
Commutativity of·: For any a−b, c−d∈Zwe have
(a−b)·(c−d) = (ac+bd)−(ad+cb) = (ca+bd)−(cb+ad) = (c−d)·(a−b), which shows that·is commutative.
Associativity of+: For anya−b, c−d, e−f ∈Zwe have
((a−b) + (c−d)) + (e−f) = ((a+c)−(b+d)) + (e−f)
= ((a+c) +e)−((b+d) +f)
= (a+ (c+e))−(b+ (d+f))
= (a−b) + ((c+e)−(d+f))
= (a−b) + ((c−d) + (e−f)), which shows that + is associative.
Associativity of·: For anya−b, c−d, e−f ∈Zwe have ((a−b)·(c−d))·(e−f)
= ((ac+bd)−(ad+cb))·(e−f)
= ((ac+bd)e+ (ad+cb)f)−((ac+bd)f+e(ad+cb))
= (ace+bde+adf +cbf)−(acf+bdf+ead+ecb)
= (a(ce+df) +b(cf+ed))−(a(cf+ed) + (ce+df)b)
= (a−b)·((ce+df)−(cf+ed))
= (a−b)·((c−d)·(e−f)), which shows that·is associative.
Distributivity: For anya−b, c−d, e−f ∈Z, we have (a−b)·((c−d) + (e−f))
= (a−b)·((c+e)−(d+f))
= (a(c+e) +b(d+f))−(a(d+f)−(c+e)b)
= (ac+ae+bd+bf)−(ad+af +cb+eb)
= ((ac+bd) + (ae+bf))−((ad+cb) + (af+eb))
= ((ac+bd)−(ad+cb)) + ((ae+bf)−(af+eb))
= ((a−b)·(c−d)) + ((a−b)·(e−f)), which establishes distributivity.
Additive identity: Define 0Z=h0,0i, and let 0 = [0Z]Z. Then 0 = 0−0.
For anya−b∈Zwe have
(a−b) + 0 = (a−b) + (0−0) = (a+ 0)−(b+ 0) =a−b, which shows that 0 is an additive identity forZ.
Multiplicative identity: Define 1Z=h1,0i, and let 1 = [1Z]Z. Then 1 = 1−0.
For anya−b∈Zwe have
(a−b)·1 = (a−b)·(1−0) = (a·1 +b·0)−(a·0 + 1·b) =a−b, which shows that 1 is a multiplicative identity forZ.
Additive inverses: Note first that, for anya−b∈Z,a−b= 0 ⇐⇒ a−b= 0−0 ⇐⇒ a+ 0 =b+ 0 ⇐⇒ a=b.
For anya−b∈Z, we have that
(a−b) + (b−a) = (a+b)−(b+a) = (a+b)−(a+b) = 0 which shows thatb−ais an additive inverse fora−b.
Definition 3.1.9(Inverse).Define−:Z→Zby−(a−b) =b−afor anya−b∈Z. Note that r+ (−r) = 0 for allr∈Z. Note also that−r= (0−1)·r= (−1)·r.
Definition 3.1.10(Subtraction).Define−:Z×Z→Zbyr−s=r+ (−s) for any r, s∈Z.
Ordering ofZ
We wish to define the usual ordering relation onZ, and we start with defining the relation≤Z onNby
n≤Zm ⇐⇒ (n)1+ (m)2≤(m)1+ (n)2. We first check that this gives rise to a well-defined relation onZ:
Proposition 3.1.11. Suppose n =Z n0 and m =Z m0. Then n ≤Z m ⇐⇒
n0≤Zm0.
Proof. Leta, b, a0, b0, c, d, c0, d0 be such thatn=ha, bi,n0 =ha0, b0i,m=hc, di and m0 =hc0, d0i. By the assumption that n =Z n0 and m =Z m0, we have a+b0=a0+bandc+d0=c0+d. This gives us
n≤Zm ⇐⇒ a+d≤c+b
⇐⇒ a+d+b0+c0+d0+a0≤b+c+b0+c0+d0+a0
⇐⇒ a0+d0+b0+c0+d+a≤b0+c0+b0+c0+d+a
⇐⇒ a0+d0≤b0+c0 ⇐⇒ n0≤Zm0.
Definition 3.1.12.This proposition shows that we can define the ordering relation≤onZby
[n]Z≤[m]Z ⇐⇒ n≤Zm.
Proposition 3.1.13.For any a−b, c−d∈Z, we have that a−b≤c−d ⇐⇒
a+d≤c+b.
Proof. For anya−b, c−d∈Z, we have
a−b≤c−d ⇐⇒ [ha, bi]Z≤[hc, di]Z
⇐⇒ ha, bi ≤Zhc, di
⇐⇒ a+d≤c+b.
Now that we have defined ≤ on Z, we wish to show that it satisfies the expected properties of≤.
Proposition 3.1.14.≤is a total order onZ.
Proof. We start by showing that≤is a partial order onZ, and do so by checking the three conditions for a partial order.
Reflexivity: For anya−b∈Z, sincea+b≤a+bwe have thata−b≤a−b, which shows that≤is reflexive.
Antisymmetry: Suppose a−b ≤ c−d and c−d ≤ a−b. Then we have thata+d≤c+bandc+b≤a+d. Thereforea+d=c+b, and thus a−b=c−d, which shows that ≤is antisymmetric.
Transitivity: Supposea−b≤c−dandc−d≤e−f. Thena+d≤c+band c+e≤d+f. Adding together both sides, we get thata+d+c+e≤ d+f +c+b, and cancellingd+c we get thata+e≤b+f, and hence a−b≤e−f, which establishes transitivity.
Since, for anya−b, c−d∈Z, we havea+d≤c+borc+b≤a+d, we must havea−b≤c−dorc−d≤a−b, which shows that≤is a total order.
Proposition 3.1.15.Z is an ordered ring.
Proof. From Proposition 3.1.8 we have that Zis a commutative ring and from Proposition 3.1.14 we have that≤is a total order onZ. Therefore it suffices to show that
i) For any r, s, t∈Z, ifr≤s, thenr+t≤s+t.
ii) For anyr, s∈Z, if 0≤rand 0≤s, then 0≤r·s.
For the first result, leta−b, c−d, e−f ∈Z. Then a−b≤c−d =⇒ a+d≤c+b
=⇒ (a+e) + (d+f)≤(c+e) + (b+f)
=⇒ (a+e)−(b+f)≤(c+e)−(d+f)
=⇒ (a−b) + (e−f)≤(c−d) + (e−f)
For the second result, leta−b, c−d∈Zand suppose that 0≤a−band 0≤c−d. Since 0≤a−bwe must have b≤a, and thus there existse such that a=b+e. Since 0≤c−d, we must haved≤c. Then
d≤c =⇒ ed≤ec
=⇒ bd+ed+bc≤bc+ec+bd
=⇒ (b+d)d+bc≤(b+e)c+bd
=⇒ ad+bc≤ac+bd
=⇒ 0≤(ac+bd)−(ad+bc)
=⇒ 0≤(a−b)·(c−d) Hence we have that 0≤(a−b)·(c−d), as desired.
Definition 3.1.16(Other comparison relations).We define the relations<,>,
≥and6= onZby
• x < y ⇐⇒ ¬(y≤x),
• x > y ⇐⇒ y < x,
• x≥y ⇐⇒ y≤xand
• x6=y ⇐⇒ ¬(x=y).
Definition 3.1.17.We define the absolute value function,|·|, by
|r|=
(r ifr≥0
−r ifr <0
For anyr, s∈Zwe have:
i) |r| ≥0.
ii) |r|= 0 ⇐⇒ r= 0 iii) |rs|=|r||s|
iv) |r+s| ≤ |r|+|s|
These properties are proved straightforwardly from the fact that Z is an ordered ring, so we omit the proofs.
Other results
Proposition 3.1.18.There exists an injective order-preserving homomorphism fromNtoZ, that is an injective functioniN:N→Zsuch that for anyn, m∈N we haveiN(n+m) =iN(n) +iN(m)and iN(n·m) =iN(n)·iN(m), and we have thatn≤m ⇐⇒ iN(n)≤iN(m).
Proof. We defineiNbyiN(n) =n−0. For anyn, mwe have
iN(n) +iN(m) = (n−0) + (m−0) = (n+m)−0 =iN(n+m) and
iN(n)·iN(m) = (n−0)·(m−0) = (n·m+ 0·0)−(n·0 + 0·m)
= (n·m)−0 =iN(n·m), which establishes that iNis a homomorphism. Since
iN(n) =iN(m) =⇒ n−0 =m−0 =⇒ n+ 0 =m+ 0 =⇒ n=m, we have thatiN is injective. Finally, we have that
n≤m ⇐⇒ n+ 0≤m+ 0 ⇐⇒ n−0≤m−0 ⇐⇒ iN(n)≤iN(m), which establishes the order-preserving property.
Because of this result, we will regardNas a subset ofZ, and identifynwith iN(n).
Proposition 3.1.19(Integral domain). If r, s∈Zare such that 0 =r·s, then we have 0 =ror 0 =s.
Proof. Let a−b, c−d∈Z be such that 0 = (a−b)·(c−d). Suppose that a−b 6= 0. We wish to show thatc−d= 0. Since a−b 6= 0, we must have a−b >0 or a−b <0. We show the case when a−b >0, as the case when
a−b <0 is identical. Since a−b >0, we have a > b, and thus there exists e >0 such thata=b+e. This gives us that
0 = (a−b)·(c−d) =⇒ 0 = (ac+bd)−(ad+bc)
=⇒ ad+bc=ac+bd
=⇒ (b+e)d+bc= (b+e)c+bd
=⇒ bd+ed+bc=bc+ec+bd
=⇒ ed=ec
=⇒ d=c
=⇒ 0 =c−d, which shows that 0 =c−d.
Corollary 3.1.20(Cancelling). If r, s, t∈Zare such thatr·t=s·t and t6= 0, thenr=s.
Proof. From the previous proposition, sincet6= 0, we have r·t=s·t =⇒ 0 =s·t−r·t
=⇒ 0 = (s−r)·t
=⇒ 0 =s−r
=⇒ r=s.
Proposition 3.1.21.If r, s∈Zsatisfy that 0≤r·sand0< s, then0≤s.
Proof. Supposea−b, c−d∈Zare such that 0≤(a−b)·(c−d) and 0<(c−d).
Since 0< c−dwe haved < c, and thus there existse >0 such thatc=d+e.
Since 0≤(a−b)·(c−d) = (ac+bd)−(ad+bc), we must havead+bc≤ac+bd.
We then have that
ad+bc≤ac+bd =⇒ ad+b(d+e)≤a(d+e) +bd
=⇒ ad+bd+be≤ad+ae+bd
=⇒ be≤ae
=⇒ b≤a
=⇒ 0≤a−b which shows that 0≤a−b, as desired.
Corollary 3.1.22(Cancelling and≤). Ifr, s, t∈Z satisfy thatr·t≤s·tand t >0, thenr≤s.
