Please help understand the solution on Math Induction

[phillyolly]

Homework Statement

Please help me understand the given solution. Is there a simpler way of solving the problem?

Homework Equations

The Attempt at a Solution

 

[╔(σ_σ)╝]

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 ?

Please, elaborate on your difficulties.

 

[phillyolly]

I don't follow logic...

 

[╔(σ_σ)╝]

I don't follow logic...

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 ?