We formulate epsilon substitution method for elementary analysisEA (second order arithmetic with comprehension for arithmetical formulas with predicate parameters). Two proofs of its termination are presented. One uses embedding into ramified system of level one and cutelimination for this system. The second proof uses non-effective continuity argument.

Constructive Zermelo–Fraenkel set theory, CZF, can be interpreted in Martin-Löf type theory via the so-called propositions-as-types interpretation. However, this interpretation validates more than what is provable in CZF. We now ask ourselves: is there a reasonably simple axiomatization of the set-theoretic formulae validated in Martin-Löf type theory? The answer is yes for a large collection of statements called the mathematical formulae. The validated mathematical formulae can be axiomatized by suitable forms of the axiom of choice.The paper builds on a self-interpretation (...) of CZF IOS Press, Amsterdam, 2004 ]) that provides an “inner” model of CZF which also validates the so-called -axiom of choice, . The crucial technical step taken in the present paper is to investigate the absoluteness properties of this model under the hypothesis .It is also shown that CZF plus the -axiom of choice possesses the disjunction property, the numerical existence property and the existence property for an important group of formulae. (shrink)

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.

We prove here that the intuitionistic theory $T_{0}\upharpoonright + UMID_{N}$ , or even $EEJ\upharpoonright + UMID_{N}$ , of Explicit Mathematics has the strength of $\prod_{2}^{1} - CA_{0}$ . In Section I we give a double-negation translation for the classical second-order $\mu-calculus$ , which was shown in [ $M\ddot{o}02$ ] to have the strength of $\prod_{2}^{1}-CA_{0}$ . In Section 2 we interpret the intuitionistic $\mu-calculus$ in the theory $EETJ\upharpoonright + UMID_{N}$ . The question about the strength of monotone inductive definitions in (...) $T_{0}$ was asked by S. Feferman in 1982, and - assuming classical logic - was addressed by M. Rathjen. (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.

An instance of Stratified Comprehension ∀x₁ … ∀x n ∃y∀x (x ∈ y ↔ φ(x, x₁, …, x n )) is called strictly impredicative iff, under minimal stratification, the type of x is 0. Using the technology of forcing, we prove that the fragment of NF based on strictly impredicative Stratified Comprehension is consistent. A crucial part in this proof, namely showing genericity of a certain symmetric filter, is due to Robert Solovay. As a bonus, our interpretation also satisfies some (...) instances of Stratified Comprehension which are not strictly impredicative. For example, it verifies existence of Frege natural numbers. Apparently, this is a new subsystem of NF shown to be consistent. The consistency question for the whole theory NF remains open (since 1937). (shrink)