This may seem a vague question, but in the process of explaining the hierarchy of transfinite sets to my students, I've had to use the Cardinality(powerset(S)) > Cardinality(S) argument, which appeared to me to be extremely weak in indicating how much larger the powerset is. Is there a better argument?


In contrast, Cantor's diagonalization argument shows that the set of reals is very much larger than the set of natural numbers -- the argument shows that there is a vast number of reals unaccounted for in any attempted bijection between the naturals and the reals. 


But then, when we get to the hierarchy of the alephs, I depend upon the argument that the powerset(S) is larger than S. Perhaps it's the version of that argument that I use, but all I'm able to show is that there is a single element of the powerset(S) unaccounted for in any attempted bijection between the powerset(S) and S. While this shows that the powerset is larger, it doesn't give any indication that it must be very, very much larger (and we are talking about infinite sets here). This is a hard way to impress my students about the vastness of each larger transfinite set.


Is there a better argument for showing that the powerset of a transfinite set is vastly larger than the set? I'm, in particular, looking for an argument that I can explain to talented high school math students.




---


Added later:


Thanks for all the comments so far. As many have pointed out, I've been a little too vague, so let me be more precise. 


The argument I present to students that the set of reals is (vastly) larger than the set of naturals is exactly the one that Jason mentions below in the first sentence of his second paragraph. Namely, in Cantor's diagonalization argument, one simply chooses a different digit in the kth position of the kth real in the supposed ordering of the reals. This will ultimately provide a large number of reals not in the proposed bijection between naturals and reals.


In contrast, the argument that I've used to show my students that the powerset(S) is larger than S is based on the Russell Paradox. Suppose there were a one-to-one correspondence between elements of S and subsets of S. Let Subset A be those elements of S which are each matched to a subset that contains it. Let Subset B be the rest of the elements of S, namely each element which has been matched to a subset not containing that element. Since there is a supposed one-to-one correspondence, subset B should be matched to some element of S, but this results in a contradiction. Therefore there is at least one element in the powerset of S (this subset B) which doesn't have a match. So the powerset(S) is larger than S... by at least one element.


So that is the root of my complaint: that the argument I'm using to show that the reals are larger than the naturals demonstrates a vast number of reals that are not covered by any trial bijection. But the argument I'm using to show that the powerset(S) > S shows only one element larger.


So I'm either misunderstanding the conclusion of the powerset argument I'm using (it really does show that the powerset is vastly larger), or I need a better elementary argument than that...



How much larger is the powerset of a transfinite set?
For infinite sets, $A$ having larger cardinality than $B$ already implies that $A$ is "much larger," and perhaps a good way to see this is to think of all the ways of making $B$ "larger" which *don't* increase its cardinality. E.g. taking the union with any set of equal or smaller cardinality, taking the Cartesian product with a set of equal or smaller cardinality, etc.


Perhaps you want to know if there are a lot of other cardinalities in between those of $B$ and $2^B$. This question can't be answered with the usual axioms of set theory. For more information, read about the [generalized continuum hypothesis](http://en.wikipedia.org/wiki/Continuum_hypothesis#The_generalized_continuum_hypothesis).


Edit: In your extended question, you mention that the usual argument only guarantees that the power set $2^A$ has "one more" element than the original set $A$: given a map $\phi : A \to 2^A$, there is at least one element not in the image of $\phi$. Call that element $x$. Certainly there is a bijection between $A$ and $A \cup \{x\}$, so repeating your argument shows there isn't a bijection between $A \cup \{x\}$ and $2^A$; at least one element is missed. So in fact $2^A$ has "two more" elements than $A$. Repeating this, one sees there are infinitely many elements missed. Moreover, by showing that $A \times A$ cannot be mapped onto $2^A$, there are at least "$|A|$ more" elements in $2^A$, and so on.


This is what I was trying to get at in my first paragraph. Of course, it has to be understood in the context that adding one element to an infinite set doesn't actually make it any larger in the sense of cardinality. To my mind, cardinality is a very crude measure of the "size" of an infinite set, and so any operation that enlarges it to an extent that it can be detected by cardinality must be a very dramatic enlargement indeed.


