Does Gödel's Incompleteness Theorem Disprove a Theory of Everything?

This may be a misconception, but it seems to me that the theorem disproves the possibility of a ToE. If I'm not mistaken, then it seems odd that physicists continue to look.

edit: Should this be in the Logic forum instead?

Originally posted by Jonathan
edit: Should this be in the Logic forum instead?

Yep!

Theory of Everything is just an attention-getting title for any theory that purports to render strong, weak, electromagnetic and gravitational interactions from a single scenario. I take Murray Gell-Mann's advice on this one- forget that name! There isn't really a (permanent) "everything" out there.

I expect any such unification theory to presume the full scope of number theory before it even gets started. So there are effectively-undecidable true propositions already in number theory without even dealing with matters of physics.

Originally posted by quartodeciman


I expect any such unification theory to presume the full scope of number theory before it even gets started. So there are effectively-undecidable true propositions already in number theory without even dealing with matters of physics.

why should it "presume the full scope of number theory"?

OK, now for a longer response.

Originally posted by Jonathan
This may be a misconception, but it seems to me that the theorem disproves the possibility of a ToE.

It does not disprove the possibility of "ToE" as physicists use the term, because the "E" does not refer to "Everything including the theory itself (as a formal system)". The "E" refers to "Every known physical interaction". Basically, Goedel's theorem says that any formal system is either inconsistent or incomplete.

Inconsistent means that, for some statement X that can be derived from the theory, it is also possible to derive ~X from the theory. Incomplete means that there are statements in the formal system that cannot be proved from within the formal system itself.

That said, string theory (as well as most other physical theories) are consistent, but incomplete. However, that is an openly acknowledged feature of all quantitative physical theories. And that's OK, because the theories of physics do not rely on their own axioms for confirmation, they rely on experimental evidence for it.

I might have said that better: "the logic capable of producing the full scope of number theory".

Even a geometric theory needs a foundation that includes some kind of complete metric function. Maybe one of those Lego-inspired theories manages to escape that prerequisite. I just don't know. Maybe you can tell me.

quartodeciman, are you saying that any ToE would have to take for granted the validity of numerical (metric) systems? Surely you realize that that is true of all Scientific endeavors. Science is not the only way we gain knowledge, and is thus subject to its own set of constraints (one of which is that it relies on Inductive Logic, and another of which is that it relies on the validity of numbers).

You may find it interesting to reflect upon the fact that euclidean geometry is both consistent and complete.

...ToE would have to take for granted the validity of numerical (metric) systems?

Not just take for granted, but essentially depend upon them to produce results that cover that "everything" implied in calling it unification. Of course, it would be a good retort to me to say that a physical theory might not have to recapitulate this logic to apply to its proper domain. In that case, the theory by itself would not necessarily be subject to Gödelian limitations. But it is hard to conceive doing without a law of large numbers and other stuff like that. How far must a theory go to be considered satisfactory?

Mentat: You answered a questions looming in my mind: somebody is a "Gamma Wave". :)

It seems to me that if you can simulate any physical system by replacing the parts with numbers and letting them interact, every once in a while there'd be a system whose outcome would be reperesented by sqrt(-1) or something. I have a hard time discussing this, it's a bit absract.
How can euclidean geometry be consistent and complete? What about the classical figure of trig relationships, the one with a circle, triangle, and a bunch of lines, because if you draw a triangle in this figure with two 90 degree angles, the third is zero and infinitly far away, making tan(90) not real (divide by zero)?

Originally posted by Hurkyl
You may find it interesting to reflect upon the fact that euclidean geometry is both consistent and complete.

That cannot be true, can it? IIRC, that is exactly the illustration that Hofstadter used in Godel, Escher, Bach: An Eternal Golden Braid. In it the incompleteness of deductive logic was shown using Euclidean geometry (specifically, Euclid's law that any two sides of a triangle who are equal to the same are equal to each other).

Originally posted by quartodeciman
Mentat: You answered a questions looming in my mind: somebody is a "Gamma Wave". :)

LOL!

And here I was trying to make an important point.

That cannot be true, can it? IIRC, that is exactly the illustration that Hofstadter used in Godel, Escher, Bach: An Eternal Golden Braid. In it the incompleteness of deductive logic was shown using Euclidean geometry (specifically, Euclid's law that any two sides of a triangle who are equal to the same are equal to each other).

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).


Incidentally, I just came across this even more interesting statement at http://www.mmsysgrp.com/QuantumGravity/lucasmath.htm

Even more surprising Tarski has shown that geometry and the elementary algebra of real numbers, with addition and multiplication, but without the general notion of natural number, is complete and decidable."

How can that be? What about finding the tan(90)? Sure, for all intents and purposes it is infinity, but in actuallity it is divide by zero. If tan(90) is decidable, then (anynumber)/0=infinity, which means infinity*0=(anynumber)! We know that any number times zero is zero, so how can infinity be any different?! Doesn't this prove that geometry is complete and inconsistent?

Jonathan,

'geometry is complete' means that, metamathematically, every statement well-formed within the system is either true within the system itself or else its negation is true within the system. An example of an 'incomplete' system is geometry without any axiom about parallel lines at all. This is incomplete, because it can be modified by adding an independent euclidean parallel axiom to its given set of axioms, and it can be alternatively modified by adding some independent non-euclidean parallel axiom (e.g. lobatchevskian) to its given set of axioms, each case producing a new refined consistent system. If that parallel-neutral geometry had been complete, a contradiction could have been raised in one of these two refinements. That didn't happen, so the parallel-neutral geometry must be incomplete.

The answer to your objection about the tangent of 90º (and all 90º + multiples of 360º)¹ is that these numbers are just not in the domain of the normal tangent function. That is an entirely different matter from the issue of whether any well-formed statements within the system of geometry might be neither true nor false.

Also, my earlier use of the term 'complete' in the phrase 'complete metric' is something entirely different. It's about existence of limit points to Cauchy sequences of points coming from a metric space ('metric' means a properly-specified 'distance' function for pairs of points). Unfortunately, mathematicians get lazy and start reusing their invented vocabularies, to the confusion of many (me included). :)

{EDIT} an improvement:
¹(and all 90º + integer multiples of 180º)

Regards,

Hi guys,
Hope you don't mind if I butt in. I have just recently heard about this theorem in my math class, and when I first heard of it, it amazed me. I don't quite understand how a system can be incomplete. Say I give a set of axioms, itn't it true that these axioms alone define my system? You can't say that my system is incomplete just because you can think of another axiom to add to my list such that it does not conflict with the one I already have.

For instance, let me propose the following math system:
E={all natural numbers}
A={1>0}
O= {a*b=1 for all a,b in E}
A is the set of axioms, O the set of operations. Now, from this system you can prove just a couple theorems. For example, you can prove 1*0>0. But you may say my system is incomplete, because you can add the axioms "if a>b and b>c then a>c" and "2>1" without contradicting any of my already proven theorems. Now you can prove 2>0, but you can't contradict any other theorem or axiom from before (I think - I haven't put too much thought into this - for the sake of argument, suppose I'm right). But the point is, if I don't include certain things in my list of axioms, that simply means that they aren't a part of my system - they are neither true nor false in my system. They don't exist and don't belong. I hope you understand my blabbering.
So, what's the deal?

...
Also, if ANY system is incomplete or inconsistent, then how do we know that any particular theorem we work with in any system is not both true and false in that system? How do we that differential calculus for example isn't based on at least one inconsistent theorem or axiom?

You're forgetting one important thing of a theory... its language. The language of your theory includes things like the symbol '>' and natural number constants like '2' and '0'... so the proposition '2>0' is a well-formed statement in the language of your theory, and since neither this statement nor its negation can be proven in your theory, your theory is thus incomplete.

So, just to make sure I understand, a system is incomplete if there exists a well-formed statement that cannot be proven or disproven by the axioms of the system?
Say I modified E to be E={0,1}. It is easy to list all statements of the language when there are so few elements. You can have,
1>0
1*1=1
1*0=0
0*1=1
a*b>0 in general
a*b>1 in general
0>0
1>1
Of these statements, at least 0>0 and 1>1 cannot be proven or disproven. So the system is incomplete, right?
I suppose you could get really particular and make a system with only one well-formed statement, which also happens to be an axiom. Would that trivial system be subject to Godel's Theorem?

Because you can find a statement like '0>0' that can be neither proven nor disproven, the system is, indeed, incomplete.

Incidentally, that is not all of the statements of the language; don't forget the logical connectives like 'and' and 'or', and formulas you can make out of variables and quantifiers.

Also, if ANY system is incomplete or inconsistent, then how do we know that any particular theorem we work with in any system is not both true and false in that system? How do we that differential calculus for example isn't based on at least one inconsistent theorem or axiom?

We don't, except inasmuch as someone has produced a viable meta-argument for consistency. Even that is NOT complete assurance. Formal demonstrations of consistency are normally always demonstrations of relative consistency (B is consistent if prior system A is presumed consistent). In the end, consistency is a logical question and we must assume that our prevalent system of logic in use only produces consistent results. Usually that logic is taken to be predicate calculus and axiomatized set theory. At the bottom, we end up having to trust something.

The following is a pretty good position paper. I used to know who made this website, but it was a long time ago and I have forgotten. The short paragraph in the paper about General Relativity theory is not germane to the subject of logical consistency. Singularities forecast by GR are not themselves in the domain of GR, though they can be supposed from outside, in spacetime regions that are not singular. That is not essentially different from the case of Newtonian Gravitation with point-sized gravitational mass-charges. The effects outside can be dealt with; the point-masses themselves can't be dealt with in NG. That rolls back to my earlier comment about the limited domain of the tangent function. --->

http://www.mathpages.com/home/kmath372.htm
Certainty in Mathematics and Physics

If you like to read stuff --->

http://plato.stanford.edu/entries/set-theory/#9
too much ado about Set Theory {SEoP}

...a system is incomplete if there exists a well-formed statement that cannot be proven or disproven by the axioms of the system?

No. That is decidability/undecidability and is the real subject of the first Gödel theorem. This says that there exists a true statement (true in the system) but no demonstration of it or its negation exists.

more bedtime reading -->

http://www.wikipedia.org/wiki/G%F6del's_incompleteness_theorem
Wikipedia: Gödel's Incompleteness Theorem

quart, it seems that you and Hurkyl disagree.
Here's what I don't get:
How can we say something is a mathematical truth if we don't prove it? What do you mean by "true in the system"? If you can demonstrate its negation, certainly it's not true in the system!?
I mean, just because we know intuitively that a+b=b+a doesn't make a mathematical truth, does it?

If quartodeciman is sure, go with what he says. Unfortunately, I don't have a solid reference on this stuff lying around that I can use to double-check myself.

I may have to back down a little. The web is not being kind to my searches for a set of simple, sweet definitions.

Gödel's famous paper was entitled "On Formally Undecidable Propositions of Principia Mathematica and Related Systems". In it he established the existence of a metamathematical statement that asserts that some statement in formal arithmetic cannot be proven. So that metamathematical statement is true in the metalogic that describes arithmetic statements. But in the process of building his demonstration he established an exact one-to-one mapping for converting metamathematical statements like this one into actual statements within formal arithmetic (about numbers and arithmetic expressions). This mapping (call it Gödel imaging) guarantees that true metamathematical statements always map to true arithmetic statements. So if Gödel's proven metamathematical statement is true, then the image in arithmetic for that metamathematical statement is a true statement of arithmetic. Guess what the image of Gödel's result is: the very arithmetic statement Gödel's result was talking about, that cannot be proven. So that arithmetic statement (some unimaginably horrible complex arithmetic relationship) is true but not provable (in fact, it is true BECAUSE it is not provable). If arithmetic is a consistent system, then the negation of the image must be false. Arithmetic is not necessarily a Gödel incomplete system because of this, but it is a Gödel undecidable one. WHEW! Sorry for all that!

Now to back down. David Hilbert thought that every problem was ultimately solvable, so he defined "complete" to mean that every statement or its negation can be proven in the system. Call that "Hilbert completeness". There are plenty of repetitions around for that definition. Also, there are other definitions for "decidable". Some come from Alan Turing's work and the subject of computability. A system is decidable (in this definition) if there exists an algorithm for testing statements within the system and this algorithm is guaranteed to terminate eventually with a YES or NO answer as to the truth of the statement. Maybe "provable" might be a better term for me to use than "decidable". That would take us into logical proof theory. OY VEH!

As a matter of fact, the arithmetic of simple integers is demonstrably an unprovable system, without needing a metamathematical proof. The case in point is a cute little item called Goodstein's theorem. A chosen positive integer is expanded into a polynomial of base 2 and all the exponents are expanded into expressions of 1 and 2. A new number is produced by raising all 2s to 3s and subtracting 1 from the resulting polynomial. Then the resulting value is expanded into a polynomial of base 3. This process is iterated again and again, expressing everything in a new base number, substituting each occurrence of the base number by the next higher integer and subtracting by 1 again. Goodstein's theorem concludes that the sequence of polynomials and numbers must eventually reduce to 0. Somebody proved that Goodstein's theorem cannot be proven in the usual simple arithmetic, but it can be proven in transfinite ordinal arithmetic, which has a more advanced logic (with transfinite set theory). Since it always holds for all normal ordinal numbers, then it is true in simple arithmetic, but can't be proven there.

links:

http://www.u.arizona.edu/~miller/thesis/node3.html
explanation of Goodstein's Theorem

http://www.u.arizona.edu/~miller/thesis/node10.html
proof of GT in transfinite ordinal theory

The thing that bugs me about the "true but unprovable" statement is this...


Suppose we have a consistent system S, and a statement P with the property that neither P nor ~P is provable in S.

The system (S + P) must be consistent; any contradiction derived in (S + P) would trivially yield a proof of ~P in S, violating the hypothesis.

Similarly, the system (S + ~P) must also be consistent.


Because of this, it doesn't seem to make sense to say that any statement of a system is "true but unprovable"; such a claim can only be made in the context of different system.

"true but unprovable" ... bugs me

Rightly so. "Unprovable" means unprovable in some particular system. A refinement of a system by adding more axioms and rules might make one of Gödel's pair p|~p provable. We expect to get new truths from a system through deductions. But we must specify what the system includes.


first---

I suppose a dumb, simple-minded example might start with a little finite set {a , b}, where a and b are specified to be distinct elements. A binary operation "*" might be specified for these elements: * == {<<a, a>, a>, <<b, b>, b>, <<a, b>, b>, <<b, a>, b>}.

So the following statements are logical atomic TRUE statements in this system:

a * a = a, b * b = b, a * b = b, b * a = b.

The axioms might be specified as:

a = a, b = b, a * a = a, b * b = b. (note: no mention of anything like "a * b" or "b * a" in these axioms)

The deduction rules might allow substitutions of equalities and consequences of applied modus ponens.

This happens to be (by specification) a semigroup under *, but not a group. {a} and {b}, with the appropriate parts of *, form separate subgroups.

OK. a~=b, a * b = b and b * a = b are true in this system, but I don't think they can be proven using these axioms. It's not a provable system.

But we already know the logical atomic truths of this system, so we can deduce basic logical molecular truths from these by enjoining them and their negations into complex expressions. It is as complete (in the sense of Gödel) as propositional logic and predicate logic allow it to be.

Adjoin some more axioms (like a * b = b and b * a = b) and you might get a new system that is provable.

done---


Gödel admits that you can add the independent p (or else its negation ~p) as a new axiom to an arithmetic system and make a new system that is equally as consistent as the starting system. But now (since the new system still has the power to generate arithmetic) he will create a new imaging into the new system and recreate his result. Another true but unprovable statement is revealed.

I see what I was missing; I was considering "complete" to be a statement about a set of axioms, not about a structure.

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.

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.

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.

the completeness of algebra which was itself equivalent to the completeness of the natural numbers

Are you sure on that?


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 and http://www.mmsysgrp.com/QuantumGravity/lucasmath.htm .

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.