What are the problems and theorems that are derived from it?
In: 80
Basically the theorem states that there are true mathematical statements that can’t be mathematically proven.
There will always be some true statements about the natural numbers that cannot be proven within the system.
This theorem has important implications for how we think about the limitations of logical systems and computational models
In the early 1900s, mathematicians such as David Hilbert were trying to develop a system of axioms (starting assumptions or statements accepted as true without proof) from which they could define all of mathematics in a consistent way (meaning you can’t contradict yourself by proving something both true and false). Godel ended these efforts by putting forth not one, but two, incompleteness theorems. They were:
1. There is no* system for which you can prove every true statement. That is, for any set of axioms, there will be some statements that are true but cannot be proved from those axioms.
2. No* consistent system can be used to prove its own consistency. This means that you cannot prove a system has no contradictions from within the system.
* It’s not strictly true that the incompleteness theorems say that *no* theorems can meet these conditions. It’s more accurate to say that *no useful, non-trivial* system can do so.
Any consistent formal system that is powerful enough to describe the natural numbers must be incomplete in the sense that there will always be statements that are true within the system but cannot be proven within the system.
In other words, Gödel’s Incompleteness Theorem says that no formal system (such as a system of mathematical axioms or a computer program) can be both consistent and complete. This has important implications for the foundations of mathematics and computer science, as it suggests that there are limits to what can be proven or computed within a formal system.
There are actually two incompleteness theorems. Both apply to formal systems, which are logical systems where specific rules are applied one by one to generate proofs. Mathematicians use formal systems as a way to formalize certain kinds of logical thought, and almost all mathematics can be reduced to a formal system. The incompleteness theorems prove that there are limits on any formal system, and therefore limits on our ability to describe math.
The first theorem more or less says that any formal system with enough complexity is either inconsistent or incomplete. “consistent” means that there are no contradictions in the system’s rules. In mathematics, even a single contradiction ruins the whole system, so consistency is desirable. “complete” means that any statement in the system can be either proved or disproved by some clever arrangement of the system. An incomplete system then has statements that are neither true nor false; the rules of the system just don’t say anything about them.
This theorem is “bad news” because it means there’s no logical system we can set up that describes “all of math.” No matter what rules we decide we want to use, there will be some “facts” that those rules can’t be used to reason about, unless the rules contradict each other, which we really don’t want. We could decide whether any of those statements “should” be true or false, and then add another rule to the system saying so, but the decision about whether they “should” be true would be a human judgement call, not a mathematical fact, and there may be people who support using both.
The second theorem says that any consistent formal system with enough complexity can’t be used to prove its own consistency. Effectively, if your logical system works, you can’t *prove* that it works, unless you use some other logical system to prove it. But then you can’t prove that *that* logical system works without even another system, and so on…
This is “bad news” because it means we’ll technically never know if the logic we’re basing our mathematics on is truly consistent, or if there’s some contradiction lurking somewhere that would ruin the whole thing. This is considered extremely unlikely for the most commonly used systems, but there’s no way to say for certain.
[deleted]
Gödel’s first incompleteness theorem:
the sentence “this sentence is false” is neither true nor false, and you can’t avoid making statements like that in any reasonably complicated system.
Gödel’ second incompleteness theorem:
We can only hope that math is logically consistent with itself and doesn’t lead to self-contradictions. If we ever succeed at proving that mathematics is consistent, then there’s a way to turn that into a self-contradiction, meaning we actually failed. Again, this is a fact about all reasonably complicated ways of setting up the rules of math.
Math tries to prove things are true or false. Like 1+1 =2 is true and 1+1 = 3 is false.
People thought math was ‘complete’, meaning you would always be able to prove if something is true or false, but Godel discovered that there are actually sums that we KNOW are true, but we can’t prove it, and therefore math is ‘incomplete’.
Here you go, Verisatium has an excellent explanation of it. No amount of ELI5 will work here in paragraphs until you see the proof. https://youtu.be/HeQX2HjkcNo
[removed]
Latest Answers