Kurt Gödel’s incompleteness theorems were written down in 1931, but they are talked about even today and will remain the subject of many more discussions to come. The reason why Gödel’s incompleteness theorem is so intriguing is that it is aimed at showing the kinks in the system that we have made for ourselves.
To be more clear, Gödel’s incompleteness theorems show that any logical system consists of either contradiction or statements that cannot be proven.
These theorems are very important in helping us understand that the formal systems we use are not complete. (A formal system is a system of axioms, containing rules of inference, which allow one to generate new theorems.) It also opens up the argument that no theory in physics, maths or any vertical can ever be 100% certain.
For a long time, mathematicians were bothered by the fact that they could not prove obvious things, due to the lack of methods of doing so.
In the 1900s, a trend of formalization of mathematics was in effect, helping mathematicians solve the hardest of problems by working towards a theory of everything - a unifying theory for all of mathematics.
However, Gödel’s incompleteness theorems showed that such a single theory of everything would not be possible. Not everything can be proved, as there will always be statements in mathematics that can neither be proved or disproved.
Gödel’s First Incompleteness Theorem
Any consistent formal system F within which a certain amount of elementary arithmetic can be carried out is incomplete; i.e., there are statements of the language of F which can neither be proved nor disproved in F.
In this statement, you need to pay attention to the two words 'consistent' and 'incomplete'.
A system is Consistent when the statements within it don’t have any contradictions.
A system is Incomplete when all or some of the statements within it can’t be proved or disproved.
The theorem states that a system F which doesn’t have any contradiction of statements when applied to elementary arithmetic will have axioms that we can neither prove nor disprove.
Now, you may ask why we can’t fully disprove or prove something. In mathematics, axioms are statements or propositions which are regarded as established, accepted, or self-evidently true and do not need to be proven within the theorem.
Axioms are very important in mathematics because they help the mathematician to expand their scope of study without having to prove every aspect of the theorem over again.
Gödel’s first incompleteness theorem, however, states that some arithmetical truths are not provable because that would require a formal system that incorporates methods going beyond the arithmetical system used to derive them.
The Second and Final Incompleteness Theorem
For any consistent system F within which a certain amount of elementary arithmetic can be carried out, the consistency of F cannot be proved in F itself.
This is an extension of the first incompleteness theorem and goes to show that a formal system which claims itself to be consistent cannot prove that it doesn’t have any contradictions. In the case of the second theorem, F must contain a little bit more arithmetic than in the case of the first theorem.
Gödel demonstrated this theorem using the liar’s paradox.
Consider the statement “I am lying.” “I am lying” is self-contradictory, since if it’s true, I’m not a liar, and it’s false; and if it’s false, I am a liar, so it’s true.
Hence, the statement can never prove or disprove itself.
Effect of Gödel’s theorem on Hilbert program
Before Gödel’s theorems, the mathematical world was governed by Hilbert’s program. This was formulated by David Hilbert in the early 20th century to put an end to the paradoxes that were found in Set Theory. It called for a formalization of all of mathematics in axiomatic form, together with a proof that this axiomatization of mathematics is consistent.
These paradoxes were becoming quite challenging for the mathematicians. So, Hilbert divided mathematical statements into two – Contentual and Ideal.
Contentual mathematics is considered to be inherently consistent and arithmetic. Ideal mathematics is math with instrumental value in science or mathematical simplicity.
In essence, ideal mathematics are conceptual while finite mathematics or contentual mathematics have a practical use.
To bring a sense of solid principle in mathematics, Hilbert proposed that mathematics should be based on a provable, consistent foundation of axioms. Hilbert called this the 'finitary standpoint.'
However, Gödel’s incompleteness theorems refuted the arguments of the Hilbert program. Gödel’s theorems which state that any systems containing arithmetic will have arguments that we can neither prove nor disprove and that we cannot prove that a mathematical system is consistent, throws the argument about finitary consistency out of the window.
Gödel’s theorem dealt a heavy blow to Hilbert’s program, and mathematicians stopped using the approach in evaluating finitary and ideal systems. Gödel essentially proved that in any branch of mathematics, there will be arguments that one can neither prove nor disprove.
This opened up a variety of arguments, not just in math but also in other fields of science and logic.
For example, Gödel’s theorem implies that you will never be able to truly understand yourself because your mind is contained in a closed system, and can only know things from its own standpoint.
What do Gödel’s incompleteness theorems mean today?
With Gödel’s incompleteness theorems, we know that any process that handles basic arithmetic will have statements which we can’t prove or disprove. In a modern sense, this means that you cannot build a compiler or a perfect antivirus.
His theorems allowed the derivation of several results about limits of the computational procedures. A prominent example is the unsolvability of the halting problem.
A halting problem is a problem of finding out whether a program with a given input will halt at some time or continue to run into an infinite loop. This decision problem is useful to demonstrate programming limitations.
Gödel’s statement that there are more things that are true than you can prove can also be used to illustrate that faith and reason are not pitted against each other, but are interdependent. All forms of reason will have something that you cannot prove.
Gödel’s theorem has even been used as a logical construct to prove the existence of God (Gödel's ontological proof).
The theorems did not mean the end of mathematics but were a new way of proving and disproving statements based on logic. Gödel’s theorem showed us the limitations that exist within all logical systems and laid the foundation of modern computer science.