Posterior a investigar con especialistas en la materia, programadores de diversas áreas y profesores hemos dado con la solución a la interrogande y la compartimos en este post.
Solución:
El problema es que la inducción solo te dice que algo es true para cada entero finito.
Por ejemplo, por inducción podemos probar que todo número natural $ n $ tiene exactamente $ n $ predecesores ($ 0 $ es un número natural). ¿Significa eso que existe un número natural con infinitos predecesores? No, no lo hace.
Similarmente aquí. Si $ A $ es un conjunto infinito, sin el axioma de elección podemos probar que por cada $ n $ hay un subconjunto de $ A $ de tamaño $ n $. Pero, ¿podemos probar que existe un subconjunto equipotente con $ Bbb N $? No. Eso nos exige más. Eso requiere que las elecciones que hicimos durante la prueba inductiva fueran coherentes entre sí, lo que esencialmente nos dice que hay algún tipo de función de elección con la que podemos trabajar.
Y de hecho, sin el axioma de elección, es consistente que hay conjuntos infinitos sin subconjuntos infinitos numerables. Estos se denominan conjuntos finitos de Dedekind.
Quizás la siguiente elaboración aclare este tema. Veamos qué hace realmente la prueba inductiva.
Empieza con el conjunto vacío y tiene $ A $ para elegir. Eso le da $ | A | $ muchas opciones para un primer elemento en su secuencia. Suponer que logró obtener $ n $ opciones, eso le da $ | A | -n $ muchas opciones para continuar, y está bien, ya que $ | A | $ no es un número entero finito, siempre podemos hacer al menos una opción y continuar la construcción.
Pero que somos De Verdad construyendo? Es un árbol de opciones. Comenzamos con la raíz, que es la secuencia vacía. Luego, en cada paso, hemos dividido de acuerdo con nuestras opciones. En este caso, sin embargo, hay infinitas divisiones en cada paso.
La construcción inductiva simplemente nos dice que construimos un árbol sin puntos máximos. El axioma de elección nos dice que este árbol tiene una rama, que a su vez puede traducirse en un subconjunto infinito numerable. Pero la existencia de una rama depende en gran medida del axioma de elección. ¿Por qué elegirías que el primer elemento sea uno y no otro? ¿Qué tal el segundo elemento? No hay ninguna preferencia canónica que hacer aquí, en el caso arbitrario.
Entonces, lo que sucede es que sin elección, podría terminar con un árbol que no tiene nodos máximos, pero tampoco ramas infinitas.
(En la respuesta de Mitchell Spector, él analiza las definiciones inductivas, en ese caso, hay una función que elige “el siguiente paso”, por lo que el árbol es de hecho una rama única y todo está bien. Pero en la prueba que sugiere, hay sin tal función, apela a elegir elementos arbitrarios en cada paso).
Creo que aclarará las cosas pensar en cómo establecería realmente la definición de $ A_n $ por inducción. Deletrearlo en detalle mostrará exactamente dónde se usa el axioma de elección.
Primero, el principio formal de definición por inducción matemática que está utilizando se ve así:
Principio de definición por inducción matemática:
Para definir una función $ f $ desde $ omega $ a un conjunto $ E $ por inducción, comience con una función $ g colon E to E $ y un $ e_0 específico en E. $ Luego puede concluir que hay es un $ f colon omega to E $ único, tal que para todos los $ n lt omega, $ $$ f (n) = begin cases e_0, & text if n = 0, g (f (n-1)), & text if n gt 0. end cases $$
(Hay variantes, por ejemplo, se puede permitir que $ g $ dependa de $ n $ también, o puede configurar las cosas para una inducción fuerte, pero lo anterior es suficiente para lo que está haciendo).
La función $ f $ que está definiendo por inducción es $ n mapsto A_n. $ Para encajarla en la plantilla anterior, puede establecer $ E $ igual a la colección de todos los subconjuntos finitos de $ S $ (donde $ S $ es el conjunto infinito con el que está comenzando), y puede establecer $ e_0 = emptyset $ (en realidad comenzó con $ A_1 $ como un conjunto $ 1 text -element $, pero esto es más fácil).
Pero, ¿qué vas a usar para $ g?
Para que su construcción funcione, la función $ g colon E to E $ debe satisfacer la siguiente propiedad:
Para cualquier subconjunto finito $ X $ de $ S, $ $ g (X) in S setminus X. $
Es true que para cualquier subconjunto finito $ X $ de $ S, $ el conjunto $ S setminus X $ no está vacío. Sin embargo, se requiere el uso del axioma de elección para concluir que hay una función $ g $ con dominio $ E $ tal que para todo $ X $ en $ E, $ $ ; g (X) en S setminus X. $