Structural Induction on Sets
View Single Post
Feb5-12, 06:47 PM
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