Accessible set functors are universal

Libor Barto

Commentationes Mathematicae Universitatis Carolinae (2019)

  • Volume: 60, Issue: 4, page 497-508
  • ISSN: 0010-2628

Abstract

top
It is shown that every concretizable category can be fully embedded into the category of accessible set functors and natural transformations.

How to cite

top

Barto, Libor. "Accessible set functors are universal." Commentationes Mathematicae Universitatis Carolinae 60.4 (2019): 497-508. <http://eudml.org/doc/295080>.

@article{Barto2019,
abstract = {It is shown that every concretizable category can be fully embedded into the category of accessible set functors and natural transformations.},
author = {Barto, Libor},
journal = {Commentationes Mathematicae Universitatis Carolinae},
keywords = {set functor; universal category; full embedding},
language = {eng},
number = {4},
pages = {497-508},
publisher = {Charles University in Prague, Faculty of Mathematics and Physics},
title = {Accessible set functors are universal},
url = {http://eudml.org/doc/295080},
volume = {60},
year = {2019},
}

TY - JOUR
AU - Barto, Libor
TI - Accessible set functors are universal
JO - Commentationes Mathematicae Universitatis Carolinae
PY - 2019
PB - Charles University in Prague, Faculty of Mathematics and Physics
VL - 60
IS - 4
SP - 497
EP - 508
AB - It is shown that every concretizable category can be fully embedded into the category of accessible set functors and natural transformations.
LA - eng
KW - set functor; universal category; full embedding
UR - http://eudml.org/doc/295080
ER -

References

top
  1. Adámek J., Gumm H. P., Trnková V., 10.1093/logcom/exn090, J. Logic Comput. 20 (2010), no. 5, 991–1015. MR2725166DOI10.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. 
  3. Barto L., 10.1007/s00012-007-2011-7, Algebra Universalis 57 (2007), no. 1, 15–26. MR2326923DOI10.1007/s00012-007-2011-7
  4. Barto L., 10.1016/j.jpaa.2007.04.001, J. Pure Appl. Algebra 211 (2007), no. 3, 721–731. MR2344225DOI10.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. MR4003368
  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. MR3631047
  7. Barto L., Opršal J., Pinsker M., 10.1007/s11856-017-1621-9, Israel J. Math. 223 (2018), no. 1, 363–398. MR3773066DOI10.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. MR2182678
  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. MR3734240
  10. Freyd P. J., 10.1016/0022-4049(73)90031-5, J. Pure Appl. Algebra 3 (1973), 171–191. MR0322006DOI10.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. MR0749524
  12. Hedrlín Z., Pultr A., 10.1215/ijm/1256054991, Illinois J. Math. 10 (1966), 392–406. MR0191858DOI10.1215/ijm/1256054991
  13. Isbell J. R., 10.4064/fm-53-1-43-49, Fund. Math. 53 (1963), 43–49. MR0156884DOI10.4064/fm-53-1-43-49
  14. Koubek V., Set functors, Comment. Math. Univ. Carolin. 12 (1971), 175–195. MR0286860
  15. Kučera L., 10.1016/0022-4049(71)90004-1, J. Pure Appl. Algebra 1 (1971), no. 4, 373–376. MR0299548DOI10.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. MR0563525
  17. Rutten J. J. M. M., 10.1016/S0304-3975(00)00056-6, Modern Algebra and Its Applications, Nashville 1996, Theoret. Comput. Sci. 249 (2000), no. 1, 3–80. MR1791953DOI10.1016/S0304-3975(00)00056-6
  18. Trnková V., Universal categories, Comment. Math. Univ. Carolinae 7 (1966), 143–206. MR0202808
  19. Trnková V., Some properties of set functors, Comment. Math. Univ. Carolinae 10 (1969), 323–352. MR0252474
  20. Trnková V., On descriptive classification of set-functors. I, Comment. Math. Univ. Carolinae 12 (1971), 143–174. MR0294445
  21. Trnková V., On descriptive classification of set-functors. II, Comment. Math. Univ. Carolinae 12 (1971), 345–357. MR0294446
  22. Trnková V., Universal concrete categories and functors, Cahiers Topologie Géom. Différentielle Catég. 34 (1993), no. 3, 239–256. MR1239471
  23. Trnková V., Amazingly extensive use of Cook continuum, Math. Japon. 51 (2000), no. 3, 499–549. MR1757312
  24. Trnková V., Barkhudaryan A., 10.1007/s00012-002-8188-x, Algebra Universalis 47 (2002), no. 3, 239–266. MR1918729DOI10.1007/s00012-002-8188-x
  25. Vinárek J., 10.1016/0022-4049(76)90019-0, J. Pure Appl. Algebra 8 (1976), no. 1, 1–4. MR0399206DOI10.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. MR3734241

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.