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

Structural Induction on Sets

  1. Feb 5, 2012 #1

    thy

    User Avatar

    Consider the set T defined recursively as follows:

    • 2∈T,

    • if x∈T and x>1,then x/2 ∈T,

    • if x∈T and x>1,then x^2 ∈T,

    • T contains no other element.

    Use Structural Induction to write a detailed, carefully structured proof that ∀ x ∈ T, ∃ n ∈ N, x = 2n.


    I'm not sure how to do this proof.
    I assume ∀ x ∈ T, ∃ n ∈ N, x = 2n is true and try to prove then x/2 ∈T and x^2 ∈T?
     
  2. jcsd
  3. Feb 5, 2012 #2

    lavinia

    User Avatar
    Science Advisor
    Gold Member

    You just get powers of 2 from the recursion not any even number.
     
  4. Feb 5, 2012 #3

    thy

    User Avatar

    substituting 2n into x? So it becomes (2n) ^2?
    I don't really get it...
     
  5. Feb 5, 2012 #4

    lavinia

    User Avatar
    Science Advisor
    Gold Member

    I find with inductions that looking at simple examples leas to the general argument.

    So if 2 is in X then 1 is in X (2/2 = 1) so these are both powers of 2. The recursion only allows you to take these two numbers to get the next numbers. But 1 does not give any new numbers so we can forget about it and just look at 2. 2^2 is 4, another power of 2, and 4/2 = 2. So again you only have powers of 2. Form 4 you get 4^2, another power of 2, and dividing by 2 you get 8 and 4 and 2 again. This is the only thing that happens. Forn * and 16 you get more powers of two and so on.
     
  6. Feb 5, 2012 #5

    thy

    User Avatar


    thanks, it helps a lot
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Structural Induction on Sets
  1. Set Induction (Replies: 3)

Loading...