The set of all strictly increasing sequences of natural numbers

Question

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?

Answer 1

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

Answer 2

Let $X$ be the set of strictly increasing sequences of natural numbers.

Define $F:X\to\mathcal P(\Bbb N)$ as $F(\{a_n\})=\{a_n:n\in\Bbb N\}$.

This function is clearly injective, and its image is precisely the set $Y=\{A\subset\Bbb N:A\text{ is infinite}\}$.

Since the complementary of $Y$ in $\mathcal P(\Bbb N)$ is the set of finite subsets of $\Bbb N$, which is countable, then $|X|=|\mathcal P(\Bbb N)|$.

Answer 3

Let $X$ be the set of strictly increasing sequences of natural numbers. Then there is an injective map from $X$ to $P(\mathbb{N})$ where $(a_{n})\to\{a_{n}\mid n\in\mathbb{N}\}$. Hence $$ |X|\leq|P(\mathbb{N})|\tag{0}\label{0} $$ There is also a surjective map from $X$ to $\mathbb{N}\times (\mathbb{N}\setminus 0)^{\mathbb{N}}$ where $a_{n}\to (a_{0}, \Delta a_n )$. Here $\Delta a_n=a_{n+1}-a_{n}$. Hence $$ |X|\geq|\mathbb{N}\times (\mathbb{N}\setminus 0)^{\mathbb{N}}|=|\mathbb{N}^{\mathbb{N}}|=|2^{\mathbb{N}}|=|P(\mathbb{N})|\tag{1}\label{1} $$ since $$ |2^{\mathbb{N}}| ≤ |\mathbb{N}^{\mathbb{N}}| ≤ |(2^\mathbb{N})^\mathbb{N}| = |2^{\mathbb{N}\times \mathbb{N}}| = |2^{\mathbb{N}}|. $$ By Cantor-Bernstein namely, $\eqref{0}$ and $\eqref{1}$, $$ |X|=|P(\mathbb{N})|. $$