Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Can you use induction on n cases (as opposed to infinity)?

  1. Jul 27, 2012 #1
    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.
  2. jcsd
  3. Jul 27, 2012 #2
  4. Jul 27, 2012 #3


    User Avatar
    Science Advisor
    Homework Helper

    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.
  5. Jul 27, 2012 #4
    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.
  6. Jul 27, 2012 #5
    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:

  7. Jul 27, 2012 #6


    User Avatar
    Science Advisor
    Homework Helper

    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?
  8. Jul 28, 2012 #7
    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.
  9. Jul 28, 2012 #8
    awesome, thanks you guys.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook