Incompleteness Theorem -- part 3
See the great wikipedia page on the proof of Goedel's incompleteness theorem:
http://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s_first_incompleteness_theorem
Now I'll go through an examination of Goedel numbering and pick some hilights from the 45 recursive definitions Goedel gives before moving on to the main proof in the next post.
We assign numbers to the elementary signs as follows:
"0" ... 1
"f" ... 3
"~" ... 5
"or" ... 7
"For all" ... 9
"(" ... 11
")" ... 13
and variables of type n are assigned values of the form p(to the power n) where p is a prime number. So, a type-I variable, a variable standing for a number, is just a prime to the first power. So, 17, 19, 23, etc.. are type one variables.
To move from a number sequence to a Goedel number, we just take the primes in increasing order and raise them to the powers of the signs. For example, 11,17,13 becomes 2(to the 11 power) times 3(to the 17 power) times 5(to the 13 power). Here, 17 is a variable, say x, so 11,17,13 is the sequence for "(x)".
I'm going to try and stay close to Goedel's proof despite the fact that sometimes the notation is a little difficult to understand. I'm going to go through some of the hilights of the 45 definitions he gives before provability. I will then borrow some discussion from the wikipedia page above regarding Goedel numbers of proofs.
Ex="There exists an x". ":=" means "defined to be"
So, here we go.
1.x|y:=(Ez)[z<=x & x=y.z]
x is divisible by y.
___
2. Prim(x):=(Ez)[z<=x & z not = 1 & z not=x &x|z] & x>1.
This reads: There does not exist a z such that z is less than or equal to z with z not =1, z not=x and where x is divisible by z, and also x is greater than 1. A simpler way of saying this is that the only numbers that divide x are 1 and x, and x >1. In other words, x is prime. Notice that 2. used x|y, which is 1.
Skipping to number 8
8.x*y:=(the smallest z){z <=Pr(l(x)+l(y))](to the x+y power) & (for all n)[n<=l(x)-->nGlz=nGlx] & (for all n)[0 < n <= l(y)-->(n+l(x))Glz=nGly]}
This expression uses l(x) from 7., nGLx from 6., and nPrx from 5. So, this is a function recursively defined in terms of previous functions. I know it looks long, but if you write it out it's horrible:
x*y is defined to be the smallest z such that z is smalller than the prime number at place length of the number sequence assigned to x plus length of the number sequence assigned to y to the x=y power and for all n, if n is less than or equal to the length of the number sequence of x then the nth term in the number sequence assigned to z equals the nth term of the number sequence assigned to x and for all n, if n is bigger than zero and less than or equal to the length of the number sequence assigned to y, then the n + length of the number sequence assigned to x term in the number series assigned to z equals the nth term in the number series assigned to y.
All this definition say is that you take two number series and stick the one for y to the right of the one for x. This corresponds in PM to putting two series of signs, for x and y, next to each other. What this illustrates is that the recursive way Goedel does these definitions allows us to avoid having to write out gazillions of symbols and words. By the time you get to 45, these are some pretty big expressions.
Armed with 8 we can start with
9. R(x):=2(to the x power)
and get
10.E(x):=R(11)*x*R(13) to mean putting the Goedel number for "(" with "x" and ")" to yield "(x)" -- 11 is the exponent assigned to "(" and 13 goes to ")". Imagine if this had to be written out!
We can also get
13. Neg(x):=R(5)*E(x) to mean the negation of x or "~(x)"
14. xDisy:=E(x)*R(7)*E(y) means (x) or (y).
15.xGeny:=R(x)*R(9)*E(y) means: "y is true for all x".
Here's part of the definition of substituting y for the nth term of x(number 27)
start with x=u*R(nGlx)*v and substitute y in to yield a number given by u*y*v, where n=l(u)+1(which means that y was subtituted in the place in the number immediately following u, as we wanted).
Later on, number 31, we get the definition of substituting in for a free variable.
Goedel goes on to define axioms, formulas, immediate consequence, and proof.
We end with provable, number 46.
To think about provability we consider a deduction rule D as a relation between the first n-1 formulas of a list and the nth formula. The Goedel number for the first n-1 will stand in numerical relation R to the Goedel number for the nth formula exactly when the first n-1 formulas imply the nth formula by the rule D. So, if we have a list of k deduction rules, then the n-1 formulas is a proof of the nth if the Goedel number of the first n-1 formulas stands in at least 1 of the k corresponding numerical relations to the nth Goedel number.
http://en.wikipedia.org/wiki/Proof_sketch_for_G%C3%B6del%27s_first_incompleteness_theorem
Now I'll go through an examination of Goedel numbering and pick some hilights from the 45 recursive definitions Goedel gives before moving on to the main proof in the next post.
We assign numbers to the elementary signs as follows:
"0" ... 1
"f" ... 3
"~" ... 5
"or" ... 7
"For all" ... 9
"(" ... 11
")" ... 13
and variables of type n are assigned values of the form p(to the power n) where p is a prime number. So, a type-I variable, a variable standing for a number, is just a prime to the first power. So, 17, 19, 23, etc.. are type one variables.
To move from a number sequence to a Goedel number, we just take the primes in increasing order and raise them to the powers of the signs. For example, 11,17,13 becomes 2(to the 11 power) times 3(to the 17 power) times 5(to the 13 power). Here, 17 is a variable, say x, so 11,17,13 is the sequence for "(x)".
I'm going to try and stay close to Goedel's proof despite the fact that sometimes the notation is a little difficult to understand. I'm going to go through some of the hilights of the 45 definitions he gives before provability. I will then borrow some discussion from the wikipedia page above regarding Goedel numbers of proofs.
Ex="There exists an x". ":=" means "defined to be"
So, here we go.
1.x|y:=(Ez)[z<=x & x=y.z]
x is divisible by y.
___
2. Prim(x):=(Ez)[z<=x & z not = 1 & z not=x &x|z] & x>1.
This reads: There does not exist a z such that z is less than or equal to z with z not =1, z not=x and where x is divisible by z, and also x is greater than 1. A simpler way of saying this is that the only numbers that divide x are 1 and x, and x >1. In other words, x is prime. Notice that 2. used x|y, which is 1.
Skipping to number 8
8.x*y:=(the smallest z){z <=Pr(l(x)+l(y))](to the x+y power) & (for all n)[n<=l(x)-->nGlz=nGlx] & (for all n)[0 < n <= l(y)-->(n+l(x))Glz=nGly]}
This expression uses l(x) from 7., nGLx from 6., and nPrx from 5. So, this is a function recursively defined in terms of previous functions. I know it looks long, but if you write it out it's horrible:
x*y is defined to be the smallest z such that z is smalller than the prime number at place length of the number sequence assigned to x plus length of the number sequence assigned to y to the x=y power and for all n, if n is less than or equal to the length of the number sequence of x then the nth term in the number sequence assigned to z equals the nth term of the number sequence assigned to x and for all n, if n is bigger than zero and less than or equal to the length of the number sequence assigned to y, then the n + length of the number sequence assigned to x term in the number series assigned to z equals the nth term in the number series assigned to y.
All this definition say is that you take two number series and stick the one for y to the right of the one for x. This corresponds in PM to putting two series of signs, for x and y, next to each other. What this illustrates is that the recursive way Goedel does these definitions allows us to avoid having to write out gazillions of symbols and words. By the time you get to 45, these are some pretty big expressions.
Armed with 8 we can start with
9. R(x):=2(to the x power)
and get
10.E(x):=R(11)*x*R(13) to mean putting the Goedel number for "(" with "x" and ")" to yield "(x)" -- 11 is the exponent assigned to "(" and 13 goes to ")". Imagine if this had to be written out!
We can also get
13. Neg(x):=R(5)*E(x) to mean the negation of x or "~(x)"
14. xDisy:=E(x)*R(7)*E(y) means (x) or (y).
15.xGeny:=R(x)*R(9)*E(y) means: "y is true for all x".
Here's part of the definition of substituting y for the nth term of x(number 27)
start with x=u*R(nGlx)*v and substitute y in to yield a number given by u*y*v, where n=l(u)+1(which means that y was subtituted in the place in the number immediately following u, as we wanted).
Later on, number 31, we get the definition of substituting in for a free variable.
Goedel goes on to define axioms, formulas, immediate consequence, and proof.
We end with provable, number 46.
To think about provability we consider a deduction rule D as a relation between the first n-1 formulas of a list and the nth formula. The Goedel number for the first n-1 will stand in numerical relation R to the Goedel number for the nth formula exactly when the first n-1 formulas imply the nth formula by the rule D. So, if we have a list of k deduction rules, then the n-1 formulas is a proof of the nth if the Goedel number of the first n-1 formulas stands in at least 1 of the k corresponding numerical relations to the nth Goedel number.
Comments
Post a Comment