Theory and Applications of Categories, Vol. 8, No. 13, 2001, pp. 377–390.

HOW LARGE ARE LEFT EXACT FUNCTORS?

J. ADÁMEK^{∗}, V. KOUBEK^{†} AND V. TRNKOVÁ^{†}

ABSTRACT. For a broad collection of categories K, including all presheaf categories, the following statement is proved to be consistent: every left exact (i.e. finite-limits preserving) functor from K to Set is small, that is, a small colimit of representables. In contrast, for the (presheaf) category K = Alg(1, 1) of unary algebras we construct a functor from Alg(1, 1) to Set which preserves finite products and is not small. We also describe all left exact set-valued functors as directed unions of “reduced representables”, generalizing reduced products.

1. Introduction

We study left exact (i.e. finite-limits preserving) set-valued functors on a category K, and ask whether they all are small, i.e., small colimits of hom-functors. This depends of the category K, of course, since even so well-behaved categories as Grp, the category of groups, have easy counterexamples: recall the well-known example

F = ∏_{i∈Ord} Grp(A_{i}, −) : Grp ⟶ Set

of a functor preserving all limits and not having a left adjoint (thus, not being small), where A_{i} is a simple group of infinite cardinality ℵ_{i}.

In the present paper we are particularly interested in the case K = Set^{A}, A small, since this corresponds to the question put by F. W. Lawvere, J. Rosický and the first author in [ALR1] of legitimacy of all A-ary operations on the category LF P of locally finitely presentable categories. The main result of our paper is that the following statement

“all left exact functors from Set^{A} to Set, A small, are small”

is independent of set theory in the following sense: this is true if the set-theoretical axiom (R), introduced below, is assumed, and this is false if the negation of the following axiom

(M) there do not exist arbitrarily large measurable cardinals

Received by the editors 2001 February 13 and, in revised form, 2001 June 27. Transmitted by F. W. Lawvere. Published on 2001 July 8. 2000 Mathematics Subject Classification: 18A35, 18C99, 04A10. Key words and phrases: left exact functor, small functor, regular ultrafilter. \begin{matrix}c \\ ◯ \end{matrix} J. Adámek, V. Koubek and V. Trnková, 2001. Permission to copy for private use granted. ∗Financial support from the Czech Ministry of Education, Project SMS 34-99141-301 is gratefully acknowledged. †Financial support from the Grant Agency of the Czech Republic under the grant No. 201/99/0310 is gratefully acknowledged.

is assumed. For categories K with finite limits we are going to describe all left exact functors F : K ⟶ Set, generalizing the results for K = Set by the third author [T]. She proved that left exact endofunctors of Set are precisely the (possibly large) directed unions of reduced-power functors Q_{K,D}. Here D is a filter on a set K, and Q_{K,D} assigns to every set X its reduced power

∏_{D} X = colim_{D∈D}X^{D},

or more precisely, Q_{K,D} = colim_{D∈D}Set(D, −).

In the present paper we prove that this result extends to left exact set-valued functors on any category with finite limits: they are precisely the (possibly large) directed unions of “reduced hom-functors” defined analogously to Q_{K,D} above.

Returning to our question of smallness of left exact functors

F : Set^{A} ⟶ Set (A small),

the negative answer has, for A = 1, been already found by J. Reiterman [R]. The idea is simple: recall that ¬(M) is equivalent to the following statement:

¬(M) For every ordinal i there exists a set K_{i} of power ≥ ℵ_{i} and a uniform ultrafilter D_{i} on K_{i} (i.e., an ultrafilter whose members have the same power as K_{i}) closed under intersections of less than ℵ_{i} members.

The functor F : Set ⟶ Set obtained by “transfinite composition” of the functors Q_{K_{i},D_{i}} (i.e., F = colim_{i∈Ord}F_{i} where F_{0} = Id, F_{i+1} = Q_{K_{i},D_{i}} ∘ F_{i} and F_{j} = colim_{i<j}F_{i} for limit ordinals j) is left exact and large (i.e., not small).

Concerning the affirmative answer, it was A. Blass who showed in [B] that every left exact endofunctor of Set is small provided that the following set-theoretical axiom is assumed:

(R) Every uniform ultrafilter on an infinite set is regular

where an ultrafilter D on a set K of cardinality λ is called regular provided that D has λ members D_{i} ∈ D (i ≤ λ) such that every element of K lies in only finitely many of the sets D_{i}. An important property of regular ultrafilters D is that ultrapowers have the “full cardinality” of powers

card ∏_{D} X = card X^{λ} for all X infinite

see [CK]. The argument of A. Blass showing that (R) implies that every left exact functor F : Set ⟶ Set is small probably does not request the full strength of (R); all we need is the following consequence of it:

(R′) There is a set Y such that for every cardinal μ there is a cardinal λ with the property that the ultrapowers of Y with respect to uniform ultrafilters on λ all have cardinality at least μ.

The argument goes as follows: suppose that, to the contrary, a large functor F : Set ⟶ Set is left exact. For every cardinal μ choose λ as in (R′), then there exists, since F is large, a set X of cardinality card X ≥ λ and an element x ∈ F X such that the filter D(x) of all subsets Z of X with x ∈ F m(F Z) for the inclusion map m : Z ⟶ X is uniform. (Since F is left exact, D(x) is indeed a filter.) Thus D(x) can be embedded into a uniform ultrafilter D^{∗}(x). Then (R′) implies

card Q_{X,D(x)}Y ≥ card ∏_{D^{∗}(x)} Y ≥ μ.

This is in contradiction to Q_{X,D(x)} being a subfunctor of F: we cannot have card F Y ≥ μ for all cardinals μ.

Now a decade after the paper of A. Blass it was proved by H.-D. Donder [D] that (R) is consistent with ZFC. We are going to extend Blass’s argument to left exact set-valued functors on any category K which

(a) is finitely complete and well-powered

(b) admits a faithful left adjoint into Set.

In particular, we conclude:

1.1. corollary. It is consistent with ZFC to state that all left exact functors Set^{A} ⟶ Set, A small, are small.

As mentioned above, this corollary answers the open problem put in [ALR1] whether it is consistent with set theory to assume that all small-ary operations on the category LF P are legitimate.

A completely different situation is shown to happen with operations on the category VAR of all finitary varieties studied in [ALR2]. The legitimacy of all small-ary operations on VAR would be equivalent to the statement that every functor

F : Set^{A} ⟶ Set (A small)

preserving finite products is small. But here is the answer dramatically different: for the free monoid A on two generators we prove that (in ZFC) there exists a large functor from Set^{A} to Set preserving finite products.

2. Reduced Hom-functors

Definition. By a filter on an object K of a finitely complete category we understand a non-empty set of subobjects of K closed under finite intersections and upwards-closed (i.e. given subobjects D_{1}, D_{2} of K, if D_{1}, D_{2} ∈ D then D_{1} ∩ D_{2} ∈ D and if D_{1} ⊆ D_{2} then D_{1} ∈ D implies D_{2} ∈ D).

Remark. (1) A filter always contains the largest subobject K.

(2) If K = Set, our concept coincides with the usual concept of a filter on a set K except that here we admit the trivial case of D = all subobjects of K.

Definition. Let D be a filter on an object K of K, then the reduced hom-functor of K modulo D is the functor

Q_{K,D} = colim_{D∈D}K(D, −) in Set^{K}.

A functor in Set^{K} is said to be reduced representable if it is naturally isomorphic to a reduced hom-functor for some filter on an object of K.

Remark. Explicitly, Q_{K,D} is a colimit of the filtered diagram in Set^{K} defined as follows: every element of D is represented by a monomorphism m_{D} : D ⟶ K; given D′ ⊆ D in D we have the unique monomorphism

m_{D′,D} : D′ ⟶ D with m_{D′} = m_{D} ∘ m_{D′,D}.

This leads to a diagram whose objects are the hom-functors

K(D, −) (D ∈ D)

and whose morphisms are the natural transformations

(−) ∘ m_{D′,D} : K(D, −) ⟶ K(D′, −) (D′, D ∈ D, D′ ⊆ D).

2.1. lemma. Every reduced representable functor is left exact.

Proof. A filtered colimit of left exact functors is always left exact because finite limits commute in presheaf categories with filtered colimits (including the large ones as far as they exist.

2.2. theorem. Let K be a finitely complete, well-powered category. A set-valued functor on K is left exact if and only if it is a (possibly large) directed union of reduced representable functors.

Remark. Directed unions are (possibly large) filtered colimits whose scheme is a directed partially ordered class and whose connecting morphisms are monomorphisms. In Set^{K} each such diagram, provided that it has a colimit, has a colimit cocone formed by monomorphisms.

Proof. (i) Sufficiency follows from II.3 since directed unions of left exact functors are left exact. (ii) To prove the necessity, let

F : K ⟶ Set

be a left exact functor. Let I be the class of all finite sets of elements of F, ordered by inclusion. (An element of F is a pair (K, k) where K ∈ Obj K and k ∈ F K.) We use finite sets of elements, rather than just elements, in order to obtain F as a directed union rather than filtered colimit below.

For each element

i = {(K_{i_{1}}, k_{i_{1}}), …, (K_{i_{n}}, k_{i_{n}})}

of I put

K_{i} = K_{i_{1}} × … × K_{i_{n}}

and since F preserves this product, we can denote by

k_{i} ∈ F K_{i}

the unique element mapped by the t-th projection of F K_{i} = F K_{i_{1}} × … × F K_{i_{n}} to k_{i_{t}} (t = 1, …, n). Denote by D_{i} the filter on K_{i} of all subobjects

m_{D} : D ⟼ K_{i}

such that k_{i} lies in the image of F m_{D}. Since F preserves pullbacks, it is easy to see that D_{i} is indeed a filter. Moreover, F preserves monomorphisms, therefore F m_{D} is a monomorphism, thus, there is a unique

k_{i}^{D} ∈ F D with F m_{D}(k_{i}^{D}) = k_{i}.

(iii) We define a diagram

H : I ⟶ Set^{K}

on objects by

Hi = Q_{K_{i},D_{i}} (i ∈ I).

For i ⊆ j in I we define the connecting morphism

h_{i,j} : H_{i} ⟶ H_{j}

by determining its composites with the colimit maps

c_{i}^{D} : K(D, −) ⟶ H_{i} = Q_{K_{i},D_{i}} (D ∈ D_{i})

of H_{i} as follows. Given m_{D} : D ⟼ K_{i} in D_{i} we form a pullback of m_{D} and the first projection, π_{1}, of

K_{j} ≅ K_{i} × K_{i′}

(where i′ denotes the complement of the set i in j), see Figure 1.

Since F preserves the pullback, from

F m_{D}(k_{i}^{D}) = k_{i} = F π_{1}(k_{i}, k_{i′}) = F π_{1}(k_{j}^{D})

we conclude that there exists k_{j}^{D′} ∈ F D′ with

F m_{D′}(k_{j}^{D′}) = k_{j} and F π′(k_{j}^{D′}) = k_{i}^{D}.  (1)

[figure: K_{j}; K_{i}; D′; D; m_{D′}; m_{D}; π_{1}; π′; Figure 1.]

Consequently, m_{D′} : D′ ⟶ K_{j} represents a member of D_{j}. We compose K(π′, −) : K(D, −) ⟶ K(D′, −) with the colimit morphism c_{j}^{D′} : K(D′, −) ⟶ H_{j} and obtain a morphism

c_{j}^{D′} ∘ K(π′, −) : K(D, −) ⟶ H_{j}.

Let us verify that these morphisms form a cocone, i.e., that given

D_{0} ⊆ D in D_{i}

(with the connecting morphism m_{D_{0},D}), then

c_{j}^{D′} ∘ K(π′, −) = [c_{j}^{D′_{0}} ∘ K(π′_{0}, −)] ∘ K(m_{D_{0},D}, −)  (2)

where π′_{0} is the morphism from the corresponding pullback for D_{0}, see Figure 2.

[figure: K_{j}; K_{i}; D′_{0}; D_{0}; m_{D′_{0}}; m_{D_{0}}; π_{1}; π′_{0}; Figure 2.]

Use the universal property to define m_{D′_{0},D′}, see Figure 3. Since c_{j}^{(−)} is a cocone, we have

c_{j}^{D′} = c_{j}^{D′_{0}} ∘ K(m_{D′_{0},D′}, −)

therefore (2) holds:

c_{j}^{D′} ∘ K(π′, −) = c_{j}^{D′_{0}} ∘ K(π′ ∘ m_{D′_{0},D′}, −)

[figure: K_{j}; K_{i}; D′; D; D′_{0}; D_{0}; m_{D′}; m_{D}; m_{D′_{0}}; m_{D_{0}}; m_{D′_{0},D′}; m_{D_{0},D}; π_{1}; π′; π′_{0}; Figure 3.]

= c_{j}^{D′_{0}} ∘ K(m_{D_{0},D} ∘ π′_{0}, −)
= c_{j}^{D′_{0}} ∘ K(π′_{0}, −) ∘ K(m_{D_{0},D}, −).

Consequently, there is a unique morphism

h_{i,j} : H_{i} ⟶ H_{j} (i ⊆ j in I)

factorizing the above cocone through the colimit cocone of H_{i}, i.e. with

h_{i,j} ∘ c_{i}^{D} = c_{j}^{D′} ∘ K(π′, −) for all D ∈ D_{i}.  (3)

(iv) h_{i,j} is a monomorphism in Set^{K} (for any i ⊆ j). In fact, it is sufficient to prove that the right-hand side of (3) is a monomorphism for all D ∈ D_{i}. That is given X ∈ Obj K and f, g : D ⟶ X with F (f ∘ π′)(k_{j}^{D′}) = F (g ∘ π′)(k_{j}^{D′}) then we are to show that F f(k_{i}^{D}) = F g(k_{i}^{D}). This follows from (1).

(v) Our functor F is a colimit of the above directed diagram of all H_{i} (i ∈ I) and h_{i,j} (i ≤ j). In fact, define a natural transformation

h_{i} : H_{i} ⟶ F (i ∈ I)

by

h_{i} ∘ c_{i} : K(D, −) ⟶ F, id_{D} ↦ k_{i}^{D} ∈ F D

for all D ∈ D_{i}. It is easy to see that h_{i} ∘ c_{i}^{D} is a cocone, i.e., if D_{0} ⊆ D then

h_{i} ∘ c_{i}^{D} = h_{i} ∘ c_{i}^{D_{0}} ∘ K(m_{D_{0},D}, −)

because F m_{D_{0},D}(k_{i}^{D_{0}}) = k_{i}^{D} (this follows from the fact that F m_{D_{0}}(k_{i}^{D_{0}}) = F m_{D}(k_{i}^{D})). Thus, h_{i} is well-defined. The above cocone is collectively epic because for every element k ∈ F K of K we have

i = {(K, k)} in I and then h_{i}^{K} : Q_{K,D_{i}} ⟶ F K maps the element c_{i}^{K}(id_{K}) to k.

And each h_{i} is a monomorphism. In fact, assume that h_{i} ∘ c_{i}^{D} merges two elements f, g : D ⟶ X, then we prove that c_{i}^{D} merges them too. By assumption, F f(k_{i}^{D}) = F g(k_{i}^{D}). Let e : D_{0} ⟶ D be an equalizer of f and g, then since F e is an equalizer of F f and F g we have k_{i}^{D} in the image of F e, thus m_{D} ∘ e : D_{0} ⟶ K is a member of D_{i}, and e = m_{D_{0},D}. Since c_{i}^{D} = c_{i}^{D_{0}} ∘ K(m_{D_{0},D}, −), from f ∘ m_{D_{0},D} = g ∘ m_{D_{0},D} we conclude c_{i}^{D}(f) = c_{i}^{D}(g).

Consequently, (H_{i} ⟶^{h_{i}} F)_{i∈I} is a filtered colimit.

3. All left exact set-valued functors are small

Definition. A category K is called strongly left exact provided that it is left exact (i.e., finitely complete) and well-powered and there exists a faithful left adjoint from K to Set.

Examples. (1) Every category of presheaves

K = Set^{A} (A small)

is strongly left exact. The functor V : K ⟶ Set defined on objects H : A ⟶ Set by

V (H) = ∐_{A∈Obj A} HA

and analogously on morphisms is obviously faithful. It preserves colimits, and since K has a set of generators (the hom-functors of objects of A), it follows from the Special Adjoint Functor Theorem that V is a left adjoint.

(2) The category K = T op of topological spaces is strongly left exact — just consider the usual forgetful functor and the indiscrete topology functor Set ⟶ T op.

The category K = Rel(n) of n-ary relations for any cardinal n and the category K = Gra of undirected graphs are strongly left exact — just consider the usual forgetful functor. More generally, all topological categories (see [AHS]) over strongly left exact base-categories are strongly left exact.

(3) The category Grp of all groups is not strongly left exact. Under (R) this is a consequence of the following

3.1. theorem. Assuming the axiom (R), every left exact functor F : K ⟶ Set with K a strongly left exact category is small.

Proof. Let F : K ⟶ Set be a left exact functor, and let

V ⊣ R : Set ⟶ K

be an adjoint situation with V faithful. Thus the unit ε_{K} : K ⟶ RV K is formed by monomorphisms.

The functor F R is left exact, therefore, small, see Introduction above. Thus, there exists a cardinal λ such that for every set M and every element x ∈ F RM there exists a function f : M′ ⟶ M, card M′ < λ, with x ∈ Im (F Rf). We are going to prove that for every object K ∈ K and every element k ∈ F K there exists an object K′ which is a subobject of RM′ for some set M′ with card M′ < λ and there exists a morphism g : K′ ⟶ K with k ∈ Im (F g). Since K is well-powered, all such objects K′ have a small set of representatives with respect to isomorphism — therefore, F is small.

For the element F ε_{K}(k) ∈ F RV K there exists a function f : M′ ⟶ V K, card M′ < λ, and y ∈ F RM′ with

F ε_{K}(k) = F Rf(y).

Let us form a pullback of ε_{K} and Rf, see Figure 4.

[figure: K; RV K; K′; RM′; g; Rf; ε_{K}; ε′_{K}; Figure 4.]

Since F preserves this pullback, the above equality implies that there exists z ∈ F K′ with F g(z) = k and F ε′_{K}(z) = y. Thus k ∈ Im (F g). Since ε_{K} is a monomorphism, so is ε′_{K}, i.e., K′ is a subobject of RM′. 3.2. corollary. The statement “all left exact functors Set^{A} ⟶ Set (A any small category) are small” is consistent with set theory.

In fact, we have remarked above that ZFC consistent implies ZFC+(R) consistent. Remark. Recall that P. Gabriel and F. Ulmer introduced in [GU] a category LF P of locally finitely presentable categories and all right adjoints preserving filtered colimits. In [ALR1] operations on LF P are studied whose arity is any small category A: an Aary operation ω assigns to every object K of LF P an “operation map”, i.e., a functor ω_{K} : K^{A} ⟶ K, which all morphisms H : K ⟶ L of LF P preserve in the expected sense: H ∘ ω_{L} ≅ ω_{K} ∘ H^{A}. It is proved in [ALR1] that A-ary operations correspond bijectively to left exact functors on Set^{A}, and operations called legitimate correspond precisely to small left exact functors. Thus: 3.3. corollary. It is consistent with ZFC to state that all operations of small arity on LF P are legitimate.

4. Set functors preserving finite products

4.1. In [ALR2] the A-ary operations on the category VAR of all varieties of algebras are studied. They correspond to set-valued functors on the category Set^{A} preserving finite products; and the so-called legitimate operations correspond to small functors preserving finite products. We will prove now that there is no analogy between the situation with LF P and VAR, namely, the following holds in ZFC

• there is a large finite-products preserving functor F : Set^{A} ⟶ Set

where A is the free monoid on two generators. 4.2. In fact, assuming the above axiom (M) (nonexistence of arbitrarily large measurable cardinals), we present large, finite-products preserving functors F : K ⟶ Set for a very broad collection of categories K. Namely, for all algebraically universal categories, i.e., categories K such that every variety of algebras has a full embedding into K, see [PT]. The category

Set^{A} ≅ Alg(1, 1)

for the above monoid A (equivalent to the category of unary algebras on two operations) is known to be algebraically universal, and so are the categories Gra (of graphs), Sem (of semigroups), and many others, see [PT].

The axiom (M) guarantees that every algebraically universal category K is universal, i.e., all concrete categories over Set have full embedding into K. In particular, K has a large, full, discrete subcategory. We prove below that it also has a large strongly discrete subcategory where we introduce the following. Definition. A full discrete subcategory D of a category K is called strongly discrete provided that given a finite product D_{1} × D_{2} × … × D_{n} (n ≥ 1) of objects of D and a morphism D_{1} × D_{2} × … × D_{n} ⟶ D with D ∈ D, it follows that D = D_{i} for some i = 1, 2, …, n. Example. of large functor F : K ⟶ Set preserving finite products.

Let D be a large, strongly discrete subcategory of K and let K have finite products. Define F on objects X of K by

F X = \{ \begin{matrix}1 if hom(D_{1} × … × D_{n}, X) ≠ ∅ for some D_{1}, …, D_{n} ∈ D, \\ ∅ else; \end{matrix}

the definition on morphisms is obvious. Then F clearly preserves finite products.

Suppose that F is small. Then there clearly exists a small collection K_{0} of objects K ∈ K with F K = 1 and such that for every object X ∈ K with F X = 1 we have hom(K, X) ≠ ∅ for some K ∈ K_{0}. We derive a contradiction. For each K ∈ K_{0} since F K = 1, there exists a finite set D_{K} ⊆ D such that we have a morphism from ∏_{D∈D_{K}} D into K.

Since K_{0} is small, also the union

D̄ = ⋃_{K∈K_{0}} D_{K}

is small. However, D̄ = D: for every object D_{0} ∈ D we have F D_{0} = 1, thus, by the choice of K_{0} there exists K ∈ K_{0} with hom(K, D_{0}) ≠ ∅. This implies hom(∏_{D∈D_{K}} D, D_{0}) ≠ ∅. By the definition of strong discreteness, we conclude that D_{0} ∈ D_{K} ⊆ D̄. This is a contradiction: D̄ is small but D is large.

4.3. theorem. Assuming (M), every algebraically universal category has a large strongly discrete subcategory. Proof. I. We construct a strongly discrete subcategory in the category Rel(Σ) of relations of signature Σ = {R, T, S} where R is binary, T unary and S ternary. This category is algebraically universal, and so is the category of directed graphs (one binary relation), see [PT]. Since (M) is assumed, it follows that there is a large, full, discrete subcategory D of the category of directed graphs. For every graph G = (X, R_{G}) we denote by G^{∗} the Σ-structure on the set X ∪ {v}, v ∉ X, where

R_{G^{∗}} = R_{G} ∪ {(v, v)},
T_{G^{∗}} = X,
S_{G^{∗}} = {(x, y, z); exactly one of v = x, v = y, v = z holds} ∪ {(v, v, v)}.

We then prove strong discreteness of D^{∗} = {D^{∗}; D ∈ D} in Rel(Σ). In fact, let

f : D_{1}^{∗} × D_{2}^{∗} × … × D_{n}^{∗} ⟶ D^{∗}

be a Σ-homomorphism for D_{i} = (X_{i}, R_{D_{i}}) and D = (Y, R_{D}) in D. Then we will prove that

(∗) there exists i = 1, 2, …, n with f(x̄) ∈ Y for all x ∈ X_{i}

where we put

x̄ = (v, v, …, v, x, v, v, …, v) x in position i.

It follows that we obtain a graph homomorphism from D_{i} to D by x ↦ f(x̄) for x ∈ X_{i}: given R(x_{1}, x_{2}) in D_{i} we have R(x̄_{1}, x̄_{2}) in D_{1}^{∗} × D_{2}^{∗} × … × D_{n}^{∗}, thus, R(f(x̄_{1}), f(x̄_{2})) in D. This proves D_{i} = D and, in case n = 1, f = id – thus, D^{∗} is strongly discrete.

Assuming that (∗) fails, we derive a contradiction by proving that f is the constant function with value v – this contradicts the preservation of T, of course. Given z = (z_{1}, z_{2}, …, z_{n}) in D_{1}^{∗} × D_{2}^{∗} × … × D_{n}^{∗} we prove f(z) = v by induction on the number k of coordinates i with z_{i} ≠ v. The case k = 0, i.e. z = v̄, follows from the negation of (∗): choose x_{i} ∈ X_{i} with f(x̄_{i}) = v (i = 1, 2, …, n). Then S(x̄_{i}, x̄_{i}, v̄) holds in D_{1}^{∗} × D_{2}^{∗} × … × D_{n}^{∗}, thus, S(v, v, f(v̄)) holds in D^{∗} and this proves f(v̄) = v. Also the case k = 1, i.e. z = ȳ_{i} for some y_{i} ∈ X_{i}, follows similarly: we have S(x̄_{i}, ȳ_{i}, v̄) in D_{1}^{∗} × D_{2}^{∗} × … × D_{n}^{∗}, thus S(v, f(ȳ_{i}), v) in D^{∗}, i.e. f(ȳ_{i}) = v. In the induction step we have k ≥ 2 and we choose a coordinate i with z_{i} ∈ X_{i}. Let z′ denote the element obtained from z by changing the i-th coordinate only, with z′_{i} = v. Then S(z, z′, z̄_{i}) in D_{1}^{∗} × D_{2}^{∗} × … × D_{n}^{∗}. Since, by the induction hypothesis, f(z′) = f(z̄_{i}) = v, we conclude S(f(z), v, v) in D^{∗}, thus, f(z) = v.

II. For an arbitrary algebraically universal category K a full embedding E : Rel(Σ) ⟶ K exists, see [PT]. Then E(D^{∗}) is strongly discrete in K. In fact, given a finite product ∏_{i=1}^{n} E(D_{i}) with D_{i} ∈ D^{∗} and given D ∈ D^{∗} for which a morphism ∏_{i=1}^{n} E(D_{i}) ⟶ E(D) exists, then form a product ∏_{i=1}^{n} D_{i} in Rel(Σ) and observe that, since one always has a morphism E(∏_{i=1}^{n} D_{i}) ⟶ ∏_{i=1}^{n} E(D_{i}), there exists a morphism from E(∏_{i=1}^{n} D_{i}) to ED in K. Since E is full, this yields a morphism from ∏_{i=1}^{n} D_{i} to D, thus, D = D_{i} for some i = 1, 2, …, n.

4.4. corollary. For the free monoid on two generators, A, there exist large functors from Set^{A} to Set preserving finite products.

In fact, if we assume (M), then this follows from IV.4 and IV.5 because Set^{A} ≅ Alg(1, 1) is algebraically universal. If ¬(M) is satisfied, we use the above functor F : Set ⟶ Set of J. Reiterman presented in Section I, composed with the natural forgetful functor U : Alg(1, 1) ⟶ Set. The composite F U preserves finite limits. And it is not small: if it were, it would preserve λ-directed colimits for some infinite cardinal λ. However, if one of the sets K_{i} in Reiterman’s example (see Introduction) is chosen to have cardinality at least λ, we can present K_{i} as a λ-directed union of sets L ⊆ K_{i} of cardinality less than λ, and for the free-algebra functor V : Set ⟶ Alg(1, 1) we obtain V K_{i} as a λ-directed colimit of the subalgebras V L. F U does not preserve this λ-directed colimit: in F UV (K_{i}) consider the universal map K_{i} ⟶ UV K_{i} as an element of Q_{K_{i},D_{i}}UV (K_{i}). This element does not lie in the image of F UV (m) for the embedding m : L ⟶ K_{i} of any set L ⊆ K_{i} of cardinality less than λ.

4.5. A description of finite-products preserving functors. Let K be a finitely complete category. A functor K ⟶ Set preserves finite products iff it is a (possibly large) directed union of quotients of representables each of which preserves finite products.

This is a trivial consequence of the following observations: Let F : K ⟶ Set preserve finite products, and let (K, k) be an element of F (k ∈ F K). Then the quotient of K(K, −) which is the image of the Yoneda transformation K(K, −) ⟶ F corresponding to k preserves finite products. The rest of the proof is analogous to that in II.4.

Example. Let D be a filter on an object K. The quotient

R_{K,D}

of K(K, −) given be the following congruence ∼

f ∼ g iff f ∘ m = g ∘ m for some m ∈ D (f, g : K ⟶ X)

preserves finite products.

Remark. In case K = Set, all finite-products preserving quotients of representables are naturally isomorphic to the functors R_{K,D}. Moreover, whenever D is a “true filter”, i.e., ∅ ∉ D, then R_{K,D} ≅ Q_{K,D}. However, given K ≠ ∅ and D = exp K, then

Q_{K,D} = Set(∅, −) −a constant functor with value 1

whereas

R_{K,D}∅ = ∅ and R_{K,D}X ≅ 1 for all X ≠ ∅.

This has been observed by the third author [T] who concluded that the only endofunctors of Set which are not left exact but preserve finite products are those naturally isomorphic to R_{K,exp K} (K ≠ ∅). This result immediately extends to K = power of Set, i.e., to the case K = Set^{A} for A small and discrete. Thus from III.4 we obtain 4.6. corollary. It is consistent with ZFC to state that all operations of small, discrete arity on VAR are legitimate.

References

[AHS] J. Adámek, H. Herrlich and G. E. Strecker, Abstract and Concrete Categories, Wiley–Interscience, New York, 1990.

[ALR1] J. Adámek, F. W. Lawvere and J. Rosický, Continuous categories revisited, submitted.

[ALR2] J. Adámek, F. W. Lawvere and J. Rosický, How algebraic is algebra?, Theory and Appl. of Categories 8 (2001), 253–283.

[B] A. Blass, Exact functors and measurable cardinals, Pacific. J. Math. 63 (1976), 335–346, correction in Pacific. J. Math. 73 (1977), 540.

[CK] C. C. Chang and H. J. Keisler, Model Theory, (3-rd edition), North Holland, Amsterdam, 1990.

[D] H.-D. Donder, Regularity of ultrafilters and the core model, Israel J. Math. 63 (1988), 289–322.

[GU] P. Gabriel and F. Ulmer, Lokal Präsentierbare Kategorien, Lect. Notes in Math. 221, Springer-Verlag, Berlin, 1971.

[M] S. MacLane, Categories for the Working Mathematician, Springer-Verlag, Berlin, 1971.

[PT] A. Pultr and V. Trnková, Combinatorial Algebraic and Topological Representations of Groups, Semigroups and Categories, North Holland, Amsterdam, 1980.

[R] J. Reiterman, An example concerning set functors, Comment. Math. Univ. Carolinae, 12 (1971), 227–233.

[T] V. Trnková, On descriptive classification of set functors I, Comment. Math. Univ. Carolinae, 12 (1971), 143–174.

Institute of Theoretical Computer Science Technical University of Braunschweig Postfach 3329 38023 Braunschweig, Germany

Department of Theoretical Computer Science and Mathematical Logic and Theoretical Institute of Computer Science Faculty of Mathematics and Physics Charles University, Malostranské nám. 25 118 00 Praha 1, Czech Republic

Mathematical Institute of Charles University Faculty of Mathematics and Physics Charles University, Sokolovská 83 186 75 Praha 8 Czech Republic

Email: adamek@iti.cs.tu-bs.de
      koubek@ksi.ms.mff.cuni.cz
      trnkova@karlin.mff.cuni.cz

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/8/n13/n13.{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, Postscript and PDF. Details will be e-mailed to new subscribers. 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 http://www.tac.mta.ca/tac/. 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, Associate Managing Editor Lawrence Breen, Université 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: aurelio.carboni@uninsubria.it P. T. Johnstone, University of Cambridge: ptj@dpmms.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.uu.nl Susan Niefield, Union College: niefiels@union.edu Robert Paré, Dalhousie University: pare@mathstat.dal.ca Andrew Pitts, University of Cambridge: Andrew.Pitts@cl.cam.ac.uk Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca, Managing Editor Jiri Rosicky, Masaryk University: rosicky@math.muni.cz James Stasheff, University of North Carolina: jds@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 Insubria: walters@fis.unico.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca