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

88 Views Asked by At

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)

2

There are 2 best solutions below

0
On BEST ANSWER

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.

8
On

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.