Is the set of all step functions countable or uncountable I've got $f:\mathbb{N}\to \mathbb{N}$ a step function if $f (1)= 1$ and for every $n\geq 2$ we have either
$f(n)=f(n−1)$ or $f(n)=f(n−1)+1.$
I need to show the set of all step functions is countable or
uncountable?
I know that if its countable i need to form a surjection between the set and the set of natural numbers but dont quite know how to show this.
For a given function $f$ define $ e_n \in \{0,1\}$ by $f(n)=f(n-1)+e_n$. So a given function is characterised by the vector $(e_1,e_2,\cdots)$. Which looks pretty uncountable ($2^{ \aleph_0}$).
Indeed a standard diagonal arguement will show it is uncountable.
One thing to note is that showing asset is countable means there exists an injective function into $\mathbb{N}$, not a surjective function. To show that a set is uncountable, you must show that there cannot exist an injective function