4 of the Most Profound Theorems in Math are Also the Easiest to Understand
It is Impossible to Detect Infinite Loops in a Computer Program
What does it mean to be able to detect an infinite loop? You might think you can just read the code and see that it contains an infinite loop. The more precise statement is that you can’t have a procedure that can always tell you whether a given program runs forever. You can certainly have a procedure that tells you whether certain specific patterns exist, but a program that runs forever is not always easy to recognize, as anyone who has accidentally forgotten to increment their loop counter can attest.
Assume I have a program that can detect if other programs run forever. Now consider this other program: Check if my input runs forever. If yes, halt and return. If no, enter into an infinite loop.
This program halts if its input runs forever, and runs forever if its input halts. What does it do when we feed this program as input into itself? Well, it halts if it runs forever and runs forever if it halts. This is impossible, so it’s not possible to make a program that can tell whether other programs run forever.
Alan Turing proved this in 1936.
All Mathematical Systems Are Incomplete
A mathematical system is incomplete if it contains statements which can neither be proven nor disproven.
Any sufficiently powerful system of axioms is be able to encode the mathematical equivalent of “This statement is disprovable.”
If the statement is provable, then the statement is false, so it can’t be provable.
If the statement is disprovable, then the statement is true, so it can’t be disprovable.
This means the statement is neither provable nor disprovable. So all sufficiently powerful systems of axioms are incomplete.
Kurt Gödel proved this in 1931.
There Are Different Sizes of Infinity
Which infinity is bigger, the number of natural numbers or the number of real numbers?
A quick primer on the different types of numbers:
Natural numbers are numbers like 1, 2, 3, etc. No decimal places, no negatives.
Integers also include 0 and negative numbers.
Rational numbers are the numbers you can get to if you’re allowed to do divisions on integers. So 1/2 is a rational number, and any other number that is a fraction or has decimal places.
Real numbers are like rational numbers but you’re allowed to use an infinite number of steps to describe them. Pi is a real number and not a rational number because it can’t be described as the division of two integers, but it can be described as an infinite sum of divisions between integers.
What do we mean when we ask if the size of one set is larger than the other? We’re asking if there exists a bijection between the sets. In other words, for every element in the first set, does there exist an element in the other set and vice versa.
If you’re comparing a set of infinite size to the natural numbers, it’s enough to just find a way to enumerate the set. If you can enumerate them, then you can map the first element with the natural number 1, the second element with natural number 2, etc. This is a bijection between the set and the natural numbers.
So, can we enumerate the integers? Yup, here’s one way:
0, 1, -1, 2, -2, 3, -3, 4, -4, etc…
Can we enumerate the rational numbers? There’s infinitely many rational numbers between 0 and 1, so maybe this is a harder question. Well, the answer is yes and here’s one way to do it (negative numbers omitted for brevity):
1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, etc…
We just proved that natural numbers, integers, and rational numbers are all the same size.
What about real numbers? Well, those are not the same size. There are more real numbers than rational numbers. In order to prove that, we’ll have to prove that there’s no way, no mater how clever you are, to enumerate the real numbers.
Let’s assume that we can enumerate the real numbers. Whatever the enumeration is, let’s lay them out and look at their decimal expansion. Consider the number that you would get by taking the first decimal of the first number, the second decimal from the second number, etc.
Now that we’ve got this number, let’s make a new number that is different in every digit. Maybe we change every digit to one higher, and maybe switch the 9s to 0s. So in the illustrated example we would make 0.138510871…
The claim is that the number we have just described does not appear anywhere in the enumeration of reals. The new number is different by at least one digit from any number in the sequence because that’s how it is constructed!
Wait, couldn’t we have done this trick for the enumeration of rational numbers? No, the key this time is that real numbers can be defined by taking an infinite number of steps. The procedure we just described takes infinitely many steps to generate the number, but that’s a totally legit was of defining a real number. It takes infinitely many steps to generate pi too.
There are more real numbers than natural numbers, even though they’re both infinite. There are different sizes of infinity.
Georg Cantor proved this in 1891.
There Are Infinitely Many Prime Numbers
Assume there are not infinitely many prime numbers. Then there is a finite list that has every prime number: [2, 3, 5, 7, 11, etc…, P]. In this list P is the largest prime number.
Let’s take the product of all those numbers and add one: (2*3*…*P) + 1.
Is this a prime number? If it is then it’s larger than all the prime numbers in our list and so our list must be incomplete.
If it’s not, then it must have a prime decomposition, because that’s what it means not to be prime. Which prime numbers could be in its prime decomposition? Well it has to be one of the numbers in our list, because that list has every prime number! But that means the same number has to be a divisor of both (2*3*…*P) + 1 and (2*3*…*P). The smallest prime number, 2, can only be a divisor of numbers that are 2 apart. So there’s no such thing as a prime number that can divide both a number, and that number +1.
Okay, so (2*3*…*P) + 1 can’t be prime and it can’t be non-prime. That’s impossible, so one of our assumptions must be false. Our only assumption was that there are finitely many primes, so there must be infinitely many primes.
