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.