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

Improve this question
$\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
    Commented Nov 22, 2010 at 17:37

2 Answers 2

Reset to default
2
$\begingroup$

Possibly you will find this somewhat useful.

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .