Barr asks if it is known that the category of sets is an EMBAR CATEGORY, that is, if for every endofunctor on the category of sets it is the case that the canonical map from the initial algebra to the final coalgebra is monic (assuming, of course, that both exist). Herewith is a proof. First, however, some counterexamples. On any category suppose that f: A -> B is a map such that there is no map at all from B back to A. Then there is an endofunctor, T, such that A is an initial T-algebra, B is a final T-coalgebra and f is the canonical map. For example: TX = if there's a map X -> A then A else B. T(x:X -> Y) = if TX = TY then 1:TX -> TY else f: A -> B. This construction says that embar categories are a bit rare. If a topos (indeed, any positive prelogos) is embar then it is two- valued, that is, if there's a proper non-trivial subterminator, 0 < U < 1, then the map U+U -> 1 is not monic but is as required for the above construction. The only boolean embar topoi are well-pointed. Embarcation is therefore very fragile under slicing. (sets)/X is embar iff X = 0 or 1. The category of G-sets is embar iff the group G is trivial but (G-sets)/G is always embar (where the last G means the regular G-set). But booleaness is not necessary for embar. The proof below works for the category of S-sets where S is the sierpinski monoid (0,1 under multiplication). The relevant property is that all non-zero objects be injective. I will say that a PRE-INVARIANT OBJECT for an endofunctor, T, is a _monomorphism_ TA -> A. (If it's an isomorphism it's an invariant object.) A MINIMAL PRE-INVARIANT OBJECT is one that contains no proper pre-invariant objects, that is, one such that for every commutative diagram of monomorphisms: TA' -> TA | | A' -> A it is the case that the horizontal maps are isomorphisms. Recalling the co-Lambek lemma that the structure map of any final coalgebra is an isomorphism one can easily see that the following proposition says that the category of sets is embar: Proposition: Let T be an endofunctor on the category of sets. Any pre- invariant object for T contains a minimal pre-invariant object. Any minimal pre-invariant object is an initial algebra. Proof: If T0 = 0 everything is quite clear. We suppose therefore that T0 is non-empty. Let m: TA -> A be a monic. Let K be the subset of A defined as the image of (T0 -> TA -> A). Let P be the lattice of all subsets of A that contain K. Consider the order-preserving endofunction, t, on P that sends A' to the image of (TA' -> TA -> A). By Tarski, if it isn't the case that there's a minimal pre-fixed point for t. But since T preserves all monomorphisms from non-empty sources, pre-fixed points of t are automatically pre-invariant objects for T. So there. Now suppose that m: TA -> A is minimal pre-invariant. Let b: TB -> B be arbitrary. Now let K be the partial map from A to B whose graph is the image of (T0 -> (TA)x(TB) -> AxB). Let P be the CPO of all partial maps from A to B that contain K. Let t be the order-preserving endofunction that sends a partial map tabled by A' to the partial map tabled by TA' / \ / \ A B TA TB / \ A B. By Scott, if it isn't the case that we have a fixed point for t. The domain of this partial map is a pre-invariant object, therefore it's all of A. The partial map is a map. If there were two T-algebra maps from A to B their equalizer would have to be smaller pre-invariant object. So there aren't two maps. Done. ==============================