Duda sobre el uso de inducción para demostraciones que involucran infinidad

[c4ebt]

Me surgió una duda a partir de la Pregunta 4.a de la I2_2016-2, cuyo enunciado adjunto a continuación:

No se si el procedimiento que seguí para esta demostración es correcto. Lo que hice fue lo siguiente:

1. Demostré por inducción estructural que, con $S'$ y $S_i$ enumerables, $S' \cup S_i$ también es enumerable.
2. Concluí de (1) que la unión de dos conjuntos enumerables siempre resulta en un conjunto enumerable.
3. Como $S = {{\bigcup}^\infty}_{i \in \mathbb{N}} \ S_i$ resulta de repetir el proceso de (2) infinitas veces, los resultados de cada unión siempre son enumerables, por lo que en ningún punto de la unión generalizada se obtiene un conjunto no enumerable.
4. Finalmente, concluí que (3) implica que $S$ es enumerable.

¿Es correcto este procedimiento? Y, en general, ¿se puede usar inducción estructural (u otro tipo de inducción) de esta manera para demostrar la enumerabilidad de conjuntos resultantes de infinitos pasos constructivos, si se conoce de antemano el "paso constructivo" (en este caso la unión con otro conjunto enumerable) mediante el cual se construye el conjunto de interés?

Muchas gracias de antemano.

[ibgarrido]

A mi me parece que el espiritu de tu demostracion va por muy buen camino. Efectivamente la union de dos conjuntos numerables da un conjunto numerable. Podrias dar mas detalles de como probaste el paso inductivo :o?

[catalinaortegacalderon]

Hola!

La inducción demuestra que para todo natural se cumple cierta propiedad. El infinito no es un natura. Por ende, se cumple que la union de dos conjuntos numerables es numerable (k = 2), tambien tres conjuntos numerables (k = 3), tambien 1000 conjuntos numerables ( 1000 es un natural) pero no infinitos conjuntos numerables ya que el infinito no es un natural. Espero se entienda la lógica.

[c4ebt]

Hola! Lamento la demora en la respuesta, el fin de semestre requiere cambiar los ramos a los que se les da atención :(

Mi duda va precisamente a eso. Mi demostración no usa inducción simple ni inducción fuerte sobre el número de conjuntos de la unión generalizada, sino inducción estructural.

Por esto, no estoy demostrando que se cumple para la unión de $n$ términos con $n \in \mathbb{N}$, sino que demuestro que se cumple para cualquier conjunto construido a través del paso inductivo.

Aquí es donde está mi duda: si bien la unión generalizada hasta el infinito efectivamente es un resultado de ejecutar el paso inductivo (unión de dos conjuntos enumerables), este paso se debe realizar infinitas veces. A primera vista diría que la demostración es correcta, pero da para pensar.

Muchas gracias nuevamente por sus respuestas.

[ibgarrido]

Hola! Lamento la demora en la respuesta, el fin de semestre requiere cambiar los ramos a los que se les da atención :(

Mi duda va precisamente a eso. Mi demostración no usa inducción simple ni inducción fuerte sobre el número de conjuntos de la unión generalizada, sino inducción estructural.

Por esto, no estoy demostrando que se cumple para la unión de n términos con n∈N, sino que demuestro que se cumple para cualquier conjunto construido a través del paso inductivo.

Aquí es donde está mi duda: si bien la unión generalizada hasta el infinito efectivamente es un resultado de ejecutar el paso inductivo (unión de dos conjuntos enumerables), este paso se debe realizar infinitas veces. A primera vista diría que la demostración es correcta, pero da para pensar.

Muchas gracias nuevamente por sus respuestas.

Como te dijo la Cata, Lo que pasa es que la demostracion por induccion estructural permite demostrar para $U_{i \in N} S_i$, es decir, tu puedes darte cualquier intervalo de conjuntos (finito), eligiendo el numero que quieras (1 o 9^99999... o el que se te ocurra) y tu demostracion aplicaria. Sin embargo cuando se trata de una union infinita el escenario es distinto ya que no tenemos forma de 'acotar' la union de los conjuntos (y Ahi la induccion se cae).

Como para darte a entender mejor lo que ocurre: Tu puedes hacer un codigo que iterando encuentre numeros primos para demostrar que son infinitos y cada vez que el codigo avanza va a ir encontrando un primo, sin embargo eso no demuestra que los numeros primos son infinitos ya que no tenemos certeza si en algun momento el codigo dejara de proporcionar numeros primos (Afortunadamente existe una demostracion que hizo Euclides que demuestra que son infinitos).

En ese sentido creo que el mejor 'approach' para enfrentar este problema seria usar el argumento de diagonalizacion de cantor o buscarte una biyeccion. Te dejo este link en el cual creo yo podrias encontrar un poco de inspiracion siguiendo esa linea:

https://proofwiki.org/wiki/Countable_Union_of_Countable_Sets_is_Countable