Without further ado, an explorations of the basis of math.
Have you ever had a kid start asking you “why”?
You: “The sky is blue”
Little Timmy: “Why?”
You: “The way the sun reflects off of the atmosphere”
Little Timmy: “Why?”
... and so on. Eventually it delves into questions that are almost impossible to answer. This was the problem with 19th century mathematics - Why does $1+1=2$, Why does $0=0$? Does that have to be how it is?
The way mathematicians solved this was “axiomatizing” the way that we do mathematics. We created “axioms”, which are just things we assume from the beginning when doing math. It’s stuff like $1+1=2$, $a+b=b+a$, etc. that can’t be proved, but we just assume because they seem to be natural truths. Any set of axioms is called a “formal system”. For example, the set of axioms we usually use is called “ZFC”, and is made of 9 assumptions. From those assumptions we can derive (pretty much) everything in mathematics.
Formal systems can be consistent, or inconsistent. If a formal system is inconsistent, then there is a theorem such that that formal system can prove the theorem to be true, and that formal system can prove the theorem to be false. More generally, a formal system is inconsistent if can prove a contradiction (i.e. $0=1$). A formal system is consistent if there is no such theorem. We believe that our usual set of axioms, ZFC, is consistent, because in the hundreds of years we have done math with it (knowingly or not), no one has discovered a proof of $0=1$ or any other contradiction.
People were very happy with this system of "axioms", and thought they had finally found a foundation for all of mathematics to rest on. They thought it was air-tight. Then, in 1931, a logician named Kurt Godel turn their hopes on their heads. He proved 2 main things:
- In any formal system that can do elementary arithmetic, there exists some statements that are true but unprovable.
- Any consistent formal system can never prove it's own consistency.
These, respectively, are called the first and second "Incompleteness Theorems" of Godel. I'm going to venture into some tough territory here, and try to outline a proof of both of these theorems to give some intuition as to why they are true.1
First, assign a number to every symbol used in mathematics. Any way will work, but you don’t actually have to construct an explicit method. Just assume that every symbol has an associated number.
Second, construct a function to assign a number to any statement by combining the numbers of each symbol in it. For example, if we just assign A=1, B=2, C=3, etc., “ADD” would be 144.
Third, extend that function to assign a number to any proof (which is, of course, just a bunch of statements that eventually prove something) by combining the numbers associated with every statement within it. So, now we have assigned a number to every theorem, as well as every statement. So, let’s take the statement “1+1=2”. It has a number associated with it, and it's proof also has a different number assigned to it.
Here’s the cool part. Take the number associated with the statement:
$$\text{“The number associated with this statement does not stand for a theorem”}$$By theorem, of course, I mean something provable in our formal system. Take a moment to process this. Obviously, this statement must be either true or false.
If this statement is false, then that statement is a theorem (because the statement is asserting that it isn’t), which means that statement is true (since something being provable and a theorem means it is true). So, if the statement is false, it's true, a contradiction.
And in mathematics, if something being false implies that that thing is true, it must not be false. So, our statement is true. The number does not stand for a theorem, and since the number stands for that statement, that statement is not a theorem. By our definition of theorem above, that means that statement is not provable, but as I asserted in bold, it’s true.
Therefore, in any system (because we aren’t working in any specific system here), there is at least one unprovable statement, “The number associated with this statement does not stand for a theorem”.
Now, let’s extend this to prove that there are infinite unprovable statements. First, assume that there does exist a system $A$ such that there is only $1$ unprovable statement. Take that unprovable statement, and make a new system $B$ which is just $A$ but with one extra axiom: That unprovable statement is true. So since we already assumed that $1$ unprovable statement to be true in our axioms, $B$ has no unprovable statements. But this contradicts Godel's First Incompleteness Theorem that every formal system has at least $1$ unprovable statement.
The same argument works for any finite amount of unprovable statements - just make a new system where they are axioms, and it violates our theorem. Therefore, every formal system, has an infinite amount of theorems that are unprovable within it.
Exercise 1 For the determined and well-versed reader, prove Godel's Second Incompleteness Theorem using the techniques outlined above. Hint: Note that inconsistency of a formal system is equivalent to $0=1$ in that system.I will not try to prove Godel's Second Incompleteness Theorem here, I don't have the talent to outline it in a similar fashion. However, there are many proofs available online for those well-versed in mathematical logic. For now, we will assume it.
These two theorems are amazing in their counter-intuitive nature and their immense power. The literature, both philosophically and mathematically, on these two theorems is absolutely titanic. For now, I will go over what I believe to be some of the most interesting and and least mainstream consequences.
Starting with the first incompleteness theorem, we have a dilemma if we look at physics. For years, physicists have been trying to make a "Theory of Everything", one theory that describes the whole universe. On a large scale, general relativity does an amazing job of predicting things. On a small scale, quantum mechanics prevails. But try to apply GR to a small scale, or QM to a large scale, and you fail miserably. Physicists have been trying to unite these two theories in attempts such as string theory, M-Theory, supersymmetry, etc. Godel's First Incompleteness Theorem, however, seems to suggest this is impossible.
A "Theory of Everything", at it's core, is a finite set of statements and equations that describes every physical phenomena. But, Godel's First Incompleteness Theorem seems to suggest that any set of axioms cannot prove everything, or describe every phenomena. This has been the subject of much debate between physicists, but comes down to more a question of semantics than actual mathematical formalism.
Now, the Second Incompleteness Theorem, which is my personal favorite. Any consistent formal system can never prove it's own consistency. But let me ask the seemingly obvious question - can a consistent formal system prove it's own inconsistency? Here's something really unintuitive - yes.
Take any consistent formal system $S$. $S$ cannot prove it's own consistency by the second incompleteness theorem, therefore if we add the axiom that $S$ is inconsistent, there is no contradiction, because there is no proof stating the opposite. So, our new "extended" version of $S$ proves it's own inconsistency yet is consistent. Weird.
A natural question that comes out of this is what happens if we take a formal system $S$, and instead of adding the axiom "$S$ is inconsistent", add the axiom, "$S$ is consistent". Well, let's try it.
Take any formal system, call it $S_0$. Create a new system $S_1$, defined as $$S_0+S_0\text{ is consistent}$$ Where I'm using $+$ to signify adding an axiom.
Now, this system does not, as it first seems, prove it's own consistency and violate our theorem. Within $S_1$, you can prove that $S_0$ is consistent (since it's an axiom), but you cannot prove $S_1$ is consistent. Here's the cool part - we can go farther.
We could make a system $S_2$ defined as $S_1+S_1\text{ is consistent}$. And we can continue this process, defining $S_n$ as $S_{n-1} + S_{n-1} \text{ is consistent}$.
Now, an apparent contradiction arises. Consider $S_\infty$. Shouldn't this system prove it's own
consistency, since for all $S_n$, $S_{n+1}$ assert's $S_n$'s consistency?
Well, no. $S_\infty$ proves the statement "$S_n$ is consistent" for every $n$, but $S_\infty$ does not prove the statement "$S_n$ is consistent for every $n$". Note the placement of the quotes. A softer analogy to this is the fact that you can easily take a proof $P$ in a system $S$ and prove that $P$ doesn't prove a contradiction, for every proof $P$ in $S$ (by simply looking at it and asking whether it's result is something like $0=1$). However, you cannot prove that $P$ doesn't prove a contradiction for every proof $P$, as this is literally the definition of consistency of $S$.
All of this is extremely unintuitive, and I don't expect anyone to understand any of it at a first reading. It took me a very long time to wrap my head around this, even with a pretty good background in mathematical logic. If you don't understand something, read it over again and again, google it, and feel free to email me at nicktwoa@gmail.com or contact me through some medium.
Hope you enjoyed!
1Of course, a lot of this is different from the actual proof and very simplified. But it's still true, just more general.
