Structural Induction on Sets

[thy]

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?

 

[lavinia]

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?

You just get powers of 2 from the recursion not any even number.

 

[thy]

You just get powers of 2 from the recursion not any even number.

substituting 2n into x? So it becomes (2n) ^2?
I don't really get it...

 

[lavinia]

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.

 

[thy]

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.

thanks, it helps a lot