Uso de la inducción para ampliar la ley de DeMorgan

Question

Tengo una tarea en mi texto que me pide que "demuestre cómo se puede utilizar la inducción para concluir que $(A_1 \cup A_2 \cup \dots A_n )^c = A_1^c \cap A_2^c \cap \dots \cap A_n^c$ . El problema al que me enfrento es que puedo probar la ley de DeMorgan para cualquier $n$ sin inducción, y no veo por qué la inducción es necesaria/posible aquí. ¿Es tan sencillo como "que x pertenezca al complemento de la unión de $A_1$ a través de $A_n$ y asumir que la ecuación se mantiene. Entonces si x pertenece al complemento de la unión $A_1$ a través de $A_{n+1}$ , $x$ no pertenece a $A_1, \dots, A_{n+1}$ , por lo que pertenece a cada uno de sus complementos, por lo que está en la intersección de todos sus complementos". ¿Es ésta la "inducción"? O sería más correcto expresarlo como "si x no pertenece a $A_{n+1}$ entonces pertenece a su complemento, y la ecuación se mantiene?"

La otra parte de la pregunta me pide que explique por qué no se puede utilizar la inducción para demostrar que $\left (\bigcup_{n=1}^{\infty} A_n \right )^c=\bigcap_{n=1}^{\infty}A_n^c$ . Estoy pensando que es porque la inducción es válida sólo para un finito $n$ no el infinito, pero ¿hay algo más? ¡Gracias!

Answer 1

Técnicamente, casi cualquier afirmación sobre " $n$ " que implique "puntos" requiere una inducción matemática. De hecho, incluso definir lo que entendemos por $$\bigcup_{i=1}^n A_i$$ requiere la inducción para demostrar que el objeto está bien definido.

El ejemplo más divertido que se me ocurre es que para mostrar $$0 = 0+0+\cdots + 0 \qquad \text{($ n $ times)}$$ ¡técnicamente requiere inducción!

Sin embargo, creo que tienes razón al adoptar el punto de vista del matemático empedernido de que en el problema particular que estás considerando, puedes "asimilar" el significado de las expresiones lo suficientemente bien como para dar una prueba que no mencione la inducción explícitamente.

Y, por supuesto, tienes toda la razón al afirmar que la inducción matemática ordinaria no es suficiente para el segundo problema. La inducción podría utilizarse para las aproximaciones "finitas" al problema infinito, pero entonces se necesitaría una maquinaria teórica de conjuntos adicional para definir incluso el significado de la unión contable. Esa maquinaria (los axiomas de la teoría de conjuntos) se basa en la intuición de que las construcciones básicas con las que estamos familiarizados en conjuntos finitos se extienden a los conjuntos infinitos.

Si, como ejercicio, deseamos (o se nos indica) utilizar la inducción para tratar el primer problema, he aquí cómo se podría proceder.

Podríamos tomar como caso base el caso $n=1$ pero también debemos tratar por separado $n=2$ . Ahora supongamos que hemos demostrado el resultado para $n=k \ge 2$ . Queremos demostrar el resultado para $n=k+1$ .

Tenga en cuenta que $$A_1 \cup A_2 \cup \cdots \cup A_{k+1}$$ es definido como ser $$(A_1 \cup A_2 \cup \cdots \cup A_k) \cup A_{k+1}$$ Lo anterior es la unión de dos conjuntos. Tome el complemento, utilizando el $n=2$ caso y el $n=k$ caso para concluir que este complemento es $$(A_1^c \cap A_2^c \cap \cdots \cap A_k^c) \cap A_{k+1}^c$$ Según la definición de $k+1$ -intersección doble, obtenemos el resultado deseado.

En general, la instrucción de utilizar la inducción me parece un poco tonta, aunque de hecho es técnicamente correcta desde el punto de vista de la lógica. Pero adoptar este punto de vista "estrictamente lógico" da mala fama a la inducción, y al pensamiento lógico. Lo que es obvio es obvio.

Answer 2

La inducción que los autores del texto probablemente tienen en mente es considerar $B=A_2\cup\cdots\cup A_{n+1}$ y utilizar la hipótesis de inducción dos veces, primero para los dos conjuntos $A_1$ y $B$ y luego para el $n$ conjuntos que componen $B$ .

Estoy de acuerdo en que esto no es necesario para demostrar la ley de De Morgan.

Con respecto a tu última pregunta, tienes razón: el punto clave es que la inducción sólo da el resultado para todo finito $n$ (en caso contrario, considerando la hipótesis de que todo conjunto de tamaño $n$ es finito, se podría demostrar que los conjuntos contables son finitos).