# Proving sets with structural induction

1. Feb 5, 2012

### thy

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. Feb 6, 2012

### CompuChip

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?

3. Feb 6, 2012

### thy

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?