Theory and Applications of Categories, Vol. 6, No. 5, 1999, pp. 65–76.

CONTRAVARIANT FUNCTORS ON FINITE SETS AND STIRLING NUMBERS

For Jim Lambek

ROBERT PARÉ

ABSTRACT. We characterize the numerical functions which arise as the cardinalities of contravariant functors on finite sets, as those which have a series expansion in terms of Stirling functions. We give a procedure for calculating the coefficients in such series and a concrete test for determining whether a function is of this type. A number of examples are considered.

1. Introduction

Let Set_{0} be the category of finite sets and F : Set_{0}^{op} → Set_{0} a functor. Such a functor induces a function on the natural numbers f : N → N by f(n) = #F [n] where # represents cardinality and [n] is the set {0, 1, 2, …, n − 1}. As two sets have the same cardinality if and only if they are isomorphic, f could be defined by the equation f(#X) = #F (X) for all finite sets X. The question we consider is which functions f arise in this way. As the natural numbers are the cardinalities of finite sets, and as functors are more structured than arbitrary functions, one might expect to get a nice class of numerical functions this way. Let us call them cardinal functions.

For example, the function f(n) = 3^{n} is a cardinal function as it is the cardinality of the representable functor Set_{0}(−, 3). But what about the functions n^{2}, 2·3^{n}−2^{n}, \binom{2n}{n}, n!, \frac{(2n)!}{2^{n}}, and so on? We shall determine a criterion which will help us decide these questions.

We shall see that we are led to certain combinatorial functions, and we can hope for some applications in that direction. We present none here, but see [3] for applications of category theory to combinatorics.

The results below were presented at the AMS meeting in Montréal in September 1997. Shortly after, Andreas Blass pointed out to me the paper [2] by Dougherty in which similar results are obtained. Our Theorems 4.1 and 4.3 are very similar to his Proposition 2.14 and Theorem 1.3. The proofs are not very different but ours have a more categorical flavor. Some lemmas on absolute colimits are of independent interest. The numerical examples in our paper are new and not without interest.

Research supported by a grant from NSERC

Received by the editors 1999 March 8 and, in revised form, 1999 September 13.

Published on 1999 November 30.

1991 Mathematics Subject Classification: 18A22, 05A10.

Key words and phrases: Functor, cardinality, Stirling numbers.

\begin{matrix}c \\ ◯ \end{matrix} Robert Paré 1999. Permission to copy for private use granted.

2. Absolute colimits revisited

Absolute colimits were introduced in my thesis [4] thirty years ago. When I told Jim Lambek, who was then my Ph.D. supervisor, about my characterization of coequalizers which are preserved by all functors, and how they came up in Beck’s tripleability theorem (as it was then called), he said “Good! Write it up. You can call them absolute.” I did. A while later, he asked “Is there a smaller class of functors which would be sufficient to test for absoluteness?” There was, namely the representables, and so my thesis began.

In this section we obtain some new results on absolute colimits in Set_{0}.

2.1. Lemma. Let

[figure: A_{0}; A_{1}; A_{2}; A; f_{1}; f_{2}; B_{0}; B_{1}; B_{2}; B; g_{1}; g_{2}]

be pushouts in Set_{0} in which the f_{i}, g_{i} are epimorphisms. Then

[figure: A_{0} × B_{0}; A_{1} × B_{1}; A_{2} × B_{2}; A × B; f_{1} × g_{1}; f_{2} × g_{2}]

is also a pushout.

Proof. First, we consider the special case where our pushouts are of the form

[figure: A_{0}; A_{0}; A; A; 1_{A_{0}}; 1_{A}; f; f; B_{0}; B; B_{0}; B .; g; g; 1_{B_{0}}; 1_{B}]

Let s be a splitting for g, gs = 1_{B}. Then in

[figure: A_{0} × B; A_{0} × B_{0}; A_{0} × B; A × B; A × B_{0}; A × B,; A_{0} × s; A × s; A_{0} × g; A × g; f × B; f × B_{0}; f × B]

the outside rectangle is a pushout, one in which the two horizontal maps are identities, and the middle vertical arrow is an epimorphism, so the right square is a pushout as required.

Now, for the general case, consider

[figure: A_{0} × B_{0}; A_{1} × B_{0}; A_{1} × B_{1}; A_{2} × B_{0}; A × B_{0}; A × B_{1}; A_{2} × B_{2}; A × B_{2}; A × B; (1); (2); (3); (4)]

where all the arrows are the obvious Cartesian products. By cartesian closedness, ( )×B_{0} and A × ( ) preserve colimits, so (1) and (4) are pushouts. (2) and (3) are diagrams of the sort discussed in the previous paragraph, so they are pushouts too. The result follows by pasting pushouts.

2.2. Remark. The proof of the above lemma goes through, with minor modifications in a monoidal closed category: if the f_{i} and g_{i} are regular epimorphisms, then

[figure: A_{0} ⊗ B_{0}; A_{1} ⊗ B_{1}; A_{2} ⊗ B_{2}; A ⊗ B; f_{1} ⊗ g_{1}; f_{2} ⊗ g_{2}]

is a pushout.

For the first part of the proof, let ϕ(A_{0} ⊗ g) = ψ(f ⊗ B_{0}). Then ϕ and ψ correspond, by adjointness, to ϕ̄ and ψ̄ such that

[figure: A_{0}; [B, C]; A; [B_{0}, C]; ϕ̄; ψ̄; f; [g, C]]

commutes. As [g, C] is monic (g is epic) and f is a regular epi, there exists a unique diagonal fill-in θ̄: A → [B, C] such that θ̄f = ϕ̄ and [g, C]θ̄ = ψ̄. Again, by adjointness, this corresponds to a unique θ : A ⊗ B → C such that θ(f ⊗ B) = ψ and θ(A ⊗ g) = ψ. So the required square is a pushout.

The second part of the proof uses only that ( ) ⊗ B_{0} and A ⊗ ( ) preserve pushouts.

Recall from [5] that a colimit is called absolute if it is preserved by all functors.

2.3. Proposition. Pushouts of epimorphisms in Set_{0} are absolute.

Proof. One of the basic results of [5] is that a colimit is absolute if and only if it is preserved by all representables. In the case of Set_{0}, the representables [A, −] are finite powers ( )^{#A}, and by Lemma 1, a finite power of a pushout of epimorphisms is again a pushout. The result follows.

2.4. Remark. Richard Wood points out that the same proof shows that reflexive coequalizers in Set_{0} are absolute. In fact, if f_{1}, f_{2} : A_{0} \overrightarrow{→} A_{1} is a reflexive pair, then the coequalizer of f_{1} and f_{2} is the same as their pushout, so this is a special case of Proposition 2.3.

2.5. Remark. A similar result, which we shall not need in the sequel, is the following: non-empty intersections are absolute in Set_{0}. Indeed, suppose that A and B are subsets of C and that A ∩ B ≠ ∅. Choose c_{0} ∈ A ∩ B and define functions f : C → A by

f(c) = \{ \begin{matrix}c & if c ∈ A \\ c_{0} & otherwise \end{matrix}

and g : B → A ∩ B by

g(b) = \{ \begin{matrix}b & if b ∈ A ∩ B \\ c_{0} & otherwise. \end{matrix}

Then it is easily seen that

[figure: A ∩ B; B; A ∩ B; A; C; A; g; f]

commutes. Furthermore, the outside rectangle is an absolute pullback (as the two horizontal arrows are identities) and the middle vertical arrow is an absolute monomorphism (as it is split). Thus the left square is an absolute pullback.

We see that non-empty pullbacks of monomorphisms in Set_{0} are absolute for a relatively simple reason. One might say that the pullback square itself is split. This is not the case for pushouts of epimorphisms in Set_{0} where an unbounded number (depending on the size of the sets involved) of functions may be required to express absoluteness equationally. Pushouts of epimorphisms between infinite sets need not be absolute either.

3. The structure of contravariant functors

Let F : Set_{0}^{op} → Set_{0} be any functor. Say that (n, a) is minimal for F if a ∈ F [n] and is not equal to any F (α)(b) for α : [n] → [m], b ∈ F [m] with m < n.

3.1. Proposition. Let x ∈ F X be any element of F. Then:

(1) There is (n, a) minimal for F and f : X → [n] epic, such that F (f)(a) = x.

(2) If (m, b) and g : X → [m] also have the same properties, then m = n and there exists σ ∈ S_{n} such that g = σf and F (σ)(b) = a.

Proof. (1) Of all the triples (n, f, a), n ∈ N, f : X → [n], a ∈ F [n] with F (f)(a) = x, choose one with minimal n. (There is at least one such triple, for if we let n be the cardinality of X, then there will be an isomorphism f : X → [n] and we can take a = F (f^{−1})(x).) Then (n, a) is minimal for F, because if there were α : [n] → [m] and b ∈ F [m] with F (α)(b) = a and m < n, then F (αf)(b) = F (f)F (α)(b) = F (f)(a) = x, and n would not have been minimal for x. Also, if f were not epic it would factor as αg where g : X → [m] and α : [m] → [n] with m < n. Then F (g)(F (α)(a)) = F (αg)(a) = F (f)(a) = x and again, n would not be minimal for x.

(2) Let (m, b) be minimal for F and g : X → [m] epic such that F (g)(b) = x. Take the pushout

[figure: X; [n]; [m]; [p]; f; β; g; α]

which is absolute by Proposition 2.3. Thus

[figure: F [p]; F [n]; F [m]; F X]

is a pullback. As F (f)(a) = x = F (g)(b), there exists c ∈ F [p] with F (α)(c) = a and F (β)(c) = b. As (n, a) is minimal for F, p cannot be less than n, so α is an isomorphism. Similarly, β is an isomorphism. It follows that n = p = m and if σ = β^{−1}α ∈ S_{n}, then σf = g and F (σ)(b) = F (α)F (β)^{−1}(b) = F (α)(c) = a.

Let A_{n} be the set of minimal elements in F [n], i.e.

A_{n} = {a ∈ F [n]|(n, a) is minimal for F }.

Then the symmetric group S_{n} acts on the right on A_{n} by

(a, σ) ↦ F (σ)(a).

Also, S_{n} acts on the left on Epi(X, [n]), the set of epimorphisms X → [n], by

(σ, f) ↦ σf.

Now the above proposition can be restated as follows.

3.2. Corollary. For each X, the function

∑_{n=0}^{∞} A_{n} ⊗_{S_{n}} Epi(X, [n]) → F X

a ⊗ f ↦ F (f)(a)

is a bijection.

3.3. Proposition. Given finite S_{n}-sets, A_{n}, for n = 0, 1, 2, …, such that A_{0} ≠ ∅ and A_{1} ≠ ∅, then

G(X) = ∑_{n=0}^{∞} A_{n} ⊗_{S_{n}} Epi(X, [n])

can be made into a functor G : Set_{0}^{op} → Set_{0}.

Proof. If n > #X, then Epi(X, [n]) = ∅ so that for any fixed X the infinite coproduct is essentially finite and G(X) is a finite set. Note that S_{0} and S_{1} are both the trivial group, so that A_{0} and A_{1} are just sets. Pick a_{0} ∈ A_{0} and a_{1} ∈ A_{1}. Let τ_{Y} : Y → [1] denote the unique function into the terminal object. It is epi if Y ≠ ∅.

Let g : Y → X and (n, a ⊗ f) ∈ G(X). Define

G(g)(n, a ⊗ f) = \{ \begin{matrix}(n, a ⊗ (fg)) & if fg is epi \\ (1, a_{1} ⊗ τ_{Y}) & if fg is not epi and Y ≠ ∅ \\ (0, a_{0} ⊗ 1) & if fg is not epi but Y = ∅. \end{matrix}

First, G(g) is well-defined. Indeed, if a ⊗ f = a′ ⊗ f′, then there is σ ∈ S_{n} such that f′ = σf and a′σ = a. Then fg is epi if and only if f′g is epi and in that case a ⊗ (fg) = (a′σ) ⊗ (fg) = a′ ⊗ (σfg) = a′ ⊗ f′g.

It is clear from the definition that G(1_{X}) = 1_{G(X)}. Now let h : Z → Y. If fgh is epi, then so is fg and

G(h)G(g)(n, a ⊗ f) = G(h)(n, a ⊗ (fg)) = (n, a ⊗ (fgh)) = G(gh)(n, a ⊗ f).

If fg is epi but fgh is not and Z ≠ ∅, then

G(h)G(g)(n, a ⊗ f) = G(h)(n, a ⊗ (fg)) = (1, a_{1} ⊗ τ_{Z}) = G(gh)(n, a ⊗ f).

If fg is not epi, then fgh is not either. If Z ≠ ∅, then

G(h)G(g)(n, a ⊗ f) = G(h)(1, a_{1} ⊗ τ_{Y}) = (1, a_{1} ⊗ τ_{Y} h) = (1, a_{1} ⊗ τ_{Z}) = G(gh)(n, a ⊗ f).

Finally, if Z = ∅, then

G(h)G(g)(n, a ⊗ f) = (0, a_{0} ⊗ 1) = G(gh)(n, a ⊗ f).

3.4. Remark. The above construction is not canonical so we can hardly expect the bijection of the previous corollary to be natural, although we do have naturality if we restrict to morphisms that are epic.

4. Stirling series

The Stirling numbers of the second kind are the numbers S(m, n) of partitions of m into n pieces. They satisfy the recurrence relations

S(0, n) = \{ \begin{matrix}1 & if n = 0 \\ 0 & otherwise. \end{matrix}
S(m + 1, n) = S(m, n − 1) + nS(m, n).

A table of values for S(m, n) can be constructed from these relations, just like Pascal’s triangle.

\begin{matrix}[figure: n; m] & 0 & 1 & 2 & 3 & 4 & 5 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ 2 & 0 & 0 & 1 & 3 & 7 & 15 \\ 3 & 0 & 0 & 0 & 1 & 6 & 25 \\ 4 & 0 & 0 & 0 & 0 & 1 & 10 \\ 5 & 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}

One might guess from this table that S(m, 2) = 2^{m−1} − 1, m ≥ 1, and this is easily seen. It can also be seen that S(m, 3) = (3^{m−1} − 2^{m} + 1)/2. For more on Stirling numbers any basic text on combinatorics can be consulted, e.g. [1].

4.1. Theorem. f : N → N is a cardinal function if and only if it can be written as a Stirling series

f(m) = ∑_{n=0}^{∞} a_{n}S(m, n)

where the a_{n} are natural numbers with the properties

(1) a_{0} = 0 ⇒ a_{n} = 0 for all n

(2) a_{1} = 0 ⇒ a_{n} = 0 for all n ≥ 1.

Proof. Assume that f is a cardinal function corresponding to the functor F and let A_{n} be as in Corollary 3.2. As S_{n} acts freely on Epi(X, [n]),

A_{n} ⊗_{S_{n}} Epi(X, [n]) ≅ A_{n} × Orbits(Epi(X, [n])),

but an orbit is precisely a quotient of X with n elements. Thus

#(A_{n} ⊗_{S_{n}} Epi(X, [n])) = #A_{n} · S(#X, n).

It then follows by Corollary 3.2 that any cardinal function f can be written as a Stirling series with a_{n} = #A_{n}.

If a_{0} = 0, then F (∅), which is A_{0}, is empty. Since there is always a function ∅ → X, we have F (X) → F (∅) = ∅ so that F (X) = ∅. Thus all a_{n} = 0.

Similarly, if a_{1} = 0 then F (1) = A_{1} = ∅, and as there is a function 1 → X for every non-empty X, we have F (X) → F (1) = ∅ which implies F (X) = ∅. We conclude that a_{n} = 0 for all n ≥ 1.

Conversely, given any Stirling series ∑_{n=0}^{∞} a_{n}S(m, n) with a_{0} and a_{1} non-zero, we can choose S_{n}-sets A_{n} with cardinalities a_{n} (say with trivial action). Then Proposition 3.3 will give a functor G with the right cardinality, thus ∑_{n=0}^{∞} a_{n}S(m, n) is a cardinal function.

The functor F = A_{0} × [−, ∅] takes the value A_{0} at ∅ and ∅ elsewhere, which covers the case where a_{0} or a_{1} are 0. 4.2. Example. The hom functor [−, [k]] : Set_{0}^{op} → Set_{0} gives rise to the exponential function f(m) = k^{m} so we should be able to write k^{m} as a Stirling series. As k^{m} is the cardinality of the set of functions α : [m] → [k] and each such α factors uniquely as a quotient followed by a one-to-one map, we get

k^{m} = S(m, 0) + kS(m, 1) + k(k − 1)S(m, 2) + k(k − 1)(k − 2)S(m, 3) + ⋯

This is because the number of one-to-one maps from a set with n elements to one with k is given by the falling power

k^{↓n} = k(k − 1)(k − 2) ⋯ (k − n + 1) = \frac{k!}{n!}.

Thus k^{m} = ∑_{n=0}^{∞} k^{↓n}S(m, n).

The additive Abelian group Z[x] is free with basis ⟨1, x, x^{2}, x^{3}, …⟩. But as x^{↓n} is a monic polynomial of degree n, ⟨1, x, x^{↓2}, x^{↓3}, …⟩ also forms a basis. The above equation shows that the change of bases matrix, changing from the first to the second, is given by the Stirling numbers of the second kind [S(m, n)]. Its inverse, which changes from the second to the first basis, defines the Stirling numbers of the first kind [s(n, m)]. Thus x^{↓n} = ∑_{m} s(n, m)x^{m}. In particular we have

∑_{m} s(n, m)S(m, k) (*) = \{ \begin{matrix}1 & if n = k \\ 0 & otherwise. \end{matrix}

Of course, all this is well-known (see [1]).

Let E : N^{N} → N^{N} be the shift operator, (Ef)(n) = f(n + 1), and I the identity operator. These are used in the calculus of finite differences, where the difference operator Δ = E − I is the main topic of study.

With these preliminaries we can now prove the following theorem giving the Stirling coefficients of a cardinal function. 4.3. Theorem. Let f(m) = ∑_{n=0}^{∞} a_{n}S(m, n). Then a_{n} = E^{↓n}f(0). Proof. E^{↓n} = E(E − I)(E − 2I) ⋯ (E − (n − 1)I) = ∑_{m} s(n, m)E^{m} so

E^{↓n}f(0) = ∑_{m} s(n, m)E^{m}f(0)
= ∑_{m} s(n, m)f(m)
= ∑_{m} s(n, m) ∑_{k} a_{k}S(m, k)
= ∑_{k} ∑_{m} s(n, m)S(m, k)a_{k}
= a_{n} (by (*)).

4.4. Corollary. f : N → N is a cardinal function if and only if one of the following holds:

(a) f(n) = 0 for all n ≥ 1

(b) E^{↓n}f(0) ≥ 0 for all n and f(0), f(1) ≠ 0.

5. Examples

5.1. Example. m^{2} Asymptotically, S(m, n) ∼ \frac{n^{m}}{n!} (for fixed n), i.e.

lim_{m→∞} \frac{n!S(m, n)}{n^{m}} = 1.

Intuitively, if m ≫ n, a random function α : [m] → [n] is almost certainly onto, so the number of quotients will be approximately the number of functions [m] → [n] divided by the number of permutations on [n]. The reader who is not convinced by this probabilistic argument can consult [1] p. 140 #10 where some hints are given.

Thus a non-constant polynomial never defines a cardinal function, for if it is nonconstant some a_{n} ≠ 0 (n > 1) and the function \frac{n^{m}}{n!} grows faster than any polynomial.

5.2. Example. \binom{2m}{m} Note that

E^{↓(n+1)}f(m) = (E − nI)E^{↓n}f(m) = E^{↓n}f(m + 1) − nE^{↓n}f(m)

so we can calculate the values E^{↓n}f(m) recursively. We arrange the values in a table with the values of f(m) in the first row, with each new entry being calculated using the two values above it in the previous row, like for finite differences. Thus for f(m) = \binom{2m}{m} we get:

[figure: n; m] 0 1 2 3 4 5 6
0 1 2 6 20 70 252 924
1 2 6 20 70 252 924
2 4 14 50 182 672
3 6 22 82 308
4 4 16 62
5 0 -2
6 -2

As E^{↓6}f(0) = −2, we see that f(m) = \binom{2m}{m} is not a cardinal function. We might have

believed that it was one, as 2^{m} ≤ \binom{2m}{m} ≤ 4^{m}.

5.3. Example. 2 · 3^{m} − 2^{m}

This is a cardinal function as is easily seen by constructing a table as above. The values of E^{↓n}f(0) turn out to be 1, 4, 10, 12, 0, 0, 0, . . .. But it is easy to construct a functor with cardinality 2 · 3^{m} − 2^{m}. Let α : [2] → [3] be the inclusion. Then the pushout P in

[figure: [−, [2]]; [−, [3]]; [−, [3]]; P]

has the right cardinality.

5.4. Example. \frac{(2m)!}{2^{m}}

5.5. Lemma. For n ≤ m natural numbers we have

E^{↓n}f(m − n) = f(m) − ∑_{i=0}^{n−1} iE^{↓i}f(m − 1 − i).

Proof.

E^{↓n}f(m − n) = (E − (n − 1)I)E^{↓(n−1)}f(m − n)
= E^{↓(n−1)}f(m − n + 1) − (n − 1)E^{↓(n−1)}f(m − n)

= E^{↓(n−2)}f(m − n + 2) − (n − 2)E^{↓(n−2)}f(m − n + 1) − (n − 1)E^{↓(n−1)}f(m − n)

⋮

= E^{↓0}f(m) − 0E^{↓0}f(m − 1) − 1E^{↓1}f(m − 2) − ⋯ − (n − 1)E^{↓(n−1)}f(m − n)

= f(m) − (1E^{↓1}f(m − 2) + 2E^{↓2}f(m − 3) + ⋯ + (n − 1)E^{↓(n−1)}f(m − n)).

5.6. Proposition. Suppose that neither f(0) nor f(1) is 0 and for every m, f(m+1) ≥ \frac{m(m+1)}{2}f(m), then f is a cardinal function.

Proof. We shall prove by induction on m that 0 ≤ E^{↓n}f(m−n) ≤ f(m) for all 0 ≤ n ≤ m. For m = 0, we have only n = 0 and the statement is obvious.

Assume the statement holds for m. Then

E^{↓n}f(m + 1 − n) = f(m + 1) − ∑_{i=0}^{n−1} iE^{↓i}f(m − i)
≥ f(m + 1) − ∑_{i=0}^{n−1} if(m) (by induction hypothesis)
= f(m + 1) − \frac{(n−1)n}{2}f(m)
≥ f(m + 1) − \frac{m(m+1)}{2}f(m) (as n ≤ m + 1)
≥ 0.

It is also clear that, as E^{↓n}f(m + 1 − n) = f(m + 1) − (non-negative terms),

E^{↓n}f(m + 1 − n) ≤ f(m + 1).

This proves the inductive step.

Then putting n = m we get E^{↓n}f(0) ≥ 0 for all n, so f is a cardinal function.

Consider f(m) = \frac{(2m)!}{2^{m}}. Its values are natural numbers and

f(m + 1) = \frac{(2m + 2)!}{2^{m+1}} = \frac{(2m + 2)(2m + 1)}{2}f(m)

so by our proposition it is a cardinal function.

The smallest function satisfying the conditions of Proposition 5.6 is

f(m) = (m − 1)!m!/2^{m−1} m ≥ 1,

with f(0) = 1. This is a cardinal function.

As cardinal functions are closed under products, f(m) = (2m)! = 2^{m} · \frac{(2m)!}{2^{m}} is also cardinal.

Consider f(m) = m^{2m}.

\begin{aligned}f(m + 1) & = & (m + 1)^{(2m+2)} & = & (m + 1)^{2}(m + 1)^{2m} \\ & > & (m + 1)^{2}m^{2m} & > & \frac{(m+1)m}{2}f(m). \end{aligned}

So m^{2m} is a cardinal function.

We don’t know of any naturally arising functor with these cardinalities.

5.7. Example. m!, m^{m}

The \frac{m(m+1)}{2} in Proposition 5.6 is the best we can do with that kind of condition, as the following shows.

5.8. Proposition. Let ϕ : N → N be a function with the property that any f for which f(m + 1) ≥ ϕ(m)f(m) for all m and f(0), f(1) ≠ 0, is a cardinal function. Then ϕ(m) ≥ \frac{m(m+1)}{2}.

Proof. For natural numbers, p and q, define a function f by

f(m) = \{ \begin{matrix}0 & if m < p \\ q ∏_{k=p}^{m−1} ϕ(k) & if m ≥ p \end{matrix}

with the convention that an empty product is 1 (so that f(p) = q). Then f(m + 1) = ϕ(m)f(m) if m ≠ p − 1 and f(m + 1) = q ≥ 0 = ϕ(m)f(m) if m = p − 1. Thus f satisfies our conditions, except for f(0), f(1) ≠ 0.

Let g(m) = ∏_{k=0}^{m−1}(ϕ(k) + 1). Then g(m + 1) = (ϕ(m) + 1)g(m) ≥ ϕ(m)g(m) and g(0), g(1) ≠ 0. So g satisfies all the conditions. It follows that f + g does too, so it is a cardinal function, by hypothesis, and by Corollary 4.4, E^{↓n}(f + g)(0) ≥ 0.

Now, as f(m) = 0 for all m < p, all the differences E^{↓n}f(m−n) = 0 for 0 ≤ n ≤ m < p. Then E^{↓n}f(p − n) = f(p) − ∑_{i=0}^{n−1} iE^{↓i}f(p − 1 − i) = f(p) = q for all 0 ≤ n ≤ p. Consequently,

E^{↓(p+1)}f(0) = f(p + 1) − ∑_{i=1}^{p} iE^{↓i}f(p − i)
= qϕ(p) − ∑_{i=1}^{p} iq
= q(ϕ(p) − \frac{p(p+1)}{2}).

Now, E^{↓(p+1)}(f + g)(0) = E^{↓(p+1)}f(0) + E^{↓(p+1)}g(0) = q(ϕ(p) − \frac{p(p+1)}{2}) + E^{↓(p+1)}g(0) which is ≥ 0 for all q. Thus ϕ(p) − \frac{p(p+1)}{2} ≥ 0.

The function f(m) = m! clearly doesn’t satisfy the conditions of Proposition 5.6. Some hand calculations suggest that it might be cardinal, but using Maple, we see that E^{↓12}f(0) = −519, 312, so it isn’t.

On the other hand, again using Maple, we see that for f(m) = m^{m} and f(m) = 2^{m}m!, E^{↓n}f(0) > 0 for all n ≤ 100, which strongly suggests that they are cardinal functions.

References

[1] Comtet, Louis, Analyse Combinatoire, Tomes I & II, Presses Universitaires de France, Paris, 1970.

[2] Dougherty, Randall, “Functors on the Category of Finite Sets,” TAMS, vol. 330, Number 2, April 1992.

[3] Joyal, André, “Une théorie combinatoire des séries formelles,” Advances in Math., Vol. 42, No. 1, 1980, pp. 1-82.

[4] Paré, Robert, “Absoluteness Properties in Category Theory,” Ph.D. Thesis, McGill, 1969.

[5] Paré, Robert, “On Absolute Colimits,” J. Alg. 19(1971), pp. 80-95.

Department of Mathematics and Statistics Dalhousie University Halifax, Nova Scotia Canada B3H 3J5

Email: pare@mathstat.dal.ca

This article may be accessed via WWW at http://www.tac.mta.ca/tac/ or by anony-

mous ftp at ftp://ftp.tac.mta.ca/pub/tac/html/volumes/6/n5/n5.{dvi,ps}

THEORY AND APPLICATIONS OF CATEGORIES (ISSN 1201-561X) will disseminate articles that significantly advance the study of categorical algebra or methods, or that make significant new contributions to mathematical science using categorical methods. The scope of the journal includes: all areas of pure category theory, including higher dimensional categories; applications of category theory to algebra, geometry and topology and other areas of mathematics; applications of category theory to computer science, physics and other mathematical sciences; contributions to scientific knowledge that make use of categorical methods.

Articles appearing in the journal have been carefully and critically refereed under the responsibility of members of the Editorial Board. Only papers judged to be both significant and excellent are accepted for publication.

The method of distribution of the journal is via the Internet tools WWW/ftp. The journal is archived electronically and in printed paper format.

Subscription information. Individual subscribers receive (by e-mail) abstracts of articles as they are published. Full text of published articles is available in .dvi and Postscript format. Details will be e-mailed to new subscribers and are available by WWW/ftp. To subscribe, send e-mail to tac@mta.ca including a full name and postal address. For institutional subscription, send enquiries to the Managing Editor, Robert Rosebrugh, rrosebrugh@mta.ca.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX is the preferred flavour. TEX source of articles for publication should be submitted by e-mail directly to an appropriate Editor. They are listed below. Please obtain detailed information on submission format and style files from the journal’s WWW server at URL http://www.tac.mta.ca/tac/ or by anonymous ftp from ftp.tac.mta.ca in the directory pub/tac/info. You may also write to tac@mta.ca to receive details by e-mail.

Editorial board.

John Baez, University of California, Riverside: baez@math.ucr.edu Michael Barr, McGill University: barr@barrs.org Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk Jean-Luc Brylinski, Pennsylvania State University: jlb@math.psu.edu Aurelio Carboni, Università dell Insubria: carboni@fis.unico.it P. T. Johnstone, University of Cambridge: ptj@pmms.cam.ac.uk G. Max Kelly, University of Sydney: maxk@maths.usyd.edu.au Anders Kock, University of Aarhus: kock@imf.au.dk F. William Lawvere, State University of New York at Buffalo: wlawvere@acsu.buffalo.edu Jean-Louis Loday, Université de Strasbourg: loday@math.u-strasbg.fr Ieke Moerdijk, University of Utrecht: moerdijk@math.ruu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mscs.dal.ca Andrew Pitts, University of Cambridge: ap@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@charlie.math.unc.edu Ross Street, Macquarie University: street@math.mq.edu.au Walter Tholen, York University: tholen@mathstat.yorku.ca Myles Tierney, Rutgers University: tierney@math.rutgers.edu Robert F. C. Walters, University of Sydney: walters b@maths.usyd.edu.au R. J. Wood, Dalhousie University: rjwood@mscs.dal.ca