Cardinality of set containing all infinite subsets of $\mathbb{Q}$

Question

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 =)

Answer 1

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.

Answer 2

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.

Answer 3

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