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?

$\endgroup$
1

5 Answers 5

19
$\begingroup$

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

$\endgroup$
4
  • 1
    $\begingroup$ That result is known as Cantor's theorem. $\endgroup$
    – lhf
    Jun 9, 2011 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$ Jun 9, 2011 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, 2011 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$ Jun 9, 2011 at 6:52
6
$\begingroup$

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.

$\endgroup$
3
  • $\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, 2011 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, 2011 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, 2011 at 19:12
5
$\begingroup$

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.

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

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

$\endgroup$
3
  • $\begingroup$ How does one show that the set of continuous functions is greater than the reals between zero and one? $\endgroup$ Jun 9, 2011 at 7:38
  • 6
    $\begingroup$ The set of continuous function from $\mathbb{R}$ to $\mathbb{R}$ has the same cardinality as $\mathbb{R}$. $\endgroup$
    – TonyK
    Jun 9, 2011 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, 2011 at 7:46
-1
$\begingroup$

The set of all functions is larger than continuum. This is because the set of all functions is a powerset of continuum.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .