cardinality of the set of $ \varphi: \mathbb N \to \mathbb N$ such that $\varphi$ is an increasing sequence

I know that the set of functions $ f:\mathbb N \to \mathbb N$ is uncountable, but what if we consider only $f$ such that $f$ is increasing? I want to know if this set is countable D: and also the case of bijective and increasing (clearly if the firstone holds then this too). I think that it could be possible that it's countable

Solution 1:

This is essentially reversing Brian M. Scott's initial argument...

Let $\mathbb{N}^{\mathbb{N}\uparrow}$ denote the family of strictly increasing functions $\mathbb{N} \to \mathbb{N}$. Given any function $f : \mathbb{N} \to \mathbb{N}$ define $\Phi ( f ) : \mathbb{N} \to \mathbb{N}$ by $$\Phi ( f ) ( n ) = \sum_{i=0}^n ( f(i) + 1 )$$ Then $\Phi ( f )$ is strictly increasing, and the mapping $f \mapsto \Phi ( f )$ is one-to-one.

Therefore, $| \mathbb{N}^\mathbb{N} | \leq | \mathbb{N}^{\mathbb{N}\uparrow} |$. A quick application of the Cantor–Bernstein–Schröder Theorem then yields $| \mathbb{N}^{\mathbb{N}\uparrow} | = | \mathbb{N}^\mathbb{N} | = 2^{\aleph_0}$.

Solution 2:

Let $e_1,e_2,e_3,\dots$ be any sequence of $0$'s and/or $1$'s. Let $a_1=1$ and $a_{i+1}=a_i+e_i+1$.

This shows that there are at least $c$ increasing sequences. So there are exactly $c$.

Solution 3:

It's uncountable. Suppose that $f_n$ is a sequence of strictly increasing sequences, let $g(0)=f_0(0)+1$; and $g(n+1)=\max\{g(n)+1, f_{n+1}(n+1)+1\}$. Clearly $g$ is not one of the $f_n$'s.

Solution 4:

Let $\mathscr{F}$ be the set of strictly increasing functions from $\Bbb N$ to $\Bbb N$: then $|\mathscr{F}|=2^\omega=|\wp(\Bbb N)|$, so $\mathscr{F}$ is certainly uncountable. One way to see this is to construct a bijection between $\mathscr{F}$ and ${}^{\Bbb N}\Bbb N$, the set of all functions from $\Bbb N$ to $\Bbb N$. This isn’t too hard.

Define a function $\mathscr{F}\to{}^{\Bbb N}\Bbb N:f\mapsto\hat f$ as follows: let $f\in\mathscr{F}$, and define $\hat f$ by setting $\hat f(0)=0$ and $\hat f(k)=f(k)-f(k-1)-1$ for $k>0$. It’s easy to check that this map is a bijection, so $|\mathscr{F}|=\left|{}^{\Bbb N}\Bbb N\right|$, which you probably already know is $2^\omega=|\wp(\Bbb N)|$.

Added: The inverse map is easy enough to write down as well: if $f\in{}^{\Bbb N}\Bbb N$, let

$$g:\Bbb N\to\Bbb N:n\mapsto n+\sum_{k\le n}f(k)\;.$$

then $$\hat g(n)=\left(n+\sum_{k\le n}f(k)\right)-\left((n-1)+\sum_{k\le n-1}f(k)\right)-1=f(n)\;,$$

i.e., $\hat g=f$.