சனி, 6 ஜூன், 2015

Gödel’s Incompleteness Theorem:
The #1 Mathematical Discovery of the 20th Century
In 1931, Kurt Gödel delivered a devastating blow to the mathematicians of his time
In 1931, Kurt Gödel delivered a devastating blow to the mathematicians of his time
In 1931, the young mathematician Kurt Gödel made a landmark discovery, as powerful as anything Albert Einstein developed.
Gödel’s discovery not only applied to mathematics but literally all branches of science, logic and human knowledge. It has truly earth-shattering implications.
Oddly, few people know anything about it.
Allow me to tell you the story.
Mathematicians love proofs. They were hot and bothered for centuries, because they were unable to PROVE some of the things they knew were true.
So for example if you studied high school Geometry, you’ve done the exercises where you prove all kinds of things about triangles based on a list of theorems.
That high school geometry book is built on Euclid’s five postulates. Everyone knows the postulates are true, but in 2500 years nobody’s figured out a way to prove them.
Yes, it does seem perfectly reasonable that a line can be extended infinitely in both directions, but no one has been able to PROVE that. We can only demonstrate that they are a reasonable, and in fact necessary, set of 5 assumptions.
Towering mathematical geniuses were frustrated for 2000+ years because they couldn’t prove all their theorems. There were many things that were “obviously” true but nobody could figure out a way to prove them.
In the early 1900’s, however, a tremendous sense of optimism began to grow in mathematical circles. The most brilliant mathematicians in the world (like Bertrand Russell, David Hilbert and Ludwig Wittgenstein) were convinced that they were rapidly closing in on a final synthesis.
A unifying “Theory of Everything” that would finally nail down all the loose ends. Mathematics would be complete, bulletproof, airtight, triumphant.
In 1931 this young Austrian mathematician, Kurt Gödel, published a paper that once and for all PROVED that a single Theory Of Everything is actually impossible.
Gödel’s discovery was called “The Incompleteness Theorem.”
If you’ll give me just a few minutes, I’ll explain what it says, how Gödel discovered it, and what it means – in plain, simple English that anyone can understand.
Gödel’s Incompleteness Theorem says:
“Anything you can draw a circle around cannot explain itself without referring to something outside the circle – something you have to assume but cannot prove.”
Stated in Formal Language:
Gödel’s theorem says: “Any effectively generated theory capable of expressing elementary arithmetic cannot be both consistent and complete. In particular, for any consistent, effectively generated formal theory that proves certain basic arithmetic truths, there is an arithmetical statement that is true, but not provable in the theory.”
The Church-Turing thesis says that a physical system can express elementary arithmetic just as a human can, and that the arithmetic of a Turing Machine (computer) is not provable within the system and is likewise subject to incompleteness.
Any physical system subjected to measurement is capable of expressing elementary arithmetic. (In other words, children can do math by counting their fingers, water flowing into a bucket does integration, and physical systems always give the right answer.)
Therefore the universe is capable of expressing elementary arithmetic and like both mathematics itself and a Turing machine, is incomplete.
Syllogism:
1. All non-trivial computational systems are incomplete
2. The universe is a non-trivial computational system
3. Therefore the universe is incomplete
You can draw a circle around all of the concepts in your high school geometry book. But they’re all built on Euclid’s 5 postulates which are clearly true but cannot be proven. Those 5 postulates are outside the book, outside the circle.
You can draw a circle around a bicycle but the existence of that bicycle relies on a factory that is outside that circle. The bicycle cannot explain itself.
Gödel proved that there are ALWAYS more things that are true than you can prove.Any system of logic or numbers that mathematicians ever came up with will alwaysrest on at least a few unprovable assumptions.
Gödel’s Incompleteness Theorem applies not just to math, but to everything that is subject to the laws of logic. Incompleteness is true in math; it’s equally true in science or language or philosophy.
And: If the universe is mathematical and logical, Incompleteness also applies to theuniverse.
Gödel created his proof by starting with “The Liar’s Paradox” — which is the statement
“I am lying.”
“I am lying” is self-contradictory, since if it’s true, I’m not a liar, and it’s false; and if it’s false, I am a liar, so it’s true.
So Gödel, in one of the most ingenious moves in the history of math, converted the Liar’s Paradox into a mathematical formula. He proved that any statement requires an external observer.
No statement alone can completely prove itself true.
His Incompleteness Theorem was a devastating blow to the “positivism” of the time. Gödel proved his theorem in black and white and nobody could argue with his logic.
Yet some of his fellow mathematicians went to their graves in denial, believing that somehow or another Gödel must surely be wrong.
He wasn’t wrong. It was really true. There are more things than are true than you can prove.
A “theory of everything” – whether in math, or physics, or philosophy – will never be found. Because it is impossible.
OK, so what does this really mean? Why is this super-important, and not just an interesting geek factoid?
Here’s what it means:
  • Faith and Reason are not enemies. In fact, the exact opposite is true! One is absolutely necessary for the other to exist. All reasoning ultimately traces back to faith in something that you cannot prove.
  • All closed systems depend on something outside the system.
  • You can always draw a bigger circle but there will still be something outside the circle.
  • Reasoning inward from a larger circle to a smaller circle is “deductive reasoning.”
Example of a deductive reasoning:
1. All men are mortal
2. Socrates is a man
3. Therefore Socrates is mortal
  • Reasoning outward from a smaller circle to a larger circle is “inductive reasoning.”
Examples of inductive reasoning:
1. All the men I know are mortal
2. Therefore all men are mortal
1. When I let go of objects, they fall
2. Therefore there is a law of gravity that governs falling objects
Notice than when you move from the smaller circle to the larger circle, you have to make assumptions that you cannot 100% prove.
For example you cannot PROVE gravity will always be consistent at all times. You can only observe that it’s consistently true every time. You cannot prove that the universe is rational. You can only observe that mathematical formulas like E=MC^2 do seem to perfectly describe what the universe does.
Nearly all scientific laws are based on inductive reasoning. These laws rest on an assumption that the universe is logical and based on fixed discoverable laws.
You cannot PROVE this. (You can’t prove that the sun will come up tomorrow morning either.) You literally have to take it on faith. In fact most people don’t know that outside the science circle is a philosophy circle. Science is based on philosophical assumptions that you cannot scientifically prove. Actually, the scientific method cannot prove, it can only infer.
(Science originally came from the idea that God made an orderly universe which obeys fixed, discoverable laws.)

Now please consider what happens when we draw the biggest circle possibly can – around the whole universe.
 (If there are multiple universes, we’re drawing a circle around all of them too):
  • There has to be something outside that circle. Something which we have to assume but cannot prove
  • The universe as we know it is finite – finite matter, finite energy, finite space and 13.7 billion years time
  • The universe is mathematical. Any physical system subjected to measurement performs arithmetic. (You don’t need to know math to do addition – you can use an abacus instead and it will give you the right answer every time.)
  • The universe (all matter, energy, space and time) cannot explain itself
  • Whatever is outside the biggest circle is boundless. By definition it is not possible to draw a circle around it.
  • If we draw a circle around all matter, energy, space and time and apply Gödel’s theorem, then we know what is outside that circle is not matter, is not energy, is not space and is not time. It’s immaterial.
  • Whatever is outside the biggest circle is not a system – i.e. is not an assemblage of parts. Otherwise we could draw a circle around them. The thing outside the biggest circle is indivisible.
  • Whatever is outside the biggest circle is an uncaused cause, because you can always draw a circle around an effect.
We can apply the same inductive reasoning to the origin of information:
  • In the history of the universe we also see the introduction of information, some 3.5 billion years ago. It came in the form of the Genetic code, which is symbolic and immaterial.
  • The information had to come from the outside, since information is not known to be an inherent property of matter, energy, space or time
  • All codes we know the origin of are designed by conscious beings.
  • Therefore whatever is outside the largest circle is a conscious being.
In other words when we add information to the equation, we conclude that not only is the thing outside the biggest circle infinite and immaterial, it is also conscious.
Isn’t it interesting how all these things sound suspiciously similar to how theologians have described God for thousands of years?
So it’s hardly surprising that 80-90% of the people in the world believe in some concept of God. Yes, it’s intuitive to most folks. But Gödel’s theorem indicates it’s also supremely logical. In fact it’s the only position one can take and stay in the realm of reason and logic.
The person who proudly proclaims, “You’re a man of faith, but I’m a man of science” doesn’t understand the roots of science or the nature of knowledge!
Interesting aside…
If you visit the world’s largest atheist website, Infidels, on the home page you will find the following statement:
“Naturalism is the hypothesis that the natural world is a closed system, which means that nothing that is not part of the natural world affects it.”
If you know Gödel’s theorem, you know that all logical systems must rely on something outside the system. So according to Gödel’s Incompleteness theorem, the Infidels cannot be correct. If the universe is logical, it has an outside cause.
Thus atheism violates the laws of reason and logic.
Gödel’s Incompleteness Theorem definitively proves that science can never fill its own gaps. We have no choice but to look outside of science for answers.
The Incompleteness of the universe isn’t proof that God exists. But… it IS proof that in order to construct a rational, scientificmodel of the universe, belief in God is not just 100% logical… it’s necessary.
Euclid’s 5 postulates aren’t formally provable and God is not formally provable either. But… just as you cannot build a coherent system of geometry without Euclid’s 5 postulates, neither can you build a coherent description of the universe without a First Cause and a Source of order.
Thus faith and science are not enemies, but allies. It’s been true for hundreds of years, but in 1931 this skinny young Austrian mathematician named Kurt Gödel proved it.
No time in the history of mankind has faith in God been more reasonable, more logical, or more thoroughly supported by science and mathematics.
Perry Marshall
“Without mathematics we cannot penetrate deeply into philosophy.
Without philosophy we cannot penetrate deeply into mathematics.
Without both we cannot penetrate deeply into anything.”
-Leibniz
“Math is the language God wrote the universe in.”

Further reading:
Incompleteness: The Proof and Paradox of Kurt Gödel” by Rebecca Goldstein – fantastic biography and a great read
A collection of quotes and notes about Gödel’s proof from Miskatonic University Press
Formal description of Gödel’s Incompleteness Theorem on Wikipedia
Science vs. Faith on CoffeehouseTheology.com

Comments on Gödel’s Incompleteness Theorem and God »

  •  Don Lauder says:
    Hi Perry,
    I refer to a comment you made almost four years ago:

    Perry says:
    July 8, 2010 at 4:36 pm
    I mean that the universe cannot explain itself, just like your fish cannot explain itself. It has to come from something. It is not self-existent.
    So far as is knowable to modern science, time itself began with the big bang. Einstein’s spacetime theorems indicate that if there is no space, there is no time.
    Time is not infinite and never at any measurable point will become infinite. Time is finite. There is a finite number of seconds in the past and that will always be the case in any rational system of time measurement.
    And yes there most certainly in an edge to the universe.http://en.wikipedia.org/wiki/Size_of_the_universe
    Everything we know about the universe indicates that everything about it is finite.
    It would seem science has advanced (or just changed its mind?) since then. The Wikipedia article you mention now starts with the sentence: “The size of the Universe is unknown; it may be infinite.” Thus, if the universe is infinite, then it becomes in essence what you are describing as God (inifinte, boundless, complete, not applicable to Gödel’s Theorem). If the universe is God, then where does that put God as defined by theologians?
    •  Perry says:
      The Wikipedia article may have changed (this is Wikipedia after all) but Einstein’s space-time theorems have not. So far as I know, space and time are intertwined so if the universe is of finite age, then its size is finite as well. We have no hard facts whatsoever to suggest that the universe is infinitely large, so far as I know. I am open to being corrected.
      •  Matthew Grimm says:
        This is a very interesting subject matter, which Gödel himself dealt with extensively, and is perhaps the most ignored, yet powerful, of the numerous works he accomplished in his lifetime. He and Einstein were actually close friends during their years at the Institute for Advanced Study in Princeton, and they discussed mathematics, physics, and their varying conceptions of God at length (as well as many other subjects).
        Gödel himself originally pursued physics during his earlier education, but instead switched to mathematics, believing it to be much more fundamental. However, what he pursued as a mere “intellectual hobby” was met with his unparalleled intellect, and with a level of understanding and ability that surpassed many of the most well-renowned individuals in their respective fields; and in this particular case, Einstein, and his own theories of relativity.
        I will make a foolhardy attempt to summarize his discoveries, but in order to grasp the full scope and implications of the following materials, I highly suggest reading the book “A World Without Time: The Forgotten Legacy of Gödel and Einstein” by Palle Yourgrau, which is the absolute best available exploration and analysis of the following information. In addition, one may want to study the concept of Gödel Universes/Constructable Universes.
        Gödel had, in the eyes of those who best understood him, considered his work to be primarily philosophical. He would utilize various disciplines (logic, mathematics, physics, etc.) and construct examples which pushed these systems to their logical extremes, in order to discover their implications, limitations, and inconsistencies. His work, in turn, was often at odds with the advocates of the systems he studied. Empiricist and logical positivist dogmas had persisted throughout the intellectual zeitgeist, but in Einstein, he found a matching enthusiasm for rationalist conceptions of reality and metaphysics. Their shared beliefs, as well as their many disagreements, led to many extensive, rich, and colorful dialogues covering all sorts of interests. In turn, Einstein’s own work became a topic of discussion and interest.
        The scientific consensus (then and now) is that the General Theory of Relativity shows that we live in an existence with 4 dimensions, 3 spatial, and one of a space-time composite. However, Gödel found the dominating interpretations to be inconsistent and inaccurate, for philosophical as well as physical reasons. He created the following “proof by contradiction” (assuming the opposite of his desired conclusion (that the concept of time and relativity theory are incompatible), and showing it led to absurd/contradictory conclusions). In his demonstration, he created many different mathematical models of a special kind of universe with a curved geometric topology that contained “world lines” which were closed loops (resulting from an even distribution of matter that created a geometrically-balanced warping of space-time). He then demonstrated that such a construction was consistent with the mathematics of General Relativity. Following this, he showed that typical “intuitive” conceptions of time are not logically consistent with the “little t” of Relativity Theory.
        Time, as it is traditionally understood, is approached in one of two ways. One school of thought is that time is a dynamic, continuous flux of ceaseless change, and that we are forever imbedded in the now (the past no longer exist, the future does not exist yet). Einstein’s claims of the implications of the Special Theory of Relativity, however, are highly problematic for this belief. It states that each event has a separate, unique inertial frame of reference; there is no shared “now” between events, or in any moment, “past,” “present,” or “future.” The other competing theory of time is that the past, present, and future exist simultaneously, even though we only experience “our” frame as we move from one to another. This is supplemented by the notion of the “arrow of time,” a concept in physics often linked with the principles of thermodynamics/entropy. In this model, time is a vector, having a set direction/pathway, and events are ordered such that no event can ever occur before a chronologically-previous event (ex: Gödel discovering his Incompleteness Theorems before he was born).
        These intuitive assumptions seem logical, but following from the belief that the General Theory of Relativity had demonstrated a union between space and time, Gödel showed such a thing would lead to the possibility of the aforementioned “closed time-like loops.” Following one of these loops (which he proved to be physically possible) would result in a journey where one moves continuously towards the future, until arriving at event preceding the beginning of the journey. Often, this is assumed to be a case for time travel, but it is not. The same “world lines” could lead to trajectories which violate the ordered nature of the “arrow of time,” i.e. where you could theoretically reach Gödel’s Incompleteness Theorems before his birth.
        In essence, he showed that any universe which operates in accordance with the mathematics of the Theories of Relativity absolutely cannot support any idea of time. The fourth dimension of Einstein’s physics is entirely spatial, time is an illusion.
        His work is much more far-reaching and well-supported than just what I’ve discussed; I barely scratched the surface of his other justifications/methods of proof. I’ve only presented the simplest mode of argument, but there are many more, and equally thorough, exacting, and rigorous.
        Any discussion regarding the relationship between the concept of time and God, or time at all, especially within Godel’s worldview, is rendered inept, inconsistent, and naive. Our intuitions and senses fail us in providing an accurate account of reality, only rationality can suffice to remedy our misconceptions. This is the main reason why these results have practically gone ignored in the physics community-rationality relies on logical devices, where science depends on the experimental and observable. Since scientists can’t study a Godel Universe (only it’s mathematics), many have attempted to formulate ad hoc principles to prevent these results from being relevant, none withstanding scrutiny and critical thinking. However, for many, such a strange, counterintuitive understanding of Einstein’s theories (which even Einstein himself misunderstood and doubted entirely until he couldn’t find any evidence disproving Godel’s results) is very difficult to accept; it requires the vast majority of modern science to be revised. This, indeed, is a tough pill to swallow.
        Regardless of the controversies and ignorance, the implications are very well-suited to the characteristics of God. There is nothing that has yet to be revealed, no dominion inaccessable to the God of Godel’s beliefs. Although we may experience “time” as a confabulation of our mind, it does not actually limit the actuality and totality of existence into chronological segments. Everything is, and always will be (in fact, “always” is a poor choice of words, because it implies time exists at all). This couples nicely with Godel’s determinism and idealism, and can explain his hesitancies towards anything that claimed to limit the order and rational construction of existence.
        Also, having space requires energy (this can be seen in a vacuum), so an infinitely sized universe would require infinite energy to sustain it.
        I hope this is helpful in stimulating further thought, I apologize for my inability to do so in fewer words.
        •  David says:
          Very interesting is right!
          In your synopsis, Godel’s conclusions sound incredibly similar to the “spherical one-being” described by the pre-Socratic philosopher Parmenedes. As being must be everything except non-being, Parmenedes concludes that everything that is, is one constant being of finite completeness. Thus anything that is, cannot move because it is already where it is. The Atomists, and later Aristotle, had some problems with this theory- namely that movement can and is observable -but they remained incapable of completely disavowing its implications, only succeeding in compounding it with emerging theories. At first glance, Godel seems to have assembled a mathematical formulation of the paradox of movement parsed out by Parmenede’s contemporaries.
          Echoes of the immovable oneness rung through my mind when I discovered the ideas of Godel. I have to read more though, as first impressions can often be very misleading.
  •  Nicooo says:
    Well, nice talk about Godel’s Theorem and its relation to the existence of God. I think however that even if the existence of god is indeed one (intuitive) possibility (but by calling it God, we kind of assimilate it as a system, which means there would be something outside it), your explanation at the end is a little dubious to asses God is a necessity for science to exist.
    First you said :
    – “we also see the introduction of information, some 3.5 billion years ago. It came in the form of the Genetic code, which is symbolic and immaterial.”
    This seems to me much debatable. Why do the Genetic code would be the origin of information ? Can’t we for example describe the existence of matter, energy, space, time as information ?
    –> Therefore your induction from codes to God is not that obvious for me (in addition to be just one possible induction). It is actually very intuitive for people who believe in God, but not at all for the others I think.
    – “All codes we know the origin of are designed by conscious beings. Therefore whatever is outside the largest circle is a conscious being.”
    That said, I think this relation between Religion/God/Phylosophy/Metaphysics/etc. and Godel’s Theorem is interesting. In a sense, I think that without really noticing it, most of us get the intuition behind Godel’s theorem when we reflect on ourself, the world, god etc.
    Nicolas
  •  Rb says:
    Yes, Godel’s Theorums are incredibly important and interesting and most of what you write is interesting and correct, but you draw several “conclusions” which are misleading and aren’t necessarily true. For example:
    “But… it IS proof that in order to construct a rational, scientific model of the universe, belief in God is not just 100% logical… it’s necessary.”
    Not necessarily. God in today’s world is a very specific entity, the odds of that being the real answer seems pretty slim. Now, the idea of a “God-Like” entity, something so advanced/powerful/whatever that “created” us isn’t out of the question. But to say that because we can’t explain life one MUST believe in God is just not true. We don’t really even have an inkling of the ways the universe
  • கருத்துகள் இல்லை:

    கருத்துரையிடுக