Set theory, it has been contended, developed from its beginnings through a progression of mathematical moves, despite being intertwined with pronounced metaphysical attitudes and exaggerated foundational claims that have been held on its behalf. In this paper, the seminal results of set theory are woven together in terms of a unifying mathematical motif, one whose transmutations serve to illuminate the historical development of the subject. The motif is foreshadowed in Cantor's diagonal proof, and emerges in the interstices of the inclusion vs. membership distinction, a distinction only clarified at the turn of this century, remarkable though this may seem. Russell runs with this distinction, but is quickly caught on the horns of his well-known paradox, an early expression of our motif. The motif becomes fully manifest through the study of functions of the power set of a set into the set in the fundamental work of Zermelo on set theory. His first proof in 1904 of his Well-Ordering Theoremis a central articulation containing much of what would become familiar in the subsequent development of set theory. Afterwards, the motif is cast by Kuratowski as a fixed point theorem, one subsequently abstracted to partial orders by Bourbaki in connection with Zorn's Lemma. Migrating beyond set theory, that generalization becomes cited as the strongest of fixed point theorems useful in computer science.

Section 1 describes the emergence of our guiding motif as a line of development from Cantor's diagonal proof to Russell's Paradox, fueled by the clarification of the inclusion vs. membership distinction. Section 2 engages the motif as fully participating in Zermelo's work on the Well-Ordering Theorem and as newly informing on Cantor's basic result that there is no bijection . Then Section 3 describes in connection with Zorn's Lemma the transformation of the motif into an abstract fixed point theorem, one accorded significance in computer science.

As an undergraduate I was taught to multiply two numbers with the help of log tables, using the formula

Having graduated to teach calculus to Engineers, I learned that log tables were to be replaced by slide rules. It was then that Imade the fateful decision that there was no need for me to learn how to use this tedious device, as I could always rely on the students to perform the necessary computations. In the course of time, slide rules were replaced by pocket calculators and personal computers, but I stuck to my original decision.

My computer phobia did not prevent me from taking an interest in the theoretical question: what is a computation? This question goes back to Hilbert's 10th problem (see Browder [1976]), which asks for an algorithm, or computational procedure, to decide whether any given polynomial equation is solvable in integers. It quickly leads to the related question: which numerical functions f : ℕn → ℕ are computable?

While Hilbert's 10th problem was only resolved in 1970, this related question had some earlier answers, of which I shall single out the following three:

(1) f is recursive (Gödel, Kleene),

(2) f is computable on an abstract machine (Turing, Post),

(3) f is definable in the untyped λ-calculus (Church, Kleene).

These tentative answers were shown to be equivalent by Church [1936] and Turing [1936–7].

I shall discuss here some of the more recent developments of these notions of computability and their relevance to linguistics and logic. I hope to be forgiven for dwelling on some of the work I have been involved with personally, with greater emphasis than is justified by its historical significance.

We announce two new dichotomy theorems for Borel equivalence relations, and present the results in context by giving an overview of related recent developments.

§1. Introduction. For X a Polish (i.e., separable, completely metrizable) space and E a Borel equivalence relation on X, a (complete) classification of X up to E-equivalence consists of finding a set of invariants I and a map c : X → I such that xEy ⇔ c(x) = c(y). To be of any value we would expect I and c to be “explicit” or “definable”. The theory of Borel equivalence relations investigates the nature of possible invariants and provides a hierarchy of notions of classification.

The following partial (pre-)ordering is fundamental in organizing this study. Given equivalence relations E and F on X and Y, resp., we say that E can be Borel reduced to F, in symbols

if there is a Borel map f : X → Y with xEy ⇔ f(x)Ff(y). Then if is an embedding of X/E into Y/F, which is “Borel” (in the sense that it has a Borel lifting).

Intuitively, E ≤BF might be interpreted in any one of the following ways:

(i) The classi.cation problem for E is simpler than (or can be reduced to) that of F: any invariants for F work as well for E (after composing by an f as above).

(ii) One can classify E by using as invariants F-equivalence classes.

(iii) The quotient space X/E has “Borel cardinality” less than or equal to that of Y/F, in the sense that there is a “Borel” embedding of X/E into Y/F.

A new games model of the language FPC, a type theory with products, sums, function spaces and recursive types, is described. A definability result is proved, showing that every finite element of the model is the interpretation of some term of the language.