DISCUSSION
Many mathematicians upon the unveiling of Gödel’s Incompleteness Theorem held the belief that while Gödel’s logic and proof was sound, the systems he was referencing perhaps didn’t fully translate to all of mathematics. However, as time wore on more theorems arose that seemingly confirmed Gödel’s Theorem. The Halting Problem analogously proved the first and second theorems, the Paris-Harrington Theorem showed incompleteness in a mathematical system, and several mathematicians acknowledge that his theorem could be used to prove a variety of identities without proving them concretely.
3.1.1 Halting problem
One example of Gödel’s first theorem is the Halting problem, as there is no solution to the halting problem. A program can end in one of two ways: either the program halts or it loops infinitely. The Halting Problem asks what algorithm can be used to determine whether a given program will halt or loop. The Halting Problem is unsolvable, and the proof is below.
3.1.2 Proof
This is a proof by contradiction, so let us assume that there is an algorithm D(x) which is a solution to the Halting Problem (it will take any program as an input and then accurately output whether the program will halt or loop infinitely).
Let there be a program S(x) which takes a program M(x) as an input. S(x) is made so that the input M(x) takes itself as an input, making M(M). This is then inputted into D(x) [so this would be D(M(M)) ]. D(M(M)) will accurately determine whether M(M) halts or loops. So the conditions of D(M(M)) are as follows: if D(M(M)) outputs “loops”, then S(x) halts and if D(M(M)) outputs “halts”, then S(x) will loop infinitely.
Consider whether S(S) [S(x) taking itself as the input] would halt or loop. If D(S(S)) outputs “loops”, then S(S) will halt, because S(x) was made to do the opposite of the output of D(x). If D(S(S)) outputs “halts”, then S(x) will loop infinitely for the same reason. In either case, D(S(S)) will always be incorrect. This contradicts the given statement that D(x) is accurate. Therefore, it is impossible for a solution D(x) to exist, and there is no statement that can be proved to solve the Halting Problem. This is an example of incompleteness because the solution is a statement that cannot be proven.
For further information on the Halting Problem, watch this video or see source 2.
3.2 Paris-Harrington Theorem
The Paris-Harrington Theorem was somewhat of an extension of Gödel’s Incompleteness theorem. In 1977, Jeff Paris and Leo Harrington were able to prove that the Finite Ramsey Theorem could not be proved using the Peano Arithmetic axioms. Recall the Peano Arithmetic’s axioms from earlier and the first incompleteness theorem that statements can be improvable simply by the selection of the system. There are more axioms in mathematics than the Peano Arithmetic Axioms.
The Finite Ramsey Theorem is a case in graph theory which involves the coloring of a graph. To understand what Ramsey Theorem states the terms graph, edge, complete graph, and clique must be defined. A graph is a network of points and the lines between, called edges. An example is below:
Graphs can be complete, this means every point is connected to every other. Lastly, cliques are complete graphs within graphs. A complete graph is shown below with a clique highlighted in red.
Roughly speaking, Ramsey’s Theorem states that if one was to color the edges of any sufficiently large and complete graph with any number of colors there must exist a clique for which all the colors of the edges are the same. Again, roughly speaking, Paris and Harrington were essentially able to prove that a part of Ramsey’s Theorem, the Finite Ramsey’s Theorem could not be proven using the Peano Arithmetic axioms. They did this by showing that Peano Arithmetic, implies, but does not prove its own consistency. Therefore Peano Arithmetic is incomplete, according to Gödel. Since the axioms were incomplete a conclusion was then reached that the axioms could not complete the computations required for the Finite Ramsey’s Theorem.
The Paris-Harrington Theorem is particularly important as it became one of the first concrete examples of an actual mathematical system that lacked completeness.
For more information and a complete proof of the Paris-Harrington Theorem, see source 1.
3.3 Applications
When it comes to the applications of Gödel’s Incompleteness Theorem there are some sad realities and great opportunities.
First and foremost is that some of mathematics' greatest questions may not have answers. Some of the most famous examples are Goldbach’s Conjecture (every even number is the sum of two primes) and the Riemann hypothesis. It has been theorized that these statements are true, but cannot be explicitly proven true. The satisfaction in knowing that a mathematical statement is intuitively true is gone simply because the statement was beyond intuition.
To reference opportunity, recall the portion of the proof of Gödel's First Theorem that stated any statement which cannot be proven must be true, if the system is consistent. By that portion of the Theorem one could technically prove a theorem true by showing that it did not have a proof. When Paris and Harrington published they were applauded not solely because they had their own theorem, but because they also strengthened the Finite Ramsey Theorem. Likewise, a possible and backwards way to prove that Goldbach’s conjecture or the Riemann Hypothesis is true would be to prove that they do not have a proof.
