What do Gödel’s incompleteness theorems mean?
In: Mathematics
**This statement is false.**
This is known as the Liar’s Paradox. If the statement is true, then it must be false, and if it is false, it must be true. The existence of these kinds of self-referential statements forces us to abandon the notion all statements must be either true or false, there must exist indeterminate states.
Gödel created a very clever proof showing any non-trivial system of logic (like arithmetic) is capable of self-reference. They can be used to say things like “this statement cannot be proven true”. The consequence is there must be statements that are true but cannot be proven true, and contrary to what mathematicians and logicians thought at the time, there is no general way to prove a given statement is true or false.
Whenever there is a particularly difficult problem (four-color theorem, Fermat’s last theorem, P != NP) that remains unsolved for a long time, speculation begins whether it might be true or unprovable.
If you have a logical system that is rich enough to do basic arithmetic and you assume that your system doesn’t lead to contradictions (i.e. for any statement in your system, you can prove that the statement is true or you can prove that it’s false, but you can’t prove that it’s both true *and* false), then two things must be true about your system:
1. There are some statements in the system that you can neither prove nor disprove.
2. You cannot prove that the system doesn’t lead to contradictions using only the system itself.
The first thing is bad because it means we can come up with questions that we will never, ever find the answer to, and we have no way of telling whether our current question is one of those unanswerables or just really, really hard. We could spend a lifetime working on a problem that simply cannot be answered.
The second thing is bad because it means that, even if we find the correct answer to a question, we can’t guarantee that it’s the *only* correct answer, at least not without using a more sophisticated logical system to prove it. But what if *that* system has contradictions? Well, we could try to prove that it doesn’t, but (2) says that it can’t prove its own consistency, so we’ll need an *even more* sophisticated system… and so on. It’s turtles all the way down.
It means that a mathematical system cannot be both consistent and complete. I.e. if you design a mathematical system based on a number of rules in the end you will always find that either:
– Your system will be able to prove that something is both true AND false.
– Your system will be unable to prove for certain statements neither that they are true or false.
Latest Answers