Remembering Gödel
The story of Kurt Gödel (1906–1978) is forever captivating. The enigma surrounding the reclusive genius conspires with the mystery of his Incompleteness Theorem to generate an aura of endless awe and wonder.
“Gödel was the greatest logician since Aristotle,” polymath John von Neumann said in a public lecture. Albert Einstein and Robert Oppenheimer firmly agreed. John Wheeler remarked, “If you called him the greatest logician since Aristotle you’d be downgrading him.” André Weil said it would be banal to affirm that in 2,500 years Gödel was the only person who could speak without exaggeration of “Aristotle and me.” (Dyson, 2013; Wang, 1996, p.2.)
Yet, Gödel never played the great man. He berated himself for his perceived shortcomings. He was very sincere and unassuming, and his innocence drew many to him. (Budiansky, 2021, pp. 91, 103–104.)
He was very generous, especially with his peers, with whom one might probably become more competitive. He was always willing to assist with their ideas while quite modest about his own work. “What a conscientious person Gödel was,” noted mathematician Verena Huber-Dyson. “His friendliness & his quiet humor are so appealing,” noted his long-time friend, economist Oskar Morgenstern. (Budiansky, 2021, pp. 69, 103, 170, 263.)
Harvard logician Gerald Sacks noted that Gödel had a “zest for life” and enthusiasm for ideas. “He was full of wonder and excitement over developments in math, logic, philosophy.” It was like talking to “a very bright eleven-year-old.” (See Budiansky, 2021, pp. 105.)
Gödel was a special friend of Einstein. He was the only one at the Institute for Advanced Studies in Princeton who “walked and talked with Einstein on equal terms,” noted Freeman Dyson. Einstein “appreciates Gödel beyond anything,” Oskar Morgenstern wrote in his diary. Einstein once remarked that he came to the office “just to have the privilege of being permitted to walk home with Kurt Gödel.” Despite having very dissimilar personalities, the two understood each other very well. They shared a fundamental quality: both went directly and wholeheartedly to the questions at the very center of things. (See Budiansky, 2021, pp. 3, 173, 217-218.)
The Incompleteness Phenomenon
When Gödel submitted his incompleteness paper to the University of Vienna as his Habilitationsschrift, his mentor and supervisor, mathematician and philosopher Hans Hahn, wrote:
“It is a scientific achievement of the first order which has generated the highest interest in all expert circles and, as can be predicted with certainty, will take its place in mathematical history.”
On the occasion of the presentation of the Albert Einstein Award to Gödel in 1951, John von Neumann remarked:
“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.”
Von Neumann emphasized that Gödel’s results are not specific to the field of mathematics but are general to any field that applies formal methods:
“Gödel actually proved this theorem, not with respect to mathematics only, but for all systems which permit a formalization, that is a rigorous and exhaustive description in terms of modern logic: For no such system can its freedom from inner contradiction be demonstrated with the means of the system itself.”
A key insight of Gödel’s Incompleteness Theorems is that formal systems rich in arithmetic can be either complete or consistent, but not both. To be complete means the system is capable of proving or disproving every sentence formulated in the language of the system. To be consistent means to be free from contradictions.
The Theorem establishes that there are trade-offs between consistency and completeness (Tieszen, 2017, p. 136). A consistent system will not be able to prove every sentence in its language. The set of truth is larger than the set of proof. Even in pure logic, it seems, there is no free lunch! Consistency is a scarce commodity.
The basic idea of the tradeoff between completeness and consistency, in the general sense, can be seen in everyday life. Consider the following statement (call it R):
(R) Every rule has an exception.
Clearly, (R) itself is a rule. Does (R) apply to itself? If yes, then there will be rules that have no exceptions, which contradicts the claim of the rule. If not, then (R) does not apply to “every” rule. The range of its applicability must be incomplete to avoid contradiction. We need to amend the rule by replacing “Every” with “Many,” for example, to consistently maintain its claim.
Here is another example:
(D) We never describe facts objectively.
Statement (D) itself is supposedly a description of a fact. Does it apply to itself? If so, then (D) will not be objective, which contradicts its claim. If not, then it will not be “complete,” and so we need to replace “never” with “frequently” or something similar.
Finally, consider the following statement:
(T) Truth is always relative.
Assuming (T) is true, does it apply to itself? If yes, then (T) is relative, and thus there are truths that are not relative. This contradicts the claim of (T). If it does not apply to itself, then the range of (T) is incomplete, and thus we need to replace “always” with “sometimes” for example to maintain consistency.
In these examples, we see how self-reference might lead to contradiction. In general, therefore, there is a tradeoff between the completeness of the range of a rule and its logical consistency. The essence of the incompleteness phenomenon is more common than might be thought.
Mini Gödel Theorem
One way to illustrate the key idea of incompleteness is provided by the mathematician Raymond Smullyan in several of his books. He calls it the “Gödelian Machine.” Logician Henk Barendregt calls it “Mini Gödel Theorem” (Smullyan, 2014, p. 171).
The “Mini Theorem” puts the basic idea of Gödel’s Theorem, borrowing from Smullyan (1982, p. 195), into as clear a light as can be imagined. The following exposition is based on Smullyan’s (2009) Logical Labyrinths, pp. 311–312.
Imagine a computing machine, the “Gödelian Machine,” that prints out expressions built from the following three symbols:
- P
- R
- ∼
An expression is any combination of these symbols (for example, PP∼RP∼∼ is an expression, and so is ∼, P, or R standing alone). By X we denote any expression.
P stands for “printable,” so PX means “X is printable.” RX results in repeating X, and hence RX = XX. The symbol ~ means “not,” so ~PX means “X is not printable.”
By a sentence is meant any expression of one of the following four forms:
- PX. This means X is printable.
- ∼PX. This means X is not printable.
- RPX. This means XX is printable.
- ∼RPX. This means XX is not printable
Each of these sentences is said to be true if and only if its meaning holds. So, for example, PX is true if and only if X is printable, and so on for the other sentences.
Any printable expression is assumed to be printed sooner or later by the machine. The machine is assumed to be totally accurate in that it prints only true sentences. Thus,
- If PX is printed, then X will also be printed, sooner or later.
- If ∼PX is printed, then X will never be printed.
- If RPX is printed, so will be XX.
- If ∼RPX is printed, then XX will never be printed.
Now comes the big question:
If the machine prints X, does that imply that it will print PX? Remember, PX means X is printable. So, if X is printed, then PX must be true. But does that imply that PX will also be printed?
The surprising answer is: No!
While every sentence printed by the machine is true (by assumption), there is nothing that says that all true sentences must be printable. This can be illustrated as follows:
Consider the sentence ∼RPX. As explained earlier, this sentence is true if and only if XX is not printable. Now, since X stands for any expression using the symbols of the machine, let X = ∼RP. Our sentence now becomes ∼RP∼RP. What does this sentence mean?
It means that the repeat of “~RP” is not printable. But what is the repeat of ~RP? It is the sentence ∼RP∼RP itself! Accordingly, the sentence ∼RP∼RP is saying about itself that it is true if and only if it is not printable.
To link this to Gödel’s theorem, we reinterpret P to mean provable in the system, rather than printable by the machine. Then, given that the system is wholly accurate (so that false sentences are never provable in it), the sentence ∼RP∼RP would be a sentence that is true but not provable in the system (Smullyan, 1992, p. 4). This is basically what the First Incompleteness Theorem says.
It is worth mentioning that the above printing system, as Henk Barendregt points out (personal communications), is a formal axiomatic system capable of expressing sufficient arithmetic. Incompleteness, therefore, does not require very complicated systems.
The Incompleteness Theorem can be further elaborated using the imaginary tale of Knights and Knaves, created by Raymond Smullyan in several of his books, particularly Forever Undecided (1987). Below is a modified version of this story.
A Logic Tale
On a sunny day in October 2931, a Logician decided to travel to an exoplanet in Alpha Centauri, about 4 light-years from Earth, to visit a newly discovered civilization. The citizens of the mysterious city are of a unique nature. They are of two types: either Knights or Knaves. Knights always tell the truth, while Knaves always lie.
After settling in a robot-managed hotel, the Logician went out to explore the highly advanced and sophisticated city. He was wondering to himself, how would one know if a citizen was a Knight or a Knave?
While wandering around, he encountered a citizen who seemed curious about this Earthly visitor. The Logician approached the citizen and asked innocently, “Excuse me. May I ask if you are a Knight or a Knave?” The citizen looked directly into the eyes of the Logician and replied with a deep voice:
“You will never believe that I am a Knight!”
The citizen then magically disappeared.
The Logician was quite puzzled by the statement. He spent the rest of the day in his room thinking about it. Being a strict logician, he started analyzing the statement. Suppose the citizen was a Knave. Then the statement must be false. Thus the true statement must be either:
- “You will believe that I am a Knight,” or
- “You will never believe that I am a Knave.”
The first statement implies that the Logician will believe the citizen was a Knight when in fact he was a Knave. This would be a false belief. If logic in general does not lead to a false belief, then the first possibility can be excluded for the time being.
The Logician is now left with the second possibility. The second states that the Logician will never believe the citizen was a Knave, when in fact he was a Knave. This is strange.
The Logician next asked himself, What if the citizen was a Knight? Then, the statement “You will never believe that I am a Knight” must be true. The Logician is now left with two options:
- If the citizen was a Knight, the Logician would not be able to prove that he was a Knight.
- If the citizen was a Knave, the Logician would not be able to prove that he was a Knave.
The Logician was seriously disturbed: How come he was unable to prove the true nature of the citizen? The citizen can be either a Knight or Knave and there is no other possibility. So, if it is not possible to prove the citizen was a Knight, the Logician must be able to prove he was a Knave (or vice versa). Yet, he is unable to prove either without falling into contradiction: If he proves the citizen was a Knight, this would contradict the Knight’s statement. If he proves the citizen was a Knave, this would contradict the negation of the Knave’s statement.
The Logician therefore found himself in a dilemma: Either he could prove every true statement, in which case he would become inconsistent. Or he shall maintain consistency but then he will fail to prove some true statements.
Back on Earth, the Logician had the impression that logic was complete: If A was not provable, then its negation, ~A, must be provable. He read somewhere about “Gödel’s Theorem,” published a millennium ago, but he thought the Theorem had only a marginal value and no practical relevance.
To resolve this dilemma, the Logician decided to use the advanced time-travel technology designed by the Centaurians, and traveled back 1000 years, to the year 1931, to meet the Great Master Kurt Gödel. Gödel has just published his incompleteness paper. “Herr Gödel,” said the Logician. “Can you explain to me this dilemma?”
The Master then carefully and clearly explained to him that the logical system of Alpha Centauri is a rich mathematical system. Such systems, while consistent, are incomplete. The citizen’s statement is analogous to the sentence Gödel has just discovered: “This sentence is not provable.” The sentence shows that there will be true sentences formulated in the language of the system that are not provable within the system.
“The way out of the dilemma,” said the Master while relaxing on his chair, “is to be humble and admit that you cannot prove all truths. Truth extends infinitely beyond the boundaries of reason.” He then leaned forward on his chair and said in no uncertain words: “The ultimate wisdom, my friend, is to remain forever undecided about your own consistency.”
Awed by the words of the Master, the Logician stood up and said, “Thank you, indeed, Herr Gödel.” As he was leaving, he assured the Master, “For the rest of my life, I promise you it will be my quest to search for the inexhaustible truth anywhere in the vast Universe and beyond.”
World Logic Day
On 26 November 2019, the 40th General Conference of UNESCO proclaimed 14 January of every year to be World Logic Day. The proclamation, made in association with the International Council for Philosophy and Human Sciences (CIPSH), intends to bring intellectual history, conceptual significance, and practical implications of logic to the attention of interdisciplinary science communities and the broader public.
The architect of World Logic Day is Jean-Yves Beziau, a Swiss Logician, Philosopher, and Mathematician. Beziau, a Professor at the University of Brazil in Rio de Janeiro, has also served as a Coordinator of Graduate Studies in Philosophy and President of the Brazilian Academy of Philosophy.
As he explains, Beziau’s inspiration for World Logic Day arose nearly 15 years ago upon realizing the convergence of two important dates in the history of logic: the death of Kurt Gödel on 14 January 1978, and the birth of Alfred Tarski on 14 January 1901. Tarski is considered one of the greatest logicians of the twentieth century, often regarded as second only to Gödel. Acknowledging the profound contributions of the two giants, there was a compelling reason to commemorate 14 January as a day of global recognition for the field.
Though Gödel’s earthly tenure has concluded, his intellectual legacy is as alive as ever. His profound insights into mathematics, science, and philosophy continue to shine, like a candle that once burned to reveal some of the most significant discoveries ever conceived by the human mind.
References
- Budiansky, S. (2021). Journey to the Edge of Reason. W.W. Norton.
- Dawson, J. (1997). Logical Dilemmas: The Life and Work of Kurt Gödel. A.K. Peters.
- Dyson, F. (2013). A walk through Johnny von Neumann’s garden. Notices of the AMS, 60, 154–161.
- Smullyan, R. (1982). The Lady or The Tiger? Times Book.
- Smullyan, R. (1987). Forever Undecided: A Puzzle Guide to Gödel. Alfred Knopf.
- Smullyan, R. (1992). Gödel’s Incompleteness Theorems. Oxford University Press.
- Smullyan, R. (2009). Logical Labyrinths. A. K. Peters.
- Smullyan, R. (2014) A Beginner’s Guide to Mathematical Logic. Dover Publications.
- Tieszen, R. (2017) Simply Gödel. Simply Charly.
- von Neumann, J. (1951). Tribute to Dr. Gödel. In J. Bulloff, T. Holyoke, & S. Hahn (Eds.), Foundations of Mathematics: Symposium Papers Commemorating the Sixtieth Birthday of Kurt Gödel (pp. ix-x). Springer-Verlag.
- Wang, H. (1996). A Logical Journey. MIT Press.
