Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 5 down vote accepted

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.

share|improve this answer
    
Perfect! Thank you =) So simple and easy to understand. –  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.

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.