16
The authors of particular non-trivial applications are thus known as the authors of self-
reference formulas.
An interesting self-reference application has been proposed by Alfred Tarski. He raised a
question whether it is possible to reproduce Epimenides Liar paradox in arithmetic, i.e., to
find a sentence claiming “I am not true”. Though it is possible to define Truth
n
(in the
standard model
N
) for some subsets of formulas, a uniform definition of Truth for all
arithmetic formulas is impossible. There is
no arithmetic formula Tr(
x) that would define the
set Th(
N
)
19
of coding numbers of formulas true in
N
(true arithmetic)
.
Tarski statement can
be formulated more generally:
Let T be any consistent theory containing Q. Then there is no arithmetic formula Tr(x)
such that for any arithmetic formula
ϕ it holds that T |– ϕ ≡ Tr(<ϕ>).
Proof: Suppose that Tr(
x) exists. Then according to the diagonal lemma for the formula
¬Tr(x) there is a sentence ω such that Q |– ω ≡ ¬Tr(<ω>). Since the theory T contains Q, it
also holds that T |–
ω ≡ ¬Tr(<ω>). Since the disquotation scheme
20
is valid for the formula
Tr(x), we have T |–
ω ≡ Tr(<ω>). It follows from both the equivalences that T proves
ω → ¬ω and ¬ω → ω, which means that T proves ω & ¬ω. This contradicts the assumption
on consistency of T.
Tarski statement is known as the impossibility to define Truth in a theory. In particular it
means that there is no formula Tr(x) such that for any sentence
ϕ the following equivalence
would hold:
N
|=
ϕ if and only if
N
|= Tr(<
ϕ>).
The diagonal self-reference lemma can be, of course, also applied to a formula
ψ(x) that is
known to exist. Gödel’s sentence claims “I am not provable”, Rosser’s sentence says that
“each my proof is preceded by a smaller proof of my negation”. Hence the last idea of
Gödel’s incompleteness proof is: apply the diagonal lemma on the formula
¬
Pr
(x). We obtain
Gödel’s diagonal formula
ν
such that Q |–
ν
≡ ¬
Pr
(
<
ν
>)). Thus we have:
ν
iff <
ν
>
∉ Thm(T) iff
ν
is not provable in T.
This reminds us of the Liar paradox: the sentence claiming “I am not true” is neither true nor
false. Gödel was inspired by such diagonal paradoxes. However, we have to keep in mind that
there is a substantial distinction: whereas Epimenides’ sentence cannot be even expressed in
the language of arithmetic
21
, the formula
ν
can be constructed as a well-formed formula of
the language.
Now
ν
is independent of T. It is true in
N
but not provable in T: indeed, if it were
provable in T, then the formula
Pr
(<
ν
>) would be true in
N
. This formula is however a
Σ-
formula, which means that it is provable in Q and thus in T as well. Now
Pr
(<
ν
>)
≡ ¬
ν
,
which means that
¬
ν
is provable in T. We have derived that both
ν
and
¬
ν
are provable,
which means that T is inconsistent. But it is not, because it has a model
N.
We have to refute
the assumption that
ν
is provable. Hence
¬
Pr
(<
ν
>) is true in
N
and
ν
is true in
N
,
but
ν
is
not provable: T is not complete, it does not demonstrate all the truths of arithmetic.
To make these results more comprehensive, we now briefly recapitulate the main steps of
the whole argument:
19
So we use the notation Th(N) – theory (for true arithmetic) and Thm(T) – for the set of theorems of T.
20
The scheme is known as “It is snowing if it is snowing”: the sentence
ω is true in N iff its code is an element
of the set defined by Tr(x):
ω ≡ Tr(<ω>).
21
The set Th(N) of numbers that encode true sentences of arithmetic is not definable by any formula
ϕ.
17
1.
A theory is adequate if it encodes finite sequences of numbers and defines sequence
operations such as concatenation. An arithmetic theory such as Peano arithmetic (PA) is
adequate (so is, e.g., a set theory).
2.
In an adequate theory T we can encode the syntax of terms, sentences (closed formulas)
and proofs. This fact means that we can ask which facts about provability in T are
provable in T itself. Let us denote the code of
ϕ as <ϕ>.
3.
Self-Reference (diagonal) lemma:
For any formula
ϕ(x) (with one free variable) in an
adequate theory there is a sentence
ψ such that ψ iff ϕ(<ψ>).
4.
Let
Th(N)
be the set of numbers that encode true sentences of arithmetic (i.e. formulas
true in the standard model of arithmetic), and
Thm(T)
the set of numbers that encode
sentences provable in an adequate (sound) theory T. Since the theory is sound, the latter is
a subset of the former:
Thm(T)
⊆
Th(N)
. It would
be nice if they were the same; in that
case the theory T would be complete.
5.
No such luck if the theory T is recursively axiomatized, i.e., if the set of axioms is
computable in the following sense: there is an algorithm that given an input formula
ϕ the
algorithm computes a Yes / No answer to the question whether
ϕ is an axiom or not.
Computability of the set of axioms and completeness of the theory T are two goals that
cannot be met together, because:
5.1.
The set
Th(N)
is not even definable by an arithmetic sentence (that would be true if
its number were in the set and false if not): Let n be a number such that n
∉
Th(N)
.
Then by the Self Reference (3) there is a sentence
ϕ such that <ϕ> = n. Hence ϕ iff
<
ϕ> ∉
Th(N)
iff
ϕ is not true in N iff not ϕ – contradiction. There is no such ϕ.
Since undefinable implies uncomputable there will never be a program that would
decide whether an arithmetic sentence is true or false (in the standard model of
arithmetic).
5.2.
The set
Thm(T)
is definable in an adequate theory, say Q: for any formula
ϕ the
number <
ϕ> is in
Thm(T)
iff
ϕ is provable, for: the set of axioms is recursively
enumerable, i.e., computable, so is the set of proofs that use these axioms and so is
the set of provable formulas and thus so is the set
Thm(T)
. Since computable implies
definable in adequate theories,
Thm(T)
is definable. Let n be a number such that n
∉
Thm(T)
. By the Self Reference (3) there is a sentence
ϕ such that <ϕ> = n. Hence ϕ
iff <
ϕ> ∉
Thm(T)
iff
ϕ is not provable. Now if ϕ is false then ϕ is provable. This is
impossible in a sound theory: provable sentences are true. Hence
ϕ is true but
improvable.
Now you may wonder: if we can algorithmically generate the set
Thm(T)
, can’t we obtain
all the true sentences of arithmetic? Unfortunately, we cannot. No matter how far shall we
generate we will never reach all of them; there is no algorithm that would decide every
formula, and there will always remain independent true formulas. We define:
A theory T is decidable if the set
Thm(T)
of formulas provable in T is (generally) recursive.
If a theory is recursively axiomatized and complete, then it is decidable. However, one of the
consequences of Gödel’s incompleteness theorem is:
No recursively axiomatized theory T that contains Q and has a model
N,
is decidable:
there is no algorithm that would decide every formula
ϕ (whether it is provable in the theory
T or not). For, if we had such an algorithm, we could use it to extend the theory so that it were
complete, which is impossible if the theory T is consistent (according to Rosser’s
improvement of Gödel’s first theorem).