Theory and Applications of Categories, Vol. 14, No. 13, 2005, pp. 294–309.

EVERY GROUP IS REPRESENTABLE BY ALL NATURAL TRANSFORMATIONS OF SOME SET-FUNCTOR

LIBOR BARTO, PETR ZIMA

Abstract. For every group G, we construct a functor F:SET → SET (finitary for a finite group G) such that the monoid of all natural endotransformations of F is a group isomorphic to G.

1. Introduction

Classical results by G. Birkhoff [3] and J. de Groot [4] show that every group can be represented as the automorphism group of a distributive lattice, and as the automorphism group of a topological space. Since then many results of similar type were proven. An extensive survey about group-universality is presented in [5]. Many such representations are consequences of far more general results concerning representations of categories, see the monograph [9].

The structures, in which the group representation problem was considered, were always structured sets – algebras, topologies or relational structures. Our contribution is of a different nature, the structure being a set functor, i.e. an endofunctor of the category SET of all sets and mappings. Set functors were studied in late sixties and early seventies ([12, 13, 14, 6, 7, 8]) to get an insight into the behaviour of generalized algebraic categories A(F, G). After about thirty years this field of problems has been refreshed and further results about internal structure of set functors obtained ([10, 11, 1, 2]).

The representation questions were not yet examined for set functors, the present paper is perhaps the first step in this direction. It solves the problem put to the authors by V. Trnková. We prove here a stronger form of the group representation problem: For every group G, we construct a set functor F such that every endotransformation of F is a natural equivalence and the group of all endotransformations of F is isomorphic to G. Moreover for a finite G, the functor F will be finitary.

1.1. Problem. Can every monoid be respresented as the monoid of all endotransformations of a set functor? Is the quasicategory of all set functors even alg-universal or even universal? Recall that a (quasi)category K is alg-universal, if every category Alg(Σ) (the category of algebras with the signature Σ and algebra homomorphisms) can be fully embedded into K. K is universal, if every concretizable category can be fully embedded into K.

Received by the editors 2005-05-26 and, in revised form, 2005-09-09.

Transmitted by Jiri Rosicky. Published on 2005-09-26.

2000 Mathematics Subject Classification: 18B15.

Key words and phrases: set functor, group universal category.

\begin{matrix}c \\ ◯ \end{matrix} Libor Barto, Petr Zima, 2005. Permission to copy for private use granted.

EVERY GROUP IS REP’BLE BY ALL NAT TRANSF’NS OF SOME SET-FUNCTOR 295

2. Notation

Notation for sets and mappings. Here R ⊆ X, Y are sets, x ∈ X, f:X → Y is a mapping, ∼ is an equivalence on X:

α  Ordinal = set of smaller ordinals
κ, λ  Cardinal = set of smaller ordinals
|X|  Cardinality of X
R ⊂ X  R is a proper subset of X
id_{X}  Identity mapping id_{X}:X → X
χ_{R,X}:X → 2 Characteristic mapping of R, i.e. f(x) = 1 iff x ∈ R
P X  Set of all subsets of X
f[R]  Image of R
f^{−1}[R]  Inverse image of R
Im(f)  Image of X (= f[X])
X/ ∼  Factor set X modulo ∼
[x]_{∼}  Equivalence class of x modulo ∼

Notation for functors. Here F is a set functor, X is a set, x ∈ F X, μ: F → F is a natural transformation:

Nat(F)  Monoid of all natural transformations of F
NatEpi(F)  Monoid of all natural epitransformations of F
μ_{X}:F X → F X X-th component of the transformation μ.
Flt(x)  Filter of x (see the next section)
Mon(x)  Monoid of x (see the next section)

Notation for groups. Here H ≤ G are groups:

S_{X}  Symmetric group on X = group of all permutations on X.
Aut(G) Automorphism group of G
G/H  Factor group (if H is a normal subgroup of G)
N_{G}H  Normalizer of H in G, i.e. N_{G}H = {g ∈ G | gHg^{−1} = H}

3. Set functors

In this section, we recall some known facts about set functors, which will be needed in this paper.

Let F : SET → SET be a set functor. F is said to be faithful, if it is one-to-one on hom sets. Recall that F is faithful, if there exists an element x ∈ F 1 such that F i_{0}(x) ≠ F i_{1}(x) for the two distinct mappings i_{0}, i_{1} :1 → 2 (see [12]).

F is said to be connected, if |F 1| = 1. Let F be a faithful connected set functor, X be a set, x ∈ F X. Then the set

Flt(x) := {U | U ⊆ X, (∃u ∈ F U) F i(u) = x where i is the inclusion i:U → X}

is a filter on X, we say filter of the point x (this is probably the most important property of set functors, see ([6])). F is said to be finitary, if there is a finite R ∈ Flt(x) for every x ∈ F X.

Next important property of a point x ∈ F X is its monoid:

Mon(x) := {f | f:X → X, F f(x) = x}

The next three propositions are easy consequences of the definitions. They are known in more general forms, but we include the proofs for the reader’s convenience:

3.1. Proposition. Let F be a faithful connected set functor, X be a set, x ∈ F X, U ∈ Flt(x), m ∈ Mon(x). Then m[U] ∈ Flt(x) (and therefore U ∩ m[U] ∈ Flt(x)).

Proof. Let i:U → X, j:m[U] → X be the inclusions, u ∈ U be such that F i(u) = x, and m′: U → m[U] the restriction of m to U. Then F j(F m′(u)) = F m(F i(u)) = x and m[U] ∈ Flt(x).

3.2. Proposition. Let F be a faithful connected set functor, μ: F → F be a natural transformation, X be a set, x ∈ F X. Then

1. Flt(x) ⊆ Flt(μ_{X}(x))

2. Mon(x) ⊆ Mon(μ_{X}(x))

Proof.

1. Let U ∈ Flt(x) and u such that F i(u) = x. Then F i(μ_{U}(u)) = μ_{X}(F i(u)) = μ_{X}(x) and U ∈ Flt(μ_{X}(x)).

2. Let m ∈ Mon(x). Then F m(μ_{X}(x)) = μ_{X}(F m(x)) = μ_{X}(x) and f ∈ Mon(μ_{X}(x)).

3.3. Proposition. Let F be a faithful connected set functor, μ: F → F be a natural transformation, x ∈ F 1, X be a set, f:1 → X be a mapping. Then μ_{X}(F f(x)) = F f(x).

Proof. Clearly μ_{X}(F f(x)) = F f(μ_{1}(x)) and μ_{1}(x) = x from the connectedness.

4. Constructions

We present here two constructions. In both of them, there figure some cardinal κ such that the constructed functor F has the following property: Every natural endotransformation μ : F → F, μ = {μ_{X} | X is a set } is completely determined by its κ-th component μ_{κ}:F κ → F κ. Then the submonoid

Nat_{κ}(F) := {μ_{κ} | μ is a natural endotransformation of F }

of the full transformation monoid on κ is isomorphic to the monoid of all natural endotransformations of F (the monoid operation is the composition of transformations).

A family of mappings μ is a natural endotransformation of F, iff μ_{Y} ∘F f = F f ∘μ_{X} for every mapping f: X → Y. The difference between the constructions is, which mappings f are used to force the monoid Nat_{κ}(F) to be isomorphic to a given group G. In the first one, which gives some partial results, the important mappings are bijections f:κ → κ. In the second one, which gives the general result for groups of order at least 7, the important mappings are f:κ → 2.

5. First construction – representing normalizers

In this section, we prove the following partial results:

5.1. Theorem. Let G be a subgroup of S_{κ}, where κ > 2 is a finite cardinal. Then there exists a finitary set functor F such that Nat(F) ≅ N_{S_{κ}}G/G

5.2. Theorem. Let G be a subgroup of S_{κ}, where κ > 2 is a cardinal. Then there exists a set functor F such that NatEpi(F) ≅ N_{S_{κ}}G/G

As an example, for the trivial subgroup G = {id_{κ}} of S_{κ}, we obtain a representation of S_{κ}. There are also computed the normalizers in some other special cases (5.15, 5.16). This gives us representations of Aut(G) for arbitrary group G, |G| > 2 and also Aut(G)/H, where H is a normal subgroup of Aut(G) such that |G| and |H| are co-prime natural numbers. In particular, this gives a representation of cyclic groups Z_{p^{n}} for arbitrary odd prime number p and natural number n, and representation of groups of order less than 7:

Z_{2} ≅ Aut(Z_{3}), Z_{3}, Z_{4} ≅ Aut(Z_{5}), Z_{2}^{2} ≅ Aut(Z_{8}), Z_{5}, Z_{6} ≅ Aut(Z_{7}), S_{3}.

To be complete, the trivial group Z_{1} can be represented, for example, by the identity functor. On the other hand, the authors don’t know the answer to the following question:

5.3. Problem. Does there exist a group G ≤ S_{κ} such that Q_{8} ≅ N_{S_{κ}}G/G? Can κ be finite? Here Q_{8} denotes the eight element quaternion group.

Group structures. Group structures are used in the constructions both in this, where their role is essential, and the next section.

5.4. Definition. Let G be a subgroup of S_{κ}, X be a set. Mappings h, h′: κ → X are said to be G-equivalent (h ∼_{G} h′), if there exists g ∈ G such that h′ = hg.

5.5. Lemma. The relation ∼_{G} is an equivalence. Let h ∼_{G} h′:κ → X and f:X → Y. Then Im(h) = Im(h′) and fh ∼_{G} fh′.

Proof. Clearly, Im(hg) = Im(h) for a bijection g; and fh′ = fhg, if h′ = hg.

5.6. Definition. A pair ([h]_{∼_{G}}, G), where h:κ → X is called a G-structure on X.

The index ∼_{G} will be omitted, because the equivalence is determined by G.

Construction. Let κ > 2 be a cardinal, G be a subgroup of S_{κ}. We are going to define a functor F:SET → SET .

F X = AX ∐ BX
AX = {R | ∅ ≠ R ⊆ X, |R| < κ}
BX = {([h], G) | h:κ → X, |Im(h)| = κ, ([h], G) is a G-structure on X}

F X is a disjoint union of AX and BX, i.e. F X = AX ×{0}∪BX ×{1}, but the elements of F X will be written without the second component (for example R ∈ F X rather than (R, 0) ∈ F X), since there is no danger of confusion.

For a mapping f:X → Y let

F f(R) = f[R]
F f([h], G) = \{ \begin{matrix}([fh], G) & if |Im(fh)| = κ \\ Im(fh) & otherwise \end{matrix}

5.7. Corollary. F is correctly defined faithful connected set functor.

Proof. The definition is correct: Let f:X → Y be a mapping.

1. Let ∅ ≠ R ⊆ X. Then ∅ ≠ f[R] ⊆ Y, |f[R]| < κ, therefore f[R] ∈ AY.

2. Let ([h], G) be a G-structure on X and |Im(h)| = κ. Then both Im(fh), [fh] don’t depend on the choice of h ∈ [h] (5.5). Either |Im(fh)| = κ or |Im(fh)| < κ. In the first case ([fh], G) ∈ BY. In the second case Im(fh) ∈ AY.

F is a set functor: It should be checked that F preserve identities and composition. It’s clear that F (id_{X}) = id_{F X}. Let f:X → Y, g:Y → Z.

1. Let R ∈ AX. Then F g(F f(R)) = g[f[R]] = gf[R] = F gf(R).

2. Let ([h], G) ∈ BX.

(a) |Im(fh)| = |Im(gfh)| = κ. Then F g(F f([h], G)) = ([gfh], G) = F gf([h], G).

(b) |Im(gfh)| < |Im(fh)| = κ. Then F g(F f([h], G)) = F g([fh, G]) = Im(gfh) = F gf([h], G).

(c) |Im(fh)| < κ. Then |Im(gfh)| < κ and F g(F f([h], G)) = Im(gfh) = F gf([h], G).

Since B1 = ∅ (because κ > 1) and A1 = {1}, the functor F is connected. For the two distinct mappings i_{0}, i_{1} : 1 → 2, i_{0}(0) = 0, we have F i_{0}({0}) = {0} ≠ {1} = F i_{1}({0}), thus F is faithful.

5.8. Corollary. Let R ∈ AX, ([h], G) ∈ BX, U ⊂ X. Then U ∈ Flt(R) iff R ⊆ U; and U ∈ Flt([h], G) iff Im(h) ⊆ U. In particular, F is finitary for a finite κ.

Proof. Let U ∈ Flt(R) an i:U → X be the inclusion. Then there exists some S ∈ AU such that R = F i(S) = S ⊆ U, because for any ([k], G) ∈ BU is |Im(ik)| = |Im(k)| = κ and thus F i([k], G) ∉ AX.

Now let U ∈ Flt([h], G). Clearly there must be ([k], G) ∈ BU for which h ∼_{G} ik. Hence by (5.5) Im(h) = Im(ik) = Im(k) ∈ U.

Proof of Theorems 5.1 and 5.2. We will prove that Nat(F) ≅ N_{S_{κ}}G/G for a finite κ and NatEpi(F) ≅ N_{S_{κ}}G/G for an arbitrary κ. Let μ : F → F be a natural transformation (or epitransformation for infinite κ).

5.9. Claim. For every set X, μ_{X} is identical on AX, i.e. μ_{X}(R) = R for every R ∈ AX.

Proof. Consider Y for which |Y | < κ and thus Y ∈ AY. Then S = μ_{Y} (Y) ∈ AY since BY = ∅. Suppose S ⊂ Y and take a bijective f : Y → Y such that f[S] ≠ S. We have f ∈ Mon(Y), but f ∉ Mon(S) a contradiction to (3.2). Thus μ_{Y} (Y) = Y.

Now, for arbitrary R ∈ AX, we can find Y, |Y | < κ and a mapping f : Y → X such that Im(f) = R. Then μ_{X}(R) = μ_{X}(F f(Y)) = F f(μ_{Y} (Y)) = F f(Y) = R.

5.10. Claim. μ_{κ}([id_{κ}], G) ∈ Bκ.

Proof. Suppose μ_{κ}([id_{κ}], G) = R ∈ Aκ. Since R ⊂ κ (because |R| < κ), we can take f:κ → κ such that |Im(f)| < κ and Im(f) ≠ f[R] since κ > 2. Then F f(μ_{κ}([id_{κ}], G)) = F f(R) = f[R], but μ_{κ}(F f([id_{κ}], G)) = μ_{κ}(Im(f)) = Im(f) (5.9). This contradicts the naturality of μ.

Let ([k], G) = μ_{κ}([id_{κ}], G), where k:κ → κ.

5.11. Claim. k is surjective.

Proof. The proof is similar to that of 5.10: If Im(k) ⊂ κ, we take f : κ → κ such that |Im(f)| < κ and Im(fk) ≠ Im(f). Then F f(μ_{κ}([id_{κ}], G)) = Im(fk) ≠ Im(f) = μ_{κ}(F f([id_{κ}], G)). This is, again, a contradiction with the naturality of μ.

5.12. Claim. μ_{X}([h], G) = ([hk], G) for every ([h], G) ∈ BX.

Proof. We have F h(μ_{κ}([id_{κ}], G)) = F h([k], G) = ([hk], G) (because k is surjective) and μ_{X}(F h([id_{κ}], G)) = μ_{X}([h], G).

5.13. Claim. k ∈ N_{S_{κ}}G. μ is identical, if and only if k ∈ G.

Proof. First, k is injective: For a finite κ, it is clear (because k is surjective). For infinite κ, suppose the contrary. Then hk ≁_{G} id_{κ} for any h: κ → κ (because hk is not injective). This contradicts the assumption that μ is an epitransformation. Hence k is bijective (5.11).

k ∈ N_{S_{κ}}G: For every g ∈ G, we have g ∼_{G} id_{κ} and therefore gk ∼_{G} k, because ([k], G) = μ_{κ}([id_{κ}], G) = μ_{κ}([g], G)) = ([gk], G) (5.12). Thus, there exists g′ ∈ G such that gk = kg′. This implies k^{−1}gk ∈ G for every g ∈ G, hence k ∈ N_{S_{κ}}G.

If μ is identical, then in particular ([k], G) = μ_{κ}([id_{κ}], G) = ([id_{κ}], G), thus k ∈ G. Conversely, if k ∈ G, then hk ∼_{G} h for every ([h], G) ∈ BX.

We have just proved that every (epi)transformation is of the form μ^{k} for some k ∈ N_{S_{κ}}G, where

μ^{k}(R) = R
μ^{k}([h], G) = ([hk], G)

On the other hand, for every k ∈ N_{S_{κ}}, μ^{k} is defined correctly (independent of the choice of h) and it is a natural transformation of F : Let f:X → Y be a mapping.

1. R ∈ AX. Then F f(μ_{X}^{k}(R)) = f[R] = μ_{Y}^{k} (F f(R)).

2. ([h], G) ∈ BX.

(a) |Im(fh)| < κ. Then F f(μ_{X}^{k}([h], G)) = Im(fhk) = Im(fh) = μ_{Y}^{k} (F f([h], G).

(b) |Im(fh)| = κ. Then F f(μ_{X}^{k}([h], G)) = ([fhk], G) = μ_{Y}^{k} (F f([h], G)).

5.14. Claim. The mapping i: N_{S_{κ}}G → Nat(F) (resp. i: N_{S_{κ}}G → NatEpi(F) for infinite κ) sending k to μ^{k^{−1}} is a group epimorphism, Ker(i) = G.

Proof. It is obvious that μ^{k^{′−1}} ∘ μ^{k^{−1}} = μ^{(k′k)^{−1}}, hence i is a grupoid homomorphism. The rest follows from 5.13.

Now, the proof of 5.1 and 5.2 is complete.

The following propositions are surely well known facts from the group theory. Therefore the proofs will be just outlined.

5.15. Proposition. Let G = (κ, ·) be a group and l : G → S_{κ} its left regular representation, let G′ := Im(l). Then N_{S_{κ}}G′/G′ ≅ Aut(G).

Proof. The largest group containing the regular group G′ as a normal subgroup is the holomorph of G, i.e. subdirect product of G and Aut(G). Viewing Aut(G) as a subgroup of S_{κ}, this is simply Aut(G)G′.

5.16. Proposition. Let κ be a finite cardinal. Let G, G′, l be as in 5.15. Let H be a normal subgroup of Aut(G) such that |H| and |G| = κ are co-prime numbers. Let K := G′H. Then K is a group and N_{S_{κ}}K/K ≅ Aut(G)/H.

Proof. Clearly K is normal subgroup of Aut(G)G′. On the other hand, every inner automorphism of S_{κ} which fixes K fixes G′ too, because G′ contains exactly these elements of K, whose rank divides κ. Hence N_{S_{κ}}(K)/K = N_{S_{κ}}(G′)/K = Aut(G)G′/HG′ ≅ Aut(G)/H.

Let G = Z_{p^{n}}, where p is an odd prime number and a n is a natural number. Then Aut(G) ≅ Z_{(p−1)p^{n−1}}. Let H be the subgroup of Aut(G) of order p − 1. The proposition 5.16 gives us a representation of Aut(G)/H = Z_{p^{n−1}}.

6. Second construction – main result

In this section, we prove the following:

6.1. Theorem. Let G be a group of order at least 7. Then there exists a set functor F such that Nat(F) ≅ G. If G is of a finite order, then F is finitary.

Groups of order less then 7 were represented in the previous section.

Let κ be a cardinal, κ ≥ 7 and G = (κ, ·) be a group.

Key proposition. Given an equivalence ∼ on some subset of P κ, let us denote

G_{∼} := {p | p:κ → κ is a bijection, R ∼ p[R] for all R where ∼ is defined }.

It’s clear that G_{∼} is a subgroup of S_{κ}.

6.2. Proposition. There exists an equivalence ∼ on κ^{[2,3]} such that G ≅ G_{∼}. Here κ^{[2,3]} denotes the set of all two and all three point subsets of κ.

Let l_{g} denote the left translation l_{g}:G → G, l_{g}(h) = gh. For R, S ∈ G^{[2,3]} let

R ∼ S iff S = l_{g}[R].

We are going to prove that G_{∼} = {l_{g} | g ∈ G}, then G ≅ G_{∼} follows.

It is clear that l_{g} ∈ G_{∼} for every g ∈ G. For the second inclusion, it suffices to prove that if p ∈ G_{∼}, p(1) = 1 (1 is the unit element of G), then p = id_{κ}: If q ∈ G_{∼}, then l_{q(1)^{−1}} ∘ q(1) = 1 and we will have l_{q(1)^{−1}} ∘ q = id_{κ}, thus q = l_{q(1)}.

Let 1 ≠ g ∈ G. If {1, g} ∼ {1, h}, then clearly h = g or h = g^{−1}. Thus either p(g) = g, or p(g) = g^{−1}, p(g^{−1}) = g, hence p consists only of fix points and transpositions. Suppose that p contains a transposition.

(1) Let p = (1)(g g^{−1})(h) … (this means that 1, g, g^{−1}, h are pairwise distinct, p(h) = h, p(g) = g^{−1}, p(g^{−1}) = g). We prove that g^{4} = 1, h = g^{2}(= g^{−2}). Because {1, g, h} ∼ {1, g^{−1}, h}, there exists a ∈ G such that {a, ag, ah} = {1, g^{−1}, h}. We have three possibilities a = 1, ag = 1, ah = 1.

(a) a = 1 … then g = g^{−1} a contradiction.

(b) a = g^{−1} … {g^{−1}, 1, g^{−1}h} = {1, g^{−1}, h}. Then g^{−1}h = h, hence g = 1, a contradiction.

(c) a = h^{−1} … {h^{−1}, h^{−1}g, 1} = {1, g^{−1}, h}. Then h^{−1} = h and h^{−1}g = g^{−1} (it is not possible that h^{−1} = g^{−1}) and we have h = g^{2}, h^{2} = 1.

(2) Let p = (1)(g g^{−1})(h h^{−1}). We prove that g^{5} = h^{5} = 1, {g^{2}, g^{−2}} = {h, h^{−1}}. Because {1, g, h} ∼ {1, g^{−1}, h^{−1}}, there exists a ∈ G such that {a, ag, ah} = {1, g^{−1}, h^{−1}}. There are three possibilities:

(a) a = 1 … {g, h} = {g^{−1}, h^{−1}}. Either g = g^{−1} or g = h^{−1}, a contradiction.

(b) a = g^{−1} … g^{−1}h = h^{−1}, hence g = h^{2}.

(c) a = h^{−1} … h^{−1}g = g^{−1}, hence h = g^{2}.

Without lost of generality, assume h = g^{2}. Because {g, g^{−1}, h} ∼ {g, g^{−1}, h^{−1}}, there exists a ∈ G such that {ag, ag^{−1}, ag^{2}} = {g, g^{−1}, g^{−2}}.

(a) a = 1 … g^{2} = g^{−2}. Then h^{−1} = g^{−2} = g^{2} = h, a contradiction.

(b) a = g^{−2} … {g^{−3}, 1} = {g, g^{−2}}. Either 1 = g, or 1 = g^{−2}, a contradiction.

(c) a = g^{−3} … g^{−4} = g. Then g^{5} = 1.

Together g^{5} = 1 and h = g^{2}.

From (1) it follows that there is at most one fix point other than 1. From (2) it follows that there are at most two distinct transpositions. This contradicts |G| ≥ 7. In fact, this works also for |G| = 6.

r-structures and s-structures. In the construction, we will need two equivalences – an equivalence ≈ on P κ such that G_{≈} ≅ G and an equivalence on P λ (λ is a cardinal) with some properties. It will be more convenient to work with the quotient mappings rather then with the equivalences.

6.3. Lemma. There exist a set E, a cardinal λ > κ + κ (finite for finite κ) and mappings q:P κ → E, r:P λ → E with the following properties:

(Q1) G ≅ G_{q} = {k | k:κ → κ a bijection, (∀R ⊆ κ) q(k[R]) = q(R)}

(Q2) q(∅) ≠ q(R), if ∅ ≠ R ⊆ κ

(Q3) q(κ) ≠ q(R), if R ⊂ κ (Q4) q(R) ≠ q(S), if |R| = 1, |S| > 1, |κ − S| > 1

(R1) r is onto E

(R2) r(∅) = r(R), iff |R| ≤ 1

(R3) r(R) = r(b[R]), if R ⊆ λ, b:λ → λ is a bijection

(R4) If r(R) = r(S), then r(λ − R) = r(λ − S) for every R, S ⊆ λ

(QR1) q(∅) = r(∅), q(κ) = r(λ)

(QR2) If q(R) = r(S), then q(κ − R) = r(λ − S), where R ⊆ κ, S ⊆ λ

(QR3) If q(R) = r(S), where |R| = 1, then either |S| = 2 or |λ − S| = 2

Proof. Let ∼ be the equivalence from 6.2. We enumerate the set (κ^{[2,3]}/ ∼) by ordinals greater than three and add four elements:

E := (κ^{[2,3]}/ ∼) ∪ {e_{0}, e_{1}, e_{2}, e_{3}} = {e_{i} | i ∈ α}.

Let q:P κ → E be the mapping

q(R) = \{ \begin{matrix}e_{0} & if R = ∅ \\ e_{1} & if R = κ \\ e_{2} & if |R| = 1 or |κ − R| = 1 \\ [R]_{∼} & if |R| ∈ \{2, 3\} \\ [κ − R]_{∼} & if |κ − R| ∈ \{2, 3\} \\ e_{3} & otherwise, \end{matrix}

where R ⊆ κ. The definition of q is clearly correct (the cases are disjoint for κ ≥ 7) and G_{q} = G_{∼} ≅ G.

Let λ_{i} denote the i-th cardinal number (i.e. λ_{0} = 0, λ_{1} = 1, …). Let λ > λ_{2·α}, λ > κ + κ be a cardinal (resp. a finite cardinal for finite κ). We define r: P λ → E as follows:

r(R) = \{ \begin{matrix}e_{0} & if |R| ≤ 1 \\ e_{1} & if |λ − R| ≤ 1 \\ e_{i} & if |R| = λ_{i} or |λ − R| = λ_{i}, where 2 ≤ i < α \\ e_{3} & otherwise, \end{matrix}

where R ⊆ λ. It is easy to see that all required properties are satisfied.

6.4. Definition. Let X be a set, s : P X → E be a mapping. We say that s is a q-structure on X, if there exists a mapping f : κ → X such that |Im(f)| < κ and s = qf^{−1}.

We say that s is an r-structure on X, if there exists a mapping f:λ → X such that |Im(f)| < λ and s = rf^{−1}.

6.5. Lemma. Let rf^{−1} be an r-structure on X and g : λ → λ be a bijection. Then rf^{−1} = rg^{−1}f^{−1}.

Proof. It is an easy consequence of (R3).

6.6. Lemma. q is neither a q-structure nor an r-structure.

Proof. q is not a q-structure: If f:κ → κ is a mapping with R = Im(f), |R| < κ, then qf^{−1}[R] = q(κ) ≠ q(R) (Q3).

q is not an r-structure: Suppose that f : λ → κ is a mapping such that rf^{−1} = q. For a ∈ κ, put I_{a} := f^{−1}[{a}]. Either |I_{a}| = 2 or |λ − I_{a}| = 2 for every a ∈ κ (because r(I_{a}) = q({a}) and (QR3)). If the second possibility occurs for some a ∈ κ neither of the possibilities can hold for the rest of κ because κ > 2. Thus {I_{a} | a ∈ κ} is a partition of λ to κ two-point sets, which is impossible, since λ > κ + κ.

The r-structures on 2 are in one-to-one correspondence with elements of E:

6.7. Lemma. Let R, S ⊆ λ. Then rχ_{R,λ}^{−1} = rχ_{S,λ}^{−1} iff r(R) = r(S).

Proof. For every T ⊆ λ, we have rχ_{T,λ}^{−1}[∅] = r(∅), rχ_{T,λ}^{−1}[{0, 1}] = r(λ), rχ_{T,λ}^{−1}[{0}] = r(λ − T), rχ_{T,λ}^{−1}[{1}] = r(T). Thus, by (R4) rχ_{R,λ}^{−1} = rχ_{S,λ}^{−1} iff r(R) = r(S).

6.8. Lemma. Every q-structure on 2 is an r-structure.

Proof. Every mapping f:κ → 2 is a characteristic mapping of some R ⊆ κ. Let S ⊆ λ be such that r(S) = q(R) (it exists due to (R1)). Then qχ_{R,κ}^{−1} = rχ_{S,λ}^{−1}: qχ_{R,X}^{−1}[∅] = q(∅) = r(∅) = rχ_{S,X}^{−1}[∅] (due to (QR1)), qχ_{R,X}^{−1}[{0, 1}] = q(κ) = r(λ) = rχ_{S,λ}^{−1}[{0, 1}] (QR1), qχ_{R,X}^{−1}[{1}] = q(R) = r(S) = rχ_{S,λ}^{−1}[{1}], and finally qχ_{R,X}^{−1}[{0}] = q(κ − R) = r(λ − S) = rχ_{S,λ}^{−1}[{0}] (QR2).

The converse (ie. every r-structure on 2 is a q-structure) is also true, but we will not need this fact (except for the motivation below the construction).

Construction. For a set X, we define

F X = AX ∐ BX ∐ CX
AX = {s | s is a q-structure or an r-structure on X}
BX = {h | h:κ → X, |Im(h)| = κ}
CX = {([h], S_{λ}) | h:λ → X, |Im(h)| = λ, ([h], S_{λ}) is a S_{λ}-structure}

Again, the elements of the coproduct will be written without the second component. For a mapping f:X → Y, put

F f(s) = sf^{−1}
F f(h) = \{ \begin{matrix}fh & if |Im(fh)| = κ \\ qh^{−1}f^{−1} & otherwise \end{matrix}
F f([h], S_{λ}) = \{ \begin{matrix}([fh], S_{λ}) & if |Im(fh)| = λ \\ rh^{−1}f^{−1} & otherwise \end{matrix}

Before we start to prove Theorem 6.1, let us try to explain the roles of the components to give the reader better insight into the construction.

The ”most important” parts of the functor F are A2 and Bκ: We have proved (in 6.7, 6.8) that r-structures (and q-structures) on 2 are in one-to-one correspondence with the elements of E (i.e. with equivalence classes of Ker(q) and Ker(r)). Let μ be an endotransformation of F such that μ_{2} = id_{F 2} and μ_{κ}(id_{κ}) = k, where k:κ → κ ∈ Bκ is a bijection. Let R be a subset of κ. The naturality of μ for the element id_{κ} ∈ Bκ gives us

μ_{2}(F χ_{R,κ}(id_{κ})) = F χ_{R,κ}(μ_{κ}(id_{κ})).

The left side equals qχ_{R,κ}^{−1} which corresponds to q(R) under the correspondence mentioned above. The right side equals qχ_{k^{−1}[R],κ}^{−1} which corresponds to q(k^{−1}[R]). We see that k must be in the group G_{q}. The component B and q-structures are there to make a set endofunctor from this idea. The component C and r-structures are used to ensure that every natural transformation is an equivalence and that μ_{2} is the identity.

6.9. Corollary. F is correctly defined faithful connected set functor.

Proof. The definition is correct: Let f:X → Y be a mapping.

1. Let s be a q-structure, i.e. s = qg^{−1} for some g : κ → 2, |Im(g)| < κ. Then |Im(fg)| < κ and qg^{−1}f^{−1} = q(fg)^{−1} is a q-structure. The argument for r-structures is analogical.

2. Let h be a mapping such that |Im(h)| = κ. Either |Im(fh)| = κ hence F f(h) = fh ∈ BY, or |Im(fh)| < κ hence F f(h) = qh^{−1}f^{−1} ∈ AY.

3. Let ([h], S_{λ}) be a S_{λ}-structure, |Im(h)| = λ. Then Im(fh), [fh], rh^{−1}f^{−1} do not depend on the choice of h ∈ [h] (5.5, 6.5). Either |Im(fh)| = λ or |Im(fh)| < λ. In the first case ([fh], S_{λ}) ∈ CY. In the second case rh^{−1}f^{−1} ∈ AY.

F is a set functor: It should be checked that F preserve identities and composition. It’s clear that F (id_{X}) = id_{F X}. Let f:X → Y, g:Y → Z be mappings.

1. Let s be a s-structure or an r-structure. Then F g(F f(x)) = sf^{−1}g^{−1} = s(gf)^{−1} = F gf(x).

2. Let h be a mapping h:κ → X.

(a) |Im(fh)| = κ, |Im(gfh)| = κ. Then F g(F f(x)) = gfh = F gf(x).

(b) |Im(fh)| = κ, |Im(gfh)| < κ. Then F g(F f(x)) = F g(fh) = qh^{−1}f^{−1}g^{−1} = F gf(x).

(c) |Im(fh)| < κ. Then |Im(gfh)| < κ and F g(F f(x)) = F g(qh^{−1}f^{−1}) = qh^{−1}f^{−1}g^{−1} = F gf(x).

3. Let ([h], S_{λ}) be a S_{λ}-structure. The proof is similar to that of 2.

Let c_{κ}: κ → 1 and c_{λ}: λ → 1 be the unique mappings. Since qc_{κ}^{−1} = rc_{λ}^{−1} (the value at ∅ is q(∅) = r(∅) (QR1), the value at {0} is q(κ) = r(λ) (QR1)) and B1 = C1 = ∅ (κ, λ > 1), the functor F is connected.

For the two distinct mappings i_{0}, i_{1} :1 → 2, i_{0}(0) = 0, we have F i_{0}(rc_{κ}^{−1}) = rc_{λ}^{−1}i_{0}^{−1} = rχ_{∅,λ}^{−1} ≠ rχ_{λ,λ}^{−1} = rc_{λ}^{−1}i_{1}^{−1} = F i_{1}(rc^{−1}_{λ})), because r(λ) ≠ r(∅) ((QR1), (Q3), 6.7). Thus F is faithful.

6.10. Corollary. f[κ] ∈ Flt(qf^{−1}), f[λ] ∈ Flt(rf^{−1}); S ∈ Flt(h) iff Im(h) ⊆ S; S ∈ Flt([h], S_{λ}) iff Im(h) ⊆ S. In particular, if κ is finite, then F is finitary.

Proof. Let i: f[κ] → X be the inclusion and f′: κ → f[κ] the restriction of f to the image. Then clearly qf^{−1} = qf^{′−1}i^{−1} = F i(qf′). Similarly for an r-structure rf^{−1} and a mapping h. The last two statements can be proved in the same way as (5.8).

Proof of Theorem 6.1. We will show that Nat(F) ≅ G_{q}. Similarly as in the proof of 5.1, 5.2, we will show in series of claims, that every natural transformation μ: F → F is of the form μ^{k}, where k is a bijection, k ∈ G_{q} (see the end of the proof for the definition of μ^{k}). This will provide us an isomorphism i:G_{q} → Nat(F).

So, let μ:F → F be a natural transformation.

6.11. Claim. Let R ⊆ λ, |R| ≤ 1. Then μ_{2}(rχ_{R,λ}^{−1}) = rχ_{R,λ}^{−1}.

Proof. We have observed in the proof of 6.9 that F i_{0}(x) = rχ_{∅,λ}^{−1} for the point x ∈ F 1 and the mapping i_{0} :1 → 2, i_{0}(0) = 0. Since rχ_{R,λ}^{−1} = rχ_{∅,λ}^{−1} ((R2) and 6.7), the statement follows from 3.3.

6.12. Claim. μ_{λ}([id_{λ}], S_{λ}) = ([id_{λ}], S_{λ}).

Proof. Every bijective f:λ → λ is in the monoid of ([id_{λ}], S_{λ}), therefore is in the monoid of μ_{λ}([id_{λ}], S_{λ}) (3.2.2). Thus, if S ∈ Flt(μ_{λ}([id_{λ}], S_{λ})), then f[S] ∩ S ∈ Flt(μ_{λ}([id_{λ}], S_{λ})) (3.1). If |S| < λ we can find either a bijection f such that f[S] ∩ S = ∅ or, for finite λ, a finite sequence of bijections f_{1}, …, f_{n} satisfying f_{1}[S] ∩ … ∩ f_{n}[S] ∩ S = ∅, both cases leading to a contradiction. Hence by (6.10) μ_{λ}([id_{λ}, S_{λ}]) = ([h], S_{λ}) ∈ C_{λ} and the same argument as in (5.11) gives us that h is a surjection.

Now since every bijection is equivalent to id_{λ} modulo ∼_{S_{λ}}, it suffices to show that h is injective. If not, let a ∈ λ be such that |h^{−1}[{a}] > 1. From the naturality of μ, μ_{2}(F χ_{{a},λ}([id_{λ}, S_{λ}])) = μ_{2}(rχ_{{a},λ}^{−1}) = rχ_{{a},λ}^{−1} (6.11) should be equal to

F χ_{{a},λ}(μ_{λ}([id_{λ}, S_{λ}])) = F χ_{{a},λ}([h, S_{λ}]) = rh^{−1}χ_{{a},λ}^{−1} = rχ_{h^{−1}[{a}],λ}^{−1},

a contradiction (6.7), (R2).

6.13. Claim. μ_{X} is identical on AX ∪ CX, in particular μ_{2} = id_{F 2}.

Proof. μ_{X} is identical on CX and r-structures: Let h:λ → X be a mapping such that |Im(h)| = λ. Then μ_{X}([h], S_{λ}) = μ_{X}(F h([id_{λ}], S_{λ})) = F h(μ_{λ}([id_{λ}], S_{λ})) = F h([id_{λ}], S_{λ}) = ([h], S_{λ}). For a mapping h: λ → X such that |Im(h)| < λ, the same computation gives μ_{X}(s) = s for every r-structure s on X.

μ_{2} = id_{F 2}: Let x ∈ F 2. B2 = ∅ and C2 = ∅, because κ, λ > 2. Hence x ∈ A2. But every q-structure on 2 is an r-structure (6.8).

μ_{X} is identical on AX: Let s be a q-structure. The filter of s contains a set of cardinality less than κ (6.10), hence the filter of μ_{X}(s) contains a set of cardinality less than κ (3.2.1). Thus μ_{X}(s) is a q-structure or an r-structure (6.10 again). For every f : X → 2, we have μ_{2}(F f(s)) = μ_{2}(sf^{−1}) = sf^{−1} (we have used μ_{2} = id_{F 2}) and F f(μ_{X}(s)) = (μ_{X}(s))f^{−1}. Putting f = χ_{R,X} and computing the value of sf^{−1} and (μ_{X}(s))f^{−1} in {1}, we obtain s(R) = (μ_{X}(s))(R) for every R ⊆ X.

6.14. Claim. μ_{κ}(id_{κ}) ∈ Bκ.

Proof. If μ_{κ}(id_{κ}) = s is a q-structure or r-structure, then F f(μ_{κ}(id_{κ})) = sf^{−1} and μ_{2}(F f(id_{κ})) = μ_{2}(qf^{−1}) = qf^{−1} for every f:κ → 2. Thus s = q (see the end of the proof of 6.13 for details), but q is neither q-structure not r-structure (6.6), a contradiction.

If μ_{κ}(id_{κ}) = ([h], S_{λ}) is a S_{λ}-structure, then κ ∈ Flt(id_{κ}), but κ ∉ Flt([h], S_{λ})) (6.10). This contradicts 3.2.1.

Let k = μ_{κ}(id_{κ}), where k:κ → κ, |Im(κ)| = κ.

6.15. Claim. μ_{X}(h) = hk for every h ∈ BX, k ∈ G_{q}.

Proof. μ_{X}(h) = hk: μ_{X}(h) = μ_{X}(F h(id_{κ})) = F h(μ_{κ}(id_{κ}) = F h(k) = hk.

For arbitrary f:κ → 2, we have qk^{−1}f^{−1} = F fk(id_{κ}) = F f(μ_{κ}(id_{κ})) = μ_{2}(F f(id_{κ})) = F f(id_{κ}) = qf^{−1} hence q = qk^{−1} (6.13).

Now, it suffices to prove that k is bijective, then clearly k ∈ G_{q}.

If k is not surjective, then there exists R ⊆ κ such that |R| = 1, k^{−1}[R] = ∅. But q(R) ≠ q(k^{−1}[R]) (Q2) a contradiction.

If k is not injective, then there exists R ⊆ κ such that |R| = 1 and |k^{−1}[R]| > 1. Then clearly |κ − k^{−1}[R]| > 1 (because k is surjective and κ > 2). But q(R) ≠ q(k^{−1}[R]) (Q4), a contradiction.

We have just proved that every natural transformation is of the form μ^{k} for some k ∈ G_{q}, where

μ^{k}(s) = s
μ^{k}([h], S_{λ}) = ([h], S_{λ})
μ^{k}(h) = hk

On the other hand, this is a natural transformation of F for every k ∈ G_{κ}:

Let f:X → Y be a mapping.

1. x ∈ AX ∪ CX. Then also F f(x) ∈ AY ∪ CY and there is nothing to verify.

2. ([h], G) ∈ BX.

(a) |Im(fh)| < κ. Then F f(μ_{X}^{k}(h)) = qk^{−1}f^{−1} = qf^{−1} = μ_{Y}^{k} (F f(h)), because q = qk^{−1} for every k ∈ G_{q}.

(b) |Im(fh)| = κ. Then F f(μ_{X}^{k}(h)) = fhk = μ_{Y}^{k} (F f(h)).

6.16. Claim. The mapping i:G_{q} → Nat(F) sending k to μ^{k^{−1}} is a group isomorphism.

This finishes the proof of 6.1.

6.17. Remark. The assumption κ ≥ 7 is not essential in this construction. The key proposition 6.2 can be improved to cover the small cases. The reasons to include the first construction were:

• It answered the first question that the authors considered: Is it possible to represent Z_{3}?

• The proof of 5.1 and 5.2 is easier and contains some methods, which are used in the proof that the second construction (more involved) works.

• It is based on the observation, how the monoids of points of a set functor F affect the monoid Nat(F). It could be useful, when one wants to compute the monoid Nat(F) for a given set functor F.

References

[1] A. Barkhudaryan, R. El Bashir, and V. Trnková. Endofunctors of Set. in: Proceedings of the Conference Categorical Methods in Algebra and Topology, Bremen 2000, eds: H. Herrlich and H.-E. Porst, Mathematik-Arbeitspapiere, 54:47–55, 2000.

[2] A. Barkhudaryan, R. El Bashir, and V. Trnková. Endofunctors of Set and cardinalities. Cahiers Topo. Geom. Diff. Cat., 44-3:217–239, 2003.

[3] G. Birkhoff. On the groups of automorphisms. Revista Unió Mat. Argentina, 11:155– 157, 1946. In Spanish.

[4] J. de Groot. Groups represented by homeomorphism groups. Math. Ann., 138:80– 102, 1959.

[5] M. Funk, O. H. Kegel, and K. Strambach. Gruppenuniversalität und homogenisierbarkeits. Ann. Math. Pura Appl., 141:1–126, 1985.

[6] V. Koubek. Set functors. Comment. Math. Univ. Carolinae, 12:175–195, 1971.

[7] V. Koubek. Set functors II - contravariant case. Comment. Math. Univ. Carolinae, 14:47–59, 1973.

[8] V. Koubek and J. Reiterman. Set functors III - monomorphisms, epimorphisms, isomorphisms. Comment. Math. Univ. Carolinae, 14:441–455, 1973.

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

[10] Y. T. Rhineghost. The functor that wouldn’t be - a contribution to the theory of things that fail to exist. in: Categorical Perspectives, Birkhauser-Verlag, Trends in Mathematics, pages 29–36, 2001.

[11] Y. T. Rhineghost. The emergence of functors - a continuation of ”the functor that wouldn’t be”. in: Categorical Perspectives, Birkhauser-Verlag, Trends in Mathematics, pages 37–46, 2001.

[12] V. Trnková. Some properties of set functors. Comment. Math. Univ. Carolinae, 10:323–352, 1969.

[13] V. Trnková. On descriptive classification of set functors I. Comment. Math. Univ. Carolinae, 12:143–175, 1971.

[14] V. Trnková. On descriptive classification of set functors II. Comment. Math. Univ. Carolinae, 12:345–357, 1971.

Mathematical Institute of Charles University Sokolovská 83, Praha 8, 18675 Czech Republic

Email: barto@karlin.mff.cuni.cz
  pzim8157@artax.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/14/13/14-13.{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.

Information for authors. The typesetting language of the journal is TEX, and L^{A}TEX 2ε 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.

Managing editor. Robert Rosebrugh, Mount Allison University: rrosebrugh@mta.ca

TEXnical editor. Michael Barr, McGill University: mbarr@barrs.org

Transmitting editors.

Richard Blute, Université d’ Ottawa: rblute@mathstat.uottawa.ca 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: aurelio.carboni@uninsubria.it Valeria de Paiva, Xerox Palo Alto Research Center: paiva@parc.xerox.com

Ezra Getzler, Northwestern University: getzler(at)math(dot)northwestern(dot)edu

Martin Hyland, University of Cambridge: M.Hyland@dpmms.cam.ac.uk 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 Stephen Lack, University of Western Sydney: s.lack@uws.edu.au 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 Jiri Rosicky, Masaryk University: rosicky@math.muni.cz Brooke Shipley, University of Illinois at Chicago: bshipley@math.uic.edu 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: robert.walters@uninsubria.it R. J. Wood, Dalhousie University: rjwood@mathstat.dal.ca