Naive Computational Type Theory

unofficial copies [PDF], [PS]

by Robert L. Constable

Proof and System-Reliability, H. Schwichtenberg and R. Steinbruggen (eds.), pp. 213-259, 2002.


The basic concepts of type theory are fundamental to computer science, logic and mathematics. Indeed, the language of type theory connects these regions of science. It plays a role in computing and information science akin to that of set theory in pure mathematics.

There are many excellent accounts of the basic ideas of type theory, especially at the interface of computer science and logic specifically, in the literature of programming languages, semantics, formal methods and automated reasoning. Most of these are very technical, dense with formulas, inference rules, and computation rules. Here we follow the example of the mathematician Paul Halmos, who in 1960 wrote a 104-page book called Nave Set Theory intended to make the subject accessible to practicing mathematicians. His book served many generations well.

This article follows the spirit of Halmos' book and introduces type theory without recourse to precise axioms and inference rules, and with a minimum of formalism. I start by paraphrasing the preface to Halmos' book. The sections of this article follow his chapters closely.

Every computer scientist agrees that every computer scientist must know some type theory; the disagreement begins in trying to decide how much is some. This article contains my partial answer to that question. The purpose of the article is to tell the beginning student of advanced computer science the basic type theoretic facts of life, and to do so with a minimum of philosophical discourse and logical formalism. The point throughout is that of a prospective computer scientist eager to study programming languages, or database systems, or computational complexity theory, or distributed systems or information discovery.

In type theory, "nave" and "formal" are contrasting words. The present treatment might best be described as informal type theory from a nave point of view. The concepts are very general and very abstract; therefore they may take some getting used to. It is a mathematical truism, however, that the more generally a theorem applies, the less deep it is. The student's task in learning type theory is to steep himself or herself in unfamiliar but essentially shallow generalities until they become so familiar that they can be used with almost no conscious effort.

Type theory has been well exposited in articles by N. G. de Bruijn and the Automath group; the writings of Per Martin-Lf, the originator of many of the basic ideas; the writings of Jean-Yves Girard, another originator; the writings of the Coq group, the Cornell group, and the Gothenberg group; and the writings of others who have collectively expanded and applied type theory.

What is new in this account is treatment of classes and computational complexity theory along lines that seem very natural. This approach to complexity theory raises many new questions.

Table of Contents

Section 1: Types And Equality
Section 2: Subtypes And Set Types
Section 3: Pairs
Section 4: Union And Intersection
Section 5: Functions And Relations
Section 6: Universes, Powers And Openness
Section 7: Families
Section 8: Lists And Numbers
Section 9: Logic And The Peano Axioms
Section 10: Structures, Records And Classes
Section 11: The Axiom Of Choice
Section 12: Computational Complexity

Revision history: