Godel's Incompleteness Theorem

  • Thread starter Jonathan
  • Start date
  • #26
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
I see what I was missing; I was considering "complete" to be a statement about a set of axioms, not about a structure.
 
  • #27
3,762
2
Originally posted by Hurkyl
Either you are remembering incorrectly or he is talking about a different kind of incompleteness (unrelated to the meaning of incompleteness in Godel's theorem).

My apologies. What he was actually showing was the incompleteness of Deductive Logic itself, using the basic principle of Euclidean Geometry to illustrate the point. Whether Euclidean Geometry is complete or incomplete wasn't addressed, but rather was used as a means to show the incompleteness of Deductive Logic.
 
  • #28
I repeat that different usages of 'complete' and 'incomplete' abound. The next book or paper you find is apt to attach these terms strictly to issues of proof. I scoured my meager library of books on the subject, and most of them support this usage. Eliot Mendelson of "Introduction To Mathematical Logic" even talks about "absolute incompleteness" within the context of systems that contain the power of producing arithmetic.

Remember, if you use 'complete' and 'incomplete' this way, proof is a matter of BOTH axioms and rules.

I think it was Haskell Curry who wrote in his book ("Foundations of Mathematical Logic", which I don't have) that underlying mathematical philosophy influences how the subject is perceived. A platonist (like Gödel) is apt to believe in truths of mathematics being out there beyond the realm of demonstrations. A formalist (like Hilbert) is apt to see the totality of mathematics strictly in terms of what can be raised in demonstrations. Intuitionists-constructivists are even more strict about what can actually be proven. The terms 'complete' and 'incomplete' may be used differently according to the philosophy of the person.
 
  • #29
HallsofIvy
Science Advisor
Homework Helper
41,833
964
Hurkyl wroteYou may find it interesting to reflect upon the fact that euclidean geometry is both consistent and complete.
.


Yes, I find that very interesting. Do you have a reference for that statement? Consistency I would accept but I thought that it could be shown that the completeness of Euclidean geometry was equivalent (through Cartesian coordinate geometry) to the completeness of algebra which was itself equivalent to the completeness of the natural numbers which is what Goedel proved must be either inconsistent or incomplete.
 
  • #30
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
the completeness of algebra which was itself equivalent to the completeness of the natural numbers

Are you sure on that? :smile:


While the real numbers contain the natural numbers, I don't think it's possible to construct a logical predicate that says "x is a natural number" using just the language of the arithmetic of the real numbers. (all of my ideas on doing this require some set theory)


Anyways, I can't find the text where I recall reading this for the first time, but some internet searching yields http://www.math.hawaii.edu/~dale/godel/godel.html#TarskiUndefinability, http://www.math.psu.edu/simpson/papers/philmath/node15.html [Broken] and http://www.mmsysgrp.com/QuantumGravity/lucasmath.htm .
 
Last edited by a moderator:
  • #31
249
0
First-order arithmetic is a language of terms and formulas. Terms or (positive) polynomials are built from variables x,y,z,..., the constants 0 and 1 and the operators + and x of addition and multiplication. The multiplication operator is normally suppressed in writing. The simplest formulas are the equations, obtained by writing an = between two terms, for instance y+2x+xy+2x3z=5y2, which is an abbreviation for y+x+x+xy+(1+1)xxxz = yy+yy+yy+yy+yy. More complicated formulas can be build from equations by means of connectives and quantifiers:
if P and Q are formulas, then P is a formula, P Q is a formula, P Q is a formula, P Q is a formula, and P <=> Q is a formula.
if P is a formula and x a variable, then x: P and x: P are formulas.
Arithmetic is interpreted in terms of the natural numbers. Every formula is either true or false (if there are free variables a formula is considered equivalent to its universal closure).
Theorem: It is undecidable whether an arithmetical formula is true.

Proof: Suppose there is an algorithm A that, given an arithmetical formula, decides whether that formula is true. I will use that to give a decision algorithm for the language APTM = {(M,w) | M is the description of a Turing machine that accepts the string w}. As the latter problem is undecidable this will show that A cannot exists.

Given a Turing machine M, a configuration of M is given by

a state of M,
the string on M's tape to the left of the position of the head of M (call it the left-string),
and the string on M's tape including the square where the head is, and extending to the right of it (the right-string).
These 3 ingredients will be represented as natural numbers:
The states of M will be numbered by an initial segment of the natural numbers. The initial state will get number 0 and the accepting state number 1.
Suppose the tape alphabet of a given Turing machine M has size n. The left-string on M's tape will be interpreted as the n-adic representation of a natural number. The blank symbol will have value n and the other symbols values 1 to n-1. The n-adic representation yields a perfect 1-to-1 correspondence between strings and numbers.
The right-string on M's tape ends in an infinite sequence of blanks that somehow "don't count". Such a string can handily represented as the n-ary representation of a natural number in reverse. This time the blank symbol has the value 0 and the other symbols (again) values 1 to n-1. In the n-ary representation of natural numbers leading 0's don't count either, so again the correspondence is perfect.
Suppose that the numbers q, x and y hold the values of the current state, the left-string and the right-string in a configuration of M. And suppose that there is a transition from state q (a number) to state r (also a number), labelled with ab,R. Let u and v be the values of the left- and right-string of the configuration that is reached by taking that transition. Than the n-ary representation of y must have ended with the digit a, while v is obtained by chopping of that digit. Thus y=nv+a. Furthermore, the n-adic representation of u is obtained by appending b to the n-adic representation of x. Thus u=nx+b.
An arbitrary configuration can be represented by a triple (Q,X,Y) of variables, whose values represent the state, left-string and right-string of that configuration, respectively. Now the formula

Q=q R=r U=nX+b Y=nV+a

expresses the property that a configuration given by (Q,X,Y) evolves into one given by (R,U,V) by taking the transition from q to r labelled with ab,R. Thanks to the use of n-ary representation for the right-string, there is no need to treat the case that Y represents a string of mere blanks separately (as I did with first order logic).
In case of a left-moving transition ab,L from q to r, the left-string looses a digit, say c, that is appended to the right-string after the last digit of the right-string is changed from a to b. Unless the left-string doesn't have any digits, i.e. is empty; in that case the last digit of y merely changes from a to b. This gives rise to the formula

Q=q R=r ( c: (0 < c < n X=nU+c Z: (Y=nZ+a V=n(nZ+b)+c)) ( X=nU+n Z: (Y=nZ+a V=n(nZ+b))) ( X=U=0 Z: (Y=nZ+a V=nZ+b)) ).

Note that the case where c is the blank symbol is treated separately (through the middle disjunction). This is because in the left-string n-adic representation is used, and the value of c is n, whereas in the right-string n-ary representation is used, and the value of c is 0. The right-most disjunction deals with the case that the head of M was already in the left-most square, so that it couldn't move further to the left, and thus stays where it is. Arithmetic doesn't have the symbol <. However, c < n can be rewritten as k: c+1+k=n.
For every transition in M there is a formula of one the the two forms above telling how a configuration (Q,X,Y) is related to a configuration (R,U,V), reached from (Q,X,Y) by taking that transition. Let T(Q,X,Y,R,U,V) be the disjunction of all those formulas. As M has finitely many transitions, this disjunction is finite as well, and thus a formula of arithmetic. T(Q,X,Y,R,U,V) has free variables Q,X,Y and R,X,Y. It says, in the language of arithmetic, that there is a transition transforming (Q,X,Y) into (R,U,V). That is, the formula T(Q,X,Y,R,U,V) is true exactly when there is such a transition.

Using the formula T(Q,X,Y,R,U,V) it is possible to build another formula T*(Q,X,Y,R,U,V) in the language of arithmetic, with free variables Q,X,Y and R,U,V, that says that it is possible to proceed from configuration (Q,X,Y) to configuration (R,U,V) by following zero or more transitions. T*(Q,X,Y,R,U,V) can be regarded as the reflexive and transitive closure of T(Q,X,Y,R,U,V). Building such a transitive closure within the language of arithmetic is a bit tricky and therefore skipped in class. I will provide the details upon request.

Now the formula

U V: T*(0,0,w,1,U,V)

says that it is possible that to proceed from the initial configuration with the word w on the tape and the head of M in its left-most position, to a configuration involving the accept state. This formula is true exactly when the Turing machine M accepts the word w.
Thus, in order to decide whether or not M accepts w, it suffices to check whether or not the formula above is true in arithmetic. This constitutes a reduction of the acceptance problem for Turing machines to the problem of determining truth in arithmetic. As the former problem is undecidable, so must be the latter.

Theorem: The language of true arithmetical formulas is not even recognizable.

Proof: Suppose B would be a Turing machine recognizing true arithmetical formulas. For any formula P in arithmetic, either P itself or its negation P is true. Thus the truth of P can be decided by running B on P and B on P in parallel. Within a finite amount of time either P or P will be accepted, which settles the question of whether P is true or not. Thus truth in arithmetic would be decidable, contradicting the previous theorem. Hence B does not exists and arithmetical truth is not recognizable.

Theorem: For every reasonable method of provability, the language of provable arithmetical formulas is enumerable (and thus recognizable).

Proof: The first requirement of a reasonable method of provability is that it should be possible to determine whether a given piece of text is a proof or not. Hence it is possible to enumerate all proofs, namely by enumerating all finite pieces of text, and deleting those that aren't proofs. The second requirement of a reasonable method of provability is that it should be possible to determine, given a proof, what formula it is that it proves. This enables the enumeration of all proofs to be converted into an enumeration of all provable formulas

Goedel's incompleteness theorem: If a proof system for arithmetic is sound (meaning that only true formulas are provable) then there must be a true formula that is not provable.

Proof: The set of provable formulas is enumerable, and the set of true formulas isn't. Therefore there must be a difference. QED

Remark: The proof of Goedel's incompleteness theorem given here rests heavily on Church's thesis, which is not a mathematical theorem. Goedel's own proof bypasses Church's thesis (in fact it predates it by several years) and therefore is much more complicated. The undecidability proof of truth goes through also in the absence of Church's thesis: truth is then not recursive. However, showing that provability is recursive enumerable is a lot of work, and requires slightly stronger assumptions regarding the notion of a reasonable method of provability. It is possible to bypass the use of decidability and recursive enumerability by showing that provability is arithmetical (see below), whereas truth is not. Alternatively it is possible to construct an actual formula that is true but not provable; this is what Goedel did.
 

Related Threads on Godel's Incompleteness Theorem

  • Last Post
Replies
15
Views
3K
  • Last Post
Replies
2
Views
1K
Replies
12
Views
3K
Replies
4
Views
3K
  • Last Post
3
Replies
56
Views
5K
  • Last Post
Replies
6
Views
3K
Replies
36
Views
3K
Replies
26
Views
10K
  • Last Post
Replies
6
Views
1K
Top