Definability, Automorphisms, and Dynamic Properties of Computably Enumerable Sets

We announce and explain recent results on the computably enumerable (c.e.) sets, especially their definability properties (as sets in the spirit of Cantor), their automorphisms (in the spirit of Felix Klein's Erlanger Programm), their dynamic properties, expressed in terms of how quickly elements enter them relative to elements entering other sets, and the Martin Invariance Conjecture on their Turing degrees, i.e., their information content with respect to relative computability (Turing reducibility). 1 Introduction All functions are on the nonnegative integers, ! = f0; 1; 2; : : : g, and all sets will be subsets of !. Turing and Godel informally called a function computable if it can be calculated by a mechanical procedure, and regarded this as being synonymous with being specified by an "algorithm " or a "finite combinatorial procedure." They each formalized it as follows. 1 The first author was supported by National Science Foundation Grant DMS 9214048, and the second author by..