×

Accessible set functors are universal. (English) Zbl 1524.18006

The original motivation for studying the universality of set functors was an open problem formulated in [V. Trnková and A. Barkhudaryan, Algebra Univers. 47, No. 3, 239–266 (2002; Zbl 1061.08004)]. Is the category of varieties and interpretations in [O. C. Garcia and W. Taylor, The lattice of interpretability types of varieties. Providence, RI: American Mathematical Society (AMS) (1984; Zbl 0559.08003)] alg-universal? L. Barto and P. Zima [Theory Appl. Categ. 14, 294–309 (2005; Zbl 1076.18001)] has shown, using a rather involved construction, that the category of set functors is group-universal. A significantly simpler construction was carried out in [L. Barto, Algebra Univers. 57, No. 1, 15–26 (2007; Zbl 1122.18002)] to establish that the category of finitary set functors is alg-universal.
This paper is concerned with the question whether the category of set functors is more comprehensive than the category of finitary ones, answering the question affirmatively.
The synopsis of the paper goes as follows.
§ 2
gives preliminaries.
§ 3
shows that the category of accessible set functors is universal.
§ 4
shows that the above result can not be further strengthened by establishing that the category of accessible set functors is concretizable. It is also demonstrated that
Theorem. A category \(\boldsymbol{Z}\)is isomorphic to a full subcategory of the category of accessible set functors iff \(\boldsymbol{Z}\)is concretizable.
§ 5
gives several questions for future study.
This paper has shown that the category of accessible set functors is as comprehensive as possible. How comprehensive is the collection of all set functors?
A combination of theorems in [L. Kučera, J. Pure Appl. Algebra 1, 373–376 (1971; Zbl 0259.18003), V. Trnková, Commentat. Math. Univ. Carol. 7, 143–206 (1966; Zbl 0163.01501)] implies that in every universal category it is possible to find equivalences on hom-sets which are compatible with composition. Is there a natural hyper-universal quotient of the category of accessible set functors? Is it some kind of a homotopy equivalence on natural transformations?
In the premise CSP (Constraint Satisfaction Problem) the author is so far interested in minions with finite universes. How comprehensive is their category?

MSC:

18B15 Embedding theorems, universal categories
18A22 Special properties of functors (faithful, full, etc.)
18A25 Functor categories, comma categories
08B05 Equational logic, Mal’tsev conditions
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Adámek J.; Gumm H. P.; Trnková V., Presentation of set functors: a coalgebraic perspective, J. Logic Comput. 20 (2010), no. 5, 991-1015 · Zbl 1207.18002 · doi:10.1093/logcom/exn090
[2] Adámek J.; Porst H. E., From varieties of algebras to covarieties of coalgebras, Coalgebraic Methods in Computer Science (a Satellite Event of ETAPS 2001), Electronic Notes in Theoretical Computer Science 44 (2001), no. 1, 27-46 · Zbl 1260.08004
[3] Barto L., Finitary set endofunctors are alg-universal, Algebra Universalis 57 (2007), no. 1, 15-26 · Zbl 1122.18002 · doi:10.1007/s00012-007-2011-7
[4] Barto L., The category of varieties and interpretations is alg-universal, J. Pure Appl. Algebra 211 (2007), no. 3, 721-731 · Zbl 1122.18003 · doi:10.1016/j.jpaa.2007.04.001
[5] Barto L.; Bulín J.; Krokhin A.; Opršal J., Algebraic approach to promise constraint satisfaction, available at arXiv:1811.00970v3 [cs.CC] (2019), 73 pages · Zbl 1433.68271
[6] Barto L.; Krokhin A.; Willard R., Polymorphisms, and how to use them, The Constraint Satisfaction Problem: Complexity and Approximability, Dagstuhl Follow-Ups, 7, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2017, pages 1-44 · Zbl 1482.68161
[7] Barto L.; Opršal J.; Pinsker M., The wonderland of reflections, Israel J. Math. 223 (2018), no. 1, 363-398 · Zbl 1397.08002 · doi:10.1007/s11856-017-1621-9
[8] Barto L.; Zima P., Every group is representable by all natural transformations of some set-functor, Theory Appl. Categ. 14 (2005), no. 13, 294-309 · Zbl 1076.18001
[9] Bulatov A. A., A dichotomy theorem for nonuniform CSPs, 58th Annual IEEE Symposium on Foundations of Computer Science-FOCS 2017, IEEE Computer Soc., Los Alamitos, 2017, pages 319-330
[10] Freyd P. J., Concreteness, J. Pure Appl. Algebra 3 (1973), 171-191 · Zbl 0277.18002 · doi:10.1016/0022-4049(73)90031-5
[11] García O. C.; Taylor W., The lattice of interpretability types of varieties, Mem. Amer. Math. Soc. 50 (1984), no. 305, 125 pages · Zbl 0559.08003
[12] Hedrlín Z.; Pultr A., On full embeddings of categories of algebras, Illinois J. Math. 10 (1966), 392-406 · Zbl 0139.01501 · doi:10.1215/ijm/1256054991
[13] Isbell J. R., Two set-theoretical theorems in categories, Fund. Math. 53 (1963), 43-49 · Zbl 0114.01302 · doi:10.4064/fm-53-1-43-49
[14] Koubek V., Set functors, Comment. Math. Univ. Carolin. 12 (1971), 175-195 · Zbl 0217.06803
[15] Kučera L., Every category is a factorization of a concrete one, J. Pure Appl. Algebra 1 (1971), no. 4, 373-376 · Zbl 0259.18003 · doi:10.1016/0022-4049(71)90004-1
[16] Pultr A.; Trnková V., Combinatorial, Algebraic and Topological Representations of Groups, Semigroups and Categories, North-Holland Mathematical Library, 22, North-Holland Publishing, Amsterdam, 1980 · Zbl 0418.18004
[17] Rutten J. J. M. M., Universal coalgebra: a theory of systems, Modern Algebra and Its Applications, Nashville 1996, Theoret. Comput. Sci. 249 (2000), no. 1, 3-80 · Zbl 0951.68038 · doi:10.1016/S0304-3975(00)00056-6
[18] Trnková V., Universal categories, Comment. Math. Univ. Carolinae 7 (1966), 143-206 · Zbl 0163.01501
[19] Trnková V., Some properties of set functors, Comment. Math. Univ. Carolinae 10 (1969), 323-352 · Zbl 0183.30401
[20] Trnková V., On descriptive classification of set-functors. I, Comment. Math. Univ. Carolinae 12 (1971), 143-174 · Zbl 0232.18004
[21] Trnková V., On descriptive classification of set-functors. II, Comment. Math. Univ. Carolinae 12 (1971), 345-357 · Zbl 0232.18005
[22] Trnková V., Universal concrete categories and functors, Cahiers Topologie Géom. Différentielle Catég. 34 (1993), no. 3, 239-256 · Zbl 0797.18003
[23] Trnková V., Amazingly extensive use of Cook continuum, Math. Japon. 51 (2000), no. 3, 499-549 · Zbl 0955.54011
[24] Trnková V.; Barkhudaryan A., Some universal properties of the category of clones, Algebra Universalis 47 (2002), no. 3, 239-266 · Zbl 1061.08004 · doi:10.1007/s00012-002-8188-x
[25] Vinárek J., A new proof of the Freyd’s theorem, J. Pure Appl. Algebra 8 (1976), no. 1, 1-4 · Zbl 0329.18006 · doi:10.1016/0022-4049(76)90019-0
[26] Zhuk D., A proof of CSP dichotomy conjecture, 2017 58th Annual IEEE Symposium on Foundations of Computer Science-FOCS 2017, IEEE Computer Soc., Los Alamitos, 2017, pages 331-342
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.