Uncountability of increasing functions on N

Question

I believe I have made a reasonable attempt to answer the following question. I would like a confirmation of my proof to be correct, or help as to why it is incorrect.

Question: Let $f : \mathbb{N} \to \mathbb{N}$ be increasing if $f(n+1) \ge f(n)$ for all $n$. Is the set $A$ of functions $f$ countable or uncountable?

For each $f$ in $A$, there is a function $g: \mathbb{N}\cup \{0\} \to \mathbb{N} \cup\{0\}$ defined by $g(0)=f(1)$ and $g(n)=f(n+1)-f(n)$ for $n>0$. Conversely, for each $g: \mathbb{N}\cup \{0\} \to \mathbb{N}\cup\{0\}$ with $g(0)>0$, there is an increasing function $f$ defined recursively by $f(1)=g(0)$ and $f(n+1)=f(n)+g(n)$ for $n>0$. Consequently, there is a bijection between $A$ and the set $B$, of $g: \mathbb{N}\cup\{0\} \to \mathbb{N}\cup\{0\}$, $g(0)>0$. If $B$ is uncountable, then $A$ must be uncountable.

The set $C$ of $h: \mathbb{N}\cup\{0\} \to \{0,1,2,3,4,5,6,7,8,9\}$ with $h(0)=1 $is a subset of $B$. For each real $x \in [1,2)$, there is a unique decimal expansion with 1 before the decimal point, ending NOT in trailing 9's. By defining for $n>0$, $h(n)=$ (n'th digit of x after decimal point), we have an injection from $[1,2)$ to the set $C$ (different $x$ => different decimal expansions => x maps to different h). Since the set of reals on $[1,2]$ is uncountable, the set C is uncountable, => the set B is uncountable, => the set A is uncountable.

Answer 1

This proof works but seems needlessly verbose. It is easier to prove that strictly increasing functions form an uncountable set (which implies that the monotone increasing are uncountable as well). This is because there is an obvious 1-1 correspondence between strictly increasing functions and infinite subsets of N (each such function is uniquely determined by its range). It is a standard result that there are uncountably many subsets of N, of which only countably many are finite. Hence, there are uncountably many infinite subsets.

Answer 2

It is rather easy to apply the diagonalization argument directly. Let $\langle f_n\rangle$ be a sequence of increasing functions from the naturals to itself. Define a function $f$ recursively by $f(1)=1$ and $$f(n+1)=f(n)+f_n(n+1)-f_n(n)+1.$$ The resulting function $f$ is clearly different from every function in the sequence $\langle f_n\rangle$.

Answer 3

Your proof looks OK to me. It's a little longer than needed though.

Right after you define your set $A$, what if we just restrict ourselves to a subset of $A$ given by the subset of monotone functions $t: \mathbb{N} \to \mathbb{N}$ such that $t(n+1)-t(n) \in \{0,1\}$ and $t(0)=k$.

Then in your spirit, we can identify each $t$ with the infinite binary sequence of its step-wise differences. Moreover, clearly for any infinite binary sequence we can construct the unique $t$ that gets related to it. Then by Cantor's diagonalization argument we know $\{0,1\}^\mathbb{N}$ is uncountable and we're done.

Answer 4

Another way to show that $A$ is uncountable : Show that if $B=\{f_n: n\in N\}\subset A$ then $B\ne A$ as follows:

Let $g(n)=\max \{1+f_j(n): j\leq n\}.$

We have $g(n)> f_n(n)$ for every $n. $ So $g\ne f_n$ for every $n.$ So $g \not \in B.$

For each $ n $ we have $g(n)=1+f_{j_n}(n)$ for some $j_n\leq n . $ So $g(n+1)=\max \{1+f_j(n+1):j\leq n+1\}\geq 1+f_{j_n}(n+1)\geq 1+f_{j_n}(n)=g(n). $ So $ g\in A. $