most recent 30 from http://mathoverflow.net 2013-05-18T16:12:59Z http://mathoverflow.net/feeds/question/46971 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/46971/fta-in-first-order-setting Elmore 2010-11-22T17:24:46Z 2010-11-22T18:42:36Z

<p>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. </p> <p>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? </p> <p>Thank you</p>

http://mathoverflow.net/questions/46971/fta-in-first-order-setting/46975#46975 Ed Dean 2010-11-22T18:02:05Z 2010-11-22T18:02:05Z

<p>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&ouml;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.</p> <p>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.</p>

http://mathoverflow.net/questions/46971/fta-in-first-order-setting/46982#46982 Todd Trimble 2010-11-22T18:42:36Z 2010-11-22T18:42:36Z

<p>Possibly you will find <a href="http://people.cs.uchicago.edu/~laci/REU09/tr9.pdf" rel="nofollow">this</a> somewhat useful. </p>