Timeline for Is multiplication implicitly definable from successor?
Current License: CC BY-SA 4.0
18 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 12, 2022 at 19:55 | comment | added | Joel David Hamkins | Yes, I was noticing the same thing. I wonder what happens with binary relations? I think with trinary, you could hope to implicitly define a pairing function, and then get the 4-ary relations using it. | |
| Jul 12, 2022 at 18:07 | comment | added | Will Sawin | It seems that a lesson of your answer and Fedor Pakhamov's answer about the primes is that the power of the notion of implicit definability depends more drastically than one would think on the number of variables of the relations. Almost no unary relations are implicitly definable over $(\mathbb N, S)$ but incredibly complex $4$-ary relations are. | |
| Jul 11, 2022 at 12:54 | vote | accept | Joel David Hamkins | ||
| Jul 10, 2022 at 21:32 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 290 characters in body
|
| Jul 10, 2022 at 3:13 | comment | added | Asaf Karagila♦ | Called it! | |
| Jul 10, 2022 at 2:50 | comment | added | user44143 | @AkivaWeinberger, I am writing that up as an answer. | |
| Jul 10, 2022 at 2:37 | comment | added | Akiva Weinberger | I'm not sure I understand - can you provide the implicit definition, written out explicitly? | |
| Jul 9, 2022 at 21:00 | comment | added | Geoffrey Irving | Follow-up question about the primes: mathoverflow.net/questions/426334/…. | |
| Jul 9, 2022 at 19:38 | comment | added | Geoffrey Irving | Let us continue this discussion in chat. | |
| Jul 9, 2022 at 18:17 | comment | added | Joel David Hamkins | That would be great! How do you know primality is not implicitly definable? | |
| Jul 9, 2022 at 18:07 | comment | added | Geoffrey Irving | In terms of your desire for a transitivity counterexample: primes is definable in terms of multiplication, but is not implicitly definable in terms of successor. | |
| Jul 9, 2022 at 17:46 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
Truth is implicitly definable from successor.
|
| Jul 9, 2022 at 17:34 | comment | added | Joel David Hamkins | Yes, we have that already, since truth is implicitly definable over +, *. But that doesn't seem to answer the question. | |
| Jul 9, 2022 at 17:32 | comment | added | Geoffrey Irving | My guess is that there is a single $n$-ary relation (roughly a universal Turing machine plus some extra features) which (1) is implicitly definable from successor and (2) can explicitly define any recursive function. In which case implicit definition is quite powerful. :) | |
| Jul 9, 2022 at 17:27 | comment | added | Joel David Hamkins | Good question. I don't see that this follows, since perhaps we have a PR function that isn't quite able to explicitly define the prior functions needed to realize it. But I have no counterexample. | |
| Jul 9, 2022 at 17:21 | comment | added | Geoffrey Irving | Does this mean that all recursive functions are explicitly definable in terms of a relation implicitly definable in terms of successor? | |
| Jul 9, 2022 at 16:52 | history | edited | Joel David Hamkins | CC BY-SA 4.0 |
added 35 characters in body
|
| Jul 9, 2022 at 16:44 | history | answered | Joel David Hamkins | CC BY-SA 4.0 |