Large Model Constructions for Second-Order ZF in Dependent Type Theory
We study various models of classical second-order set theories in the dependent type theory of Coq. Without logical assumptions, Aczel's sets-as-trees interpretation yields an intensional model of second-order ZF with functional replacement. Building on work of Werner and Barras, we discuss the need for quotient axioms in order to obtain extensional models with relational replacement and to construct large sets. Specifically, we show that the consistency strength of Coq extended by excluded middle and a description operator on well-founded trees allows for constructing models with exactly $n$ Grothendieck universes for every natural number $n$. By a previous categoricity result based on Zermelo's embedding theorem, it follows that those models are unique up to isomorphism. Moreover, we show that the smallest universe contains exactly the hereditarily finite sets and give a concise independence proof of the foundation axiom based on permutation models.
Tue 9 JanDisplayed time zone: Tijuana, Baja California change
13:30 - 15:30 | Type Theory, Set Theory, and Formalized MathematicsCPP at Museum A Chair(s): Thorsten Altenkirch University of Nottingham | ||
13:30 30mTalk | Finite Sets in Homotopy Type Theory CPP Dan Frumin Radboud University, Herman Geuvers Radboud University Nijmegen, Netherlands, Léon Gondelman LRI, Université Paris-Sud, Niels van der Weide Radboud University Nijmegen, Netherlands DOI | ||
14:00 30mTalk | Generic Derivation of Induction for Impredicative Encodings in Cedille CPP DOI | ||
14:30 30mTalk | Large Model Constructions for Second-Order ZF in Dependent Type Theory CPP DOI | ||
15:00 30mTalk | A Constructive Formalisation of Semi-algebraic Sets and Functions CPP Boris Djalal INRIA |