Proving |2^{A}| = 2^|A| Using Mathematical Induction - Step By Step Guide

[bigrodey77]

Hey all,

As I said in one of my earlier posts I'm not that good with proofs, hence why I have another post.

Here is the one I'm on now...

Prove using mathematical induction that |2^{A}| = 2^{|A|} where A is a finite set.

..Here is what I have so far

http://img293.imageshack.us/img293/1944/proofdu9.jpg

Any help is greatly appreciated.

Thanks!

 

[fopc]

Hey all,

As I said in one of my earlier posts I'm not that good with proofs, hence why I have another post.

Here is the one I'm on now...

Prove using mathematical induction that |2^{A}| = 2^{|A|} where A is a finite set.

..Here is what I have so far

http://img293.imageshack.us/img293/1944/proofdu9.jpg

Any help is greatly appreciated.

Thanks!

You might look at a proof this way.

Let's let |S| = n and S' = S U {a} (where a is not in S). Clearly, |S'| = n+1.
Let P(S) and P(S') denote their powersets.
Let A = {B U {a} | B is in P(S)}.

In the induction step, the induction hypothesis says |P(S)| = 2^n.
So if you can show the following

1. P(S') = P(S) U A,
2. P(S) and A are disjoint,
3. |A| = 2^n,

you'll be home.

Of course, induction isn't the only approach.
You might think about a proof based on characteristic maps.

 

[HallsofIvy]

2^A means, of course, the collection of all subsets of A. |A| is the number of elements in A and |2^A| is the number of elements in 2^A, i.e. the number of subsets of A. And, of course, we are assuming A is a finite set.

Assume, as you did in the induction, that |2^A|= 2^|A| for all sets with k members: |A|= k. Now let B be a set with k+1 members: |B|= k+1. Let x be a specific member of B (since |B|= k+1> 0, there exist such a member). Every subset of B either includes x or it does not. Those subsets that do not include x are subsets of B\{x} which has k members. How many of them are there? Those subsets that do include x can be thought of as C\cup {x} where C is a subset of B that does not include x. How of them are there? How many subsets does B have?