Home  Online Resources  Table of Contents

Journal of Logic and Computation, Volume 11, Issue 4, pp. 545-557: Abstract.

Embedding First-order Logic in a Pure Type System with Parameters

Twan Laan, and Michael Franssen

Eindhoven University of Technology, P.O.Box 513 / HG 7.37, 5600 MB Eindhoven, The Netherlands. E-mail: twan.laan@wxs.nl; E-mail: mfranssen@usa.net

A standard way to code first-order predicate logic in a propositions-as-types style uses a type system that is a variant of the pure type system [lambda]P. Types in this system are not necessarily in [beta]-normal form. Therefore, checking whether two types are [beta]-equal is decidable, albeit sometimes costly in terms of time and/or memory. In this paper we present an alternative to Berardi's system, based on pure type systems with parameters. We show that all types in our system are in [beta]-normal form, which is an advantage for implementations. Moreover, the syntactical structure of the system with parameters is similar to the syntax of first-order predicate logic. This is not the case for the system without parameters.

Keywords: First-, order predicate logic, pure type systems, type theory

  Full-Text PDF  (157 KB)

[ Oxford University Press]   [ Oxford Journals]   [ Comments & Feedback]   Copyright© Oxford University Press, 2001.