Gödel's fixed point theorem
This proof is based on Complete Proofs of Gödel's incompleteness theorems by B. Kim |
This is the fourth step of my construction of a Gödel sentence. The third step is a way of converting a function in a programming language into an arithmetical formula. Although I haven't finished that step yet I thought it would be useful to skip to this one, firstly because it provides the most insight about Gödel's proof, and secondly it gives some useful pointers as to how the third step should be done.
If you want to find out more on how to get into this way of thinking you should read I am a strange loop by Douglas Hofstadter. |
The thing is that, from step 1, we have a program which will convert between an arithmetical formula and an integer representing its coded form. Hence it is possible to think of any arithmetical formula which is written down just as a representation the corresponding integer and so we don't need to keep mentioning the
conversion function. However, we need to keep in mind the following three things
1: An integer within an arithmetical formula
In the system given, it won't work if you expect the integer to represent itself in a formula. As mentioned in 1+1=2 we can represent 1 as 0' (encoded as 11) and 2 as 0'' (encoded as 91). For large integers it looks like we might need lots of dashes, but of course we have addition and multiplication, and so 0'''''''''''''''''''''''''''''''''''''''''' (i.e. 42), for instance, can be represented as
0''''''''''*0''''+0''. We can use a base other than 10 if so wished, and the function num(x) which does this conversion in step 3 uses base 3.
Some related reading |
---|
This book gives a clear explanation of the basics of the proof of Gödel's incompleteness theorem. It would be useful for those wishing to get a clear idea of Gödel's theorem without getting too technical, and to go further than what is given in most popular treatments of the subject |
My review of Godel's proof |