# Is every sequence bounded by a sequence which can be represented in closed form?

Let $$X$$ be the set of $$\mathbb{R}$$-valued sequences, i.e. $$X := \mathbb{R}^{\mathbb{N}}=\{f: \mathbb{N} \to \mathbb{R}\}$$, and let $$S$$ the set of sequences which can be expressed in closed form, i.e.: $$S:= \{f \in \mathbb{R}^\mathbb{N} \space | \space f \text{ is in closed form}\} \subseteq X$$ Now since "closed form" is not well-defined: I basically mean the usual stuff. That is: $$f$$ is in closed form if there is a mathematical expression that can be evaluated in a finite number of operations. The allowed symbols in the expression are: constants, variables and applications of $$!$$ (factorial), $$\exp, \ln$$, the trigonometric and hyperbolic functions with their inverses, $$\lfloor \cdot \rfloor, \lceil \cdot \rceil, [\cdot]$$.

For example, $$(a_k)_{k\in\mathbb{N}}\in S$$ if $$\displaystyle a_k = e^{(k!)^2\cdot \sin\left(\binom{2k}{k}\right)}$$.

Now we have $$S \subset X$$, i.e. there are sequences which cannot be represented in closed form.

However, does at least the following statement hold? $$\forall f \in X: \exists g \in S: f \leq g$$ (i.e. every sequence is bounded by a sequence which can be expressed in closed form)

• How about $a_1=3$, $a_{n+1}=a_n!$ ? – Mindlack Jan 9 '19 at 18:29
• Since you admit [arbitrary real] constants in the expressions deemed "closed-form", and there are continuum-many reals, there are at least so many sequences in $S$ (not that this makes difficulty in providing an answer). – John Bentin Jan 9 '19 at 18:54
• @JohnBentin oh...you are absolutely right. I'll correct that. – Jakob B. Jan 9 '19 at 19:16

I think your definition of closed form is equivalent to the primitive recursive functions. The Ackermann function eventually overtakes every primitive recursive function, so the answer is that no function in $$S$$ dominates it.

In particular, probably the fastest growing type of function in your library is $$n^{n^{n^n}}$$ for some finite height of the tower. Ackermann uses $$2$$'s instead of $$n$$'s, but makes the height increase without bound, so eventually it will be taller than whatever tower you pick.

I think not. Since $$S$$ is countable, enumerate it as $$\{s(n)\}$$. Now create a sequence $$t$$ such that

$$t(n)_n = 1 + \max\{ s(n)_k \ | \ k \le n \} .$$.

This construction should work even if you allow constructions like repeated factorials $$!^{n}$$ as in @Mindlack 's comment.

• @SmileyCraft Any number that's not the $k$th term in $s(n)$. – Ethan Bolker Jan 9 '19 at 18:39
• You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)? – Daniel Schepler Jan 9 '19 at 18:39
• I think it is useful to give $t$ explicitly, for example by $t(n)_k:=\max\{s(n)_l:1\leq l\leq k\}+1$. – SmileyCraft Jan 9 '19 at 18:40
• @SmileyCraft Thanks. Used your suggestion. – Ethan Bolker Jan 9 '19 at 18:44
• Interestingly this also proves that you can not define a bijection from $\mathbb{N}$ to $S$. – SmileyCraft Jan 9 '19 at 18:47