Search for a command to run...
One of the greatest discoveries of all times explained in a bunch of simple words
Computer Scientist. Researching on Artificial Intelligence and working as a Software Engineer. Cuban based in Spain.
No comments yet. Be the first to comment.
A series on how to predict the future
A series on how to predict the future
The field of Predictive Analytics is everywhere these days. We can hear about it in several and different areas like medicine, businesses, industries, and so on. But what exactly Predictive Analytics is? How can some algorithms predict the future, an...
Greedy algorithms try to find the optimal solution by taking the best available choice at every step. For example, you can greedily approach your life. You can always take the path that maximizes your happiness today. But that doesn't mean you'll be...
This is a collection of three threads published on Twitter, about Goedel's Theorems.
Today I want to start a potentially little series of threads about one of my biggest passions: Gödel's theorems. One of the greatest discoveries of all time that I'm sure will blow your mind! I'll structure the series as follows.
First: The history that preceded the theorems
Then: The theorems. Explanation and some common misconceptions
And finally: Shallow overview of the demonstrations.
Let's start with the history that preceded Gödel's results. It is pretty much the history of math so let's see if we can comprise it in a thread.
The study of math as science started in ancient Greece. Although math was applied earlier in other ancient civilizations, philosophers like Tales were the first that studied 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 philosophy group that defended that the essence of the universe was numbers.
But 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 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. So 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 of the history of science: "The Elements". Almost all the geometry we learned until high school was written by Euclid 2500 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 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.
More than 2000 years after the first publication of "The Elements", mathematicians were still figuring out how to remove the fifth axiom by demonstrating it. 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
As a side 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 could be demonstrated someday and they built the entire Math building on top of the robust and unique Euclidian geometry. This meant the second deep crisis of Math. We need to rebuild the whole thing again!
But what do we mean by building the entire Math on top of something?
It is 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 yo 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! 🤯🤯🤯
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 the first-order logic (with 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. The main reason: it was 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:
They were trying to prove that the 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. Actually, 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 that include 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 times was in vain. Jon Von Neuman never worked again in Logic.
But for those who have some hope in their hearts. I remind you that there are two theorems.
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.
Now, 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 arithmetic.
Misconception number one:
Gödel said: for any sufficiently complex theory if it is consistent, then it is incomplete
❌ There is this idea of anything more complex than number theory has the conditions to apply Gödel's incompleteness theorem. Real numbers is 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:
The truth is unreachable for scientists
❌ 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 bout some demonstrations?
Let's try to understand how Gödel was able to prove that there are not 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 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.
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. 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 Goedel 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 and unique natural number that identifies 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. A proposition can't talk about itself in that way.
We need to achieve that in a more subtle way.
For that, we'll use the method proposed by Quine that 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!
Gödel proposed another method but it is trickier.
Let's denote the previous sentence with th 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". 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. But (and precisely because of the previous sentence), the consistency of T is not provable either.
And that's it. We proved the Goedel theorems!
Of course, these demonstrations are not too accurate but they comprise the main ideas behind those mind-blowing results.
So, this is the end of the series😢. Gödel's theorems started a revolution. A revolution that resulted in the birth of Computer Science. But that's another history. Maybe I'll write my own version of that history in the form of threads in the future😉.
