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}).$

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

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