Is there a subset of the natural number plane, which doesn't know which of its slices are arithmetic?

Question

$\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 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.

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.

Answer 1

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.