h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

I got confused in your proof, only because of the explanation, but I have some problems with the existence of S: How do you know that S exists for any injection?
This might be obvious, but I'm used to mathematics in notational form which is convenient for me since I have a very short, short term memory.
Also, is P(X) the Boolean of X, if so then where does f({}) map.
Since A is in X this doesn't present a problem for me with S.
On the whole it's excellent and Reminded me of Russell, I hope I spelled his name right, X={A|A does not belong to{A}}.
In class we learned that if you arranged a subset of R of some of the numbers between (0,1), their binary expansions, in an array in a canonical correspondence with N, then looking down the diagonal choose another sequence 1-d where d is the value of the r,r position, we get one more different number not in correspondence.
Showing at least a set of numbers with more members than N.

"I got confused in your proof, only because of the explanation, but I have some problems with the existence of S: How do you know that S exists for any injection?"

S = {a in X such that there is some subset A of X with f(A) = a, and a is not in A}
(just for reference; this is the definition given in the article)

Remember that we're assuming f is one-to-one (which is really impossible). For any one-to-one function f: P(X) -> X, S is well-defined since it is certainly possible to take any element a of X and determine whether there is a subset A of X that maps to it. Since f is one-to-one, there must be AT MOST one A such that f(A)=a. Given that such an A does exist, it is certainly possible to determine whether a is an element of A. Each of these steps on its own is not a problem--it's only when we put it all together that we reach a contradiction (which is the goal, since we want to show f CAN'T be one-to-one).

"Also, is P(X) the Boolean of X, if so then where does f({}) map."

Since we're talking about an arbitrary function f, we don't know what f({}) is.

"On the whole it's excellent and Reminded me of Russell, I hope I spelled his name right, X={A|A does not belong to{A}}."

Careful of your brackets and functions. The set S is defined by S = {a in X|a does not belong to f(A)}. Russell's paradox is different, {A|A does not belong to A}. There are some similarities because of the self-reference, but in this proof there is no discussion of sets containing themselves (in fact, in axiomatic set theory, Russell's paradox is avoided by not allowing any set to contain itself). Russell's paradox is pretty interesting, though, especially since it always seems to crop up when you least expect it.

"In class we learned that if you arranged a subset of R of some of the numbers between (0,1), their binary expansions, in an array in a canonical correspondence with N, then looking down the diagonal choose another sequence 1-d where d is the value of the r,r position, we get one more different number not in correspondence.
Showing at least a set of numbers with more members than N."

This is often referred to as Cantor's Diagonalization Method, and it's a very elegant (in my opinion) way of proving that the reals are uncountable. It's also the case that |R| = |P(N)|, so it is a good way of showing that P(N) is uncountable. However, the proof given in this article is more general, since it works for any set (including finite ones!) and also shows that there are more than two sizes of infinity.

Shouls have read this first before my adden-dum. Thanks.