Set of rapidly increasing functions is uncountable?

You could define recursively $f(n+1) = 2^{f(n)}+c$, where $c$ is any real greater than $0$, and since $\mathbb{R}^+$ is uncountable you are done.

Following this, I'm going to build a set of functions $F=\bigcup\limits_{i>0} \{f_i \}$:

  1. For every $i$: $f_i(0)=1$

  2. $f_i(n+1) = 2^{f_i(n)}+i$

First, notice how this set of functions satisfy your rapidly-increasing restriction; second, there is an $f_i$ for every $i\in\mathbb{R}^+$ so the cardinality of $F$ must be uncountable. For a concrete example: $f_1(0)=1$, and $f_1(1)=2^1+1=3$, $f(2)=2^3+1=9$ and so on.


A non-constructive proof via diagonalization would be as follows:

Assume $S$ is countable, and order $f, g \in S$ by $f \ll g \iff \forall x f(x)<g(x)$. Notice how under this definition it is not always true that $f \ll g$ or $f=g$ or $f\gg g$. So this is a partial ordering. Now pick a maximal chain $f_i$ and define $\hat f(1)=f_1(1)$ and $\hat f(i)=f_i(i) + \left[f_{i+1}(i)-f_{i}(i)\right]/2$.You can check that this $\hat f$ satisfies the rapidly-increasing restriction and it is different from every $f_i$ at $i$. A contradiction!


You can actually show that the set $S=\{f:\mathbb{N} \to \mathbb{N} : f(n+1) \geq 2^{f(n)}\}$ is uncountable. For each given $n$, let $A_n \subset S$ denote those functions such that $f(n+1) > 1 + 2^{2^{f(n)}}$. We have a surjection $g:S \to \mathcal{P}(\mathbb{N})$ by mapping $f \in S$ to $\{n \in \mathbb{N} : f \in A_n\}$.


I think a simpler proof is to notice that if we restrict the predicate to $f(n+1)=2^{f(n)}$, every function $f:\mathbb N\to blah$ is determined by its value $f(0)$. Setting $blah=\mathbb R$, $f(0)$ can then take $\mathbb R$-many values, so the set of all such functions is uncountable. Then the obvious injection from the previous set of functions to yours proves that the latter is uncountable.


Shiranai's answer is similar, except they fix the first (or $n$-many) values, so $f(n+1)$ is required to be greater than or equal to $2^{f(n)}$.