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

share|improve this question
    
it's $2^{\aleph_0}$, by definition. –  Dustan Levenstein Jun 2 '12 at 8:19
1  
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
2  
@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
add comment

2 Answers 2

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

share|improve this answer
add comment

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

share|improve this answer
    
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
add comment

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.