No matter how many articles I read on this subject I cannot comprehend how it proves what it proves. I do well with words and rhetorics, philosophy and science – but as soon as you add numbers my mind goes blank. Not very helpful when those fields often rely on equations and models for explanations and proof. I can somewhat understand equations if explained in a simple or cohesive way – but if at all possible analogies or just word-centric explanations would be very helpful.
In: 25
Suppose you have some formal, logical theory of arithmetic. That is, you’ve reduced statements like 2 + 2 = 4 (a true statement) or 5 – 4 = 7 (a false one) into purely logical terms, without directly invoking the concept of numbers.
The (first) incompleteness theorem says that, given such a language, there are sensible statements you can make, but which can’t be proven true *or* proven false using that logical language. In other words, you can never create a structured theory of arithmetic (satisfying certain relatively weak assumptions) that can prove every true statement in arithmetic.
Math can result in an “This statement is false” situation.
It is obviously true, but that would mean it is false. Which would mean it is true.
That is, you cannot prove everything.
This is how I understand the theorem.
Have you read the simple version of the wiki – https://simple.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems
For thousands of years mathematicians have relied on proofs as the basis of mathematical systems. Statements can either be true or false, and finding ways to prove whether a given statement is true or false allows you to build larger and more complex systems.
But can all statements be proven true or false? Some mathematicians believed that should be true, and they set about to find or create a system that would allow them to do that.
However not all people believed that to be the case and Godel, with his incompleteness theorems proved (somewhat ironically) that such a system could not exist. That there would ALWAYS be statements which, while they could be true, could also not be proven.
How did he do it? Well on a very abstract level Godel created a mathematical version of the statement “This statement can not be proven”. If it COULD be proven it would set up a paradox, because it would be simultaneously false (because it had been proven) and true, because there was a proof that it was true. Instead the statement had to be true, but also unprovable (I. The mathematical sense). He further proved that this would be the case for any mathematical system, that no matter how you tried to adjust it to account for true but unprovable statements like his own, you’d simply introduce more.
The YouTube channel Veritasium has a great, though lengthy explanation in the following video:
The core statement is something like “no self-consistent recursive axiomatic system can contain a proof of its own validity”. The problem goes something like this:
Q: Math seems great, and I can do all kinds of useful stuff with it, but can I trust it? Is there some way to prove that math is logically valid?
M: Yes – the trouble is, the proof doesn’t use math; it uses this other logical system that I’ll call L1.
Q: Cool. L1 actually seems neat too, and it can do some useful stuff that math can’t. But wait, can I trust L1? Is there some way to prove that L1 is logically valid?
M: Yes. The trouble is, the proof isn’t based on math or L1; it uses this other system called L2.
Q: Can I trust L2?
M: Totally. As long as you accept this proof that’s based on L3…
…and so on like that. All this arose when a mathematician named David Hilbert suggested that we should carefully come up with proofs of all our math ideas, so we know everything’s on firm logical ground, and the community tried for years and went “man, this is harder than we thought it’d be”. And finally Godel did some work and announced “stop trying, I’m pretty sure it’s impossible”.
Gödel proved in an extemely abstract way that there are limits to what statements any logical/symbolic system (like math) can make *about itself*, so there are statements in math that fundamentally cannot be proven or disproven (although we do not know which those are).
Gödel developed his theorem during a time where some mathematicians worked on a big project to prove that basically all maths is consistent and “true” (to its own rules). Gödel proved that their project was fundamentally doomed.
Self referential paradoxes are one of the oldest kinds of paradoxes known to man.
The famous “everything I say is a lie” comes to mind, or “this statement is false.”
Bertrand Russell used a variation of this to construct his famous paradox in set theory. Many, many different paradoxes and brain teasers boil down to self referential statements. Keep this in mind, and I’ll walk you through the history.
Now in mathematics, things are proven to be true via inference from other things known to be true. Pick any theorem in an introductory calculus textbook, and you can keep asking “why” or “how do we know that is true.” Eventually, this chain must end somewhere.
The place it ends is called axioms. Axioms aren’t really “true” or “false” rather “useful” or “not useful.” Euclid included several axioms in his description of geometry, most famous his fifth postulate. Mathematicians tried for centuries to prove the fifth postulate from the other, simpler axioms, but failed. In the 19th century, it was discovered that taking a different axiom than Euclid’s fifth resulted in different geometries. These geometries, elliptical and hyperbolic, were actually used in the development of general relativity and form part of our modern understanding of cosmology.
Between Cantor’s paradoxes of different sized infinites, the discovery of new geometries, Riemann and Cauchy placing calculus on firmer ground, and Russell’s paradox, mathematicians became increasingly concerned with their foundations, the axioms as we call them.
Since the axioms are a freely chosen set of base truths, we can construct them how we please. There are certain features we desire.
1.) Sufficiently strong to do arithmetic with. If your axioms aren’t at least sufficient to describe adding natural numbers, it likely isn’t going to be useful. There would be little you could do with such a limited system. The technical term here is “Peano arithmetic” after a mathematician named Giuseppe Peano, who listed the first set of axioms for the natural numbers.
2.) Consistent. From your axioms, you should not be able to derive both a statement and it’s negation. Once you allow contradictions in, principle of explosion results in anything in principle being proven. We only want our axioms to be able to prove true statements.
3.) Complete. Any question that we can ask in terms of this axiomatic system should be able to be answered with a “yes” or a “no.”
What Godel did was use a clever way of constructing a self referential paradox to show that this is impossible. Any system of axioms that is at least powerful enough to perform elementary arithmetic of natural numbers must have either the possibility of contradictions, or statements that are true but unprovable.
For an understandable construction of Godel’s theorem, there is a veritasium video on YouTube. But the above is the “how, when, and why” so to speak.
I personally think it’s not do-able in “plain english” so to speak. But let’s try.
Godel’s theorems came about when mathematicians were trying to prove the consistency of math. In other words, prove that it’s not “broken”. There were some issues they came across that was bothering them in a very existential way. Kind of like how infinitesimals did prior to the 1600s.
They tried the age-old Greek methods of https://en.wikipedia.org/wiki/Geometry … but they fell short (I’ll skip why).
So they resorted to [https://en.wikipedia.org/wiki/Set_theory](https://en.wikipedia.org/wiki/Set_theory) which was much more basic but also very analytic and could cover topics geometry failed at.
They started the task of constructing a minimal set of “rules” called axioms from which ALL of math could be constructed.
(here’s where Godel comes in)
He was able to show, that if you had a finite set of axioms (say, nine of them) – then Godel was able to show that there MUST be a statement that was true, but could not be proven by those 9. He didn’t need to provide this statement, just prove it must exist.
So, in the same way we can prove that there is no “biggest number”, or that there is no “biggest prime” … Godel proved we can never have a “complete set of rules” for math that would let us prove or disprove any statement.
I’ll just add that we understand very very well when we know something is provable (or disprovable). So it’s not like math is broken. But there are limits, we know there are, and Godel gave us tools to determine if a statement is provable.
He showed there are statements that are provably unprovable.
He also show there are statements which are unprovably unprovable.
Hence his nickname – the Nietzsche of Logic.
Completeness would be “all true statements have proofs”. Godel constructed a statement which, if true, means that the statement does not have a proof. If the statement is true, it has no proof, thus an incomplete system. If the statement if false, it is a true statement with a proof and thus inconsistent. Any sufficiently expressive logical system is either incomplete or inconsistent. If it can express “This statement has no proof” then it is incomplete.
Mathematicians were bummed. They asked “Can we find all of the statements with proofs?” Alan Turing described a theorem proving machine — a Turing Machine — which would test a statement to see if a proof could be found for it. Turing showed that we can’t tell if the machine would ever stop trying to prove some statements. So we can’t tell if a statement does not have a proof.
The essential idea is Quine’s paradox, which is just an upgrade of Liar’s paradox.
Liar’s paradox said “this sentence is false”. This paradox relies on self-reference (the sentence talk about itself). Every formal system of logic in math don’t allow self-reference.
Quine’s paradox said ” ‘yields falsehood when preceded by its quotation’ yields falsehood when preceded by its quotation”. This sentence does not refer to itself, but the quotation of itself. It said that if you take the string of letter “yields falsehood when preceded by its quotation”, put that at the end of a sentence, then put the entire string in the quote, then put it at the beginning of the sentence, to form a sentence, then that sentence if false. This is a clever way for a sentence to talk about a different statement that looks exactly like itself.
So if you have a logical system of string manipulation, you can potentially perform Quine’s paradox. If you do Quine’s paradox literally, you end up with Tarski’s undefinability of truth: since the paradox cannot happen, the only way out is that there are no ways to define “true” or “false” in the system.
Instead of of doing Quine’s paradox literally, we use it as a recipe to change any self-reference paradox into a paradox that does not use self-reference.
For example, we have the following Curry’s paradox: “if this sentence is true, then Santa is real”. If the sentence is false, then the implication “this sentence is true” -> “Santa is real” is false, but the only way the implication can fail is if the hypothesis is true and the conclusion is false, so the sentence is true, a contradiction. So the sentence must be true, then it is concluded that Santa is real.
We can use that same recipe for Quine’s paradox to upgrade this into Lob’s paradox: ” ‘implies Santa is real when preceded by its own quotation’ implies Santa is real when preceded by its own quotation”. By a similar argument to above, this sentence must be true so Santa is real.
But as I mentioned above, what we discovered is that “true” and “false” cannot be defined by the system (to prevent Quine’s paradox), so we can’t actually talk about whether the sentence is true or false. However, what we could talk about is whether the sentence is provable or not. This is because provable is a much more mechanical condition: a proof must exist, and a proof is a string satisfying all the law of logical inference.
So we have the following version of Lob’s paradox: ” ‘when preceded by its own quotation, if provable implies P’ when preceded by its own quotation, if provable implies P” (where P is an arbitrary statement). If the sentence is provable, then it is also provable that the existence of the proof of this sentence implies P (because that’s what the sentence said). But if there is a proof that the sentence is provable implies P, then if there is a proof that the sentence is provable, there is also a proof of P. Combining the 2 statement above, if the sentence is provable, and there is a proof that the sentence is provable, then there is a proof of P. But if there is a proof of the sentence, then of course there is a proof that the sentence is provable, so we can eliminate a redundancy above: if the sentence is provable, then there is a proof for P. Now we make a jump, an additional assumption! We assume that we have a proof that a proof of P implies P is true. Then if the sentence is provable, then P is true. But that’s exactly what the original sentence said. So the sentence is provable, so P is true.
That’s Lob’s theorem: if “P is provable then P” is provable then P. For any P. This implies Godel’s incompleteness theorem. Let P be the statement “the system is inconsistent”. So we have if “‘the system is inconsistent’ then the system is inconsistent” is provable, then the system is inconsistent. So if the system is consistent, “‘the system is inconsistent’ then the system is inconsistent” is not provable, but that statement is equivalent to saying that the system is consistent. So the claim that the “system is consistent” is not provable.
Latest Answers