Godel's Theorems

Cantor's Uncountability Theorem	Richard's Paradox
Godel's Incompleteness Theorem By Dale Myers
The Halting Problem	Tarski's Self-Reference Lemma
Cantor's Power-set Theorem	Tarski's Undefinability of Truth Theorem
Russell's Contradiction	Godel's First Incompleteness Theorem
The Liar Paradox	Godel's Second Incompleteness Theorem

Diagonalization arguments are clever but simple. Particular instances though have profound consequences. We'll start with Cantor's uncountability theorem and end with Godel's incompleteness theorems on truth and provability.

In the following, a sequence is an infinite sequence of 0's and 1's. Such a sequence is a function f : N -> {0,1} where N = {0,1,2,3, ...}.
Thus 10101010... is the function f with f(0) = 1, f(1) = 0, f(2) = 1, ... .
A sequence f is the characteristic function of the set {i : f(i) = 1}.
Thus 101010101... is the characteristic function of the set {0,2,4,6, ...}.
If X has characteristic function f(i), its complement has characteristic function 1 - f(i).

Cantor's Uncountability Theorem. There are uncountably many infinite sequences of 0's and 1's.

Proof. Suppose not.
Let f₀, f₁, f₂, ... be a list of all sequences.
Let f be the complement of the diagonal sequence f_i(i).
Thus f(i) = 1-f_i(i).
For each i, f differs from f_i at i.
Thus f is not in {f₀, f₁, f₂, ...}.
This contradicts the assumption that the list contained all sequences.

Corollary. There are uncountably many subsets of N. There are uncountably many reals.

Proof. The set of subsets of N is isomorphic to the set of 0-1 sequences via the bijection between subsets and characteristic functions.
There are uncountably many reals since the map which sends a 0-1 sequence 10101010... to the decimal .1010101... is 1-1.

The diagonal f_i(i) is constructed from the list f_j(i) by substituting i for j. Thus f can be constructed from the given list using just complementation and substitution.

In general, diagonalization shows that a set of objects (sequences, programs, provable theorems, true facts) either can't be listed, computed or defined in a nice way or else a simple-to-construct diagonal or self-referential object is not one of the set's objects.
Roughly either the objects can't be listed or they aren't closed under the substitution and complementation operations used to construct a diagonal.

Let's replace "sequences" by "sequences I can comprehend". Then either I can't comprehend the list of all such sequences, or I can't comprehend the diagonal. I figure that if I could comprehend the whole list in any way, I should also be able to comprehend the diagonal. Hence I must accept the first alternative: I can't comprehend the list of comprehensible sequences. The same applies to "sequences which God can comprehend". Thus omniscience has some limits.

Now replace "sequences" with "computable sequences".

Definition. A sequence f(i) is computable if there is a program which given input i computes f(i).

Are the computable sequences countable? Sure, a program is a finite sequence of symbols, say, ASCII symbols. There are only countably many finite sequences of symbols and so there are only countably many programs and hence only countably many computable sequences. But on the other hand --

Theorem. The set of computable sequences cannot be listed in a computable way.

Proof. Suppose f₀, f₁, f₂, ... , is a computable list of all computable sequences. By this we mean that there is a program P which given inputs j and i computes f_j(i).
Let f be the complement of the diagonal: f(i) = 1-f_i(i).
As before, f is not in the list f₀, f₁, f₂, ... .
But we can compute f as follows:
Read input i.
Apply P to the two inputs i and i.
Output 1 if P outputs 0 and output 0 if not.
Again we have a contradiction.

Pick your favorite programming language (if its COBOL, take a break and come back after your nap). Each program is a string of symbols.

Definition. A 0-1 sequence program is a string of symbols which
(1) is grammatically correct for the chosen programming language,
(2) has a single input variable i with domain N,
(3) has output statements only of the form "return 0" or "return 1",
(4) for every input i, produces an output ("halts") in a finite number of steps.

Any program which computes a sequence of 0's and 1's can easily be rewritten so as to satisfy (1)-(4).

Corollary. The set of 0-1 sequence programs cannot be listed in a computable way.

Proof. Suppose P₀, P₁, P₂, ... is a computable list of such programs.
Let f₀, f₁, f₂, ... be the list of sequences they compute. This list contains all computable sequences and it can be computed as follows:
Read inputs j and i.
Get program P_j from the given list.
Run program P_j on input i.
Output whatever P_j outputs.
This contradicts the theorem above.

We can computably list all strings.
We can also computably check conditions (1), (2), and (3) of the definition above.
Hence it is condition (4) which can't be checked in a computable way.
Thus --

Lemma. There is no program which each input p, determines if p is a program which halts on all of its inputs.

What about the simpler problem of checking that a program halts a particular input?

Halting Problem Theorem. There is no program R(p,i) which for each program p and each input i, can determine "yes" or "no" if p halts on i.

Proof. Suppose there is such a program R(p,i).
Let h be the program which on input p computes
R(p,0), R(p,1), R(p,2), ... until it finds an i such that R(p,i) is "no".
On finding such an i, it outputs i and halts.
If there is no such i, it searches forever and doesn't halt.
Now for any program p, we can decide whether or not p halts on all of its inputs:
p doesn't halt on all its inputs iff
h does halt on input p iff
R(h,p) is "yes".
Contradiction: by the lemma above, this is undecidable.

To see why halting problems are hard, consider the program which
on input n, looks for the first pair of twin primes greater than n.
Thus on input 8, we get 11,13.
Does this program halt on all inputs?

The extra-strength version of Cantor's theorem says that a set cannot count its own subsets.

Theorem (Cantor). The set P(X) of all subsets of a set X has a larger cardinality (number of elements) than the original set X.

Proof. Suppose they have the same number of elements.
Let f : X -> P(X) be a bijection between X and P(X).
(1) Let D = {x in X: x is not in f(x)}.
Since D is a subset of X and f is onto,
(2) D = f(d) for some d.
Thus d is in f(d) iff (by 2) d is in D iff (by 1) d is not in f(d).
This is a contradiction.

The set theoretic analog of listing a sequence of things, is grouping or "comprehending" a collection of things into a set. Sets are sort of unordered lists.

Russell's Contradiction. To formalize Cantor's set theory, Frege proposed the "comprehension" schema:
For every condition p(x) on x,
there is a set {x: p(x)} of elements which satisfy the condition.
Russell discovered that this omnipotent schema runs afoul of the diagonalization principal: you can't list (comprehend) things or you can't construct the diagonal.
Let D = {x: x not in x}.
Then D in D iff D not in D, a contradiction.

Quine proposed banning self-referential conditions like "x not in x" by requiring that the variables of the condition be stratifiable into layers with membership "x in y" allowed only when x is in a lower layer than y.
Zermelo proposed restricting the comprehension schema to subsets:
For every condition p(x) on x and every set Y,
there is a subset {x in Y : p(x)}.

Both proposals finesse Russel's contradiction but are there other inconsistencies in the closet? Once burned, logicians wanted a proof of consistency. None was found. Then Godel proved such consistency proofs are impossible. Zermelo's set theory has been universally accepted, but its consistency will always be a matter of faith. Quine's set theory would be just an historical footnote except for a long-standing open problem: Does the consistency of Zermelo's axioms imply the consistency of Quine's?

From sets which are members of themselves we now go to sentences which refer to themselves.

The Liar Paradox. "Truth" for English sentences is not definable in English.

Proof. Suppose it is. Then so is its complement "False".
Let s be the sentence "This sentence is false" .
Since the phrase "This sentence" refers to s, we have
s iff "This sentence is false" iff "s is false" iff not s.
A contradiction.

Richard's Paradox. Definability, the relation "the number n is defined by the (English) sentence s" not definable in English.

Proof. Suppose it is. Let n be the least number not definable by a sentence of less than 1000 symbols. Exercise: find the contradiction.

When translated into precise formal logic, these curiosities become Godel's magnum opus.
To make the transition, note that the sentence s which says
"This sentence is false"
is characterized up to logical equivalence as being the solution to the logical equation:
s iff "s is false".
Tarski's Self-Reference Lemma states that in adequate mathematical theories, such equations always have solutions.

A theory is adequate if it is strong enough to encode finite sequences of numbers and define simple sequence operations such as concatenation. In an adequate theory, we can encode the syntax of such things as terms, sentences, programs, and proofs. In particular, for every formula p, there is an object < p > which encodes this formula.

Even very weak number theories are adequate. So is set theory since numbers can be defined in set theory. For concreteness, let's pick number theory with our favorite axioms: +, x, 0, 1 have the associative, commutative, distributive, identity and cancellation properties. For any first-order formula p(x),
if p(0) and p(n) -> p(n+1) for all n, then p(n) holds for all n.

Tarski's Self-Reference Lemma. For any formula p(x) in an adequate theory, there is a sentence (formula without free variables) s such that
s iff p( < s > )
where < s > is the number which encodes s.

Proof. We omit the short but technical 5-line proof.

Suppose p(x) says "x has at most 1000 symbols".
By Tarski's Self-Reference Lemma, there is a solution s to:
s iff p( < s > ).
Thus s says "This sentence has at most 1000 symbols".

Since sentences of number theory can be coded up as numbers (the ASCII coding your computer uses does just fine), the set of true sentences can be identified with the set TRUTH of numbers which encode true sentences. Is this set definable in number theory?

Tarski's Undefinability of Truth Theorem. TRUTH, the set of numbers which encode true sentences of number theory, is not definable in number theory.

Proof. By the definition of TRUTH, for any sentence s,
(1) < s > is in TRUTH iff s is true.
Let s be the sentence "This sentence is false".
This sentence exists by Tarski's Self-Reference Lemma since it is the solution of
(2) s iff < s > is not in TRUTH.
Thus
s iff < s > is not in TRUTH iff s is not true iff not s.
This is a contradiction. We have used the law of the excluded middle and the consistency of the set of true sentences.

Since undefinable implies uncomputable, there will never be a program which can decide, for each sentence of number theory, whether the sentence is true or false.

Let PROVABLE be the set of sentences of number theory which are provable in our favorite axiom system. Since all our axioms are true, PROVABLE is a subset of TRUTH. It would be nice if they were the same. In this case our set of axioms would be complete. No such luck.

Definition. A theory is axiomatizable if it has a computably generated set of axioms.

Any sentence can be an axiom as long as it is true.

Godel's First Incompleteness Theorem. Any adequate axiomatizable theory is incomplete. In particular the sentence "This sentence is not provable" is true but not provable in the theory.

Proof. Given a computably generated set of axioms, let PROVABLE be the set of numbers which encode sentences which are provable from the given axioms.
Thus for any sentence s,
(1) < s > is in PROVABLE iff s is provable.
Since the set of axioms is computably generable,
so is the set of proofs which use these axioms and
so is the set of provable theorems and hence
so is PROVABLE, the set of encodings of provable theorems.
Since computable implies definable in adequate theories, PROVABLE is definable.
Let s be the sentence "This sentence is unprovable".
By Tarski, s exists since it is the solution of:
(2) s iff < s > is not in PROVABLE.
Thus
(3) s iff < s > is not in PROVABLE iff s is not provable.
Now (excluded middle again) s is either true or false.
If s is false, then by (3), s is provable.
This is impossible since provable sentences are true.
Thus s is true.
Thus by (3), s is not provable.
Hence s is true but unprovable.

Note 1. An analysis of the proof shows that the axioms don't have to be true. It suffices that (a) the system is consistent and (b) it can prove the basic facts needed to do arithmetical computations, e.g., prove that 2+2=4. The latter is needed to encode sequences of numbers and insure that computable sets are definable.

Note 2. Godel discovered that the sentence "This sentence is unprovable" was provably equivalent to the sentence CON:
"There is no < s > with both < s > and < not s > in PROVABLE".
CON is the formal statement that the system is consistent.
Since s was not provable, and since s and CON are equivalent,
CON is not provable. Thus --

Godel's Second Incompleteness Theorem. In any consistent axiomatizable theory (axiomatizable means the axioms can be computably generated) which can encode sequences of numbers (and thus the syntactic notions of "formula", "sentence", "proof") the consistency of the system is not provable in the system.

The theories of real numbers, of complex numbers, and of Euclidean geometry do have complete axiomatizations. Hence these theories have no true but unprovable sentences. The reason they escape the conclusion of the first incompleteness theorem is their inadequacy, they can't encode and computably deal with finite sequences.

There is a weak theological parallel in the Problem of Evil:

God doesn't exist since an ultimate ruler must be responsible for all things but a perfectly just being wouldn't be responsible for evil acts.

Actually this doesn't prove divine nonexistence: just that certain notions of being "ultimately responsible" and being "perfectly just" are inconsistent. Being ultimately responsible is a form of strength like being able to encode sequences of numbers. Being just is like the property of being self-consistent (inconsistency is the sole mathematical evil). As with diagonal arguments, you can't have both.

Godel biography Another biography

References about Godel

Godel's other results

Implications of Godel's theorems