How Liar's Paradox inspired Gödel to prove Mathematics Incomplete

685

Computation

Mathematics

Paradoxes are statements that contradict themselves. You must have encountered some of them in brain teasers or solving other puzzles. But they aren't just puzzles. They play an essential role in mathematics. In this article, we will first discuss paradoxes and how Kurt Gödel used them to question the foundations of mathematics, that all true Mathematical statements can be proved. <b><h2><center>Paradoxes</b></h2></center> Let's start this section with a question: <i>Statement A: Statement A is False. Is statement A true or false?</i> If you say that statement A is true, but statement A says that it is false, it means it must be false. But if statement A is false, then you are saying that the claim of statement A is true, and hence statement A is true. And this logical conflict can go on forever. This is one example of a <b>paradox</b>. As said above, Paradoxes are statements that contradict themselves. If you are looking for a solution to the above question, that doesn't exist. Such statements are called <b>inconsistent or undecidable</b>. Inconsistent statements mean they don't have a specific value between true and false. <b><h2><center>Gödel's Incompleteness Theorem</b></h2></center> Kurt Gödel was an Austrian mathematician. In 1931, he shook the mathematical community with his <b>Incompleteness theorem</b>. In that theorem, he proved that not all true statements are provable. This contradicted the foundations of Mathematics that if something is true, then proof exists for it. Gödel's incompleteness theorem meant we didn't know what could be proved and what could not. What Gödel proved precisely was that <i>if we have a set of axioms for a number system, then there exists a true statement that cannot be verified or proved with the given axioms</i>. But let's say there is a more extensive set of assumptions (in a different number system) that can prove your statement; then, more such statements still exist that cannot be proven with this set of axioms. <b><h2><center>How are Paradoxes Involved?</b></h2></center> The liar's paradox which is "This statement is False", led Gödel to think about incompleteness in Mathematics. Axioms are undeniable statements about the numbers involved. We can use these axioms to prove something in mathematics (applicable to that specific system). For example, to prove 2+3 = 3+2, we can use the hypothesis of how addition works. From self-referential paradoxes like the liar's paradox, Gödel got the idea of proving how axioms can contradict themselves. His proof starts by converting Mathematical statements (like axioms and expressions) into code called <b>Gödel's Number</b> so that these equations can be expressed as numbers. Gödel could use this encoding to encode <i>"This statement cannot be proved"</i> as an equation. It is creating the first self-referential mathematical statement. But mathematical statements must be true or false. So what about this equation? If it's false, then it means the statement does have proof, and if a mathematical statement has proof, then it must be true. <b>This contradiction implies that Gödel's statement cannot be false, but it can neither be proved to be true.</b> <b><h2><center>What Does Gödel's Theorem Mean Exactly?</b></h2></center> Gödel's first incompleteness theorem introduced new kinds of statements in Maths. In Gödel's paradigm, statements still have either a true or a false value, but true statements can be provable or unprovable within a given set of axioms. Gödel also proved that such statements exist in every axiomatic system in Mathematics, and hence we can never create a complete system in Maths. This means there will <b>never exist a Mathematical Theory of Everything</b> as there always exists a statement that is true but not provable in Mathematics. If you add these true unprovable statements as axioms to the current set of axioms, it will introduce a new set of true unprovable statements. <b><h2><center>Gödel's Theorem in Computer Science</b></h2></center> Gödel's work also allowed Mathematicians in the field of computer science to decide what could be computed and what not. The <b>incompleteness theorem is equivalent to the halting problem</b>, which is a way to prove that some problems are <b>undecidable</b> for a computer. An undecidable problem in Computer Science means you might run the algorithm for the problem on the computer, but you don't know if it will ever stop running (with success or failure) or not.

- Ojas Srivastava, 08:17 PM, 05 Feb, 2023