8
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ How many choices are there for $f(m)$ where $m \in \{0,1\}$, whichever is the least element of $\Bbb{N}$? $\endgroup$ – Eric Towers Oct 19 '19 at 17:22
11
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Or require $c=1$, but exploit the fact $f(1)$ can take uncountably many values. $\endgroup$ – J.G. Oct 19 '19 at 17:23
  • $\begingroup$ @Shiranai How you will define $f(1)$ ? $\endgroup$ – Manoj Kumar Oct 19 '19 at 17:26
  • $\begingroup$ @Manoj it can be any positive number $\endgroup$ – Shiranai Oct 19 '19 at 17:32
  • $\begingroup$ @Shiranai I'm sorry, but I did not get your logic, can you elaborate little with more. $\endgroup$ – Manoj Kumar Oct 19 '19 at 17:35
  • $\begingroup$ Sure, I just expanded on my answer, check it out @Manoj $\endgroup$ – Shiranai Oct 19 '19 at 18:02
5
$\begingroup$

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\}$.

$\endgroup$
  • $\begingroup$ Why you are taking $f(n+1)>1+2^{2^{f(n)}}$ ? $\endgroup$ – Manoj Kumar Oct 19 '19 at 17:38
  • 3
    $\begingroup$ You can simplify this construction to simply $f\in A_n\iff f(n+1)>2^{f(n)}$. At each $n$, $f(n+1)$ can be freely chosen among all values that are at least $2^{f(n)}$, so the set of all such functions is isomorphic to ${\Bbb N}^{\Bbb N}$. $\endgroup$ – Mario Carneiro Oct 20 '19 at 2:47
5
$\begingroup$

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)}$.

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @ManojKumar by recursive construction of $f$ we have $f(n+1)=\max\{f_{n+1}(n+1)+1,2^{f(n)}\}\ge 2^{f(n)}$. That is, once $f(n)$ is defined, then you define $f(n+1)$ to be the bigger of the two numbers $f_{n+1}(n+1)+1$ and $2^{f(n)}$, so in particular $f(n+1)\ge 2^{f(n)}$. $\endgroup$ – Mirko Oct 20 '19 at 4:59
  • 1
    $\begingroup$ Ah! Great that's what I want. $\endgroup$ – Manoj Kumar Oct 20 '19 at 5:03
  • $\begingroup$ I could have accepted this as answer to my question, but I already accepted other one. $\endgroup$ – Manoj Kumar Oct 20 '19 at 5:32
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.