21
$\begingroup$

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

$\endgroup$
15
  • $\begingroup$ I'm quite ignorant in forcing in this sort of context, but what about other generic reals? $\endgroup$
    – Asaf Karagila
    Sep 5, 2013 at 23:29
  • $\begingroup$ 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. $\endgroup$ Sep 5, 2013 at 23:36
  • $\begingroup$ 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. $\endgroup$
    – Asaf Karagila
    Sep 6, 2013 at 0:02
  • $\begingroup$ 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. $\endgroup$ Sep 6, 2013 at 0:07
  • 2
    $\begingroup$ @Noah: There are only countably many arithmetic sets, so almost all $A$ have all columns non-arithmetic. $\endgroup$ Sep 6, 2013 at 4:09

1 Answer 1

16
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ This is great! Thank you very much for pushing the idea through! Could you kindly send me an email, so that we may cite you properly in our paper? (You can find my contact details on my web page, accessible from my profile.) $\endgroup$ Sep 7, 2013 at 13:33
  • $\begingroup$ The application, incidentally, is this: there are two models of set theory $M_1$ and $M_2$, with their natural number structure in common $\langle\mathbb{N},{+},{\cdot},0,1,{\lt}\rangle^{M_1}= \langle\mathbb{N},{+},{\cdot},0,1,{\lt}\rangle^{M_2}$, and with a set $A\subset\mathbb{N}$ in common, but $M_1$ thinks $A$ is arithmetic and $M_2$ thinks it is not arithmetic. I'll post a link to the paper when it is ready. $\endgroup$ Sep 7, 2013 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.