4
$\begingroup$

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?

  • 3
    See [Cantor's theorem](http://en.wikipedia.org/wiki/Cantor's_theorem).2011-06-09

4 Answers 4

19

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
    That result is known as [Cantor's theorem](http://en.wikipedia.org/wiki/Cantor's_theorem).2011-06-09
  • 0
    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?2011-06-09
  • 4
    @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.2011-06-09
  • 3
    @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.)2011-06-09
6

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.

  • 0
    It isn't obvious to me that any non-empty subclass of a well-ordered proper class necessarily has a minimum. Certainly, a sub*set* would, but I'm a little fuzzy about classes...2011-06-09
  • 0
    @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$.2011-06-09
  • 1
    @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).2011-06-09
5

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.

  • 0
    Great notes, Pete!2011-06-09
4

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

  • 0
    How does one show that the set of continuous functions is greater than the reals between zero and one?2011-06-09
  • 0
    @vfiddlestix: I can't, so I will remove that statement2011-06-09
  • 5
    The set of continuous function from $\mathbb{R}$ to $\mathbb{R}$ has the same cardinality as $\mathbb{R}$.2011-06-09
  • 0
    Wikipedia gives five examples of [Sets with cardinality greater than the continuum](http://en.wikipedia.org/wiki/Cardinality_of_the_continuum#Sets_with_cardinality_greater_than_the_continuum) including the set of all Lebesgue measurable sets in $\mathbb{R}$.2011-06-09