# Why can i not use induction here?

1. Dec 17, 2007

### linuxux

I'm presented with this,

$$(1)\ (\bigcup^{\infty}_{\n=1}A_{n})^{c}\ =\ \bigcap^{\infty}_{\n=1}A_{n}^{c}$$

and asked why induction cannot be used to conclude this.

Now, i know the principle behind induction is to show that P(S)=N by showing that when

(i) S contains 1 and
(ii) whenever S contains a natural number n, it also contains n+1.

So I assume somewhere along the line (1) cant fit into either (i) or (ii), but i'm just not getting it. Help please, thanks.

I also have some trouble understanding infinity in general. My text says that, notationally,

$$(2)\ \bigcup^{\infty}_{\n=1}A_{n}$$

is just another way of saying the set whose elements consist of any element that appears in at least one particular (An), but, in a previous question, we already proved with induction that

$$(3)\ (A_1\ \cup\ A_2\ \cup\ A_3\ \cup\ ...\ \cup\ A_n)^c\ =\ A^{c}_{1}\ \cup\ A^{c}_{2}\ \cup\ A^{c}_{3}\ \cup\ ...\ \cup\ A^{c}_{n}$$

In my mind, (3) should lead to (1), and since we used induction on (3) to extrapolate to (1), then we did use induction to prove (1), but obviously, this is incorrect and im not sure why?

Last edited: Dec 17, 2007
2. Dec 17, 2007

### SiddharthM

Consider a sequence of sets, A_n. If an element x in not in the union of this collection of sets then it is not inside ANY set in this sequence of sets. (*)That means it is in the compliment of every set contained in the sequence of sets ie the intersection(*). We have shown the LHS is contained in the RHS of (1), now show the other containment using contraposition.

You can use induction to prove in detail the sentence surrounded with asterisks given the information of the previous sentence. A similar proof is used for the converse.

3. Dec 18, 2007

### HallsofIvy

The principle of induction can be used to prove that a statement S(n) is true for n any positive integer. It CANNOT be used to prove that a statement is true for infinity.

Induction can be used to prove
$$(1)\ (\bigcup^{N}_{n=1}A_{n})^{c}\ =\ \bigcap^{N}_{n=1}A_{n}^{c}$$
for any positive integer N.

It cannot be used to prove
$$(1)\ (\bigcup^{\infty}_{\n=1}A_{n})^{c}\ =\ \bigcap^{\infty}_{\n=1}A_{n}^{c}$$
because "$\infty$" is NOT a positive integer.

4. Dec 18, 2007

Thanks.