Sets in types, types in sets

B Werner - International Symposium on Theoretical Aspects of …, 1997 - Springer
International Symposium on Theoretical Aspects of Computer Software, 1997Springer
We present two mutual encodings, respectively of the Calculus of Inductive Constructions in
Zermelo-Fraenkel set theory and the opposite way. More precisely, we actually construct two
families of encodings, relating the number of universes in the type theory with the number of
inaccessible cardinals in the set theory. The main result is that both hierarchies of logical
formalisms interleave wrt expressive power and thus are essentially equivalent. Both
encodings are quite elementary: type theory is interpreted in set theory through a …
Abstract
We present two mutual encodings, respectively of the Calculus of Inductive Constructions in Zermelo-Fraenkel set theory and the opposite way. More precisely, we actually construct two families of encodings, relating the number of universes in the type theory with the number of inaccessible cardinals in the set theory. The main result is that both hierarchies of logical formalisms interleave w.r.t. expressive power and thus are essentially equivalent. Both encodings are quite elementary: type theory is interpreted in set theory through a generalization of Coquand's simple proof-irrelevance interpretation. Set theory is encoded in type theory using a variant of Aczel's encoding; we have formally checked this last part using the Coq proof assistant.
Springer