Microsoft Word goedel-duzi rtf

 

11

model are chosen for special axioms. On this condition, which is trivially met by sentences, 

the calculus is sound:  if T |– 

ϕ, then T |= ϕ. 

Another natural demand on special axioms is their mutual consistency. If the axioms 

contradicted each other, anything would be entailed by them, and any formula would be 

provable. The theory would be useless. Thus we define:  

A theory T is consistent iff there is a formula 

ϕ which is not provable in T. 

The strong version of the Completeness theorem claims that a formula 

ϕ is provable in a 

(consistent) theory T if and only if 

ϕ

 is logically entailed by its special axioms; in other words, 

iff 

ϕ is valid in every model of the theory; in (meta) symbols: 

      

 

 

 

T |= 

ϕ ⇔ T |– ϕ. 

The proof of the Completeness theorem is based on the following Lemma: 

Each consistent theory has a model. 

We need to prove that any formula 

ϕ that is logically entailed by T is also provable in T 

(if T |= 

ϕ then T |– ϕ). We will show that if T does not prove ϕ then ϕ is not logically entailed 

by T (if not T |– 

ϕ, then not T |= ϕ). Indeed, if T does not prove ϕ then T extended by ¬ϕ, i.e., 

{T 

∪ ¬ϕ}, does not prove ϕ as well (¬ϕ does not contradict T), which means that {T ∪ ¬ϕ} 

is consistent. Hence according to the Lemma there is a model 

M

 of 

 

{T 

∪ ¬ϕ}; however, 

M

 is a model of T in which 

ϕ is not true, which means that ϕ is not 

entailed by T.   

Hilbert expected the Completeness theorem; this result was valuable but it was not a 

surprise. Hilbert, however, expected more. He wanted to avoid any inconsistencies in 

mathematics. Arithmetic of natural numbers is a fundamental theory of mathematics. 

Consider the set 

ω of natural numbers {0, 1, 2, …}. Often we say that there are infinitely 

many of them: no matter how far we count, we can always count one more. But Cantor’s set 

theory actually says something much stronger: it says, e.g., that the power set P(

ω) of all the 

subsets of 

ω is a set as well, and is larger than ω (uncountable), which means that an actual 

infinite exists. Platonists have no trouble with actual infinities while thinkers like Kant, and 

later intuitionists reject them outright, allowing only potential infinities. For Hilbert, 

statements involving the infinite are ‘meaningless’ but useful, justified by their enormous 

power and utility. He thought of these as ‘ideal elements’ that can be added to the meaningful, 

finite, true mathematics as supplements to make things run smoothly and to derive new 

things. There is, however, a necessary condition that these elements are added in a consistent 

way. Hilbert declares: ‘there is one condition, albeit an absolutely necessary one connected 

with the method of ideal elements. That condition is a proof of consistency, for the extension 

of a domain by the addition of ideal elements is legitimate only if the extension does not 

cause contradictions’

14

. Hence Hilbert needed to find a consistent theory whose axioms 

characterise arithmetic of natural numbers completely, so that each arithmetic truth expressed 

in a formal language would be logically entailed by the axioms and thus derivable from them 

in a finite number of steps. Moreover, the set of axioms has to be fixed and initially well 

defined. Gödel’s two theorems on incompleteness show that these demands cannot be met. 

 

                                                 

14

 Brown (1999, p.66) 

---

 

12

3. Incompleteness. 

3.1. Incompleteness of arithmetic, Gödel’s first and second theorems    

The results on incompleteness were announced by Gödel in 1930 and the work “Über 

formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I” was 

published in 1931. This work contained a detailed proof of the Incompleteness theorem and a 

statement of the second theorem; both statements were formulated within the system of 

Principia Mathematica. In 1932 Gödel published in Vienna a short summary “Zum 

intuitionistischen Aussagenkalkül”, which was based on a theory that is nowadays called 

Peano arithmetic. I will now present

15

 these revolutionary results in terms of current systems 

of mathematical logic introduced above. 

Now we are not interested just in logical  truths, i.e., sentences true under every 

interpretation  of the FOPL language, but in sentences characterizing arithmetic of natural 

numbers which are true under the standard (intended) interpretation, which is the structure 

N

:

 

 

N

 = 

〈N, 0, S

N

, +

N

, *

N

, =

N

, 

≤

N

〉 

where N is the set of natural numbers, 0 is the number zero, S

N

 is the successor function 

(adding 1), +

N

 is the sum function (adding natural numbers), *

N 

is the multiplication function 

(on natural numbers), =

N 

is the relation of identity on natural numbers, and  

≤

N  

is the relation 

“less than or equal” of linear ordering on natural numbers.  

In order to be able to create formulas true in 

N

, the alphabet of the arithmetic language has 

to contain a constant symbol 0, unary functional symbol S, binary functional symbols + and *, 

and binary predicate symbols =, 

≤; the obvious intended interpretation associates these 

symbols with the respective elements of 

N

. In this language we can express sentences like 

∀x∀y (x+y) = (y+x), or ∃x (S(S(x)) ≤ 0), the former being true in the structure 

N

, the latter 

being false under this intended interpretation

16

. Actually, each sentence 

ϕ of the arithmetic 

language is either true or false under the intended interpretation. Hence if a theory is to 

characterise 

N

 completely, i.e., to demonstrate all the arithmetic truths, there must not be a 

sentence independent of T, i.e., neither provable nor refutable: 

A theory T is complete if T is consistent and for each sentence 

ϕ it holds that T proves either 

ϕ

 

or 

¬ϕ

, T |

− ϕ or T |− ¬ϕ;  in other words, each sentence 

ϕ

  is decidable in T. 

There are incomplete theories. Since according to the Completeness theorem, any 

consistent theory proves just the sentences entailed by the theory, to show that a theory is 

incomplete, we need to find an independent sentence 

ϕ that is neither entailed by the axioms 

of the theory, nor contradicts them (because then the theory would prove 

¬ϕ); in other words, 

a sentence true in some but not all models of the theory.  For instance, the theory O of partial 

ordering introduced in the previous chapter is not complete: there are partially ordered sets, 

like the set N ordered by 

≤

N

, which are ordered linearly, and partially ordered sets that are not 

ordered linearly, like the power set of a set S ordered by set-theoretical inclusion. Hence the 

formula 

ϕ

5

 

⎯ ∀x∀y [P(x,y) ∨ P(y,x)] ⎯is independent of the theory O = {ϕ

1

, 

ϕ

2

, 

ϕ

3

}. Also, 

the theory of linear ordering LO = {

ϕ

1

, 

ϕ

2

, 

ϕ

3

, 

ϕ

5

} is incomplete. The sentence independent of 

LO is the sentence 

ϕ

4

 

⎯ ∃x∀y P(x,y). There are also complete theories, like, e.g., the theory 

of discrete ordering or the theory of a successor, however the proof of their completeness is 

rather non-trivial.  

                                                 

15

 For details, see Hájek (1996), Švejdar (2002) 

16

 In the arithmetic language we use an infix notation when applying symbols like ‘+’, ‘*’, ‘

≤’, and instead of 

¬(S(x) = a) we write Sx ≠ a.  

---