Lecture #7 —Continued
0.0.0.1 Proposition. If R(⃗x,y,⃗z) ∈ PR∗ and λw⃗.f(w⃗) ∈ PR, then R(⃗x,f(w⃗),⃗z) is in PR∗.
Proof. By lemma, let g ∈ PR such that
Then
R(⃗x,y,⃗z) ≡ g(⃗x,y,⃗z) = 0, for all ⃗x,y,⃗z
R(⃗x,f(w⃗),⃗z) ≡ g(⃗x,f(w⃗),⃗z) = 0, for all ⃗x,w⃗,⃗z
By the lemma, and since λ⃗xw⃗⃗z.g(⃗x.f(w⃗),⃗z) ∈ PR by Grzegorczyk Ops, we have that R(⃗x,f(w⃗),⃗z) ∈ PR∗.
1
2
0.0.0.2 Proposition. If R(⃗x, y, ⃗z) ∈ R∗ and λw⃗ .f (w⃗ ) ∈ R, then R(⃗x, f (w⃗ ), ⃗z)
is in R∗.
Proof. Similar to that of 0.0.0.1.
3 0.0.0.3 Corollary. If f ∈ PR (respectively, in R), then its graph, z = f(⃗x) is
in PR∗ (respectively, in R∗).
Proof. Using the relation z = y and 0.0.0.1.
4
0.0.0.4 Exercise. Using unbounded search, prove that if z = f(⃗x) is in R∗ and f is total, then f ∈ R.
0.0.0.5 Definition. (Bounded Quantifiers) The abbreviations (∀y)
for all x, y.
Pause. Why is the above expression correct?
Because setting z = ⌊x/y⌋ we have
1For any real number x, the symbol “⌊x⌋” is called the floor of x. It succeeds in the literature (with the same definition) the so-called “greatest integer function, [x]”, i.e., the integer part of the real number x. Thus, by definition, ⌊x⌋ ≤ x < ⌊x⌋ + 1.
z≤x
16
(2) λxy.rem(x, y) (the remainder of the division x/y).
rem(x, y) = x −. y⌊x/y⌋.
(3) λxy.x|y (x divides y).
x|y ≡ rem(y, x) = 0.
Note that if y > 0, we cannot have 0|y —a good thing!— since rem(y, 0) = y > 0.
Our redefinition of ⌊x/y⌋ yields, however, 0|0, but we can live with this in practice.
17
18
(4) Pr(x) (x is a prime).
P r(x) ≡ x > 1 ∧ (∀y)≤x(y|x → y = 1 ∨ y = x).
19
(5) π(x) (the number of primes ≤ x).2
The following primitive recursion certifies the claim: π(0) = 0,
and
π(x + 1) = if P r(x + 1) then π(x) + 1 else π(x).
2The π-function plays a central role in number theory, figuring in the so-called prime number theorem. See, for example, [LeV56].
20
(6) λn.pn (the nth prime).
First note that the graph y = pn is primitive recur- sive:
y=pn ≡Pr(y)∧π(y)=n+1.
Next note that, for all n,
pn ≤ 22n (see Exercise 0.0.0.18 below), thus pn = (μy)≤22n (y = pn),
which settles the claim.
21
(7) λnx. exp(n, x) ( the exponent of pn in the prime fac- torization of x).
exp(n, x) = (μy)≤x¬(py+1|x). n
Isxagoodbound? Yes! x=…pyn…≥pyn ≥ 2y > y.
22
(8) Seq(x) (x’s prime number factorization contains at least one prime, but no gaps).
Seq(x) ≡ x > 1 ∧ (∀y)≤x(∀z)≤x(Pr(y) ∧ Pr(z) ∧ y < z ∧ z|x → y|x).
0.0.0.17 Remark. What makes exp(n, x) “ the expo- nent of pn in the prime factorization of x”, rather than an exponent, is Euclid’s prime number factorization the- orem: Every number x > 1 has a unique factorization —within permutation of factors— as a product of primes.
23
24
0.0.0.18 Exercise. Prove by induction on n, that for all n we have pn ≤ 22n .
Hint. Consider, as Euclid did,3 p0p1 · · · pn + 1. If this number is prime, then it is greater than or equal to pn+1 (why?). If it is composite, then none of the primes up to pn divide it. So any prime factor of it is greater than or equal to pn+1 (why?).
3In his proof that there are infinitely many primes.
0.1. CODING SEQUENCES 25 Lecture #9, Oct. 7
0.1 CODING Sequences
0.1.0.1 Definition. (Coding Sequences) Any sequence of numbers, a0,…,an, n ≥ 0, is coded by the number de- noted by the symbol
⟨a0,…,an⟩
and defined as pai+1
Example. Code 1, 0, 3. I get 21+130+153+1
i≤n i
For coding to be useful, we need a simple decoding scheme.
26
By Remark 0.0.0.17 there is no way to have z = ⟨a0, . . . , an⟩ =
⟨b0,…,bm⟩, unless (i) n = m
and
(ii) For i = 0,…,n, ai = bi.
Thus, it makes sense to correspondingly define the de- coding expressions:
(i) lh(z) (pronounced “length of z”) as shorthand for (μy)≤z¬(py|z)
A comment and a question:
• The comment: If py is the first prime NOT in the decomposition of z, and Seq(z) holds, then since numbering of primes starts at 0, the length of the coded sequence z is indeed y.
• Question: Is the bound z sufficient? Yes!
a+1 b+1 exp(y−.1,z) z=2 3 …p .
y times (ii) (z)i is shorthand for exp(i, z) −. 1
y
y−1
≥2·2···2=2 >y
0.1. CODING SEQUENCES 27
Note that
(a) λiz.(z)i and λz.lh(z) are in PR.
(b) If Seq(z), then z = ⟨a0,…,an⟩ for some a0,…,an. In this case, lh(z) equals the number of distinct primes in the decomposition of z, that is, the length n + 1 of the coded sequence. Then (z)i, for i < lh(z), equals ai. For larger i, (z)i = 0. Note that if ¬Seq(z) then lh(z) need not equal the number of distinct primes in the decomposition of z. For example, 10 has 2 primes, but lh(10) = 1.
The tools lh, Seq(z), and λiz.(z)i are sufficient to per- form decoding, primitive recursively, once the truth of Seq(z) is established. This coding/decoding scheme is essentially that of [Go ̈d31], and will be the one we use throughout these notes.
28
0.1.1 Simultaneous Primitive Recursion
Start with total hi,gi for i = 0,1,...,k. Consider the
new functions fi defined by the following “simultaneous
primitive recursion schema” for all x, ⃗y.
f0(0, ⃗y)
.
= h1(⃗y) = hk(⃗y)
= g0(x, ⃗y, f0(x, ⃗y), . . . , fk(x, ⃗y)) = gk(x, ⃗y, f0(x, ⃗y), . . . , fk(x, ⃗y))
. .
fk(0,⃗y) f0(x + 1, ⃗y)
. .
(2)
fk(x + 1, ⃗y)
Hilbert and Bernays proved the following:
0.1. CODING SEQUENCES 29
0.1.1.1 Theorem. If all the hi and gi are in PR (resp. R), then so are all the fi obtained by the schema (2) of simultaneous recursion.
Proof. Define, for all x, ⃗y, Def
Def
F(x,⃗y) = ⟨f0(x,⃗y),...,fk(x,⃗y)⟩ Def
H(⃗y) = ⟨h0(⃗y), . . . , hk(⃗y)⟩
G(x,⃗y,z) = ⟨g0(x,⃗y,(z)0,...,(z)k),...,gk(x,⃗y,(z)0,...,(z)k)⟩
WereadilyhavethatH ∈PR(resp. ∈R)andG∈PR (resp. ∈ R) depending on where we assumed the hi and gi to be. We can now rewrite schema (2) (p.28) as
F(0,⃗y) = H(⃗y) F(x+1,⃗y) =Gx,⃗y,Fx,⃗y
(3)
The 2nd line of (3) is obtained from
F ( x + 1 , ⃗y ) = ⟨ f 0 ( x + 1 , ⃗y ) , . . . , f k ( x + 1 , ⃗y ) ⟩
= g x,⃗y,f (x,⃗y),...,f (x,⃗y),...,g same as g 00kk0
= g x,⃗y,F(x,⃗y) ,...,F(x,⃗y) ,...,g same as g 00kk0
30
By the above remarks, F ∈ PR (resp. ∈ R) depend- ing on where we assumed the hi and gi to be. In partic- ular, this holds for each fi since, for all x,⃗y, fi(x,⃗y) =
F(x,⃗y) . i
0.1. CODING SEQUENCES 31
0.1.1.2 Example. We saw one way to justify that λx.rem(x, 2) ∈ PR in 0.0.0.16. A direct way is the following. Setting
f(x) = rem(x,2), for all x, we notice that the sequence
of outputs (for x = 0,1,2,...) of f is
0,1,0,1,0,1...
Thus, the following primitive recursion shows that f ∈
PR:
f(0) =0 f(x+1) =1−. f(x)
Here is a way, via simultaneous recursion, to obtain a proof that f ∈ PR, without using any arithmetic! No- tice the infinite “matrix”
010101... 101010...
Let us call g the function that has as its sequence outputs the entries of the second row—obtained by shifting the first row by one position to the left. The first rowstill represents our f. Now
f(0) = 0 g(0) = 1 f(x+1) =g(x) g(x + 1) = f(x)
(1)
32
0.1.1.3 Example. We saw one way to justify that λx. ⌊x/2⌋ ∈ PR in 0.0.0.16. A direct way is the following.
0
2 =0
x+1 =x+rem(x,2)
2 2
where rem is in PR by 0.1.1.2.
Alternatively, here is a way that can do it —via simul-
taneous recursion— and with only the knowledge of how to add 1. Consider the matrix
00112233... 01122334...
The top row represents λx. ⌊x/2⌋, let us call it “f ”. The bottom row we call g and is, again, the result of shifting row one to the left by one position. Thus, we have a simultaneous recursion
f(0) = 0
g(0) = 0 f(x+1) =g(x) g(x+1) =f(x)+1
(2)
Bibliography
[Dav65] M. Davis, The undecidable, Raven Press, Hewlett, N. Y., 1965.
[Go ̈d31] K. G ̈odel, U ̈ber formal unentsceidbare s ̈atze der pricipia mathematica und verwandter systeme i, Monatshefte fu ̈r Math. und Physic 38 (1931), 173–198, (Also in English in Davis [Dav65, 5– 38]).
[LeV56] William J. LeVeque, Topics in number theory, vol. I, Addison-Wesley, Reading, Massachusetts, 1956.
33