Mechanizing higher order logic on top of set theory

Mike Gordon FRS

(University of Cambridge)

Set theory is the standard foundation for mathematics. However, the majority of general purpose mechanized proof assistants support versions of type theory (higher order logic). Examples include Alf, Automath, Coq, Ehdm, HOL, IMPS, Lambda, LEGO, Nuprl, PVS and Veritas. For many applications type theory works well and provides, for specification, the benefits of type-checking that are well-known in programming. However, there are areas where types get in the way or seem unmotivated. Furthermore, most people with a scientific or engineering background already know set theory, whereas type theory may appear inaccessable and so be an obstacle to the uptake of proof assistants based on it.

My talk will describe some experiments (using the HOL system) in combining set theory and type theory; the aim is to get the best of both worlds in a single system. Three approaches have been tried, all based on an axiomatically specified type V of ZF-like sets:

1. HOL is used without any additions besides V
2. a "hard-wired" shallow embedding of the HOL logic into V is provided
3. a mechanism is implemented for converting HOL axiomatic theories into set-theoretic definitional theories

These approaches are illustrated with two examples: the construction of lists and a simple lemma in group theory. Various advantages and disadvantages are discussed and some tentative conclusions drawn.

Knowledge of HOL will not be assumed.
Tuesday 29th November 1994, 14:30
Seminar Room 322
Department of Computer Science