2
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ How about $a_1=3$, $a_{n+1}=a_n!$ ? $\endgroup$ – Mindlack Jan 9 '19 at 18:29
  • 1
    $\begingroup$ 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). $\endgroup$ – John Bentin Jan 9 '19 at 18:54
  • $\begingroup$ @JohnBentin oh...you are absolutely right. I'll correct that. $\endgroup$ – Jakob B. Jan 9 '19 at 19:16
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @SmileyCraft Any number that's not the $k$th term in $s(n)$. $\endgroup$ – Ethan Bolker Jan 9 '19 at 18:39
  • $\begingroup$ You mean $t_n > s(n)_n$, not just unequal (and there's diagonalization in there too)? $\endgroup$ – Daniel Schepler Jan 9 '19 at 18:39
  • $\begingroup$ 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$. $\endgroup$ – SmileyCraft Jan 9 '19 at 18:40
  • $\begingroup$ @SmileyCraft Thanks. Used your suggestion. $\endgroup$ – Ethan Bolker Jan 9 '19 at 18:44
  • $\begingroup$ Interestingly this also proves that you can not define a bijection from $\mathbb{N}$ to $S$. $\endgroup$ – SmileyCraft Jan 9 '19 at 18:47

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.