# Cantor's Theorem

• Nov 27th 2010, 04:38 PM
thamathkid1729
Cantor'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 PM
Quote:

Originally Posted by thamathkid1729
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

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 PM
Plato
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\}\$.