4
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ it's $2^{\aleph_0}$, by definition. $\endgroup$ Jun 2, 2012 at 8:19
  • 1
    $\begingroup$ 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}$. $\endgroup$ Jun 2, 2012 at 8:28
  • 2
    $\begingroup$ @Dunstan: Not by definition, since the OP is asking about $|[\omega]^\omega|$, not $|\wp(\omega)|$. $\endgroup$ Jun 2, 2012 at 8:31
  • $\begingroup$ How many subsequences does $a_n=1$ has? $\endgroup$
    – Asaf Karagila
    Jun 2, 2012 at 8:51
  • $\begingroup$ @BrianM.Scott point taken. $\endgroup$ Jun 2, 2012 at 19:44

2 Answers 2

4
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ Why is it that collection of finite subsets of N is countable? $\endgroup$
    – TempReg
    Jun 2, 2012 at 19:18
  • $\begingroup$ I have added the details. $\endgroup$ Jun 2, 2012 at 19:27

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.