[ Pobierz całość w formacie PDF ]
k
i.e., f0(n) = n and fk+1(n) = f(fk(n)).
Write a formula F (x, y, z) in the language +, ·, 0, 1, =,
terpreted over the natural number system N, defines the 3-place predicate
fx(y) = z.
Exercise 2.2.19. Show that the function »x [ the xth Fibonacci number ] is
arithmetically definable.
Exercise 2.2.20. Which of the following number-theoretic predicates are arith-
metically definable? Prove your answers.
1. x is the sum of all the prime numbers less than y.
2. xy = z.
3. x! = y.
Theorem 2.2.21. Every partial recursive function is arithmetically definable.
Proof. Recall that the partial recursive functions have been characterized as the
smallest class of functions which includes the initial functions and is closed under
composition, primitive recursion, and the least-number operator. Lemma 2.2.6
says that the class of arithmetically definable functions includes the initial func-
tions. Lemmas 2.2.7, 2.2.8, and 2.2.9 say that the class of arithmetically de-
finable functions is closed under composition, the least-number operator, and
primitive recursion, respectively. It follows that the arithmetically definable
functions include the partial recursive functions.
55
Corollary 2.2.22. There exists a set K †" N which is arithmetically definable
but not recursive.
Proof. Recall that
K = {x " N | Õ(1)(x) is convergent}
x
is our basic example of a non-recursive set. By the Enumeration Theorem,
the 2-place partial function »xy[Õ(1)(y)] is partial recursive. Hence, by Theo-
x
rem 2.2.21 »xy[Õ(1)(y)] is arithmetically definable. Let F (x, y, z) be a formula
x
which defines this function. Then K is defined by the formula "zF (x, x, z). This
completes the proof.
More generally, recall our discussion of the arithmetical hierarchy in Chap-
ter 1, Section 1.9. The next theorem characterizes arithmetically definability
(Definition 2.2.1) in terms of the arithmetical hierarchy (Definition 1.9.1).
Theorem 2.2.23. Let P be a k-place predicate, P †" Nk. The following are
equivalent:
1. P is arithmetically definable;
2. P belongs to the arithmetical hierarchy, i.e., P belongs to the class £0 for
n
some n " N.
Proof. Theorem 2.2.21 implies that every predicate in the class £0 (= 0) is
0 0
arithmetically definable. From this it is straightforward to prove by induction
on n " N that every predicate in the class £0 *" 0 is arithmetically definable.
n n
For the converse, put
£0 = £0 = 0 .
" n n
n"N n"N
By Theorem 1.9.2, the class £0 is closed under Boolean connectives '", (", ¬ and
"
universal and existential quantification " and ". From this it follows that every
arithmetically definable predicate P belongs to the class £0 ; this is proved by
"
induction on the number of symbols in a defining formula for P .
Exercise 2.2.24. Let A and B be subsets of N. Prove that if A is reducible to
B and B is arithmetically definable, then A is arithmetically definable.
Exercise 2.2.25. For each n e" 1 let Cn be a set which is £0 complete. Consider
n
the set B = {2n3x | x " Cn}. Prove that B is not arithmetically definable.
Remark 2.2.26 (Hilbert s Tenth Problem). A refinement of Theorem 2.2.23
due to Matiyasevich 1967 is as follows. Let us say that P †" Nk is Diophantine
if P = Àl(Q) for some l e" 0 and some strongly Diophantine Q †" Nk+l. Thus
P = { a1, . . . , ak " Nk | " b1, . . . , bl " Nl (f(a1, . . . , ak, b1, . . . , bl) = 0)}
56
where f(x1, . . . , xk, y1, . . . , yl) is a polynomial with integer coefficients. Matiya-
sevich s Theorem states that P is Diophantine if and only if P is £0.
1
A corollary of Matiyasevich s Theorem is that, for example, the sets K and H
are Diophantine. Thus, we can find a polynomial f(z, x1, . . . , xl) with integer
coefficients, such that the set of a " N for which f(a, x1, . . . , xl) = 0 has a
solution in N is nonrecursive. Here it is known that one can take l = 9, but
l = 8 is an open question.
Hilbert s Tenth Problem, as stated in Hilbert s famous 1900 problem list,
reads as follows:
To find an algorithm which allows us, given a polynomial equation in
several variables with integer coefficients, to decide in a finite number
of steps whether or not the equation has a solution in integers.
From Matiyasevich s Theorem plus the unsolvability of the Halting Problem, it
follows that there is no such algorithm. In other words, Hilbert s Tenth Problem
is unsolvable.
A full exposition of Hilbert s Tenth Problem and the proof of Matiyasevich s
Theorem is in my lecture notes for Math 574, Spring 2005, at
http://www.math.psu.edu/simpson/notes/. [ Pobierz całość w formacie PDF ]
zanotowane.pl doc.pisz.pl pdf.pisz.pl chiara76.opx.pl
k
i.e., f0(n) = n and fk+1(n) = f(fk(n)).
Write a formula F (x, y, z) in the language +, ·, 0, 1, =,
terpreted over the natural number system N, defines the 3-place predicate
fx(y) = z.
Exercise 2.2.19. Show that the function »x [ the xth Fibonacci number ] is
arithmetically definable.
Exercise 2.2.20. Which of the following number-theoretic predicates are arith-
metically definable? Prove your answers.
1. x is the sum of all the prime numbers less than y.
2. xy = z.
3. x! = y.
Theorem 2.2.21. Every partial recursive function is arithmetically definable.
Proof. Recall that the partial recursive functions have been characterized as the
smallest class of functions which includes the initial functions and is closed under
composition, primitive recursion, and the least-number operator. Lemma 2.2.6
says that the class of arithmetically definable functions includes the initial func-
tions. Lemmas 2.2.7, 2.2.8, and 2.2.9 say that the class of arithmetically de-
finable functions is closed under composition, the least-number operator, and
primitive recursion, respectively. It follows that the arithmetically definable
functions include the partial recursive functions.
55
Corollary 2.2.22. There exists a set K †" N which is arithmetically definable
but not recursive.
Proof. Recall that
K = {x " N | Õ(1)(x) is convergent}
x
is our basic example of a non-recursive set. By the Enumeration Theorem,
the 2-place partial function »xy[Õ(1)(y)] is partial recursive. Hence, by Theo-
x
rem 2.2.21 »xy[Õ(1)(y)] is arithmetically definable. Let F (x, y, z) be a formula
x
which defines this function. Then K is defined by the formula "zF (x, x, z). This
completes the proof.
More generally, recall our discussion of the arithmetical hierarchy in Chap-
ter 1, Section 1.9. The next theorem characterizes arithmetically definability
(Definition 2.2.1) in terms of the arithmetical hierarchy (Definition 1.9.1).
Theorem 2.2.23. Let P be a k-place predicate, P †" Nk. The following are
equivalent:
1. P is arithmetically definable;
2. P belongs to the arithmetical hierarchy, i.e., P belongs to the class £0 for
n
some n " N.
Proof. Theorem 2.2.21 implies that every predicate in the class £0 (= 0) is
0 0
arithmetically definable. From this it is straightforward to prove by induction
on n " N that every predicate in the class £0 *" 0 is arithmetically definable.
n n
For the converse, put
£0 = £0 = 0 .
" n n
n"N n"N
By Theorem 1.9.2, the class £0 is closed under Boolean connectives '", (", ¬ and
"
universal and existential quantification " and ". From this it follows that every
arithmetically definable predicate P belongs to the class £0 ; this is proved by
"
induction on the number of symbols in a defining formula for P .
Exercise 2.2.24. Let A and B be subsets of N. Prove that if A is reducible to
B and B is arithmetically definable, then A is arithmetically definable.
Exercise 2.2.25. For each n e" 1 let Cn be a set which is £0 complete. Consider
n
the set B = {2n3x | x " Cn}. Prove that B is not arithmetically definable.
Remark 2.2.26 (Hilbert s Tenth Problem). A refinement of Theorem 2.2.23
due to Matiyasevich 1967 is as follows. Let us say that P †" Nk is Diophantine
if P = Àl(Q) for some l e" 0 and some strongly Diophantine Q †" Nk+l. Thus
P = { a1, . . . , ak " Nk | " b1, . . . , bl " Nl (f(a1, . . . , ak, b1, . . . , bl) = 0)}
56
where f(x1, . . . , xk, y1, . . . , yl) is a polynomial with integer coefficients. Matiya-
sevich s Theorem states that P is Diophantine if and only if P is £0.
1
A corollary of Matiyasevich s Theorem is that, for example, the sets K and H
are Diophantine. Thus, we can find a polynomial f(z, x1, . . . , xl) with integer
coefficients, such that the set of a " N for which f(a, x1, . . . , xl) = 0 has a
solution in N is nonrecursive. Here it is known that one can take l = 9, but
l = 8 is an open question.
Hilbert s Tenth Problem, as stated in Hilbert s famous 1900 problem list,
reads as follows:
To find an algorithm which allows us, given a polynomial equation in
several variables with integer coefficients, to decide in a finite number
of steps whether or not the equation has a solution in integers.
From Matiyasevich s Theorem plus the unsolvability of the Halting Problem, it
follows that there is no such algorithm. In other words, Hilbert s Tenth Problem
is unsolvable.
A full exposition of Hilbert s Tenth Problem and the proof of Matiyasevich s
Theorem is in my lecture notes for Math 574, Spring 2005, at
http://www.math.psu.edu/simpson/notes/. [ Pobierz całość w formacie PDF ]