Microsoft Word goedel-duzi rtf

 

5

founded in Brno, and the Society is an organiser of the International conference Logical 

Foundations of Mathematics, Computer Science and Physics – Kurt Gödel’s Legacy held 

regularly every four years. The first conference Gödel’96 was held in Brno on August 25–29, 

1996 on the occasion of Gödel’s 90

th

 birthday. 

2. Completeness of the 1

st

-order predicate logic proof calculus 

Now we are going to deal in more details with Gödel’s undoubtedly greatest results, 

namely those on completeness and incompleteness. There is a question, however: How to 

communicate something from those ingenious thoughts to a reader enthusiastic about rigorous 

science but not being a specialist in mathematical logic? There are at least three ways of doing 

so. First, to give a systematic historical exposition of the development of ideas that led to the 

major Gödel’s achievements. Second, to outline a philosophical interpretation of the results; 

and third, to enunciate basic ideas of Gödel’s work in a comprehensive way, in terms of 

current logical systems. Instead of doing the first, I briefly summarized Gödel’s life. Now I 

will confine myself to a mathematical exposition accompanied by brief philosophical and 

historical comments, because I am convinced that without a good understanding of the 

mathematical fundamentals any historical and philosophical considerations would not be 

well-founded. I will not reproduce original Gödel’s formulations and proofs. Instead, I will 

give an exposition from the point of view of current mathematical logic. I would just like to 

stress that Gödel’s results are mathematical facts.  Despite a strong resemblance to Liar 

paradox (and an obvious inspiration by it) they are no paradoxes, no hypotheses.  

2.1. First order predicate logic. 

In mathematical logic we work with closed well-formed formulas (called sentences) 

which in a less or more precise way render the logical structure (meaning) of our statements. 

We define, what it means that a formula 

ϕ is provable  (from some premises) and that a 

formula 

ϕ is true  (under some interpretation). The notions of provability and truth are two 

basic notions of mathematical logic; in which way are they related? Are provable formulas 

exactly those that are true (under some or all interpretations)? 

To make sense of this fundamental question, we have to explicate the notions of formula, 

provability and truth. Gödel’s results on completeness and incompleteness are two answers to 

our question 

⎯ one positive (and coming up to expectations of that time) and one negative (at 

that time an unexpected surprise). I will also try to elucidate a terminological confusion that is 

frequently caused by a nodding acquaintance with Gödel’s work, when two distinct notions of 

completeness are commingled: completeness of a proof calculus and completeness of an 

axiomatic theory (formulated within a calculus). I will also distinguish two notions of 

decidability (Entscheidbarkeit): decidability of a formula in a given theory and decidability of 

the whole theory.  

Language of the 1

st

-order predicate logic (FOPL) has nowadays become a mathematical 

stenography. Using the FOPL language we can characterise properties (denoted by predicate 

symbols of arity 1) of objects of a universe of discourse, and n-ary relations (denoted by 

predicate symbols of arity n) between objects of a universe of discourse. We can also express 

propositions that some (using existential quantifier 

∃) or all (using universal quantifier ∀) 

objects  x have a property P or are in a relation Q. The language is, however, formal: its 

symbols are devoid of meaning, they are empty signs. The reader might well wonder what 

sense it makes to claim that using empty signs we can express meaningful propositions. The 

answer is that we are walking a subtle midway path between truly empty signs and truly 

meaningful ones. To evaluate a formula we have to interpret the formula. For instance, the 

following formula 

ϕ 

---

 

6

∀x [P(x) → Q(x, a)] 

“claims”: for all x it holds that if x has a property P then this x is in a relation Q with an a. The 

question whether 

ϕ is true does not make sense until we know what ‘P’, ‘Q’ and ‘a’ mean. To 

evaluate a truth-value of 

ϕ we have to choose the universe of discourse over which the 

variable x can range. For instance, let the universe be the set of natural numbers 

N

. Second, 

we have to assign a subset of 

N 

to the predicate symbol ‘P’ and a binary relation over 

N 

(i.e., 

a subset of the Cartesian product 

N

 

× 

N

) to the predicate symbol ‘Q’. Let P stand for the set E 

of even numbers and Q for the relation D, “divisible by”. Third, we have to assign an element 

of 

N 

to the constant symbol ‘a’, let it be the number 2. Under this interpretation the formula 

ϕ 

is true (all the even numbers are divisible by 2). We say that the structure  

M

 = 

〈

N

, E, D, 2

〉, 

where the set E is assigned to the symbol ‘P’, the relation D to the symbol ‘Q’ and the number 

2 to the symbol ‘a’, is a model of the formula 

ϕ. There are other models of ϕ, for instance the 

structure  

M

’ = 

〈

N

, Pos, >, 0

〉, 

where Pos (assigned to the symbol ‘P’) is the set of positive numbers, > (assigned to the 

symbol ‘Q’) is the ordinary linear ordering of numbers and 0 is the number zero (assigned to 

the constant ‘a’). Under this interpretation 

ϕ claims that all the positive numbers are greater 

than zero, which is obviously true. The structure  

M

’’ = 

〈

N

, E, D, 3

〉 

is not a model of 

ϕ (it is not true that all the even numbers are divisible by 3). It is, however, a 

model of another formula 

ψ, namely  

∃x [P(x) & Q(x,a)], 

for there are such numbers that are even and divisible by 3. Formulas 

ϕ and ψ are satisfied by 

a model independently of a valuation of x; we say that x is bound here by quantifiers (general 

∀ or existential ∃, respectively), and the formulas ϕ,  ψ are closed. We will call closed 

formulas sentences.  

Some formulas may have free variables. For instance the formula [P(x) & Q(x,a)] is not 

closed; it cannot be evaluated even if a structure 

M’’

 is assigned to it by the realization of ‘P’, 

‘Q’ and ‘a’ (i.e., by assigning the set E to the symbol ‘P’, the relation D to the symbol ‘Q’ and 

the number 3 to the constant symbol ‘a’), because its truth-value in 

M’’ 

depends on a 

valuation  e of x. Valuation is a total function that assigns elements of the universe of 

discourse to variables. If e  assigns the number 2 to  x, the formula is false, if it assigns the 

number 6, the formula is true, it is satisfied by this valuation.   

Using these elementary examples, we illustrated almost all the basic notions we need: 

predicates of arity n  (here P of arity 1 and Q of arity 2), n-ary functional symbols (here 

constant a of arity 0), variables (here x), logical connectives (such as & (‘and’), 

∨ (‘or’), → 

(‘if … then’), 

¬ (‘not’)), quantifiers (∀–‘all’,  ∃–‘some’), and the notion of formula, its 

interpretation and a model. If a universe U of discourse is chosen, realization of predicate 

symbols consists in assigning subsets of the universe to symbols of arity 1, and n-ary relations 

over the universe U (subsets of Cartesian products U

n

) to n-ary predicate symbols. Constant 

symbols are realized as elements of the universe U, and n-ary functional symbols as mappings 

from the Cartesian product of the universe to the universe (U

n

 

→ U). Logical symbols such as 

---