17
$\begingroup$

Let $\mathrm{FinSet}$ be the category of finite sets.

A finite set structure is a faithful functor $F\colon C\to \mathrm{FinSet}$ such that, for any $n\geq 1$, there are only finitely many isomorphism classes of objects $F$ maps to $\{1, \dots, n\}$.

Question. Is there a natural finite set structure realizing the Ackermann function (or some other computable function growing faster than any primitive recursive function)?

$\endgroup$
15
  • 9
    $\begingroup$ @fosco : why is the convergence of the series relevant to the question ? $\endgroup$ May 10, 2021 at 14:37
  • 3
    $\begingroup$ @fosco, surely not; $f(n) \ge (n!)^2$ eventually. $\endgroup$
    – LSpice
    May 10, 2021 at 14:37
  • 7
    $\begingroup$ I'm not sure how to understand this question. For any function $f:\mathbb{N} \to \mathbb{N}$ I can chose a sequence of sets $P_n$ such that $\# P_n = f(n)$ and take $C$ to be a naively defined category with an object for each $i \in P_n$ mapping to a set with $n$ elements... so any functions can be obtained this way. $\endgroup$ May 10, 2021 at 14:42
  • 4
    $\begingroup$ Interesting question. Maybe some nested set-partition-like structures? A stupid answer would be to take a deterministic rewrite system that takes $A\left(n,m\right)$ steps to terminate (I think there should be one), and just say "the intermediate states of this rewrite system". $\endgroup$ May 10, 2021 at 15:47
  • 7
    $\begingroup$ The inverse Ackermann function appears in some algorithms, e.g. using a "soft heap" you can find the minimum spanning tree in time $O(m\alpha(m, n))$. A decade ago I probably knew why and whether something was being counted. $\endgroup$
    – Ville Salo
    May 10, 2021 at 17:55

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.