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

Proving sets with structural induction

  1. Feb 5, 2012 #1


    User Avatar

    Consider the set S defined recursively as follows:
    • 3 ∈ S,
    • if x,y ∈ S,then x−y∈S,
    • if x∈S, then 2x ∈ S,
    • S contains no other element.
    Use Structural Induction to write a detailed, carefully structured proof that
    ∀ x ∈ S, ∃ n ∈ Z, x = 3n.

    What I've got is since 3 is in the set, then 2 * 3 = 6 is also in the set, 6 = 3 * 2 (n=2).
    Let x = 6 and y = 3, 6-3 =3 is also in the set which is 3 * 1 = 3 (n=2).

    It works on x = 12, y=6 as well. Is that the way to prove it?
  2. jcsd
  3. Feb 6, 2012 #2


    User Avatar
    Science Advisor
    Homework Helper

    No, the way to prove it is by structural induction. That means that, assuming you have an element/two elements that sastify the proposition, try to prove that a new element created from them also satisfies it.

    Let me give you an example.
    The trivial step is the first one: it is true for 3, taking n = 1.
    Now suppose that x∈S, so there is an n such that x = 3n. Consider y = 2x. Can you find a number m such that y = 3m?

    Now do something similar for z = x - y: what would be the thing to prove?
    Given that there exist n and m such that x = 3n and y = 3m, find a number k such that z = 3k.

    Do you see how this proves the statement for any number in S?
  4. Feb 6, 2012 #3


    User Avatar

    so consider y = 2x,
    a number m such that y = 3m, then m = 2n? because y = 2(3n).

    for z = x - y, x = 3n, y=3m,
    then z = 3n - 3m = 3(n-m).
    that means k = n-m?
    is that the right way?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook