There is a tight fit between type theories à la Martin-Löf and constructive set theories such as Constructive Zermelo-Fraenkel set theory, CZF, and its extension as well as classical Kripke-Platek set theory and extensions thereof. The technology for determining their (exact) proof-theoretic strength was developed in the 1990s. The situation is rather different when it comes to type theories (with universes) having the impredicative type of propositions Prop from the Calculus of Constructions that features in some powerful proof assistants. Aczel's sets-as-types interpretation into these type theories gives rise to rather unusual set-theoretic axioms: negative power set and negative separation. But it is not known how to determine the proof-theoretic strengths of intuitionistic set theories with such axioms via familiar classical set theories (though it is not difficult to see that ZFC plus infinitely many inaccessibles provides an upper bound). The first part of the talk will be a survey of known results from this area. The second part will be concerned with the rather special computational and proof-theoretic behavior of such theories.
- Logic Seminar