Menu
EN

Vyhledávání

Lidé

prof. RNDr. Jiří Adámek, DrSc.

Všechny publikace

A categorical view of varieties of ordered algebras

  • DOI: 10.1017/S0960129521000463
  • Odkaz: https://doi.org/10.1017/S0960129521000463
  • Pracoviště: Katedra matematiky
  • Anotace:
    It is well known that classical varieties of Sigma-algebras correspond bijectively to finitary monads on Set. We present an analogous result for varieties of ordered Sigma-algebras, that is, categories of algebras presented by inequations between Sigma-terms. We prove that they correspond bijectively to strongly finitary monads on Pos. That is, those finitary monads which preserve reflexive coinserters. We deduce that strongly finitary monads have a coinserter presentation, analogous to the coequalizer presentation of finitary monads due to Kelly and Power. We also show that these monads are linings of finitary monads on Set. Finally, varieties presented by equations are proved to correspond to extensions of finitary monads on Set to strongly finitary monads on Pos.

Approximate injectivity and smallness in metric-enriched categories

  • DOI: 10.1016/j.jpaa.2021.106974
  • Odkaz: https://doi.org/10.1016/j.jpaa.2021.106974
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Varieties of Qantitative Algebras and Their Monads

  • Autoři: prof. RNDr. Jiří Adámek, DrSc.,
  • Publikace: Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science. New York: Association for Computing Machinery, 2022. p. 1-10. ISSN 1043-6871. ISBN 978-1-4503-9351-5.
  • Rok: 2022
  • DOI: 10.1145/3531130.3532405
  • Odkaz: https://doi.org/10.1145/3531130.3532405
  • Pracoviště: Katedra matematiky
  • Anotace:
    Quantitative Σ-algebras, where Σ is a signature with countable arities, are Σ-algebras equipped with a metric making all operations nonexpanding. They have been studied by Mardare, Panangaden and Plotkin who also introduced c-basic quantitative equations for regular cardinals c. Categories of quantitative algebras that can be presented by such equations for c = ℵ1 are called ω1-varieties. We prove that they are precisely the monadic categories , where is a countably basic monad on the category of metric spaces. For Σ finitary one speaks about ω-varieties for c = ℵ0. If all spaces used are restricted to UMet, the category of ultrametric spaces, then ω-varieties are precisely the monadic categories , where is a finitely basic monad.

ALGEBRAIC COCOMPLETENESS AND FINITARY FUNCTORS

  • DOI: 10.23638/LMCS-17(2:23)2021
  • Odkaz: https://doi.org/10.23638/LMCS-17(2:23)2021
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

D-ultrafilters and their monads

  • DOI: 10.1016/j.aim.2020.107486
  • Odkaz: https://doi.org/10.1016/j.aim.2020.107486
  • Pracoviště: Katedra matematiky
  • Anotace:
    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 the category of posets

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Ford, C., Milius, S., Schroeder, L.
  • Publikace: Mathematical Structures in Computer Science. 2021, 31(7), 799-821. ISSN 0960-1295.
  • Rok: 2021
  • DOI: 10.1017/S0960129521000360
  • Odkaz: https://doi.org/10.1017/S0960129521000360
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Initial algebras without iteration

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Milius, S., Moss, L.S.
  • Publikace: 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021. p. 1-20. Leibniz International Proceedings in Informatics (LIPIcs). vol. 211. ISSN 1868-8969. ISBN 978-3-95977-212-9.
  • Rok: 2021
  • DOI: 10.4230/LIPIcs.CALCO.2021.5
  • Odkaz: https://doi.org/10.4230/LIPIcs.CALCO.2021.5
  • Pracoviště: Katedra matematiky
  • Anotace:
    The Initial Algebra Theorem by Trnková et al. states, under mild assumptions, that an endofunctor has an initial algebra provided it has a pre-fixed point. The proof crucially depends on transfinitely iterating the functor and in fact shows that, equivalently, the (transfinite) initial-algebra chain stops. We give a constructive proof of the Initial Algebra Theorem that avoids transfinite iteration of the functor. For a given pre-fixed point A of the functor, it uses Pataraia’s theorem to obtain the least fixed point of a monotone function on the partial order formed by all subobjects of A. Thanks to properties of recursive coalgebras, this least fixed point yields an initial algebra. We obtain new results on fixed points and initial algebras in categories enriched over directed-complete partial orders, again without iteration. Using transfinite iteration we equivalently obtain convergence of the initial-algebra chain as an equivalent condition, overall yielding a streamlined version of the original proof.

On the behaviour of coalgebras with side effects and algebras with effectful iteration

  • DOI: 10.1093/logcom/exab049
  • Odkaz: https://doi.org/10.1093/logcom/exab049
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Which categories are varieties?

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Rosický, J.
  • Publikace: 9th Conference on Algebra and Coalgebra in Computer Science (CALCO 2021). Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2021. p. 1-14. Leibniz International Proceedings in Informatics (LIPIcs). vol. 211. ISSN 1868-8969. ISBN 978-3-95977-212-9.
  • Rok: 2021
  • DOI: 10.4230/LIPIcs.CALCO.2021.6
  • Odkaz: https://doi.org/10.4230/LIPIcs.CALCO.2021.6
  • Pracoviště: Katedra matematiky
  • Anotace:
    Categories equivalent to single-sorted varieties of finitary algebras were characterized in the famous dissertation of Lawvere. We present a new proof of a slightly sharpened version: those are precisely the categories with kernel pairs and reflexive coequalizers having an abstractly finite, effective strong generator. A completely analogous result is proved for varieties of many-sorted algebras provided that there are only finitely many sorts. In case of infinitely many sorts a slightly weaker result is presented: instead of being abstractly finite, the generator is required to consist of finitely presentable objects.

Approximate coalgebra homomorphisms and approximate solutions

  • Autoři: prof. RNDr. Jiří Adámek, DrSc.,
  • Publikace: Coalgebraic Methods in Computer Science. Cham: Springer International Publishing, 2020. p. 11-31. ISSN 0302-9743. ISBN 978-3-030-57200-6.
  • Rok: 2020
  • DOI: 10.1007/978-3-030-57201-3_2
  • Odkaz: https://doi.org/10.1007/978-3-030-57201-3_2
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

How nice are free completions of categories?

  • DOI: 10.1016/j.topol.2019.106972
  • Odkaz: https://doi.org/10.1016/j.topol.2019.106972
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

On free completely iterative algebras

  • Autoři: prof. RNDr. Jiří Adámek, DrSc.,
  • Publikace: Leibniz International Proceedings in Informatics, LIPIcs. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2020. p. 1-21. ISSN 1868-8969. ISBN 978-3-95977-132-0.
  • Rok: 2020
  • DOI: 10.4230/LIPIcs.CSL.2020.7
  • Odkaz: https://doi.org/10.4230/LIPIcs.CSL.2020.7
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

On Well-Founded and Recursive Coalgebras

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Milius, S., Moss, L.S.
  • Publikace: Lecture Notes in Computer Science. Basel: Springer, 2020. p. 17-36. vol. 12077. ISSN 0302-9743. ISBN 978-3-030-45230-8.
  • Rok: 2020
  • DOI: 10.1007/978-3-030-45231-5_2
  • Odkaz: https://doi.org/10.1007/978-3-030-45231-5_2
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Colimit-dense subcategories

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Brooke-Taylor, Andrew D., Campion, T., Positselski, L.
  • Publikace: Commentationes Mathematicae Universitatis Carolinae. 2019, 60(4), 447-462. ISSN 0010-2628.
  • Rok: 2019
  • DOI: 10.14712/1213-7243.2019.021
  • Odkaz: https://doi.org/10.14712/1213-7243.2019.021
  • Pracoviště: Katedra matematiky
  • Anotace:
    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).

Finitely presentable algebras for finitary monads

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Milius, S., Sousa, L., Wissmann, T.
  • Publikace: Theory and Applications of Categories. 2019, 34 1179-1195. ISSN 1201-561X.
  • Rok: 2019
  • Pracoviště: Katedra matematiky
  • Anotace:
    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

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Milius, S., Myers, Robert S. R., Urbat, H.
  • Publikace: ACM Transactions on Computational Logic. 2019, 20(1), 1-47. ISSN 1529-3785.
  • Rok: 2019
  • DOI: 10.1145/3276771
  • Odkaz: https://doi.org/10.1145/3276771
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

On finitary functors

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Milius, S., Sousa, L., Wissmann, T.
  • Publikace: Theory and Applications of Categories. 2019, 34 1134-1164. ISSN 1201-561X.
  • Rok: 2019
  • Pracoviště: Katedra matematiky
  • Anotace:
    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

  • DOI: 10.1016/j.tcs.2019.01.018
  • Odkaz: https://doi.org/10.1016/j.tcs.2019.01.018
  • Pracoviště: Katedra matematiky
  • Anotace:
    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

  • Autoři: prof. RNDr. Jiří Adámek, DrSc.,
  • Publikace: Leibniz International Proceedings in Informatics. Dagstuhl: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2019. p. 1-21. ISSN 1868-8969. ISBN 978-3-95977-120-7.
  • Rok: 2019
  • DOI: 10.4230/LIPIcs.CALCO.2019.12
  • Odkaz: https://doi.org/10.4230/LIPIcs.CALCO.2019.12
  • Pracoviště: Katedra matematiky
  • Anotace:
    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

  • DOI: 10.1007/s10485-018-9530-6
  • Odkaz: https://doi.org/10.1007/s10485-018-9530-6
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Fixed points of functors

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Milius, S., Moss, Lawrence S.
  • Publikace: Journal of Logical and Algebraic Methods in Programming. 2018, 95 41-81. ISSN 2352-2208.
  • Rok: 2018
  • DOI: 10.1016/j.jlamp.2017.11.003
  • Odkaz: https://doi.org/10.1016/j.jlamp.2017.11.003
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

On algebras with effectful iteration

  • Autoři: Milius, S., prof. RNDr. Jiří Adámek, DrSc., Urbat, H.
  • Publikace: Coalgebraic Methods in Computer Science. Basel: Springer, 2018. p. 144-166. Lecture notes in computer science. vol. 11202. ISSN 0302-9743. ISBN 9783030003883.
  • Rok: 2018
  • DOI: 10.1007/978-3-030-00389-0_9
  • Odkaz: https://doi.org/10.1007/978-3-030-00389-0_9
  • Pracoviště: Katedra matematiky
  • Anotace:
    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

  • Pracoviště: Katedra matematiky
  • Anotace:
    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)

  • DOI: 10.1515/tmj-2017-0113
  • Odkaz: https://doi.org/10.1515/tmj-2017-0113
  • Pracoviště: Katedra matematiky
  • Anotace:
    This is a survey of results concerning the algebraic hulls of two 2-categories: VAR, the 2-category of finitary varieties, and LFP, the 2-category of locally finitely presentable categories.

Eilenberg theorems for free

  • Autoři: Urbat, H., prof. RNDr. Jiří Adámek, DrSc., Chen, L.-T., Milius, S.
  • Publikace: 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.
  • Rok: 2017
  • DOI: 10.4230/LIPIcs.MFCS.2017.43
  • Odkaz: https://doi.org/10.4230/LIPIcs.MFCS.2017.43
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

KZ-MONADIC CATEGORIES AND THEIR LOGIC

  • Pracoviště: Katedra matematiky
  • Anotace:
    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?

  • DOI: 10.1007/s10485-016-9451-1
  • Odkaz: https://doi.org/10.1007/s10485-016-9451-1
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.).

A LOGIC OF INJECTIVITY

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Hebert, M., Sousa, L.
  • Publikace: JOURNAL OF HOMOTOPY AND RELATED STRUCTURES. 2007, 2(2), 13-47. ISSN 1512-2891.
  • Rok: 2007
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Recursive coalgebras of finitary functors

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Luecke, D., Milius, S.
  • Publikace: RAIRO - Theoretical Informatics and Applications. 2007, 41(4), 447-462. ISSN 0988-3754.
  • Rok: 2007
  • DOI: 10.1051/ita:2007028
  • Odkaz: https://doi.org/10.1051/ita:2007028
  • Pracoviště: Katedra matematiky
  • Anotace:
    For finitary set functors preserving inverse images, recursive coalgebras A of Paul Taylor are proved to be precisely those for which the system described by A always halts in finitely many steps.

Abstract and Concrete Categories: the Joy of Cats

Elgot Algebras

  • DOI: 10.2168/LMCS-2(5:4)2006
  • Odkaz: https://doi.org/10.2168/LMCS-2(5:4)2006
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Elgot Algebras (Extended Abstract)

  • Pracoviště: Katedra matematiky
  • Anotace:
    We axiomatize algebras that allow a solution of finitary recursive equations. We prove that these algebras arise as Eilenberg-Moore algebras of the free iterative monad.

How Iterative are Iterative Algebras?

  • Pracoviště: Katedra matematiky
  • Anotace:
    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 Algebras at Work

  • DOI: 10.1017/S0960129506005706
  • Odkaz: https://doi.org/10.1017/S0960129506005706
  • Pracoviště: Katedra matematiky
  • Anotace:
    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

  • DOI: 10.1016/j.jalgebra.2006.01.014
  • Odkaz: https://doi.org/10.1016/j.jalgebra.2006.01.014
  • Pracoviště: Katedra matematiky
  • Anotace:
    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 Morphisms in Pro-categories

  • DOI: 10.1016/j.jpaa.2005.09.013
  • Odkaz: https://doi.org/10.1016/j.jpaa.2005.09.013
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Terminal Coalgebras and Free Iterative Theories

  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

A General Final Coalgebra Theorem

  • Pracoviště: Katedra matematiky
  • Anotace:
    By the Final Coalgebra Theorem of Aczel and Mendler, every endofunctor of the category of sets has a final coalgebra that may be a proper class. We generalize this to ``well-behaved'' categories.

A logic of coequations

  • Autoři: prof. RNDr. Jiří Adámek, DrSc.,
  • Publikace: COMPUTER SCIENCE LOGIC. Berlin & Heidelberg: Springer, 2005. pp. 70-86. Lecture Notes in Computer Science. ISSN 0302-9743. ISBN 3-540-28231-9.
  • Rok: 2005
  • Pracoviště: Katedra matematiky
  • Anotace:
    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

  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Birkhoff's Covariety Theorem without Limitations

  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Introduction to Coalgebra

  • Pracoviště: Katedra matematiky
  • Anotace:
    This is a survey article devoted to basic results in coalgebra, based on an invited lecture series at the conference "Category Theory and Computer Science" (CTCS 2003) in Ottawa

Iterative Algebras for a Base

  • Pracoviště: Katedra matematiky
  • Anotace:
    We introduce iterativity w.r.t. to a base (a functor of two variables yielding finitary monads in one variable). We provide a coalgebraic construction of free iterative algebras

A Categorical Characterization of Varieties

  • Pracoviště: Katedra matematiky
  • Anotace:
    A category is equivalent to a variety iff it is cocomplete and has an exactly projective regular generator

From Iterative Algebras to Iterative Theories

  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

On Coalgebra Based on Classes

  • Pracoviště: Katedra matematiky
  • Anotace:
    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

On Pure Quotients and Pure Subobjects

  • Pracoviště: Katedra matematiky
  • Anotace:
    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

On quasivarieties and varieties as categories

  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

On Reflective Subcategories of Varieties

  • Pracoviště: Katedra matematiky
  • Anotace:
    We characterize reflective subcategories of Variet and we solve the open Problem of characterizing orthogonality classes with finitely presentable domains and codomains

On Tree Coalgebras and Coalgebra Presentations

  • Pracoviště: Katedra matematiky
  • Anotace:
    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

Towards a Characterization of Algebraic Exactness

  • Pracoviště: Katedra matematiky
  • Anotace:
    We characterize algebraically exact categories among all categories with finite coproducts. And a full characterization of algebraically exact functors is presented

Continuous Categories Revisited

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Lawvere, F.W., Rosický, J.
  • Publikace: Theory and Applications of Categories. 2003,(11), 252-282. ISSN 1201-561X.
  • Rok: 2003

Free Iterative Theories

How Accessible are Categories of Algebras?

Infinite Trees and Completely Iterative Theories

On a Description of Terminal Coalgebras and Iterative Theories

On Final Coalgebras of Continuous Functors

On Rational Monads and Free Iterative Theories

On the Duality Between Varieties and Algebraic Theories

On Varieties and Covarieties in a Category

Some Remarks on Finitary and Iterative Monads

A Classification of Accessible Categories

A Remark on Conservative Cocompletions of Categories

Final Coalgebras and a Solution Theorem for Arbitrary Endofunctors

Final Coalgebras are Ideal Completions of Initial Algebras

More on Injectivity in Locally Presentable categories

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Rosický, J., Borceux, F.
  • Publikace: Theory and Applications of Categories. 2002,(10), 148-161. ISSN 1201-561X.
  • Rok: 2002

On Abstract Data Types Presented by Multiequations

On Generalized Small-Object Argument

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Rosický, J.
  • Publikace: Cahiers de topologie et geometrie differentielle categoriques. 2002,(33), 83-106. ISSN 0008-0004.
  • Rok: 2002

Weak Faktorization Systems and Topological Functors

A Coalgebraic View of Infinite Trees and Iteration

Categorical Methods of the Theory of Structures and Computer Science

Constructions of Solid Hulls

From Varieties of Algebras to Covarieties of Coalgebras

How Algebraic is Algebra?

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Lawvere, F.W., Rosický, J.
  • Publikace: Theory and Applications of Categories. 2001,(8), 253-283. ISSN 1201-561X.
  • Rok: 2001

How Large Are Left Exact Functors

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Koubek, V., Trnková, V.
  • Publikace: Theory and Applications of Categories. 2001,(8), 377-390. ISSN 1201-561X.
  • Rok: 2001

More on Ortogonality in Locally Presentable Categories

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Hebert, M., Rosický, J.
  • Publikace: Cahiers de topologie et geometrie differentielle categoriques. 2001,(32), 51-80. ISSN 0008-0004.
  • Rok: 2001

On Algebraically Exact Categories and Essential Localization of Varieties

On Functors Which Are Lax Epimorphisms

On Multivarieties and Multialgebraic Theories

On Sifted Colimits and Generalized Varieties

A Duality between Infinitary Varieties and Algebraic Theories

M-completeness is Seldom Monadic over Graphs

Morita Equivalence of Sketches

Totality of Product Completion

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Sousa, L., Tholen, W.
  • Publikace: Commentationes Mathematicae Universitatis Carolinae. 2000, 41 9-24. ISSN 0010-2628.
  • Rok: 2000

Applications of ordered sets in computer science - Preface

Categorical Methods of the Theory of Structures and Computer Science

  • Pracoviště: Katedra matematiky
  • Anotace:
    Kategorialni metody teorie struktur a informatiky

On Essentialy Algebraic Theories and Their Generalizations

Algebraic theories of quasivarieties

  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

A Categorical Generalization of Scott Domains

A Remark on Topological Spaces, Grids and Topological Systems

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Pedicchio, M.
  • Publikace: Cahiers de topologie et geometrie differentielle categoriques. 1997,(38), 217-226. ISSN 0008-0004.
  • Rok: 1997

Finitary sketches

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Johnstone, PT, Makowsky, JA, Rosicky, J
  • Publikace: Journal of Symbolic Logic. 1997, 62(3), 699-707. ISSN 0022-4812.
  • Rok: 1997
  • Pracoviště: Katedra matematiky
  • Anotace:
    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.

Finite Models of Sketches

A Remark on Fixed Points of Functors in Topological Categories

An Algebraic Description of Locally Multipresentable Categories

Applications of Algebra in Computer Science

How to Sketch Quasivarieties

On Geometric and Finitary Sketches

On Pure Morphisms in Accessible Categories

A Remark on Fixed Points of Functors in Topological Categories

Continuous algebras revisited

Finitary sketches and finitely accessible categories

On preaccessible categories

On the greatest fixed point of a set functor

On the Largest Fixed Point of a Set Functor

Recursive Data Types in Algebraically Omega-Complete Categories

Banachs fixed-point theorem as a base for data-type equations

Existence and nonexistence of regular generators

Locally Presentable and Accessible Categories

Sketches and Presentation of Structures

Weakly locally presentable categories

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Rosický, J.
  • Publikace: Cahiers de topologie et geometrie differentielle categoriques. 1994,(35), 179-186. ISSN 0008-0004.
  • Rok: 1994

Data Types in Metrically Enriched Categories

Injectivity in Locally Presentable Categories

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Rosický, J.
  • Publikace: Transactions of the American Mathematical Society. 1993, 336(2), 785-804. ISSN 0002-9947.
  • Rok: 1993
  • DOI: 10.2307/2154375
  • Odkaz: https://doi.org/10.2307/2154375
  • Pracoviště: Katedra matematiky
  • Anotace:
    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

  • Autoři: prof. RNDr. Jiří Adámek, DrSc., Reiterman, J.
  • Publikace: Commentationes Mathematicae Universitatis Carolinae. 1993, 32(4), 689-693. ISSN 0010-2628.
  • Rok: 1993

Foundations of coding

Abstract and concrete categories

Automata and algebras in a category

How many variables does a quasivariety need

Theory of Mathematical Structures

Za stránku zodpovídá: Ing. Mgr. Radovan Suk