Timeline for Is there a simple instance of intransitivity for implicit definability?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 11, 2022 at 8:24 | comment | added | Geoffrey Irving | And we can simplify this example slightly: the same argument applies to the set of powers of two, which is implicitly definable in terms of addition. | |
| Jul 11, 2022 at 3:20 | comment | added | Noah Schweber | The forcing argument does give a "local" non-collapsing result, namely that for every predicate $A$ on $\mathbb{N}$ there is a properly $(\mathbb{N};\times,+,A)$-i.d. relation. But of course that's not at all the same as "the hierarchy doesn't collapse," which is bonkers. My bad! | |
| Jul 10, 2022 at 22:51 | comment | added | Noah Schweber | Oh wait, I was being silly: it does collapse! After a couple levels you get all the $0^\alpha$s, everything in the implicit definability hierarchy is hyperarithmetic, and every hyperarithmetic set is computable relative to some $0^\alpha$. Whoops ... | |
| Jul 10, 2022 at 22:50 | comment | added | Noah Schweber | That's more-or-less the definition I had in mind, see the comment thread for the specific definition I'm using. But why does that obviously collapse? I don't think that's the case. | |
| Jul 10, 2022 at 22:21 | comment | added | Fedor Pakhomov | @NoahSchweber I am not sure what do you mean by implicit definability hierarchy. The natural definition would have been $R$ is $0$ implicitly definable in $M$ if it is explicitly definable and $R$ is $n+1$ implicitly definable in $M$ if it is implicitly definable in $(M,R')$, for some $n$ implicitly definable $R'$. But this definition obviously leads to the collapse of the hierarchy for $(\mathbb{N},S)$ at the level 2 (i.e. 3 implicitly definable predicates are the same as 2 implicitly definable predicates). | |
| Jul 10, 2022 at 22:06 | comment | added | Noah Schweber | Nice! Out of curiosity, do you see a way to show that the implicit definability hierarchy over $(\mathbb{N},S)$ is non-collapsing that doesn't use forcing? (See the comment thread below my answer.) | |
| Jul 10, 2022 at 22:03 | history | undeleted | Fedor Pakhomov | ||
| Jul 10, 2022 at 22:02 | history | edited | Fedor Pakhomov | CC BY-SA 4.0 |
replaced the answer with a reference to an answer with the same content
|
| Jul 10, 2022 at 19:51 | history | deleted | Fedor Pakhomov | via Vote | |
| Jul 10, 2022 at 19:36 | history | answered | Fedor Pakhomov | CC BY-SA 4.0 |