1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

  4. Jul 27, 2012 #3

    Dick

    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

    Dick

    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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook