Hostname: page-component-8448b6f56d-mp689 Total loading time: 0 Render date: 2024-04-19T10:04:04.468Z Has data issue: false hasContentIssue false
  • English
  • Français

A general formulation of simultaneous inductive-recursive definitions in type theory

Published online by Cambridge University Press:  12 March 2014

Peter Dybjer
Peter Dybjer*
Affiliation:
Department of Computing Science, Chalmers University of Technology, S-412 96 Göteborg, Sweden, E-mail: peterd@cs.chalmers.se
Get access Rights & Permissions [Opens in a new window]

Abstract

The first example of a simultaneous inductive-recursive definition in intuitionistic type theory is Martin-Löfs universe à la Tarski. A set U0 of codes for small sets is generated inductively at the same time as a function T0, which maps a code to the corresponding small set, is defined by recursion on the way the elements of U0 are generated.

In this paper we argue that there is an underlying general notion of simultaneous inductive-recursive definition which is implicit in Martin-Löf's intuitionistic type theory. We extend previously given schematic formulations of inductive definitions in type theory to encompass a general notion of simultaneous induction-recursion. This enables us to give a unified treatment of several interesting constructions including various universe constructions by Palmgren, Griffor, Rathjen, and Setzer and a constructive version of Aczel's Frege structures. Consistency of a restricted version of the extension is shown by constructing a realisability model in the style of Allen.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 65 , Issue 2 , June 2000 , pp. 525 - 549
Copyright
Copyright © Association for Symbolic Logic 2000

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

REFERENCES

[1]Aczel, Peter, An introduction to inductive definitions, Handbook of mathematical logic (Barwise, Jon, editor), North-Holland, 1977, pp. 739–782.CrossRefGoogle Scholar
[2]Aczel, Peter, The strength of Martin-Löf's type theory with one universe, Proceedings of the symposium on mathematical logic (Oulu 1974) (Miettinen, S. and Väänanen, J., editors), 1977, Report No 2 of Dept. Philosophy, University of Helsinki, pp. 1–32.Google Scholar
[3]Aczel, Peter, The type theoretic interpretation of constructive set theory, Logic colloquium '77 (MacIntyre, A., Pacholski, L., and Paris, J., editors), North-Holland, 1978, pp. 55–66.CrossRefGoogle Scholar
[4]Aczel, Peter, Frege Structures and the Notions of Proposition, Truth, and Set, pp. 31–59, North-Holland, 1980, pp. 31–59.CrossRefGoogle Scholar
[5]Allen, Stuart, A non-type-theoretic semantics for type-theoretic language, Ph.D. thesis Department of Computer Science, Cornell University, 1987.Google Scholar
[6]Altenkirch, Thorsten, Constructions, inductive types and strong normalization, Ph.D. thesis, The University of Edinburgh, Department of Computer Science, 11 1993.Google Scholar
[7]Backhouse, Roland, On the meaning and construction of the rules in Martin-Löf's theory of types, Proceedings of the workshop on general logic, edinburg, february 1987 (Avron, A., Harper, B., Honsell, F., Mason, I., and Plotkin, G., editors), Laboratory for Foundations of Computer Science, Department of Computer Science, University of Edinburgh, 1988, ECS-LFCS-88-52.Google Scholar
[8]Barendregt, Henk P., The lambda calculus, North-Holland, 1984, Revised edition.Google Scholar
[9]Bird, Richard and Wadler, Philip, Introduction to functional programming, Prentice Hall, 1988.Google Scholar
[10]Bishop, E., Foundations of constructive analysis, McGraw-Hill, 1967.Google Scholar
[11]Coquand, Catarina, From semantics to rules: a machine assisted analysis, Proceedings of CSL '93, LNCS 832 (Börger, Egon, Gurevich, Yuri, and Meinke, Karl, editors), 1993.Google Scholar
[12]Coquand, Catarina, A realizability interpretation of Martin-Löf's type theory, Twenty-five years of constructive type theory (Sambin, G. and Smith, J., editors), Oxford University Press, 1998, pp. 73–82.Google Scholar
[13]Coquand, Thierry, An algorithm for testing conversion in type theory, Logical frameworks, Cambridge University Press, 1991, pp. 255–279.CrossRefGoogle Scholar
[14]Coquand, Thierry, Pattern matching with dependent types, Proceedings of the 1992 workshop on types for proofs and programs (Nordström, Bengt and Petersson, Kent and Plotkin, Gordon, editor), 06 1992.Google Scholar
[15]Coquand, Thierry and Dybjer, Peter, Intuitionistic model constructions and normalization proofs, Mathematical Structures in Computer Science, vol. 7 (1997), pp. 75–94.CrossRefGoogle Scholar
[16]Coquand, Thierry and Paulin, Christine, Inductively defined types, preliminary version, LNCS 417, COLOG '88, International Conference on Computer Logic, Springer-Verlag, 1990.Google Scholar
[17]Čubrić, Djordje, Dybjer, Peter, and Scott, Philip, Normalization and the Yoneda embedding, Mathematical Structures in Computer Science, vol. 8 (1998), pp. 153–192.CrossRefGoogle Scholar
[18]Dowek, Gilles, Felty, Amy, Herbelin, Hugo, Huet, Gerard, Paulin, Christine, and Werner, Benjamin, The Coq proof assistant version 5.6, user's guide, Technical report, INRIA Rocquencourt - CNRS ENS Lyon, 1991.Google Scholar
[19]Dybjer, Peter, Inductive sets and families in Martin-Löf's type theory and their set-theoretic semantics, Logical frameworks (Huet, Gerard and Plotkin, Gordon, editors), Cambridge University Press, 1991, pp. 280–306.CrossRefGoogle Scholar
[20]Dybjer, Peter, Inductive families, Formal Aspects of Computing, vol. 6 (1994), pp. 440–465.CrossRefGoogle Scholar
[21]Dybjer, Peter, Internal type theory, Types '95, types for proofs and programs, Lecture Notes in Computer Science, no. 1158, Springer, 1996, pp. 120–134.CrossRefGoogle Scholar
[22]Dybjer, Peter and Setzer, Anton, A finite axiomatization of inductive-recursive definitions, Typed Lambda Calculi and Applications (Girard, J-Y., editor), Lecture Notes in Computer Science, no. 1581, Springer, 1999, pp. 129–146.CrossRefGoogle Scholar
[23]Giménez, Eduardo, A command for inductive sets in ILF, Master Thesis, Universidad de la República, Montevideo, 1992.Google Scholar
[24]Griffor, Edward and Rathjen, Michael, The strength of some Martin-Löf type theories, Archive for Mathematical Logic, vol. 33 (1994), pp. 337–385.CrossRefGoogle Scholar
[25]Hedberg, Michael, Type theory and the external logic of programs, Ph.D. thesis, Chalmers University of Technology and University of Göteborg, 1994.Google Scholar
[26]Kameyama, Yukiyoshi, A type-free theory of half-monotone inductive definitions, International Journal of Foundations of Computer Science, vol. 6 (1995), no. 3, pp. 203–234.CrossRefGoogle Scholar
[27]Martin-Löf, Per, Hauptsatz for the intuitionistic theory of iterated inductive definitions, Proceedings of the Second Scandinavian Logic Symposium (Fenstad, J. E., editor), North-Holland, 1971, pp. 179–216.CrossRefGoogle Scholar
[28]Martin-Löf, Per, An intuitionistic theory of types: Predicative part, Logic colloquium '73 (Rose, H. E. and Shepherdson, J. C., editors), North-Holland, 1975, pp. 73–118.Google Scholar
[29]Martin-Löf, Per, Constructive mathematics and computer programming, Logic, methodology and philosophy of science, vi, 1979, North-Holland, 1982, pp. 153–175.Google Scholar
[30]Martin-Löf, Per, Intuitionistic type theory, Bibliopolis, 1984.Google Scholar
[31]Martin-Löf, Per, Amendment to intuitionistic type theory, Notes from a lecture given in Göteborg, 03 1986.Google Scholar
[32]Martin-Löf, Per, An intuitionistic theoy of types, Twenty-five years of constructive type theory (Sambin, G. and Smith, J., editors), Oxford University Press, 1998, Reprinted version of an unpublished report from 1972, pp. 127–172.Google Scholar
[33]Mendler, Paul Francis, Predicative type universes and primitive recursion, Proceedings sixth annual synposium on logic in computer science, IEEE Computer Society Press, 1991.Google Scholar
[34]Milner, Robin, Tofte, Mads, and Harper, Robert, The Definition of Standard ML, MIT Press, 1990.Google Scholar
[35]Nordström, Bengt, Petersson, Kent, and Smith, Jan, Programming in Martin-Löfs type theory: an introduction, Oxford University Press, 1990.Google Scholar
[36]Palmgren, Erik, On universes in type theory, Twenty-Five Years of Constructive Type Theory (Sambin, G. and Smith, J., editors), pp. 191–204.Google Scholar
[37]Palmgren, Erik, On fixed point operators, inductive definitions and universes in Martin-Löfs type theory, Ph.D. thesis, Uppsala University, 1991.Google Scholar
[38]Parigot, Michel, Programming with proofs: a second order type theory, ESOP'88, 2nd European Symposium on Programming, Nancy, LNCS300 (Ganzinger, H., editor), 03 1988, pp. 145–159.Google Scholar
[39]Paulin-Mohring, Christine, Inductive definitions in the system Cog - rules and properties, Proceedings typed λ-calculus and applications, Springer-Verlag, LNCS, 03 1993, pp. 328–245.Google Scholar
[40]Rathjen, Michael, Edward Griffor, R., and Palmgren, Erik, Inaccessibility in constructive set theory and type theory, Annals of Pure and Applied Logic, vol. 94 (1998), pp. 181–200.CrossRefGoogle Scholar
[41]Sato, Masahiko, Adding proof objects and inductive definition mechanism to Frege structures, Proc. international conference on theoretical aspects of computer science (Ito, T. and Meyer, A., editors), LNCS, no. 526, Springer Verlag, 1991, pp. 53–87.Google Scholar
[42]Setzer, Anton, Extending Martin-Löf type theory by one Mahlo-universe, to appear in Archive for Mathematical Logic.Google Scholar
[43]Setzer, Anton, Proof theoretical strength of Martin-Löf type theory with W-type and one universe, Ph.D. thesis, Fakultät für Mathematik der Ludwig-Maximilians-Universität München, 1993.Google Scholar
[44]Smith, Jan, The independence of Peano's fourth axiom from Martin-Löf's type theory without universes, this Journal, vol. 49 (1988). no. 3.Google Scholar
[45]Smith, Jan, Prepositional functions and families of types, Notre Dame Journal of Formal Logic, vol. 30 (1989), no. 3, pp. 442–458.CrossRefGoogle Scholar
[46]Werner, Benjamin, A normalization proof for an impredicative type system with large elimination over integers, Proceedings of the 1992 workshop on proofs and programs (Nordström, Bengt, Petersson, Kent, and Plotkin, Gordon, editors), Department of Computer Sciences, Chalmers University of Technology, 06 1992, pp. 361–377.Google Scholar