Search code examples
logiccoqisabellelean

Is it possible to convert all higher-order logic and dependent type in Lean/Isabelle/Coq into first-order logic?


More specially, given arbitrary Lean proof/theorem, is it possible to express it solely using first-order logic? If so, is it practical, i.e. the generated FOL will not be enormously large?

I have seen https://www.cl.cam.ac.uk/~lp15/papers/Automation/translations.pdf, but since I am not an expert, I am still not sure whether all Lean's proof code can be converted.

Other mathematical proof languages are also OK.


Solution

  • The short answer is: yes, it is not impractically large and this is done in particular when translating proofs to SMT solvers for sledgehammer-like tools. There is a fair amount of blowup, but it is a linear factor on the order of 2-5. You probably lose more from not having specific support for all the built in rules, and in the case of DTT, writing down all the defeq proofs which are normally implicit.