Decomposition into primes in Peano arithmetic.

Question

The language of first-order Peano arithmetic seems to me rather limited. As far as I am aware, you have only the symbols $S, 0, +, \times ,= $. Now the theorem of unique factorization into primes, states that for every $n$ natural number, there exists a unique finite increasing sequence of primes $(p_k)_{k \leq m}$, such that $n=p_0 \times \cdots \times p_m$, but since this language has no inherent notion of sequence, I don't know how this theorem can be written in this language.

Is there a simple way of working around this problem? I'd like to point out, I am not very familiar with logic and I am mostly self taught.

Answer 1

Yes.

You can easily code the notion of a finite sequence into the natural numbers with the language of arithmetic. There are many ways, for example Godel's $\beta$ function, or using prime powers.

But the idea is that you can uniquely code every finite sequence of natural numbers as another natural number. And you can do that in a recursive way (even primitive recursive), so that the decoding process of the length and coordinates are also recursive (and even primitive recursive).

Then prime decomposition becomes easy to state.

Answer 2

While PA doesn't have a built-in notion of finite sequences, we can still talk about finite sequences in PA. (And this means that talking about e.g. prime factorization is easily done in PA.)

This is easy to see if we consider PA augmented by exponentiation: then we can code any sequence $\langle a_1, ..., a_n\rangle$ by the number $2^{a_1+1}3^{a_2+1}...p_n^{a_n+1}$ (think about why we need the "$+1$"). Basic facts about sequences can then be expressed and handled appropriately.

In PA itself, this is a bit trickier, but can still be done using a clever application of the Chinese remainder theorem, discovered by Godel.