Incompleteness Theorem -- Part 4
Goedel ends his 46 definitions with the definition for provable:
46. Bew(x):=(Ey)yBx
This definition refers to definition 45 and says: " There exists a y such that y is a proof of x."
There is a theorem, provable by induction, that I will take as a given.
Theorem 0: For every recursive relation R(x1,...,xn) there exists an n place relation sign r between the free variables u1,...,un such that for all n-tuples of numbers (x1,...,xn):
R(x1,...,xn) -->Bew[Sb(r (u1,...,un)=(Z(x1),...,Z(xn))]
_
R(x1,...,xn)-->Bew[Neg[Sb(r u1,...,un)=(Z(x1),...,Z(xn))]]
What this says is that if the relation R holds between the n-tuple of numbers x1,...,xn, then there exists a relation r between variables of PM such that the proposition obtained by substituting the numerals Z(x1),...,Z(xn) corresponding to the n-tuple of numbers into the n variables of r, the result is provable. Note: numerals are repeated applications of the successor function to zero to obtain an expression for a number, say xi, inside the formal system I'm calling PM. This completes the translation from the numerical relation R to the relation r between signs in PM. If the negation of R is true, then the provable proposition is the negation of the proposition you get by performing the substitution into r.
Basically, if a relationship R holds between the natural numbers x1,..,xn, then in PM there is a corresponding relation between the signs(numerals) for the numbers. If the relation does not hold between the numbers, then the corresponding relation between the numerals does not hold.
Now that we have this we can proceed to the statement of the First Incompleteness Theorem:
Definition: A formal system like PM satisfies omega-consistency if there is no formula a for which a(Z(n)) is true for each n and at the same time (for all n)a(Z(n)) is false.
Theorem 1: For every omega-consistent recursive class K of formulas[like the formulas of PM] there are recursive class signs r such that neither v Gen r nor Neg(v Gen r) belongs to FLG(K).
Recall v Gen R:=for all v, R is true.
Also, FLG(K) is the set of consequences of K.
Now, define the relation Q(x,y) between the natural numbers x and y as the relation that exists when the formula corresponding to the Goedel number x is not a proof of the formula obtained when Z(y) is substituted in for the free variable(whose Goedel number sequence is 19) of the formula whose Goedel number is y. That is, and this is important, the numeral for the Goedel number of y is substituted into the formula y's own free variable.
By Theorem 0, there is a relation q in PM such that q(Z(x),Z(y)) is provable in PM whenever Q(x,y) is true, and the negation of q(Z(x),Z(y)) is provable whenever Q(x,y) is false. The relation q is exactly the relation that obtains between Z(x) and Z(y) when the formula x is not a proof of y(Z(y)).
Goedel introduces some abbreviations: p=17 Gen q and r=Sb(q 19=Z(p)).
Now we consider the proposition 17 Gen r=17 Gen(Sb(q 19=Z(p))=Sb(p 19=Z(p))=p(Z(p).
Now, this abbreviation extravaganza actually obscures what is happening here. The wikipedia page has it right: 17 Gen r = (for all y)q(y,Z(p)) . That is, for all y, we have y is not a proof of p(Zp), which is the same as saying p(Zp) is not provable. Now, and this is the interesting part, p(Z(p)) IS 17 Gen r!
Assumption 1: Assume (for all y)q(y,Z(p)) is provable, then there is a formula n such that n is a proof of (for all y)q(y,Z(p)). Substituting n for y we get that q(n,Z(P)) is true.
Now, p(Z(p)) IS 17 Gen r so by Theorem 0, given that n proves p(Z(p)) we know that Q(n,p(Z(p)) is false, we have ~q(n,Z(p)). This contradicts q(n,Z(P)) shown above.
Assumption 2: Assume ~(for all y)q(y,Z(p)). By Theorem 0 we have q(z(n),Z(p)) for every n. But our assumption is ~(for all y)q(y,Z(p)), which contradicts omega-consistency.
46. Bew(x):=(Ey)yBx
This definition refers to definition 45 and says: " There exists a y such that y is a proof of x."
There is a theorem, provable by induction, that I will take as a given.
Theorem 0: For every recursive relation R(x1,...,xn) there exists an n place relation sign r between the free variables u1,...,un such that for all n-tuples of numbers (x1,...,xn):
R(x1,...,xn) -->Bew[Sb(r (u1,...,un)=(Z(x1),...,Z(xn))]
_
R(x1,...,xn)-->Bew[Neg[Sb(r u1,...,un)=(Z(x1),...,Z(xn))]]
What this says is that if the relation R holds between the n-tuple of numbers x1,...,xn, then there exists a relation r between variables of PM such that the proposition obtained by substituting the numerals Z(x1),...,Z(xn) corresponding to the n-tuple of numbers into the n variables of r, the result is provable. Note: numerals are repeated applications of the successor function to zero to obtain an expression for a number, say xi, inside the formal system I'm calling PM. This completes the translation from the numerical relation R to the relation r between signs in PM. If the negation of R is true, then the provable proposition is the negation of the proposition you get by performing the substitution into r.
Basically, if a relationship R holds between the natural numbers x1,..,xn, then in PM there is a corresponding relation between the signs(numerals) for the numbers. If the relation does not hold between the numbers, then the corresponding relation between the numerals does not hold.
Now that we have this we can proceed to the statement of the First Incompleteness Theorem:
Definition: A formal system like PM satisfies omega-consistency if there is no formula a for which a(Z(n)) is true for each n and at the same time (for all n)a(Z(n)) is false.
Theorem 1: For every omega-consistent recursive class K of formulas[like the formulas of PM] there are recursive class signs r such that neither v Gen r nor Neg(v Gen r) belongs to FLG(K).
Recall v Gen R:=for all v, R is true.
Also, FLG(K) is the set of consequences of K.
Now, define the relation Q(x,y) between the natural numbers x and y as the relation that exists when the formula corresponding to the Goedel number x is not a proof of the formula obtained when Z(y) is substituted in for the free variable(whose Goedel number sequence is 19) of the formula whose Goedel number is y. That is, and this is important, the numeral for the Goedel number of y is substituted into the formula y's own free variable.
By Theorem 0, there is a relation q in PM such that q(Z(x),Z(y)) is provable in PM whenever Q(x,y) is true, and the negation of q(Z(x),Z(y)) is provable whenever Q(x,y) is false. The relation q is exactly the relation that obtains between Z(x) and Z(y) when the formula x is not a proof of y(Z(y)).
Goedel introduces some abbreviations: p=17 Gen q and r=Sb(q 19=Z(p)).
Now we consider the proposition 17 Gen r=17 Gen(Sb(q 19=Z(p))=Sb(p 19=Z(p))=p(Z(p).
Now, this abbreviation extravaganza actually obscures what is happening here. The wikipedia page has it right: 17 Gen r = (for all y)q(y,Z(p)) . That is, for all y, we have y is not a proof of p(Zp), which is the same as saying p(Zp) is not provable. Now, and this is the interesting part, p(Z(p)) IS 17 Gen r!
Assumption 1: Assume (for all y)q(y,Z(p)) is provable, then there is a formula n such that n is a proof of (for all y)q(y,Z(p)). Substituting n for y we get that q(n,Z(P)) is true.
Now, p(Z(p)) IS 17 Gen r so by Theorem 0, given that n proves p(Z(p)) we know that Q(n,p(Z(p)) is false, we have ~q(n,Z(p)). This contradicts q(n,Z(P)) shown above.
Assumption 2: Assume ~(for all y)q(y,Z(p)). By Theorem 0 we have q(z(n),Z(p)) for every n. But our assumption is ~(for all y)q(y,Z(p)), which contradicts omega-consistency.
Comments
Post a Comment