Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-20T07:01:45.073Z Has data issue: false hasContentIssue false
  • English
  • Français

Least fixpoints of endofunctors of cartesian closed categories

Published online by Cambridge University Press:  04 March 2009

J. Lambek
J. Lambek
Affiliation:
Department of Mathematics, McGill University, Montreal, Quebec, Canada
Get access Rights & Permissions [Opens in a new window]

Abstract

Least fixpoints are constructed for finite coproducts of definable endofunctors of Cartesian closed categories that have weak polynomial products and joint equalizers of arbitrary families of pairs of parallel arrows. Both conditions hold in PER, the category whose objects are partial equivalence relations on N, and whose arrows are partial recursive functions. Weak polynomial products exist in any cartesian closed category with a finite number of objects as well as in any model of second order polymorphic lambda calculus: that is, in the proof theory of any second order positive intuitionistic propositional calculus, but such a category need not have equalizers. However, any finite coproduct of definable endofunctors of a cartesian closed category with weak polynomial products will have a least fixpoint in a larger category with equalizers whose objects are right ideals (or sieves) of modulo certain congruence relations, and whose arrows are induced from .

Type
Research Article
Information
Mathematical Structures in Computer Science , Volume 3 , Issue 2 , June 1993 , pp. 229 - 257
Copyright
Copyright © Cambridge University Press 1993

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

Adámek, J. and Koubek, V. (1977) Remarks on fixpoints of functors. Springer LNCS 56 199–209.Google Scholar
Adámek, J. and Trnková, V. (1989) Automata and algebras in categories, Kluwer Academic Publishers, Dordrecht.Google Scholar
Arbib, M. A. (1977) Free dynamics and algebraic dynamics. Springer LNCS 56 212–227.Google Scholar
Arbib, M. A. and Manes, E. (1974) Machines in a category. SIAM Review 16 163–192.CrossRefGoogle Scholar
Asperti, A. G. (1990) Categorical topics in computer science, Ph.D. Thesis TD-7/90, University of Pisa, Dipartimento di Informatica.Google Scholar
Asperti, A. G. and Longo, G. (1991) Categories, types and structures, M.I.T. Press, Cambridge, Mass.Google Scholar
Bainbridge, E. S., Freyd, P. J., Scedrov, A. and Scott, P. J. (1990) Functorial polymorphism. Theoretical Computer Science 70 35–64.CrossRefGoogle Scholar
Birkhoff, G. (1948) Lattice theory, Revised edition, A.M.S. Colloq. Publ. 25, New York.Google Scholar
Curry, H. B. and Feys, R. (1958) Combinatory logic, Vol. 1, North Holland, Amsterdam.Google Scholar
Feferman, S. (1990) Polymorphic typed lambda-calculi in a type-free axiomatic framework. Contemporary Mathematics 106 101–136.CrossRefGoogle Scholar
Freyd, P. (1972) Aspects of topoi. Bull. Austral. Math. Soc. 7 1–76, 467–480.CrossRefGoogle Scholar
Gierz, G., Hofmann, K. H., Keimel, K., Lawson, J. D., Mislove, M. and Scott, D. S. (1986) A compendium of continuous lattices, Springer Verlag, Berlin/Heidelberg/New York.Google Scholar
Girard, J.-Y. (1972) Interprétation fonctionelle et élimination des coupures dans l’arithmétique d’ordre supérieur, Thèse de Doctorat d’Etat, Paris.Google Scholar
Girard, J.-Y. (1986) The system F of variable types fifteen years later. Theoretical Computer Science 45 159–192.CrossRefGoogle Scholar
Girard, J.-Y., Lafont, Y. and Taylor, P. (1989) Proofs and types, Cambridge Tracts in Theoretical Computer Science 7, Cambridge University Press, Cambridge.Google Scholar
Gray, J. W. (1989) The integration of logical and algebraic types, Preprint, University of Illinois at Urbana-Champagne.CrossRefGoogle Scholar
Howard, W. A. (1980) The formula-as-types notion of construction. In: Seldin, J. P. and Hindley, J. R. (eds.) To H.B. Curry: essays on combinatory logic, lambda calculus and formalism, Academic Press, London, 479–490.Google Scholar
Huwig, H. and Poigné, A. (1990) A note on inconsistencies caused by fixpoints in a cartesian closed category. Theoretical Computer Science 72 101–112.CrossRefGoogle Scholar
Hyland, J. M. E. (1988) A small complete category. Annals of Pure and Applied Logic 40 135–165.Google Scholar
Kleene, S. C. (1952) Introduction to metamathematics, Van Nostrand, New York.Google Scholar
Knaster, B. (1928) Un théorème sur les fonctions d’ensembles. Ann. Soc. Polon. Math. 6 133–134.Google Scholar
Lambek, J. (1968) A fixpoint theorem for complete categories. Math. Zeitschr. 103 151–161.CrossRefGoogle Scholar
Lambek, J. (1970) Subequalizers. Can. Math. Bull. 13 337–349.CrossRefGoogle Scholar
Lambek, J. (1972) Deductive systems and categories III. Springer LNM 274 52–82.Google Scholar
Lambek, J. (1974) Functional completeness of Cartesian categories. Annals of Math. Logic 6 259–292.CrossRefGoogle Scholar
Lambek, J. (1980) From λ-calculus to cartesian closed categories. In: Seldin, J. P. and Hindley, J. R. (eds.) To H.B. Curry: essays on combinatory logic, lambda calculus and formalism, Academic Press, London, 375–402.Google Scholar
Lambek, J. (1989) On some connections between logic and category theory. Studia Logica 48 269–278.CrossRefGoogle Scholar
Lambek, J. (1989) Fixpoints revisited. Springer LNCS 363 200–207.Google Scholar
Lambek, J. and Scott, P. J. (1986) Introduction to higher order intuitionistic logic, Cambridge Studies in Advanced Mathematics 7, Cambridge U. Press, Cambridge.Google Scholar
Lawvere, F. W. (1969a) Adjointness in foundations. Dialectica 23 281–296.CrossRefGoogle Scholar
Lawvere, F. W. (1969b) Diagonal arguments and cartesian closed categories. Springer LNM 92 134–145.Google Scholar
Longo, G. (1988) Some aspects of impredicavity, Notes on Weyl’s philosophy of mathematics and today’s type theory, Preprint, Carnegie Mellon.Google Scholar
Longo, G. and Moggi, E. (1991) Constructive natural deduction and its “ω-set” interpretation. Math. Structures in Computer Science 1 215–254.CrossRefGoogle Scholar
Martin-Lö, P. (1984) Intuitionistic type theory, Studies in Proof Theory I, Bibliopolis, Naples.Google Scholar
Narayanan, B. R. (1988) A general framework for models of type polymorphism, Ph.D. Thesis, Department of Computer and Information Science, Syracuse University.Google Scholar
Pitts, A. M. (1987) Polymorphism is set theoretic constructively. Springer LNCS 283 12–39.Google Scholar
Pitts, A. M. (1989) Non-trivial power types can't be subtypes of polymorphic types, U. of Cambridge, Computer Laboratory, Technical Report No. 159.Google Scholar
Prouté, A. (1988) Catégories et lambda-calcul, Preprint, Université de Paris VI.Google Scholar
Reynolds, J. C. (1974) Towards a theory of type structure. Springer LNCS 19 408–425.Google Scholar
Reynolds, J. C. (1984) Polymorphism is not set-theoretic. Springer LNCS 173 145–156.Google Scholar
Reynolds, J. C. and Plotkin, G. D. (1989) On functors expressible in the polymorphic typed lambda calculus. In: Huet, G. (ed), Logical foundations of functional programming, Addison-Wesley, Reading, Mass., 140.Google Scholar
Rodenburg, P. H. and van der Linden, F. J. (1989) Manufacturing a cartesian closed category with exactly two objects out of a C-monoid. Studia Logica 48 279–283.CrossRefGoogle Scholar
Scott, D. S. (1972) Continuous lattices. Springer LNM 274 97–136.Google Scholar
Scott, D. S. (1980) Relating theories of the λ-calculus. In: Seldin, J. P. and Hindley, J. R. (eds.) To H.B. Curry: essays on combinatory logic, lambda calculus and formalism, Academic Press, London, 403–450.Google Scholar
Seely, R. A. G. (1987) Categorical semantics for higher order polymorphic lambda calculus. J. Symbolic Logic 52 969–989.CrossRefGoogle Scholar
Smyth, M. B. and Plotkin, G. D. (1982) The category-theoretic solution of recursive domain equations. S1AM Journal of Computing 11 761–783.Google Scholar
Tarski, A. (1955) A lattice theoretical fixpoint theorem. Pacific J. Math. 5 285–309.CrossRefGoogle Scholar