Microsoft Word goedel-duzi rtf

 

16

The authors of particular non-trivial applications are thus known as the authors of self-

reference formulas.  

An interesting self-reference application has been proposed by Alfred Tarski. He raised a 

question whether it is possible to reproduce Epimenides Liar paradox in arithmetic, i.e., to 

find a sentence claiming “I am not true”. Though it is possible to define Truth

n

 (in the 

standard model 

N

) for some subsets of formulas, a uniform definition of Truth for all 

arithmetic formulas is impossible. There is no arithmetic formula Tr(x) that would define the 

set Th(

N

)

19

 of coding numbers of formulas true in 

N 

(true arithmetic)

.

 Tarski statement can 

be formulated more generally: 

Let T be any consistent theory containing Q. Then there is no arithmetic formula Tr(x) 

such that for any arithmetic formula 

ϕ it holds that T |– ϕ ≡ Tr(<ϕ>). 

Proof: Suppose that Tr(x) exists. Then according to the diagonal lemma for the formula 

¬Tr(x) there is a sentence ω such that Q |– ω ≡ ¬Tr(<ω>). Since the theory T contains Q, it 

also holds that T |– 

ω ≡ ¬Tr(<ω>). Since the disquotation scheme

20

 is valid for the formula 

Tr(x), we have T |– 

ω  ≡ Tr(<ω>). It follows from both the equivalences that T proves  

ω → ¬ω and ¬ω → ω, which means that T proves ω & ¬ω. This contradicts the assumption 

on consistency of T.   

Tarski statement is known as the impossibility to define Truth in a theory. In particular it 

means that there is no formula Tr(x) such that for any sentence 

ϕ the following equivalence 

would hold: 

N

 |= 

ϕ if and only if 

N

 |= Tr(<

ϕ>).  

The diagonal self-reference lemma can be, of course, also applied to a formula 

ψ(x) that is 

known to exist. Gödel’s sentence claims “I am not provable”, Rosser’s sentence says that 

“each my proof is preceded by a smaller proof of my negation”. Hence the last idea of 

Gödel’s incompleteness proof is: apply the diagonal lemma on the formula 

¬

Pr

(x). We obtain 

Gödel’s diagonal formula 

ν

 such that Q |– 

ν

 

≡ ¬

Pr

(

<

ν

>)). Thus we have:  

ν

  iff  <

ν

> 

∉ Thm(T)  iff  

ν

  is not provable in T.   

This reminds us of the Liar paradox: the sentence claiming “I am not true” is neither true nor 

false. Gödel was inspired by such diagonal paradoxes. However, we have to keep in mind that 

there is a substantial distinction: whereas Epimenides’ sentence cannot be even expressed in 

the language of arithmetic

21

, the formula 

ν

  can be constructed as a well-formed formula of 

the language. 

Now 

ν

   is independent of T. It is true in 

N

 but not provable in T: indeed, if it were 

provable in T, then the formula 

Pr

(<

ν

>) would be true in 

N

. This formula is however a 

Σ-

formula, which means that it is provable in Q and thus in T as well. Now 

Pr

(<

ν

>) 

≡  ¬

ν

, 

which means that 

¬

ν

  is provable in T. We have derived that both 

ν

  and 

¬

ν

  are provable, 

which means that T is inconsistent. But it is not, because it has a model 

N.

 We have to refute 

the assumption that 

ν

  is provable. Hence 

¬

Pr

(<

ν

>) is true in 

N 

and 

ν

  is true in 

N, 

but 

ν

  is 

not provable: T is not complete, it does not demonstrate all the truths of arithmetic. 

To make these results more comprehensive, we now briefly recapitulate the main steps of 

the whole argument:  

                                                 

19

 So we use the notation Th(N) – theory (for true arithmetic) and Thm(T) – for the set of theorems of T. 

20

 The scheme is known as “It is snowing if it is snowing”: the sentence 

ω is true in N iff its code is an element 

of the set defined by Tr(x): 

ω ≡ Tr(<ω>).  

21

 The set Th(N) of numbers that encode true sentences of arithmetic is not definable by any formula 

ϕ. 

---

 

17

1.

 

A theory is adequate  if it encodes finite sequences of numbers and defines sequence 

operations such as concatenation. An arithmetic theory such as Peano arithmetic (PA) is 

adequate (so is, e.g., a set theory). 

2.

 

In an adequate theory T we can encode the syntax of terms, sentences (closed formulas) 

and proofs. This fact means that we can ask which facts about provability in T are 

provable in T itself. Let us denote the code of 

ϕ as <ϕ>. 

3.

 

Self-Reference (diagonal) lemma:  For any formula 

ϕ(x) (with one free variable) in an 

adequate theory there is a sentence 

ψ such that ψ iff ϕ(<ψ>). 

4.

 

Let 

Th(N)

 be the set of numbers that encode true sentences of arithmetic (i.e. formulas 

true in the standard model of arithmetic), and 

Thm(T)

 the set of numbers that encode 

sentences provable in an adequate (sound) theory T. Since the theory is sound, the latter is 

a subset of the former: 

Thm(T) 

⊆ 

Th(N)

. It would be nice if they were the same; in that 

case the theory T would be complete.   

5.

 

No such luck if the theory T is recursively axiomatized, i.e., if the set of axioms is 

computable in the following sense: there is an algorithm that given an input formula 

ϕ the 

algorithm computes a Yes / No answer to the question whether 

ϕ is an axiom or not. 

Computability of the set of axioms and completeness of the theory T are two goals that 

cannot be met together, because: 

5.1.

 

The set 

Th(N)

 is not even definable by an arithmetic sentence (that would be true if 

its number were in the set and false if not): Let n be a number such that n 

∉ 

Th(N)

. 

Then by the Self Reference (3) there is a sentence 

ϕ such that <ϕ> = n. Hence ϕ iff 

<

ϕ>  ∉ 

Th(N)

 iff 

ϕ is not true in N iff not ϕ – contradiction. There is no such ϕ. 

Since undefinable implies uncomputable there will never be a program that would 

decide whether an arithmetic sentence is true or false (in the standard model of 

arithmetic). 

5.2.

 

The set 

Thm(T) 

is definable in an adequate theory, say Q:  for any formula 

ϕ the 

number <

ϕ> is in 

Thm(T)

 iff 

ϕ is provable, for: the set of axioms is recursively 

enumerable, i.e., computable, so is the set of proofs that use these axioms and so is 

the set of provable formulas and thus so is the set 

Thm(T)

. Since computable implies 

definable in adequate theories, 

Thm(T) 

is definable. Let n be a number such that n 

∉ 

Thm(T)

. By the Self Reference (3) there is a sentence 

ϕ such that <ϕ> = n. Hence ϕ 

iff <

ϕ> ∉ 

Thm(T)

 iff 

ϕ is not provable. Now if ϕ is false then ϕ is provable. This is 

impossible in a sound theory: provable sentences are true. Hence 

ϕ is true but 

improvable. 

Now you may wonder: if we can algorithmically generate the set 

Thm(T)

, can’t we obtain 

all the true sentences of arithmetic? Unfortunately, we cannot. No matter how far shall we 

generate we will never reach all of them; there is no algorithm that would decide every 

formula, and there will always remain independent true formulas. We define: 

A theory T is decidable if the set 

Thm(T)

 of formulas provable in T is (generally) recursive. 

If a theory is recursively axiomatized and complete, then it is decidable. However, one of the 

consequences of Gödel’s incompleteness theorem is: 

No recursively axiomatized theory T that contains Q and has a model 

N,

 is decidable: 

there is no algorithm that would decide every formula 

ϕ (whether it is provable in the theory 

T or not). For, if we had such an algorithm, we could use it to extend the theory so that it were 

complete, which is impossible if the theory T is consistent (according to Rosser’s 

improvement of Gödel’s first theorem). 

---