Gödel’s First Incompleteness Theorem
You probably think that math is a purely logical, 100% consistent, black and white subject. Everything in math is either right or wrong: 1 +1 has only one correct answer, the solutions of 5x² + 6x + 1 = 0 are either 1 and -2.2 or they are not, and the Goldbach Conjecture can be only proven either true or false. For almost two thousand years, since the Ancient Greeks, this is the way math was practiced, by noble scholars and the mass population alike. It was believed by all the great mathematicians, from Aristotle to Newton, that every true statement has a proof. Even David Hilbert himself, while publishing his famous 23 greatest unsolved problems, stated, “Every mathematical problem should have a solution.” The proof may be hard to find, such as how the proof of Fermat’s Last Theorem took 350 years, but regardless of how hard a problem is, a solution always exists in black and white logic. It was believed that anything that we don’t know in the realm of mathematics, we don’t know because of our human incapability to solve the problem.
Then came the continuum hypothesis, proposed by German mathematician Georg Cantor in 1878. Just like many math problems before it, the CH had no clear solution. Many mathematicians devoted hundreds of hours to this problem, yet no one was able to either prove or disprove the hypothesis. To show you how big of a deal this problem is, the continuum hypothesis was listed first on Hilbert’s greatest unsolved problems of the 19th century.
The continuum hypothesis states, “There is no set whose cardinality is strictly between that of the integers and the real numbers.” (Don’t worry, I’ll explain what this means later.)
In 1940, Austrian mathematician Kurt Gödel demonstrated that the continuum hypothesis cannot be proven false. Then, in the 1960s, U.S. mathematician Paul Cohen showed that the continuum hypothesis cannot be proven true. Taken together, this meant that the continuum hypothesis cannot be answered??¿¿
This stirred up some unease in the within the mathematical community. Math was practiced as a subject with a clear distinction between right and wrong for centuries, so how come this new problem pops up as unsolvable?
It turns out, the continuum hypothesis isn’t the only problem that cannot be proven neither true or false. In fact, according to the first incompleteness theorem, there will always be some unanswerable questions in any field of math. But in order to understand why the existence of an unprovable concept is possible, first we have to zoom way out, go back to the fourth century BC, and dig deep into the essence of mathematics.
The Essence of Math
The building blocks of mathematics are not the digits of numbers, not equations or formulas, and not even the four basic arithmetic operations, although your school’s math classes may portray it that way. Instead, the building blocks of math are axioms.
An axiom (or postulate) is an assumption that is self-explanatory and widely accepted as true, without requiring a proof.
Some examples of axioms:
- A line can be drawn from a point to any other point.
- The probability of an event is a real number greater than or equal to 0.
- If set X and set Y have the same elements, then X=Y.
- A + B = B + A
As you can see, all of these axioms are pretty self explanatory.
How do axioms relate to math? Take any branch of math, geometry, for example. You may know that Euclid is father of geometry, because he created geometry. But do you know why? You may ask, how does one possibly create a branch of math?
Crash Course: How to create your own field of math
Fundamentally, math is all about solving questions. A question that is solved and proven true then becomes a theorem. Each branch of math is made up of theorems.
To create a branch of math, here’s what you got to do: First, establish a few independent axioms. Then, construct proofs for theorems based on the axioms. Keep trying to prove more and more theorems using logical deductions from axioms and other theorems you proved from the axioms.
Basically, axioms are the starting point. Axioms are the foundation upon which theorems are built. All theorems are derived from either axioms or other theorems (which themselves are derived from axioms).
After Euclid defined these 5 axioms, he and his scholars began expanding geometry, for example, we can conclude the existence of perpendicular lines from axioms 1, 2, and 5. These logical deductions are then turned into proofs for theorems, such the Perpendicular Bisector Theorem. Finally, these axioms and their derived theorems are applied to describe geometry of how lines and shapes interact in our physical world. This is how a new branch of mathematics is born.
Although these axioms and theorems worked well in describing the geometry of our world, Euclid wasn’t content with his 5th axiom. Remember the definition of an axiom from before?
“An axiom is self-explanatory.”
Now look at these five axioms again.
The wording of the fifth axiom is so complex that it seems like a theorem rather than a self-evident axiom. In fact, the number of words in the fifth axiom is greater than the word count of the other four combined.
Euclid was not happy with his fifth axiom. After laying the foundation for geometry, he spent a lot of time trying to prove the 5th axiom from the other four. A year passed. Then ten years. No matter how hard he tried, he couldn’t find the proof. After Euclid died, many other mathematicians spent countless hours trying to do the same, all with no avail.
Different Types of Geometry
It wasn’t until a full fourteen centuries later did anyone make a breakthrough. However, this discovery was not proving the fifth postulate, as you’d expect. Instead, in 1829, Russian mathematician Nikolai Lobachevsky proved that the parallel postulate doesn’t have to be true!
What Lobachevsky found was that if you assume the parallel postulate is true, then you get one set of geometry with one set of rules and theorems, that accurately describe one type of world. If you assume the opposite, you get a different type of geometry, with different rules and theorems, and has applications in describing a different type of space. This was really exciting.
The parallel postulate states that given a point and a line, there is only one line through that point parallel to the given line. Lobachevsky found out that if you assumed that given a point and a line, there is more than one line through that point parallel to the given line, you get a different type of geometry where space curves inward like a Pringles chip, the angles of a triangle add up to less than 180 degrees, and two lines can intersect at more than one point. He called this new geometry Hyperbolic Geometry.
Around the same time, Georg Riemann made a similar discovery as Lobachevsky. However, instead of assuming there is more than one line, he assumed that there were no such thing as parallel lines. If he replaced Euclid’s fifth postulate with his, while keeping the other four, we’d get another, different branch of geometry. In this world, space is curved outwards like a sphere, the angles of a triangle add up to more than 180 degrees, and all lines have the same finite length π. Today, Riemann’s branch of geometry is called Elliptical Geometry. Euclid’s original geometry is called Euclidean Plane Geometry or just Euclidean Geometry.
This was a groundbreaking discovery for the entire realm of mathematics — the discovery that something as simple as parallel lines doesn’t have to be true caused some unease. This new uncertainty violated the principles that everything has to be either true or false, principles that were built up over centuries.
Gödel’s Breakthrough
In 1931, 30 years after Hilbert published his 23 problems, Kurt Gödel proved his first incompleteness theorem, which reflects this idea of ambiguity. Put into the words of the Stanford Encyclopedia of Philosophy, this theorem states, In any consistent formal system F within which a certain amount of arithmetic can be carried out, there are statements of the language of F which can neither be proved nor disproved in F. In other words, for any system of axioms, there are concepts which can be neither proved nor disproved by those axioms. And since math is fundamentally constructed on axioms, there will always be problems that can never be proven neither true or false. No field of mathematics is — and can possibly be — complete.
Godel’s first incompleteness theorem states: For any system of axioms, there are concepts which can be neither proved nor disproved by those axioms.
When Gödel first published this theorem, he was faced with a lot of criticism from the scientific and mathematical community. Many scholars did not appreciate his work, because it showed that the way math was practiced for centuries was incorrect. Because math was respected and known for its pure logic and consistency, there should be a clear border between the correct and and incorrect. Gödel’s theorem forced mathematicians to contend with aspects of their profession that they’d prefer not to acknowledge or examine.
In every field of math, there will always be problems that can never be proven neither true or false.
Gödel was actually quite upset about his own discovery, as Hilbert was one of Godel’s biggest heros. He had originally set out to confirm Hilbert’s opinion that “every mathematical problem should have a solution,” and instead, he destroyed it.
Back to the Continuum Hypothesis
The continuum hypothesis states, “There is no set whose cardinality is strictly between that of the integers and the real numbers.”
Let’s break down what this means, bit by bit.
There is no set whose cardinality is strictly between that of the integers and the real numbers.
A set is any collection of objects. Some examples of sets:
There is no set whose cardinality is strictly between that of the integers and the real numbers.
For this part, you have to understand, what exactly does it mean for two sets have the same cardinality?
Cardinality refers to the number of elements in a set. For two sets to be equivalent, a perfect one-to-one match must be able to be established between the elements of the two sets, with no leftovers in either set. The two sets don’t have to have the same elements, but each element from one set must be able to be paired with one from the other set. This may sound abstract and confusing, so here’s an example to illustrate the topic:
To prove that these two sets have the same cardinality, we must establish a one-to-one match between the two sets:
As you can see, the elements of Set A and Set B can be paired up with each other perfectly, with no leftovers in either set. This is what it means for two sets to have the same cardinality.
There is no set whose cardinality is strictly between that of the integers and the real numbers.
The continuum hypothesis mentions two distinct sets, the set of integers and the set of real numbers. The set of integers is the infinity of all the whole numbers and their opposites.
Now, what is the cardinality of this set? Obviously, there are an infinite amount of integers. The countable infinity of all integers is the smallest value of infinity, called aleph-null, written with the symbol ℵ₀. Learn more about different infinities.
The continuum hypothesis also mentions another set — the set of real numbers. This includes all decimals, irrational numbers, transcendental numbers, and every other number on the 2D number line. What is the cardinality of this set? Just like integers, the amount of real numbers is an infinity, but is it also aleph-null? Take a guess.
It turns out, Cantor proved that the cardinality of the set of real numbers does not equal to aleph-null, or in other words, a one-to-one match cannot be established between the set of integers and the set of real numbers. To illustrate this, suppose you wrote a list, matching up each integer with a real number between 0 and 1. For example:
No matter how you designed this list, it is impossible to match every single real number with an integer. No matter what your list was, I’d always be able to give you a real number that is not on your list.
All I have to do is this:
Take the first digit of your first number. I will design my number so that the first digit of my number is different from the first digit of your first number.
Then, I’ll make the second digit of my number different from the second digit of your number.
Repeat with all the numbers.
Now, I have made a number that is not on your list. How do I know for sure? Say… could my number be the same as your 213rd number? Well, the 213rd digit of my number is different from the 213rd digit of your 213rd number. I’ve designed my number so that it cannot possibly be on your list.
As well, I can repeat this process an infinite amount of times to generate an infinite amount of numbers not on your list. Crazy, eh?
Your list goes on forever. You have an aleph-null amount of real numbers on your list, yet it’s not complete. The only possible explanation is that the amount of real numbers is greater than the amount of integers, that some infinities are greater than others. Still confused? Watch this.
Going back to earlier, the definition of two sets to have the same cardinality is that a perfect one-to-one match can be established between the two sets, with no leftovers in each. Given this definition, the set of integers and the set of real numbers do not have the same cardinality.
Now that we understand each part of the continuum hypothesis, we can revisit the whole thing:
There is no set whose cardinality is strictly between that of the integers and the real numbers.
What this means, essentially, is that there isn’t an infinity whose value is between the cardinality of the set of integers and the set of real numbers. Or you can put it as, if aleph-null is the smallest infinity, then aleph-one is the 2nd smallest infinity, and the continuum hypothesis states that the cardinality of the set of real numbers equals to aleph-one.
The continuum hypothesis belongs to a branch of math called Zermelo–Fraenkel set theory. Using what we learned about the essence of math, we know that all fields of math are constructed on axioms. In set theory, there happens to be 8 axioms:
Remember Paul Cohen from the beginning? The groundbreaking, Field’s-medal-winning discovery that he made was that the continuum hypothesis is independent of Zermelo–Fraenkel set theory, that the continuum hypothesis can neither be proved correct or incorrect by the 8 existing axioms. As well, just like the Euclid’s parallel postulate, if we assume the CH is true, we get one branch of math, and if we assume the CH is false, we get another branch of math. The continuum hypothesis is another example that illustrates the incompleteness theorem.
Well then, you might ask, why can’t you add the continuum hypothesis as an axiom to make set theory “complete?” The thing is, you can add it. You can add as many axioms as you like. What Gödel’s first incompleteness theorem states is that there will still always be unsolvable questions, even after you’ve added a hundred axioms.
Closing Thoughts
Sometimes, I hear people ask, “Is math invented or discovered?” At first glance, it may seem that mathematical concepts are discoveries, just like scientific ones. 1+1 was always 2, whether humans know it or not, and the law of sines always existed, even before we “discovered” it. However, I like to think of math as an abstract notion created by humans, intangible ideas that only exists in the delicate neural networks of our brains. Unlike science, when you discover a quark, you’re examining an object the real world, an object that exists in objective reality that your work is grounded to. However, with math, equations only exist in our mind and on paper, and nowhere in the universe are mathematical concepts rooted in physical existence. The universe operates the way it does because it just does, not because it’s following some hidden code of math. When Newton came up with his laws of classical physics, they seemed to describe our world perfectly—when a ball is thrown up and falls back down, Newton’s gravity laws describe the motion accurately. Then Einstein came along with his theory of relativity, and we realized Newton’s laws are just a generalization that fails to apply to extreme scenarios such as the center of black holes. In an alternate universe, where math did not exist, the universe would still operate as it does today. Therefore, math is definitely an invention, invented when someone establishes the grounding axioms of a new branch of math. And just like any invention, mathematics can never be perfect.
If you liked this article, keep up with my content by subscribing to my newsletter!
