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)?

Improve this question
$\endgroup$
15
  • 9
    $\begingroup$ @fosco : why is the convergence of the series relevant to the question ? $\endgroup$
    – Simon Henry
    Commented May 10, 2021 at 14:37
  • 3
    $\begingroup$ @fosco, surely not; $f(n) \ge (n!)^2$ eventually. $\endgroup$
    – LSpice
    Commented 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$
    – Simon Henry
    Commented 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$
    – darij grinberg
    Commented 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
    Commented May 10, 2021 at 17:55

0

Reset to default

Browse other questions tagged or ask your own question.