How many sequences of positive integers contain the positive integers? If $$\Bbb{Z}^{+} = \{1, 2, 3,\ldots\}$$
Then there are a lot of sequences that contain $\Bbb{Z}^{+}$
$$\Bbb{Z}^{+} \subseteq \{i\}_{i=1}^\infty = \Bbb{Z}^{+}$$
$$\Bbb{Z}^{+} \subseteq \{ \left(\begin{array}{cc} 7 & i\textrm{ is odd}\\ i/2 & i\textrm{ is even} \end{array}\right) \}_{i=1}^\infty = \{7,1,7,2,7,3,7,\ldots\}$$
And many (more?) that clearly do not contain $\Bbb{Z}^{+}$.
My question is stated in the title.
I thought of this question while reading and thinking about fractal sequences. How many of those are there? That is clearly another question.
 A: There's at least one such sequence for each subset $A\subseteq \mathbb N$, namely
$$ f(n) = \begin{cases} n/2 & \text{if $n$ is even} \\
5 & \text{if $n$ is odd and }\frac{n-1}2\in A \\
7 & \text{otherwise} \end{cases} $$
On the other hand, each function $f:\mathbb N\to\mathbb N$ (surjective or not) can be encoded as a subset of $\mathbb N$, for example
$$ \{ 2^a3^b \mid f(a)=b \} $$
So, by the Cantor-Schröder-Bernstein theorem, the number of surjective functions $\mathbb N\to\mathbb N$ is the same as the number of all functions $\mathbb N\to\mathbb N$, and the same as the number of subsets of $\mathbb N$, namely $2^{\aleph_0}$.
A: Well if you mean sequences in $\mathbb{Z}^+$ then the answer is pretty straightforward: as many as the real numbers.
This is easy to see: take any real number in its decimal representation and intertwine $\mathbb{Z}^+$ saying that if $a= a_1 \dots a_k \dots$ then
$x_{2n} = a_{n}$ and $x_{2n+1}=n$ is a sequence that contains $\mathbb{Z}^+$. This is injective so it's enough to say that what you're asking is $\geq |\mathbb{R}|$
