3 ms·

Your explanation of why a powerset of a countable set is not countable didn't make intuitive sense to me, but wikipedia concurs ( http://en.wikipedia.org/wiki/C

• joshzayin 14y ago
  Here's perhaps an easier to understand proof. Let A be a countable set. Now, suppose that there was a surjective function (one that hits every element of P(A)) f: A -> P(A). (Note that f takes elements of A, and produces subsets of A.) Now, define Y ⊆ A as follows: For all x in A, x is in Y if and only if x is not in f(x). Thus, Y, which is in P(A), is distinct from every output of f, and so f is not actually surjective. This means that no surjective function f: A -> P(A) exists. This is a generalization of Cantor's Diagonal Argument (http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument).
• tikhonj 14y ago
  Honestly, the reason my explanation didn't make sense is because I didn't explain it. I just took a countably infinite set's powerset's not being countable as a fact because it was mentioned in the article. Now, the fact that the set of functions from X to Y (usually written as X → Y) is uncountable if X or Y is countably infinite I did try to explain but failed :P.
• Evbn 14y ago
  It was actually a muddled and incorrect proof. Joshzayin gives a correct proof below.