MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

When I took model theory is an undergraduate, early on we wrestled with trying to state the fundamental theorem of arithmetic in the first order language of arithmetic. The problem was that we needed and unbounded and variable number of quantifiers Depending on each natural numbers factorization in the statement. I.e. For 6 we we need 2 quantifiers but for 110 needs 3. We stopped there because it illuatrated one of the shortcomings of the first order setting. We can quantify over a fixed number of primes and make the statement, but it will be false in general for any fixed prime, obviously.

I was recently refreshing my mind about non-standard models of arithmetic I found out that a form of unique factorization into primes does exist in these setting, but you may have non-standard primes in the factorization. So this means there is some first order sentence capturing the essence of FTA. I want to know what this sentence is. I am certain it will have to use some sort of recursive (=> definable In arithmetic) coding but the details I am unsure of. Can anyone assist me or point me onthe correct direction?

Thank you

share|cite|improve this question
First-order arithmetic can (in a way I don't know) define exponentiation, which lets then allows (in a way I can explain, if you can't figure it out) uniform coding of tuples, and then also the product of the entries of tuples, which is enough to state FTA. – Ricky Demer Nov 22 '10 at 17:37
up vote 2 down vote accepted

Possibly you will find this somewhat useful.

share|cite|improve this answer

As Ricky indicates above, talk of tuples of natural numbers can be coded as talk of natural numbers in the language of arithmetic (see e.g. Gödel's original incompleteness paper for a full, clear account; while he works there in a system of type theory rather than the first-order language of arithmetic, the idea of this coding is made plain), which gets around your issue of needing different numbers of quantifiers for different arguments. So there's no problem expressing FTA in the language of arithmetic.

As for proving FTA, it certainly can be done in Peano arithmetic (so FTA holds in all of its models, standard and nonstandard), but also in the much weaker $S^1_2$ if I'm not mistaken. Look up Sam Buss and bounded arithmetic if you're curious about that.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.