can you use induction on n cases (as opposed to infinity)?

bennyska

1. The problem statement, all variables and given/known data
this is probably a dumb question, but i'm doing this proof where i have to show two sets are equal, where each set is a union from 1 to n sets. this is pretty easy to show with induction, i think, but i'm used to using induction when i have an infinite amount of things, so i'm not sure i'm allowed to use induction. any thoughts?

specifically, it goes like this:
Suppose that A_1, ..., An are Borel sets, that is they belong to ß. Define
the following sets: B_1 = A_1, B_n = A_n ∩ (A_1∪ ... ∪ A_n-–1)^c (^c is complement), and let S equal the universal set. Show that

U_i=1 to n A_i = U_i=1 to n B_i.

2. Relevant equations



3. The attempt at a solution

U_1 to 1 A_i = A_1 = U_1 to 1 B_i = B_1. So we have a base case. So assume it's true for n=k. Then we have that U_i=1 to k A_i = U_i=1 to k B_i.
Then we have that U_i to k B_i U B_k+1 = U_i to k A_i U (A_k+1 ∩ (A_1∪ ... ∪ A_k)^c
=U_i to k A_i U (A_k+1 ∩ A_1^c ∩ A_2^c...∩A_k^c)...
Let A_1^c ∩ A_2^c...∩A_k^c = D, and let U_i to k A_i = E
Then we have U_i to k B_i U B_k+1 = E U (A_k+1 ∩ D)
= (E U D) ∩ (E U A_k+1) = S ∩ (U_i to k A_i U A_k+1) = U_i=1 to k+1 A_i.

god that looks hideous. hopefully it makes sense. any comments would be appreciated.

micromass

Please take out a little of your time to learn LaTeX: http://www.physicsforums.com/showthr...=1#post3977517

Your post is close to unreadable.

Dick

That is hideous to read. The basic idea is that E U (A_k+1 n E^c)=E U A_k+1. Right? You can certainly use induction on a finite set of premises, no problem with that. It looks ok to me. Cleaning up the presentation certainly wouldn't hurt. Using TeX wouldn't hurt either. But I think you've got one way to do it.

Villyer

The purpose of induction is to show that if a statement is true for some value k, it has to be true for k+1.

It's up to you how far you want to extend your conclusion, so it's perfectly fine to use it on a finite set.

bennyska

alright, sorry i was a bit lazy on the latex, i didn't think it would be that bad originally, and i haven't used latex in a while.

i've attached a pdf. how does that look?

Attached Files

borel.pdf (69.6 KB, 9 views)

Dick

Fine. The deMorgan stuff is a little unnecessarily complicated. Just use that K U (L n K^c)=K U L. That's true, right?

who_

I'm not sure where the "finiteness" of your question is. Also, to answer your original question, it is perfectly fine to use induction where the variable you are inducting on has finite range. It is a common technique used in real analysis. In fact, the original definition of induction imposes no restriction that the variable has to have infinite (countably infinite) range.

bennyska

awesome, thanks you guys.