3Computability theory
III Logic
3.4 Logic
When we do logic, our theorems, proofs, rules etc. are all encoded as some finite
strings, which can certainly be encoded as numbers. Even though our theories
often have infinitely many axioms, the set of axioms is also decidable. It follows
from this that the set of theorems in our theory is semi-decidable, as to know if
something is a theorem, we can run through all possible strings and see if they
encode a proof of the statement. This also works if our set of axioms is just
semi-decidable, but we will need to use some diagonalization argument.
We start with a rather cute observation.
Theorem
(Craig’s theorem)
.
Every first-order theory with a semi-decidable set
of axioms has a decidable set of axioms.
Proof.
By assumption, there is a total computable function
f
such that the
axioms of the theory are exactly
{f
(
n
) :
n ∈ N}
. We write the
n
th axiom as
ϕ
n
.
The idea is to give an alternative axiom that says the same thing as
ϕ
n
, but
from the form of the new axiom itself, we can deduce the value of
n
, and so we
can compute
f
(
n
) to see if they agree. There are many possible ways to do this.
For example, we can say that we add
n
many useless brackets around
ϕ
n
and
take it as the new axiom.
Alternatively, without silly bracketing, we can take the nth axiom to be
φ
n
=
^
i<n
ϕ
i
!
→ ϕ
n
.
Then given any statement
ψ
, we can just keep computing
f
(1)
, f
(2)
, · · ·
, and
then if
ψ
=
φ
n
, then we will figure in finite time. Otherwise, we will, in finite
time, see that
ψ
doesn’t look like
f
(1)
∧ f
(2)
∧ · · ·
, and thus deduce it is not an
axiom.
We can also do some other fun things. Suppose we take our favorite copy of
N
with the usual 0 and successor functions. We let
T
be the theory of all true
first-order statements in
N
. We call this the theory of true arithmetic. We add
a constant c to this theory, and add axioms to say
0 < c, 1 < c, 2 < c, · · · .
Then by compactness, this has a model, and by Lowenheim–Skolem, it has a
countable model, which is a non-standard model of
N
. We wlog assume the
carrier set of this model is in fact N. How bad can this be?
Theorem
(Tennenbaum’s theorem)
.
For any countable non-standard model of
true arithmetic, the graph of + and × cannot be decidable.
Interestingly, computability theory offers us an easy proof of G¨odel’s incom-
pleteness theorem. We first note the following result:
Theorem.
The set of G¨odel numbers of machines that compute total functions
is not semi-decidable.
Proof.
Suppose it were. Then there is a computable total function
f
:
N → N
such that every computable total function is
{f
(
n
)
}
for some
n
. Now consider
the function
g(n) = {f(n)}(n) + 1.
This is a total computable function! But it is not
{f
(
n
)
}
for any
n
, because it
differs from {f(n)} at n.
Note that this proof is very explicit and constructive. If we are presented
with a function
{e}
:
N → N
, then there is an algorithm that returns an
n
such
that {n} is total, and is not in the image of {e}.
Definition
(Productive set)
.
A set
X ⊆ N
is productive if there is a total
computable function
f
:
N → N
such that for all
n ∈ N
, we have
f
(
n
)
∈
X \ (im{n}).
Then the theorem says the set of all machines that compute total functions
is productive.
In some sense, productive sets are “decidably non-semi-decidable”.
If we work in, say, ZFC, then there exists a fixed, canonical copy of
N
. We
note the following definition:
Definition
(Sound theory)
.
A sound theory of arithmetic is one all of whose
axioms are true in N.
This is not to be confused with consistency, which does not refer to any
model. For example, the theory of Peano arithmetic plus the statement that PA
is inconsistent is actually a consistent theory, but is unsound (if PA is consistent).
Theorem
(G¨odel’s incompleteness theorem)
.
Let
T
be a recursively axiomatized
theory of arithmetic, i.e. the set of axioms is semi-decidable (hence decidable).
Suppose
T
is sufficiently strong to talk about computability of functions (e.g.
Peano arithmetic is). Then there is some proposition true in
N
that cannot be
proven in T .
Proof.
We know the set of theorems of
T
is semi-decidable. So
{n
:
T `
{n} is a total function}
is semi-decidable. So there must be some total function
such that T does not prove it is total. In other words, T is not complete!
Ramsey theory
In Ramsey theory, we have the following famous result:
Theorem
(Ramsey’s theorem)
.
We write
N
(k)
for the set of all subsets of
N
of
size k. Suppose we partition N
(k)
in m many distinct pieces. Then there exists
some infinite
X ⊆ N
such that
X
is monochromatic, i.e.
X
(k)
⊆ N
(k)
lie entirely
within a partition.
The natural thing for us to do is to insert the word “decidable” everywhere
in the theorem, and see if it is true. Note that a partition of
N
(k)
into
k
pieces
is equivalently a function
N
(k)
→ {
0
,
1
, · · · , k −
1
}
, and it is not hard to encode
k
-subsets of
N
as natural numbers, e.g. by encoding them as an increasing
k
-tuple.
Thus, it makes sense for us to ask if the partition is decidable, then are we
guaranteed to have a decidable infinite monochromatic set?
One might expect not, because the proof of Ramsey’s theorem is rather
non-constructive. Indeed, we have the following theorem:
Theorem
(Jockusch)
.
There exists a decidable partition of
N
(3)
into two pieces
with no infinite decidable monochromatic set.
Proof.
We define a partition
ρ
:
N
(3)
→ {
0
,
1
}
as follows. Given
x < y < z
, we
define
ρ
(
{x, y, z}
) to be 0 if for any
p, d < x
, we have “
{p}
(
d
) halts in
y
steps iff
{p}
(
d
) halts in
z
steps”, and 1 otherwise. This is a rather weird colouring, but
let’s see what it gives us.
We first note that there can be no monochromatic set coloured 1, as given
any
x
, for sufficiently large
y
and
z
, we must have
{p}
(
d
) halts in
y
steps iff
{p}(d) halts in z steps.
We claim that an infinite decidable monochromatic set
A
for 0 will solve the
halting problem. Indeed, if we want to know if
{p}
halts on
d
, then we pick
some
x ∈ A
such that
p, d < x
. Then pick some
y ∈ A
such that
y > x
. Then
by construction of
ρ
, if
{p}
(
d
) halts at all, then it must halt in
x
steps, and we
can just check this.
Thus, there cannot be an infinite decidable monochromatic set for this
partition.
But what about partitioning
N
(2)
? The same trick doesn’t work, and the
situation is quite complex. We will not talk about this.