Gödel's Incompleteness For Dummies
An incomplete sketch of the famous Incompleteness Theorems
In this post I will try to make a post along the line of:
Gödel’s Incompleteness theorems For Dummies
For Dummies is an extensive series of instructional reference books that strive to present non-intimidating guides for readers new to the various topics covered. The series has been a worldwide success, with editions in numerous languages.
In 1987, new technologies were popping up all over the place. But computer manuals were dull and difficult to understand. A frustrated customer in a computer store, who knew nothing about computers, was looking for a simple, basic book about the difficult DOS operating system. “Something,” he suggested, “like DOS for dummies.” A publisher knew the man’s frustration was shared by many other computer users, and they set out to do something about it. Thus, the For Dummies phenomenon began.
From the start, For Dummies was a simple, yet powerful concept: Relate to the anxiety and frustration that people feel about technology by poking fun at it with books that are insightful and educational and make difficult material interesting and easy. Add a strong dose of personality, a dash of comic relief with entertaining cartoons, and — voilá — you have a For Dummies book.
In this post I hope to employ a similar strategy to explain Gödel Incompleteness theorems to a broad audience assuming knowledge about elementary arithmetic. The history of Gödel’s Incompleteness Theorems centers on Kurt Gödel’s 1931 publication, which shattered the mathematical ambition of finding a single, complete, and consistent set of axioms for all of mathematics. Published when he was 25, Gödel’s theorems proved that for any consistent formal system strong enough to include basic arithmetic, there will always be true statements that cannot be proven within the system itself. This was a major turning point in logic, as it demonstrated the fundamental limits of formal axiomatic systems and showed that a system cannot prove its own consistency.
David Hilbert, a stalwart mathematician of all time, was initially red faced angry at Gödel’s incompleteness theorems because they demonstrated the impossibility of his program for a complete and consistent system of mathematics. However, as a mathematician, he eventually accepted the validity of Gödel’s proofs and even began to constructively adapt his own work in response.
So get ready for some heavy story telling gently unveiled in the language of something basic that we all understand:
Arithmetic
What is Arithmetic?
Arithmetic is the fundamental branch of mathematics that studies numbers and their operations. In particular, it deals with numerical calculations using the arithmetic operations of addition, subtraction, multiplication, and division. In a wider sense, it also includes exponentiation, extraction of roots, and logarithm. The term arithmetic has its root in the Latin term arithmetica which derives from the Ancient Greek words ἀριθμός (arithmos), meaning ‘number’, and ἀριθμητική τέχνη (arithmetike tekhne), meaning ‘the art of counting’.
Axiomatic foundations of arithmetic try to provide a small set of laws, called axioms, from which all fundamental properties of and operations on numbers can be derived. They constitute logically consistent and systematic frameworks that can be used to formulate mathematical proofs in a rigorous manner.
0 is a natural number.
For every natural number, there is a successor, which is also a natural number.
The successors of two different natural numbers are never identical.
0 is not the successor of a natural number.
If a set contains 0 and every successor then it contains every natural number.
Looks simple right?
You cannot be more wrong - read more to find out.
Language
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed forms, and may also be conveyed through writing. Human language is characterized by its cultural and historical diversity, with significant variations observed between cultures and across time. Human languages possess the properties of productivity and displacement, which enable the creation of an infinite number of sentences, and the ability to refer to objects, events, and ideas that are not immediately present in the discourse. The use of human language relies on social convention and is acquired through learning.
Estimates of the number of human languages in the world vary between 5,000 and 7,000. Precise estimates depend on an arbitrary distinction (dichotomy) established between languages and dialects. Natural languages are spoken, signed, or both; however, any language can be encoded into secondary media using auditory, visual, or tactile stimuli – for example, writing, whistling, signing, or braille. In other words, human language is modality-independent, but written or signed language is the way to inscribe or encode the natural human speech or gestures.
Depending on philosophical perspectives regarding the definition of language and meaning, when used as a general concept, “language” may refer to the cognitive ability to learn and use systems of complex communication, or to describe the set of rules that makes up these systems, or the set of utterances that can be produced from those rules. All languages rely on the process of semiosis to relate signs to particular meanings. Oral, manual and tactile languages contain a phonological system that governs how symbols are used to form sequences known as words or morphemes, and a syntactic system that governs how words and morphemes are combined to form phrases and utterances.
Enough of Theory - let’s take an example.
We are all very familiar with English. We know the letters (a-z, A-Z, 0-9, …). We form words by combining letters. We know the rules of English Language like Capitalization:
Capitalization is writing a word with its first letter as a capital letter (uppercase letter) and the remaining letters in lower case, in writing systems with a case distinction. The term also may refer to the choice of the casing applied to text.
We also know rules like Acronyms":
An acronym is an abbreviation formed using the initial letters of a multi-word name or phrase. Acronyms are often spelled with the initial letter of each word in all caps with no punctuation. Here is an example statement:
The GDP of USA is 29.18 trillion USD (2024)
Spot three acronyms in the above sentence?
GDP - Gross Domestic Product
USA - United States of America
USD - United States Dollar
Metalanguage
In logic and linguistics, a metalanguage is a language used to describe another language, often called the object language. Expressions in a metalanguage are often distinguished from those in the object language by the use of italics, quotation marks, or writing on a separate line. The structure of sentences and phrases in a metalanguage can be described by a metasyntax. For example, to say that the word “noun” can be used as a noun in a sentence, one could write “noun” is a <noun>.
Let’s take an interesting example:
TLA
A three-letter acronym (TLA), or three-letter abbreviation is, as the phrase suggests, an abbreviation consisting of three letters. The term has a special status among abbreviations and to some is considered humorous since the term TLA is itself a three-letter acronym; it is an autological word. An autological word (or homological word)expresses a property that it also possesses. For example, the word “word” is a word, the word “English” is (in) English, the word “writable” is writable, and the word “pentasyllabic“ has five syllables.
Suppose you come across an English statement:
“TLA” is a TLA
How do you make sense of the above statement? Here are the sense making steps:
You remember the Language rule that Acronyms are in ALL CAPS
Then you remember that Metalanguage syntax rule of enclosing autological words in quotes such as “TLA”
You consult Wikipedia to look up TLA acronym for Three Letter Acronym
Then you understand that TLA acronym is asserting about a property of itself, namely:
The acronym named “TLA” has three lettersIf you wish you can expand the original sentence for clarity:
TLA stands as an acronym for Three Letter Acronym and it so happens that TLA itself is a three letter acronym (TLA)You also understand that the following statement about Four Letter Acronym (FLA) is True:
”FLA” is a TLA
and the following statement is False:
”FLA” is a FLA
The fun in the above exercise that we were reasoning about properties of English Language using English Language itself. We were engaged in meta linguistic analysis of English using the same language which is being analyzed.
If you want to extend the fun define a new acronym:
NFLA : Not Four Letter Acronym
then determine True or False for the following statements:
“NFLA” is a NFLA
“NFLA” is not a FLA
“NFLA” is not a NFLA
Metamatheatics
Mathematics is carried out in a Formal Language. The language of mathematics or mathematical language is an extension of the natural language (for example English) that is used in mathematics and in science for expressing results (scientific laws, theorems, proofs, logical deductions, etc.) with concision, precision and unambiguity. The consequence of these features is that a mathematical text is generally not understandable without some prerequisite knowledge. For example, the sentence “a free module is a module that has a basis“ is perfectly correct, although it appears only as a grammatically correct nonsense, when one does not know the definitions of basis, module, and free module. The sentence is from the mathematical field of Abstract Algebra:
A free abelian group is precisely a free module over the ring Z of integers
Due to precise nature of Language of Mathematics, it is now becoming possible for Artificial Intelligence to be of effective aid to Mathematicians, as described in the following video:
November 18: (Re)imagining mathematics in a world of reasoning machines
In the coming decades, developments in automated reasoning will likely transform the way that research mathematics is conceptualized and carried out. I will discuss some ways we might think about this. The talk will *not* be about current or potential abilities of computers to do mathematics – rather I will look at topics such as the history of automation and mathematics, and related philosophical questions.
But we are deviating too far from this section topic:
Metamathematics
Due to precise nature of Mathematical Language, we can use the Language of Mathematics itself to argue and deduce about properties of Mathematics.
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories. Emphasis on metamathematics (and perhaps the creation of the term itself) owes itself to David Hilbert‘s attempt to secure the foundations of mathematics in the early part of the 20th century. Metamathematics provides “a rigorous mathematical technique for investigating a great variety of foundation problems for mathematics and logic“. An important feature of metamathematics is its emphasis on differentiating between reasoning from inside a system and from outside a system. An informal illustration of this is categorizing the proposition “2+2=4” as belonging to mathematics while categorizing the proposition “’2+2=4’ is valid” as belonging to metamathematics.
Serious metamathematical reflection began with the work of Gottlob Frege, especially his Begriffsschrift, published in 1879.
David Hilbert was the first to invoke the term “metamathematics” with regularity (see Hilbert’s program), in the early 20th century. In his hands, it meant something akin to contemporary proof theory, in which finitary methods are used to study various axiomatized mathematical theorems.
At long last, Gödel enters the scene:
Gödel’s incompleteness theorems are two theorems of mathematical logic that establish inherent limitations of all but the most trivial axiomatic systems capable of doing arithmetic. The theorems, proven by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The two results are widely, but not universally, interpreted as showing that Hilbert’s program to find a complete and consistent set of axioms for all mathematics is impossible, giving a negative answer to Hilbert’s second problem.
The first incompleteness theorem states that no consistent system of axioms whose theorems can be listed by an “effective procedure“ (e.g., a computer program, but it could be any sort of algorithm) is capable of proving all truths about the relations of the natural numbers (arithmetic). For any such system, there will always be statements about the natural numbers that are true, but that are unprovable within the system. The second incompleteness theorem, an extension of the first, shows that such a system cannot demonstrate its own consistency.
Gödel How?
Remember the sentences:
True : “TLA” is a TLA
False: “FLA” is a FLA
The interesting property of these English sentences is they are Self Asserting.
The first sentence (True) talks about TLA in a sentence which is all about TLA
The second sentence (false) talks about FLA in a sentence which is all about FLA
Gödel used the language of Arithmetic to construct a sentence:
I am not Provable
The crucial words in the above sentence is:
I
Provable
Both are words of Metamathematics:
Gödel used a numbering system so that a mathematical sentence can unambiguously refer to itself (I) - since each mathematical statement has an unique number assigned to it
A mathematical proof is a concept of Metamathematics
The property of being Probavle (or not Provable) is also a concept of Metamathematics
So here we are, we are left with a stunning sentence:
I am not Provable
Compare this sentence to the sentence:
“TLA” is a TLA
What are our options at this point, on evaluating this earth shattering claim:
The claim is False
But it cannot be! The sentence is constructed precisely. We can see by way of construction that the sentence cannot be False. This is just as same as the sentence
”TLA” is a TLAThe claim is True
Finally we arrive at the Gödel Incompleteness:
There is True Statement precisely constructed using Language of Arithmetic which asserts that the statement is Not Provable!!
This completes the story of Gödel’s first incompleteness theorem.
Gödel’s second incompleteness theorem states that a consistent formal system, such as a system of mathematics, cannot prove its own consistency. In simpler terms, if a system is sound and doesn’t contain a contradiction, it cannot use its own rules and axioms to logically prove that it is, in fact, sound and contradiction-free.
Think about this for a moment:
A proof of Consistency requires checking all proofs possible in that system
Gödel’s first incompleteness theorem just demonstrated at least one Unprovable Statement
This realization implies Gödel’s second incompleteness theorem
Tribute
If you are thinking that my post is a tribute to tremendous Gödel - thanks but no thanks. I am not qualified to be within 100 miles of Gödel thought sphere. In this post I am paying tribute to Erin Carmody, faculty at Sarah Lawrence College - a prestigious, residential, coeducational liberal arts college.
Dr. Carmody is BS, University of Nebraska. MA, University of Kansas. PhD, City University of New York. Special interests in set theory, art, and writing. Special interests in set theory focus on the interactions between large cardinals and forcing, a tool that was developed by Paul Cohen in the 1960s. Set theory was created by Georg Cantor in the 1860s, which has turned into an amazing galaxy of mathematical universes. Large cardinals are infinite numbers that are so large that we cannot prove their existence. Set theory is also the foundation of mathematics and about the foundation of mathematics. Special interests in art include portraits of great writers, mathematicians, and artists. Writing special interests include, so far, two self published books: The first is about a world without the prime number 2 and the consequences; it is also about the philosophy of set theory. The second is a book of portraits, poems, and drawings, many of which are inspired by set theory. SLC, 2021–
She is developing a tremendously interesting book:
The Set Theory Guide for Artists
Subscribe to get approximately monthly chapters from The Set Theory Guide for Artists. Paid subscribers get video podcast readings of the book (exclusively for paid subscribers). Your subscription makes it possible to keep the written book free, especially for students. Founding members are the first to get a book once it is published.
It also goes without mention that I am fan of my daughter:
Sherry Sarkar
I’m a sixth and final year mathematics PhD student in the Algorithms, Combinatorics, Optimization program at Carnegie Mellon University. I’m fortunate enough to be advised by Dr. Anupam Gupta.
I’ve also had the pleasure of doing a lot of research outside of CMU – last summer, I worked with the Algorithms Group at Microsoft Research, and in the fall of 2022, I was part of the Simons Theory of Computering “Data Driven Decision Properties” program.
I graduated with my Bachelor’s degree in Computer Science at Georgia Institute of Technology in 2020. I am interested in all things discrete optimization. Some of my favorite problems include online bipartite matching (and its generalization to matroid intersection), and network design. I like to study problems in both a full information (offline) and parital information setting (online), and my current research direction is to understand what flexibility applications might lend to online problems to give us offline performance guarantees.
I also really enjoy mentoring and teaching. I’ve teaching at the undergraduate level for over eight years; I’ve also taught in high school math circles as well as done outreach and tutoring volunteer work for elemetary students. For mentoring, I’ve been particularly involved in the Polymath Jr Research Program; in 2023, I led my own research group producing surveys in theory CS.
Outside of work, I am an avid foodie, I foster cats, and I rock climb!