Timeline for Is there a subset of the natural number plane, which doesn't know which of its slices are arithmetic?
Current License: CC BY-SA 4.0
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 12, 2022 at 2:01 | history | edited | LSpice | CC BY-SA 4.0 |
While this is on the front page, deleted spurious line break; link to @AndrewMarks's answer
|
| Jun 15, 2020 at 7:27 | history | edited | CommunityBot |
Commonmark migration
|
|
| Sep 30, 2014 at 11:51 | vote | accept | Joel David Hamkins | ||
| Dec 4, 2013 at 1:45 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
Added link to the paper where the argument appears
|
| Sep 7, 2013 at 5:27 | comment | added | Garrett Ervin | Oh: that definition for $X$ isn't quite right. I was thinking in terms of sequences. I assume $B_n = (0, 0, \ldots)$ means $B_n = \emptyset$ (for $n \in X$), so $\phi(n)$ should read $\forall k [\neg B(n, k)]$ | |
| Sep 7, 2013 at 3:33 | answer | added | Andrew Marks | timeline score: 16 | |
| Sep 7, 2013 at 2:32 | comment | added | Garrett Ervin | I think your example is ruled out because Joel includes $B$ as a predicate in the structure $\langle \mathbb{N}, +, \cdot, 0, 1, B \rangle$. Your $X$ is chosen to be undefinable over $\langle \mathbb{N}, +, \cdot, 0, 1 \rangle$, but we may define $X$ using $B$. For example, the formula $\phi(n) = \forall k [B(n, k) \leftrightarrow k=0]$ defines $X$. But $X = \{n: B_n$ is arithmetic$\}$, which is precisely the set we want to be undefinable over $\langle \mathbb{N}, +, \cdot, 0, 1, B \rangle$. | |
| Sep 7, 2013 at 1:18 | comment | added | user39649 | (This should be a comment, but one needs an account to post comments here). Is there some part of your question that is left unstated because everyone takes it for granted? Or am I misunderstanding it completely? Let X be your favorite non-arithmetic set (point in $2^\omega$), e.g. maybe X is the truth set of arithmetic. Can't you just say (for the version as written) $B_i=\begin{cases}X & \text{if $X_i=0$}\\ 0,0,\ldots & \text{otherwise?}\end{cases}$ or something like that? This is obvious enough that I have to presume it doesn't actually match the question. | |
| Sep 6, 2013 at 11:51 | comment | added | Noel Vaillant | @JoelDavidHamkins yes my apologies | |
| Sep 6, 2013 at 10:26 | comment | added | Joel David Hamkins | @NoelVaillant, there are continuum many sets having arithmetic slices only on the even coordinates, for example. | |
| Sep 6, 2013 at 10:13 | comment | added | Noel Vaillant | This doesn't define an injection. I am sorry. Please ignore | |
| Sep 6, 2013 at 9:41 | comment | added | Noel Vaillant | Isn't the set of $B\subseteq\mathtt{N}\times\mathtt{N}$ for which $\{n\in\mathtt{N}:B_{n}\mbox{ is arithmetic }\}$ is definable in $\langle \mathtt{N},+,.,B\rangle$ a countable set? As to any such $B$ you can injectively associate a pair $(\phi,(\phi_{n})_{n\in\mathtt{N}})$ where $\phi$ is a formula in the extended language, and the $\phi_{n}$'s in the usual language. | |
| Sep 6, 2013 at 5:06 | comment | added | Noah Schweber | Oh, of course. (This is why I shouldn't do math while tired.) | |
| Sep 6, 2013 at 4:09 | comment | added | François G. Dorais | @Noah: There are only countably many arithmetic sets, so almost all $A$ have all columns non-arithmetic. | |
| Sep 6, 2013 at 0:37 | comment | added | Noah Schweber | (Or "positive measure" can be replaced with "non-meager," etc.) | |
| Sep 6, 2013 at 0:35 | comment | added | Noah Schweber | I don't know if this helps, but: suppose the answer to your question is "no," there is no such $B$. Then since there are only countably many formulas in the relevant language, some $\varphi$ has to have the property that, for positive-measure many $A$, $\varphi$ defines in $(\mathbb{N}, +, \times; A)$ the set of non-arithmetic columns of $A$. This seems very strong. | |
| Sep 6, 2013 at 0:07 | comment | added | Joel David Hamkins | Well, the definability of the forcing notion could play a role, making it different, even if it is isomorphic to Cohen forcing by a map that washes away the definability issues. But for the purpose of this problem, I do think that it makes sense to think of forcing over $V$. Can you make a set $B$ like a want in a forcing extension of $V$? If so, then we will get a $B$ like this back in $V$ by Shoenfield absoluteness, since the existence of such a $B$ is a $\Sigma^1_1$ assertion. | |
| Sep 6, 2013 at 0:02 | comment | added | Asaf Karagila♦ | Well, before I attempt anything I should probably sleep for a little bit. While I'm at it, let me leave with one question. If we talk about "sufficiently generic" sort of objects, can we prove a uniqueness theorem of Cohen forcing? That is, can we prove that every two countable [and nontrivial] forcings are Cohen? If not, then perhaps cooking up a particular variant of Cohen forcing might work. | |
| Sep 5, 2013 at 23:36 | comment | added | Joel David Hamkins | Well, be my guest to try other methods! I had in mind the computability theorist's version of forcing, where one takes only sufficiently generic objects, meeting definable dense sets. But if you can define a notion of forcing for which the fully $V$-generic filters would provide an example, then almost surely we can build a pseudo-generic object without actually forcing and get the example provably in ZFC. | |
| Sep 5, 2013 at 23:29 | comment | added | Asaf Karagila♦ | I'm quite ignorant in forcing in this sort of context, but what about other generic reals? | |
| Sep 5, 2013 at 23:09 | history | edited | Joel David Hamkins | CC BY-SA 3.0 |
added 140 characters in body
|
| Sep 5, 2013 at 22:49 | history | asked | Joel David Hamkins | CC BY-SA 3.0 |