Godel’s (first) incompleteness theorem

I would like to describe a most amazing result in math, computer science, logic and even philosophy (kind of a stretch there but..).

Godel’s incompleteness theorem addresses the theory of natural numbers constructed from axioms. The results also apply to any equivalent theory and state that if,

1. The axioms of the theory are consistent
2. The axioms apply to a finite number of objects or if they (as likely) have infinite applicability, are recursively list-able/enumerable. This just means that there is an algorithmic rule to decide if a given statement in the theory is an axiom.
3. The axioms give rise to a theory capable of basic integer arithmetic

..then, the list of axioms are not complete! In the precise sense, that it is possible to come up statements in the theory that cannot be proven or dis-proven using the axioms. Such statements are also referred to as being independent of the axioms by mathematicians.

Now we will proceed to describe the reason the theorem is true! We need two concepts first: 1) Types of infinity (to quantify all possible statements and all possible proofs) ; 2) Godel encoding (so that proofs can be dealt with as functions of input statements).

——-

Types of infinity

TBD

Godel encoding

TBD

——-

The fundamental reason is that the space of possible statements is uncountably infinite while the space of possible proofs or deciding functions in an arithmetic theory is only countably infinite. So, there simply does not exist enough information to prove/disprove or decide all possible statements that can be expressed in the language of the theory, since there are too many of them. The integer arithmetic caveat is important for resulting in a theory allowing only a countably infinite (list-able) variety of deciding functions over a countably infinite (list-able) domain, thus encoding only countably infinite information. If the domain is not over the natural numbers, rather over an uncountably infinite space, then the functions in that theory can indeed encode enough information to possibly decide all statements expressible in the language of the theory. The nuance of being expressible is important. For example, the theory of real numbers is complete but we cannot use that fact to claim that natural number theory is also complete as a consequence just because it is a subset of real numbers. There is no way to express natural numbers from real numbers in first-order logic! There is no effective way to pick out that subset in the language of the theory and axioms.

Now let us actually prove the theorem for natural numbers. Let us list all possible deciding functions f_i(x) by row, where the function encodes the proof of the statement x. In the columns, let us have the values of the function by varying the input x over the integers. Since the domain is integers, the columns are list-able. It is sufficient to construct a statement which cannot be decided by the list of all possible deciding functions.

Obviously, we cannot prepare a statement beforehand and be sure it does not appear in the list. But given a list of all possible proofs/deciding functions, we can have a recipe for generating such a statement. The standard way to construct such a statement is by diagonal-ization. Define a property that is possessed by each number n as false when the nth element of the nth function is true. In essence, the property is defined as the negation of the diagonal elements. Now none of these functions match the property’s decision value atleast in one element of the column i.e, for one input case where the property has to be decided. So none of these functions in the list can be the exact decider or proof encoder of the so-constructed statement. Hence, any sufficiently complex theory of natural numbers is incomplete.