Let $$ S=\{f \colon \mathbb{N} \mapsto \mathbb{R} \mid f(n+1) \ge 2^{f(n)} \}.$$ How to prove $S$ is uncountable ?
I tried proving by contradiction, but not able to construct a new function different from the countable collection.
Any help would be appreciated.
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 \}$:
For every $i$: $f_i(0)=1$
$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)}$.
Yes, you could come up with a proof by contradiction. It also works if you replace $\Bbb R$ with $\Bbb N$ in the definition of $S$. (The version with $\Bbb R$ is too easy as $f(0)$ can take continuum many values, as in the answers by palmpo and by Shiranai. The answer by MathematicsStudent1122 already shows that we can replace $\Bbb R$ with $\Bbb N$, but I will use a proof by contradiction and diagonalization.)
Let $S=\{f \colon \mathbb{N} \mapsto \mathbb{N} \mid f(n+1) \ge 2^{f(n)} \}$ where $\Bbb N$ is the set $\{0,1,2,...\}$ of all non-negative integers. Suppose $S$ were countable, say $S=\{f_n : n\in\Bbb N\}$. Define a new function $f$ by $f(0)=f_0(0)+1$ and, recursively, $f(n+1)=\max\{f_{n+1}(n+1)+1,2^{f(n)}\}$. Then $f(n+1)\ge 2^{f(n)}$, hence $f\in S$, but on the other hand for every $n$ we have $f(n)\ge f_n(n)+1>f_n(n)$, hence $f\notin S$. This contradiction shows that $S$ is uncountable.
The powerset of any set has greater cardinality than the original set.
Every nontrivial sunset of $\mathbb{N}$ can be mapped to by some function from $\mathbb{N}$ to $\mathbb{R}$.
So now you just need to show each nontrivial subset of $\mathbb{N}$ can correspond with a particular rapidly growing function.
Start with one rapidly growing function F. For each subset of $\mathbb{N}$ with n elements and largest element m, construct a degree m polynomial with n terms with exponents corresponding to the members of $\mathbb{N}$. Multiply this polynomial by F and you have a new rapidly growing function.
