Conjuntos no Borel sin axioma de elección

Question

Esta es una simple duda mía sobre los fundamentos de la teoría de la medida, que debería ser fácil de responder para los lógicos. El ejemplo que conozco de conjuntos no Borel sería una base de Hamel, que necesita el axioma de elección, y los ejemplos de conjuntos medibles no Lebesgue serían Conjuntos Vitali , que parece ser indemostrable sin el axioma de elección. Entonces vi la respuesta de François G. Dorais . Su construcción de un incontable $\mathbb{Q}$ -sistema independiente en $\mathbb R$ no requiere un axioma de elección. Lo que deja una débil esperanza para lo siguiente:

¿Es posible construir sin utilizar el axioma de elección ejemplos de conjuntos no Borel?

Hay un ejemplo clásico de un conjunto analítico pero no Borel debido a Lusin, descrito por Gerald Edgar aquí pero no me queda claro si necesita el axioma de elección ya que parece que pone restricciones a términos cada vez más altos en la expansión de la fracción continua. Como no sé de lógica y teoría de conjuntos, esperaba preguntar a los expertos.

Answer 1

No, no es posible. Es coherente con ZF sin elección que

los reales son la unión contable de conjuntos contables. (*)

De ello se deduce que todos los conjuntos de reales son de Borel. Por supuesto, el "axioma" (*) hace imposible cualquier análisis. Tan pronto como uno permite el poco de elección que se utiliza típicamente para establecer el análisis clásico como uno está acostumbrado (sobre todo la elección contable, pero DC parece necesario para Radon-Nikodym), se puede implementar los argumentos necesarios para mostrar

(**) La jerarquía habitual de los conjuntos de Borel (obtenida tomando primero los conjuntos abiertos, luego los complementos, luego las uniones contables de éstos, luego los complementos, etc.) no termina antes de la etapa $\omega_1$ (es una especie de argumento diagonal).

Los lógicos llaman a los conjuntos así obtenidos $\Delta^1_1$ . Son en general una subcolección de los conjuntos de Borel. Demostrar que son todos los conjuntos de Borel requiere un poco de elección (Se necesita que $\omega_1$ es regular).

En realidad hay un buen resultado de Suslin relevante aquí. Demostró que los conjuntos de Borel son precisamente los $\Delta^1_1$ conjuntos: Son los conjuntos que son simultáneamente la imagen continua de un conjunto de Borel ( $\Sigma^1_1$ ), y el complemento de dicho conjunto ( $\Pi^1_1$ conjuntos).

Que hay $\Pi^1_1$ conjuntos que no son $\Delta^1_1$ (y por lo tanto, a través de un poco de elección, no Borel) es de nuevo un resultado de Suslin. También demostró que cualquier $\Sigma^1_1$ es contable o contiene una copia del conjunto de Cantor y, por tanto, tiene el mismo tamaño que los reales. Su ejemplo de $\Sigma^1_1$ no $\Delta^1_1$ conjunto utiliza la lógica (un poco de teoría de conjuntos descriptiva efectiva), y hoy en día es más común utilizar el ejemplo del $\Pi^1_1$ conjunto WO mencionado por Joel, que no es $\Delta^1_1$ por lo que los lógicos llaman un argumento de limitación.

Una buena referencia para algunas de estas cuestiones es el libro Mansfield-Weitkamp, Aspectos recursivos de la teoría descriptiva de conjuntos , Oxford University Press, Oxford (1985).

Answer 2

Si se asume el axioma contable de elección, entonces la mayoría de los conjuntos de reales no son de Borel. Bajo AC, lo que se obtiene es que hay un continuo de conjuntos de Borel, es decir, $2^{\aleph_0}$ muchos, pero $2^{2^{\aleph_0}}$ muchos conjuntos de reales, por lo que la mayoría de los conjuntos de reales no son Borel. En el caso de la elección elección $AC_\omega$ lo que tenemos es una suryección de la reales sobre los conjuntos de Borel, y esto sigue siendo suficiente para concluir que la mayoría de los conjuntos de reales no son Borel.

Para ver que sólo hay un número continuo de conjuntos de Borel, uno puede pensar en cómo se construyen los conjuntos de Borel. En comenzamos con los conjuntos abiertos básicos, de los que hay contablemente muchos, y luego cerramos sistemáticamente bajo uniones, intersecciones y complementos contables. De ello se desprende que los conjuntos de Borel se construyen en una jerarquía de longitud $\omega_1$ y que todo conjunto de Borel tiene un plantilla de construcción, conocida como código de Borel, que detalla exactamente cómo se construyó a partir de los conjuntos abiertos básicos. Se puede pensar en el código de Borel como un árbol contable bien fundado cuyas hojas están etiquetadas con conjuntos abiertos básicos y cuyos otros nodos están etiquetados con la unión, la intersección y el complemento, lo que significa que ésta es la operación que debe aplicarse que hay que aplicar al nodo hijo para saber qué conjunto está codificado en el nodo padre. Todo árbol de este tipo es un objeto contable codificado por un real.

En $AC_\omega$ la colección de conjuntos de reales codificados por tales códigos de Borel es un $\sigma$ -que contiene todos los conjuntos abiertos, y el más pequeño de ellos, por lo que es exactamente la colección de conjuntos de Borel. La prueba de que es un $\sigma$ -el álgebra utiliza $AC_\omega$ porque cuando tenemos un contable familia de conjuntos de Borel, para hacer el código de su unión, podemos podemos simplemente pegar los códigos de Borel para cada uno de ellos, siempre que podamos elegir códigos de Borel representativos. Por lo tanto en $AC_\omega$ podemos mapear los reales en el conjunto de conjuntos de Borel. Pero por el teorema de Cantor, no podemos mapear los reales en el conjunto de potencias de los reales, por lo que en este sentido, la mayoría de los conjuntos de reales no son Borel.

En $AC_\omega$ También se pueden dar ejemplos concretos de conjuntos que no son de Borel. Por ejemplo, el conjunto de reales conocido como WO es el conjunto de reales que codifica una relación binaria sobre los números naturales que es un orden de pozo. Se trata de un completo $\Pi^1_1$ conjunto, y no puede ser Borel.

Para explicar un poco más: si tengo una relación $R$ en el números naturales para los que $\langle\mathbb{N},R\rangle$ es un orden de pozo, entonces puedo codificar esta relación $R$ como una sola secuencia binaria, colocando un $1$ en el $2^n3^m$ dígito exactamente si $nRm$ . El conjunto de tales secuencias que codifican tales órdenes de pozos tiene una complejidad $\Pi^1_1$ ya que para ser un significa que es un orden lineal (lo que es fácil de expresar usando expresar utilizando sólo cuantificadores de números naturales) más la afirmación de que todo subconjunto tiene un elemento mínimo (que es el cuantificador universal sobre los reales). Pero además, es completo $\Pi^1_1$ lo que significa que cada $\Pi^1_1$ set se reduce a WO. Pero (bajo $AC_\omega$ ) los conjuntos de Borel son exactamente los $\Delta^1_1$ conjuntos, que son los conjuntos que son ambos $\Pi^1_1$ y $\Sigma^1_1$ , lo que significa que su complemento es $\Pi^1_1$ .

Básicamente, cualquier conjunto que se defina utilizando la fundamentación implicará esencialmente $\Pi^1_1$ y WO, y sacarte del contexto de Borel. El conjunto de todos los árboles contables bien fundados el conjunto de las relaciones contables bien fundadas, el conjunto de órdenes bien fundadas, y así sucesivamente, son todos completos $\Pi^1_1$ conjuntos, y por lo tanto no son de Borel.

Se puede trabajar de forma similar en el lado analítico, para llegar a con $\Sigma^1_1$ ejemplos. Existe un sistema universal de $\Sigma^1_1$ conjunto, un subconjunto analítico del plano cuyo son todos conjuntos analíticos, y tal conjunto no puede ser Borel, bajo $AC_\omega$ ya que si lo fuera, podría voltear los valores de la diagonal y producir un conjunto analítico que no es un trozo.

Answer 3

La teoría de la medida sin el axioma de la elección (ni siquiera la elección contable) se discute en Fremlin, teoría de la medida volumen 5, capítulo 56. Está disponible gratuitamente en línea. Gracias a MO y a ex-falso-quodlibet por darme a conocer este extenso texto en esta respuesta .

Menciona el resultado de Feferman & Levy de que es consistente que los reales sean una unión contable de conjuntos contables, según la respuesta de Andrés. Esto hace que la definición estándar de conjuntos de Borel no sea útil, ya que todo es Borel. Sin embargo, todavía es posible hacer análisis y teoría de la medida sin elección. Sólo se necesitan las definiciones adecuadas. Fremlin discute conjuntos de Borel codificables . Las uniones e intersecciones de "secuencias codificables" de conjuntos codificables de Borel son a su vez conjuntos codificables de Borel. La idea básica es representar exactamente cómo se construye un conjunto en términos de secuencias sucesivas de uniones y complementos de conjuntos, partiendo de una enumeración de una base para la topología. Esto se hace mediante estructuras de árbol contables, que definen una construcción de subconjuntos de R (o de cualquier espacio polaco) aplicando uniones contables de complementos a medida que se avanza en el árbol. Esta definición utiliza una inducción transfinita contable para construir el mapa de árboles a conjuntos de Borel codificables. Un punto importante es:

En presencia de elección contable, conjuntos de Borel codificables = conjuntos de Borel.

Veo que Andrés y Joel mencionan esto como un teorema en sus respuestas. Sin embargo, no es cierto sin elección contable. La unión de una secuencia de conjuntos codificables de Borel no tiene por qué ser de Borel, así que aunque los reales pudieran escribirse como una unión contable de conjuntos contables no se deduce que todos los subconjuntos sean codificables de Borel. Sin embargo, dada una secuencia de conjuntos codificables de Borel con una elección específica de codificaciones, su unión es codificable de Borel. Sin elección contable, tiene sentido trabajar con conjuntos de Borel codificables en lugar de los conjuntos de Borel estándar. Entonces, muchos resultados estándar se trasladan a la situación sin elección contable. Por ejemplo, un conjunto es Borel codificable si y sólo si tanto él como su complemento son conjuntos analíticos (imágenes continuas de subconjuntos cerrados de $\mathbb{N}^\mathbb{N}$ ).

Ciertamente hay subconjuntos de los reales explícitamente construibles que no son Borel codificables. Creo que los argumentos de Joel deberían aplicarse a la situación sin elección contable.

Una forma de construir ejemplos explícitos de conjuntos de Borel no codificables es construir un conjunto analítico cuyo complemento no sea analítico. El ejemplo de Lusin (enlazado en la pregunta) se ajusta a este método, aunque no estoy seguro de que siga funcionando sin elección. Sin embargo, hay otros ejemplos más difíciles de describir que sí lo hacen. (Me he quedado sin tiempo para esta respuesta, así que volveré a ella más tarde).

[continúa...]

Existe una forma estándar de construir conjuntos no Borel, que se menciona, por ejemplo, en Cohn, teoría de la medida (Corolario 8.2.17) e, incluso sin elección contable, el argumento sigue funcionando para obtener un conjunto no codificable-Borel. Es un argumento del tipo de la diagonalización. Esto construye un subconjunto del espacio de Baire $\mathcal{N}=\mathbb{N}^\mathbb{N}$ (bajo la topología del producto). Este es un espacio polaco homeomorfo a los números irracionales en [0,1] por la representación de fracción continua (estoy tomando $\mathbb{N}=\{1,2,\ldots\}$ para mayor comodidad).

Si X,Y son espacios polacos, entonces digamos que un subconjunto $S\subseteq X\times Y$ es universal si todo subconjunto cerrado de X es de la forma $S_y=\{x\in X\colon(x,y)\in S\}$ . Siempre es posible construir un subconjunto universal cerrado de $X\times\mathcal{N}$ . Si $U_1,U_2,\ldots$ es una enumeración de una base para la topología sobre X, entonces

$$ S=\left\{(x,y)\in X\times\mathcal{N}\colon x\in\bigcap_{n=1}^\infty U_{y(n)}^c\right\} $$

es cerrado y universal.

Ahora, tomemos S como un subconjunto universal cerrado de $X\times\mathcal{N}$ donde $X=\mathcal{N}\times\mathcal{N}$ .

El conjunto $A=\{x\in\mathcal{N}\colon \exists y\in\mathcal{N}{\rm\ s.t.\ } (x,y,x)\in S\}$ es una analítica pero subconjunto no codificable-Borel de $\mathcal{N}$ .

Un subconjunto de un espacio polaco X es analítico si es la proyección de un subconjunto cerrado de $X\times\mathcal{N}$ sobre X. El conjunto A anterior es la proyección del conjunto $\{(x,y)\in\mathcal{N}^2\colon(x,y,x)\in S\}$ también lo es la analítica. Si fuera Borel codificable, entonces su complemento sería la proyección de algún conjunto cerrado $B\subseteq\mathcal{N}^2$ . Por universalidad, $B=S_x$ para algunos $x\in\mathcal{N}$ . Sin embargo, $$x\in A^c\iff \exists y{\rm\ s.t.\ } (x,y)\in S_x \iff \exists y{\rm\ s.t.\ }(x,y,x)\in S\iff x\in A$$ daría una contradicción.

De hecho, creo que puedo demostrar que el conjunto que enlazaste de Lusin no es codificable de Borel, sin usar la elección. Por representación de fracción continua, es lo mismo que decir que lo siguiente no es codificable Borel.

S = el conjunto de $x\in\mathcal{N}$ para la que existe una secuencia creciente $0\lt i_1\lt i_2\lt\cdots$ de manera que cada $x(i_k)$ divide $x(i_{k+1})$ .

En presencia de la elección, esto es estándar ( Kechris, Teoría Descriptiva Clásica de Conjuntos tiene una prueba, pero no tengo una copia). Espero que la prueba se pueda adaptar en ausencia de elección contable pero, como no conozco la prueba estándar de esto, puedo dar un esbozo propio muy muy aproximado. La idea es considerar el conjunto de árboles $\mathcal{T}$ donde cada nodo tiene un conjunto contable de hijos que corresponden a elementos de $\mathbb{N}$ . Cualquier árbol de este tipo está definido por el conjunto de caminos finitos $(i_1,\ldots,i_n)\in\mathbb{N}^*=\bigcup_{n=1}^\infty\mathbb{N}^n$ que contiene, y $\mathcal{T}$ forma un espacio polaco (utilizando la topología del producto en $\{0,1\}^{\mathbb{N}^*}$ ). Sea $\mathcal{T}_0\subseteq\mathcal{T}$ sean los árboles que no contienen caminos infinitos. Estos corresponden a los códigos de Borel. Entonces, $\mathcal{T}_0$ no es en sí mismo codificable Borel (*). A continuación, cada árbol puede ser representado unívocamente por un elemento $x\in\mathcal{N}$ de tal manera que pasar de un nodo a uno de sus hijos corresponde a pasar de i a $j\gt i$ donde $x(i)$ divide $x(j)$ . Entonces, $\mathcal{T}_0$ correponde precisamente al conjunto S anterior que, por lo tanto, no es Borel codificable.

(*) Que $\mathcal{T}_0$ no es Borel es estándar (en presencia de AoC). No conozco la prueba de esto, tal vez se pueda demostrar usando un argumento similar al anterior para conjuntos no analíticos. Sin embargo, puedo elaborar un argumento aproximado alternativo por mi cuenta de que no es Borel codificable. La idea es que cada árbol corresponde a un programa para alguna máquina de super-Turing que puede realizar operaciones booleanas contables a la vez, y las que no tienen caminos infinitos tienen garantizada la parada. Si $\mathcal{T}_0$ fuera codificable, entonces habría un código de Borel $T\in\mathcal{T}_0$ que genera $\mathcal{T}_0$ . Esto es similar a tener un programa de Turing que resuelve el problema de detención, y podríamos derivar una contradicción de manera similar. Hay algunos detalles complicados para conseguir que esta analogía funcione correctamente, pero parece que debería funcionar.

Answer 4

Hay algunos ejemplos muy bonitos de conjuntos no Borel. Dos que me gustan especialmente son las funciones diferenciables (como subconjunto del espacio de funciones continuas en [0,1], por ejemplo) y el conjunto de todos los grafos infinitos que contienen una camarilla infinita (como subconjunto del conjunto de todos los grafos con conjunto de vértices $\mathbb{N}$ con la topología del producto). En general, una imagen continua de un conjunto Borel no tiene por qué ser Borel, y muchos conjuntos naturales no Borel surgen de esta manera.