Let

 F(n) = the number of isomorphism classes of objects X of a finite–set structure F : C → FinSet with |F(X)| = n.

The question is whether we can get F(n) to be the (diagonal) Ackermann function
A(n,n), or at least some total computable function that grows faster than every primitive–recursive function.

1. A cheap way: “Yes”

For every total computable function g : ℕ→ℕ there is an entirely straightforward finite-set structure whose counting function is g. Fix such a g. Define Cg as follows.

• Objects: pairs (X,i) where X is a finite set and i∈{1,…,g(|X|)}.
• A morphism (X,i)→(Y,j) is a bijection f:X→Y with i=j (so the extra label is preserved).
• Fg(X,i)=X and Fg(f)=f.

Fg is faithful, and for each n there are exactly g(n) isomorphism classes with underlying set {1,…,n}. Taking g(n)=A(n,n) gives the Ackermann numbers. Nothing deep is happening here – we have merely “painted” each set of size n with g(n) different colours.

This shows that, in the absence of further requirements on C, Ackermann-sized growth (indeed any computable growth) is attainable.

2. A more substantial question: can it happen in a natural example – say, the usual forgetful functor from some familiar algebraic or combinatorial category (finite groups, finite posets, finite graphs, …)? In that arena the answer is “No”.

   Suppose F : C → FinSet is the forgetful functor of

   • models of a finite algebraic theory (finitary operations + equations), or more generally
   • models of a finite limit / finite product sketch,

   i.e. the kind of specification that produces the familiar concrete categories mentioned above.

   Proposition. For such an F the function n↦F(n) is primitive-recursive.

   Sketch of proof. Let Σ be the finite list of operation and relation symbols of arities ≤k appearing in the sketch. On an n–element set

   – a k–ary operation can be chosen in n^{n^k} ways,
   – an ℓ–ary relation in 2^{n^ℓ} ways.

   Thus there are at most

       P(n) = n^{c·n^k}·2^{d·n^ℓ}
   

   ways to interpret Σ on {1,…,n}, where c,d,k,ℓ depend only on Σ. P(n) is primitive-recursive (indeed elementary). Filtering those interpretations that satisfy the finitely many axioms, and then quotienting by isomorphism, are both effectively performable in primitive recursion. Hence F(n) ≤ P(n) and F itself is primitive-recursive.

   Because the Ackermann function outgrows every primitive-recursive function, it cannot occur as the counting function of any finite-set structure that arises from such a finite algebraic (or finite-limit) specification.

3. Conclusion.

• If one is willing to accept an ad-hoc construction, Ackermann-sized growth is easy to realise, as shown in (1).

• In the familiar “natural” concrete categories coming from a finite amount of algebraic data, the counting function is always primitive-recursive, so the Ackermann function (or any faster computable function) cannot appear.

Thus the Ackermann function does not “count” any standard algebraic or combinatorial structures carried by a finite set, although it can be forced to do so by an artificial construction.