Gödel’s theorem had made it clear that no single formal system could be devised that would en- able all mathematical truths, even those expressible in terms of basic operations on the natural numbers, to be provided with a formal proof.
Gödel’s Proof
Gödel proceeded to define a code by means of which each expression of a formal system would have its own natural number, what has come to be called its Gödel number, associated with it.
Working with a particular formal system loosely based on that of Whitehead and Russell and exploiting [the idea that expressions of the system that represent propositions about the natural numbers might be seen by someone privy to the code as also making assertions, incidentally as it were, about the system itself.]
Gödel showed how to con- struct a remarkable expression of the system we may designate as U.
There are true statements unprovable in the given system.
We write N = {0,1,2,...} for the set of natural numbers. A function f : N → N is called computable if there is an algorithm that given an x ∈ N will compute f (x).
Here the notion of algorithm is assumed to involve no restriction as to the amount of time or space required to complete a computation.
Finally a set S ⊆ N is called computable if its characteristic function CS (x) = {1 if x [something] S... is computable.
Computability theory provides a perspective from which it can be seen that incompleteness is a pervasive fundamental property not dependent on a trifling trick.