Department of Mathematics

Van Vleck Hall, 480 Lincoln Drive, Madison, WI

Math 873: Advanced Topics in Foundations (Spring)

Joe Miller, Spring 2018:
Computing with incomplete information: The structure of the enumeration degrees
Mariya Soskova (Spring 2017)

Enumeration reducibility is a relation between sets of natural numbers. It was introduced in 1959 by Friedberg and Rogers and was motivated by the desire to capture the notion of computability relative to a partial oracle. Intuitively, a set of natural numbers A is enumeration reducible to a set of natural numbers B  if every enumeration of B can be effectively transformed into an enumeration of A. This effective transformation is formalized by a c.e. set, which we call an enumeration operator. In contrast to a Turing reduction, which generates a complete description of the membership relation of a set from a complete description of the membership relation of another set, an enumeration reduction generates positive information from positive information.  The enumeration degrees give a structural representation of the enumeration reducibility. This degree structure can be viewed as an extension of the Turing degrees, as there is a natural structure preserving embedding of the Turing degrees into the enumeration degrees. On the other hand, the enumeration degrees can be viewed as a substructure of the Medvedev degrees.  In recent years the structure of the enumeration degrees has attracted a lot of interest, mainly due to the discovery of a large collection of first order definable classes in the structure.

The focus of this course will be on the relationship between the enumeration degrees and the Turing degrees. We will explore structural differences and similarities. We will discuss the complexity of their theories. We will talk about the standard local substructures and the relationship between them. We will describe recent advancements in understanding the definable relations on the enumeration degrees. We will also give a few applications of enumeration reducibility to other subfields of computability theory, such as computable structure theory and computable analysis.

Although our knowledge of the properties of the Turing degrees will motivate the questions that we ask in this course, I will not assume a thorough understanding of degree theory and its methods. A basic knowledge of computability theory will be assumed.

There is no required textbook.


Math 770, and Math 773 or concurrent registration in Math 773

UW-Madison Department of Mathematics
Van Vleck Hall
480 Lincoln Drive
Madison, Wi  53706

(608) 263-3054

Contact Us

Got a question about
accessibility, content
or structure of this website?