Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!!

share|improve this question
    
Just to comment on the induction part, induction can be used to prove things in the infinite case, this is called a transfinite induction. It requires more care than the regular induction, though. –  Asaf Karagila Jun 13 '11 at 7:21
add comment

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

The induction the authors of the text probably have in mind is to consider $B=A_2\cup\cdots\cup A_{n+1}$ and to use the induction hypothesis twice, first for the two sets $A_1$ and $B$ and then for the $n$ sets composing $B$.

I agree this is not necessary to prove De Morgan's law.

Re your last question, you are right: the key point is that induction only gives the result for every finite $n$ (otherwise, considering the hypothesis that every set of size $n$ is finite, one could prove that countable sets are finite).

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.