The diagonal argument establishes that the continuum is greater than countable infinity. What is an example of the next infinity (or any greater infinity) and how can it be shown that there is no 1:1 correspondence with the continuum?


The same type of diagonalization argument which is used to show $|\mathbb{R}| > |\mathbb{Z}|$ can be used to show that for any set $X$ the power set of $X$ has strictly greater cardinality than $X$. Thus, if you want a set of cardinality greater than $\mathbb{R}$ try $\mathcal{P}(\mathbb{R}).$

  • 1
    $\begingroup$ That result is known as Cantor's theorem. $\endgroup$ – lhf Jun 9 '11 at 3:58
  • $\begingroup$ Unfortunately this isn't an example (referencing "the power set" doesn't provide an example.) The construction of the diagonal argument used a countable set so wouldn't something significant have to change to apply it to the continuum? $\endgroup$ – vfiddlestix Jun 9 '11 at 4:08
  • 4
    $\begingroup$ @vfiddlestix: Diagonal arguments can be made with larger cardinalities, and essentially this is Cantor's theorem to which lhf linked. Also, how this is not an example? You have asked for a set whose cardinality is larger than the continuum, and you were given one. $\endgroup$ – Asaf Karagila Jun 9 '11 at 5:49
  • 3
    $\begingroup$ @vfiddlestix: I don't understand your comment. The power set of $\mathbb{R}$ is an example of a set with cardinality greater than the continuum. (It's the same example I gave in my answer and probably the most natural example.) $\endgroup$ – Pete L. Clark Jun 9 '11 at 6:52

Since you are not satisfied with the power set being the most natural example, here is one slightly less natural - but still very common (especially in the absence of choice):

Consider all the ordinal numbers that there is an injective function from them into $\mathbb R$, i.e. $A = \{\alpha\mid\alpha\text{ is an ordinal, and }\exists f\colon\alpha\xrightarrow{1-1}\mathbb R\}$.

We claim that $A$ cannot be bijected with $\mathbb R$.

First, a set of ordinals which is downwards-closed (i.e. if $\alpha\in A$ and $\beta<\alpha$, then $\beta\in A$) is an ordinal. There is a simple proof for this fact, simply because a set $x$ is an ordinal if and only if it is transitive and well-ordered by $\in$.

From this we have that $A$ is an ordinal, because if $\alpha\in A$ and $\beta<\alpha$ then the same injective function from $\alpha$ is still injective from $\beta$ when restricted to $\beta$ (recall that $\beta<\alpha$ if and only if $\beta\in\alpha$ if and only if $\beta\subsetneq\alpha$).

Suppose there was a function from $A$ into the reals which is injective, since $A$ is an ordinal we would have $A\in A$, in contradiction to the fact that an ordinal cannot be a member of itself (regardless to whether or not the axiom of foundation holds in the universe).

Alternatively, one could define $A$ as the least ordinal which cannot be injected into $\mathbb R$. This ordinal exists, since $\mathbb R$ is a set, and the ordinals form a proper class; and it would have the exact same properties.

This construction is called Hartogs number.

  • $\begingroup$ It isn't obvious to me that any non-empty subclass of a well-ordered proper class necessarily has a minimum. Certainly, a subset would, but I'm a little fuzzy about classes... $\endgroup$ – Zhen Lin Jun 9 '11 at 9:14
  • $\begingroup$ @Zhen: Since this is really about ordinals, let $M$ be a nonempty class of ordinals, denote $M_\alpha = M\cap\alpha$. Then For some $\alpha$ we have $M_\alpha$ is non-empty, and a set. Take $\beta$ the least ordinal in $M_\alpha$, suppose some $\gamma\in M$ is such that $\beta>\gamma$, then $\gamma\in\beta\in\alpha$ then $\gamma$ is the least ordinal of $M_\alpha$ for every nonempty $M_\alpha$. $\endgroup$ – Asaf Karagila Jun 9 '11 at 9:26
  • 1
    $\begingroup$ @Zhen: Actually a lot more is true, if $(M,R)$ is a partially ordered class, such that for all $x\in M$ the class $\{y\mid yRx\}$ is a set, and $R$ is well-founded (i.e. no infinitely decreasing chains) then every nonempty class has an $R$-minimal element. (Note: since partial orders are usually defined as irreflexive and transitive, it means that if $a\notin M$ then it is automatically $R$-minimal). $\endgroup$ – Asaf Karagila Jun 9 '11 at 19:12

Very similar questions have been asked here before, but I am finding it easier to simply answer again than search for the closest precedent.

An example of a set of cardinality greater than the continuum is given in $\S 2.2$ of these notes. In $\S 2.4$ it is shown that there is more than a set's worth of cardinalities of uncountable sets.

  • $\begingroup$ Great notes, Pete! $\endgroup$ – wckronholm Jun 9 '11 at 1:41

If you don't like the power set, another example is the set of functions $f:\mathbb{R} \rightarrow \mathbb{R}$.

  • $\begingroup$ How does one show that the set of continuous functions is greater than the reals between zero and one? $\endgroup$ – vfiddlestix Jun 9 '11 at 7:38
  • $\begingroup$ @vfiddlestix: I can't, so I will remove that statement $\endgroup$ – Henry Jun 9 '11 at 7:43
  • 5
    $\begingroup$ The set of continuous function from $\mathbb{R}$ to $\mathbb{R}$ has the same cardinality as $\mathbb{R}$. $\endgroup$ – TonyK Jun 9 '11 at 7:44
  • $\begingroup$ Wikipedia gives five examples of Sets with cardinality greater than the continuum including the set of all Lebesgue measurable sets in $\mathbb{R}$. $\endgroup$ – Henry Jun 9 '11 at 7:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.