Return to 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^{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.

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

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

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

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

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