Undecidable Sentences of L – Part 2

Theorem 1°:  If L is correct and if the set R* is expressible in  L, then L is incomplete.

Proof:  Assume L is correct and that R* is expressible.  Let K be the predicate that expresses R*.  The diagonalization of K is K(k), which by Lemma (D) is a Gödel sentence for R.  What this means is that K(k) is true if and only if the Gödel number for K(k) is in R.  Further, this says is that K(k) is true if and only if K(k) is refutable.  This leaves us two possibilities: (1) K(k) is true and refutable or (2) K(k) is false and not refutable.  Since L is correct, then (1) cannot be the case.  Therefore, (2) holds.  Since no false statements can be provable (because L is correct), then K(k) is neither provable or refutable.  This means K(k) is undecidable, and L is incomplete. Q.E.D.¹

Sentence K(k) can be thought of as saying “I am refutable” as opposed to our earlier H(h) which said, “I am not provable”.

---

1. Smullyan – GIT, Pg. 11.

Undecidable Sentences of L – Part 1

L is called consistent if no sentence is both provable and refutable in L, and inconsistent otherwise.  Note, this definition does not refer to the set of true sentences.  A sentence X is called decidable in L if it is either provable or refutable in L and undecidable otherwise.  The system L is called complete if every sentence is decidable, and incomplete otherwise.

Theorem 1:  If L is correct and if the set * is expressible in L, then L is incomplete.

Proof:  Assume L is correct and that set * is expressible.  From Lemma (D) it follows that there is a Gödel sentence for .  This Gödel sentence is a sentence that says that it is true if and only if it is not provable.   For L to be correct means every provable sentence is true and every refutable sentence is false.  If our Gödel sentence were false, then it would be provable.  But this contradicts the assumption that L is correct where every provable sentence is true.  Therefore, our Gödel sentence must be true and not provable.   This also means our Gödel sentence is not refutable because L is correct - only false sentences are refutable.  So, our Gödel sentence is neither provable or refutable.  By the definitions given above, our Gödel sentence is undecidable making system L incomplete.  Q.E.D.¹

---

1. Smullyan – GIT, Pgs. 10-11.

An Abstract Form of Gödel’s Theorem – Part 8

Lemma (D) – A Diagonal Lemma¹

Part I

Prove: For any set A, if A* is expressible in L, then there is a Gödel sentence for A.

We first assume that A* is expressible in L.  That means there is a predicate H(n) such that the following holds…

(1) H(n) ∈ T ↔ n ∈ A*

By definition of set A* the following holds…

(2) n∈ A* ↔ d(n) ∈ A.

By definition, d(n) is the Gödel number of the predicate expressing A* instantiated with its own Gödel number.   In other words, if we let h be the Gödel number of H(n), then…

(3) d(h) = g(H(h))

Substituting (2) and (3) into (1) we get the following equivalence…

(4) H(h) ∈ T ↔ g(H(h)) ∈ A

We now have in (4) above the very definition of a Gödel sentence.  As such, H(h) is the Gödel sentence for A.  Q.E.D. 

Part II

Prove: If L satisfies condition G₁, then for any set A expressible in L, there is a Gödel sentence for A.

Condition G₁ says, “For any set A expressible in L, the set A* is expressible in L.”  If we assume set A is expressible in L and condition G₁ holds, then set A* is expressible in L. Then from Lemma D – Part I it follows that there is a Gödel sentence for A.  Q.E.D.

What is interesting here is that Lemma D leads to a very quick proof of Theorem (GT).  Since we are given that set * is expressible in L, then by Lemma D there is a Gödel sentence for .  This sentence is nothing more than a sentence that is true if and only if it is not provable in L.  If it is true, then it is not provable, and if it is false, then it is provable.  Since we are given that L is correct (it cannot prove a false statement), then this Gödel sentence must be true and not provable.

---

1. Smullyan – GIT, Pgs. 8-9.

An Abstract Form of Gödel’s Theorem – Part 7

Gödel Sentences¹

A sentence E_n is called a Gödel sentence for a number set A if and only if the following condition holds:

(1) E_n ∈ T ↔ n∈ A

Remember that n is the Gödel number of E_n.  As such, a Gödel sentence for a number set A is a sentence asserting that its own Gödel number lies in A.  In other words…

(2) E_n : g(E_n) ∈ A

Now, this leads us to what we looked at in the last post regarding self-referential statements like “I am not provable.”  We noted in the previous post that the referent for ‘I’ was, presumably, the sentence “I am not provable.”  The same seems to be the case with E_n.  What is the referent of E_n in the expression g(E_n) ∈ A as found in (2) above?  Presumably, g(E_n) ∈ A!  This leads to the very interesting equivalence…

(3) g(E_n) = g(g(E_n) ∈ A)

Since n is the Gödel number of  E_n  we can substitute n into (3) giving us…

(4) n = g(n ∈ A)

This raises an interesting question. How could the Gödel number of an expression like n ∈ A be n?  At first blush it would seem to me that given any n along with direct Gödel number substitutions,  g(n ∈ A) > n would hold.   I suppose it is possible to express numbers in different ways.  For example, the number 100 could be expressed as 10².  If the Gödel number for 100 were greater than the Gödel number of 10², then it seems possible that the equivalence could hold.  But this seems very problematic to me.

Now, Gödel sentences are a critical part of the abstract form of the proof we have been considering.   Here is one of the equivalences from the proof (see statement (2)):

(5) *

Here, h is the Gödel number of H(h), and H(h) is a Gödel sentence for number set *.  That means…

(6) *

This then leads to the equivalence

(7) 

Since h is the Gödel number of H(h) then (7) becomes…

(8) 

This is the same form as (4) above, and runs into the same issues.   For Gödel’s proof to apply in general it seems to me that this equivalence must be able to hold for any given formal system with any given Gödel numbering scheme.  In fact, this issue seems to go beyond this for now that we have the value of h being  we can substitute this back into (8)…

(9)

Is it legitimate to continue the substitutions ad infinitum?  I am sure I am missing something here.

---

1. Smullyan – GIT, Pg. 8.

An Abstract Form of Gödel’s Theorem – Part 6

The Expressibility of *

A critical piece in this argument is the given that * is expressible.  Here is the definition for expressibility for this set:

(1) *

What is being said here is that the predicate H(n) expresses the set *. We will come back to this in a moment, but for now we will look at how Smullyan says that he will verify the hypothesis that * is expressible in L.  He will do this be separately verifying the following three conditions:¹

G₁: For any set A expressible in L, the set A* is expressible in L.
G₂: For any set A expressible in L, the set is expressible in L.
G₃: The set P is expressible in L.

Of course, G₁ and G₂ imply that for any set A, the set * is expressible in L. Smullyan notes that the verification of both G₁ and G₂ is a relatively simple matter. It is the verification of G₃ that is “extremely elaborate.”²

“I am not Provable”

Consider (1) above.  What does it mean to say that H(n)∈ T for some given number n?  Well, in this case we know that n represents the Gödel number of an expression that when instantiated with its own Gödel number becomes an unprovable sentence.  Let E_n be an expression whose Gödel number is n.  Let’s also say that the expression E_n(n) is unprovable.  Then we would say that H(n)∈ T.  So, H(n)∈ T if and only if  E_n(n) is unprovable.  Again, H(n) is a predicate that says, “n is the Gödel number of an expression that when instantiated with its own Gödel number is unprovable.”  This predicate of one free variable can itself be Gödelized to come up with its own Gödel number.  Let’s call it h and instantiate H(n) with it giving us: H(h).

Now, we know  H(h) ∈ T if and only if the expression H(h) is unprovable.  From this we concluded H(h) ∈ T must be true because if it is false, then H(h) is provable which contradicts our assumption that in L no false statements are provable.  But, let’s ask ourselves what H(h) actually says and see if we can determine anything from this.  It says, “h is the Gödel number of an expression that when instantiated with h is unprovable.” In other words:

• H(h): h is the Gödel number of an expression that when instantiated with h is not provable.
• H(h): h is the Gödel number of H(x) that when instantiated with h is not provable.
• H(h): H(h) is not provable.
• H(h): I am not provable.

So, we finally can see how Gödel created a sentence that says “I am not provable.”  We do not determine its truth of falsity by showing that there does not exist a proof for H(h).  Rather, we play on the assumptions that (A) all sentences must be either true or false, and (B) no false statements are provable.  Regarding (A), consider the sentence…

Lair: “I am not true.”

Is it true or is it false?  If it is true, then it immediately asserts its falsehood.  That is to say, if it is true, then it is false.  So, it is false.  But if it is false, then what it says is true.  So, its being false leads to it being true…and around and around we go.  Some, have tried to resolve this by pointing out the ungrounded nature of Liar.  Namely, they point out the referent for ‘I’ is problematic.  What does the ‘I’ refer to?  Itself?  If so, then we get…

Lair (1): “‘I am not true” is not true.”

But once again, we have an ‘I’ that lacks groundedness in terms of its referent.  This would give us…

Lair (2): “‘I am not true’ is not true’ is not true.”

….and on and on we go.  They argue from this that Liar is not really a sentence that can be said to be true or false.  Might not this objection equally apply to H(h)?  In the next post we will look at this briefly as we consider Gödel sentences.

---

1. Smullyan – GIT, Pg. 7.
2. Smullyan – GIT, Pg. 8.

An Abstract Form of Gödel’s Theorem – Part 5

OK, I finally feel as if I am really close to understanding the general idea here (see last post).  * is a set of natural numbers that are Gödel numbers of predicates with one free variable such that if these predicates are instantiated with their own Gödel numbers form sentences that are not provable in L.  Surely, * has members in it.  For example, it would be easy to construct a formal system of arithmetic that expresses the predicate “x is even” such that its own Gödel number is odd.  If we instantiate ‘x’ with this odd Gödel number, then the resulting statement is false.  Given that the formal system is consistent, then this statement is not provable in the system.  Here is one example of such a statement from Douglas Hofstadter’s formal system called Typographical Number Theory (TNT).¹

(1) 

This says that there exists a number such that if you multiply it by two it equals a´.  In other words, it says ”a´ is even.”  Since a´ is a free variable in (1) we have a predicate with one free variable.  The Gödel number of (1) is as follows…

(2) 333,262,636,262,236,123,123,666,111,262,123

Now, this is a very large number, and it is odd.  When we instantiate (1) with its own Gödel number we get…

(3)

where “…” represents 333,262,636,262,236,123,123,666,111,262,117 “S’s”!  Note, I had to translate (2) into the system of TNT because numbers like ’1′, ’2′, ’3′, etc… are not part of TNT.  Now, (3) says that there exists a number such that if you multiply it by 2 it gives you 333,262,636,262,236,123,123,666,111,262,123.  Now, this is false.  We also know independently that TNT is consistent so that it cannot prove any false statements.  Therefore, the Gödel number of (3) is a member of and (2) is a member of .  By the way, the Gödel number of (3) is a humongous number.  Here is what it looks like…

(4) 333,262,636,262,236,123,123,666,111,123,123,123,…(333,262,636,262,236,123,123,666,111,262,117 more sets of 123!)…123,123,123,666

So, we can construct expressions that have Gödel numbers that are members of .  We just need to construct expressions that we know if we instantiate it with their own Gödel number are false.  Since we assume the system is consistent, then these statements will not be provable.  But there is a problem here.  This method of populating set utilizes the fact that the expression instantiated with its own Gödel number will be false and therefore unprovable.  But, we need an expression that when instantiated with its own Gödel number is both true and unprovable!  How is this to be done?   

Well, this is where a neat little tick comes into play.  What would happen if we had a sentence such that if it were false would assert that it is provable?  Given that the system was consistent, this could not happen.  So, the sentence would have to be true, and if true, not-provable.  So, we just need to find a sentence that is true if and only if it is not-provable.  Here is how we do it.   

First, we recognize that if is expressible in L, then there is a predicate with one free variable that expresses this set of natural numbers. Let’s call it H(x).  It, too, will have its own Gödel number: g(H(x)).  Secondly,  we instantiate H(x) with its own Gödel number:  H(g(H(x))).  This expression has its own Gödel number: g(H(g(H(x)))).  If g(H(g(H(x)))) is an element of , then H(g(H(x))) is not provable.  If H(g(H(x))) happens to be true, then we have discovered a sentence that is both true and not provable.  But if system L is consistent, then H(g(H(x))) cannot be false!  Why?  Because if it is false, then it asserts that it is provable, and a consistent system cannot prove a false sentence!  So, H(g(H(x))) must be true.  If it is true, then it is not proveable and its Gödel number is a member of meaning that g(H(x)) is a member of ! 

Now what is the difference between H(g(H(x))) and (3) ?  (3) predicates ”evenness” whereas H(g(H(x))) predicates “provableness.”  So, to determine the truth of (3), we determine whether or not the number being referred to is in fact even.   But to determine the truth of H(g(H(x))) we don’t ask whether or not it is provable.  We simply note that if it is false, then it is provable, which cannot be the case with consistent systems.  That leaves us with it being true.  It is the expressibility of set that makes this type of argument possible. 

---

1. Hofstadter – GEB, Pgs. 204-230; 268.

An Abstract Form of Gödel’s Theorem – Part 4

In this post I want to explore the nature of the sets P, P*,   and * and the role they play in this proof.  So, we begin with P.

Set P

Set P is defined as the set of all Gödel numbers of provable expressions in L.   This set is made up of only natural numbers.  If E_n is an expression whose Gödel number is n, then the function g(E_n)=n.  By the same token,  g^-¹(n)=E_n.  So, if we apply the g^-¹(n) function to each element of P we will get the set of all provable expressions in P.

Set

Set is the compliment of set P relative to the natural numbers.  So,  Set is the set of all Gödel numbers of expressions in L that are not provable.  Once again, this set is made up of only natural numbers – all the remaining natural numbers not in P.  So, if we apply the g^-¹(n) function to each element of we will get the set of all expressions in P that are not provable.

Set P*

This set is a little more complicated for me.  To begin, let’s simply look at what any *-set, say A*.  It is defined as follows:

(1) (n∈A*) ↔ (d(n)∈A)

where d(n) is the Gödel number of an expression with one free variable instantiated with its own Gödel number.  Since g(E_n)=n, if E_n is a predicate with one free variable, then instantiating this expression with its own Gödel number gives us E_n(n).  This, itself, will have its own Gödel number.  We call that number d(n).  So, d(n)=g(E_n(n)).

So, what does that make A*? Well, first of all, it is a set of natural numbers.  But not only that, it is a set of natural numbers that are Gödel numbers.  But not only that, it is a set of Gödel numbers whose expressions when instantiated with their own Gödel number have Gödel numbers that are elements of A.  Here is the progression…

1. We have an expression that is a predicate with one free variable: E_n(x).
2. We determine the Gödel number of this expression: g(E_n(x))=n.
3. We instantiate the expression with its own Gödel number: E_n(n).
4. We determine the Gödel number of this expression: g(E_n(n))=d(n). 

Set A is made of d(n).   Given a set A, set A* is then determined as follows…

1. We convert the Gödel number in A back into an expression: g^-¹(d(n))=E_n(n).
2. We then turn this sentence into a predicate of one free variable: C(E_n(n))=E_n(x).
3. We then determine the Gödel number of this expression: g(E_n(x))=n.

Set A* is made up of n.  Again, all set A* is the a set of Gödel numbers representing predicates of one free variable such that when they are instantiated with themselves are expressions whose Gödel numbers are in A.

So, what about set P*?  Well, since P is the set of all Gödel numbers of provable expression in L, presumably, some of these provable expressions are expressions that have been instantiated with their own Gödel number.  So, P* is simply made up of the Gödel numbers of those expressions before they have been instantiated with their own Gödel number.   (Note: the set P* does not seem to have any Gödel numbers that represent provable expressions?  Why?  Because predicates are not provable.  Take for example the predicate, “x is even” where x is a variable.  It does not make sense to say that we can prove “x is even” apart from defining x.)

Set *

Now, we get to the crux of the issue.  The set is made up of Gödel numbers of those expressions that have been instantiated with their own Gödel number, and these expressions are not provable.   Let’s say these expressions have the Gödel number d(n)  So, set * is defined as follows…

(2) g(C(g^-¹(d(n)))))=n

That is ugly.  But, nevertheless, there it is. So, when it come right down to it, set * is simply the set of Gödel numbers of predicates of one free variable when instantiated with their own Gödel number become expressions that are not provable.

Now, what is really interesting here is that if the set * is expressible in L, then it entails a predicate expressing this set, and it, too, will have its own Gödel number.  Is the Gödel number of this predicate a member of * or not?¹ If so, then when one instantiates this predicate with its own Gödel number it produces a sentence that is not-provable.  If not, then when one instantiates this predicate with its own Gödel number it produces a sentence that is provable.  I feel we are very close to figuring out the general idea of what Gödel did.  However, it will have to wait for a future post.

---

1. This reminds me of those self-referencing paradoxes like the Grelling–Nelson paradox where an adjective is heterological if it does not describe itself.  For example, ‘long’ is heterological in the sense that ‘long’ is not a lengthy word.  So, is ‘heterological’ heterological?  That is to say, does ‘heterological’ describe itself?  If it does describe itself, then it is not heterological.  However, if ‘heterological’ is not heterological, then it does not describe itself!

An Abstract Form of Gödel’s Theorem – Part 3

Earlier we define P to be the set of sentences of L called the provable sentence of L.  In this post P will be the set of Gödel numbers of all the provable sentences of L instead of the set of expressions themselves.  Not only that, given any number set A, àwill stand for the compliment of A relative to the natural numbers.  So, à is the set of all natural numbers not in A.  So, if P is the set of Gödel numbers of all the provable sentences of L, then  is the set of Gödel numbers of all the non-provable sentences of L.

Theorem (GT) – After Gödel with Shades of Tarski¹

Prove:  There is a true sentence of L not provable in L.

Given: (1) The set * is expressible in L and (2) L is correct.

To begin, let’s examine our givens.  First off, when we say that * is expressible in L, we mean that there is some predicate of L that expresses *.  Let’s call this predicate H.  So, by the definition of expressibility that was given in an earlier post…

(1) *

where T is the set of all true sentences of L.   Secondly, when we say L is correct, then we are saying that no provable sentences in L can be false.

With those two ideas in place, the proof follows quickly.  Let h be the Gödel number of the predicate H.  Since (1) is true for all n, and in particular for n=h, then…

(2) *

In the previous post we called the Gödel number for the expression H(n) to be d(n).  Also, in the earlier post the set A* was defined as the set of all natural numbers such that d(n)∈A. If we let A be the set , then we get the following equivalence…

(3) 

Once again, this equivalence holds for all n, and in particular for n=h, which in turn gives us…

(4)

Since the sets  and  are compliments of one another, then it follows that…

(5)

Once again, this holds are all n, and in particular it will hold for the Gödel number for the expression H(n), which is d(h) giving us…

(6)

Substituting (6) into (4) gives us…

(7)

And substituting (7) into (2) gives us…

(8)

Since d(h) is the Gödel number for the expression H(h) then by definition of the set P…   is provable in L and is not provable in L.  Now, if H(h) is provable, then .  However, from (8) above, this means that H(h) is not in T! So, we would have a provable sentence that is not in T making it false.  But this contradicts our given that L is correct – namely, no provable sentences are false.  Now, if H(h) is not provable, then and from (8) above we get that H(h) is in T.  In other words, H(h) is a true sentence not provable in L.  Q.E.D.

For me, I am not quite completely clear on what took place above.  I can follow the symbol manipulation and understand the final argument, but what is exactly happening is still fuzzy for me.  In the next couple of posts I will try to look further at the nature of the sets P, P*, and * and the role they play in this proof.

---

1. Smullyan – GIT, Pg. 7.

An Abstract Form of Gödel’s Theorem – Part 2

Gödel Numbering and Diagonalization¹

Gödel Numbering 

Let g be a 1-1 function (bijective) which assigns to each expression E a natural number g(E) called the Gödel number of E.  This function uniquely pairs off each natural number (the domain of the function) with an expression E (the range of the function).  So, given any expression of E, there is one and only one natural number paired with it, and vice versa.  So, in a sense, the expressions of L can be referred to by natural numbers; namely, those natural numbers uniquely associated with each expression.  Each natural number is the Gödel number of some expression E.  So, we let E_n be an expression paired off with the natural number n so that  g(E_n)=n. 

Diagonalization

The diagonalization of E_n is the expression E_n(n).  If E_n is a predicate then the diagonalization of E_n is the instantiation of the predicate with n.  For example, let’s say the predicate “x is an even number” has a Gödel number of ’2′.  The diagonalization of this predicate is the sentence ”2 is an even number.”  So, if E_n is a predicate, then its diagonalization is a sentence, and this sentence is true if and only if E_n is satisfied by its own Gödel number n. 

Now, at this point we have an expression E_n whose Gödel number is n.  The diagonalization of E_n is E_n(n).  This expression will have its own Gödel number.  We will call this  Gödel number d(n) – the  Gödel number of the digonalization of E_n.  The function d(x) takes any number n (which is the Gödel number of E_n) and pairs it off with the Gödel number of the digonalization of E_n, that is to say, d(x) takes any number n and pairs it off with the Gödel number of E_n(n).  In other words, d(n)=g(E_n(n)).

Given any set of natural numbers A, then by A* we mean the set of all numbers n such that: 

(n∈A*) ↔ (d(n)∈A) or…

(n∈A*) ↔ (g(E_n(n))∈A)

So, what is A*?  Smullyan says that it is the inverse image of A under the diagonal function d(x), and therefore, it can be said that A* = d^-¹(A).  This is not easy for me to understand.  What I really do not understand is the expression E_n(n).  I can understand instantiating a predicate of one variable with its own Gödel number.  I used the example above of the predicate “x is even” with a Gödel number of ’2′.  In this case, E_n(n) is the sentence “2 is even.”  But most expressions are not going to be predicates of one variable.  They either will have multiple variables like ‘∀xy((x+y)=5)’ or no variables like ’1=1′.  What is E_n(n) in those cases?  Maybe, in the latter case E_n(n) is simply the same expression, but what about the former case?  If ‘∀xy((x+y)=5)’ has the Gödel number of 9, then what is E_n(n)? 

Edited to Add:   Smullyan is concerned only with a predicate of one variable that says something like “X is not provable.”  Not only that, he wants to take this kind of expression and instantiate itself through the use of its own Gödel number to create an expression like “This expression is not provable.”  As such, Smullyan is only concerned with those cases that are predicates of one variable where E_n(n) makes sense.  At least for now, I think this resolves my issue.     

---

 1. Smullyan – GIT, Pgs. 6-7.

An Abstract Form of Gödel’s Theorem – Part 1

Some Definitions¹  

1. Let E represent a denumerable set whose elements are the expressions of L.
2. Let S represent a subset of E whose elements are the sentences of L.
3. Let P represent a subset of S whose elements are the provable sentences of L.
4. Let R represent a subset of S whose elements are the refutable sentences of L.
5. Let H represent a subset of E whose elements are the predicates of L.  (For example, the expression “2 is an even number” is a sentence and can be true or false; whereas, the expression “X is an even number” is a predicate that is neither true or false. H represents expressions of the latter type.)
6. Let φ represent a function that assigns to every expression E and every natural number n an expression E(n).  The function is required to obey the condition that for every predicate H and every natural number n, the expression H(n) is a sentence.  (Informally, H(n) expresses the proposition that n is an element of the set named by H.  So, if H names the predicate “X is even,” then H(1) expresses the proposition that “1 is even.”)    
7. Let T represent a subset of S called the true sentences of L.  (Note: The predicate H is true for a number n if and only if H(n)∈T.)
8. The predicate H expresses A if and only if for every number n, n∈A↔H(n)∈T. (Informally, given the set A={2, 4, 6,…}, the predicate H=”X is even” expresses A because given any n in A the expression “n is even” is true.  Now, if A was the set of natural numbers, then H would not express A because there are elements of A where the expression “n is even” is false, ex., when n=3.)
9. The set A is expressible (nameable) in L if and only if there exists a predicate H that expresses A. 
10. L is called correct if every provable sentence is true and every refutable sentence is false.  This means that if L is correct, then P is a subset of T, and R is disjoint from T.

At this point, we are now interested in finding the sufficient conditions under which there are sentences of L that are true but not provable.  In other words, we are interested in finding the conditions where there are sentences that are elements of T but not P. 

---

1. Smullyan – GIT, Pgs. 5-6.