Microsoft Word goedel-duzi rtf

 

15

mapping 

gn

 (Gödel’s numbering) assigning to each formula 

ϕ and to each proof d (in the 

theory T) a natural number 

gn

(

ϕ), 

gn

(d), respectively. Moreover, Gödel’s definition of the 

mapping is effective: there is an algorithm that calculates the value of 

gn

  at each formula or 

proof, and there is also an algorithm that to each Gödel’s number calculates its inverse 

syntactic image.  

The technique of numbering is not important. Any well-defined effective one-to-one 

mapping can serve the goal. Therefore we will use notation <

ϕ> for a code of a formula ϕ. 

However, what matters is the fact that due to unambiguous coding of syntactic objects by 

natural numbers formulas and other syntactic objects can be identified with natural numbers, 

and sets of formulas can be considered as sets of natural numbers. Thus, for instance, we can 

ask whether a set of formulas is recursive.  

To remember basic notions of the theory of recursive functions, we briefly recapitulate: 

(partial) recursive functions are exactly those functions that are algorithmically computable. A 

set S is recursively enumerable if there is a partial recursive function f such that S is a domain 

of f: Dom(f) = S. A set S is a (general) recursive set if its characteristic function is a (total) 

recursive function.  

We will also need the notion of a set  definable by a formula: Let 

D

 = 

〈D, …〉 be an 

interpretation structure for a language L. We say that a formula 

ϕ(x

1

,…,x

k

) of L, where 

variables x

1

,…,x

k

 are free in 

ϕ, defines a set A in 

D

 if A is the set of those k-tuples of elements 

a

1

,…,a

k

 of D (i.e., A 

⊆  D

k

) for which the formula 

ϕ is satisfied: 

D

 |= 

ϕ(x

1

,…,x

k

)[e] for a 

valuation e that assigns elements a

1

,…,a

k

 to variables x

1

,…,x

k

.  

Note that for any arithmetic formula 

ϕ(x

1

,…,x

k

) the definability of a set A in the standard 

model 

N

, i.e., the condition 

N

 |= 

ϕ(x

1

,…,x

k

)[e], where e assigns numbers n

1

,…,n

k

 to variables 

x

1

,…,x

k

, is equivalent to 

N

 |= 

ϕ(n

1

,…,n

k

).  

The second ingredient of the incompleteness proof is the 

Σ

-completeness of the theory Q. 

We are going to prove that PA and any (recursively axiomatizable) stronger 1

st

-order theory 

are incomplete. On the other hand there is a class of 

Σ-formulas such that each Σ-sentence 

true in 

N

 is provable in Q. An important property of the class of 

Σ-formulas is its exact 

correspondence to algorithmic computability: 

Σ-formulas define just all the algorithmically 

computable, i.e., recursively enumerable sets of natural numbers. Now the set Thm(T) of 

Gödel’s numbers of those formulas that are provable in T (theorems of T) is definable by a 

Σ-

formula

18

, which Gödel denoted by 

Bew

(x) – “beweisbar”, we will use 

Pr

(x). Hence: 

ϕ is 

provable in T if and only if <

ϕ> ∈ Thm(T), i.e., the sentence 

Pr

(

<

ϕ>) is valid in 

N,

 which is 

equivalent to 

N

 |= 

Pr

(

<

ϕ

>

), where 

<

ϕ

> 

is the numeral denoting Gödel’s number of 

ϕ. 

The third ingredient is Gödel’s diagonal lemma: For any formula 

ψ(x) of the arithmetic 

language with one free variable there is a sentence 

ϕ such that ϕ ≡ ψ (<ϕ>) is provable in Q.   

Hence the equality Q |– 

ϕ ≡ ψ(<ϕ>) with one unknown sentence ϕ has always, for any ψ,  

a solution, and the solution is independent of coding. We could say in a rather metaphoric 

way that 

ϕ says “I have a property ψ”. The proof of the lemma also contains the self-reference 

element, and it is not difficult. However, particular non-trivial applications of the self-

reference lemma are targets of importance. What matters is a proper choice of the formula 

ψ(x) so that the equality Q |– ϕ ≡ ψ(<ϕ>) had a solution ϕ with some interesting properties. 

                                                 

18

 This fact follows from the recursive axiomatization of T. Roughly: since the set of axioms is algorithmically 

computable, so is the set of proofs and so is the set Thm(T) of formulas provable in T. Hence Thm(T)

 

is a 

recursively enumerable set, which implies that Thm(T)

 

is definable by a 

Σ-formula.  

---