# How “many” sub-sequences in a given sequence (cardinality of the set of countably infinite subsets of a countably infinite set)

I don't know how "many" (cardinality) sub-sequences are there in a sequence.

Or equivalently,

What is the cardinality of the set of countably infinite subsets of a countably infinite set?

I guess it should not be $\aleph_0$, maybe $2^{\aleph_0}$ ($\aleph_0$ is the cardinality of natural numbers).

Thank you.

-
it's $2^{\aleph_0}$, by definition. –  Dustan Levenstein Jun 2 '12 at 8:19
Use the fact that if $A$ is infinite and $B$ countable, the cardinality of $A\cup B$ is the same as the cardinality of $A$. You will indeed find $2^{\aleph_0}$. –  Davide Giraudo Jun 2 '12 at 8:28
@Dunstan: Not by definition, since the OP is asking about $|[\omega]^\omega|$, not $|\wp(\omega)|$. –  Brian M. Scott Jun 2 '12 at 8:31
How many subsequences does $a_n=1$ has? –  Asaf Karagila Jun 2 '12 at 8:51
@BrianM.Scott point taken. –  Dustan Levenstein Jun 2 '12 at 19:44

It is indeed $2^{\aleph_0}$. $\Bbb N$ has $2^{\aleph_0}$ subsets altogether, so certainly it has no more than $2^{\aleph_0}$ infinite subsets. On the other hand, there is an injection $\varphi$ from $\wp(\Bbb N)$ into the set of infinite subsets of $\Bbb N$.

Let $O=\{2n+1:n\in\Bbb N\}$, the set of odd positive integers. Then for each set $S\subseteq\Bbb N$ let $$\varphi(S)=O\cup\{2n:n\in S\}\;.$$

Since $\varphi(S)\supseteq O$ for every $S\subseteq\Bbb N$, every $\varphi(S)$ is infinite. On the other hand, it’s clear that $\varphi$ is injective (one-to-one), since whenever $S_0,S_1\subseteq\Bbb N$ with $S_0\ne S_1$, $\varphi(S_0)\setminus O\ne\varphi(S_1)\setminus O$, and therefore $\varphi(S_0)\ne\varphi(S_1)$.

Intuitively, $\varphi(S)\setminus O$ looks just like $S$, except that it’s been blown up by a factor of $2$: it’s simply the double of $S$. Thus $S$ is completely recoverable from the even numbers in $\varphi(S)$: just divide each of them by $2$. This ensures that $\varphi$ is an injection. Throwing in $O$ just ensures that $\varphi(S)$ is always infinite.

Thus, if $\mathscr{A}$ is the set of infinite subsets of $\Bbb N$, $\varphi$ is an injection of $\wp(\Bbb N)$ into $\mathscr{A}$, while the identity map is an injection of $\mathscr{A}$ into $\wp(\Bbb N)$, and it follows from the Cantor-Schröder-Bernstein theorem that $|\mathscr{A}|=|\wp(\Bbb N)|=2^{\aleph_0}$.

-

We use the following result:

Let $A$ an infinite set and $B$ a countable set. Then $|A\cup B|=|A|$.

When $A$ is countable, $A=\{a_n,n\in \mathbb N\}$, we can use the bijection $\varphi\colon A\to A\cup B$ given $\varphi(a_{2n})=a_n$ and $\varphi(a_{2n+1})=b_n$.

We can assume that $A$ and $B$ are disjoint. If $A$ is not countable, let $D\subset A$ infinite countable contained in $A$, $D=\{d_n,n\in\mathbb N\}$. We define $\varphi\colon A\to A\cup B$ by $\varphi(x)=x$ if $x\in A\setminus D$, $\varphi(d_{2n})=d_n$ and $\varphi(d_{2n+1})=b_n$, which is a bijection.

Now we apply the result with $A$ the collection of infinite subsets of $\Bbb N$ and $B$ the collection of finite subsets of $\Bbb N$, which is countable.

Indeed, denote by $S_n$ the collection of the subsets of $\Bbb N$ with $n$ elements. You can find an injection of $S_n$ into $\Bbb N^n$, which has the same cardinality as $\Bbb N$.

-
Why is it that collection of finite subsets of N is countable? –  TempReg Jun 2 '12 at 19:18
I have added the details. –  Davide Giraudo Jun 2 '12 at 19:27