Timeline for Is multiplication implicitly definable from successor?
Current License: CC BY-SA 4.0
32 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 12, 2022 at 14:12 | history | edited | user44143 | CC BY-SA 4.0 |
added reference to Julia Robinson's thesis
|
| Jul 11, 2022 at 12:54 | vote | accept | Joel David Hamkins | ||
| Jul 10, 2022 at 12:33 | comment | added | Joel David Hamkins | @NoahSchweber Actually, I have a new plan. I have asked a question specifically about transitivity, and I would encourage you to post the forcing answer there. mathoverflow.net/q/426359/1946 | |
| Jul 10, 2022 at 4:32 | answer | added | user44143 | timeline score: 22 | |
| Jul 10, 2022 at 2:35 | comment | added | Akiva Weinberger | That last example, of first-order truth being implicitly but not explicitly definable in $(\Bbb N,+,\cdot,0,1,<)$, is really interesting. Is there a simpler example of this, of an implicit definition (that you'd be willing to explicitly write out) that defines only one relation which cannot be explicitly defined from that theory? | |
| Jul 10, 2022 at 0:42 | comment | added | Joel David Hamkins | Yes, please go ahead. | |
| Jul 10, 2022 at 0:39 | comment | added | Noah Schweber | @JoelDavidHamkins While it's not actually an answer, would you mind if I added the non-transitivity example as an answer (for relative permanence and accessibility)? | |
| Jul 9, 2022 at 20:36 | history | became hot network question | |||
| Jul 9, 2022 at 16:44 | answer | added | Joel David Hamkins | timeline score: 26 | |
| Jul 9, 2022 at 16:34 | comment | added | Joel David Hamkins | The answer is yes. The suggestion of Clemens seems to work. I am posting an answer now. | |
| Jul 9, 2022 at 16:26 | comment | added | Joel David Hamkins | I don't see a typo there---what did you have in mind? Being even is implicitly but not explicitly definable in that structure. | |
| Jul 9, 2022 at 16:22 | comment | added | Andrej Bauer | Is there a typo in the first example, namely the second occurrence of $\langle \mathbb{N}, S, 0\rangle$? | |
| Jul 9, 2022 at 16:14 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
Give update with Grabmayer proposal.
|
| Jul 9, 2022 at 14:59 | comment | added | Joel David Hamkins | I prefer to ask: is there a simpler, more elementary example? | |
| Jul 9, 2022 at 14:57 | comment | added | Noah Schweber | Yes, I think so too. (OK, so now: is there a natural example of intransitivity?) | |
| Jul 9, 2022 at 14:52 | comment | added | Joel David Hamkins | Noah, I think that example works to show intransitivity. With the truth predicate we can define Cohen real that is generic wrt all definable dense sets. But no such real can be implicitly definable, since if phi(G), then there will be some condition forcing this, in which there will be other reals also fulfilling phi. | |
| Jul 9, 2022 at 14:43 | comment | added | Joel David Hamkins | Incidentally, for the set theorists, one can iterate the implicit definability operator to form an implicit analogue of L. We call it Imp, and see more here: projecteuclid.org/journals/notre-dame-journal-of-formal-logic/… | |
| Jul 9, 2022 at 14:43 | comment | added | Noah Schweber | Hm, what about the following: still take $B$ to be truth, but now have $A$ be a sufficiently generic real (since ${\bf 0^{(\omega)}}$ lets us define lots of those). Genericity might prevent $A$ from being i.d. over $\mathbb{N}$. | |
| Jul 9, 2022 at 14:39 | comment | added | Noah Schweber | Ah, now I see; yes, that's right, and gives the hyperarithmeticity result in my previous comment. Sorry, I was misinterpreting what you meant by "jump" there! | |
| Jul 9, 2022 at 14:38 | comment | added | Joel David Hamkins | If I have an oracle for the jump of truth, I can define the truth predicate. So I can implicitly define that the jump has the property that the definition obeys the Tarski recursion, and that it is the jump of it. | |
| Jul 9, 2022 at 14:37 | comment | added | Noah Schweber | "truth is definable from the jump" What do you mean by that? Truth isn't definable, but the jump is. That said, you're right that my idea doesn't work: everything hyperarithmetic is (reducible to something which is) i.d. over $\mathbb{N}$. | |
| Jul 9, 2022 at 14:37 | comment | added | Joel David Hamkins | I don't think the proposal about jump-of-truth works, since truth is definable from the jump and so we can make a single implicit definition, even for truth about truth. | |
| Jul 9, 2022 at 14:37 | comment | added | Noah Schweber | @JoelDavidHamkins Ah, that's quite nice, I'd started thinking along those lines but didn't see how to get $+$ from $S$ and $\cdot$ so I dropped it. | |
| Jul 9, 2022 at 14:36 | comment | added | Joel David Hamkins | Meanwhile, Clemens Grabmeyer has an interesting proposal for a positive answer (see twitter.com/clegra/status/1545771851586146304). The idea is that + is definable from S and $\cdot$. | |
| Jul 9, 2022 at 14:35 | comment | added | Noah Schweber | @JoelDavidHamkins What about taking $\mathcal{M}$ to be $(\mathbb{N};+,\times)$, $B$ to be the truth predicate for arithmetic, and $A$ to be something like the Turing jump of $B$? | |
| Jul 9, 2022 at 14:34 | comment | added | Joel David Hamkins | @NoahSchweber This was going to be my example for that. | |
| Jul 9, 2022 at 14:12 | comment | added | Noah Schweber | Is there an obvious example that implicit definability isn't transitive (that is, $A$ is i.d. over $\mathcal{M}[B]$ and $B$ is i.d. over $\mathcal{M}$ but $A$ isn't i.d. over $\mathcal{M}$)? | |
| Jul 9, 2022 at 13:43 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 251 characters in body
|
| Jul 9, 2022 at 13:41 | comment | added | Joel David Hamkins | That would be great! | |
| Jul 9, 2022 at 13:35 | comment | added | Asaf Karagila♦ | Ever since I heard your story about Hugh sending you to disprove something, and you coming back with a proof, I always expect when "I expect the answer is no" to have someone come in and say "Oh, it's yes, and here's the proof". | |
| Jul 9, 2022 at 12:45 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 11 characters in body
|
| Jul 9, 2022 at 12:35 | history | asked | Joel David Hamkins | CC BY-SA 4.0 |