Prove that the set of rapidly increasing functions is uncountable using diagonalization

discrete mathematicselementary-set-theorysolution-verification

Problem

A function $f:\mathbb{N}\rightarrow\mathbb{N}$ is defined to be rapidly increasing if

$$f(n+1)\geq 2^{f(n)}$$

for all $n\in\mathbb{N}$. Let Rapid be the set of rapidly increasing functions.

Use a diagonalization argument to prove that Rapid is uncountable.

Can someone please verify the following solution attempt?

Solution

Assume, by contradiction, that Rapid is countable. Then, there is an enumeration $f_0,f_1,f_2,\cdots$ of the elements in Rapid.

Let $f_k$ denote the $k$-th function in the enumeration.

Define a new function $F$ as follows, for all $n \in \mathbb{N}$:

$$F(n) = 2^{\max(f_0(n), \cdots, f_n(n))}$$

  1. Claim 1: $F$ is not in the enumeration of the elements of Rapid.

    Proof. For each $n \in \mathbb{N}$, $F(n) \neq f_n(n)$. Therefore, $F$ differs from each $f_0,f_1,f_2,\cdots$ in the enumeration.

  2. Claim 2: $F$ is in Rapid. That is:

    $$F(n+1) \geq 2^{F(n)}$$

    $$2^{\max(f_0(n+1), f_1(n+1), \cdots, f_{n+1}(n+1))} \geq 2^{2^{\max(f_0(n), f_1(n), …, f_n(n))}}$$

    Proof. For the Claim 2 to be true, it's sufficient that:

    $$\max(f_0(n+1), f_1(n+1), \cdots, f_{n+1}(n+1)) \geq 2^{max(f_0(n), f_1(n), \cdots, f_n(n))}\text{ (*)}$$

    Let $f_i(n+1)$ be the value of left-hand side $\max$ expression of (*), and $f_j(n)$ be the value of the right-hand side $\max$ expression of (*), where $0 \leq i \leq n + 1$ and $0 \leq j \leq n$. That is:

    $$f_i(n+1) = \max(f_0(n+1), f_1(n+1), \cdots, f_{n+1}(n+1))$$

    $$f_j(n) = \max(f_0(n), f_1(n), \cdots, f_n(n))$$

    If $f_i = f_j$, then (*) follows directly, by definition, from the fact that $f_i$ is in Rapid: $f_i(n+1) \geq 2^{f_i(n)}$. Therefore, in this case, the Claim 2 is true.

    Now, assume that $f_i \neq f_j$.

    Assume, by contradiction, that (*) is false, that is, $f_i(n+1) < 2^{f_j(n)}$.

    Since $f_j$ is in Rapid, we have, by definition: $f_j(n+1) \geq 2^{f_j(n)}$.

    But $f_i(n+1) < 2^{f_j(n)}$ and $f_j(n+1) \geq 2^{f_j(n)}$ imply that:

    $$f_i(n+1) < 2^{f_j(n)} \leq f_j(n+1)$$

    $$f_i(n+1) < f_j(n+1),$$

    which contradicts the assumption that $f_i(n+1) = \max(f_0(n+1), f_1(n+1), \cdots, f_{n+1}(n+1))$.

    Therefore, it can't be the case that $f_i(n+1) < 2^{f_j(n)}$ with $i \neq j$. So, $f_i(n+1) \geq 2^{f_j(n)}$, which means that (*) is true, and therefore $F$ is in Rapid.

From Claim 1 and Claim 2, we defined a function $F$ that is not in the enumeration of all rapidly increasing functions, but which is in Rapid. This contradicts the assumption that we have an enumeration of all rapidly increasing functions. So, such an enumeration cannot exist. Therefore, Rapid is uncountable.

Best Answer

Correct. Your proof of $(*)$ in Claim 2 can be streamlined: Let $j_n\le n$ such that $f_{j_n}(n)=\max_{j\le n}f_j(n).$ Then $$2^{\max_{j\le n}f_j(n)}=2^{f_{j_n}(n)}\le $$ $$\le f_{j_n}(n+1)\le$$ $$\le \max_{j\le n+1}f_j(n+1).$$

Related Question