phillyolly said:
I don't blame you. The author has a not so friendly way of proving his proposition.
Basically, what the author is trying to do is use induction to show the if a set, A, has n elements then p(A) has 2^n elements. This much I know you understand.
The logic
The author shows that for n=0 this holds
The author uses the inductive hypothesis and assumes it holds for some K then, he tries to show it holds for K+1. This much I believe you understand.
To accomplish his purpose the author does the following. He takes a set of K+1 elements. Let's call this set A.
He then defines a set B like this
B= A/{x} [ B has all the elements in A except x ( some x ) , therefore B has K elements ]
We know by inductive hypothesis p(B) has 2^k elements, since B has K elements.
We also know that if we take
every subset of A it is either a subset of B or a set that contains the element x. Now we know there are two possible cases.
Cases
1) We have a subset of A that contains x
2) We have a subset of A that does not contain x.
We know that all subsets of B lie in A. We also know that the only thing that B is lacking is the element x.
So from this we can "conclude" , based on the two cases, that for every subset of A there are two kinds; one that contains x and one that does not. p(B) is a collection of all subsets of A that do not have x . So this means there is a p(B*) which consist of every subset of A that contains x.
Considering there are only two cases we can match up all the subsets that contain x and those that do not contain x.
That is, we can form a bijection from p(B) to p(B*).
From this we see that p(A) = 2p(B) = 2*2^k = 2^(k+1)
Do you understand a little more ?
