We define a realizability interpretation of Aczel's Constructive Set Theory CZF into Explicit Mathematics. The final results are that CZF extended by Mahlo principles is realizable in corresponding extensions of T 0 , thus providing relative lower bounds for the proof-theoretic strength of the latter.

One objective of this paper is the determination of the proof-theoretic strength of Martin-Löf's type theory with a universe and the type of well-founded trees. It is shown that this type system comprehends the consistency of a rather strong classical subsystem of second order arithmetic, namely the one with Δ 2 1 comprehension and bar induction. As Martin-Löf intended to formulate a system of constructive (intuitionistic) mathematics that has a sound philosophical basis, this yields a constructive consistency proof of a (...) strong classical theory. Also the proof-theoretic strength of other inductive types like Aczel's type of iterative sets is investigated in various contexts.Further, we study metamathematical relations between type theories and other frameworks for formalizing constructive mathematics, e.g. Aczel's set theories and theories of operations and classes as developed by Feferman. (shrink)

We define a novel interpretation R of second order arithmetic into Explicit Mathematics. As a difference from standard D-interpretation, which was used before and was shown to interpret only subsystems proof-theoretically weaker than T 0 , our interpretation can reach the full strength of T 0 . The R-interpretation is an adaptation of Kleene's recursive realizability, and is applicable only to intuitionistic theories.

It is shown that an intuitionistic model of set theory with the axiom of choice has to be a classical one.