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 Naïve 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, "naïve" and "formal" are contrasting words. The present treatment might best be described as informal type theory from a naïve 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-Löf, 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: http://www.nuprl.org/html/NaiveTypeTheoryRevisions.html