$\newcommand{\N}{\mathbb{N}}$My question, more precisely, is:


**Question.** Is there a set $B\subset \N\times\N$, such that the set of indices where it is arithmetically definable, that is, $\{ n\in\N \mid B\_n\text{ is arithmetic}\}$, is not first-order definable in the structure $\langle\N,{+},{\cdot},0,1,{\lt},B\rangle$?


By $B\_n$, I mean the $n^\text{th}$ slice of $B$, the set $B\_n=\{ k\mid (n,k)\in B\}$. And a set is *arithmetic*, if it is first-order definable in the standard model of arithmetic $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$.


I have need of such a set $B$, with an application ready to go, if
there is such a set $B$.


One might hope to make an example via forcing, say, with
conditions that specify finitely many of the slices. We cannot
allow, however, that arbitrary arithmetic sets appear in the
slices of $B$, because then the $\Sigma\_k$ truth predicates would
appear for arbitrarily large $k$, and one can recognize these and
use them to define arithmetic truth from $B$, and thereby tell
which $B\_n$ are arithmetic.


So we want to restrict the kinds of arithmetic sets that are
allowed to appear as slices of $B$. Perhaps we want the slices of
$B$ to be themselves somewhat generic, as Cohen reals, say, with
the $B\_n$s increasingly $\Sigma^0\_k$-generic, and with some of
them fully arithmetically generic (and hence not arithmetic). But
I did not succeed in pushing this idea through.



> 
> **Update.** The result that Andrew has [provided](https://mathoverflow.net/a/141479) now appears as Lemma 10.1 (credited to him) in my paper with Ruizhi Yang:
> 
> 
> 
> > 
> > J. D. Hamkins and R. Yang, [Satisfaction is not absolute](http://jdh.hamkins.org/satisfaction-is-not-absolute/).
> > 
> > 
> > 
> 
> 
> The lemma is used to prove the following, which was the application that I had mentioned in the original question.
> 
> 
> **Theorem 10.** Every countable model of set theory $M$ has elementary
> extensions $M\_1$ and $M\_2$, which agree on the structure of their standard
> natural numbers $$\langle \mathbb{N},{+},{\cdot},0,1,\lt\rangle^{M\_1}= \langle \mathbb{N},{+},{\cdot},0,1,\lt\rangle^{M\_2},$$ and which have
> a set $A\subset\mathbb{N}$ in common, extensionally identical in $M\_1$ and $M\_2$, yet $M\_1$ thinks $A$ is first-order definable in $\mathbb{N}$ and $M\_2$ thinks it is not.
> 
> 
> 



Is there a subset of the natural number plane, which doesn't know which of its slices are arithmetic?
There are $B$ with this property.


Lets first recall some definitions and notation. Suppose $X \in 2^\omega$ (which we identify with subsets of $\mathbb N$ via characteristic functions). Then $X'$ is the Turing jump of $X$, and $X^{(n)}$ is the nth iterate of the Turing jump of $X$. $X$ is said to be $n$-generic (i.e. $\Sigma^0\_n$-generic for Cohen forcing) if for every $\Sigma^0\_n$ subset $S$ of $2^{< \omega}$ there is a finite initial segment $\sigma$ of $X$ so that either $\sigma \in S$, or there are no extensions of $\sigma$ contained in $S$. $X$ is said to be arithmetically generic if $X$ is $n$-generic for every $n$. It is a standard fact that if $X$ is $1$-generic, then $X' \equiv\_T 0' \oplus X$, where $\oplus$ is recursive join. We also have that if $X$ is $n$-generic and $Y$ is $1$-generic relative to $X \oplus 0^{(n-1)}$, then $X \oplus Y$ is $n$-generic. Finally, if $X\_0, X\_1, \ldots \in 2^\omega$, then $\bigoplus\_n X\_n = \{\langle n, m \rangle: m \in X\_n\}$ notes their recursive join.


Let $A = 0^{(\omega)} = \bigoplus\_{n} 0^{(n)}$; the set of true sentences in first order arithmetic. Below, we will construct a $B$ so that:


1. If $n \notin A$, then $B\_n$ is arithmetically generic, and if $n \in A$, then $B\_n$ is $(n+1)$-generic and computable from $0^{(n+1)}$. Hence $\{n \in \mathbb{N} : \text{$B\_n$ is arithmetic}\}$ is equal to $A$.
2. For each $k \in \mathbb N$, let $m\_i$ be the $i$th element of the set $\{m \in \mathbb N : m \notin A \lor m \geq k\}$. Then $C\_k = \bigoplus\_{i \in \omega} B\_{m\_i}$ is $(k+1)$-generic.


A $B$ with the above two properties gives a positive answer to your question by the following reasoning. We can prove by induction that for any $n$, $B^{(n)} \equiv\_T 0^{(n)} \oplus C\_{n}$. This is trivial when $n = 0$. Now for the inductive case, assume $B^{(n)} \equiv\_T 0^{(n)} \oplus C\_{n}$. Then we see that $B^{(n+1)} \equiv\_T (0^{(n)} \oplus C\_n)' \equiv\_T 0^{(n+1)} \oplus C\_n$ since $C\_n$ is $(n+1)$-generic and hence $1$-generic relative to $0^{(n)}$. Finally, $0^{(n+1)} \oplus C\_n \equiv\_T 0^{(n+1)} \oplus C\_{n+1}$ because either $n \notin A$ and so $C\_n = C\_{n+1}$ or $n \in A$ so $C\_{n+1} \equiv\_T B\_n \oplus C\_n$, but then $B\_n \leq\_T 0^{(n+1)}$.


Hence, $B^{(n)}$ cannot compute $A$ for any $n \in \omega$, since $C\_{n}$ is $(n+1)$-generic, and so $0^{(n)} \oplus C\_{n} \ngeq\_T 0^{(n+1)}$. (Indeed, it's easy to see that $B$ is $GL\_n$ for every $n \in \mathbb N$). Thus, $A$ is not arithmetically definable relative to $B$.




---


So lets turn now to the construction of a $B$ with the required properties (1) and (2) above. We construct $B$ in countably many steps where after step $n$ we will have completely defined $B\_0, B\_1, \ldots, B\_n$ and finitely many other bits of $B$ (i.e. finitely many bits of finitely many $B\_i$ where $i > n$). For step $0$, let $B\_0$ be an arbitrary real satisfying condition (1).


Given $k \leq n$, let $m\_0, \ldots, m\_j$ be the elements of $\{m \in \mathbb{N}: m \notin A \lor m \geq k\} \cap \{0, \ldots, n\}$, and define $C\_{k,n} = B\_{m\_0} \oplus \ldots \oplus B\_{m\_j}$. After each stage $n$, we will have ensured that $C\_{n,k}$ is $(k+1)$-generic for every $k \leq n$.


Now at step $n > 0$, for each pair $(i,k)$ where $i,k < n$, do the following. Let $S\_{i,k}$ be the $i$th $\Sigma^0\_{k+1}$ subset of $2^{< \omega}$. If we can find a finite extension of our approximation of $B$ so that the resulting approximation of $C\_k$ extends an element of $S\_{i,k}$, then extend our approximation of $B$ in this way. If this is not possible, then since $C\_{k,n-1}$ is $(k+1)$-generic, there must be some finite subset of our current approximation to $B$ which cannot be extended to extend an element of $S\_{i,k}$.


Next, we finish step $n$ by defining $B\_n$. If $n \notin A$ pick $B\_n$ to be an element of $2^{\omega}$ extending the finite approximation of $B\_n$ that we currently have, which is arithmetically generic relative to $B\_0 \oplus \ldots \oplus B\_{n-1}$. This clearly ensures that $C\_{k,n}$ will be $(k+1)$-generic for each $k < n$, since $C\_{k,n-1}$ is $(k+1)$-generic, and $B\_n$ is $(k+1)$-generic relative to it. Similarly, $C\_{n,n}$ is clearly $(n+1)$-generic. Otherwise, if $n \in A$, let $B\_n$ be an arbitrary $(n+1)$-generic computable from $0^{(n+1)}$ and extending the finitely many bits of $B\_n$ we have already determined. Now for any $k < n$, let $j\_0, \ldots, j\_t$ be the elements of $A$ that are $\geq k$ and $< n$. Then since $B\_n$ is $1$-generic relative to $0^{(n)}$ which can compute $B\_{j\_0} \oplus \ldots \oplus B\_{j\_t}$ we have that $B\_{j\_0} \oplus \ldots \oplus B\_{j\_t} \oplus B\_n$ is $(k+1)$-generic. Hence $C\_{k,n}$ is $(k+1)$-generic, since the remaining elements in the finite join defining $C\_{k,n}$ are mutually arithmetically generic (and are hence $(k+1)$-generic relative to $B\_{j\_0} \oplus \ldots \oplus B\_{j\_t} \oplus B\_n$). Similarly, $C\_{n,n}$ is again clearly $n+1$-generic.


To verify that our construction works, note that condition (1) is satisfied by how we pick $B\_n$ in the last paragraph. Condition (2) is satisfied by the paragraph before that.


