3
$\begingroup$

I am self studying point set topology with MAT327 from Toronto University. In the topic of countability (chapter 4), I am asked to: "given a fixed set of functions $f_n:\mathbb{N}\rightarrow\mathbb{N}$, $n\in\mathbb{N}$ construct a function $g: \mathbb{N}\rightarrow\mathbb{N}$ that grows faster than all $f_n$"

this is: $\lim_{k\rightarrow\infty}\frac{g(k)}{f_n(k)}= \infty$

In the course is assumed that $0\not\in\mathbb{N}$. If the set of functions $f_n$ were finite $g(k)=\Pi_nf(k)^{f(k)}$ would be a solution, but I am not sure I can use this trick for an infinite set of functions.

How can I construct a function than grows faster than a given (infinite) set of functions?

$\endgroup$
2
  • 1
    $\begingroup$ What definition of "growth" do you use? As in big-O? Also your $g$ is not necessarily growing strictly faster than all $f_n$ in finite case, e.g. if all $f_n$ are constant, then so is your $g$. $\endgroup$
    – freakish
    Jul 5 at 12:32
  • $\begingroup$ @freakish Edited the question to define growth. Thanks for noticing the caveat for constant f_n. I take your comment as a solution. Thx $\endgroup$ Jul 5 at 12:41

1 Answer 1

8
$\begingroup$

Your $g(k)=\prod_{n} f_n(k)^{f_n(k)}$ does not necessarily work even in finite case. For example when all $f_n$ are constant then so is $g$.

What works for both finite and infinite case is

$$g(k)=k\cdot\max_{j\leq k}\{f_j(k)\}$$

Indeed, for any fixed $n$ we have

$$\lim_{k\to\infty}\frac{g(k)}{f_n(k)}=\lim_{k\to\infty}\frac{k\cdot\max_{j\leq k}\{f_j(k)\}}{f_n(k)}$$

Now given $k\geq n$ we have $$\frac{k\cdot\max_{j\leq k}\{f_j(k)\}}{f_n(k)}\geq\frac{k\cdot f_n(k)}{f_n(k)}=k\to\infty$$

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