Automated theorem proving for dependent typed theories via a translation to higher-order logic
Higher-order logic (HOL) offers a simple syntax and semantics for representing and reasoning about typed mathematical concepts. There are many state-of-the-art automated theorem provers for HOL. But the type system of HOL lacks advanced features where types may depend on terms. This is useful as many mathematical notions are inherently dependent typed. Dependent type theory offers such a rich type system but has rather substantial conceptual differences to HOL and isn’t supported as well by automated theorem provers. We introduce a dependently typed extension DHOLP of HOL that supports dependent types while retaining the style and conceptual framework of HOL. Moreover, we describe one translation from DHOLP and a second one from one of its fragments to HOL and prove the soundness and completeness of the translations. We implement both translations within the MMT system—a system for formalizing mathematics—where they are combined with a HOL prover into an automated theorem prover for DHOLP. Finally, we formalize basic set theory notions in DHOLP and outline how such a formalization can be combined with a recent translation of the language of the Mizar proof assistant to MMT to obtain an automated theorem prover for problems in the language of the Mizar proof assistant.