1. Aug 29, 2010

### phillyolly

1. The problem statement, all variables and given/known data

2. Relevant equations

3. The attempt at a solution

#### Attached Files:

• ###### pic.jpg
File size:
48.2 KB
Views:
85
2. Aug 29, 2010

### ╔(σ_σ)╝

I am no expert but this is usually the proof given in most txtbooks.
The proof is board, so which part do you not understand ?

Do you know the definition of the power set ? Can you follow the logic of the proof or are you having trouble with the logic ?

Last edited: Aug 29, 2010
3. Aug 29, 2010

### phillyolly

4. Aug 29, 2010

### ╔(σ_σ)╝

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. Lets 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 ?

Last edited: Aug 29, 2010