Information Technology Reference
In-Depth Information
We conclude by giving the schema of a sketch of Godel's famous incompleteness
theorem [175, 173, 188], where logical incompleteness is strictly related to the no-
tion undecidability (formulae over a signature can be seen as strings of a particular
formal languages). Basic logical notions of first-order logic are outlined in Chap. 5.
Given a model
M
over a domain
D
,atheory
Φ
represents
a subset
A
of
D
,by
means of a formula
.
A theory is
g odelian
if it can represent any language of
RE
. A theory is
ax-
iomatic
if it is constituted by all the logical consequences, called theorems, de-
ducible, by means of a logical calculus (a deduction algorithm), from a finite set of
sentences, called axioms. A theory is
complete
if for any sentence
ϕ
(
x
)
with a free variable
x
,if
a
∈
A
⇔M |
=
ϕ
(
a
)
ϕ
of its signature
either
ϕ
or
¬
ϕ
belongs to the theory. A theory is
consistent
if there is no sentence
ϕ
such that both
belong to the theory.
The following lemmas are the basis of G odel's
incompleteness theorem
.
ϕ
and
¬
ϕ
Lemma 6.8.
The Peano Arithmetic PA is g odelian.
The previous lemma was proved by Godel via a method, called
syntax arithmetiza-
tion
, able to translate in arithmetical terms the logical notions of first-order theories.
Lemma 6.9 (G odel).
Any consistent axiomatic theory that is complete is decidable.
An informal argument proving the previous lemma is the following. In order to
decide if
, generate all the theorems you can deduce
from the axioms, by the completeness of
ϕ
is a theorem of a theory
Φ
Φ
either
ϕ
or
¬
ϕ
will be generated. In the
first case
ϕ
is a theorem, in the other case
ϕ
is not a theorem; both cases cannot
occur because
is assumed to be consistent.
We know that there is a language
K
that is a RE language, but it is not decidable.
This fact implies the following proposition.
Φ
Lemma 6.10.
If a consistent theory
Φ
is decidable, then it cannot be g odelian.
Proof.
If
Φ
were g odelian then
Φ
should represent the set
K
in
RE
, which is not
decidable, that is,
a
∈
K
⇔
Φ
|
=
ϕ
(
a
)
, for some formula
ϕ
(
x
)
with a free variable.
But, being
Φ
decidable, the theorems of
Φ
are a decidable set, therefore also the
subset of sentences
, are a decidable set. Therefore,
K
should be decidable, against the hypothesis that
K
is not decidable.
ϕ
(
a
)
, which are theorems of
Φ
No g odelian axiomatic theory can deduce all the arithmetical true sentences (that,
of course, are a complete theory), as it is stated by the following theorem.
Theorem 6.11.
PA is incomplete.
In fact,
PA
is axiomatic and g odelian. If it would be complete, then it should be
decidable for Lemma 6.9, but this should contradict, by Lemma 6.10, its property
of being g odelian.
Godel Incompleteness says that there are true arithmetical propositions that can-
not be deduced from
PA
axioms. In general, arithmetics cannot be axiomatized in
FOL. This incompleteness, in the original proof of G odel, was proved by using an
