Timeline for Induction, the infinitude of the primes, and workaday number theory
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 23, 2011 at 18:02 | vote | accept | David Feldman | ||
| Mar 23, 2011 at 14:55 | answer | added | Dave Marker | timeline score: 11 | |
| Mar 23, 2011 at 11:16 | answer | added | François G. Dorais | timeline score: 21 | |
| Mar 23, 2011 at 6:56 | comment | added | Gerhard Paseman | There is a 2008 paper by P. Nguyen on the infinitude of primes in bounded arithmetic. In IDelta0 + something weak like a definition of log(binomial coeff), he claims to prove Bertrand's postulate and some asymptotics. People (like me) unfamiliar with the issues might benefit from reading his introduction. Even with this, I think workaday number theory is too strong for 1) 2) and 3) to be applicable. But then, I am using (relatively) strong methods to do some elementary number theory, so I am biased. Gerhard "Ask Me About Jacobsthal's Function" Paseman, 2011.03.22 | |
| Mar 23, 2011 at 6:53 | comment | added | Andrej Bauer | @SJR: I was rather hoping that we could define a candidate function $f$, which given $n$ returns the first prime between $n$ and $2 n$, if it finds one, otherwise it returns $0$. I suppose the problem is to show that the function never returns $0$? | |
| Mar 23, 2011 at 6:44 | comment | added | KConrad | Concepts from model theory do have serious applications in workaday number theory. See the last section of math.berkeley.edu/~scanlon/papers/csp.pdf for a recent account of some of these. | |
| Mar 23, 2011 at 6:11 | comment | added | Sidney Raffer | @Andrej: The usual proofs of Bertrand's Postulate make use of the factorial function. Factorial can be defined in the standard integers by a first-order formula (using the operations $+, \cdot, 0, 1$) but the axioms of bounded arithmetic cannot prove that any such definition gives a total function. Indeed, there are nonstandard models of bounded arithmetic in which for any nonstandard $x$ and $y$ there is a standard $n$ such that $y<x^n$. This would rule out such a thing as $x!$. | |
| Mar 23, 2011 at 6:03 | history | edited | David Feldman | CC BY-SA 2.5 |
added 199 characters in body
|
| Mar 23, 2011 at 5:59 | comment | added | David Feldman | Don't Chebyshev's and Erdos' methods depend on binomial coefficients, which grow too fast for bounded arithmetic? | |
| Mar 23, 2011 at 5:07 | comment | added | Andrej Bauer | Isn't there always a prime between $n$ and $2n$? That seems like a good basis for proving infinitude of primes in bounded arithmetic. | |
| Mar 23, 2011 at 4:38 | history | asked | David Feldman | CC BY-SA 2.5 |