2
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user5810
    Nov 22, 2010 at 17:37

2 Answers 2

2
$\begingroup$

Possibly you will find this somewhat useful.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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