Abstract
It is well-known that the proof theory of many sufficiently powerful logics may be represented internally by Gödelization. Here we show that for Constructive Type Theory, it is furthermore possible to define a semantics of the types in the type theory itself, and that this procedure results in new reasoning principles for type theory. Paradoxes are avoided by stratifying the definition in layers.
Preview
Unable to display preview. Download preview PDF.
References
S. F. Allen, R. L. Constable, D. Howe, and W. Aitken. The semantics of reflected proof. In Proceedings of the Fifth Annual Symposium on Logic in Computer Science, pages 95–105, 1990.
S. F. Allen. A non-type-theoretic semantics for type-theoretic language. Technical Report 87-866, Department of Computer Science, Cornell University, September 1987. Ph.D. Thesis.
R. S. Boyer and J S. Moore. Metafunctions: Proving them correct and using them efficiently as new proof procedures. In R. S. Boyer and J Strother Moore, editors, The Correctness Problem in Computer Science, chapter 3. Academic Press, 1981.
R. L. Constable, S. F. Allen, H. Bromley, W. R. Cleveland, J. Cremer, R. Harper, D. Howe, T. Knoblock, N. P. Mendier, P. Panangaden, J. Sasaki, and S. F. Smith. Implementing Mathematics with the Nuprl Proof Development System. Prentice-Hall, Englewood Cliffs, New Jersey, 1986.
M. Davis and J. T. Schwartz. Metamathematical extensibility for theorem verifiers and proof-checkers. Computers and Mathematics with Applications, 5:217–230,1979.
P. Dybjer. Inductively defined sets in Martin-Löf's set theory. Technical report, Department of Computer Science, University of Göteburg/Chalmers, 1987.
S. Feferman. Transfinite recursive progressions of axiomatic theories. Journal of Symbolic Logic, 27:259–316, 1962.
S. Feferman. A language and axioms for explicit mathematics. In J. N. Crossley, editor, Algebra and Logic, volume 450 of Lecture notes in Mathematics, pages 87–139. Springer-Verlag, 1975.
J.-Y. Girard. Une extension de l'interprétation de Gödel à l'Analyse, et son application à l'Élimination des coupures dans l'Analyse et la Théorie des types. In J. E. Fenstad, editor, Second Scandinavian Logic Symposium, pages 63–92, Amsterdam, 1971. North-Holland.
P. Martin-Löf. Constructive mathematics and computer programming. In Sixth International Congress for Logic, Methodology, and Philosophy of Science, pages 153–175, Amsterdam, 1982. North Holland.
P. F. Mendler. Inductive definition in type theory. Technical Report 87-870, Department of Computer Science, Cornell University, September 1987. Ph.D. Thesis.
G. Plotkin. Call-by-name, call-by-value, and the λ-calculus. Theoretical Computer Science, pages 125–159, 1975.
S. F. Smith. From operational to denotational semantics. In MFPS 1991, Lecture notes in Computer Science, 1991. (To appear).
S. F. Smith. Partial computations in constructive type theory. Submitted to Journal of Logic and Computation, 1991.
S. Thompson. Type Theory and Functional Programming. Addison-Wesley, 1991.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1992 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Smith, S.F. (1992). Reflective semantics of constructive type theory. In: Myers, J.P., O'Donnell, M.J. (eds) Constructivity in Computer Science. Constructivity in CS 1991. Lecture Notes in Computer Science, vol 613. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0021081
Download citation
DOI: https://doi.org/10.1007/BFb0021081
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-55631-2
Online ISBN: 978-3-540-47265-0
eBook Packages: Springer Book Archive