Gödel's incompleteness theorem

Recently Published
Hofstadter's latest book, in which he examines the parallels between Gödel's incompleteness theorem and the the emergence of mind
My Review of I am a strange loop
Gödel's incompleteness theorem states that given a first order axiomatization of arithmetic, such as the first-order Peano axioms, there exist arithmetical statements which cannot be either proved or disproved using those axioms. The aim of this project is to write a computer program which will generate such an undecidable statement from the axioms. This will be done in the following steps

Gödel numbering

The first part of Gödel's theorem is to devise a mapping between sequences of arithmetical statements and positive integers, giving the Gödel number of a sequence of such statements. In computer terms this looks simple - if a structure is stored on a computer then it will be stored as a sequence of bytes, and a sequence of bytes can be interpreted as a positive integer. However, it may turn out that a different mapping allows the rest of the proof to proceed more smoothly.

Applet implementing a Gödel numbering numbering scheme

Checking a proof via a computer

A proof of an arithmetical statement is a sequence of arithmetical statements, starting with the axioms and ending with the statement to be proved. Such a proof must follow fixed rules of inference. This means it is possible to write a boolean function PROVES(X,Y) where Y an arithmetical statement , and X is a possible proof of Y. This function returns true if X is a valid proof, and false otherwise. The intention is to produce such a program, written in a well-known programming language. However for what follows it may be more efficient to express it in a specially devised programming language as well.

A proof system for arithmetic

A formal proof that 1+1=2

Gödel proof code applet

Unprovability expressed in terms of arithmetic

Arithmetical operations can be used to express the operations of a computer. Thus given a boolean function written for a computer, it is possible to translate it into an arithmetical statement. In particular we can transform the function PROVES(X,Y) into an arithmetical formula proves(x,y), where x and y are the Gödel numbers of X and Y. This transformation will be done in a similar way to that in which a programming language compiler would translate the code of PROVES(X,Y) into machine code.

Given the formula proves(x,y) we can then define unprovable(y) = ¬∃x(proves(x,y)), so we have a way of expressing the unprovability of arithmetical statements within arithmetic itself

Gödel arithmetization applet

Gödel's fixed point theorem

Given a formula with one free variable such as unprovable, the fixed point theorem (see for example http://math.yonsei.ac.kr/bkim/goedel.pdf ) shows how to construct an arithmetical statement Z with Gödel number z such that (Z⇔unprovable(z)) is a theorem of arithmetic. Then Z cannot be false, as this would mean that unprovable(z) is false, i.e. Z is provable and so true - a contradiction. Hence Z is true (so it cannot be proved false), meaning that unprovable(z) is true, which says that Z cannot be proved to be true. Thus Z is an undecidable statement, as required

Putting it all together

The Gödel number of the undecidable sentence

The undecidable Gödel sentence

Gödel's incompleteness theorem - project summary

Javadoc Documentation of Applets

Gödel arithmetization applet details

Recommended Reading

" ?>