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