Antirandom reales

Question

Este es un crossposting de https://math.stackexchange.com/questions/1446602/anti-random-realsque no ha recibido ninguna respuesta; después de pensar sobre el problema, me he vuelto más convencido de que pertenece aquí en su lugar.

Para una función de $f: \mathbb{N}\rightarrow\mathbb{R}_{>0}$ y un conjunto $X\subseteq \mathbb{R}$, un $f$-cubierta de $X$ es una secuencia $(I_n)_{n\in\mathbb{N}}$ de intervalos abiertos con rational extremos tales que

• $X\subseteq\bigcup I_n$, y

• $\mu(I_n)<f(n)$.

Decir que un conjunto $X\subseteq\mathbb{R}$ es $f$-pequeño si $X$ tiene $f$a cubrir.

Hablando de $f$-cubre nos ofrece muchas diferentes refinamientos de la noción de "medida cero": por ejemplo, un conjunto es fuerte medida cero si tiene un $f$-portada para cada función de $f$.

Decir que un conjunto de reales $X$ es computably fuerte medida cero (csmz) si hay un $e$ tal que $\Phi_e^f$ es $f$-cubierta de $X$ siempre $f$ es una función de $\mathbb{N}$ a $\mathbb{R}_{>0}$. (Esto es lo triste es que no es el mismo como eficaz fuerte medida cero, una noción introducida por Kihara en su tesis; véase también http://www.sciencedirect.com/science/article/pii/S016800721400044X.)

En la teoría de la computabilidad, un real que se dice (de manera informal) para ser "al azar", si no está en ninguna "simple" medida-ajuste a cero; por supuesto, hay muchas maneras de formalizar este, pero este es el tema de fondo. Csmz conjuntos de proporcionar una muy fuerte noción de no-aleatoriedad: decir que un individuo real $r$ es antirandom si $\{r\}$ es csmz - equivalentemente, si $r$ está contenida en algunos csmz conjunto. Mi pregunta es:

¿Cuáles son los antirandom reales?

Tengo la fuerte sospecha de que cada antirandom real es computable, pero no puedo demostrarlo. EDIT: Como Joe Miller respuesta a continuación se muestra, mi suposición era realmente mal!

---

Comentario 1. El conjunto de antirandom reales es contable, pero la prueba es sorprendentemente realista. Hay una contables set $\{A_i: i\in\omega\}$ de csmz conjuntos tales que cada csmz conjunto está contenida en uno de los $A_i$s; específicamente, tome $A_i$ a ser el más grande csmz conjunto de testigo para ser csmz por $\Phi_i$. Ahora, puede ser forzoso que cada gran medida la puesta a cero es contable (esto es Borel de la conjetura) - de forzar la extensión, la antirandoms son contables. Mientras tanto, antirandomness es una $\Pi^1_1$ de la propiedad. Esto significa que la afirmación "hay countably muchos antirandom reales" es $\Sigma^1_3$, y de manera absoluta suponiendo grandes cardenales.

Este argumento es probablemente una exageración, pero (1) nos parecen necesidad de Borel de la conjetura para coanalytic conjuntos, que es independiente de ZFC, y (2) hacemos parecen necesitar $\Sigma^1_3$-valor absoluto para el correcto forzar, que ha trivial gran cardenal de la fuerza (ver http://www.logic.univie.ac.at/~sdf/papers/bagfried.pdf).

Comentario 2. Thomas Andrews, en la sección de comentarios a la pregunta original, propuso mirar al "c-csmz" conjuntos - estos son los conjuntos que se csmz, pero que sólo nos permiten computable secuencias de epsilons. Decir que un real $r$ es débilmente antirandom si $\{r\}$ es un c-csmz conjunto. Yo creo que hay noncomputable débilmente antirandom reales, pero no he sido capaz de demostrar que todavía; yo estaría interesado en estos reales así. Tenga en cuenta que el countability prueba se rompe: un c-csmz conjunto es no fuerte medida cero.

Answer 1

Sea a un c.e. conjunto con la propiedad de que hay infinitamente muchas etapas $s$ tal que $A_s\upharpoonright s = A\upharpoonright s$. Llame a una etapa "muy verdadero". Noncomputable $A$ con infinidad fuertemente verdadero etapas pueden ser producidos utilizando un mueble de marcador de la construcción.

Yo afirmación de que cualquier $A$ es antirandom.

Definir $\Phi_e^f$ como sigue: en Primer lugar, podemos calcular de $f$, un aumento de la función $g$ tal que $2^{-g(n)}<f(n)$ para todos los $n$. El $n$th intervalo en nuestra portada debería ser $I_n = \left[\;A_{g(n+1)}\upharpoonright g(n)\;\right]$.

Para comprobar que esto funciona, sólo tenga en cuenta que si $s\in[g(n),g(n+1)]$ es un muy verdadero escenario, a continuación, $I_n$ cubre $A$.

Mejora de Ejemplo: me dicen que si $A$ es un rango de 1 punto en una $\Pi^0_1$ de la clase, a continuación, $A$ es antirandom. Se puede demostrar que esta subsume la respuesta anterior, y además, hay un rango de 1 punto $A\equiv_T\emptyset''$, por lo que no todos antirandom conjuntos de $\Delta^0_2$.

Para ver la demanda, vamos a $P$ ser $\Pi^0_1$ clase con exactamente un punto límite $A$. En primer lugar, tenga en cuenta que es cierto que hay un $f$-cubierta de $P$ por cada $f$, y de hecho, uno de los que utiliza sólo un número finito de intervalos. Para ver esto, fix $f$ y empezar cubriendo $A$ con un intervalo de $I_0$ de la longitud de la $f(0)$. Ahora hay sólo un número finito de puntos de $P$ no cubiertos, y que puede ser cubierto por un número finito de los restantes $I_n$'s.

Ahora tenga en cuenta que por compacidad, eventualmente veremos que un $f$-cubierta de $P$ utilizando sólo un número finito de $I_n$s'es correcta, por lo que en relación a $f$, se puede buscar por una cubierta.

Mejor aún: Este argumento puede ser mejorado a cualquier miembro de cualquier contables $\Pi^0_1$ de la clase. Esto es porque contables clases están fuertemente medida cero y, por compacidad, sólo un número finito de la $I_n$'s son necesarias para cualquier fija $f$. De modo que una búsqueda (relativos a la $f$) se encuentra un $f$a cubrir.

Esto significa que antirandom conjuntos pueden tener complejidad tan alto como nos gustaría en el hyperarithmetical jerarquía.

Sugerencia: tal vez hay una buena relación entre antirandom y nunca de forma continua al azar (NCR)? Después de todo, Kjos-Hanssen y Montalbán mostró que los miembros de contables $\Pi^0_1$ clases de NCR. Estoy simplemente copiar su idea.

Mi Edición Final: en Realidad, es fácil ver que cada antirandom $A$ es la NCR. Dado un nombre de $m$ para una medida continua $\mu$, podemos encontrar una función $f$ de manera tal que cada intervalo de longitud de $f(n)$ ha $\mu$-medida en la mayoría de las $2^{-n}$. Ahora, usando el hecho de que $A$ es antirandom, podemos construir una $\mu$-ML de prueba relativa a $m$ cubriendo $A$.

Tenga en cuenta que Reimann y Slaman demostraron que cada NCR es hyperarithmetic (lo que le da otra prueba de que la colección de antirandom conjuntos contables).

Así que nos quedamos con lo siguiente:

Pregunta: Si $A$ es la NCR, debe ser antirandom?

Answer 2

No tengo una respuesta a la pregunta principal, pero hay un noncomputable débilmente antirandom real; de hecho, podemos construir un perfecto c-csmz $\Pi^0_1$clase $Q$.

Tenemos estrategias para cada parcial computable de la secuencia de epsilons $\psi$. Una estrategia comienza por la elección de un gran $n$ y espera hasta que $\psi$ ha convergido en la primera $2^{n+1}$ elementos. Deje $\epsilon_0$ ser el menor de estos primeros $2^{n+1}$ epsilons, y $s$ la etapa en la que vemos de esta convergencia. Para cada $\sigma \in 2^{n+1}$ con $[\sigma] \cap Q_s$ no vacío, nuestra estrategia escoge un $\tau$ extender $\sigma$ con $[\tau] \cap Q_s$ no vacío y $\mu([\tau]) < \epsilon_0$ y declara que $[\sigma] \cap Q_{s+1} = [\tau] \cap Q_s$. Organizar estas estrategias en un número finito de lesión de la construcción.

Ahora podemos definir la $\Phi$. Dada una secuencia de epsilons como un oráculo, se espera hasta que ve algo de estrategia actuar con $\epsilon_0$ e $n$ tal que $\epsilon_0$ no es más que el mínimo de la primera $2^{n+1}$ elementos de la secuencia. Cuando esto ocurre, podemos definir a la $I_0, \dots, I_{2^{n+1}-1}$ tal que se cubra todos los de $Q_{s+1}$ cubriendo el adecuado $\tau$. Vamos a ver finalmente una estrategia de este tipo tan largo como el oráculo es un computable de la secuencia de epsilons. Podemos definir el resto de $I_k$ en cualquier forma que sea coherente con la secuencia.

Edit: De hecho, cualquier débilmente 1-genérico será débilmente antirandom. Sólo tienes $\Phi$ elegir los intervalos en algunos densa de la moda.