Timeline for Natural Numbers
Current License: CC BY-SA 4.0
13 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 23 at 17:54 | history | became hot network question | |||
| Apr 23 at 14:29 | comment | added | Joel David Hamkins | The importance of the observation for computable model theory is usually taken to be that having a computable model in an infinite language imposes a uniform computability requirement that may not otherwise be apparent if one thinks merely about assertions in the language, which cannot span over the whole signature. A weaker but still natural concept of "computable model", after all, might drop the uniformity and just ask that atomic truth is computable for any given formula separately. | |
| Apr 23 at 14:29 | vote | accept | Speltzu | ||
| Apr 23 at 14:18 | comment | added | Joel David Hamkins | Yes, I make that point in my answer. This theorem is a standard observation in computable model theory, and seems to me very likely what the OP has intended. | |
| Apr 23 at 14:17 | comment | added | Emil Jeřábek | @JoelDavidHamkins If you don't allow "expressing" predicates other than the basic relations, then there is no point in talking about models at all. The assertion then degenerates to just that there is no uniformly decidable enumeration of all decidable sets. | |
| Apr 23 at 13:35 | history | edited | Joel David Hamkins |
edited tags
|
|
| Apr 23 at 13:04 | comment | added | Joel David Hamkins | The question could be improved by speaking of the unary relations as being realized as the extension of one of the predicates, rather than merely "expressible". | |
| Apr 23 at 12:49 | comment | added | Joel David Hamkins | @EmilJeřábek I think I give a sensible reading of the question, where the claim is correct. Namely, you can't have a computable model where every recursive relation appears as one of the predicates. | |
| Apr 23 at 12:45 | answer | added | Joel David Hamkins | timeline score: 10 | |
| Apr 23 at 10:19 | comment | added | Emil Jeřábek | It’s unclear what $L^N$ means, but under any sensible reading, the standard model of arithmetic $(\mathbb N,+,\cdot)$ is a counterexample (it is a recursive structure, and all recursive relations are definable in it). | |
| Apr 23 at 10:16 | review | Close votes | |||
| May 2 at 3:06 | |||||
| Apr 23 at 10:06 | comment | added | YCor | A more specific title (than "Natural numbers") would be useful (here, or at MathSE if the question is more suitable there). In which context did the question arise? | |
| Apr 23 at 9:54 | history | asked | Speltzu | CC BY-SA 4.0 |