# Does Godel preclude a workable TOE?

Godel's incompleteness theorem prevents a universal axiomatic system for math. Is there any reason to believe that it also prevents a Theory of everything for physics?

Edit:

I haven't before seen a formulation of Godel that included time. The formulation I've seen is that any axiomatic systems capable of doing arithmetic can express statements that will be either 1) impossible to prove true or false or 2) possible to prove both true and false.

This leads to the question: are theories of (nearly) everything, axiomatic systems capable of doing arithmetic? (Given they are able to describe a digital computer, I think it's safe to say they are.) If so, it follows that such a theory will be able to describe something that the theory will be either unable to analyse or will result in an ambiguous result. (Might this be what forces things like the Heisenberg uncertainty principle?)

-
 Related post on Math.SE: math.stackexchange.com/q/228806/11127 – Qmechanic♦ Feb 10 at 19:50

The answer is no, because a "Theory of Everything" means a computational method of describing any situation, It does allow you to predict the eventual outcome of the evolution an infinite time into the future, but only to plod along, prediciting the outcome little by little as you go on.

Godel's theorem is a statement that it is impossible to predict the infinite time behavior of a computer program.

Theorem: Given any precise way of producing statements about mathematics, that is, given any computer program which spits out statements about mathematics, this computer program either produces falsehoods, or else does not produce every true statement.

Proof: Given the program "THEOREMS" which outputs theorems (it could be doing deductions in Peano Arithmetic, for example), write the computer program SPITE to do this:

• SPITE prints its own code into a variable R
• SPITE runs THEOREMS, and scans the output looking for the theorem "R does not halt"
• If it finds this theorem, it halts.

If you think about it, the moment THEOREMS says that "R does not halt", it is really proving that "SPITE does not halt", and then SPITE halts, making THEOREMS into a liar. So if "THEOREMS" only outputs true theorems, SPITE does not halt, and THEOREMS does not prove it. There is no way around it, and it is really trivial.

The reason it has a reputation for being complicated is due to the following properties of the logic literature:

• Logicians are studying formal systems, so they tend to be overly formal when they write. This bogs down the logic literature in needless obscurity, and holds back the development of mathematics. There is very little that can be done about this, except exhorting them to try to clarify their literature, as physicists strive to do.
• Logicians made a decision in the 1950s to not allow computer science language in the description of algorithms within the field of logic. They did this purposefully, so as to separate the nascent discipline of CS from logic, and to keep the unwashed hordes of computer programmers out of the logic literature.

Anyway, what I presented is the entire proof of Godel's theorem, using a modern translation of Godel's original 1931 method. For a quick review of other results, and for more details, see this mathoverflow answer:http://mathoverflow.net/questions/72062/what-are-some-proofs-of-godels-theorem-which-are-essentially-different-from-th/72151#72151 .

As you can see, Godel's theorem is a limitation on understanding the eventual behavior of a computer program, in the limit of infinite running time. Physicists do not expect to figure out the eventual behavior of arbitrary systems. What they want to do is give a computer program which will follow the evolution of any given system to finite time.

A TOE is like the instruction set of the universe's computer. It doesn't tell you what the output is, only what the rules are. A TOE would be useless for predicting the future, or rather, it is no more useful for prediction than Newtonian mechanics, statistics, and some occasional quantum mechanics for day-to-day world. But it is extremely important philosophically, because when you find it, you have understood the basic rules, and there are no more surprises down beneath.

There were comments which I will incorporate into this answer. It seems that comments are only supposed to be temporary, and some of these observations I think are useful.

Hilbert's program was an attempt to establish that set theoretic mathematics is consistent using only finitary means. There is an interpretation of Godel's theorem that goes like this:

• Godel showed that no system can prove its own consistency
• Set theory proves the consistency of Peano Arithmetic
• Therefore Godel kills Hilbert's program of proving the consistency of set theory using arithmetic.

This interpretation is false, and does not reflect Hilbert's point of view, in my opinion. Hilbert left the definition of "finitary" open. I think this was because he wasn't sure exactly what should be admitted as finitary, although I think he was pretty sure of what should not be admitted as finitary:

1. No real numbers, no analysis, no arbitrary subsets of Z. Only axioms and statements expressible in the language of Peano Arithmetic.
2. No structure which you cannot realize explicitly and constructively, like an integer. So no uncountable ordinals, for example.

Unlike his followers, he did not say that "finitary" means "provable in Peano Arithmetic", or "provable in primitive recursive Arithmetic", because I don't think he believed this was strong enough. Hilbert had experience with transfinite induction, and its power, and I think that he, unlike others who followed him in his program, was ready to accept that transfinite induction proves more theorems than just ordinary Peano induction.

What he was not willing to accept was axioms based on a metaphysics of set existence. Things like the Powerset axiom and the Axiom of choice. These two axioms produce systems which not only violate intuition, but are further not obviously grounded in experience, so that the axioms cannot be verified by intuition.

Those that followed Hilbert interpreted finitary as "provable in Peano Arithmetic" or a weaker fragment, like PRA. Given this interpretation, Godel's theorem kills Hilbert's program. But this interpretation is crazy, given what we know now.

Hilbert wrote a book on the foundations of mathematics after Godel's theorem, and I wish it were translated into English, because I don't read German. I am guessing that he says in there what I am about to say here.

### What Finitary Means

The definition of finitary is completely obvious today, after 1936. A finitary statement is a true statement about computable objects, things that can be represented on a computer. This is equivalent to saying that a finitary statement is a proposition about integers which can be expressed (not necessarily proved) in the language of Peano Arithmetic.

This includes integers, finite graphs, text strings, symbolic manipulations, basically, anything that Mathematica handles, and it includes ordinals too. You can represent the ordinals up to $\epsilon_0$, for example, using a text string encoding of their Cantor Normal form.

The ordinals which can be fully represented by a computer are limited by the Church-Kleene ordinal, which I will call $\Omega$. This ordinal is relatively small in traditional set theory, because it is a countable ordinal, which is easily exceeded by $\omega_1$ (the first uncountable ordinal), $\omega_\Omega$ (the Church-Kleene-th uncountable ordinal), and the ordinal of a huge cardinal. But it is important to understand that all the computational representations of ordinals are always less than this.

So when you are doing finitary matheamtics, it means that you are talking about objects you can represent on a machine, you should be restricting yourself to ordinals less than Church-Kleene. The following argues that this is no restriction at all, since the Church-Kleene ordinal can establish the consistency of any system.

### Ordinal Religion

Godel's theorem is best interpreted as follows: Given any (consistent, omega-consistent) axiomatic system, you can make it stronger by adding the axiom "consis(S)". There are several ways of making the system stronger, and some of them are not simply related to this extension, but consider this one.

Given any system and a computable ordinal, you can iterate the process of strengthening up to a the ordinal. So there is a map from ordinals to consistency strength. This implies the following:

• Natural theories are linearly ordered by consistency strength.
• Natural theories are well-founded (there is no infinite descending chain of theories $A_k$ such that $A_k$ proves the consistency of $A_{k+1}$ for all k).
• Natural theories approach the Church Kleene ordinal in strength, but never reach it.

It is natural to assume the following

• Given a sequence of ordinals which approaches the Church Kleene ordinal, the theories corresponding to this ordinal will prove every theorem of Arithmetic, including the consistency of arbitrarily strong consistent theories.

Further, the consistency proofs are often carried out in constructive logic just as well, so really:

• Every theorem that can be proven, in the limit of Church Kleene ordinal, gets a constructive proof.

This is not a contradiction with Godel's theorem, because generating an ordinal sequence which approaches $\Omega$ cannot be done algorithmically, it cannot be done on a computer. Further, any finite location is not really philosophically much closer to Church Kleene than where you started, because there is always infinitely more structure left undescribed.

So $\Omega$ knows all and proves all, but you can never fully comprehend it. You can only get closer by a series of approximations which you can never precisely specify, and which are always somehow infinitely inadequate.

You can believe that this is not true, that there are statements that remain undecidable no matter how close you get to Church-Kleene, and I don't know how to convince you otherwise, other than by pointing to longstanding conjectures that could have been absolutely independent, but fell to sufficiently powerful methods. To believe that a sufficiently strong formal system resolves all questions of arithmetic is an article of faith, explicitly articulated by Paul Cohen in "Set Theory and the Continuum Hypothesis". I believe it, but I cannot prove it.

### Ordinal Analysis

So given any theory, like ZF, one expects that there is a computable ordinal which can prove its consistency. How close have we come to doing this?

We know how to prove the consistency of Peano Arithmetic--- this can be done in PA, in PRA, or in Heyting Arithmetic (constructive Peano Arithmetic), using only the axiom

• Every countdown from $\epsilon_0$ terminates.

This means that the proof theoretic ordinal of Peano Arithmetic is $\epsilon_0$. That tells you that Peano arithmetic is consistent, because it is manifestly obvious that $\epsilon_0$ is an ordinal, so all its countdowns terminate.

There are constructive set theories whose proof theoretic ordinal is similarly well understood, see here: http://en.wikipedia.org/wiki/Ordinal_analysis#Theories_with_larger_proof_theoretic_ordinals

To go further requires an advance in our systems of ordinal notation, but there is no limitation of principle to establishing the consistency of set theories as strong as ZF by computable ordinals which can be comprehended.

Doing so would complete Hilbert's program--- it would removes any need for an ontology of infinite sets in doing mathematics. You can disbelieve in the set of all real numbers, and still accept the consistency of ZF, or of inaccessible cardinals (using a bigger ordinal), and so on up the chain of theories.

### Other interpretations

Not everyone agrees with the sentiments above. Some people view the undecidable propositions like those provided by Godel's theorem as somehow having a random truth value, which is not determined by anything at all, so that they are absolutely undecidable. This makes mathematics fundamentally random at its foundation. This point of view is often advocated by Chaitin. In this point of view, undecidability is a fundamental limitation to what we can know about mathematics, and so bears a resemblence to a popular misinterpretation of Heisenberg's uncertainty principle, which considers it a limitation on what we can know about a particle's simultaneous position and momentum (as if these were hidden variables).

I believe that Godel's theorem bears absolutely no resemblence to this misinterpretation of Heisenberg's uncertainty principle. The preferred interpretation of Godel's theorem is that every sentence of Peano Arithmetic is still true or false, not random, and it should be provable in a strong enough reflection of Peano Arithmetic. Godel's theorem is no obstacle to us knowing the answer to every question of mathematics eventually.

Hilbert's program is alive and well, because it seems that countable ordinals less than $\Omega$ resolve every mathematical question. This means that if some statement is unresolvable in ZFC, it can be settled by adding a suitable chain of axioms of the form "ZFC is consistent", "ZFC+consis(ZFC) is consistent" and so on, transfinitely iterated up to a countable computable ordinal, or similarly starting with PA, or PRA, or Heyting arithmetic (perhaps by iterating up the theory ladder using a different step-size, like adding transfinite induction to the limit of all provably well-ordered ordinals in the theory).

Godel's theorem does not establish undecidability, only undecidability relative to a fixed axiomatization, and this procedure produces a new axiom which should be added to strengthen the system. This is an essential ingredient in ordinal analysis, and ordinal analysis is just Hilbert's program as it is called today. Generally, everyone gets this wrong except the handful of remaining people in the German school of ordinal analysis. But this is one of those things that can be fixed by shouting loud enough.

### Torkel Franzen

There are books about Godel's theorem which are more nuanced, but which I think still get it not quite right. Greg P says, regarding Torkel Franzen:

• I thought that Franzen's book avoided the whole 'Goedel's theorem was the death of the Hilbert program' thing. In any case he was not so simplistic and from reading it one would only say that the program was 'transformed' in the sense that people won't limit themselves to finitary reasoning. As far as the stuff you are talking about, John Stillwell's book "Roads to Infinity" is better. But Franzen's book is good for issues such as BCS's question (does Godel's theorem resemble the uncertainty principle).

Finitary means computational, and a consistency proof just needs an ordinal of sufficient complexity.

Greg P responded:

• The issue is then what 'finitary' is. I guess I assumed it excluded things like transfinite induction. But it looks like you call that finitary. What is an example of non-finitary reasoning then?

When the ordinal is not computable, if it is bigger than the Church Kleene ordinal, then it is infinitary. If you use the set of all reals, or the powerset of Z as a set with discrete elements, that's infinitary. Ordinals which can be represented on a computer are finitary, and this is the point of view that I believe Hilbert pushes in "The Grundlagen", but it's not translated.

-
Let's have any further discussion go to Physics Chat. I'll be cleaning up the comments here after a while. – David Zaslavsky May 22 '12 at 4:12
@Argus: The Grudnlagen is a whole book, you just gave a link to a short statement of formalism, which is not the main point of the Grundlagen. – Ron Maimon May 22 '12 at 19:38
@ronmaimon: he is talking about Hilberts book released after grundlagen was already published the link was to a translation of Hilbert statements that were directly related to grundlagens statements – Argus May 22 '12 at 21:18
@Argus: The grundlagen is a book after Godel's theorem and Gentzen, and it is not useful to pick out vague summary statements--- the meat is in the details. How did Hilbert respond to Godel's theorem? This is not clear. Did he propose ordinal analysis? Did he say that countable ordinals are finitary? None of the quotes reveal anything about this question, and I believe the book should. – Ron Maimon May 22 '12 at 21:27
@ronmaimon: my apoligies I misunderstood. Hope this helps ags.uni-sb.de/~cp/p/hilbertbernays/index.html – Argus May 22 '12 at 22:04

I think Conway's Game Of Life is a great example here. We have the "Theory of Everything" for Conway's Game Of Life--the laws that determine the behavior of every system. They're extremely simple! These simple "rules of the game" are analogous to a "theory of everything" that would satisfy a physicist living in the Game Of Life universe.

On the other hand, you can build a Turing-complete computer in The Game Of Life, which means you can formulate questions about the asymptotic behavior of (extremely complex) configurations of dots within the Game Of Life which have no mathematically provable answer.

The two things aren't really related. Of course we can understand the extremely simple "theory of everything" for the Game Of Life. At the same time, of course we cannot mathematically prove the answer to every question about the asymptotic behavior of very complicated configurations of dots within the Game Of Life.

Likewise, we can (one hopes) find the ToE for our universe. But we certainly will not be able to mathematically prove every possible theorem about the asymptotic behavior of things following the laws of the universe. No one expected to do that anyway.

-
 I think we are agreeing to some extent. see my answer (primarily the first section) to this question. – BCS Sep 26 '11 at 3:27 Nobody that needs hope of a resolution as their motivation. So everyone besides me wants to prove that wrong maybe maybe not you would only have to disprove it once for the hundreds of examples supporting it. Same with any proof. Never gonna happen but hope beyond hope is a key aspect of the human condition – Argus May 25 '12 at 0:50

One way to look at this is in terms of Hilbert's 6th problem, i.e. axiomatizing physics. Now, it may be said that what Hilbert understood from "axiomatizing" is refuted by Godel's (and Gentzen's) results (see his 2nd problem).

-
 Hilbert's axiomatization program is not refuted by Godel, but is enhanced by it. Although Hilbert's Grundlagen der Mathematische (sp? Foundation of Mathematics) is not available in English, the basic response to Godel's theorem outlined there is that of Gentzen and the rest of the German school. Gentzen worked with Hilbert, and followed his program. He proved the consistency of Peano Arithmetic by finitary means, and only a postwar politically motivated redefinition of finitary to exclude ordinal countdowns made his proof "infinitary". – Ron Maimon Sep 24 '11 at 4:01

I don't agree with your statement of Godel's theorem. Godel's incompleteness theorem says that in any formal language that is strong enough to do arithmetic (ie you can write down Peano's axioms) there will always be a true statement that can not be proven. What Godel did to prove this was to construct something like the liars paradox in any such language "this sentence is not provable."

I don't think this has any effect on whether or not there is a workable TOE, but I don't know much about TOE.

I feel like Godel's incompleteness theorem is misunderstood a lot. It makes no claims as to whether or not statements are true, it simply says we can not prove everything that is true, somethings just are.

-
 What would the physical theory equivalent be of a true statement that can not be proven? A physical arrangement where the "next step" can't be deduced exactly? (Sounds like the Heisenberg uncertainty principle.) – BCS Sep 22 '11 at 23:05 The statment "we cannot prove everything that is true" is a completely wrong intepretation of Godel's theorem. Godel's theorem does not mean that there are unprovable theorems in an absolute sense, rather it says that given any (consistent, omega-consistent) axiom system S we can find a computational statement which is obviously true but unprovable, which is equivalent to the formal statement "S is consistent". What Godel's theorem says is that given a system S, you can add "S is consistent" to produce a stronger system, and iterate this process transfinitely over all ordinals you can name. – Ron Maimon Sep 24 '11 at 3:49 Every time you take a step up in the tower of axiom system, you prove more theorems. As you go higher, you need to name higher countable recursive ordinals, and this requires more complex computer programs. In the limit that the ordinals get closer to the Church-Kleene ordinal, every true theorem should be provable. This is not a contradiction, because the Church Kleene ordinal is not computable, so the process of getting there is infinitely complex. Set theory is higher up the chain than Peano Arithmetic, and various large cardinals are higher still. Each theory is indexed by an ordinal. – Ron Maimon Sep 24 '11 at 3:54 I don't think anyone here has made the claim that Godel's theorem makes any assertion about unprovable theorems in an absolute sense, but only about systems based on a finite set of axioms. If you allow an infinite set of axioms, then there is a trivial system that is consistent and complete: the system consisting of an axiom asserting every true proposition. – BCS Sep 28 '11 at 2:13 @RonMaimon: I am confused, you say that "The statment "we cannot prove everything that is true" is a completely wrong intepretation of Godel's theorem." Then you say "we can find a computational statement which is obviously true but unprovable." Maybe the differences are above my pay grade... – Sean Tilson Oct 6 '11 at 15:35

tl;dr; All possible universes are finite is scale and are "to small" to be able to encode all possible conjectures so they can't operate on them and thus can't prove their truthfulness. Therefore a fully computable universe model can't violate Gödel's Theorem.

Extracts form various other places in the answers:

I think the answer becomes one of two things:

Option A: Gödel's Theorem does not prevent the existence of mechanistic means for determining the the truthfulness of an arbitrary conjecture. (While I'm not sure that Gödel's preclude this, it is precluded by reduction to the halting problem.)

Option B: that Gödel's Theorem implies that even given a valid, computable, TOE, there is no mapping between arithmetic conjectures and states of the universe such that some identifiable property will hold iff the conjectures is correct. This could be (and I suspect is) true simply by the set of all possible conjectures being larger (a higher order infinity, or larger ordinals) than the set of all possible state of universes that can exist under the TOE.

-

In Aether Wave Theory the Universe is random and it can be infinitely dimensional system of the nested density fluctuations of hypothetical infinitely dense Boltzmann gas. With introduction of sufficient number of dimensions all formal theories will converge mutually into relevant description of Universe, but their determinism will decrease during it. It means, we cannot have the deterministic and universal TOE at the same moment - it's sort of uncertainty principle of quantum mechanics. Even fuzzy theory can still make robust testable predictions, but if would become too general and "universal", it would change into self-referencing implicit tautology.

This theorem can be understood with implicate geometry of AWT: the postulates of formal theories are forming zero rank tensors (tautologies) in casual space and the implications are higher rank tensors, the orientation of which is determined with logical time arrow (implication vectors). These postulates must remain mutually inconsistent, or we could substitute them and replace with single one - which would lead into reduction of theory into tautology and into the lost of its ability to provide testable predictions ("we can draw infinite number of vectors through single point in space"). It means, the axioms of formal theory must remain mutually inconsistent, or we couldn't use this theory for predictions, testable the less - which is basically, what the Goedel's theorems are about for the natural numbers set.

There are already two theories which describe the observable Universe from intrinsic perspective of transverse energy waves (general relativity) and extrinsic perspective (quantum mechanics). IMO these two theories are most deterministic models usable for description of observable Universe, but they cannot be reconciled mutually in solely deterministic way at the price (we cannot mix the intrinsic and extrinsic perspectives in deterministic way).

-