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

Show that the set of sets {An} has n elements

  1. Mar 2, 2014 #1
    We define by recursion the set of sets {An:n∈ℕ} this way:

    A_0=∅
    A_n+1=A_n ∪ {A_n}.

    I want to prove by induction that for all n∈ℕ, the set A_n has n elements and that A_n is transitive (i.e. if x∈y∈A_n, then x∈A_n).

    My thoughts:

    for n=0, A_1 = ∅∪ {∅} = {∅}

    then, for n+1: A_n+2 =A_n+1 ∪ {A_n+1}

    I'm confused on how to proceed.
     
    Last edited: Mar 2, 2014
  2. jcsd
  3. Mar 2, 2014 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Could you give the exact definition of what it means that a set has ##n##elements?

    I feel it might be useful to prove by induction that

    [tex]A_{n+1} = \{A_0,...,A_n\}[/tex]

    Then proving transitivity is a lot easier.
     
  4. Mar 3, 2014 #3

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    For n=0, A_0=∅ has 0 elements.

    Suppose A_n has n elements, prove A_n+1 has n+1 elements. Than you are done proving the number of elements. The transitive part is probably similar.
     
  5. Mar 3, 2014 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Again, what do you mean with "a set has ##n## elements"?
     
  6. Mar 3, 2014 #5

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    I'm not sure I understand the question. I mean that the set is finite, countable and when you count the elements, there are n of them.
     
  7. Mar 3, 2014 #6

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Not really a formal definition though. But maybe the OP is happy with handwaving.
     
  8. Mar 4, 2014 #7

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Although, in this particular case, you might need also to justify that the elements are different from each other!
     
  9. Mar 4, 2014 #8

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    I don't want to get into a discussion here over what counting with natural numbers means.
     
  10. Mar 4, 2014 #9

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Ok, good to know.

    But maybe the OP needs to have such a discussion in order to correctly answer his question. It depends what his professor is happy with.
     
  11. Mar 4, 2014 #10

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    I am not trying to do his homework. I'm just trying to point out where he was missing the proof by induction because he was not using the fact that it is true for n in the proof of n+1. That seemed to be the original OP question. I don't know what is assumed or wanted in his class.
     
  12. Mar 4, 2014 #11

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    In this very special case, induction is actually not needed if you define things the correct (and the usual) way.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook