The set of all strictly increasing sequences ($a_n$) of natural numbers has cardinality $\mathbb{N}$, $\mathcal{P}(\mathbb{N})$ or $\mathcal{P}( \mathcal{P}(\mathbb{N}))$?
I answered $\mathcal{P}(\mathcal{P}(\mathbb{N}))$ because as the set can be described by $X=\{\{\ldots, a_n, \ldots \},\{\ldots,b_n,\ldots\}, \ldots\}$ as it is not known if there are any limited sequences (so, assuming all have infinite elements), the cardinality of $X$ could not be the first option $\mathbb{N}$ because considering any function $\phi : \mathbb{N} \rightarrow X$ there would always be elements not listed from $X$. So I thought it would possible to say that $|X|\ge | \mathcal{P}(\mathbb{N})|$ and thinking that trying to build any bijection $\varphi: \mathcal{P}(\mathbb{N}) \rightarrow X$ would also not be possible as there would be elements from $X$ not listed too. So than I got $|X| = |\mathcal{P}( \mathcal{P}(\mathbb{N}))|$, but I would like to know if I answered correct and, if not, why?
Best Answer
Each strictly increasing sequence of natural numbers corresponds to a particular infinite subset of $\mathbb N$. So there can't be more such sequences than there are subsets.
On the other hand, for every (finite or infinite) subset there is an infinite subset (which again corresponds to a strictly increasing sequence) -- for example, just multiply every number in the original subset by $2$ and then add in all of the odd numbers. So there can't be more subsets than there are sequences.
By Cantor-Bernstein, then, the set of strictly increasing sequences has the same cardinality as $\mathcal P(\mathbb N)$.