Hostname: page-component-586b7cd67f-t7fkt Total loading time: 0 Render date: 2024-11-24T16:06:30.175Z Has data issue: false hasContentIssue false
  • English
  • Français

Models of non-well-founded sets via an indexed final coalgebra theorem

Published online by Cambridge University Press:  12 March 2014

Benno van den Berg  and
Federico de Marchi
Benno van den Berg
Affiliation:
Technische Universität Darmstadt, Fachbereich Mathematik, Schlobgartenstr. 7. 64289 Darmstadt, Germany. E-mail: [email protected].
Federico de Marchi
Affiliation:
Corso montegrappa 18/4, 16137 Genova, Italy. E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper uses the formalism of indexed categories to recover the proof of a standard final coalgebra theorem, thus showing existence of final coalgebras for a special class of functors on finitely complete and cocomplete categories. As an instance of this result, we build the final coalgebra for the powerclass functor, in the context of a Heyting pretopos with a class of small maps. This is then proved to provide models for various non-well-founded set theories, depending on the chosen axiomatisation for the class of small maps.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 3 , September 2007 , pp. 767 - 791
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Aczel, P., Non-well-founded sets, CSLI Lecture Notes, vol. 14, CSLI Publications, Stanford, CA, 1988.Google Scholar
[2] Aczel, P. and Mendler, N., A final coalgebra theorem. Category theory and computer science (Manchester, 1989), Lecture Notes in Computer Science, vol. 389, Springer-Verlag, Berlin, 1989, pp. 357–365.Google Scholar
[3] Aczel, P. and Rathjen, M., Notes on constructive set theory, Technical Report No. 40, Institut Mittag-Leffler, 2000/2001.Google Scholar
[4] Adámek, J., Milius, S., and Velebil, J., On coalgebra based on classes, Theoretical Computer Science, vol. 316 (2004), no. 1-3, pp. 3–23.CrossRefGoogle Scholar
[5] Awodey, S., Butz, C., Simpson, A.K., and Streicher, T., Relating topos theory and set theory via categories of classes, available from http://www.phil.emu.edu/projects/ast/, 06 2003.Google Scholar
[6] Awodey, S. and Warren, M.A., Predicative algebraic set theory, Theory and Applications of Categories, vol. 15 (2005), no. 1, pp. 1–39.Google Scholar
[7] van den Berg, B., Predicative topos theory and models for constructive set theory, Ph.D. thesis, University of Utrecht, 2006.Google Scholar
[8] van den Berg, B. and de Marchi, F., Non-well-founded trees in categories, Annals of Pure and Applied Logic, vol. 146 (2007), pp. 40–59.CrossRefGoogle Scholar
[9] van den Berg, B. and Moerdijk, I., A unified approach to algebraic set theory, Submitted, 10 2006.Google Scholar
[10] Borceux, Francis, Handbook of categorical algebra. volume 2: Categories and structures, Encyclopedia of Mathematics and its Applications, vol. 51, Cambridge University Press, Cambridge, 1994.Google Scholar
[11] Butz, C., Bernays-Gödel type theory, Journal of Pure and Applied Algebra, vol. 178 (2003), no. 1, pp. 1–23.CrossRefGoogle Scholar
[12] Hyland, J.M.E., The effective topos, The L.E.J. Brouwer Centenary Symposium (Noordwijker-hout, 1981) (Troelstra, A.S. and van Dalen, D., editors), Studies for Logic Foundations of Mathematics, vol. 110, North-Holland Publishing Co., Amsterdam, 1982, pp. 165–216.Google Scholar
[13] Johnstone, P.T., Sketches of an elephant: a topos theory compendium. Volume 1, Oxford Logic Guides, vol. 43, Oxford University Press, New York, 2002.Google Scholar
[14] Johnstone, P.T., Power, A.J., Tsujishita, T., Watanabe, H., and Worrell, J., On the structure of categories of coalgebras. Theoretical Computer Science, vol. 260 (2001), no. 1-2, pp. 87–117.CrossRefGoogle Scholar
[15] Joyal, A. and Moerdijk, I., Algebraic set theory, London Mathematical Society Lecture Note Series, vol. 220, Cambridge University Press, Cambridge, 1995.CrossRefGoogle Scholar
[16] Lambek, J., Subequalizers, Canadian Mathematical Bulletin, vol. 13 (1970), pp. 337–349.CrossRefGoogle Scholar
[17] Lindström, I., A construction of non-well-founded sets within Martin-Löf's type theory, this Journal, vol. 54 (1989), no. 1, pp. 57–64.Google Scholar
[18] Moerdijk, I. and Palmgren, E., Wellfounded trees in categories, Annals of Pure and Applied Logic, vol. 104 (2000), pp. 189–218.CrossRefGoogle Scholar
[19] Myhill, J., Constructive set theory, this Journal, vol. 40 (1975), no. 3, pp. 347–382.Google Scholar
[20] Pedicchio, M.C. and Tholen, W. (editors), Categorical foundations: Special topics in order, topology, algebra, and sheaf theory, Encyclopedia of Mathematics and Its Applications, vol. 97, Cambridge University Press, Cambridge, 2004.Google Scholar
[21] Rathjen, M., Kripke-Platek set theory and the anti-foundation axiom, Mathematical Logic Quarterly, vol. 47 (2001), no. 4, pp. 435–440.3.0.CO;2-7>CrossRefGoogle Scholar
[22] Rathjen, M., The anti-foundation axiom in constructive set theories, Games, logic, and constructive sets (Stanford, CA, 2000), CSLI Lecture Notes, vol. 161, CSLI Publications, Stanford, CA, 2003, pp. 87–108.Google Scholar
[23] Rathjen, M., Predicativity, circularity, and anti-foundation, One hundred years of Russell's paradox, de Gruyter Series in Logic and its Applications, vol. 6, De Gruyter, Berlin, 2004, pp. 191–219.Google Scholar
[24] Rieger, L., A contribution to Gödel's axiomatic set theory. I, Czechoslovak Mathematical Journal, vol. 7(82) (1957), pp. 323–357.Google Scholar
[25] Simpson, A.K., Elementary axioms for categories of classes (extended abstract), 14th Symposium on Logic in Computer Science (Trento, 1999), IEEE Computer Society, Los Alamitos, CA, 1999, pp. 77–85.Google Scholar