I have an assignment in my text that asks me to "Show how induction can be used to conclude that $(A_1 \cup A_2 \cup \dots A_n )^c = A_1^c \cap A_2^c \cap \dots \cap A_n^c$. The issue I am facing is that I can prove DeMorgan's law for any $n$ without induction, and don't see why induction is necessary/possible here. Is it as simple as "let x belong to the complement of the union of $A_1$ through $A_n$ and assume the equation holds. Then if x belongs to the complement of the union $A_1$ through $A_{n+1}$, $x$ does not belong to $A_1, \dots, A_{n+1}$, thus belongs to each of their complements, thus is in the intersection of all of their complements." Is this the "induction?" Or would it be more correct to phrase it as "if x doesn't belong to $A_{n+1}$ then it belongs to its complement, and the equation holds?"
The other part of the question asks me to explain why induction can't be used to show that $\left (\bigcup_{n=1}^{\infty} A_n \right )^c=\bigcap_{n=1}^{\infty}A_n^c$. I am thinking it's because induction is valid only for a finite $n$, not infinity, but is there more to it? Thanks!!
Best Answer
Technically, almost any assertion about "$n$" that involves "dots" requires mathematical induction. In fact, even defining what we mean by $$\bigcup_{i=1}^n A_i$$ requires induction to prove that the object is well-defined.
The most amusing example I can think of is that to show $$0 = 0+0+\cdots + 0 \qquad \text{($n$ times)}$$ technically requires induction!
However, I think you are right in taking the hard-boiled mathematician's point of view that in the particular problem you are considering, you can "take in" the meaning of the expressions well enough to give a proof that does not mention induction explicitly.
And of course you are absolutely right in asserting that ordinary mathematical induction is not enough for the second problem. Induction could be used for the "finite" approximations to the infinite problem, but then you would need additional set-theoretic machinery to even define the meaning of countable union. That machinery (the set-theoretic axioms) is based on the intuition that the basic constructions we are familiar with in finite sets extend to infinite sets.
If, as an exercise, we wish to (or are instructed to) use induction to deal with the first problem, here is how one could proceed.
We could take the base case to be the case $n=1$, but we should also deal separately with $n=2$. Now suppose we have proved the result for $n=k \ge 2$. We want to prove the result for $n=k+1$.
Note that $$A_1 \cup A_2 \cup \cdots \cup A_{k+1}$$ is defined as being $$(A_1 \cup A_2 \cup \cdots \cup A_k) \cup A_{k+1}$$ The above is the union of two sets. Take the complement, using the $n=2$ case and the $n=k$ case to conclude that this complement is $$(A_1^c \cap A_2^c \cap \cdots \cap A_k^c) \cap A_{k+1}^c$$ By the definition of a $k+1$-fold intersection, we get the desired result.
Overall, the instruction to use induction seems kind of silly to me, though in fact it is technically correct from the point of view of the logic. But taking this "strictly logical" point of view gives induction, and logical thinking, a bad name. What's obvious is obvious.