GÖDEL’S SECOND THEOREM
Gödel’s Second Incompleteness Theorem is most simply stated as follows:
2.1 Background
It is known from Gödel’s First Incompleteness Theorem that a sufficiently expressive system cannot be both complete and consistent. While this theorem does not put any restrictions on an information system which is not sufficiently expressive, it is our first priority to have a system which is sufficiently expressive, for the purpose of making mathematics a broad field with many topics and applications. So, between completeness and consistency, it would be best to sacrifice completeness in order to maintain consistency in our information system. This is because without consistency, false statements can be proven true, and all of the information that was discovered using our current information system would be invalidated. Therefore, in order to ensure that we have an information system which is sufficiently expressive, consistent, and incomplete, we must prove that our system is consistent.
2.2 Completeness
Completeness is a description of an information system. An information system is complete when all statements that can be formed in an information system using the axioms in the system can be proven true. An example of incompleteness, which will be explored later, is the Halting Problem. There is no solution that can be proved to solve the Halting Problem using the axioms in our information system. Another example of incompleteness is Gödel’s Second Incompleteness Theorem. It is impossible for a consistent system to prove its own consistency, and this makes that system incomplete.
2.3 Proof of Gödel’s Second Incompleteness Theorem
Let there be 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) (see section 3 below).
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.
Let us consider whether S(S) [S(x) taking itself as the input] would halt or loop. Below in section 3.1, it is proven that it is impossible to prove that S(S) will halt or that S(S) will loop, assuming a consistent information system. So, let us try a different approach, still assuming a consistent system.
Since S(S) cannot be proven to loop or halt, it will continue infinitely iterating over itself in an attempt to prove either that S(S) will loop or halt. So, S(S) itself is looping infinitely. This statement, while using sound logic, contradicts the earlier statement that it is impossible to prove that S(S) halts or that S(S) loops. Both of these statements were made assuming a consistent system.
If this system proved its own consistency, then these two contradicting statements would both be true, creating an inconsistency. This is paradoxical, so therefore, a system can not prove its own consistency.
2.4 Implications
It is evident that our information system is sufficiently expressive, because mathematics has so many topics and applications. It is of very high importance that our information system is consistent, because otherwise, false statements could be proven true. If our system was inconsistent, then everything that was previously discovered using mathematics would be invalidated, and a new information system would have to be created before we can even attempt to find new information.
So, by Gödel’s First Incompleteness Theorem, we should hope that our information system is incomplete. This would mean that no matter how long philosophers, mathematicians, and scientists try to discover new information, we will never find out everything there is to know.
By Gödel’s Second Incompleteness Theorem, our information system can not prove its own consistency. This means that we are unsure if anything that has already been discovered using mathematics is valid. We can not even be sure that the nearly countless discoveries of mathematics are even true.
For further information on Gödel’s Second Theorem, see source 5.
