Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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 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$.
