Gödel's Theorems from the History to the Demonstrations
One of the greatest discoveries of all times explained in a bunch of simple words
Hello, Hypers!
The twentieth century was full of amazing scientific discoveries. Enumerating them here would be impossible. Just a few examples:
Einstein’s General Relativity Theory
Heisenberg’s Uncertainty Principle
Gödel’s Incompleteness Theorems
From the three discoveries above, I’m sure you have heard of the first one. The second one is also very famous, and you have heard the name Heisenberg for sure (at least in Breaking Bad). But the third is by far the least known. Well, as you can imagine (mainly from the title of this post), today in Under the Hype, we’ll make justice and talk about the awesomeness of Gödel’s Incompleteness Theorems.
I’m in love with these results because of two reasons:
To understand them you need to take a journey through the entire history of Math.
They probably are the starting point of Computer Science.
The following history is a compilation of three Twitter threads I wrote some years ago. Of course, I made some modifications to make the content more suitable for a Substack post.
Note: Twitter was a nice social media app where you could publish your Substack’s links. Now it is known as X.
The history
The study of math as a science started in ancient Greece. Although math was applied earlier in other ancient civilizations, philosophers like Tales were the first that study mathematical abstractions like shapes, without asking for the practical purpose of that study. Math started to have its very own questions that only could be answered inside Math itself. Math became a science.
Pythagoreans were a philosophical group that defended that the essence of the universe was numbers. However, their theory was based on the hypothesis that all numbers could be expressed as a fraction of two integer numbers.
It seemed an acceptable supposition back then until a member of the Pythagorean school discovered some numbers that cannot be expressed that way. For example sqrt(2)
and sqrt(5)
. Those are presumably the first known irrational numbers. All the Pythagorean theory was reduced to ashes. That was the first big crisis of math.
What was wrong with the Pythagorean theory? They assumed as true a proposition that is false inside that theory. You can prove some numbers cannot be expressed as a fraction using just the theorems, elements, and operations of the theory.
Greeks realized they needed to change the way math was developed so far. And then, Euclid wrote one of the most important books in the history of science: "The Elements". Almost all the geometry we learned until high school was written by Euclid 2,500 years earlier. But the best part was the method Euclid used to formulate his geometry.
"The Elements" showed the first example of an axiomatic theory. An axiomatic theory is built on top of very simple propositions that are assumed as true (axioms). Every other proposition needs to be demonstrated from the axioms by following a set of rules that state how we can go from proposition A to proposition B.
The process of going from the set of axioms to some proposition A is called demonstration. When we demonstrate proposition A we say that A is a theorem in our theory. Let's see how the history continues.
Euclid built his geometry on top of five axioms. The first four of them seemed pretty simple but the fifth was trickier. It's well known that Euclid himself tried to demonstrate the fifth axiom from the other four without success.
More than 2,000 years after the first publication of "The Elements", mathematicians were still figuring out how to remove the fifth axiom. The result of those studies unveiled an astonishing fact: Euclid just defined one of the many possible geometries (🤯). If you change the fifth axiom a little bit, you can end up with a perfectly defined (although very crazy) geometry.
Note: The General Theory of Relativity demonstrated that the geometry of our universe is non-Euclidean (it's one of the new crazy ones).
But this was a big problem! Mathematicians thought the fifth axiom would be eventually demonstrated and they built the entire Math building on top of the robust and unique Euclidian geometry. This was the second deep crisis in Math. We need to rebuild the whole thing again!
But what do we mean by building the entire Math on top of something?
It means defining some axioms in a way that any mathematical proposition can be either proved or refuted by a demonstration process. Many of the greatest mathematicians of all time worked hard on that problem. And then, in 1931, a 25-year-old man destroyed that intention. Kurt Gödel proved that such a system was impossible to build. He proved that there are true propositions that cannot be proved in some theories. He proved some things cannot be proved! 🤯🤯🤯.
The Theorems
First things first. Let's talk about some important concepts.
We saw what an axiomatic theory is. Well, there are two properties that you'd like to have if you were an axiomatic theory:
Consistency and Completeness
Consistency: A consistent theory is one in which a proposition can be either true or false but not both. In other words, a theory without contradictions.
Inconsistent theories are useless because you can prove anything from them... Yeah, anything. There's a funny story of Bertrand Russell proving that if 2+2=5 then he was the Pope 😆.
Completeness: A complete theory is one in which all the true propositions are provable inside the theory. The doctoral thesis of Gödel was the demonstration of the completeness of first-order logic (23 yo).
Now we can continue with the history.
So, mathematicians were trying to build math on top of other ground different from geometry. They picked number theory (arithmetic, natural numbers) as the new foundations. Natural numbers were axiomatized some years before. To give you an idea of the magnitude of Gödel discovery I'm going to mention some of the mathematicians trying to rebuild math:
David Hilbert💪
Bertrand Russel💥
Wilhelm Ackermann❗
John Von Neuman🔥
They were trying to prove that number theory was both Consistent and Complete. That way, Math would be safe. The entire Math would be contradictions-free and everything could be proven. It seemed to be a matter of time before the proof arrived. Some sub-theories of arithmetic were proven to be both consistent and complete. Gödel himself was working on that but he realized this:
Theorem 1: About incompleteness.
For any axiomatic theory that includes a certain part of arithmetic, if it is consistent, then it is incomplete
This means that all theories including the number theory, contain true propositions that we'll never be able to prove inside that theory!
All the work of some of the greatest mathematicians of all time was in vain. For example, Jon Von Neuman never worked again in Logic after this. But there is another theorem.
Theorem 2: About consistency.
For any consistent theory that contains a certain part of arithmetic, the consistency of the theory is not provable.
Precisely one of those true but not provable propositions is the consistency of the theory itself! So, 0 out of 2. No consistency and no completeness. Math can't be built that way. We have to live with that. There are true propositions out there we'll never prove😔. End of story.
Misconceptions
Not so fast. Let's talk about some misconceptions generated from the theorems. First I'd like you to note that both theorems say "with a certain amount of arithmetic".
We will be talking about that amount in the next section. For now, just suppose a theory containing the entire arithmetic.
Misconception number one:
Gödel said that for any sufficiently complex theory if it is consistent, then it is incomplete
❌ There is this idea that anything more complex than number theory has the conditions to apply Gödel's incompleteness theorems. Real numbers are a complete theory. And real numbers are at least as complex as natural numbers. It is not about complexity. It is about how natural numbers are defined. That definition has the "poison".
Misconception number two:
Truth is unreachable for science
❌ OK, some true propositions can't be proven in some theories. But maybe there are other alternative theories. Furthermore, experiments and observations are other methods to discover the truth about our universe.
Misconception number three:
There is no philosophic system that can explain the universe
❌ The explanation of the universe doesn't have to do with natural numbers necessarily. And Gödel's theorems don't apply when there is no arithmetic in the theory.
Of course, there are lots more misconceptions about Gödel's results. But I'll stop here 🥵. What about some demonstrations?
Sketch of the demonstrations
Let's try to understand how Gödel was able to prove that there are no provable propositions and let's do it as smoothly as we can 🙄.
By the end, we'll have proved one of the most mind-blowing results ever.
From now on, we denote with T an axiomatic theory that contains the number theory (theory of natural numbers).
The first Gödel's theorem states that if T is consistent, then it is incomplete.
It means that there are true propositions in T that can't be proven inside T.
Think about this proposition: "This proposition is not a theorem of T", or equivalently, "This proposition is not provable in T".
If the proposition was true, then it was a true but unprovable proposition in T. Problem solved. End of the thread.
WAIT ⛔️
Well, there is a little problem with that last proposition. First of all, we don’t know if it is true. Also, it talks about the theory T, but it is not a proposition in T. There's a difference between talking about something and being part of it. Let's see how Gödel did it.
He created a code for every proposition and proof in T, in a way that every one of those propositions and proofs had its own unique natural number that identified it. That way, we can talk about the theory from the language of numbers. That's what we call Gödel numeration. But remember that T contains the number theory. And that's the fact Gödel took advantage of.
Expressing propositions with numbers is a way to talk about T from within T itself. But how?
By saying: "N is not the code of any theorem in T", we are talking about T. But being the code of a theorem in T is an arithmetic property, and T contains the arithmetic.
So now we can state the proposition: "The code of this proposition is not the code of any theorem in T".
But that previous proposition can't still be formulated in T. That's a non-valid syntax. We can’t express this self-reference using the language of numbers and the theory. We need to achieve that more subtly.
For that, we'll use the method proposed by the American philosopher Willard Van Orman Quin. This method is called "quinning". Let's see the following statement:
"yields a proposition with property P when appended to its own quotation." yields a proposition with property P when appended to its own quotation.
We can substitute the quotation for any other sentence. But when using the same sentence the statement starts to talk about itself!
Note: Gödel originally proposed another method but it is trickier.
Let's denote the previous sentence with the letter G. So, if G is true then G has the property P and if G has the property P, then G is true. Let's do the last twist!
Let's make P = "its code is not the code of any theorem in T".
"yields a proposition whose code is not the code of any theorem in T when appended to its own quotation." yields a proposition whose code is not the code of any theorem in T when appended to its own quotation.
Now if G is false, then it is not provable, and that makes P true, and that makes G also true. So, T would be inconsistent. If T is consistent, then G is true, then P is also true, and G is not provable!
We did it!
G is true but not provable in T!
What about the second theorem?
"The consistency of T is not provable in T"
That's a "direct" result from the previous demonstration!
If T is consistent, then G is true. And that's a demonstration of G, and G is not provable!
What we know is that if T is consistent then G is true but not provable. If the consistency of T was provable, then we would also have a proof for G. That’s why the consistency is not provable either.
And that's it. We proved the Gödel theorems!
Of course, these demonstrations are not too accurate but they comprise the main ideas behind those mind-blowing results.
And this is the end of the post! I hope you have enjoyed it. If you need to re-read some parts don’t worry, I had to do it too when writing this. Please, don’t hesitate to ask any doubts about this or any other post. Thank you very much for reading Under the Hype for another week.
See you next Tuesday!
Do you think Gödel points to a deeper nature of reality, not just mathematically speaking? Sure seems like it, perhaps reinforcing quantum uncertainty, for instance.