FOM: "definability theory"

Stephen G Simpson simpson at
Sun Aug 30 19:17:07 EDT 1998

Wayne Richter writes:
 > As Joe has mentioned, some form of definability is at the heart of
 > recursion theory, and quite similar notions of definability seem to
 > be at the heart of complexity theory as well.

This reminds me of an episode in the 1970's.  I'll relate it here for
what it's worth.  

What happened was that a group of people including Jon Barwise and
Yiannis Moschovakis proposed "definability theory" as an umbrella term
for a collection of topics which included inductive definitions and at
least parts of generalized recursion theory.  For several years
Barwise's plan as editor of the Handbook of Mathematical Logic was for
"definability theory" to be one of the principal divisions of that
book.  In the end, this plan didn't fly.  "Definability theory" was
abandoned, and the Handbook stayed with the traditional 4-fold scheme
whereby mathematical logic is partitioned into model theory, proof
theory, recursion theory, and set theory.

I never learned exactly what went wrong, but I suspect at least part
of the problem was that people couldn't agree on the boundaries of
"definability theory".  Does it include descriptive set theory?
degrees of unsolvability?  r.e. sets?  complexity theory?  Beth's
definability theorem?  To be sure, definability is a theme in many
parts of mathematical logic, and there are many analogies.  But maybe
it's not so easy to turn these analogies into a subject.

-- Steve

More information about the FOM mailing list