# Decomposition into primes in Peano arithmetic.

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.

• I always suspected this was why Arnold Ross said that the fundamental theorem of arithmetic should be: "If $a\mid bc$ and $\gcd(a,b)=1$ then $a\mid c$" rather than unique factorization. – Thomas Andrews Jul 24 '17 at 21:40
• @Keen Thanks for asking this question! I have been wondering about this for a long time myself. – Bram28 Jul 24 '17 at 21:50
• @ThomasAndrews That one is certainly provable in PA! – Bram28 Jul 24 '17 at 21:51

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.

• So this has always been a question for me as well ... in order to prove something like the FTA, we need to talk about finite sequences, but saying that I can encode sequences using some prime number encoding assumes the FTA, and saying that I can code sequences using Godel's beta functions is assuming something about sequences. I mean, how can I prove the Chinese Remainder Theorem in PA? – Bram28 Jul 24 '17 at 21:44
• @Bram28: You use FTA as a meta theorem. You know it is true in the natural numbers, so you can use it. There are other methods that one can use as well to code sequences without resorting to FTA. – Asaf Karagila Jul 24 '17 at 21:52
• @Bram28 That's not really accurate. What's going on is that a statement $\varphi$ can be often be expressed in the language of PA, even if it's not a priori in the language of PA - but the claim that this statement has been successfully expressed must be made and proved in a larger language/theory, in particular one powerful enough to express $\varphi$ itself. So the task is twofold: (i) express the statement $\varphi$ in the language of PA; that is, find a sentence $\varphi'$ in the language of PA which is true iff $\varphi$ is. (ii) Prove $\varphi'$ in PA. (continued) – Noah Schweber Jul 24 '17 at 23:12
• Task (ii) is entirely inside PA. For task (i), though, the proof of $\varphi\iff\varphi'$ has to take place in a system powerful enough to express $\varphi\iff\varphi'$, so in particular one powerful enough to express $\varphi$. This sort of coding, though, is also what lets us "do mathematics inside set theory" - we are always looking at making definitions inside a theory and working (inside that theory) with those definitions, and arguing externally that they capture what we want them to. And, in fact, this is no different from how metatheory is deployed all throughout logic. (continued) – Noah Schweber Jul 24 '17 at 23:16
• When we prove completeness, or soundness, or incompleteness, or ..., we prove these theories inside some formal theory, which is implicit but may not be made explicit. Similarly, when we say that a statement is expressible inside PA via appropriate internal definitions, we are making this claim and proving it inside some formal theory, which is implicit but may not be made explicit. So if you're comfortable with any of logic in the first place you should be comfortable with coding into PA (and other theories). And we sometimes do study what theory is necessary to prove an encoding "works." – Noah Schweber Jul 24 '17 at 23:21

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.

• I'd mention finite sequences of integers are just sequences of bytes exactly as natural numbers. – reuns Jul 24 '17 at 23:23