Properties of categories enriched over the category of metric spaces are investigated and applied to a study of well-known constructions of metric and Banach spaces. We prove e.g. that weighted limits and colimits exist in a metric-enriched category iff ordinary limits and colimits exist and epsilon-(co)equalizers are given by epsilon-(co)isometries for all E.
A number of categories is presented that are algebraically complete and cocomplete, i.e., every endofunctor has an initial algebra and a terminal coalgebra. Example: assuming GCH, the category Set(<=lambda ) of sets of power at most lambda has that property, whenever lambda is an uncountable regular cardinal.
For a number of locally finitely presentable categories K we describe the codensity monad of the full embedding of all finitely presentable objects into K. We introduce the concept of D-ultrafilter on an object, where Dis a "nice" cogenerator of K. We prove that the codensity monad assigns to every object an object representing all D-ultrafilters on it. Our result covers e.g. categories of sets, vector spaces, posets, semilattices, graphs and M-sets for finite commutative monoids M. (C) 2020 Elsevier Inc. All rights reserved.
Finitary monads on Pos are characterized as precisely the free-algebra monads of varieties of algebras. These are classes of ordered algebras specified by inequations in context. Analogously, finitary enriched monads on Pos are characterized: here we work with varieties of coherent algebras which means that their operations are monotone.
On the behaviour of coalgebras with side effects and algebras with effectful iteration
For every finitary monad T on sets and every endofunctor F on the category of T-algebras, we introduce the concept of an ffg-Elgot algebra for F, i.e. an algebra admitting coherent solutions for finite systems of recursive equations with effects represented by the monad T. The goal is to study the existence and construction of free ffg-Elgot algebras. To this end, we investigate the locally ffg fixed point phi(F), i.e. the colimit of all F-coalgebras with free finitely generated carrier, which is shown to be the initial ffg-Elgot algebra. This is the technical foundation for our main result: the category of ffg-Elgot algebras is monadic over the category of T-algebras.
Approximate coalgebra homomorphisms and approximate solutions
Terminal coalgebras ν F of finitary endofunctors F on categories called strongly lfp are proved to carry a canonical ultrametric on their underlying sets. The subspace formed by the initial algebra μ F has the property that for every coalgebra A we obtain its unique homomorphism into ν F as a limit of a Cauchy sequence of morphisms into μ F called approximate homomorphisms. The concept of a strongly lfp category includes categories of sets, posets, vector spaces, boolean algebras, and many others. For the free completely iterative algebra Ψ B on a pointed object B we analogously present a canonical ultrametric on its underlying set. The subspace formed by the free algebra φ B on B has the property that for every recursive equation in Ψ B we obtain the unique solution as a limit of a Cauchy sequence of morphisms into φ B called approximate solutions. A completely analogous result holds for the free iterative algebra RB on B.
Every category K has a free completion PK under colimits and a free completion Sigma K under coproducts. A number of properties of K transfer to PK and Sigma K (e.g., completeness or cartesian closedness). We prove that PK is often a pretopos, but, for K large, seldom a topos. Moreover, for complete categories K we prove that PK is locally cartesian closed whenever K is additive or cartesian closed or dual to an extensive category. We also prove that PK is (co)wellpowered if K is a 'set-like' category, but it is neither wellpowered nor cowellpowered for a number of important categories. (C) 2019 Elsevier B.V. All rights reserved.
For every finitary set functor F we demonstrate that free algebras carry a canonical partial order. In case F is bicontinuous, we prove that the cpo obtained as the conservative completion of the free algebra is the free completely iterative algebra. Moreover, the algebra structure of the latter is the unique continuous extension of the algebra structure of the free algebra. For general finitary functors the free algebra and the free completely iterative algebra are proved to be posets sharing the same conservative completion. And for every recursive equation in the free completely iterative algebra the solution is obtained as the join of an ω-chain of approximate solutions in the free algebra.
This paper studies fundamental questions concerning category-theoretic models of induction and recursion. We are concerned with the relationship between well-founded and recursive coalgebras for an endofunctor. For monomorphism preserving endofunctors on complete and well-powered categories every coalgebra has a well-founded part, and we provide a new, shorter proof that this is the coreflection in the category of all well-founded coalgebras. We present a new more general proof of Taylor’s General Recursion Theorem that every well-founded coalgebra is recursive, and we study conditions which imply the converse. In addition, we present a new equivalent characterization of well-foundedness: a coalgebra is well-founded iff it admits a coalgebra-to-algebra morphism to the initial algebra.
Among cocomplete categories, the locally presentable ones can be defined as those with a strong generator consisting of presentable objects. Assuming Vopenka's Principle, we prove that a cocomplete category is locally presentable if and only if it has a colimit dense subcategory and a generator consisting of presentable objects. We further show that a 3-element set is colimit-dense in Set(op), and spaces of countable dimension are colimit-dense in Vec(op).
For finitary regular monads T on locally finitely presentable categories we characterize the finitely presentable objects in the category of T-algebras in the style known from general algebra: they are precisely the algebras presentable by finitely many generators and finitely many relations.
Generalized Eilenberg Theorem: Varieties of Languages in a Category
For finite automata as coalgebras in a category C, we study languages they accept and varieties of such languages. This generalizes Eilenberg's concept of a variety of languages, which corresponds to choosing as C the category of Boolean algebras. Eilenberg established a bijective correspondence between pseudovarieties of monoids and varieties of regular languages. In our generalization, we work with a pair C/D of locally finite varieties of algebras that are predual, i.e., dualize, on the level of finite algebras, and we prove that pseudovarieties D-monoids bijectively correspond to varieties of regular languages in C. As one instance, Eilenberg's result is recovered by choosing D = sets and C = Boolean algebras. Another instance, Pin's result on pseudovarieties of ordered monoids, is covered by taking D = posets and C = distributive lattices. By choosing as C = D the self-predual category of join-semilattices, we obtain Polak's result on pseudovarieties of idempotent semirings. Similarly, using the self-preduality of vector spaces over a finite field K, our result covers that of Reutenauer on pseudovarieties of K-algebras. Several new variants of Eilenberg's theorem arise by taking other predualities, e.g., between the categories of non-unital Boolean rings and of pointed sets. In each of these cases, we also prove a local variant of the bijection, where a fixed alphabet is assumed and one considers local varieties of regular languages over that alphabet in the category C.
A simple criterion for a functor to be finitary is presented: we call F finitely bounded if for all objects X every finitely generated subobject of F X factorizes through the F-image of a finitely generated subobject of X. This is equivalent to F being finitary for all functors between ‘reasonable’ locally finitely presentable categories, provided that F preserves monomorphisms. We also discuss the question when that last assumption can be dropped. The answer is affirmative for functors between categories such as Set, K-Vec (vector spaces), boolean algebras, and actions of any finite group either on Set or on K-Vec for fields K of characteristic 0. All this generalizes to locally λ-presentable categories, λ-accessible functors and λ-presentable algebras. As an application we obtain an easy proof that the Hausdorff functor on the category of complete metric spaces is ℵ1-accessible.
On functors preserving coproducts and algebras with iterativity
An algebra for a functor H is called completely iterative (cia, for short) if every flat recursive equation in it has a unique solution. Every cia is corecursive, i.e., it admits a unique coalgebra-to-algebra morphism from every coalgebra. If the converse also holds, H is called a cia functor. We prove that whenever the base category is hyper-extensive (i.e. countable coproducts are 'well-behaved') and H preserves countable coproducts, then H is a cia functor. Surprisingly few cia functors exist among standard finitary set functors: in fact, the only ones are those preserving coproducts; they are given by X bar right arrow W x (-) + Y for some sets W and Y. (C) 2019 Elsevier B.V. All rights reserved.
On terminal coalgebras derived from initial algebras
A number of important set functors have countable initial algebras, but terminal coalgebras areuncountable or even non-existent. We prove that the countable cardinality is an anomaly: every setfunctor with an initial algebra of a finite or uncountable regular cardinality has a terminal coalgebraof the same cardinality.We also present a number of categories that are algebraically complete and cocomplete, i.e.,every endofunctor has an initial algebra and a terminal coalgebra.Finally, for finitary set functors we prove that the initial algebraμFand terminal coalgebraνFcarry a canonical ultrametric with the joint Cauchy completion. And the algebra structure ofμFdetermines, by extending its inverse continuously, the coalgebra structure ofνF.
A Formula for Codensity Monads and Density Comonads
For a functor F whose codomain is a cocomplete, cowellpowered category K with a generator S we prove that a codensity monad exists iff for every object s in S all natural transformations from K( X, F-) to K( s, F-) form a set. Moreover, the codensity monad has an explicit description using the above natural transformations. Concrete examples are presented, e.g., the codensity monad of the power-set functor P assigns to every set X the set of all nonexpanding endofunctions of PX. Dually, a set-valued functor F is proved to have a density comonad iff all natural transformations from X-F to 2(F) form a set. Moreover, that comonad assigns to X the set of all those transformations. For preimages-preserving endofunctors F of Set we prove that F has a density comonad iff F is accessible.
This is a survey on fixed points of endofunctors, including initial algebras and terminal coalgebras. We also consider the rational fixed point, a canonical domain of behavior for finitely presentable systems. In addition to the basic existence theorems for fixed points, several new results are presented. For example, the Smyth-Plotkin theorem that locally continuous endofunctors of DCPO have terminal coalgebras is derived from a new result stating that every locally monotone endofunctor with a fixed point has a terminal coalgebra. We introduce bounded endofunctors on abstract categories and prove that they have terminal coalgebras. We study well-founded coalgebras and prove that for set functors, the largest well-founded coalgebra of every fixed point is the initial algebra. Another new result concerns mixed fixed points: initial algebras and terminal coalgebras of a parametrized accessible functor always form accessible functors. (C) 2017 Elsevier Inc. All rights reserved.
For every finitary monad T on sets and every endofunctor F on the category of T-algebras we introduce the concept of an ffg-Elgot algebra for F, that is, an algebra admitting coherent solutions for finite systems of recursive equations with effects represented by the monad T. The goal of this paper is to study the existence and construction of free ffg-Elgot algebras. To this end, we investigate the locally ffg fixed point φF, the colimit of all F-coalgebras with free finitely generated carrier, which is shown to be the initial ffg-Elgot algebra. This is the technical foundation for our main result: the category of ffg-Elgot algebras is monadic over the category of T-algebras.
A PRESENTATION OF BASES FOR PARAMETRIZED ITERATIVITY
Finitary monads on a locally finitely presentable category A are wellknown to possess a presentation by signatures and equations. Here we prove that, analogously, bases on A , i.e., finitary functors from A to the category of finitary monads on A , possess a presentation by parametrized signatures and equations.
Algebra and local presentability: how algebraic are they? (A survey)
42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2017. p. 1-14. ISSN 1868-8969. ISBN 978-3-95977-046-0.
Eilenberg-type correspondences, relating varieties of languages (e.g., of finite words, infinite words, or trees) to pseudovarieties of finite algebras, form the backbone of algebraic language theory. We show that they all arise from the same recipe: one models languages and the algebras recognizing them by monads on an algebraic category, and applies a Stone-type duality. Our main contribution is a variety theorem that covers e.g. Wilke’s and Pin’s work on ∞-languages, the variety theorem for cost functions of Daviaud, Kuperberg, and Pin, and unifies the two categorical approaches of Bojańczyk and of Adámek et al. In addition we derive new results, such as an extension of the local variety theorem of Gehrke, Grigorieff, and Pin from finite to infinite words.
Given an order-enriched category, it is known that all its KZ-monadic subcategories can be described by Kan-injectivity with respect to a collection of morphisms. We prove the analogous result for Kan-injectivity with respect to a collection H of commutative squares. A square is called a Kan-injective consequence of H if by adding it to H Kan-injectivity is not changed.
Fixed Points of Set Functors: How Many Iterations are Needed?
The initial algebra for a set functor can be constructed iteratively via a well-known transfinite chain, which converges after a regular infinite cardinal number of steps or at most three steps. We extend this result to the analogous construction of relatively initial algebras. For the dual construction of the terminal coalgebra Worrell proved that if a set functor is alpha-accessible, then convergence takes at most alpha + alpha steps. But until now an example demonstrating that fewer steps may be insufficient was missing. We prove that the functor of all alpha-small filters is such an example. We further prove that for beta aecurrency sign alpha the functor of all alpha-small beta-generated filters requires precisely alpha + beta steps and that a certain modified power-set functor requires precisely alpha steps. We also present an example showing that whether a terminal coalgebra exists at all does not depend solely on the object mapping of the given set functor. (This contrasts with the fact that existence of an initial algebra is equivalent to existence of a mere fixed point.).
Injectivity of objects with respect to a set H of morphisms is an important concept of algebra, model theory and homotopy theory. Here we study the logic of injectivity consequences of H, by which we understand morphisms h such that injectivity with respect to H implies injectivity with respect to h. We formulate three simple deduction rules for the injectivity logic and for its finitary version where morphisms between finitely ranked objects are considered only, and prove that they are sound in all categories, and complete in all "reasonable" categories.
We introduce so-called Elgot algebras and propose them as a convenient structure for semantics. Elgot algebrais an algebra with a specified solution for every flat system of recursive equations. This specification must satisfy two well motivated axioms.
Iterative algebras are defined by the property that every guarded system of recursive equations has a unique solutions. We prove that they have a much stronger property: every system of recursive equations has a unique strict solution.
Iterative theories, which were introduced by Calvin Elgot, formalise potentially infinite computations as unique solutions of recursive equations. One of the main results of Elgot and his coauthors is a description of a free iterative theory as the theory of all rational trees. Their algebraic proof of this fact is extremely complicated. In our paper we show that by starting with iterative algebras, that is, algebras admitting a unique solution of all systems of flat recursive equations, a free iterative theory is obtained as the theory of free iterative algebras. The (coalgebraic) proof we present is dramatically simpler than the original algebraic one. Despite this, our result is much more general: we describe a free iterative theory on any finitary endofunctor of every locally presentable category.
Morita Equivalence of Many-sorted Algebraic Theories
Algebraic theories are called Morita equivalent provided that the corresponding varieties of algebras are equivalent. Generalizing Dukarm's result from one-sorted theories to many-sorted ones, we prove that all theories Morita equivalent to an S-sorted theory T are obtained as idempotent modifications of T. This is analogous to the classical result of Morita that all rings Morita equivalent to a ring R are obtained as idempotent modifications of matrix rings of R. (c) 2006 Published by Elsevier Inc.
Pure epimorphisms in categories pro-C, which essentially are just inverse limits of split epimorphisms in C, were recently studied by J. Dydak and F.R.R. del Portal in connection with Borsuk's problem of descending chains of retracts of ANRs. We prove that pure epimorphisms are regular epimorphisms whenever C has weak finite limits, or pullbacks, or copowers. This improves the results of the above paper, and the results of the present authors on pure subobjects in accessible categories. We also turn to pure monomorphisms in pro-C, essentially just inverse limits of split monomorphisms in C, and prove that they are regular monomorphisms whenever C has finite products or pushouts. (c) 2005 Elsevier B.V. All rights reserved.
Every finitary endofunctor H of Set can be represented via a finitary signature Sigma and a collection of equations called "basic". We describe a terminal coalgebra for Has the terminal Sigma-coalgebra (of all E-trees) modulo the congruence of applying the basic equations potentially infinitely often. As an application we describe a free iterative theory on H (in the sense of Calvin Elgot) as the theory of all rational E-trees modulo the analogous congruence. This yields a number of new examples of iterative theories, e.g., the theory of all strongly extensional, rational, finitely branching trees, free on the finite power-set functor, or the theory of all binary, rational unordered trees, free on one commutative binary operation. (c) 2006 Elsevier Inc. All rights reserved.
By Rutten's dualization of the Birkhoff Variety Theorem, a collection of coalgebras is a covariety (i.e., is closed under coproducts, subcoalgebras, and quotients) iff it can be presented by a subset of a cofree coalgebra. We introduce inference rules for these subsets, and prove that they are sound and complete. For example, given a polynomial endofunctor of a signature Sigma, the cofree coalgebra consists of colored Sigma-trees, and we prove that a set T of colored trees is a logical consequence of a set S iff T contains every tree such that all recolorings of all its subtrees lie in S. Finally, we characterize covarieties whose presentation needs only n colors.
Birkhoff Varitey Theorem with and without Free Algebras
We present a full characterization of those set functors for which the appropriate generalization of Birkhoff's Variety Theorem is valid (under the assumption of preservation of preimages): they are precisely the functors for which free algebras exist. The assumption of preservation of preimages is relatively weak; it cannot be omitted from the above result, as a counter-example in the article demonstrates.
An example constructed in this article demostrates that coequational presentations in the sense of J. Rutten are not sufficient for covarieties in general. However, a "natural" generalization of the concept of coequation is presented which makes the full strength of the dual of Birkhoff's Variety Theorem valid.
The coalgebraic proof of the existence of a free iterative theory is given. The proof uses a concept of iterative algebras and is much simpler and more general than the original proof given by Calvin Elgot and his collaborators.
The category Class of classes is proved to have a number of properties suitable for algebra and coalgebra: for example, every endofunctor is set-based, has an initial algebra and final coalgebra. A description of a final coalgebra of the power-set functor is given
We introduce the concept of a pure epimorphism as an analogy of pure monomorphisms, and we prove basic relationships. For example, in abelian categories pure epimorphisms are precisely the cokernels of pure monomorphisms, and the other way round
Finitary quasivarieties are characterized categorically by the existence of colimits and of an abstractly finite, regularly projective regular generator G. Analogously, infinitary quasivarieties are characterized: one drops the assumption that G be abstractly finite. For (finitary) varieties the characterization is similar: the regular generator is assumed to be exactly projective, i.e., hom(G, −) is an exact functor. These results sharpen the classical characterization theorems of Lawvere, Isbell and other authors.
For Coalgebras on a polynomial functor the existence of a multifree family, viz, the family of all tree coalgebras, is proved. As a consequence, these categories of coalgebras are proved to the locally finitely presentable
Analogously to the fact that Lawvere's algebraic theories of (finitary) varieties are precisely the small categories with finite products, we prove that (i) algebraic theories of many-sorted quasivarieties are precisely the small, left exact categories with enough regular injectives and (ii) algebraic theories of many-sorted Horn classes are precisely the small left exact categories with enough M-injectives, where M is a class of monomorphisms closed under finite products and containing all regular monomorphisms. We also present a Gabriel-Ulmer-type duality theory for quasivarieties and Horn classes. (C) 1998 Academic Press.
Finitary sketches, i.e., sketches with finite-limit and finite-colimit specifications, are proved to be as strong as geometric sketches, i.e., sketches with finite-limit and arbitrary colimit specifications. Categories sketchable by such sketches are fully characterized in the infinitary first-order logic: they are axiomatizable by sigma-coherent theories, i.e., basic theories using finite conjunctions, countable disjunctions, and finite quantifications. The latter result is absolute; the equivalence of geometric and finitary sketches requires (in fact, is equivalent to) the non-existence of measurable cardinals.
Classes of objects injective w.r.t. specified morphisms are known to be closed under products and retracts. We prove the converse: a class of objects in a locally presentable category is an injectivity class iff it is closed under products and retracts. This result requires a certain large-cardinal principle.
The Category of Uniform Spaces as a Completion of the Category of Metric Spaces