Incompleteness Theorem -- part 2
See the following by Torkel Franzen for insight into the incompleteness theorems:
http://www.hashref.com/summaries/GodelsTheorem.pdf
Important for Hofstadter is the notion of recursion. This notion also plays a central role in the Goedel's proof. Goedel gives the following definition:
phi(x1,x2,...,xn) is said to be recursively defined in terms of psi(x1,x2,,...,x(n-1)) and mu(x1,x2,...,x(n+1)) if
phi(0,x2,...,xn)=psi(x2,...,xn) and phi(k+1,x2,...,xn)=mu(k,phi(k,x2,...,xn),x2,...,xn).
So, phi is initialized by psi, and increasing values of x1 are given in terms of mu where he have substituted the previous k's phi value in for the value before x2 in mu. Of course we could iterated back from k+1 to zero by back substituting. Oddly, the mu is a function of more variables than phi itself and yet phi is written recursively in terms of it. Well, I guess I don't understand that too well. But then Goedel adds the clause "or results from any of the preceding functions by substitution"; he then gives a footnote with a nice example:
phi_k(x1,x2)=phi_p[phi_q(x1,x2),phi_r(x2)] (p,q,r < k)
This is more like what I think of when I think of recursion, and it allows me to think of a function as recursively defined in term of the previous two functions. The mu thing hasn't really caused me any trouble understanding the rest of the proof, but if anyone out there wants to clear up the mu business that would be cool. When he defines a recursive relation R between natural numbers as being defined by the zeroes of a recursive function phi; that is, R(x1,...,xn) is given by the points x1,...,xn that satisfy phi(x1,...,xn)=0, where phi is recursively defined.
He then states some theorems that make good sense:
1. A function(relation) obtained from recursive functions is recursive.
2. If R and S are recursive, then so are negation R and (R or S) and (R and S).
3. If the functions phi(x) and psi(y) are recursive, so is the relation phi(x)=psi(y).
4. If phi(x) and R(y,z) are recursive then so are the relations
S(x,z)=(there exists a y such that)[y <= phi(x) and R(y,z) holds]
T(x,z)=(for all y)[if y <=phi(x) then R(y,z) holds]
The recursive nature of these definitions plays an important role in the building up of 45 the definitions that he needs to show that unprovability is expressible in terms of PM:
"The functions x+y, x.y, and x(to the y power), as well as the relations x < y and x=y, are recursive, as we readily see. Starting from these notions, we now define a number of functions(relations) 1-45, each of which is defined in terms preceding ones by the procedures given in Theorems 1-4[above] ... Each of the functions (relations) 1-45, among them occur, for example, the notions "FORMULA, "AXIOM", and "IMMEDIATE CONSEQUENCE", is recursive."[van Heijenoort, From Frege to Goedel, pg. 603 -- this book is a compendium of classic papers in mathematical logic including Goedel's incompleteness theorems.]
I take for granted that he succeeded in showing that these things can be expressed in PM. From there the proof of the incompleteness theorem is not so bad.
Hofstadter mentions the recursive formulas when he talks about Goedel and the Fibonacci sequence, which is a sequence of numbers such that each number is the sum of the previous two(starting with the third number, of course): 1,1,2,3,5,8,13,21,...
"...the axioms of PM would play the role of Fibonacci seeds 1 and 2, and the rules of inference of PM would play the role of adding the two most recent numbers."(Hofstadter pp. 160-161 Nookbook)
I will go into more detail regarding the first 45 recursive definitions in the next post.
http://www.hashref.com/summaries/GodelsTheorem.pdf
Important for Hofstadter is the notion of recursion. This notion also plays a central role in the Goedel's proof. Goedel gives the following definition:
phi(x1,x2,...,xn) is said to be recursively defined in terms of psi(x1,x2,,...,x(n-1)) and mu(x1,x2,...,x(n+1)) if
phi(0,x2,...,xn)=psi(x2,...,xn) and phi(k+1,x2,...,xn)=mu(k,phi(k,x2,...,xn),x2,...,xn).
So, phi is initialized by psi, and increasing values of x1 are given in terms of mu where he have substituted the previous k's phi value in for the value before x2 in mu. Of course we could iterated back from k+1 to zero by back substituting. Oddly, the mu is a function of more variables than phi itself and yet phi is written recursively in terms of it. Well, I guess I don't understand that too well. But then Goedel adds the clause "or results from any of the preceding functions by substitution"; he then gives a footnote with a nice example:
phi_k(x1,x2)=phi_p[phi_q(x1,x2),phi_r(x2)] (p,q,r < k)
This is more like what I think of when I think of recursion, and it allows me to think of a function as recursively defined in term of the previous two functions. The mu thing hasn't really caused me any trouble understanding the rest of the proof, but if anyone out there wants to clear up the mu business that would be cool. When he defines a recursive relation R between natural numbers as being defined by the zeroes of a recursive function phi; that is, R(x1,...,xn) is given by the points x1,...,xn that satisfy phi(x1,...,xn)=0, where phi is recursively defined.
He then states some theorems that make good sense:
1. A function(relation) obtained from recursive functions is recursive.
2. If R and S are recursive, then so are negation R and (R or S) and (R and S).
3. If the functions phi(x) and psi(y) are recursive, so is the relation phi(x)=psi(y).
4. If phi(x) and R(y,z) are recursive then so are the relations
S(x,z)=(there exists a y such that)[y <= phi(x) and R(y,z) holds]
T(x,z)=(for all y)[if y <=phi(x) then R(y,z) holds]
The recursive nature of these definitions plays an important role in the building up of 45 the definitions that he needs to show that unprovability is expressible in terms of PM:
"The functions x+y, x.y, and x(to the y power), as well as the relations x < y and x=y, are recursive, as we readily see. Starting from these notions, we now define a number of functions(relations) 1-45, each of which is defined in terms preceding ones by the procedures given in Theorems 1-4[above] ... Each of the functions (relations) 1-45, among them occur, for example, the notions "FORMULA, "AXIOM", and "IMMEDIATE CONSEQUENCE", is recursive."[van Heijenoort, From Frege to Goedel, pg. 603 -- this book is a compendium of classic papers in mathematical logic including Goedel's incompleteness theorems.]
I take for granted that he succeeded in showing that these things can be expressed in PM. From there the proof of the incompleteness theorem is not so bad.
Hofstadter mentions the recursive formulas when he talks about Goedel and the Fibonacci sequence, which is a sequence of numbers such that each number is the sum of the previous two(starting with the third number, of course): 1,1,2,3,5,8,13,21,...
"...the axioms of PM would play the role of Fibonacci seeds 1 and 2, and the rules of inference of PM would play the role of adding the two most recent numbers."(Hofstadter pp. 160-161 Nookbook)
I will go into more detail regarding the first 45 recursive definitions in the next post.
Comments
Post a Comment