Proof of Proposition 6. This proof uses Fact 5, the converse Barcan formula.
Strictly speaking, variables in Peano arithmetic are supposed to refer to natural numbers, and axioms like
reflect this. But in this post, we have been treating variables like rational numbers! In fact, there are ways of talking about rational numbers using Peano arithmetic, and so far in this post we haven’t bothered to write them out. But for this proof it will be important to distinguish between naturals and rationals. First we’ll prove literal readings of (a) - (e) — that is, we’ll assume variables refer to natural numbers. Then we’ll indicate how to extend the proofs to rational versions of the Lemma.
Proof of Proposition 6. This proof uses Fact 5, the converse Barcan formula.
Strictly speaking, variables in Peano arithmetic are supposed to refer to natural numbers, and axioms like
(a)
(b)
(c) Starting from the fourth line in the proof of (b),
operatorname{Concat} is a recursive function such that
so
(d) We proceed by induction on y. The base case:
Now for the induction step, which implicitly uses part (a) in almost every step:
(e)
Now we consider rational numbers. Every rational number x can be written as
where x,x′, and x′′ are natural numbers. So one way to represent a rational-valued variable in Peano arithmetic is with a triple
Rearranging, we get xy′′ x y′x′′ y′=yx′′ y x′y′′ x′
This condition is expressible in Peano arithmetic, and is how we can express equality of two rationals.
We can prove a rational version of (b) using the natural version of (b) and repeated application of the natural versions of (c) and (d):
With similar strategies one can prove rational versions of (a), (c), (d), and (e). Then we can prove the rational version of (f) directly:
(f)
square