How much larger is the powerset of a transfinite set?

Question

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...

Answer 1

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.

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.

Answer 2

After being rather confused for a while at your edit, I think I finally now see the issue. Your point (I hope?) is that when diagonalizing against decimal expansions of real numbers, you have flexibility to choose each digit. That is, in ensuring that the $n$th digit of your "unlisted" decimal expansion differs from the $n$th digit of the $n$th element of the list, you can choose one of nine digits. However, in what you refer to the Russell paradox argument, your hands are tied. You aren't making any choices and there's just a single set it spits back at you. This makes it feel like the argument isn't giving you as much information about the number of unlisted elements of the power set.

As indicated by the responses, this intuition is not accurate. In fact, the arguments are essentially identical, but it might take a bit of familiarity with cardinal arithmetic to see it. The simplest way I can see to imbue the general powerset argument with a similar amount of flexibility is through some basic cardinal arithmetic. For each infinite aleph $\kappa$ it's not too hard to show that the disjoint union of two copies of $\kappa$ can be put into bijection with $\kappa$. Once you do this, you can iterate to get that the disjoint union of 10 copies of $\kappa$ (which I'll denote by $10\kappa$ for now) is again equinumerous with $\kappa$. From here you can argue that $\mathcal{P}(10\kappa)$ is the same size as $\mathcal{P}(\kappa)$, and thus enumerating $\mathcal{P}(\kappa)$ by $\kappa$ is possible if and only if enumerating $\mathcal{P}(10\kappa)$ by $\kappa$ is possible.

This gives you flexibility. You are now starting with a list of length $\kappa$ of subsets of $10\kappa$. For my convenience, I'll write it as a function $\phi: \kappa \to \mathcal{P}(10\kappa)$. For each $x \in \kappa$ you now have ten choices. You can put $x \in B$ iff the $x$ of the first copy of $\kappa$ in $10\kappa$ is not in $\phi(x)$. Or you might have a change of heart and put some other $y \in B$ iff the $y$ in the seventh copy of $\kappa$ in $10\kappa$ is not in $\phi(y)$. The upshot is that you can now build a huge family of possible sets $B$, one for each decision of copy of $\kappa$ for each $x$, and the same Russellian argument shows that any such $B$ is unlisted. This grants you the same flexibility as the diagonal argument (in fact, a little more, by the celebrated theorem "10>9," also known as my inability to plan in advance).

This argument can of course be distilled down to a couple lines by working in an appropriate sequence space, or performing more opaque cardinal arithmetic and so on, but I think it might be the most compelling to somebody at a high school level. I think it also lends itself well to drawing on the blackboard. Of course, there might be a yet simpler way of incorporating this sort of flexibility into the argument.

Of course, this should be taken in tandem with the advice of the other answers, which essentially explain why this flexibility doesn't matter, and the "vastness" between a set and its power set is not something one can easily formulate precisely (for good reason!).

I'll cross my fingers I didn't completely misunderstand your question!

Answer 3

As you probably know, $\aleph_1$ is (by definition) the first uncountable cardinality, and Cantor's continuum hypothesis is that $2^{\aleph_0} = \aleph_1$. For any ordinal $\alpha$, $\aleph_\alpha$ is defined by recursion ($\aleph_{\alpha + 1}$ is the first cardinality greater than $\aleph_\alpha$, and if $\alpha$ is a limit ordinal, then $\aleph_\alpha$ is the supremum of $\aleph_\beta$ taken over all $\beta < \alpha$). The generalized continuum hypothesis (GCH) is that $2^{\aleph_\alpha} = \aleph_{\alpha + 1}$.

Under the standard ZFC axioms, there is a lot of leeway in what $2^{\aleph_\alpha}$ might be: assuming that ZFC is consistent, it is consistent to assume GCH holds, and it is also consistent to assume it fails dramatically, as Nate has already answered. (For just how much leeway one has, see Easton's theorem.)

So as to how vastly larger $2^{\aleph_0}$ is than $\aleph_0$, one can't be too definitive within the confines of ZFC. But it may be possible to give a glimmer, even under the most conservative assumption (continuum hypothesis), that $\aleph_1$ is in some sense far, far larger than $\aleph_0$. Nate has already given some suggestions; an alternate suggestion is to get your students to take a tour through the land of countable ordinals, and get a feel for how indescribably large they can get (as ordinals). Then, $\aleph_1$ is bigger than all of them: it can be defined as the supremum of all ordinals of countable cardinality, hence greater than any of them.

For a gentle introduction to sizes of countable ordinals, you might try John Baez's This Week's Finds, Number 236. My own favorite description involves consideration of fixed points of certain order-preserving maps on $\aleph_1$, as touched upon in this article by Hilbert Levitz. Your students might enjoy trying to outdo each other in describing really whoppingly large countable ordinals, and using these to describe really super-fast growing functions on the integers, as described for example here. It's loads of fun.

---

Edit: I had meant to mention this but then forgot. Another fun thing for your students to think about with regard to the continuum hypothesis is Freiling's argument that the continuum is larger than $\aleph_1$. It's just an intuitive argument, really, but some mathematicians (notably David Mumford) seem to take it seriously.

---

Edit 2: I've just seen P. Brooks' most recent edit, and maybe I can help. Explain to your students that there is an explicit bijection between subsets of $\mathbb{N}$ and binary sequences, as per Jason's answer. Then, explain to your students that there is also an explicit bijection between binary sequences and hexadecimal sequences. (You see it, right?) So if there exists a bijection between $\mathbb{N}$ and $P(\mathbb{N})$, there would exist an explicit bijection between $\mathbb{N}$ and hexadecimal sequences. Then the same proof, that the existence of a bijection between $\mathbb{N}$ and decimal expansions leads to a contradiction, can be adapted with "hexadecimal" in place of "decimal". Thus, there are clearly "vastly more" hexadecimal expansions than there are natural numbers.

One thing to point out here is that the proof "based on Russell's paradox" really is a diagonalization argument in disguise! (Historically, what I think what happened is that Russell applied the idea behind Cantor's diagonalization to devise his paradox, to show the inconsistency in Frege's system.) Given a putative bijection $\phi$ from $\mathbb{N}$ to the set of binary sequences $2^{\mathbb{N}}$, one shows that the sequence $x_n = 1 - \phi(n)(n)$, obtained from the diagonal $\phi(n)(n)$ by changing all 0's to 1's and all 1's to 0's, is not in the image of $\phi$. That's the diagonalization argument. But it's morally the same as the Russell-paradox style argument where a putative bijection $\psi: \mathbb{N} \to P(\mathbb{N})$ is considered and one forms $\{n: n \notin \psi(n)\}$; the role of the negation (changing $\in$ to $\notin$) is isomorphic to the role played by changing 0's to 1's and 1's to 0's (thinking of 0's and 1's as the truth values "false" and "true").

Answer 4

Nate and Todd gave good answers already, but here is something that I am wondering about:

You say you were using the "Cardinality(powerset(S)) > Cardinality(S)" argument, which, given a map from an infinite set $S$ to its power set, exhibits a single subset of $S$ not in the range of the map.
Isn't that exactly what Cantor's argument showing that the set of reals is uncountable does? You start with a map from the natural numbers to the reals and then exhibit a real number that does not appear in the list.

To me these two arguments are practically identical and I don't see how the argument for the reals shows that there are "much more" real than natural numbers.

Finally, the "Cardinality(powerset(S)) > Cardinality(S)" argument does not assume that $S$ is infinite, actually. It works just as well in the finite and even when $S$ is empty!

All of this seems too vague without specifically saying what I think you mean by the "Cardinality(powerset(S)) > Cardinality(S)" argument:

Let $S$ be a set, $\mathcal P(S)$ its power set. Suppose $f:S\to\mathcal P(S)$ is any function. We show that $f$ is not onto. Let $X=\{x\in S:x\not\in f(x)\}$. Suppose $X$ is in the range of $f$, i.e., $X=f(x)$ for some $x\in S$. Checking the two cases $x\in f(x)$ and $x\not\in f(x)$ we arrive at a contradiction. This shows that $X$ is not in the range of $f$.

Answer 5

As Stefan mentions, the Cantor diagonal argument is completely general to larger cardinals. The difference merely is that the indices of your list range over infinite ordinals rather than just the finite ones. However, if I correctly understand the difference you are trying to point out, it's this:

Given a countable list of infinite decimal expansions of Real numbers between 0 and 1, one can easily produce infinitely many such numbers not in this list by the Cantor diagonal argument because when selecting the $n^{th}$ digit, we have $9$ choices that won't match the given digit. On the other hand, for our constructed subset of $\aleph_{\alpha}$, our choice is uniquely determined using the Cantor diagonal argument across the main diagonal, mainly we include a given $\beta < \aleph_{\alpha}$ if and only if it is not in the $\beta^{th}$ subset in our list.

However, as you are probably aware, $2^{\aleph_0}$ represents the cardinality of the set of functions from $\mathbb{N}$ into $\{0, 1\}$ or the number of subsets of $\mathbb{N}$ by viewing the binary functions as characteristic functions determining membership (i.e., $n \in S_f \Leftrightarrow f(n) = 1$). The fact that $10^{\aleph_0}$ (cardinality of set of functions from $\aleph_0$ into $\{0, 1, \ldots, 9\}$) can be put into one to one correspondence with $2^{\aleph_0}$ is not unique to $\aleph_0$. Specifically, $10^{\aleph_{\alpha}}$ can be put in one-to-one correspondence with $2^{\aleph_{\alpha}}$ for any $\aleph_{\alpha}$, and this goes along the lines of what Nate was saying about certain operations not affecting cardinality. In fact, since $2^{\aleph_{\alpha}} = (2^{\aleph_{\alpha}})^{\aleph_{\alpha}}$, we actually have $2^{\aleph_{\alpha}}$ many choices for $f(\beta)$ for each $\beta < \aleph_{\alpha}$ using the Cantor diagonal argument when constructing our $f$. Therefore, if anything, the Cantor diagonal argument shows even wider gaps between $\aleph_{\alpha}$ and $2^{\aleph_{\alpha}}$ for increasingly large $\alpha$ when viewed in this light.

---

A way to emphasize how much larger $2^{\aleph_0}$ is than $\aleph_0$ is without appealing to set operations or ordinals is to ask your students which they think is larger:

(a) The number of possible books that can be written in any language

(b) The number of Real numbers between $1/10^{1001}$ and $1/10^{1000}$

The first answer would of course be only countably many since there are countably (or finitely) many possible alphabet symbols, and each book has only finitely many characters. You can then ask variations of (a) by making it sound larger. For example, you can ask what would happen if there were actually countably infinite many possible languages. At a more advanced level, you could replace (b) with the nowhere dense Cantor set.

---

The rest of this answer is most likely not suitable below the college level, but I'll mention it anyway just in case:

If you are extremely ambitious (going along the large countable ordinal route that Todd mentions), you could consider various reflection/Löwenheim-Skolem arguments. For example, for any fixed finite fragment of the theory of ZFC, ZFC proves that we have a countable transitive model $M$ of this fragment of set theory. In this case, $2^{\aleph_0} > \aleph_0 = |M|$, but assuming we chose a sufficiently large finite fragment, $M$ will contain a fairly rich array of definable countable ordinals. You can then point out that such a model will have all of the "natural" functions $f: \mathbb{N} \rightarrow \mathbb{N}$ so it will still know that ordinals such as $\epsilon_0$ are countable. But $M$ has many ordinals beyond what it can put into one to one correspondence with $\aleph_0$, mainly all of the actual countable ordinals that it thinks are uncountable. Similarly, there will be many ordinals that $M$ can put into one-to-one correspondence with $\aleph_{\alpha}^M$ for every ordinal $\alpha \in M$. But again, all of these ordinals are actually countable.

Answer 6

This is not an answer per se, but it sums up many of the points made in earlier answers.

If the question is: "How many more elements does $\mathcal P(S)$ have than $S$?" then the answer is of course: $|\mathcal P(S)|$ !

(Why? Because $\mathcal P(S)$ has $|\mathcal P(S)\smallsetminus S)|$ more elements than $S$, and we know that $|\mathcal P(S)\smallsetminus S)|=|\mathcal P(S)|$.) This may seem like a really trivial remark, but the point is this: if you only understand sets of size $|S|$, then $\mathcal P(S)$ has so many elements that you don't understand how many more it has. So sentences like "one more", "two more", ... , "$\aleph_0$ more", and even "$|S|$ more" can't even begin to describe it.

Answer 7

Here I am collecting some comments I made on this question into a CW answer, which should be easier to read and respond to.

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.

As others have touched on in their answers, it's somewhat debatable what the first sentence even means: there is no agreed upon meaning for "vastly larger" among infinite sets. One could even argue (as Nate Eldredge did above, rather cogently in my opinion) that "having larger cardinality" is a reasonable way to construe "vastly larger": thus the set of rational numbers is larger than that of the natural numbers, but the set of real numbers has larger cardinality so is "vastly larger".

To say much more than this goes into subtleties of set theory that the average working mathematician need not be conversant with. You might want to mention the Generalized Continuum Hypothesis -- which argues against any stronger sense of "vastly larger" -- and you might try expressing that in some precise sense GCH has been shown to be equiconsistent with the usual axioms of set theory. But to understand this one needs training in mathematical logic and exposure to the specific axioms of ZFC set theory, which again plenty of research mathematicians do not have. So I don't think it will make much sense to high school students, however bright. In particular I would advise against the sort of thing Asaf Karagila mentions in his comment:

[E]xplain vaguely that the power set can be almost anything larger, so it must be vastly larger.

The first part of this comment alludes to rather sophisticated ideas in logic and set theory -- i.e., for which ordinals $\alpha$ is the equation $2^{\aleph_0} = \aleph_{\alpha}$ equiconsistent with ZFC? (And to answer one must, presumably, mention things like cofinality...) On the other hand, the last part -- "so it must be vastly larger" -- is, as far as I understand it, a heuristic / intuition rather than a precise mathematical statement. One should be careful not to conflate these kinds of things.

At least, these are my opinions. If I were a professional set theorist I might have more confidence in my insight. But that's a key point too -- the OP sounds like he is not fully conversant with the post-Cohen age of axiomatic set theory. (That's not meant to be a stinging insult: it applies equally well to me.) I would tell anyone working with high school students -- especially bright ones -- to stick to things they know and understand very well.

Answer 8

I think if you really try to wrap your head around the fact there is no surjection $S \to \mathcal{P}(S)$, you will see that it already does imply that the cardinality of $\mathcal{P}(S)$ must be, in some sense, "vastly larger". You shown any particular alleged surjection must be missing one element. But it's easy enough to find a new alleged surjection whose image contains the new element in addition to all of the previous ones' -- and that still isn't surjective. And so forth.

You can rearrange your argument to turn it into a diagonal argument. One can identify subsets of $S$ with their characteristic functions $S \to 2 = \{ 0,1 \}$. For any function $f : S \to 2^S$, the function $g(s) := 1 - f(s)(s)$ is not contained in the image. Proof: if $f(t)=g$, then $ f(t)(t) = g(t) = 1 - f(t)(t)$.

Note that any permutation $\pi$ of $S$ gives another element $g_\pi(s) := 1 - f(\pi(s))(s)$ which is also not in the image of $f$.

If you use the axiom of choice, then there is a bijection $2^S \to 3^S$. If you replace $2^S$ with $3^S$, then you can do the same thing you wanted to do with Cantor's argument showing the naturals are bigger than the reals, by making many choices of how to change the diagonal.