Gödel’s Theorem

Kurt Gödel[1] was a Platonist,[2] logician and mathematician who developed the intention of making a profound and lasting impact on philosophical mathematics. His next task was to think of something! Amazingly, at the age of twenty five, he achieved his goal, publishing his incompleteness theorem.

A good friend of Albert Einstein’s, Einstein once said that late in life when his own work was not amounting to much, the only reason he bothered going to his office at the Institute for Advanced Study at Princeton was for the pleasure of walking home with Gödel.

John von Neumann wrote: “Kurt Gödel’s achievement in modern logic is singular and monumental – indeed it is more than a monument, it is a landmark which will remain visible far in space and time. … The subject of logic has certainly completely changed its nature and possibilities with Gödel’s achievement.”[3]

While at university, Gödel attended a seminar run by David Hilbert who posed the problem of completeness: Are the axioms of a formal system sufficient to derive every statement that is true in all models of the system?

Gödel’s incompleteness theorem published in 1931 proved that this was not possible.

The point of Gödel’s Incompleteness Theorem is that not everything that is true can be proven to be true by showing that statements are logically derived from axioms. In a “complete” system, every statement that falls within the purview of the system is “decidable;” it can be shown to be either true or false. Only inconsistent axiomatic systems have this ability, at least beyond a certain low level of complexity – but this means permitting contradictions and since there are no true contradictions, a complete system will end up apparently proving that false things are true. Better to opt for an incomplete system where not everything is proved. Settle for proving too little rather than too much!  As Verena Huber-Dyson wrote: “There is more to truth than can be caught by proof.”[4]

Gödel’s Incompleteness Theorem applies to all axiomatic systems capable of generating simple arithmetic at the level of multiplication and above. An axiom is “a statement or proposition on which an abstractly defined structure is based,” a kind of foundational belief or first principle that is treated as self-evident. It is the nature of axioms that their truth is not proven.

Here are the nine revised Peano axioms, necessary for multiplication to work:

(A9)  (Φ(0) → (∀xi(Φ(xi) →Φ(xi′)) →∀xiΦ(xi)))

The choice of axioms for setting up a formal system is guided by an intuitive understanding of what is self-evidently true given the meanings of the symbols of the system. In deciding that a formal system is sensible on this criterion it is not enough that it be self-consistent. A self-consistent system could have false or meaningless axioms and rules of procedure.[5]

Without Gödel’s theorem, making use of notions like “self-evidence” and “meaning” might have been thought to be necessary just for setting up a formal system; for choosing axioms. These vague, intuitive notions would be involved only in this preliminary stage, but have no role in determining mathematical truth. However, Gödel’s theorem shows that mathematical truth goes beyond formalism. As the great mathematical physicist Roger Penrose writes, mathematical truth is “God-given;” such truths exist in a Platonic realm.[6]

Mathematical Platonists think the practice of mathematics involves discovering preexisting truths rather than inventing them. These truths are not creations of the human mind, but the mind can apprehend them.

Formal systems are useful but they are provisional and “man-made;” “they can supply only a partial (or approximate) guide to truth. Real mathematical truth goes beyond mere man-made constructions.”[7]

Formalism in mathematics means reducing it to the mere manipulation of symbols without worrying about what those symbols mean. This is what is going on with the “zeroes” and “ones” of computers which are really just “on,” and “off” switches. The symbols are not even being treated as numbers. Mathematical meaning and mathematical truth are completely eliminated. Since Gödel’s theorem involves reference to truth, the theorem could not even be expressed in a purely formal system.

Formalizing mathematics would make it fully algorithmic; which means following step-by-step procedures for answering well-defined questions universally applicable by all who use them. It turns mathematics into a meaningless game. Even calling the items being manipulated according to rules “symbols” is misleading because a symbol implies some kind of content.

Gödel’s theorem proves that mathematics cannot be completely formalized. Mathematical truth goes beyond the scope of any formal system; both when axioms are chosen and in the Gödelian propositions axiomatic systems generated.

In the late nineteenth century, mathematics had advanced due to new kinds of proofs that often depended on the idea of infinite sets with infinite members based on Georg Cantor’s idea of infinite numbers. These sets were treated as actual things. In 1902, however, confidence in these new ideas and techniques was undermined when Bertrand Russell, working with an idea that Cantor had already anticipated, came up with the following paradox. R is the set of all sets that do not have themselves as members. Is R a member of itself? If it is a member, then R is not a member of sets that do not have themselves as members. If R is not a member, then R is a member of sets that do not have themselves as members.

Mathematicians started to try to figure out a way to avoid these contradictions. Russell and Alfred North Whitehead attempted to come up with a mathematical system using axioms that did not generate paradoxes in their three volume Principia Mathematica, the last volume of which was published in 1913. It tried to derive all mathematics from purely logical axioms while avoiding all contradictions. It took 360 pages to prove that 1 + 1 = 2. Yet, the system required axioms that did not seem to be matters of mere logic[8] and it was very limited and cumbersome to try to use.

David Hilbert wanted to have a system that included all correct mathematical reasoning for any particular mathematical area and to prove it contained no contradictions. Gödel was directly responding to this challenge.

In 1931, Gödel’s incompleteness theorem proved that what Principia Mathematica and Hilbert were trying to do was impossible.

Gödel’s theorem states that any axiomatic system capable of generating the simple truths of arithmetic must include a true statement not provable in that system.

This true proposition lies outside the system. So any axiomatic system of sufficient complexity can be symbolized by A + P. A = axiomatic system. P = a true proposition not decidable by the system.

The + P is called a Gödelian proposition. Gödelian propositions can be included as axioms within a new enlarged system, but this new enlarged system will generate new unprovable Gödelian propositions. These can be again treated as axioms, but the same thing will happen each time. The axiomatic system will generate truths that cannot be determined to be true within the system – rendering the system incomplete each time. Incomplete because unable to prove the truth or falsity of all statements the system knows how to address simply on the basis of its axioms.

The unprovable statement, the +P, that Gödel used in his theorem was this:

“This statement is not provable within this axiomatic system.”[9]

An arithmetic version of this statement could be expressed as:

[10]

If this statement is proved to be true, then it has been proved that the statement is unprovable, since that is what the statement claims, that the statement is not provable within this axiomatic system. We can “see” that it is true. Since the Gödelian proposition is true, its denial must be false, since we should not have been so sloppy as to construct an axiomatic system that includes inconsistencies and the GP is syntactically correct; meaning that it is written following the axioms and rules of procedure of the axiomatic system.

Crucially, while the formal system cannot prove the statement, the human mind can perceive the truth of the proposition. Proposition VI of Gödel’s paper proved that “when an arithmetic proposition g is specified as one which is undecidable within the system, this statement of the undecidability of proposition g is not a mere arithmetic but a metamathematical assertion.”[11]

Gödel’s Theorem proves that any axiomatic system can either be:

1. Consistent, but incomplete; or
2. Inconsistent and complete.
3. However, it is impossible for any axiomatic system to be consistent and complete.

“Consistency” is a desirable feature of a logical system whereby there are no statements which are regarded as both true and false by the system.

“Completeness” is the notion that the logical system will be able to prove a statement either to be true or false that the system knows how to address. However, Gödel’s theorem proves that only inconsistent systems have this feature.

It is vital that option two, “inconsistent and complete,” is avoided. The word “inconsistent” there means contradictory. Any system that includes a contradiction can be used to prove anything at all. Unfortunately, it will “prove” things to be true even when they are false. Consistent systems will be unable to prove all its statements are true but – as stated earlier – better to prove too little than too much!

Propositional logic uses variables as placeholders for constants. Traditionally these include the letters p, q, r, and the like. These variables are used to show the formal structure of arguments – the relations between propositions that can hold across multiple instances.

The most famous and simplest “formal argument” is modus ponens:

If p, then q.

p

Therefore, q.

A lot of arguments have this structure.

• If it rains, then you will get wet.
• It is raining.
• Therefore, you are wet.

Any argument with this structure will be valid, because if the premises are true, then the conclusion must also be true.

The letter “p” stands for any proposition or constant. When replacing variables, the same constant must replace the same variable each time.

One rule of logic is that if “p” is stated, then it is permissible to add “or q.” This is because adding “or q” symbolized by “v q” does not alter the truth of the overall statement. This is what is called “truth preserving.”

If p = I am a human, and q = I am a dinosaur, then p v q says either I am a human or I am a dinosaur. That is true. I am a human. So long as p is true – it is true that I am a human – then it does not matter what q is.

But with a contradiction, p & not p (~p), then it is possible to prove anything.

p & ~p means p is to be considered true and ~p is to be considered true. Therefore, it is possible to write:

1. p
2. ~p

Since p is true, it is possible to write:

3. p v q

But, if ~p is true, then p must be false which leaves q as true.

4. p v q
5. Therefore, q

But q can be anything.

Socrates is human.

Socrates is not human.

Socrates is human or the moon is made of blue cheese.

But Socrates is not human, therefore the moon is made of blue cheese.

Gödel takes something resembling Russell’s undecidable paradox, “if R is the set of all sets that are not members of themselves, is R a member of that set?” and makes it a part of a valid mathematical proof, reversing the attempt to avoid the paradox at all costs.

Gödel’s paradox, “this statement is not provable within this axiomatic system,” might produce a feeling of frustration as though there is a trick involved. Henri Poincaré even accused Georg Cantor, whose set theory started this train of thought, of corrupting the youth.[12] But this feeling is simply revealing a truth; at the root of all slightly complex thought is something that goes beyond the ability of any formal system to prove.

If it were required that all assumptions be formally proved true, human thought could not progress beyond the level of addition; 1 + 1 = 2.

So, if the only complete axiomatic systems are ones based on contradictions, then the desire for an all-encompassing, all-inclusive logical system is misguided. It is simply not possible. There will always be unprovable truths and the mere fact that a truth is unprovable is not necessarily proof that it is false or should be regarded as false.

The desire for “rigor,” and deriving everything from first principles, just does not map on to reality. Gödel’s Theorem proves that some statements are true despite not being formally provable from the axioms of any given system. Intuition is here to stay.

The major physicist Eddington commented: “Dismiss the idea that natural law may swallow up religion, it cannot even tackle the multiplication table single-handed.”[13]

Some writers who want to defend the idea that machines and minds are the same claim that human minds are able to decide the truth of Gödelian propositions that formal systems and thus machines cannot handle not because there is something meaningful being referred to by the terms “intuition,” “self-reflecting,” and “informal,” but because the human mind is inconsistent.[14] The mind is operating algorithmically, but accepts contradictions as true, enabling it to handle Gödelian propositions. Thus we just need to build inconsistent machines to match the human mind.[15]

However, this would mean that the human mind operates on the basis of contradictions and that would be to give up on the idea of rationality. The argument is a performative contradiction since there can be no rational argument that rational proofs do not exist!

Human thought must strive for consistency. If we choose p when it is convenient and not p at other times, then we have just given up on truth and the attempt to make sense of things since our own thinking would make no sense.

An algorithm is a fixed and reliable step-by-step method of deriving particular results to well-defined questions. If the method is followed correctly, the right number will result. Long division and computer programs are examples of algorithms.

At no point in an algorithm can it be stated – “now use your common sense.” Or “insight and intuition enter the picture at this point.” But, with Gödelian propositions, this is precisely what is needed.

It is as easy to produce an algorithm that produces nothing but falsehoods as it is true statements so thinking must go beyond algorithms. The truth and validity of an algorithm requires assessing truth and this is not an algorithmic process.

Anyone who has taken a class in symbolic logic knows that symbolic logic is at most a limited tool – and not a particularly great one at that. It cannot, for instance, capture the relation between cause and effect. It states that conditionals, if p then q, p → q, are true so long as the consequent (q) is true. The antecedent (p) can be anything at all. “If polar bears have 19 teeth, then the world is a sphere.” That statement is considered true if the consequent is true even though there is no particular relationship between the number of polar bear teeth and the shape of the Earth.

Symbolic logic is a technique and it studies the way in which certain types of statements are related to each other. That is why variables are employed. Multiple arguments can have the same logical structure and it is this structure that is being analyzed. Truth as correspondence with the way the world is only enters the picture when variables are replaced with constants and then the statements and argument must be compared to reality. A valid argument is sound only when its premises are true and that truth cannot be determined formally.

“Truth” here has to do with empirically confirmable realities. For most mathematicians, mathematical truths have an objective reality but they are obviously not confirmed by just going outside and checking.

Penrose writes: “Consciousness is a crucial ingredient in our comprehension of mathematical truth. We must “see” the truth of a mathematical argument to be convinced of its validity. This “seeing” is the very essence of consciousness. It must be present whenever we directly perceive mathematical truth. When we convince ourselves of the validity of Gödel’s theorem we not only “see” it, but by so doing we reveal the very non-algorithmic nature of the “seeing” process itself.”[16]

The idea that the human mind operates via algorithms, as a computer does, in a wholly machine-like, rule-driven manner, would mean that we could never perceive the truth of Gödelian propositions because they are not derived algorithmically.

“Machines merely perform functions which man correlates with thought. Their output is devoid of any intellectual content and becomes meaningful only if the human operator is there to interpret it.”[17]

Penrose argues that if mathematicians are unknowingly using an algorithm in their brain for determining mathematical truth; an algorithm that is so complicated and obscure that its validity can never be known, is to misunderstand the nature of mathematics. Mathematicians do not rely on authority and rules that they can never understand. “Mathematical truth is not a horribly complicated dogma whose validity is beyond comprehension. It is something built up from such simple and obvious ingredients – and when we comprehend them, their truth is clear and agreed by all.”[18]

Machines cannot function like minds because machines must be consistent and are rule-following devices. An axiomatic system is such a set of rules but some truths generated by the system can only be perceived by a mind capable of going outside the system and relying on intuition.

We can intuitively perceive the truth of the Gödelian proposition “This statement is not provable within this axiomatic system,” though the perception of this truth is not derived from an axiomatic, rule-driven system. The human mind can do something that a rule-driven device like a computer cannot do.

The validity and truth of an algorithm cannot be algorithmically determined. Alan Turing’s halting problem proved that there is no general algorithm for finding and proving all other algorithms. It is necessary to step outside the narrowly rule-driven confines of a mechanical decision procedure to assess the truth and validity of mechanical decision procedures.

Stanley Jaki writes: “The fact that the mind cannot derive a formal proof of the consistency of a formal system from the system itself is actually the very proof that human reasoning, if it is to exist at all, must resort in the last analysis to informal, self-reflecting, intuitive steps as well. This is precisely what a machine, being necessarily a purely formal system, cannot do, and this is why Gödel’s Theorem distinguishes in effect between self-conscious beings and inanimate objects.”[19]

So long as machines are rule-driven devices, then they must operate within formal systems and they are governed by Gödel’s theorem and computers will not be able to do what minds do. Consciousness, if it did not exist, would need to have evolved precisely to deal with non-rule driven situations – or at least situations where the rules are not known – which are functionally the same. The human mind can often handle unpredictable situations and it would not be able to if the human mind was simply algorithmic like a computer program. This mysterious ability to go beyond formal systems is what we are referring to when we use words like “intuition,” and “creativity.” If this ability was gained by being willing to contradict ourselves then we would have to give up on the idea of truth entirely since there are no true contradictions.

In the stories of the Ancient Greeks, in Hesiod and Homer, hubris was the main moral failing. Hubris is arrogance and the stepping over of appropriate boundaries – particularly between man and the gods. The demand or requirement for certainty and proof in all things is hubristic and a sin against reality. The only way to meet the requirement is to engage in pretense and lies – to engage in contradictions.

Philosophers are right to be suspicious of systems that attempt to have an explanation for everything and that would include religious thinkers like Thomas Aquinas. His Summa Theologica was intended as a resource for priests who when asked a theological question by a parishioner could simply turn to the appropriate section and find the answer. No thinking required. Hegel’s philosophy seems to have a similar tendency.

Since a person’s moral and intellectual growth must be an ongoing process, a book of worthwhile questions might be better than a giant book of answers. So long as the latter is treated as provisional then there is no problem. It is certainly possible to learn something from other people’s attempts to answer questions – most especially if they are not too far ahead of you on the path.

Plato’s philosophy, by contrast with someone like Aquinas, has a definite tentative, questioning, probing quality. He does believe in the Form of Truth, but he is under no illusions that he has cognized it or that it is possible to fully do so. His Socrates’ claim to wisdom, after all, is that he knows that he does not know. Socrates certainly has some firm moral convictions, such as the belief in the pursuit of goodness being worthwhile, but he knows that his attempt to persuade will include unprovable propositions. The worthwhileness of the pursuit of goodness is a conviction that is known intuitively. Plato hopes to persuade the reader partly by showing the beauty of these notions. Socrates, despite his physical ugliness, is morally beautiful. He is restrained, stalwart and seemingly incorruptible.

Scientists have to retain a similar openness to truth not derivable from axioms. They must just hope that reality has some knowable structure. At this point in time, quantum physics which applies to the subatomic scale is inconsistent with the theory of relativity that applies to the very big and the very fast, approaching the speed of light. Since quantum physics and relativity are complex formal systems they will generate Gödelian propositions and this seems to mean that there can be no “Theory of Everything.” The very name is suggestive of an obnoxious hubris and Gödel seems to show that it is in fact an illusion.

Conclusion

C. S. Lewis writes in The Abolition of Man, that if some truths are not treated as self-evident, no truths can be known. Gödel’s Theorem takes this even further and shows that in complex axiomatic systems there will appear true propositions not provable even on the basis of any consistent set of axioms.

The left hemisphere of the human brain is attracted to certainty, logic, mechanism, the ability to articulate propositions clearly. It tends to grandiose optimism about a person’s capacities and to assert tyrannical dominance over the right hemisphere with the latter’s focus on lived experience, the organic, intuition, emotion, the body, music, the perception of depth, humor, poetry, nuance, irony and metaphor.

The fact that axioms are not provable seems like a point of entrance for right hemisphere intuition based on experience. Those who call themselves “empiricists” tend to want to limit experience to truths derived from the measurement of physical reality. Human experience includes a whole rich universe more than that; ranging from emotional and felt aspects of reality to religious experience. The ability to understand other human beings at all relies on these elements.

Gödel’s theorem proves that David Hilbert’s desire to have an axiomatic system from which all mathematical truths can be shown to derive is not possible. This can only be done at the price of inconsistency. It is a common feature of LH writers like Richard Dawkins that they will suddenly introduce propositions that not only are not derivable from their axioms but are inconsistent with them. For instance, in The God Delusion he proposes that moral actions not derived from the biologically advantageous desire for a good reputation and reciprocity are nonetheless “good” mistakes. But, since, he has defined “goodness” as that which offers biological advantage, he is contradicting himself.

Aristotle recognized the provisional nature of axioms when he wrote that first principles are not provable. Now it turns out that no set of axioms are sufficient to capture all true statements no matter how the axioms are modified – at least when it comes to first-order logic.

It is as though LH thinking is a cylinder open at both ends. There is tremendous room for flexibility in the choice of axioms, in philosophical thinking at least. This leaves things so open-ended it is rather astonishing. And not all true statements proceeding downstream from these axioms will necessarily be provable within the system either.

Algorithms, step-by-step procedures for finding answers to well-defined questions, certainly exist. Computer programs are an instance. The halting problem discussed elsewhere shows, however, that there is no algorithm for finding all and only algorithms.

An algorithm can be used in the context of solving a particular problem but rests on non-algorithmic thinking. Axiomatic systems rely on axioms the truth of which must just be assumed and generate truths not provable within those systems either. It is as though no matter how hard the lid is shoved down on the pot, truths fly away into a broader context, the nature of which remains nebulous and poorly defined –  exactly the context in which right hemisphere thinking comes into its own. It is that ability of the human mind that sets it apart from machines.

Notes

[1] The name Gödel is spelt with an umlaut – two little dots above the “o.” Since English does not have umlauts it gets transliterated as “Goedel” which gives a clue concerning the pronunciation, i.e., it is not “God-el,” although some of his fans referred to him as “God.” https://www.newyorker.com/tech/elements/waiting-for-godel

[2] Penrose, R. The Emperor’s New Mind, p. 113.

[3] Halmos, P.R. “The Legend of von Neumann”, The American Mathematical Monthly, Vol. 80, No. 4. (April 1973), pp. 382–394.

[4] Verena Huber-Dyson https://www.newyorker.com/tech/elements/waiting-for-godel

[5] Penrose, p. 112.

[6] Penrose, p. 112.

[7] Penrose, p. 112.

[8] http://www.storyofmathematics.com/20th_russell.html

[9] This gets expressed as an equation – so this is just an English language version of the equation.

[10] Roger Penrose, The Emperor’s New Mind, p. 107. The backwards E symbol with the tilde means “It is not the case that…” This statement does include a word in English, but this is still a legitimately arithmetical expression.

[11] Stanley Jaki, Brain, Mind and Computers, Herder and Herder, 1969,  p. 215.

[12] Aharoni Ron, Cantor’s Story, p. 191.

[13] Science and the Unseen World (NY, 1930), p. 57.

[14] H. Rogers, Jr: Recursive Functions and Effective Computability (Cambridge, Mass., 1957), p. 152.

[15] Inconsistent machines would still need to operate according to some rules or other and then Gödel’s theorem will apply once again.

[16] Roger Penrose, The Emperor’s New Mind, p. 418.

[17] Jaki, p. 228.

[18] Ibid.

[19] Stanley Jaki, Brain, Mind and Computers, Herder and Herder, 1969, p. 220.

Print