Cantor's Theorem says Let X denote any set.  Then |X| < |P(X)| where
P(X) denotes the set of all subsets of X also known as the powerset of
X.  Note the | | symbol represents the cardinality of the set, not
absolute value.  Using Cantor's Theorem,
1. Show there are "infinitely many different infinities" - what Cantor
calls cardinal numbers.
2. Show that the set P(N) is uncountable or otherwise deduce that 2^N
is uncountable.  Where N is the set of all natural numbers.

I'm just talking out my ass, but...

1) |P(X)|<|P(P(X))|<|P(P(P(X)))|<|P(P(P(P(X))))|<... 
if X is infinite each set has size infinity and each infinity is
greater then the last.

2) I'd try to make a 1:1-onto mapping that brings P(X) <-> interval (0,1)
You'll have to work some rigor into the language, but if you stick a
decimal place infront of each element of P(X) intuitively you can have
any element on (0,1). That the interval (0,1) is uncountable either
should not need proving at this point in your math career or else you
can look it up.

Whoops, thinking about the second statement, Its not nearly as easy as
i made it sound.. sorry...

I think the second statement is easy, with the instruction to use Cantor's Theorem.

A set X is finite or countably infinite if and only if |X| <= |N|.  So
how would we show P(N) is uncountable from Cantor's Theorem?

regards, mathtalk-ga

I'll leave math advice to the pros.

Might you clarify what further knowledge you are allowed to assume? I
ask because it appears that part 2 is trivial -- any cardinal greater
than |N| is by definition uncountable, and Cantor's theorem guarantees
that |P(N)|is some cardinal larger than |N|; thus part 2 is immediate.
Or are you looking for a direct proof of the uncountability of |P(N)|?

I am looking for a direct proof to show that |P(N)| or 2^N is
uncountable.  (N being the set of natural numbers).  As far as I know,
we are not allowed to assume anything else.It might seem trivial, but
for someone who is learning for the first time about proofs it seems
so foreign.  If you need anything further, please let me know.
Thanks :)

The google answerers are pretty strict about not giving answers to
questions that look just like homework. Clues may be all you get.
Sorry.

2. Show that the set P(N) is uncountable or otherwise deduce that 2^N
is uncountable.  Where N is the set of all natural numbers.

Pf. Following Shockandawe's suggestion:P(N) =  2^N = {f:N->{0,1}} =
{all functions from N to {0,1}} where the function f corresponds to
the set A(f)={n in N | f(n) = 1}, i.e., f is the characteristic
function of A(f). For each f create the binary decimal:

x(f) = Sum[f(i)*10^(-i), i,1,2,...] = 0.f(1)f(2).... 

Every real number in the interval [0,1] is represented by such an
infinite decimal. This is known to be uncountable by Cantors diagonal
argument: Assume the set of all x(f) were countable and let them be
numbered:
x1 = 0.a11a12a13...
x2 = 0.a21a22a23...etc

define x = 0.b1b2b3... where bi = aii+1 Modulo 2. Then x is not equal
to xi for any i since the ith binary digit is different by
construction.

Than you very much guys.  I think this will work.

That should be THANKS very much.