¿Existe un subconjunto del plano de los números naturales que no sepa cuáles de sus cortes son aritméticos?

Question

$\newcommand{\N}{\mathbb{N}}$

Mi pregunta, más precisamente, es:

Pregunta. ¿Existe un conjunto $B\subset \N\times\N$ , tal que el conjunto de índices donde es definible aritméticamente, es decir, $\{ n\in\N \mid B_n\text{ is arithmetic}\}$ no es definible de primer orden en la estructura $\langle\N,{+},{\cdot},0,1,{\lt},B\rangle$ ?

Por $B_n$ Me refiero a la $n^{th}$ rebanada de $B$ el conjunto $B_n=\{ k\mid (n,k)\in B\}$ . Y un conjunto es aritmética si es definible de primer orden en el modelo estándar de la aritmética $\langle\N,{+},{\cdot},0,1,{\lt}\rangle$ .

Tengo necesidad de un conjunto de este tipo $B$ con una aplicación lista para ser utilizada, si existe tal conjunto $B$ .

Se podría esperar hacer un ejemplo vía forzamiento, digamos, con condiciones que especifiquen un número finito de cortes. No podemos Sin embargo, no podemos permitir que aparezcan conjuntos aritméticos arbitrarios en las rodajas de $B$ porque entonces el $\Sigma_k$ los predicados de verdad aparecerían aparecen para un tamaño arbitrario de $k$ y uno puede reconocerlos y utilizarlos para definir la verdad aritmética de $B$ y así saber que $B_n$ son aritméticos.

Así que queremos restringir los tipos de conjuntos aritméticos que están pueden aparecer como trozos de $B$ . Tal vez queremos que las rebanadas de $B$ ser ellos mismos algo genérico, como los reales de Cohen, digamos, con el $B_n$ s cada vez más $\Sigma^0_k$ -genérico, y con algunos de ellos ellos totalmente aritméticos genéricos (y por tanto no aritméticos). Pero no conseguí llevar a cabo esta idea.

Actualización. El resultado que Andrew ha proporcionado aparece ahora como Lemma 10.1 (acreditado por él) en mi trabajo con Ruizhi Yang:

J. D. Hamkins y R. Yang, La satisfacción no es absoluta .

El lema se utiliza para demostrar lo siguiente, que era la aplicación que había mencionado en la pregunta original.

Teorema 10. Todo modelo contable de la teoría de conjuntos $M$ tiene extensiones elementales extensiones $M_1$ y $M_2$ que coinciden en la estructura de su norma números naturales $$\langle \mathbb{N},{+},{\cdot},0,1,\lt\rangle^{M_1}= \langle \mathbb{N},{+},{\cdot},0,1,\lt\rangle^{M_2},$$ y que tienen un conjunto $A\subset\mathbb{N}$ en común, extensamente idénticos en $M_1$ y $M_2$ Sin embargo $M_1$ piensa $A$ es definible de primer orden en $\mathbb{N}$ y $M_2$ cree que no lo es.

Answer 1

Hay $B$ con esta propiedad.

Recordemos primero algunas definiciones y notación. Supongamos que $X \in 2^\omega$ (que identificamos con subconjuntos de $\N$ mediante funciones características). Entonces $X'$ es el salto de Turing de $X$ y $X^{(n)}$ es la enésima iteración del salto de Turing de $X$ . $X$ se dice que $n$ -genérico (es decir $\Sigma^0_n$ -genérica para el forzamiento de Cohen) si para cada $\Sigma^0_n$ subconjunto $S$ de $2^{< \omega}$ existe un segmento inicial finito $\sigma$ de $X$ para que $\sigma \in S$ o no hay extensiones de $\sigma$ contenida en $S$ . $X$ se dice que es aritméticamente genérico si $X$ es $n$ -genérico para todos $n$ . Es un hecho habitual que si $X$ es $1$ -genérico, entonces $X' \equiv_T 0' \oplus X$ , donde $\oplus$ es una unión recursiva. También tenemos que si $X$ es $n$ -genéricos y $Y$ es $1$ -generico relativo a $X \oplus 0^{(n-1)}$ entonces $X \oplus Y$ es $n$ -genérico. Por último, si $X_0, X_1, \ldots \in 2^\omega$ entonces $\bigoplus_n X_n = \{\langle n, m \rangle: m \in X_n\}$ observa su unión recursiva.

Dejemos que $A = 0^{(\omega)} = \bigoplus_{n} 0^{(n)}$ ; el conjunto de sentencias verdaderas en aritmética de primer orden. A continuación, construiremos un $B$ para que:

1. Si $n \notin A$ entonces $B_n$ es aritméticamente genérico, y si $n \in A$ entonces $B_n$ es $(n+1)$ -genérico y computable a partir de $0^{(n+1)}$ . Por lo tanto, $\{n \in \mathbb{N} : \text{$ B_n $ is arithmetic}\}$ es igual a $A$ .
2. Para cada $k \in \N$ , dejemos que $m_i$ sea el $i$ elemento del conjunto $\{m \in \N : m \notin A \lor m \geq k\}$ . Entonces $C_k = \bigoplus_{i \in \omega} B_{m_i}$ es $(k+1)$ -genérico.

A $B$ con las dos propiedades anteriores da una respuesta positiva a su pregunta mediante el siguiente razonamiento. Podemos demostrar por inducción que para cualquier $n$ , $B^{(n)} \equiv_T 0^{(n)} \oplus C_{n}$ . Esto es trivial cuando $n = 0$ . Ahora, para el caso inductivo, supongamos $B^{(n)} \equiv_T 0^{(n)} \oplus C_{n}$ . Entonces vemos que $B^{(n+1)} \equiv_T (0^{(n)} \oplus C_n)' \equiv_T 0^{(n+1)} \oplus C_n$ desde $C_n$ es $(n+1)$ -genérico y por lo tanto $1$ -generico relativo a $0^{(n)}$ . Finalmente, $0^{(n+1)} \oplus C_n \equiv_T 0^{(n+1)} \oplus C_{n+1}$ porque o bien $n \notin A$ y así $C_n = C_{n+1}$ o $n \in A$ así que $C_{n+1} \equiv_T B_n \oplus C_n$ pero luego $B_n \leq_T 0^{(n+1)}$ .

Por lo tanto, $B^{(n)}$ no puede calcular $A$ para cualquier $n \in \omega$ ya que $C_{n}$ es $(n+1)$ -genérico, y así $0^{(n)} \oplus C_{n} \ngeq_T 0^{(n+1)}$ . (De hecho, es fácil ver que $B$ es $GL_n$ por cada $n \in \N$ ). Así, $A$ no es definible aritméticamente respecto a $B$ .

---

Así que vamos a pasar a la construcción de un $B$ con las propiedades requeridas (1) y (2) anteriores. Construimos $B$ en un número contable de pasos en los que después del paso $n$ habremos definido completamente $B_0, B_1, \ldots, B_n$ y otros bits finitos de $B$ (es decir, un número finito de bits de un número finito de $B_i$ donde $i > n$ ). Para el paso $0$ , dejemos que $B_0$ sea un real arbitrario que satisfaga la condición (1).

Dado $k \leq n$ , dejemos que $m_0, \ldots, m_j$ sean los elementos de $\{m \in \mathbb{N}: m \notin A \lor m \geq k\} \cap \{0, \ldots, n\}$ y definir $C_{k,n} = B_{m_0} \oplus \ldots \oplus B_{m_j}$ . Después de cada etapa $n$ habremos garantizado que $C_{n,k}$ es $(k+1)$ -genérico para todos $k \leq n$ .

Ahora en el paso $n > 0$ para cada par $(i,k)$ donde $i,k < n$ haz lo siguiente. Deja que $S_{i,k}$ sea el $i$ th $\Sigma^0_{k+1}$ subconjunto de $2^{< \omega}$ . Si podemos encontrar una extensión finita de nuestra aproximación de $B$ para que la aproximación resultante de $C_k$ extiende un elemento de $S_{i,k}$ y luego ampliar nuestra aproximación de $B$ de esta manera. Si esto no es posible, entonces como $C_{k,n-1}$ es $(k+1)$ -genérica, debe haber algún subconjunto finito de nuestra actual aproximación a $B$ que no puede extenderse para ampliar un elemento de $S_{i,k}$ .

A continuación, terminamos el paso $n$ definiendo $B_n$ . Si $n \notin A$ elige $B_n$ para ser un elemento de $2^{\omega}$ ampliando la aproximación finita de $B_n$ que tenemos actualmente, que es aritméticamente genérico en relación con $B_0 \oplus \ldots \oplus B_{n-1}$ . Esto garantiza claramente que $C_{k,n}$ será $(k+1)$ -genérico para cada uno $k < n$ ya que $C_{k,n-1}$ es $(k+1)$ -genérico, y $B_n$ es $(k+1)$ -genérico relativo a él. Del mismo modo, $C_{n,n}$ es claramente $(n+1)$ -genérico. En caso contrario, si $n \in A$ , dejemos que $B_n$ sea una variable arbitraria $(n+1)$ -generico computable desde $0^{(n+1)}$ y extendiendo los bits finitos de $B_n$ que ya hemos determinado. Ahora, para cualquier $k < n$ , dejemos que $j_0, \ldots, j_t$ sean los elementos de $A$ que son $\geq k$ y $< n$ . Entonces, como $B_n$ es $1$ -generico relativo a $0^{(n)}$ que puede calcular $B_{j_0} \oplus \ldots \oplus B_{j_t}$ tenemos que $B_{j_0} \oplus \ldots \oplus B_{j_t} \oplus B_n$ es $(k+1)$ -genérico. Por lo tanto, $C_{k,n}$ es $(k+1)$ -genérica, ya que los elementos restantes en la unión finita que define $C_{k,n}$ son aritméticamente genéricos entre sí (y por lo tanto son $(k+1)$ -generico relativo a $B_{j_0} \oplus \ldots \oplus B_{j_t} \oplus B_n$ ). De la misma manera, $C_{n,n}$ es de nuevo claramente $n+1$ -genérico.

Para verificar que nuestra construcción funciona, observe que la condición (1) se satisface por la forma en que elegimos $B_n$ en el último párrafo. La condición (2) se cumple con el párrafo anterior.