Timeline for Computable nonstandard models for weak systems of arithmetic
Current License: CC BY-SA 2.5
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:57 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Sep 9, 2010 at 20:16 | vote | accept | CommunityBot | ||
| Sep 9, 2010 at 19:55 | comment | added | Joel David Hamkins | When $n$ is standard, which is all we care about here, we can compute the $n^{th}$ prime directly, outside of $M$, and then add $1$ to itself inside $M$ that many times. | |
| Sep 9, 2010 at 19:44 | comment | added | user5810 | Then, how do you define "p is the nth prime"? | |
| Sep 9, 2010 at 19:31 | comment | added | Joel David Hamkins | This is a fun exercise in coding and computability. It may be easiest to code a finite set $A$ with the product of primes $p_n$ for $n\in A$, where $p_n$ is the $n^{th}$ prime. Given a nonstandard model $M$ with code $c$, a standard $n$ is in the set coded by $c$ iff the prime $p_n$ divides $c$ in $M$. But if the $+$ and $\cdot$ of $M$ are computable, then so is the residue of $c$ mod $p$; just look for which one of $c,c+1,c+2,\ldots c+(p-1)$ is a multiple of $p$ in $M$, by exhaustive search for the missing factor. Thus, the decoding is computable. | |
| Sep 9, 2010 at 16:57 | comment | added | user5810 | Now, I've only managed to find one paper describing how to code sequences in PA, but that paper uses existential quantification in the decoding procedure. How can sets be coded so membership is computable from the model operations? | |
| Sep 9, 2010 at 11:45 | comment | added | Joel David Hamkins | Since the function taking $d$ to the code $c$ of that list of programs is primitive recursive, as well as the de-coding function, it seems that the argument also captures PRA. | |
| Sep 9, 2010 at 11:26 | history | answered | Joel David Hamkins | CC BY-SA 2.5 |