I need to find the cardinality of the set $S$ of all infinite subsets of $\mathbb{Q}$.

It's easy to prove $\operatorname{card} S=\mathfrak c$ if you first prove that the cardinality of the set of all finite subsets of $\mathbb{Q}$ is $\aleph_0$.

But is there some other proof for the statement without using the second one (about finite subsets)? Probably there is =)


To each real number $r$, you can associate the set $\{q\in\mathbb Q:q<r\}$. Distinct real numbers produce in this way distinct infinite sets of rational numbers. So there are at least $\mathfrak c$ infinite sets of rational numbers. Since you seem to already know tha there are at most $\mathfrak c$ such sets, the Schröder-Bernstein Theorem finishes the proof.

  • $\begingroup$ Perfect! Thank you =) So simple and easy to understand. $\endgroup$ – Meow Jun 18 '13 at 20:27

Actually the standard proof is easier in this case: Let $A$ be the set of all infinite subsets of $\mathbb N$.

For each $B \in A$ we define $x_i=1$ if $i \in B$ and $x_i=0$ if $i \notin B$. Define

$$f(B)=0.x_1x_2...x_n..._{(2)} \,,$$ meaning the representation in binary.

Then $f$ is a bijection between $A$ and $(0,1]$. Note that this time you don't run anymore into the issue with some numbers having two expansions.


Fix a bijection $f: \Bbb N \to \Bbb Q$. For convenience assume $\Bbb N = \Bbb Z_{>0}$.

It is clear that there is a bijective correspondence between infinite subsets $A \subseteq \Bbb Q$ and strictly increasing functions $g: \Bbb N \to \Bbb N$, by:

\begin{align} A\subseteq \Bbb Q \quad&\longrightarrow\quad g(n) = \text{$n$th smallest $m$ such that $f(m) \in A$}\\ \{f(g(n)):n \in \Bbb N\} \quad&\longleftarrow\quad g:\Bbb N \to \Bbb N \end{align}

An increasing function $g: \Bbb N \to \Bbb N$ is equivalently described by a mapping $h: \Bbb N \to \Bbb N$, as follows:

\begin{align} g: \Bbb N \to \Bbb N \quad&\longrightarrow\quad h(1)=g(1),h(n) = g(n)-g(n-1)\\ g(n) = \sum_{k\le n} h(k) \quad&\longleftarrow\quad h:\Bbb N \to \Bbb N \end{align}

Of these last functions there are $\aleph_0^{\aleph_0} = 2^{\aleph_0} = \mathfrak c$.


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.