What is gödel’s theorem?
In: 0
There are a few Godel theorems, but the most well known one is probably the Incompleteness theorem.
If our definitions of math and logic are correct and valid, then these two sentences should be true…
If a statement is true, then it can be proven.
If a statement has been proven, then it is true.
…. right?
Well, it turns out No. Godel demonstrated that there are facts that are true, but cannot be proven, by your math and logic. Turns out you can’t have both sentences true at the same time, 100% consistently.
There are various unproven conjectures in arithmetic, like Goldbach’s conjecture that “Every even integer greater than 2 can be expressed as the sum of two primes”. We’ve checked a bunch of integers and haven’t found any counterexamples to that conjecture, but we haven’t been able to check *all* the even integers because there are infinitely many of them.
Gödel proved that at least some of these unproven conjectures (though not that particular one) *can’t* be proven. We will never be able to generate a counterexample *nor* prove that there could never be a counterexample.
The way his proof works is basically that it assigns a number to each possible mathematical statement. For example, we might represent “3 + 5 = 8” as “11 4 101 8 1000”. Once we’ve done that, we can characterize a “proof” mathematically: it’s a series of numbers, each of which bears a certain kind of relationship to the preceding ones.
Which meant that Gödel could construct an arithmetic claim that amounted to “No series of numbers has the property of encoding a proof of this claim”. Assuming that it’s not possible to prove false stuff, this claim is true but unprovable.
Of course, if we could *prove* that it’s not possible to prove false stuff, then we’d be able to prove that the claim is true. So that means “No series of numbers has the property of encoding a proof of a false statement” is *also* unprovable.
The way math works if you start with a set of rules and axioms, and then you construct statements with those rules and axioms.
For example, a statement for arithmetic might be 1+1=2. Or “all integers have a unique set of prime factors” (since this is ELI5, I wrote that as words, but there is a way to write it with math). Before Gödel mathematics thought that math would be a completely enumerable system, which a concrete and finite set of these rules and axioms, from which all valid math statements would derive.
What Gödel showed was that there exist true statements within the language of the rules and axioms, that cannot be proved with the rules and axioms.
This doesn’t mean the statements can’t be proved; it just means you need a different or expanded set of rules and axioms to prove it. It’s really quite a deep result. In a way it shows that math is infinite; there is always another layer of the onion to peel back, so to speak.
Unfortunately there are no trivial examples of a true statement that cannot be proved with a simple set of
Rules and axioms.
Latest Answers