A Gödelian Puzzle (The Variant)


A Discusson Of The First Few Pages Of "Gödel's Incompletness Theorems" by Raymond M. Smullyan

In the frist few pages of this book Dr. Smullyan presents what he calls a "Gödelian Puzzle".  A previous page presents an anotation of that, while this page presents A Variant that Dr. Smullyan also presents.

Consider another computing machine that prints symbols.  The machine can only print expressions composed from the five symbols:

~ P N 1 0

In this case we represent the Natural numbers in binary notation then you can get them all by just using strings of 1's and 0's.

Every expression is assigned a number called the Gödel number of the expression.  The scheme to make this assignment is to assign each of the five symbols a Gödel number as follows:

       ~ gets 10
       P
gets 100
       N
gets 1000
       1
gets 10000
       0 gets 100000

The Gödel number of a compound expression is created by replacing each symbol by its Gödel number -- for example PNP would have the Gödel number 1001000100.

We next redefine norm of an expression to be the expression followed by its Gödel number -- For example the norm of PNP is the expression PNP1001000100. A sentance is now an expression of one for the four forms:

(1)     PX
(2)     PNX
(3)     ~PX
(4)     ~PNX

In the above X is any number written in binary form. Now PX is true if X is the Gödel number of a printable expression.  We call PNX true iff X is the Gödel number of an expression whos norm is printable.  We call ~PX true if PX is not true (X is not the Gödel number of a printable expression.  ~PNX true iff PNX is not true.

Again we are given that the machine never prints a false sentence. And again we are tasked with finding a true sentence that the machine cannot print.

(5)     ~PN101001000

You can see that the digits following the symbols ~PN make up the  Gödel number of ~PN thus the entire string is the norm of ~PN. and it is the same as (5) in the previous page that did not use numbers.