Theory and Applications of Categories, Vol. 16, No. 32, 2006, pp. 923–956.

COPOWER OBJECTS AND THEIR APPLICATIONS TO FINITENESS IN TOPOI

TOBY KENNEY

Abstract. In this paper, we examine a new approach to topos theory – rather than considering subobjects, look at quotients. This leads to the notion of a copower object, which is the object of quotients of a given object. We study some properties of copower objects, many of which are similar to the properties of a power objects. Given enough categorical structure (i.e. in a pretopos) it is possible to get power objects from copower objects, and vice versa.

We then examine some new definitions of finiteness arising from the notion of a copower object. We will see that the most naturally occurring such notions are equivalent to the standard notions, K-finiteness (at least for well-pointed objects) and K̃-finiteness, but that this new way of looking at them gives new information, and in fact gives rise to another notion of finiteness, which is related to the classical notion of an amorphous set — i.e. an infinite set that is not the disjoint union of two infinite sets.

Finally, We look briefly at two similar notions: potency objects and per objects.

Acknowledgements

This research was funded by EPSRC. I would like to thank my PhD. supervisor, Peter Johnstone, and the anonymous referee for a lot of helpful suggestions.

1. Introduction and Background

The standard definition of an (elementary) topos is based on power objects. A power object is the object that classifies subobjects of a fixed object. A natural question to ask is whether the definition in terms of power objects is the only reasonable way to approach elementary topos theory, or whether things like an object that classifies the quotient objects of a fixed object can be used to define an elementary topos. This would mean that in proofs in a general topos, the use of power objects could be replaced by these copower objects. However, it seems likely that while there are many things that are better understood using the standard power object based methods, the fact that copower objects have the same expressive power means that there should also be some things that can be better understood in terms of copower objects, so hopefully a study of copower objects and the best ways to use them will lead to new insights in a variety of areas.

Received by the editors 2005-09-15 and, in revised form, 2006-12-03. Transmitted by Ieke Moerdijk. Published on 2006-12-08. 2000 Mathematics Subject Classification: 03G30, 18B25. Key words and phrases: Topoi, Finiteness, Copower objects. \begin{matrix}c \\ ◯ \end{matrix} Toby Kenney, 2006. Permission to copy for private use granted.

In Section 2, we show that while copower objects do not produce as simple a definition of a topos, for a pretopos (a coherent category in which all equivalence relations occur as kernel pairs and in which there are disjoint coproducts), the existence of copower objects is equivalent to the existence of power objects. We also prove some simple properties of copower objects that are similar to useful properties of power objects. To express some of the results in this section in full generality, we will need the notion of a quasitopos:

1.1. Definition. [J. Penon] A weak subobject classifier is the codomain of a morphism from 1 of which every strong monomorphism (morphism that doesn’t factor through an epi) is a pullback along a unique morphism. A quasitopos is a locally cartesian closed cocartesian (i.e. having all finite colimits) category with a weak subobject classifier.

As any topos is a quasitopos, the reader unfamiliar with quasitopoi may simply read “topos” instead of “quasitopos” wherever it occurs.

Also, for Proposition 2.12, we will need to recall the definitions of the closed subtopos complementary to a given subterminal object U of E, denoted, Sh_{c(U)}(E), and an internally widespread subterminal object.

The objects of Sh_{c(U)}(E) (called c(U)-sheaves) are objects X of E such that X×U ≅ U. For example, if E is the topos of sheaves on a topological space or locale X, then a subterminal object U in E will correspond to an open subspace or sublocale of X. The subtopos Sh_{c(U)}(E) will then be equivalent to the topos of sheaves on the complement of U, with the topology that a subset of this complement is open if its union with U is open in X.

A subterminal object U is called internally widespread if the subtopos Sh_{c(U)}(E) is boolean — i.e. all its subobject lattices have complements. For example, in sheaves on a 3-point topological space {0, 1, 2} whose open sets are exactly those that contain 0, the subterminal object corresponding to {0} is internally widespread, since the topology induced on its complement is discrete.

If the reader is unfamiliar with these concepts, Proposition 2.12 is not important in the rest of the paper. I believe that there should be an easier proof of the result, not involving power objects.

In Section 3, we examine the partial order on copower objects. We show that they are in fact lattices. In the topos of sets, these lattices have already been studied. In this context they are called partition lattices, with copower objects being viewed as sets of equivalence relations, rather than quotients. (The order on them is by inclusion of equivalence relations, which is the opposite of the order we consider in this section, since smaller equivalence relations lead to larger quotients). One reason for their importance is a theorem of P. M. Whitman [7] that any lattice can be embedded in a partition lattice.

Whitman’s proof of this result is fairly long and complicated. The main ideas are as follows:

1. For each element x in the lattice that we wish to embed, we take some set S_{x} with elements l(x) and r(x), so that we will embed our lattice in the partition lattice of the disjoint union of the S_{x}, in such a way that the equivalence relation corresponding to y will relate l(x) and r(x) if and only if x ⩽ y. This will ensure that the map is injective.

COPOWER OBJECTS AND THEIR APPLICATIONS TO FINITENESS IN TOPOI 925

2. The problem with this is that we might have y_{1} and y_{2} such that x ⩽ y_{1} ∨ y_{2} but neither x ⩽ y_{1} nor x ⩽ y_{2}. Therefore, we need to do something to force the join of the equivalence relations corresponding to y_{1} and y_{2} to relate l(x) and r(x). To achieve this, we introduce some extra points p_{1}(y_{1}, y_{2}), …, p_{5}(y_{1}, y_{2}) to S_{x}, for every pair of points y_{1}, y_{2} such that x ⩽ y_{1} ∨ y_{2}, with the idea that the equivalence relation corresponding to y_{1} should relate l(x) to p_{1}(y_{1}, y_{2}), p_{2}(y_{1}, y_{2}) to p_{3}(y_{1}, y_{2}), and p_{4}(y_{1}, y_{2}) to p_{5}(y_{1}, y_{2}), while the equivalence relation corresponding to y_{2} should relate p_{1}(y_{1}, y_{2}) to p_{2}(y_{1}, y_{2}), p_{3}(y_{1}, y_{2}) to p_{4}(y_{1}, y_{2}) and p_{5}(y_{1}, y_{2}) to r(x). (Introducing 5 new points rather than just one is necessary in order to get both joins and meets to work.)

3. This still leaves the problem that if y_{1} ⩽ z_{1} ∨ z_{2}, while neither y_{1} ⩽ z_{1} nor y_{1} ⩽ z_{2} holds, we need to ensure that the join of the equivalence relations corresponding to z_{1} and z_{2} should relate l(x) to p_{1}(y_{1}, y_{2}), and the other pairs of elements that we required to be related above. To achieve this, we introduce more points between them – indeed we eventually want to introduce a copy of S_{y_{1}} between them. We do this iteratively; at each stage, adding a copy of what we currently have in S_{y_{1}} between them. Then we take the union of all the iterations.

Each element of S_{x}, apart from r(x) can be viewed as a list of pairs of elements of the lattice, with a natural number from 1 to 5, indicating to which of the p_{i} the element corresponds. (l(x) corresponds to the empty list.) This construction can be implemented in any topos with a natural numbers object (see Example 1.7 for a recap of the definition of a natural numbers object). Therefore, Whitman’s theorem should hold in any such topos.

It has also been proved in the topos of finite sets by P. Pudlák and J. Tůma [5]. It would be interesting to determine whether Whitman’s theorem actually holds in any topos, but I suspect that this would be hard to prove, since the finite case was an open problem for 30 years, and a proof for a general topos would almost certainly give a new proof of the finite case.

1.2. Remark. For distributive lattices, things are much easier: If L is distributive, then

the morphism L [figure: f] QL, sending a to R_{a} given by bR_{a}c ⇔ (b ∨ a = c ∨ a) is a lattice embedding, so any distributive lattice embeds in its own partition lattice in an arbitrary topos.

Another relevant result: in [3], G. Grätzer and E. T. Schmidt show that every compactly generated lattice in \underline{Set} is the lattice of global sections of a copower object in [M, \underline{Set}] for some monoid M. (They use the terms unary algebra for a functor in [M, \underline{Set}], and lattice of congruences for the lattice of global sections of its copower object.) Again, this proof requires a natural number object, but other than that, should be able to be done in an arbitrary topos.

In Section 4 we look at one possible application of copower objects in the study of finiteness in topoi. Classically, there are many different definitions of finiteness, all of which give rise to the same concept. Constructively, these definitions give rise to different types of finiteness. In some cases, two different definitions of finiteness are only equivalent if the axiom of choice holds. These different definitions of finiteness are useful in different cases – some results hold for one definition of finiteness, while other results will hold for another.

We introduce a new definition of finiteness, based on copower objects, which we call K^{∗}-finiteness, because the way in which it is defined is similar to the definition of K̃- finiteness (recalled below). We then show that this definition is equivalent to K̃-finiteness, so can be used to help us study K̃-finiteness.

Here is a recap of some well-known notions of finiteness, and some of their properties that we will need.

1.3. Definition. Given an object X in a topos, KX is the sub-join-semilattice of P X generated by {} : X [figure] P X. X is Kuratowski finite (or K-finite for short) if 1 [figure: ⌜X⌝] P X factors through KX.

It is well known that:

1.4. Lemma. KA is the object of K-finite subobjects of A, i.e. given A′ [figure: m] A, A′ is K-finite if and only if ⌜m⌝ : 1 [figure] P A factors through KA [figure] P A.

K-finiteness corresponds to the following induction principle: “If all singleton subobjects of X have property Φ, where Φ is expressible in the internal language of the topos, and the class of objects with property Φ is closed under union, then all K-finite subobjects of X have property Φ.”

K-finiteness is closed under quotients, products and unions, but not under subobjects – K1 = 2, so all K-finite subterminal objects are complemented. To fix this problem, the notion of K̃-finiteness was invented. This is similar to K-finiteness, but starts with the

partial map classifier X̃ of X, instead of the subobject X [figure: {}] P X. Recall that X̃ is an

object with a canonical monomorphism from X, such that morphisms A [figure: f] X̃ corre-

spond bijectively to partial morphisms from A to X. i.e. for every morphism A′ [figure: f] X

from a subobject A′ [figure] A to X, there is a unique morphism A [figure: f′] X̃ such that

[figure: A′; f; X; A; f′; X̃]

is a pullback. X̃ can be embedded in P X as the object of subsingleton subobjects of X,

i.e. the downset in P X generated by X [figure: {}] P X.

1.5. Definition. Given an object X in a topos, K̃X is the sub-join-semilattice of P X generated by X̃ [figure] P X. X is K̃-finite if 1 [figure: ⌜X⌝] P X factors through K̃X.

K̃-finiteness is closed under subobjects, quotients, products and unions. It corresponds to the induction principle: “If all subsingleton subobjects of X have property Φ, where Φ is expressible in the internal language of the topos, and the class of objects with property Φ is closed under union, then all K̃-finite subobjects of X have property Φ.”

To prove the result that K̃-finiteness and K^{∗}-finiteness are equivalent, we will need to use the theory of numerals, due to P. Freyd [2].

1.6. Definition. A pre-numeral is a poset with a constant 0 and a unary operation s which is order preserving and inflationary.

A numeral is a minimal pre-numeral i.e. a pre-numeral whose only subobject that contains 0 and is closed under application of s is itself.

This allows induction over numerals – if Φ(0) holds and Φ(x) ⇒ Φ(sx) holds for all x, then Φ(x) holds for all x.

1.7. Examples. (i) A natural numbers object is an object N with morphisms 1 [figure: 0] N

and N [figure: s] N, such that for any other object X with morphisms 1 [figure: x] X and X [figure: f] X,

there is a unique morphism N [figure: g] X such that

\xymatrix{1 \ar[r]^{s} \ar[dr]^{x} & N \ar[r]^{s} \ar[d]^{g} & N \ar[d]^{g} \\  & X \ar[r]^{f} & X}

commutes i.e. N is an initial prenumeral. Any natural numbers object N is a numeral, since given a subobject N′ [figure] N that contains 0 and is closed under the action of s,

there is a unique morphism N [figure: g] N′ as above, and the composite N [figure: g] N′ [figure] N commutes with 0 and s, and is therefore the identity on N. Thus, N′ must be the whole of N. If it exists, N is clearly therefore an initial numeral. Conversely, if there is an initial numeral, then it will be a natural numbers object, as any pre-numeral contains a numeral, and any morphism from the initial numeral to it is contained in this numeral.

(ii) If n is a natural number (in the set theoretic sense), then the coproduct of n copies of 1 is a numeral, with 0 picking out the first copy of 1, and the successor map s sending the kth copy of 1 to the (k + 1)th copy of 1 for k < n, and sending the nth copy to itself.

(iii) In the Sierpinski topos (the functor category [2, \underline{Set}], where 2 is the category

with two objects A and B and one non-identity morphism A [figure: f] B) the functor F with F (A) = m, F (B) = n where m and n represent m and n element sets for natural numbers m ⩾ n with F (f)(i) = min(i, n) is a numeral; 0 picks out the least element of m and n, and s increases the elements of m and n by 1 if they are not the top element, and fixes the top element.

(iv) Given a reflexive relation R on X, and a subobject X_{0} of X, form a pre-numeral on P X by letting 0 be X_{0} and letting s send a subobject X′ of X to the subobject of elements of X related to something in X′. Restricting to the numeral n, contained in this pre-numeral, there is a relation, ϕ between n and X, given by ϕ(0, x) if x ∈ X_{0} and ϕ(si, x) if (∃y : X)(ϕ(i, y) ∧ (yRx)). The image of n under this relation is then the R-closure of X_{0}.

1.8. Definition. When the relation R in Example 1.7(iv) is the relation “differ by a singleton” on P X, i.e. the relation

(X_{1}RX_{2}) ⇔ (∃x : X)(X_{1} ∪ {x} = X_{2})

the transitive closure of the singleton containing the empty subset of X is just KX. In this case, the numeral produced in forming the transitive closure is called num_{X}.

In this paper, we use the notation K_{n}-finite for an object X that is K-finite and has num_{X} ⩽ n. We also define { \atop num}_{X} in the same way as num_{X}, but using the relation “differ by a partial singleton” – i.e. the construction of K̃X as a transitive closure.

1.9. Examples. (i) In \underline{Set}, if X is an n element set for some natural number n, then X is K_{n}-finite.

(ii) In the Sierpinski topos, any functor F with F (A) = m and F (B) = n (for m ⩾ n natural numbers) is K_{G}-finite, where G is the numeral with G(A) = m and G(B) = n (defined in Example 1.7(iii)).

We then observe that the definition of K^{∗}-finiteness leads to another definition, which we call K^{∗∗}-finiteness. This is not even classically equivalent to other definitions of finiteness without the axiom of choice – classically, it is related to the notion of an amorphous set:

1.10. Definition. A set is amorphous if it is infinite but not the disjoint union of two infinite sets.

1.11. Examples. (i) If G is the group of permutations of an infinite set X, given the topology that sets containing the pointwise stabilizers of finite subsets of X are open, then there is a Fraenkel-Mostowski model of set theory that is equivalent as a topos to the topos of continuous G-sets for this topology. In this topos, X with the obvious Gaction (which is continuous) is an amorphous set, since a subset of X in the original model of set theory will only give a subobject of X × U for some subterminal object U here if its stabilizer is an open subgroup of G, and this only occurs if the set is either finite or has finite complement.

Many of the properties of amorphous sets are studied in [6]. In any partition of an amorphous set with infinitely many pieces, all the pieces must be finite, and all but finitely many of the pieces must be the same size. This leads to the following definition.

1.12. Definition. An amorphous set X is bounded amorphous if there is a natural number n, such that in any partition of X, all but finitely many of the pieces have size at most n. X is strictly amorphous if this n is 1.

At the end of Section 4, we show that in a general topos, K^{∗∗}-finite objects are exactly some suitably constructive version of bounded amorphous objects with an extra property which we call usual finiteness, which is necessary to compensate for the possibility that the subobject classifier might not be K-finite. The proof of this result is fairly technical, and so the reader might wish to move to Section 5 after Remark 4.10. In the proof, we use a well-known theorem from combinatorics:

1.13. Theorem. [F. P. Ramsey] For any two natural numbers m and n, there is an N such that whenever the edges of a complete graph on N vertices is coloured with two colours, red and blue, say, there is either a set of m vertices with all edges between them coloured red, or a set of n vertices with all edges between them coloured blue.

The form we shall actually need is the following.

1.14. Theorem. Given a complete graph on a set X of vertices, and a two-colouring of the edges of X, if there is a finite bound on the size of monochromatic subsets of X, then there is a finite bound on the size of X.

This version of the theorem is constructive, and so true in any topos (there is an infinite version also called “Ramsey’s theorem” which is not constructive).

In Section 5, we briefly consider some alternative approaches to topos theory that might require further study, such as the object of all retracts of X, or the object of all subquotients of X. The former does not lead to a definition of a topos, but might be of use for studying weaker categories, while the latter does define a topos, and so might be of use in topos theory.

2. Copower Objects

In this section, we investigate a new approach to topos theory, based on quotients rather than subobjects. We show that in a pretopos (an effective regular, positive coherent category), the existence of copower objects is equivalent to the existence of power objects, and show how in this case, we can construct exponentials directly from copower objects. We show that the assignment of copower objects can be made functorial in either a contravariant or a covariant way. (We will see in Section 3 that these functors are internally adjoint with respect to the canonical lattice structure on copower objects.)

2.1. Definition. Given an object A in a cartesian category C, a copower object for A is an object QA equipped with a cover (a morphism that doesn’t factor through any nonidentity monos) QA × A [figure: q] RA through which the projection QA × A [figure: π_{1}] QA factors, such that if X × A [figure: x] Y is any other cover through which the projection π_{1} factors, then there is an unique morphism X [figure: ⌞x⌟] QA such that in the following diagram, where the vertical composites are projections, both small squares are pullbacks:

\xymatrix{X × A \ar[r]^{⌞x⌟×1_{A}} \ar@{|->}[d]_{x} & QA × A \ar@{|->}[d]^{q} \\ Y \ar[r] \ar[d] & RA \ar[d] \\ X \ar[r]_{⌞x⌟} & QA}

2.2. Remark. Of course, the top square will be a pullback whenever the bottom one is and the top square commutes, as the whole rectangle is always a pullback.

2.3. Remark. It would be nice to have a generic quotient, as well as a copower object for each object. Unfortunately, this does not occur in any non-degenerate topos, or indeed in any category with disjoint coproducts, since the functor sending an object to the set of its quotients doesn’t send coproducts to products, and so cannot be representable.

2.4. Examples. (i) In \underline{Set}, QA is just the set of all isomorphism classes of surjections with domain A, or equivalently the set of all equivalence relations on A. RA is the set of ordered pairs consisting of an equivalence relation on A and an equivalence class for this relation, or equivalently pairs consisting of a surjection with domain A and an element of the codomain.

(ii) In a poset with a top element, the top element is a copower object for every element, since the only quotients are the identities.

(iii) In [C, \underline{Set}], copower objects are given by the Yoneda lemma – for a functor F, and an object X of C,

QF (X) ≅ [C, \underline{Set}](C(X, ), QF) ≅ \{quotients of C(X, ) × F over C(X, )\}

2.5. Lemma. (i) In a regular category, the assignment A ↦ QA can be made into a contravariant functor Q. This functor sends covers to monos, and in a category with monic pushouts of monos, it sends monos to covers.

(ii) In a regular category with pullback-stable pushouts of covers (e.g. a quasitopos), A ↦ QA can be made into a covariant functor Ⅎ. This functor preserves covers, and if monos are stable under pushout then it preserves them also.

Proof. (i) Let A [figure: f] B be a morphism. We need to determine the morphism QB [figure: Qf] QA. In \underline{Set}, it sends a quotient q of B to the cover part of the composite qf, or in terms of equivalence relations, it takes the pullback along f.

For a general topos, form the composite QB × A [figure: 1×f] QB × B [figure: q] RB. Let its cover-

mono factorization be QB ×A [figure: c] I [figure: i] RB. π_{1} factors through c, so take QB [figure: Qf] QA to be ⌞c⌟. It is a straightforward diagram chase to verify that this is indeed a functor.

If f is a cover then for any X [figure: ⌞q⌟] QA, Qf⌞q⌟ = ⌞q(f × 1_{X})⌟, so that whenever Qf⌞q⌟ = Qf⌞q′⌟, qf = q′f. f is epi, so this can only happen if q = q′. Therefore, Qf is mono.

If f is mono and there are pushouts that preserve monos then the pushout of any quotient q of X × A along 1_{X} × f gives a quotient q′ of X × B such that Qf⌞q′⌟ = ⌞q⌟. Therefore, Qf is a cover.

(ii) Let A [figure: f] B be a morphism. We need to determine the morphism QA [figure: Ⅎf] QB. In \underline{Set}, it sends a quotient q of A to its pushout along f, or in terms of equivalence relations, Ⅎf(R) relates elements a and b of B if and only if a = f(c) and b = f(d) for some elements c and d of A that are related by R.

Covers are preserved under pushouts. Given A [figure: f] B, form the pushout:

\xymatrix{QA × A \ar[r]^{1×f} \ar@{|->}[d]_{q} & QA × B \ar@{|->}[d]^{x} \\ RA \ar[r] & R_{f}}

π_{1} clearly factors through x. We set Ⅎf = ⌞x⌟. It remains to check that composition

works. Given A [figure: f] B [figure: g] C, there is a diagram:

\xymatrix{QA × B \ar@{|->}[d] \ar[r]^{Ⅎf×1_{B}} & QB × B \ar@{|->}[d]^{q} \ar[r]^{1_{QB}×g} & QB × C \ar@{|->}[d] \\ R_{f} \ar[d] \ar[r] & RB \ar[d] \ar[r] & R_{g} \ar[dl] \\ QA \ar[r]^{Ⅎf} & QB}

where both left-hand squares are pullbacks. To show that Ⅎ(gf) = ℲgℲf, it is sufficient to show that in the following diagram:

\xymatrix{QA × B \ar@{|->}[d] \ar[r]^{1_{QA}×g} & QA × C \ar@{|->}[d] \ar[r]^{Ⅎf×1_{C}} & QB × C \ar@{|->}[d] \\ R_{f} \ar[dr] \ar[r] & R_{gf} \ar[d] \ar[r] & R_{g} \ar[d] \\  & QA \ar[r]^{Ⅎf} & QB}

the right-hand squares are pullbacks, and the left-hand one is a pushout. However, this follows trivially from the fact that Ⅎf^{∗} preserves pushouts of covers.

If f is a cover then for any quotient q of X × B the pushout of q(1_{X} × f) along 1_{X} × f is just q, so Ⅎf is a cover.

If f is mono, and monos are stable under pushout, then any quotient q of X × A is the cover part of the diagonal of the pushout square

[figure: X × A; 1_{X}×f; q; X × B; r; Q; R]

so QfℲf is the identity, making Ⅎf mono.

2.6. Proposition. In a quasitopos E, all objects have copower objects.

Proof. Given an object A, the copower object QA is just the object of (strong) equivalence relations on A, i.e. the object

{R : P (A × A)|(∀a, b, c : A)((a, a) ∈ R ∧ (a, b) ∈ R ⇒ (b, a) ∈ R ∧
(((a, b) ∈ R ∧ (b, c) ∈ R) ⇒ (a, c) ∈ R)}

The object RA is then the coequalizer of the equivalence relation on QA × A that relates (R, a) to (S, b) if and only if R = S and (a, b) ∈ R.

Given an arbitrary cover X × A [figure: x] Y through which the projection factors, ⌞x⌟ is the factorization of the name of the relation

{(m, a, b) : X × A × A|x(m, a) = x(m, b)}

(which is a morphism X [figure] P (A × A)) through QA [figure] P (A × A). Let the pullback of

RA along ⌞x⌟ be Y′, and let the morphism (⌞x⌟)^{∗}(q) be X × A [figure: x′] Y′. Its kernel pair is the pullback of the kernel pair of q, which is the relation on X × A that relates (m, a) to (n, b) if and only if m = n and x(m, a) = x(m, b). This relation is the kernel pair of x. Therefore, Y′ = Y and x′ = x.

Let f be any morphism with f^{∗}(q) = x. Then the composite

X [figure: f] QA [figure] P (A × A)

names the kernel pair of x, so f = ⌞x⌟ as QA [figure] P (A × A) is monic.

There is an analogue of the Beck-Chevalley condition for copower objects in a quasitopos.

2.7. Lemma. In a quasitopos, let

\xymatrix{A \ar[r]^{f} \ar[d]^{g} & B \ar[d]^{h} \\ C \ar[r]^{k} & D}

be a pushout. Then

\xymatrix{QB \ar[r]^{Qf} \ar[d]^{Ⅎh} & QA \ar[d]^{Ⅎg} \\ QD \ar[r]^{Qk} & QC}

commutes.

Proof. Let QB×D  [figure] Y be the pushout of QB×B  [figure] RB along 1_{QB}×h. QkℲh corre-

sponds to the quotient QB×C [figure] Z, where Z [figure] Y is the image of QB×C [figure: 1_{QB}×k]QB× D [figure] Y. On the other hand, if I [figure] RB is the image of

QB × A [figure: 1_{QB}×f]QB × B [figure] RB

then ℲgQf corresponds to the pushout Z′ of QB × A [figure] I along 1_{QB} × g. To show that these are the same, it is merely necessary to show that the morphism from Z′ to Y is mono. Consider the following diagram:

[figure: QB × A; QB × B; QB × C; QB × D; I; RB; Z′; Y]

The left-hand, right-hand and top squares are pushouts, so the bottom square is also a pushout, making Z′ [figure] Y monic.

This shows that in a quasitopos Q sends covers to split monos and Ⅎ sends covers to split epis. The proof of Lemma 2.5 has already shown that in a topos Q sends monos to split epis and Ⅎ sends monos to split monos.

2.8. Theorem. A pretopos in which all objects have copower objects is a topos.

Proof. The idea here is that subobjects of A correspond bijectively to equivalence relations on A ⨿ 1 whose only non-trivial equivalence class is the equivalence class containing 1. The object of these equivalence relations is a retract of the object of all equivalence relations on A, since any equivalence relation can be restricted to just the equivalence class containing 1. To obtain the power object P A, we just need to construct the composite Q(A ⨿ 1) [figure] P A [figure] Q(A ⨿ 1), then we can take its cover-mono factorization.

First we construct the pullback:

[figure: P; p; Q(A ⨿ 1); 1×ν_{2}; Q(A ⨿ 1) × (A ⨿ 1); Q(A ⨿ 1) × (A ⨿ 1); R(A ⨿ 1)]

The right vertical morphism is monic because it is split by R(A ⨿ 1) [figure] Q(A ⨿ 1).

The idea here is that P should contain the equivalence class of 1 for each equivalence relation on A ⨿ 1. We will next restrict to the equivalence relation q′ that relates two elements (q, a) and (q, b) if and only if q relates both a and b to 1. The morphism ⌞q′⌟ will then send two quotients of A to the same thing if and only if they relate the same subset of A to 1, so its image will be isomorphic to the power object of A.

To do this, construct the intersection m in Sub(Q(A ⨿ 1) × (A ⨿ 1) × (A ⨿ 1)) of p_{12} and p_{13}, where p_{12} is just the Cartesian product of the subobject p with A ⨿ 1, and p_{13} is the composite of this with the isomorphism that swaps the two copies of A ⨿ 1 – i.e. in \underline{Set}, p_{12} is the set of triples (q, a, b) such that (q, a) ∈ p, while p_{13} is the set of triples such that (q, b) ∈ p, and thus, m is the set of triples (Q, a, b) such that both (q, a) ∈ p and (q, b) ∈ p. Let Q(A ⨿ 1) × (A ⨿ 1) [figure: q′] R′(A ⨿ 1) be the coequalizer of π_{12}m and π_{13}m, where π_{12} and π_{13} are the projections. This coequalizer exists because (π_{12}m, π_{13}m) is an equivalence relation, and is therefore effective. It is a map over Q(A ⨿ 1) because π_{1} has the same composite with π_{12} and π_{13}. Q(A ⨿ 1) [figure: c] P A [figure: i] Q(A ⨿ 1) is the cover-image factorization of ⌞q′⌟.

The universal relation, ∈ [figure] P A × A occurs as the pullback of the relation

S [figure] Q(A ⨿ 1) × (A ⨿ 1) × (A ⨿ 1)

along \xymatrix{P A × A ≅ P A × A × 1 \ar[r]^{i×ν_{1}×ν_{2}} & Q(A ⨿ 1) × (A ⨿ 1) × (A ⨿ 1)}, where S is the ker-

nel pair of Q(A ⨿ 1) × (A ⨿ 1) [figure: q] R(A ⨿ 1) and ν_{1} and ν_{2} are the coprojections.

It remains to show that this is indeed a power object for A. Given an arbitrary relation T [figure: m] X × A, let m′ = (m_{12} ∩ m_{13}) ∪ (1_{X} × Δ_{A⨿1}), where m_{12} is the subobject:

[figure: (T ⨿ X) × (A ⨿ 1); (m⨿1)×1; (X × A ⨿ X) × (A ⨿ 1) ≅ X × (A ⨿ 1) × (A ⨿ 1)]

and m_{13} is similar, but with the order of the copies of A ⨿ 1 swapped. The idea is that m′ should relate (x, a) to (x, 1) if and only if (x, a) ∈ m (consider the case X = 1, where m_{12} is just (m ⨿ 1) × (A ⨿ 1), i.e. it relates the elements of m ⨿ 1 to all elements of A, while m_{13} relates elements of A to elements of m ⨿ 1, so that two elements of A are related by m_{12} ∩ m_{13} if and only if they are both in m ⨿ 1).

Let X × (A ⨿ 1) [figure: x] Y be the coequalizer of π_{12}m′ and π_{13}m′. (π_{12}m′, π_{13}m′) is an equivalence relation, so the coequalizer exists. The composite X [figure: ⌞x⌟] Q(A ⨿ 1) [figure: c] P A is then the name of T.

The pullback of R′(A ⨿ 1) along ⌞x⌟ is Y, so the pullback of its kernel pair is T′, by effectiveness, and ⌞q′⌟⌞x⌟ = ⌞x⌟. Therefore, the pullback of ∈ along

X × A [figure: ⌞x⌟×1_{A}]Q(A ⨿ 1) × A [figure: c×1_{A}] P A × A

is the pullback of T′ along [figure: X × A; 1_{X}×ν_{1}×ν_{2}; X × (A ⨿ 1) × (A ⨿ 1)], which is T.

On the other hand, if the pullback of ∈ along X × A [figure: f×1] P A × A is T, then if = ⌞y⌟

for some X × (A ⨿ 1) [figure: y] Y′ for which the pullback of Z [figure: z] X × (A ⨿ 1) × (A ⨿ 1) along 1_{X} ×ν_{1} ×ν_{2} is T, where (π_{12}z, π_{13}z) is the kernel pair of y. Also, if = icif factors through ⌞q′⌟, meaning that Z only relates (v, a) and (v, b) if it also relates (v, a) and (v, 1). This forces y = x, since y is the coequalizer of its kernel pair, and hence, f = c⌞x⌟.

The construction of exponentials from copower objects can be done directly by considering the cographs:

2.9. Theorem. In a topos E, the exponential A^{B} is the intersection of the pullbacks:

[figure: P_{1}; 1; ⌞1_{A}⌟; Q(A ⨿ B); Qν_{1}; QA]  and  [figure: P_{2}; 1; ⌞1⨿B⌟; Q(A ⨿ B); Ⅎg; Q(1 ⨿ B)]

in Sub(Q(A ⨿ B)), where g is the morphism A ⨿ B [figure: g] 1 ⨿ B induced by A [figure] 1 and 1_{B}, and 1 ⨿ B is used to refer to the morphism 1 ⨿ B [figure] 1.

Proof. The idea here is that given a quotient q of A ⨿ B, q is the cograph of a morphism

B [figure: f] A if and only if qν_{1} ≅ 1_{A}. Since a topos is balanced, it suffices to show that qν_{1} is monic and epic. However, q is in P_{1} if and only if qν_{1} is monic, since the cover part of the cover-mono factorization of qν_{1} is the identity. On the other hand, q is in P_{2} if and only if qν_{1} is epic, since

\xymatrix{A \ar[r] \ar[d]^{ν_{1}} & 1 \ar[d]^{ν_{1}} \\ A ⨿ B \ar[r] & 1 ⨿ B}

is a pushout, so the pushout of qν_{1} along A is the identity on 1, so qν_{1} must be a cover.

More formally, let f be the morphism X × A [figure] X × (A ⨿ B) [figure: x] Y. We need to prove:

(i) The morphism X [figure: ⌞x⌟] Q(A ⨿ B) factors through P_{1} if and only if f is monic. (ii) ⌞x⌟ factors through P_{2} if and only if f is epic.

(i): Let Q(A ⨿ B) × A [figure] I [figure] R(A ⨿ B) be the cover-mono factorization of qν_{1}. The pullback of I along ⌞x⌟ is X × A if and only if Qν_{1}⌞x⌟ factors through ⌞1_{A}⌟, or equivalently, if and only if ⌞x⌟ factors through P_{1}. The pullback of I along ⌞x⌟ is the image of f, so saying that it is X × A is the same as saying that f is monic.

(ii): Let

\xymatrix{Q(A ⨿ B) × (A ⨿ B) \ar[r] \ar[d] & Q(A ⨿ B) × (1 ⨿ B) \ar[d]^{y} \\ R(A ⨿ B) \ar[r] & W}

be a pushout. Then Ⅎg⌞x⌟ factors through ⌞1 ⨿ B⌟ if and only if ⌞x⌟^{∗}(Y) = X. We therefore want to show that ⌞x⌟^{∗}(W) = X if and only if f is epic.

[figure: Q(A ⨿ B) × A; Q(A ⨿ B); y′; R(A ⨿ B); W]

Is also a pushout. (The right-hand arrow is monic because it has a left inverse.) Let Q(A ⨿ B) × A [figure] Z [figure] R(A ⨿ B) be the cover-mono factorization. Then

[figure: Z; Q(A ⨿ B); y′; R(A ⨿ B); W]

is a pushout, since pushouts preserve cover-mono factorizations, and therefore a pullback. Let X [figure: h] W be the pullback of ⌞x⌟ along the left inverse of y′ (the domain is X because the left-hand edge in this pullback is an isomorphism). h factors through y′, since the pullback of y′ along it is the identity. Therefore, in the following diagram, all squares are pullbacks.

[figure: X × A; f; Y; ≅; Y; X; h; X; ⌞x⌟; Q(A ⨿ B) × A; Z; R(A ⨿ B); W; Q(A ⨿ B)]

Therefore, f is epi.

Having proved (i) and (ii), morphisms C [figure] P_{1} ∩ P_{2} correspond bijectively to quotients C × (A ⨿ B) [figure: c] C × A over C, whose restriction to C × A is the identity. Each such morphism is uniquely determined by its restriction to C ×B, and the first projection is fixed, so the morphism is uniquely determined by the second projection C × B [figure] A, i.e. P_{1} ∩ P_{2} is the exponential A^{B}.

2.10. Remark. The above proof did require E to be a topos, since in general, the pushout of a mono won’t also be a pullback, so the above does not show that categories with copower objects are cartesian closed in any weaker cases.

2.11. Proposition. Any slice of a cocartesian regular category with copower objects has copower objects.

Proof. Given A [figure: f] B in C/B, Let A [figure: f′] B′ [figure: f′′] B be the cover-mono factorization of f. The copower object Qf is given by the pullback:

[figure: Qf; ⩽; B × QA; ⌞g⌟×1; QA × QA]

where g is the pushout of f′ along the graph of f, i.e. the quotient that identifies (a, b) and (a′, b′) if and only if b = b′ and f(a) = f(a′) = b, and ⩽ is the order relation on QA, where quotients are ordered by factorization. (This order on QA will be studied in more detail in Section 3.) Qf can be thought of as the object of pairs (b, R) where b is an element of B and R is a quotient of f^{−1}({b}).

Given an object C [figure: h] B of C/B, morphisms from h to Qf in C/B correspond to morphisms from C to B × QA whose second projection names a quotient through which h^{∗}(g) factors, i.e. to quotients of h × f in C/B.

2.12. Proposition. In a topos E, an object A satisfies A ≅ QA if and only if there is a pushout:

[figure: U; 1; 1; A]

where U is an internally widespread subterminal object in E.

Proof. Given a pushout diagram as above, A is a c(U)-sheaf, and A ≅ QA clearly holds in Sh_{c(U)}(E), so it holds in E, since any quotient of A is also a c(U)-sheaf.

Conversely, let A ≅ QA. There are two canonical morphisms \xymatrix{1 \ar[r]^{⊤} \ar[r]_{⊥} & A}, where ⊤

corresponds to the identity on A, and ⊥ to the map from A to its support (which is 1, as A admits a morphism from 1). Let U [figure] 1 be the equalizer of ⊤ and ⊥, and let A [figure: c] C be their coequalizer. Clearly, U is also the equalizer of ⊤ and ⌞c⌟. Let V [figure] 1 be the equalizer of ⊥ and ⌞c⌟.

As elements of A are quotients of A, they are partially ordered by factorization, i.e. c_{1} ⩽ c_{2} if and only if c_{1} factors through c_{2}, so that ⊥ is a bottom element. Note that this is the reverse of the inclusion ordering on the corresponding equivalence relations. Now for any a ∈ A, we have the equivalence relation R, given by

(bRb′) ⇔ ((b ⩽ a) ∧ (b′ ⩽ a)) ∨ (b = b′)

This gives a morphism A [figure: f] A. f is monic because A has a bottom element, so if f(a) = f(b) then both f(a) and f(b) relate a to ⊥, so a ⩽ b, and similarly b ⩽ a, making b = a, as required.

Define an equivalence relation S by

aSb ⇔ (a = b) ∨ ((⌞c⌟ ⩽ a) ∧ (⌞c⌟ ⩽ b))

⌞S⌟ is in the image of f if and only if c = ⊥, which is an assertion whose truth value is V. Let V [figure: m] A be the pullback of ⌞S⌟ along f. There is a morphism P^{m}A [figure: g] A, where P^{m}A is the object of subobjects of A containing m, given by x ↦ R_{x}, where

aR_{x}b ⇔ (a = b) ∨ (a ∈ (∃_{f}(x) ∪ {⌞S⌟}) ∧ b ∈ (∃_{f}(x) ∪ {⌞S⌟}))

Now g(x) = g(x′) if and only if ∃_{f}(x) ∪ {⌞S⌟} = ∃_{f}(x′) ∪ {⌞S⌟}, which occurs if and only if x ∪ m = x′ ∪ m. Therefore, in Sh_{c(V)}(E), g becomes a mono P A [figure] A, meaning that Sh_{c(V)}(E) is degenerate, i.e. that V = 1.

Thus A is a quotient of 2. In Sh_{c(U)}(E), ⊤ and ⊥ are disjoint, so that A = 2. Therefore, in this topos 2 ≅ Q2 ≅ Ω. Therefore, Sh_{c(U)}(E) is boolean. Hence U is internally widespread and A is the pushout of U [figure] 1 along itself.

3. Lattice Structure of Copower Objects

Recall that there is a canonical way of inducing a partial order on a copower object by factorization as in Proposition 2.12 – a quotient X [figure: q] Y is less than or equal to another

quotient X [figure: q′] Y′ if q factors through q′. In this section, we study this partial order in more detail, and show that in a topos any copower object is a complete lattice, and the canonical functors Q and Ⅎ send any morphism to an adjoint pair of order preserving lattice homomorphisms.

3.1. Proposition. In a quasitopos, QA is an internal lattice for any A.

Proof. Let X × A [figure: y] Y [figure: y′] X and X × A [figure: z] Z [figure: z′] X be two quotients. The least upper bound of x and y is the image of

X × A [figure: 1×Δ_{A}] X × A × A [figure] P

where P is the pullback

[figure: P; Z; z′; Y; y′; X]

since any upper bound factors through P and is a quotient of X. Therefore, we seek a quotient q′ of QA × QA × A over QA × QA whose pullback along (⌞x⌟, ⌞y⌟) is this image. Then QA × QA [figure: ∨] QA will just be ⌞q′⌟.

The pullback of

QA × QA × A [figure: 1_{QA×QA}×Δ_{A}]QA × QA × A × A [figure: q×q] RA × RA

along (⌞x⌟, ⌞y⌟) is

X × A [figure: 1×Δ_{A}] X × A × A [figure] P

so q′ is just the cover part of the cover-mono factorization of (q ×q)(1_{QA×QA} ×Δ_{A}), where q is the generic cover QA × A [figure] RA.

The greatest lower bound of x and y is clearly the pushout

\xymatrix{X × A \ar@{|->}[r]^{y} \ar@{|->}[d]^{z} & Y \ar@{|->}[d] \\ Z \ar@{|->}[r] & S′}

So we seek a quotient of QA × QA × A over QA × QA whose pullback along (⌞x⌟, ⌞y⌟) is the diagonal of the above pushout. The diagonal s of the pushout

[figure: QA × QA × A; QA × RA; RA × QA; S]

clearly has this property. We therefore obtain the binary meet ∧ as ⌞s⌟.

3.2. Proposition. In a topos, QA is an internal complete lattice for any object A.

Proof. Given a subobject S [figure: s] X × QA, the projection to QA is ⌞t⌟ for some quotient

S × A [figure: t] T. The meet of S is the pushout

\xymatrix{S × A \ar[r] \ar@{|->}[d]^{t} & X × A \ar@{|->}[d]^{z} \\ T \ar[r] & Z}

because for any quotient r : QA in S, any a and b related by r, will also be related by z, as

(r, a) and (r, b) are related by t. The morphism P QA [figure: ⋀] QA must therefore be ⌞y⌟ for

some quotient P QA × A [figure: y] Y [figure] P QA, such that for any subobject S [figure] X × QA, the following squares are both pullbacks:

\xymatrix{X × A \ar[r]^{⌜S⌝×1} \ar@{|->}[d]^{z} & P QA × A \ar@{|->}[d]^{y} \\ Z \ar[r] \ar[d] & Y \ar[d] \\ X \ar[r]^{⌜S⌝} & P QA}

where z is the meet of the elements of S as described above.

Let ∈_{QA} ×A [figure] I [figure] P QA × RA be the cover-mono factorization of

∈_{QA} ×A [figure] P QA × QA × A [figure] P QA × RA

This means that ∈_{QA} ×A [figure] I corresponds to the morphism ∈_{QA} [figure] P QA×QA [figure: π_{2}] QA. We will show that the morphism y we require is the pushout:

[figure: ∈_{QA} ×A; P QA × QA × A; π_{13}; P QA × A; y; I; Y]

Since T [figure] X ×RA is a pullback of S [figure] X ×QA, it is mono. Also, in the following diagram, both squares are pullbacks.

[figure: S × A; ∈_{QA} ×A; X × QA × A; ⌜S⌝×1; P QA × QA × A; X × RA; ⌜S⌝×1; P QA × RA]

Therefore, in the following cube, the left, right, top and bottom faces are pullbacks (the bottom face is a pullback because cover-mono factorizations are pullback-stable).

[figure: S × A; X × A; ∈_{QA} ×A; P QA × A; T; Z; I; Y]

The front face is a pushout, and pullback along Z [figure] Y preserves pushouts because it has a right adjoint, so the back square is also a pushout.

The existence of infinitary meets ensures the existence of infinitary joins. However, it is enlightening to construct the joins explicitly. Given S and S [figure: t] T as above, the join of S

must be a quotient X ×A [figure: z′] Z′  [figure] Z such that for any quotient X ×A [figure: y] Y  [figure] X,

the pullback of y along S [figure: π_{1}s] X factors through t if and only if z′ factors through y, since the pullback factoring through t means that the quotient is ⩾ all quotients in S. This means that z′ must be Π_{π_{1}s}(t), where Π_{π_{1}s} is the functor right adjoint to pullback along π_{1}s.

We therefore need to get Π_{π_{1}s}(t) as the pullback along ⌜S⌝ of some

P QA × A [figure: w] W [figure: w′] P QA

for any S. The required object W is just Π_{∈_{QA} [figure] QA}(I), since pullback preserves Π-

functors and

\xymatrix{S \ar[r] \ar[d] & ∈_{QA} \ar[d] \\ X \ar[r]^{⌜S⌝} & P QA}

is a pullback. The infinitary join ⋁ is then just ⌞w⌟.

3.3. Proposition. For any A [figure: f] B, Qf ⊣ Ⅎf as order-preserving morphisms. Thus, Qf is a join-homomorphism and Ⅎf is a meet-homomorphism, and they are complete in a topos.

Proof. Note that ℲfQf corresponds to the morphism QB × B [figure] P in the following diagram, where the top left square is a pushout:

[figure: QB × A; 1×f; QB × B; I; P; RB]

so for any x : QB, x ⩽ ℲfQf(x).

QfℲf corresponds to the morphism QA × A [figure] I′ in the following diagram, where the top square is a pushout.

[figure: QA × A; 1×f; QA × B; RA; P; I′]

RA  [figure] P factors through I′ [figure] P because it is the image of QA × A  [figure] P. Thus

for any x : QA, QfℲf(x) ⩽ x. Therefore, Qf ⊣ Ⅎf as order-preserving morphisms.

3.4. Proposition. (i) If f is mono, then Ⅎf is a lattice homomorphism, and in a topos preserves all inhabited meets.

(ii) If f is a cover, then Qf is a lattice homomorphism, and in a topos preserves all inhabited joins.

Proof. (i) When f is mono, we will show that ℲfQf = ∨ c, so QA is order-isomorphic, and therefore complete-lattice-isomorphic to the sublattice of QB consisting of quotients that are ⩾ c. The embedding of this lattice into QB is a lattice homomorphism that preserves inhabited joins, so Ⅎf will also preserve all inhabited joins.

Let

[figure: A; f; B; c; σ(A); C]

be a pushout, and let the cover-mono factorization of QB × A [figure: 1×f] QB × B [figure: q] RB be QB ×A [figure] I [figure] RB (Here σ(A) denotes the support of A, i.e. the image of the unique morphism A [figure] 1). Consider the following diagram in which both squares are pushouts (and therefore also pullbacks).

[figure: QB × A; 1×f; QB × B; g; I′; f; I′; σ(A); C]

q and c both factor through g, so q ∨ c also factors through g. This gives a diagram:

[figure: I; f′; I′; x; C ∨ RB; σ(A); C]

The kernel pair of x is contained in the kernel pair of I′ [figure] C, which is (f′ × f′) ∪ Δ as a relation on I′ × I′. Let S be the kernel pair of x as a relation on I′ × I′. Since I [figure] C ∨RB is monic, the intersection of S with f′ ×f′ is the diagonal, so S is contained in the diagonal, meaning that x is an iso.

(ii) When f is a cover, we want to show that ⋀ ∃Qf = Qf ⋀ when restricted to P^{+}QB. First we consider ⋀ ∃Qf. It will be ⌞z⌟ for some P^{+}QB × A [figure: z] Z [figure] P^{+}QB. This occurs as a pullback:

\xymatrix{P^{+}QB × A \ar[r]^{∃Qf×1} \ar@{|->}[d]^{z} & P^{+}QA × A \ar@{|->}[d]^{y} \\ Z \ar[r] \ar[d] & Y \ar[d] \\ P^{+}QB \ar[r]^{∃Qf} & P^{+}QA}

where y is as in Proposition 3.2.

There is a commutative diagram:

[figure: QB × A; Qf×1; 1×f; QB × B; RB; QB; Qf; QA × A; RA; QA]

where both squares are pullbacks. Therefore, the pullback of

∈_{QA} ×A  [figure] P^{+}QA × QA × A  [figure] P^{+}QA × RA

along ∃Qf × 1_{RA} is

∈_{QB} ×A [figure: 1×f]∈_{QB} ×B [figure] P^{+}QB × RB [figure] P^{+}QB × RA

Let the cover-mono factorization of this pullback be

∈_{QB} ×A [figure] L [figure] P^{+}QB × RA
Then z is the pushout of ∈_{QB} ×A  [figure] L along ∈_{QB} ×A  [figure] P^{+}QB × A.

Now consider Qf ⋀. This corresponds to the right-hand composite in the following diagram, where the bottom square is a pushout and ∈_{QB} ×B [figure] J [figure] P^{+}QB × RB is the cover-mono factorization of ∈_{QB} ×B [figure] P^{+}QB × RB:

[figure: ∈_{QB} ×A; 1×f; P^{+}QB × A; 1×f; ∈_{QB} ×B; P^{+}QB × B; J; M]

However, since ∈_{QB} [figure] P^{+}QB is a cover, the top square is also a pushout, and therefore, so is the whole rectangle. Also, J ≅ L, as they are both the image of

∈_{QB} ×A [figure: 1×f]∈_{QB} ×B [figure] P^{+}QB × RB [figure] P^{+}QB × RA

Thus, the quotients of P^{+}QB × A corresponding to ⋀ ∃Qf and Qf ⋀ are equal, so ⋀ ∃Qf = Qf ⋀.

4. Finiteness

In this section, we look at an application of copower objects to the study of finiteness. In a topos, the many different classical definitions of finiteness are no longer equivalent, so we have a number of different definitions which can be applied in different situations. We use copower object based ideas to produce a new definition, which we call K^{∗}-finiteness. We then show that this is equivalent to K̃-finiteness – therefore giving a new way of studying K̃-finiteness.

We then observe that the definition of K^{∗}-finiteness gives rise to a new definition of finiteness, which we call K^{∗∗}-finiteness. We then characterise K^{∗∗}-finiteness in terms of a constructive version of amorphousness, and a concept which we call usual finiteness.

Given an object X in a topos E and elements a, b of X̃, we have a relation R_{ab} that relates only the members of a and b, i.e. two elements c and d are related if and only if (c = d) ∨ (c ∈ a ∧ d ∈ b) ∨ (c ∈ b ∧ d ∈ a) holds. Now define a relation R on the copower object QX, by setting xRy if (∃a, b : X̃)(x ∧ R_{ab} = y ∧ R_{ab}). (Recall that the order on QX is by factorization – i.e. the opposite of inclusion of equivalence relations.) Let \overline{R} be the transitive closure of R.

4.1. Definition. Let K^{∗}X be the quotient of QX corresponding to \overline{R} above. X is K^{∗}- finite if K^{∗}X ≅ 1.

4.2. Lemma. Subterminal objects are K^{∗}-finite.

Proof. If U is subterminal then QU ≅ 1, so K^{∗}U ≅ 1.

4.3. Lemma. (i) Subobjects of K^{∗}-finite objects are K^{∗}-finite.

(ii) Quotients of K^{∗}-finite objects are K^{∗}-finite.

Proof. (i) Let X be K^{∗}-finite and let Y [figure: m] X be a subobject of X. Qm(R_{ab}) = R_{m^{∗}(a)m^{∗}(b)}, so the diagram:

[figure: QX; Qm; QY; K^{∗}X ≅ 1; K^{∗}Y]

commutes. Therefore, K^{∗}Y ≅ 1.

(ii) Let X be K^{∗}-finite, and let X [figure: c] Y be a quotient. Ⅎc(R_{ab}) = R_{c(a)c(b)}, so the diagram:

[figure: QX; Ⅎc; QY; K^{∗}X ≅ 1; K^{∗}Y]

commutes. Therefore, K^{∗}Y ≅ 1.

4.4. Remark. This proof in fact gives that if X′ is a subquotient of X, then K^{∗}X′ is a quotient of K^{∗}X.

4.5. Lemma. The disjoint union of two K^{∗}-finite objects is K^{∗}-finite.

Proof. Let X and Y be K^{∗}-finite. There are embeddings of QX and QY into Q(X ⨿ Y) given by q ↦ q ⨿ 1_{Y} and q′ ↦ (X [figure] σ(X)) ⨿ q′ respectively, where σ(X) denotes the support of X, i.e. the image of the unique morphism X [figure] 1. These embeddings both preserve R, and are both quotiented to 1 in K^{∗}(X ⨿ Y), so 1_{X⨿Y} \overline{R}(σ(X) ⨿ σ(Y)). But (σ(X) ⨿ σ(Y))Rσ(X ⨿ Y), so K^{∗}(X ⨿ Y) ≅ 1.

4.6. Corollary. All K̃-finite objects are K^{∗}-finite.

Proof. This is immediate from the preceding lemmas.

For the other direction we will need the following:

4.7. Lemma. [“outduction”] Let Φ(x) be a formula with one free variable x, expressible in the internal language of a topos. Let (n, 0, s) be a numeral in which Φ(sx) ⇒ Φ(x) holds for all x ⩾ l, and suppose (∃y : n)(y ⩾ l ∧ Φ(y)) holds. Then Φ(l) holds.

Proof. Let Ψ(x) = (Φ(x) ⇒ Φ(l)). Clearly Ψ(l) holds, and Ψ(x) ⇒ Ψ(sx) holds for all x : n with x ⩾ l. Therefore, (∀x : n)(x ⩾ l ⇒ (Φ(x) ⇒ Φ(l))), and also, (∃y : n)(y ⩾ l ∧ Φ(y)). Therefore, Φ(l) holds.

4.8. Lemma. If X [figure: y] Y and X [figure: z] Z are quotients of X, and yRz, then Y is K̃-finite if and only if Z is.

Proof. It is sufficient to prove the result when (∃a, b : X̃)(z = y ∧R_{ab}) and Z is K̃-finite, since taking z′ = y ∧ R_{ab} = z ∧ R_{ab} reduces the general case to this one. We know that z′ is K̃-finite as it is a quotient of both y and z, one of which is K̃-finite.

The proof proceeds by induction on Z. If Z is a subsingleton, then Y is a quotient of the union of {a} and {b}, so it is K̃-finite. Now suppose Z = U ∪V, where the hypothesis

holds for Z = U and Z = V. Let Y [figure: f] Z be the factorization of z through y. Let X′ = z^{∗}(U), X′′ = z^{∗}(V). Let R′_{ab} be R_{(a∩X′)(b∩X′)} in QX′, and let R′′_{ab} be R_{(a∩X′′)(b∩X′′)} in QX′′. Then Y = f^{∗}(U) ∪ f^{∗}(V), U = f^{∗}(U) ∧ R′_{ab} and V = f^{∗}(V) ∧ R′′_{ab}, so by the inductive hypothesis, f^{∗}(U) and f^{∗}(V) are K̃-finite. Therefore, Y is also K̃-finite.

Putting this all together gives:

4.9. Theorem. In a topos, E, an object X is K^{∗}-finite if and only if it is K̃-finite.

Proof. One direction is just Corollary 4.6.

For the converse, suppose X is K^{∗}-finite. Define a numeral (n, 0, s) in P QX by letting 0 be {1_{X}}, and letting

sx = {z : QX|(∃y : QX)((y ∈ x) ∧ (yRz))}

Let Φ(x) be the assertion (∃y : QX)(y ∈ x∧K̃_{y}). By Lemma 4.8, Φ(sx) ⇒ Φ(x). Because X is K^{∗}-finite, 1_{X} \overline{R}(X [figure] σ(X)), so

(∃x : n)((X [figure] σ(X)) ∈ x)

Therefore, (∃x : n)(Φ(x)), so by outduction Φ(0) holds, i.e. X is K̃-finite.

4.10. Remark. If R were taken to be (∃a, b : X)(x∧R_{ab} = y ∧R_{ab}), and X were required to have complemented support, then by the same argument as above, the resulting notion of finiteness would be K-finiteness. The only tricky part in this modification is proving the modified version of Lemma 4.8. If z = y ∧ R_{ab} and f is the factorisation of z through y, as in the proof above, and f(a) = f(b) = a′, then for any K-finite subobject Z′ of Z, the preimage f^{∗}(Z′ ∪ {a′}) is K-finite. This is shown by induction on Z′ – It is obvious that this property is preserved under unions, so it is sufficient to prove the result when Z′ is a singleton. If X′=z^{∗}(Z′ ∪ {a′}) then in QX′, z′ = y′ ∧ R_{ab}. Therefore, it is sufficient to prove the case where Z is a singleton {x}. In this case, the following deduction is valid:

(∀x_{1}, x_{2} ∈ f^{∗}(x))((x_{1} = x_{2}) ∨ (x_{2} = a ∨ x_{2} = b))
(∀x_{1} ∈ f^{∗}(x))(f^{∗}(x) ∪ {a, b} = {x_{1}} ∪ {a, b})
(∀x_{1} ∈ f^{∗}(x))(K_{f^{∗}(x)∪{a,b}})
K_{f^{∗}(x)∪{a,b}}

Therefore, f^{∗}(Z′∪{a′}) is K-finite whenever Z′ is, so in particular, Y is K-finite whenever Z is.

So K^{∗}-finiteness gives another way of looking at K̃-finiteness. This other way does give some genuinely new information. It is well known that if K̃X is K̃-finite then so is X. The same is not true for K^{∗}X.

4.11. Example. In the topos [C, \underline{Set}], where C is the 2-element monoid whose non-identity element is idempotent, let X be the representable functor. Then K^{∗}X = 2, so X is not K^{∗}-finite, but K^{∗}X is.

This leads to the following definition:

4.12. Definition. An object X is K^{∗∗}-finite if K^{∗}X is K^{∗}-finite. More generally, X is K^{n∗}-finite for a standard natural number n ⩾ 2 if K^{∗}X is K^{(n−1)∗}-finite, where K^{1∗}- finiteness is just K^{∗}-finiteness.

This definition is weaker than the normal definition of finiteness in \underline{Set} without AC – any bounded amorphous set is K^{∗∗}-finite. To study K^{∗∗}-finiteness more thoroughly, it will be necessary to look at the analogue of amorphous sets in general topoi. Classically the definition of an amorphous set is non-constructive – it assumes that the set has complements. The following is a more constructive definition.

4.13. Definition. An object X, in a topos, is amorphous if whenever Y and Z are subobjects of X, with Y ∩ Z K̃-finite, either Y is K̃-finite, or Z is K̃-finite.

It is bounded amorphous if it is amorphous and there is a j : ñum_{X}, such that for any quotient of X with finite fibres, all but finitely many of the fibres {x ∈ X|f(x) = y} are K̃_{j}-finite. In this case, j is called a bound for X.

Two subobjects X′ and X′′ of X will be said to differ finitely if there is a K̃-finite subobject Y of X, such that Y ∪ X′ = Y ∪ X′′. We will use P^{∗}X to denote the quotient of P X by the relation

X′RX′′ ⇔ (∃Y : K̃X)(Y ∪ X′ = Y ∪ X′′)

For an amorphous object X, the term almost all elements of X will sometimes be used to refer to subobjects of X that differ only finitely from X.

The collection of amorphous objects in a topos is clearly closed under subobjects, but it is not closed under quotients – Let C be the category

\xymatrix{A \ar[dr] \\  & C \\ B \ar[ur]}

and let X be an amorphous set. Then in [C, \underline{Set}] the functor sending A, B and C all to X and all morphisms to the identity on X is amorphous. However, the quotient that sends A and B to X and C to 1 is not amorphous.

In \underline{Set} (even without AC) K^{∗∗}-finite sets are finite unions of bounded amorphous sets (this will follow from the results later in this section). However, this is because if a set has the property that whenever it is partitioned into 3 disjoint parts one is finite, then the set must be a union of 2 amorphous sets, and similarly for sets with larger bounds on the number of infinite parts into which they can be partitioned. However, in a topos, this does not apply. For example, let X be an amorphous set and consider X × ℝ [figure] ℝ in LH/ℝ, where LH is the category of locales and local homeomorphisms between them (the topos LH/ℝ is equivalent to the topos of sheaves on the real numbers). For any 2 K̃-finitely-intersecting subobjects A and B of X × ℝ [figure] ℝ, if A has an infinite fibre at x, then taking a decreasing sequence x_{n} ↘ x, let A_{n} be the set of elements of X that are in all fibres of A above points in the interval [x, x_{n}]. The A_{n} form an increasing sequence of subsets of X whose union is infinite. Therefore, some A_{n} must be infinite (otherwise there would be an infinite subsequence with every A_{n} \ A_{n−1} non-empty, and we could partition X into ⋃_{n=1}^{∞} A_{2n+1} \ A_{2n} and ⋃_{n=1}^{∞} A_{2n} \ A_{2n−1}, both of which are infinite). This means that there must be a finite bound on the fibres of B in an open neighbourhood of x. This means that given any 3 K-finitely intersecting subobjects of X × ℝ [figure] ℝ, and any real number x, one of them has finite fibres on some neighbourhood of x. However, X × ℝ [figure] ℝ is not amorphous, and all its amorphous subobjects are finite, so it is not a union of amorphous sets. We will therefore need the following definition.

4.14. Definition. An object X in a topos, is S-weakly amorphous for some K-finite

numeral S, if for any S [figure: f] P X, with (∀y, z : S)(K̃_{f(y)∩f(z)} ∨(y = z)), there is a K̃-finite f(z) for some z ∈ S. X is weakly amorphous if there is a K-finite numeral S for which it is S-weakly amorphous.

X is bounded weakly amorphous if it is weakly amorphous, and there is some j : ñum_{X}, such that for any quotient R of X, all but finitely many equivalence classes of R are K̃_{j}-finite. Again, j is called a bound for X.

In fact, weak amorphousness is still not enough, as we would like to know that if we partition our object into subobjects whose intersections are S′-weakly amorphous, then one of these subobjects will be S′-weakly amorphous. The appropriate definition is therefore:

4.15. Definition. Let S be a K-finite numeral. An object X is S-pseudo-amorphous if

for any K-finite numeral S′ < S, and any S [figure: f] P X such that for any i, j : S either f(i) ∩ f(j) is S′-pseudo-amorphous or i = j, there is an i : S such that f(i) is S′- pseudo-amorphous, where an object is 0-pseudo-amorphous if it is K̃-finite. X is pseudoamorphous if there is a K-finite numeral S for which it is S-pseudo-amorphous.

Clearly any S-pseudo-amorphous object is weakly amorphous. I have not yet been able to determine whether pseudo-amorphous objects and weakly amorphous objects are in fact the same thing.

The truth of the assertion “X is S-pseudo-amorphous” will sometimes be denoted S-psam_{X}. The definition of bounded pseudo-amorphous is analogous to the definitions of bounded amorphous and bounded weakly amorphous.

The notion of pseudo-amorphousness is not sufficient to describe K^{∗∗}-finiteness. For example, if X is an amorphous set, then in [ω, \underline{Set}], the constantly X functor is bounded weakly amorphous, but it has an infinite number of quotients that are pairwise infinitely different – all the associated sheaves complementary to U for subterminal U, i.e. the quotients identifying any pair of elements to extent U. The problem is that Ω is infinite. If Ω is K-finite, then bounded pseudo-amorphousness is sufficient to ensure K^{∗∗}-finiteness. To fix this problem, we introduce an extra condition on X which will allow our arguments to work as if Ω were K-finite.

4.16. Definition. Given an object X in a topos E, define an equivalence relation R_{X} on Ω, by UR_{X}V if and only if the associated sheaf of X ×(U ∪V) is K̃-finite in Sh_{c(U∩V)}(E).

Let Ω_{X} be the quotient of Ω by the relation R_{X}. Say that X is usually finite if Ω_{X} is K̃-finite.

The remainder of this paper will be devoted to the proof of:

4.17. Theorem. An object X is K^{∗∗}-finite if and only if it is bounded pseudo-amorphous and usually finite.

To motivate what follows, we will start by giving a sketch proof:

Proof (sketch). Only if: We will start by dealing with the case where Ω is K-finite. The general result will follow from this without too much difficulty.

Let j : { \atop num}_{X} be a bound for X. We will show (Theorem 4.22) that P^{∗}X is K̃-finite. Therefore, there are only K̃-finitely many possible collections of infinite equivalence classes up to finite difference. Therefore, if we can show that there are only K̃-finitely many finitary equivalence relations (equivalence relations all of whose equivalence classes are K̃-finite) up to finite difference, then X will be K^{∗∗}-finite, since given any equivalence relation R on X, we can map it to the finitary equivalence relation R′ given by x R′ y if and only if x R y and the R-equivalence class [x]_{R} of x is K̃-finite. We let K_{fin}^{∗}X denote the object of finitary equivalence relations of X up to finite difference.

To show that K_{fin}^{∗}X is K̃-finite, we will start by forming some partially ordered object L of possible ‘sizes’ of K̃-finite subobjects of X. This will give us the morphism

K_{fin}^{∗}X [figure: f] (L^{X})^{∗}, where (L^{X})^{∗} is the quotient of L^{X} that identifies functions that agree on almost all elements of X, sending each equivalence relation R to the function that sends x : X to the ‘size’ of [x]_{R} (the R-equivalence class of x). We will choose L in such a way that (L^{X})^{∗} is a K̃-finite poset with a top element.

We will then use an induction principle on posets of this type (Lemma 4.20) to show that all the fibres of f are K̃-finite. This is where we will need Lemma 4.19 and Lemma 4.23.

If: There is a monomorphism P^{∗}X [figure] K^{∗}X, sending a subobject X′ of X to the equivalence relation that relates two elements of X if they are equal, or they are both in X′. Therefore, if X is K^{∗∗}-finite then P^{∗}X is K̃-finite, so (as we will show in Theorem 4.22) X is pseudo-amorphous and usually finite.

We want to find a bound for X. We construct a morphism X × Q_{fin}X [figure: g] U({ \atop num}_{X}) sending (R, x) to the object of upper bounds on the size of [x]_{R}. We will show (Lemma 4.25) that any weakly amorphous subobject of a numeral is in fact K̃-finite, and therefore has an upper bound. This means that for any finitary relation R, there is an inhabited object i_{R} of upper bounds on the size of [x]_{R}. For each element of K_{fin}^{∗}X, we take the union of the i_{R} for relations on that equivalence class. The intersection of these unions is a K̃-finite intersection of inhabited upsets of a numeral, and is therefore inhabited. An element of this intersection is a bound for X.

4.18. Lemma. (i) If X is K_{sn}-finite, then for any x : X, there is a K_{n}-finite X′ ⊆ X such that X = X′ ∪ {x}.

(ii) If X is K̃_{sn}-finite, then for any x : X, there is a K̃_{n}-finite X′ ⊆ X such that X = X′ ∪ {x}.

Proof. (i) Induction on X. If X is a singleton or empty, the result is obvious. If X = X_{1} ∪ {y}, n = sm and ϕ(n, X_{1}) (i.e. X_{1} is K_{n}-finite) then for any x : X, x ∈ X_{1} ∨ x = y. If x = y, the result is trivial, so suppose x ∈ X_{1}. ϕ(sm, X_{1}), so there is an X′_{1} satisfying ϕ(m, X′_{1}) and X′_{1} ∪ {x} = X_{1}. But now Y = X′_{1} ∪ {y} satisfies ϕ(n, Y) and Y ∪ {x} = X.

(ii) The proof is essentially the same as (i).

As mentioned in the sketch proof, we will need a way of measuring the ‘size’ of an equivalence class in order to get the object L that we use there. We will need this measure of ‘size’ to distinguish proper subobjects, i.e. if A′ ⊆ A are K̃-finite subobjects of X, then we will want A′ and A to have the same ‘size’ only if they are equal. The obvious measure of ‘size’ – sending a K̃-finite subobject A of X to the least i : { \atop num}_{X} for which ϕ_{X}(i, A) – won’t work, as a proper subobject of A can have the same ’size’ as A in this sense (also the least such i may not be defined). One measure of size which does work is the upset U of { \atop num}_{Ω^{X}} given by U = \{i : { \atop num}_{Ω^{X}}|ϕ_{Ω^{X}}(i, Ω^{A})\}. We need to check that this distinguishes proper subobjects:

4.19. Lemma. If A [figure] B is a subobject of a K̃-finite object B, Ω^{B} is K-finite, and (∀j : ñum_{Ω^{B}})(ϕ_{Ω^{B}}(j, Ω^{A}) ⇒ j = sj), then A [figure] B is an isomorphism.

Proof. Fix b : B̃. We will show that (∀i : { \atop num}_{Ω^{B}})(b ∈ Ω^{A} ∨ i = si). We prove this by outduction on i. As { \atop num}_{Ω^{B}} is K-finite, it has a fixed point, which clearly satisfies the hypothesis. Now suppose that si satisfies (b ∈ Ω^{A} ∨ si = ssi). Clearly b ∈ Ω^{A} implies b ∈ Ω^{A} ∨ i = si, so suppose si = ssi. Then ϕ_{Ω^{B}}(si, Ω^{B}), so by Lemma 4.18, there is some subobject C of Ω^{B} such that ϕ_{Ω^{B}}(i, C) ∧ ({b} ∪ C = Ω^{B}). Now as Ω^{A} is injective, we can pick a : Ω^{A} such that b ∈ Ω^{A} ⇒ b = a. Clearly (a ∈ C) ∨ (a = b) as C ∪ {b} = Ω^{B}.

However, if a ∈ C then b ∈ Ω^{A} ⇒ b ∈ C. Since Ω^{A} = (Ω^{A} ∩ C) ∪ (Ω^{A} ∩ {b}), this means that Ω^{A} ⊆ C, and therefore, ϕ_{Ω^{B}}(i, Ω^{A}), whence i = si.

Thus we have (b ∈ Ω^{A}) ∨ (i = si), which completes the outduction, and allows us to deduce that (b ∈ Ω^{A}) ∨ (⊥ = s⊥). However ⊥ = s⊥ never holds, as Ω^{B} has a point. Therefore, we deduce that b ∈ Ω^{A}. As b was arbitrary, B̃ ⊆ Ω^{A}, and thus A ≅ B.

This lemma is related to the fact that Ω is an internal cogenerator (proved by F. Borceux [1]).

The induction principal that we will need to use is the following:

4.20. Lemma. Given a formula Φ(x) in the internal logic of the topos and a K̃-finite partial order L with a top element ⊤, if (∀x : L)(((∀y : L)(y ∈ ↿(x) ⇒ Φ(y))) ⇒ Φ(x)), where ↿(x) = {z : L|(x ⩽ z) ∧ (x = z ⇒ x = ⊤)} and Φ(⊤), then (∀x : L)(Φ(x)).

Proof. Induction on L: if L = {⊤}, then the result is obvious. If L = L′ ∪ x where x is a subsingleton and ⊤ ∈ L′, and the lemma holds for L′, then as for any x′ : x, ↿(x′) ⊆ L′, we have that (∀x′ : x)(∀y : L)(y ∈ ↿(x′) ⇒ Φ(y)), so by hypothesis, Φ(x′). Therefore, for z : L′,

(∀y : L)(y ∈ ↿(z) ⇒ Φ(y)) ⇔ (∀y : L′)(y ∈ ↿(z) ⇒ Φ(y))

Hence, (∀y : L′)(Φ(y)), and thus (∀y : L)(Φ(y)).

4.21. Lemma. For any K̃-finite X, any monomorphism ñum_{X} [figure: f] X is a cover.

Proof. Induction on { \atop num}_{X}. If { \atop num}_{X} = 0, the result is obvious. Let n : { \atop num}_{X} satisfy sn = ssn, and let m : { \atop num}_{X} satisfy sm = n. By Lemma 4.18, there is an X′ ⊆ X such that ϕ_{X}(n, X′) and X = X′ ∪ f(sn). However, f(n) is a member of X, so (f(n) ∈ X′) ∨ (f(n) = f(sn)). But since f is monic, (f(n) = f(sn)) ⇒ (n = sn) which means that X is K̃_{n}-finite. Therefore, in either case, X′′ = X′ ∪ {y} is K̃_{n}-finite. The restriction of f to \{i : { \atop num}_{X}|i ⩽ n\} is therefore a monomorphism into X′, and \{i : { \atop num}_{X}|i ⩽ n\} can be made into a numeral isomorphic to { \atop num}_{X′}. Therefore, by the inductive hypothesis, it is a cover. Thus, f is also a cover.

4.22. Theorem. For any X, P^{∗}X is K̃-finite if and only if X is pseudo-amorphous and usually finite.

Proof. If P^{∗}X is K̃-finite, then the subobject consisting of equivalence classes of subobjects of X of the form X × U for some subterminal U is also K̃-finite, but this subobject is isomorphic to the quotient of Ω by R_{X}, so X is usually finite.

By Lemma 4.21, any morphism { \atop num}_{P^{∗}X} [figure: f] P X whose composite with P X [figure] P^{∗}X is mono covers P^{∗}X. If f satisfies

(∀i, j : { \atop num}_{P^{∗}X})((i = j) ∨ S-psam_{f(i)∩f(j)})

then the composite must either be mono or send some i to an S-pseudo-amorphous object. If it is mono, then it must cover P^{∗}X, so in either case, some i must be sent to an Spseudo-amorphous object in P^{∗}X. Therefore, X is { \atop num}_{P^{∗}X}-pseudo-amorphous.

For the converse, it suffices to show that for any K-finite numeral S, the object P_{S}^{∗}X of R-equivalence classes of subobjects of X that are S-pseudo-amorphous is K̃-finite. P^{∗}X will then be K̃-finite.

Induct on S. If S = 1, then the subobjects in question are K̃-finite and so all equivalent. If S = S_{1} ∪ {s}, then, for any R-closed and downwards closed collection A of S_{1}-pseudo-amorphous subobjects of X, the object of subobjects of X whose S_{1}-pseudo-amorphous subobjects are exactly those in A is K-finite. The object of R-closed and downwards closed families of S_{1}-pseudo-amorphous subobjects of X is K̃-finite, as it is a subquotient of Ω_{X}^{P_{S_{1}}^{∗}X}. Therefore, P_{S}^{∗}X is K̃-finite.

In the proof of Theorem 4.17, we will need to consider refinements of given equivalence relations. An equivalence relation R′ on X is a refinement of an equivalence relation R if any pair of elements related by R′ is also related by R, i.e. if and only if R ⩽ R′ in the order relation on QX. The following lemma will be necessary.

4.23. Lemma. Let X be a usually finite object, and let R be a finitary relation on X, such that for some j : ñum_{X}, all equivalence classes of R are K̃_{j}-finite. Then R has K-finitely many refinements up to finite difference.

Proof. Let T be the object of refinements of R, quotiented by finite difference. There is a morphism T × T [figure: g] P^{∗}X sending a pair of relations (R_{1}, R_{2}) to the object of elements of X whose R_{1} and R_{2} equivalence classes are the same. As almost all equivalence classes of R are K̃_{j}-finite, if we quotient each Q([x]_{R}) (where [x]_{R} denotes the equivalence class of x) by relating two quotients R_{1} and R_{2} if there is a sequence 0 = U_{0} ⩽ U_{1} ⩽ U_{2} ⩽ … ⩽ U_{n} = 1 of subterminal objects such that in each Sh_{c(U_{2n})}(E), U_{2n+1} ⇒ R_{1} = R_{2}, while U_{2n+1} R_{X} U_{2n+2} (i.e. relating two quotients if they agree unless X is finite), then there is a finite numeral k such that all the resulting quotients are K̃_{k}-finite. Therefore, given any subobject T′ of T, either T′ is K̃_{k}-finite, or for almost every equivalence class of R there are two elements of T′ that agree on all elements of this class. Therefore, the image of the restriction of g to T′ × T′ is a K̃-finite collection of subobjects of X whose union is almost the whole of X. Thus, every fibre of g has all of its cliques K̃_{k}-finite (a clique is a subobject of T any two elements of which are either related or equal). Thus, by Ramsey’s theorem, there is some finite numeral l such that T is K̃_{l}-finite.

4.24. Theorem. Let U be a subterminal object. If Ω × U is K-finite and X is bounded pseudo-amorphous with support U, then X is K^{∗∗}-finite.

Proof. As explained in the sketch proof, we need only show that K_{fin}^{∗}X is K̃-finite. Let U({ \atop num}_{Ω^{X}}) denote the object of inhabited upsets in { \atop num}_{Ω^{X}}, with the reverse of

the inclusion ordering. We will consider a morphism K_{fin}^{∗}X [figure: f] (U({ \atop num}_{Ω^{X}})^{X})^{∗}, where (U({ \atop num}_{Ω^{X}})^{X})^{∗} is the quotient of U({ \atop num}_{Ω^{X}})^{X} by the relation which relates two functions if the subobject on which they agree is finitely different from the whole of X. The morphism f is given by f(R)(x) = g(Ω^{[x]_{R}}) where g is the morphism sending a K̃-finite subobject A of Ω^{X} to the object \{i : { \atop num}_{Ω^{X}}|ϕ_{Ω^{X}}(j, A)\} (Ω^{[x]_{R}} is K̃-finite because [x]_{R} is a subobject of X, and therefore has support ⩽ U, so Ω^{[x]_{R}} = (Ω × U)^{[x]_{R}} which is K̃-finite).

Because almost all the [x]_{R} are K̃_{j}-finite, almost all the elements in the image of f(R) are below some fixed \overline{j} : U({ \atop num}_{Ω^{X}}). Let L be the subobject of elements of U({ \atop num}_{Ω^{X}}) that

are less than or equal to \overline{j}. L is K̃-finite, so by considering the morphisms Ω^{L} [figure: (P h)^{∗}] P^{∗}X, we see that the quotient (L^{X})^{∗} of L^{X} under the finite difference relation is a K̃-finite partial order with a top element. We need to show that the inverse image of each element of (L^{X})^{∗} under f is K̃-finite. We do this using the generalised form of induction in Lemma 4.20, where Φ(x) is the assertion that P f({x}) is K̃-finite.

We note that if R′ is a refinement of R and f(R′) = f(R), then R′ and R differ finitely, because [x]′_{R} ⊆ [x]_{R} and if f(R′)(x) = f(R)(x) then [x]′_{R} = [x]_{R} by Lemma 4.19. Φ therefore holds for the top element of L because any R and R′ are both refinements of R ∧ R′.

Now suppose that Φ(h′) holds for every h′ ∈ ↿(h). Let

V = [(∃R : K_{fin}^{∗}X)(f(R) ∈ ↿(h))]

In Sh_{c(V)}(E), there are no relations R with f(R) ∈ ↿(h), so given R_{1} and R_{2} with f(R_{1}) ⩾ h and f(R_{2}) ⩾ h, f(R_{1} ∧ R_{2}) ⩾ h, so f(R_{1} ∧ R_{2}) = h, and therefore, R_{1} and R_{2} differ finitely in Sh_{c(V)}(E). On the other hand, in E/V, any R′ with f(R′) = h is a refinement of one of the relations R with f(R) ∈ ↿(h), so there are only K̃-finitely many possible values for R′ × V by Lemma 4.23 (it is K̃-finite in E, not just in E/V, as the object ↿(x) is K̃-finite in E). Therefore the preimage of h under f has K̃-finite product with V, and K̃-finite associated c(V)-sheaf, so some K̃-finite quotient of it is K̃-finite, and it is therefore K̃-finite.

Therefore, by induction, all the preimages are K̃-finite, and thus, K_{fin}^{∗}X is K̃-finite, and hence X is K^{∗∗}-finite.

4.25. Lemma. Any weakly amorphous subobject of a numeral is K̃-finite.

Proof. Let (n, 0, s) be a numeral, and let X be an S-weakly amorphous subobject of n, where S is a numeral (S, 0, t) with top element ⊤. Let X′ be the downset generated by X. As the downset generated by a single element is K̃-finite, X′ is an S-weakly amorphous union of K̃-finite objects, so it is S-weakly amorphous.

If S satisfies t^{m}(0) = ⊤ for some standard natural number m, then we can partition n into the numerals contained in the prenumerals (n, s^{i}(0), s^{m}) for i = 0, 1, …, m − 1.

This gives a morphism m [figure: f] P n such that for any i, j : m, either i = j or f(i) ∩ f(j)

is K̃-finite. We now form a morphism S [figure: g] P n by g(i) = ⋃{f(j)|t^{j}(0) = i}. For any i_{1}, i_{2} : S, either g(i_{1}) ∩ g(i_{2}) is K̃-finite, or there are j_{1}, j_{2} : m with t^{j_{1}}(0) = i_{1}, t^{j_{2}}(0) = i_{2} and j_{1} = j_{2}, in which case i_{1} = i_{2}. Therefore, as X′ is S-weakly amorphous, there is an i : S for which g(i) ∩ X′ is K̃ − finite. This means that one of the numerals contained in the prenumerals (n, s^{i}(0), s^{m}) ∩ X′ is K̃-finite. However, if the numeral contained in (n, s^{i}(0), s^{m}) ∩ X′ is K̃-finite, then so are the numerals contained in (n, s^{i+1}(0), s^{m}) ∩ X′ and (n, s^{i−1}(0), s^{m}) ∩ X′. Therefore X′ is a K̃-finite union of K̃-finite objects, so it is K̃-finite, and therefore, so is X.

Now we are ready to prove Theorem 4.17.

1. The fact that a K^{∗∗}-finite object is bounded pseudo-amorphous and usually finite was shown in the sketch proof, Lemma 4.25 and Theorem 4.22.

4.26. Lemma. For any object X and any subterminal U, K^{∗}(X × U) × U ≅ K^{∗}X × U.

Proof. The objects Q(X × U) × U and QX × U are isomorphic via the morphisms (⌞R(X ×U)×U⌟, π_{2}) and (⌞RX ×U⌟, π_{2}). These isomorphisms send the quotient R_{ab} for a and b elements of { \atop X × U} ×U to the quotient R_{a′b′} where a′ and b′ are the corresponding elements of X̃×U, and vice versa. Therefore, they preserve the relation on QX×U used in constructing K^{∗}X ×U, and therefore, restrict to an isomorphism between K^{∗}(X ×U)×U and K^{∗}X × U.

2. A bounded pseudo-amorphous usually finite object is K^{∗∗}-finite.

Proof. Let X be a bounded pseudo-amorphous usually finite object. Consider the collection F of subterminal objects U such that X × U is K^{∗∗}-finite. It is clearly downwards closed. It is also closed under R_{X}, since if X × U is K^{∗∗}-finite, then K^{∗}X × U is K̃-finite, so if in Sh_{c(U)}(E), X × V is K^{∗∗}-finite, then K^{∗}X × V is K̃-finite in E. Also, by Theorem 4.24, this collection contains all U such that Ω × U is K̃-finite. Indeed, if it contains U and in Sh_{c(U)}(E), Ω × V is K̃-finite, then it will also contain V, as X × V will be K^{∗∗}-finite in Sh_{c(U)}(E). Therefore, since X is usually finite, F will contain 1, and thus X will be K^{∗∗}-finite.

5. Related notions

There are a number of obvious variations on the notion of a copower object – what about the object of all retracts of X, or the object of all subquotients of X? In this section, we briefly look at these ideas, and show that the former is a weaker notion, in that it does not allow us to construct power objects. However, this means that we may be able to use it in constructions in categories which are not topoi. The latter is as strong a notion as a power object, so perhaps an approach to topos theory based on per objects is possible. The theory of these objects still needs to be developped.

5.1. Definition. In a cartesian category C, a potency object for an object A is an object BA equipped with a retract BA×A [figure] CA [figure] BA×A over BA, such that for any other

retract X × A [figure] Y [figure] X × A over X, there is an unique morphism X [figure: ^{⌈}Y^{⌉}] BA, such

that the retract is a pullback of BA × A [figure] CA [figure] BA × A along X × A [figure: ^{⌈}Y^{⌉}×1] BA × A.

5.2. Proposition. Any cartesian closed category with all finite limits has potency objects.

Proof. Given X, BX is the object of idempotent endomorphisms of X, i.e. the object {f : X^{X}|ff = f}. The retract CX is the image of (π_{1}, ev|_{BX}), where π_{1} is the projection from BX × X to BX, and ev is the evaluation morphism X^{X} [figure] X. This image exists because it is the equalizer of (π_{1}, ev|_{BX}) and 1_{BX×X}. Given a retract A×X [figure] B [figure] A×X, the morphism A [figure] BX is the factorization of the exponential transpose of the composite with π_{2}.

5.3. Proposition. Any regular category with potency objects, such that subobjects of 1 form a Heyting semilattice, is cartesian closed.

Proof. Let k denote the generic endomorphism of B(X × Y) × X × Y. The exponential X^{Y} can be obtained from the object of graphs. A graph is an idempotent endomorphism of X × Y that factors through π_{2}, and whose composite with π_{2} is π_{2}, so X^{Y} is contained in

B′(X × Y) = {f : B(X × Y)|(∃g : (X × Y)^{Y})(f = gπ_{2})}

The idea here is that B′(X × Y) is the object of retracts of X × Y contained in Y. It therefore admits a cover to BY sending a retract of X × Y to its factorization through π_{2}. The exponential X^{Y} will then be the pullback of ^{⌈}1_{Y}^{⌉} along this cover, i.e. the retracts whose image is isomorphic to Y.

To form B′(X × Y), we note that if σ(X) ⩽ σ(Y) then π_{2} is the coequalizer of

\xymatrix{X × Y × Y \ar[r]^{π_{12}} \ar[r]_{π_{13}} & X × Y}

Therefore, f will factor through π_{2} if f has equal composites with π_{12} and π_{13}. We can test this by composing these composites with the monomorphism 1_{X} × Δ_{Y}, where Δ_{Y}

is the diagonal map Y [figure: Δ_{Y}] Y × Y. This gives a retract of X × Y × Y. Therefore, we

construct the morphisms B(X ×Y) [figure: h_{2}] B(X ×Y ×Y) and B(X ×Y) [figure: h_{3}] B(X ×Y ×Y) corresponding to the idempotent endomorphisms Δ_{Y} kπ_{123} and Δ_{Y} kπ_{124} respectively. Now B′(X × Y) will be the product E × (σ(X) ⇒ σ(Y)), where E is the equalizer of h_{2} and

h_{3}. We now construct X^{Y} as the pullback P of ^{⌈}1_{y}^{⌉} along B′(X × Y) [figure: ^{⌈}g^{⌉}] B(Y), where g is the factorization of the endomorphism of B′(X × Y) × X × Y through π_{13} composed with π_{13} on the other side.

A morphism Z [figure] P corresponds to a morphism Z [figure] B′(X × Y), corresponding to a retract of Z × X × Y, that factors through Z × Y. composing this factorization with π_{1} gives a morphism Z × Y [figure] X. Therefore, P is indeed the exponential X^{Y}.

5.4. Proposition. Any cartesian category with disjoint coproducts and potency objects is cartesian closed.

Proof. Let k denote the generic endomorphism of B(X ⨿Y)×(X ⨿Y). The exponential X^{Y} can be obtained from the object of cographs. A cograph is an idempotent endomorphism of X ⨿ Y that factors through ν_{1}, and whose composite with ν_{1} is ν_{1}, so X^{Y} is contained in

B′(X ⨿ Y) = {f : B(X ⨿ Y)|Imf ⊆ ν_{1}}

Since ν_{1} is the equalizer of

\xymatrix{X ⨿ Y \ar[r]^{ν_{12}} \ar[r]_{ν_{13}} & X ⨿ Y ⨿ Y}

an endomorphism f of X ⨿ Y will factor through ν_{1} if and only if it has equal composites with ν_{12} and ν_{13}. If we form the composites ν_{12}f(1 ⨿ ∇_{Y}) and ν_{13}f(1 ⨿ ∇_{Y}), where

Y ⨿ Y [figure: ∇_{Y}] Y is the codiagonal map, we get two retracts of X ⨿ Y ⨿ Y which will be equal if and only if f factors through ν_{1}. We can therefore construct B′(X ⨿ Y) as the equalizer of the two morphisms from B(X ⨿ Y) to B(X ⨿ Y ⨿ Y) corresponding to the composites ν_{12}k(1 × ∇_{Y}) and ν_{13}k(1 × ∇_{Y}).

Factorization through ν_{1} gives a morphism from B′(X ⨿ Y) to BX, and the pullback along this of ^{⌈}1_{X}^{⌉} is easily seen to be the exponential X^{Y}.

5.5. Remark. Some condition besides cartesianess is required to get cartesian closure, since in any partial order with a top element, the top element is a potency object.

5.6. Definition. Given an object A in a cartesian category C, a per object for A is an object ΨA equipped with a cover ΨA×A [figure: q]∋ through which the projection ΨA×A [figure: π_{1}] ΨA factors, and a subobject ΦA [figure]∋ such that for any other cover X × A [figure: x] Y through

which π_{1} factors, and any subobject Z [figure] Y, there is an unique morphism X [figure: ⌜Z⌟] ΨA such that in the following diagram:

[figure: Z; ΦA; Y; ∋; X; ΨA]

both small squares are pullbacks, and the morphism Y [figure]∋ commutes with x and q(⌜Z⌟ × 1_{A}).

5.7. Remark. The object ΦA is the object of ordered pairs (ψ, x) where ψ is a subquotient of A and x is an element of ψ, while ∋ is the object of ordered pairs (ψ, a), where ψ is still a subquotient of A, but a is now any element of the quotient of A involved in the construction of ψ.

5.8. Proposition. A topos has per objects.

Proof. The per object ΨX is just the object of symmetric transitive relations on X, which is a subobject of P (X × X).

5.9. Proposition. A cartesian category with per objects is a topos.

Proof. Given an object X in E, let ΨX [figure: ξ] ΨX correspond to the subobject ∈ of ΨX × X, which is the pullback of ΦX [figure]∋ along ΨX × X [figure]∋, viewed as a subquotient of ΨX × X whose quotient part is the identity. The image of ξ is then the power object P X. Given any R [figure] A×X, ξ⌜R⌟ = ⌜R⌟, so ⌜R⌟ factors uniquely through P X, so P X is the power object.

References

[1] F. Borceux. When is Ω a cogenerator in a topos? Cah. Top. Geo. Diff., 16:1–5, 1975.

[2] P. J. Freyd. Numerology in topoi. Th. App. Cat., 16:522–528, 2006.

[3] G. Grätzer and E. T. Schmidt. Characterizations of congruence lattices of abstract algebras. Acta Sci. Math. (Szeged), 24:34–59, 1963.

[4] P. T. Johnstone. Sketches of an Elephant: a Topos Theory Compendium, volume 1 and 2. Clarendon Press, 2002.

[5] P. Pudlák and J. Tůma. Every finite lattice can be embedded in a finite partition lattice. Alg. Univ., 10:74–95, 1980.

[6] J. K. Truss. The structure of amorphous sets. Ann. Pure Appl. Logic, 73:191–233, 1995.

[7] P. M. Whitman. Lattices, equivalence relations and subgroups. Bull. AMS, 52:507– 522, 1946.

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

Email: tkenney@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/16/32/16-32.{dvi,ps,pdf}

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}TEX2e 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@uottawa.ca Lawrence Breen, Université de Paris 13: breen@math.univ-paris13.fr Ronald Brown, University of North Wales: r.brown@bangor.ac.uk 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