From Gödel to God

​“Gödel’s paper is difficult. Forty-six preliminary definitions, together with several important preliminary propositions, must be mastered before the main results are reached.” – Nagel, E. and Douglas R. Hofstadter. 2001. “Gödel’s proof, Rev. ed.” New York: New York University Press.

But fear not, we can grasp the essential idea behind it by constructing a “Mini Gödelian Machine”.

A Mini Gödelian Machine[1]

Let us consider a computing machine that prints out various expressions composed of the following five symbols: ~ P N ( )​.

An expression X is called printable if the machine can print it. We assume the machine is so programmed that any expression the machine can print will be printed sooner or later.

By the norm of an expression X, we mean the expression X(X), e.g. the norm of X: John is Reading is N(X): John is Reading(John is Reading). John is reading, “John is reading” and is therefore not self-referential. By a sentence we mean any expression of one of the following four forms (where X is any expression whatever).
(1) P(X)
(2) ~P(X)
(3) PN(X)         [Read: the norm of X is printable]
(4) ~PN(X)       [Read: the norm of X is not printable]

Informally, P stands for “printable”, ~ stands for not, and N stands for “the norm of”. And so we define P(X) to be true iff X is printable, ~P(X) to be true iff X is not printable, PN(X) to be true iff the norm of X is printable, and ~PN(X) to be true iff the norm of X is not printable.

We have now given a perfectly precise definition of what it means for a sentence to be true. We now assume that we are also given that the machine is completely accurate in that all sentences printed by the machine are true. It never prints any false sentences. Thus, for example, if the machine ever prints P(X), then X is really printable, and so the machine will print X sooner or later.

What about the converse? If X is printable, does it follow that P(X) is also printable? Not necessarily. If X is printable, then P(X) is certainly true, but that does not mean that P(X) must be printable. We are given that all printable sentences are true, but we are not given that all true sentences are printable! As a matter of fact, there is a sentence which is true but not printable: ~PN(~PN) [Read: It is not possible to print the norm of this expression(It is not possible to print the norm of this expression]! The norm of ~PN is the very sentence ~PN(~PN) and so the sentence is true iff it is not printable, or it's printable and not true. The latter alternative violates the given hypothesis that the machine never prints sentences that are not true. Hence the sentence must be true but the machine cannot print it.

Gödel took this insight and went about constructing the provability of propositions. What Gödel did was showed that within any axiomatic system, there would remain true propositions which cannot be proven within that system.

How he did it[2]
As a first step, Gödel showed how to assign a unique number, called the Gödel number, to every string of symbols in a system. This numbering allowed him to uniquely number not only random strings but also statements, theorems, and even entire arguments, valid or otherwise. For example, all these strings could be represented:
4 + 9 = 13
4 + 9 = 1962
∀x ∃y[x + y = 3]
=48<+33-=7=


Because Gödel numbering worked at the level of the string, literally nothing that could be expressed in the system escaped his numbering, including that last string, which is meaningless.

Next, he showed how to use the system to build special statements called meta-statements, which referred to other statements. For example:
The statement “4 + 9 = 13” is a theorem.
The statement “4 + 9 = 13” is not a theorem.
The statement “4 + 9 = 13” includes the symbol “3.”
There exists a proof that the statement “4 + 9 = 13” is a theorem.

These meta-statements themselves were just statements, each with its own Gödel number. In this way, one meta-statement could refer to another meta-statement. A meta-statement could even refer to itself. For example:

“There does not exist a proof that this statement is a theorem.”

The paradox in the previous statement is even more subtle than it appears because Gödel built the statement to guarantee that at the level of semantics, the statement is a tautology. But consider the following:

  • If the statement can be derived as a theorem, then it isn’t a theorem, so the contradiction of the statement can also be derived as a theorem, making the system by definition inconsistent.
  • If the statement can’t be derived as a theorem, then the system is by definition incomplete.


If it sounds complicated, that’s because it is. And we’ve only scratched the surface. Understanding what Gödel accomplished is fascinating but understanding how he accomplished it is something that even most mathematicians have only attained in a more or less sketchy fashion.


[1] As outlined by: Smullyan, Raymond M. 2014. “A Beginner’s Guide to Mathematical Logic”. Dover Publications, Inc.

[2] As outlined by: Zagarelli, M. 2007. “Logic for Dummies”. New Jersey: John Wiley & Sons, Inc.