Modified Realizability Toposes and Strong Normalization Proofs
Lists
Only you see this
Abstract
This paper is motivated by the discovery that an appropriate quotient SN of the strongly normalising untyped λ *-terms (where * is just a formal constant) forms a partial applicative structure with the inherent application operation. The quotient structure satisfies all but one of the axioms of a partial combinatory algebra (pca). We call such partial applicative structures conditionally partial combinalory algebras (c-pca). Remarkably, an arbitrary rightabsorptive c-pca gives rise to a tripos provided the underlying intuitionistic predicate logic is given an interpretation in the style of Kreisel's modified realizabilily, as opposed to the standard Kleene-style realizability. Starting from an arbitrary right-absorptive C-PCA U, the tripos-to-topos construction due to Hyland et al. can then be carried out to build a modified realizability topos TOPm(U) of non-standard sets equipped with an equality predicate. Church's Thesis is internally valid in TOP m (K 1) (where the pca k 1 is “Kleene's first model” of natural numbers) but not Markov's Principle. There is a topos inclusion of SET-the “classical” topos of sets-into TOP m(U); the image of the inclusion is just sheaves for the ⌝⌝-topology. Separated objects of the ⌝⌝-topology are characterized. We identify the appropriate notion of PER's (partial equivalence relations) in the modified realizability setting and state its completeness properties. The topos TOP m (U) has enough completeness property to provide a category-theoretic semantics for a family of higher type theories which include Girard's System F and the Calculus of Constructions due to Coquand and Huet. As an important application, by interpreting type theories in the topos TOP m (SN.), a clean semantic explanation of the Tait-Girard style strong normalization argument is obtained. We illustrate how a strong normalization proof for an impredicative and dependent type theory may be assembled from two general “stripping arguments” in the framework of the topos TOP m (SN.). This opens up the possibility of a “generic” strong normalization argument for an interesting class of type theories.
BibTeX
@inproceedings{hyland1993modified,
author = {J. M. E. Hyland and C.-H. Luke Ong},
title = {{Modified Realizability Toposes and Strong Normalization Proofs}},
booktitle = {TLCA},
year = {1993},
url = {https://openreview.net/forum?id=BizUUlH0Vap},
}Loading related content...