Logical Structure of Constructive Set Theories
Robert Paßmann

Abstract:
The tautologies and admissible rules of a formal system may exceed those of its underlying logic. For example, Diaconescu, Goodman and Myhill showed that any set theory containing the axioms (and schemes) of extensionality, empty set, pairing, separation and choice proves the law of excluded middle---even if that set theory is based on intuitionistic logic.

The goal of this dissertation is, roughly speaking, to study situations where this is not the case: we show that many intuitionistic and constructive set theories are loyal to their underlying logic. We say that a formal system is (propositional/first-order) tautology loyal if its (propositional/first-order) tautologies are exactly those of its underlying logic. We call a formal system (propositional/first-order) rule loyal if its (propositional/first-order) admissible rules are exactly those of its underlying logic.

Using Kripke models with classical domains, we show that intuitionistic Kripke--Platek set theory (IKP) is first-order loyal (Chapter 4). Moreover, we introduce a realisability notion based on Ordinal Turing Machines that allows us to prove that IKP is propositional rule loyal, as well (Chapter 7). This notion of realisability also lends itself to realising infinitary set theories.

We introduce blended models for intuitionistic Zermelo--Fraenkel set theory (IZF) to show that this system is propositional tautology loyal (Chapter 5). A variation of this technique is useful for studying the admissible rules of various constructive set theories and proving that they are propositional rule loyal (Chapter 6).

Finally, we also prove that constructive Zermelo--Fraenkel set theory (CZF) is first-order tautology loyal as well as propositional rule loyal (Chapter 8). To this end, we introduce a new notion of transfinite computability, the so-called Set Register Machines. We combine the resulting notion of realisability with Beth models to show that CZF is first-order tautology loyal.