¿Es necesario el axioma de la elección en este caso?

Question

En el libro Análisis I, de Terence Tao, aparece el siguiente ejercicio: Sea $X $ sea un conjunto, demuestre que $X $ es infinito si y sólo si existe un subconjunto propio $Y $ de $X $ que tiene la misma cardinalidad que $X $ . (Este ejercicio requiere el Axioma de elección)

Mi intento:

• Si $X $ es finito, entonces es trivial (por inducción en el número de elementos)

• Si $X $ es infinito, entonces elige $x_0 $ en $X $ mostraremos una biyección entre $X $ y $Y=X\setminus \{x_0\} $ . Tome una secuencia $(x_n ) $ de elementos distintos de $Y $ (la definición de la secuencia es por inducción) Si ya hemos definido $x_i $ para todos $0\leq i \leq n $ para algunos $n $ , entonces toma $x_{n+1} $ sea cualquier elemento del conjunto no vacío $Y\setminus \{x_1,\ldots , x_n\} $ . Entonces tome la biyección $f:X\to Y $ definido por $f (x)=x $ si $x\neq x_i $ para todos $i \geq 0$ y $f (x_i)=x_{i+1} $ de lo contrario.

No veo dónde hemos utilizado el axioma de la elección...

Answer 1

Se utiliza el axioma de elección al construir la secuencia $(x_n \mid n \in \mathbb N)$ . Para que esto sea más evidente, tenemos que ser un poco más formales en cómo se obtiene dicha secuencia:

Considere el conjunto $S$ de todas las secuencias finitas $\vec{y} = (y_n \mid n \le m)$ tal que $y_0 = x_0$ como se ha fijado anteriormente y tal que para todo $n < m$ $y_{n+1} \in X \setminus \{ y_0, \ldots, y_n \}$ . Consideremos ahora la relación $R$ en $S \times S$ dado por $$ (y_0, \ldots, y_m) R (z_0, \ldots, z_l) : \iff l > m \wedge \forall n \le m \colon y_n = z_n, $$

en palabras más sencillas: $\vec{y}R\vec{z}$ si $\vec{z}$ es una extensión final de $\vec{y}$ .

Su inducción demuestra que para todos $\vec{y} \in S$ hay algo de $\vec{z} \in S$ tal que $\vec{y} R \vec{z}$ . El axioma de elección (basta con tener la axioma de la elección dependiente ) permite ahora elegir una secuencia infinita $( \vec{y}_n \mid n \in \mathbb N)$ tal que para todo $n \in \mathbb N$ $$ \vec{y}_n R \vec{y}_{n+1}. $$

Si ahora dejas que $x_n$ sea el $n$ -éste es el elemento de $\vec{y}_n$ la secuencia resultante $(x_n \mid n \in \mathbb N)$ es la deseada.

---

Nótese que esto no demuestra que sea necesaria alguna forma de elección. Sólo pone de manifiesto dónde se utiliza implícitamente el axioma de elección (dependiente). Ver que, en general, necesitamos alguna forma de elección aquí es mucho más difícil y (por el momento) no deberías preocuparte por ello.

Answer 2

la definición de la secuencia es por inducción

Bueno, no, en realidad no - usted no ha mostrado cómo definir la secuencia en absoluto, ya que la elección de $x_n$ dado $x_0, ..., x_{n-1}$ no es único. Lo que puede demostrar por inducción es que para cada $n$ hay una secuencia de $n$ -muchos elementos distintos de $X$ , pero esto no le da una forma de obtener un infinito secuencia de elementos de $X$ En realidad, este es exactamente el tipo de cosas para las que se necesita la elección.

Answer 3

Las otras respuestas han identificado correctamente el problema. Permítanme destacar la dificultad: es relativamente consistente con los axiomas de la teoría de conjuntos, excepto el axioma de elección, que hay conjuntos infinitos que no contienen una copia de los números naturales (es decir, hay conjuntos infinitos $X$ de manera que no haya ninguna inyección $f\!:\mathbb N\to X$ ).

Esto significa que la estrategia sugerida falla para estos conjuntos, pero es aún peor, ya que es no es cierto que estos conjuntos tienen un subconjunto propio del mismo tamaño. Tal vez esto parezca demasiado abstracto, así que vamos a explicar el punto:

Supongamos que $X$ es un conjunto infinito cerrado o abierto de reales. Podemos encontrar explícitamente un subconjunto contablemente infinito de $X$ en este caso (sin invocar el axioma de elección); este es un ejercicio decente que se puede intentar. Lo mismo ocurre si $X$ es un poco más complicado, por ejemplo si $X$ es una unión contable de conjuntos cerrados o incluso una unión contable de intersecciones contables de conjuntos abiertos (esto ya es un reto).

Sin embargo, una no puede incluso demostrar sin usar el axioma de elección que si $X$ es una intersección contable de uniones contables de conjuntos cerrados de reales entonces $X$ tiene un subconjunto propio del mismo tamaño. Estos son todavía conjuntos bastante concretos, y ya el axioma de elección es necesario aquí.