Prove by induction onn: If a setAhasnelements, its power set has 2^nelements.

*Given a setA, thepower setofAis the set of all subsets ofA

Printable View

- Nov 27th 2010, 04:38 PMthamathkid1729Cantor's Theorem
Prove by induction on

*n*: If a set**A**has*n*elements, its power set has 2^*n*elements.

*Given a set**A**, the*power set*of**A**is the set of all subsets of**A** - Nov 27th 2010, 04:51 PMArchie Meade

**P(k)**

The power of a set with k elements is $\displaystyle 2^k$

**P(k+1)**

The power of a set with k+1 elements is $\displaystyle 2^{k+1}$

Show that P(k+1) must be true if P(k) is true.

If a set of k elements has a power of $\displaystyle 2^k$

then an added element will form $\displaystyle 2^k$ new subsets as it can be placed with all $\displaystyle 2^k$ existing subsets.

Therefore a set of k+1 elements has a power of $\displaystyle (2)2^k$ if a set of k elements has power $\displaystyle 2^k.$

Finally prove for the base case. - Nov 27th 2010, 05:47 PMPlato
This proof turns on a simple fact: $\displaystyle 2^n+2^n=2(2^n)=2^{n+1}.$

Any subset of $\displaystyle \{1,2,\cdots,n\}$ is a subset of $\displaystyle \{1,2,\cdots,n,n+1\}.$

So by uniting any subset of $\displaystyle \{1,2,\cdots,n\}$ with $\displaystyle \{n+1}\}$ we get a subset of $\displaystyle \{1,2,\cdots,n+1\}$.