4Predicate logic
II Logic and Set Theory
4.4 Peano Arithmetic
As an example, we will make the usual axioms for
N
into a first-order theory.
We take Ω =
{
0
, s,
+
, ×}
, and Π =
∅
. The arities are
α
(0) = 0
, α
(
s
) = 1
, α
(+) =
α(×) = 2.
The operation
s
is the successor operation, which should be thought of as
“+1”.
Our axioms are
Definition (Peano’s axioms). The axioms of Peano’s arithmetic (PA) are
(i) (∀x)¬(s(x) = 0).
(ii) (∀x)(∀y)((s(x) = s(y)) ⇒ (x = y)).
(iii) (∀y
1
) ···(∀y
n
)
[
p
[0
/x
]
∧
(
∀x
)(
p ⇒ p
[
s
(
x
)
/x
])]
⇒
(
∀x
)
p
. This is actually
infinitely many axioms — one for each formula
p
, free variables
y
1
, ··· , y
n
, x
,
i.e. it is an axiom scheme.
(iv) (∀x)(x + 0 = x).
(v) (∀x)(∀y)(x + s(y) = s(x + y)).
(vi) (∀x)(x ×0 = 0).
(vii) (∀x)(∀y)(x ×s(y) = (x + y) + x).
Note that our third axiom looks rather funny with all the (
∀y
i
) in front. Our
first guess at writing it would be
[p[0/x] ∧ (∀x)(p ⇒ p[s(x)/x])] ⇒ (∀x)p.
However, this is in fact not sufficient. Suppose we want to prove that for all
x
and
y
,
x
+
y
=
y
+
x
. The natural thing to do would be to fix a
y
and induct
on
x
(or the other way round). We want to be able to fix any
y
to do so. So
we need a (
∀y
) in front of our induction axiom, so that we can prove it for all
values of
y
all at once, instead of proving it once for
y
= 0, once for
y
= 1 , once
for
y
= 1 + 1 etc. This is important, since we might have an uncountable model
of PA, and we cannot name all
y
. When we actually think about it, we can just
forget about the (∀y
i
)s. But just remember that formally we need them.
We know that PA has a model
N
that is infinite. So it has an uncountable
model by Upward L¨owenheim-Skolem. Then clearly this model is not isomorphic
to
N
. However, we are also told that the axioms of arithmetic characterize
N
completely. Why is this so?
This is since Axiom 3 is not full induction, but a “first-order” version. The
proper induction axiom talks about subsets of N, i.e.
(∀S ⊆ N)((0 ∈ S ∧x ∈ S ⇒ s(x) ∈ S) ⇒ S = N).
However, there are uncountably many subsets of
N
, and countably many formulae
p. So our Axiom 3 only talks about some subsets of N, not all.
Now the important question is: is PA complete?
G¨odel’s incompleteness theorem says: no! There exists some
p
with PA
⊢ p
and PA ⊢ ¬p.
Hence, there is a p that is true in N, but PA ⊢ p.
Note that this does not contradict G¨odel’s completeness theorem. The
completeness theorem tells us that if
p
holds in every model of PA (not just in
N), then P A ⊢ p.