Math 873

Math 873 Advanced Topics in Foundations Spring 2017

Computing with incomplete information: The structure of the enumeration degrees

Time and place:

MWF 2:25-3:15

Van Vleck B235

Instructor:

Mariya Soskova

soskova@wisc.edu

Course description:

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.

Main references:

Rogers, Hartley, Jr. Theory of recursive functions and effective computability. McGraw-Hill Book Co., New York-Toronto, Ont.-London 1967 xx+482 pp.

Cooper, S. Barry Enumeration reducibility, nondeterministic computations and relative computability of partial functions. Recursion theory week (Oberwolfach, 1989), 57-110, Lecture Notes in Math., 1432, Springer, Berlin, 1990.

Odifreddi, P. G. Classical recursion theory. Vol. II. Studies in Logic and the Foundations of Mathematics, 143. North-Holland Publishing Co., Amsterdam, 1999. xvi+949 pp.

Articles:

Ahmad, Seema Embedding the diamond in the Sigma2 enumeration degrees. J. Symbolic Logic56 (1991), no. 1, 195-212.

Andrews, Uri; Ganchev, Hristo A; Kuyper, Rutger; Lempp, Steffen; Miller, Joseph S.; Soskova, Alexnadra A.; Soskova, Mariya I. On cototality and the skip operator in the enumeration degrees, submitted

Badillo, Liliana; Harris, Charles; Soskova, Mariya I. Enumeration 1-genericity in the local enumeration degrees, To appear in Notre Dame J. of Formal logic.

Calhoun, William C.; Slaman, Theodore A. The Pi 2 enumeration degrees are not dense. J. Symbolic Logic 61 (1996), no. 4, 1364-1379.

Casalegno, Paolo On the T-degrees of partial functions. J. Symbolic Logic 50 (1985), no. 3, 580-588.

Case, John Enumeration reducibility and partial degrees. Ann. Math. Logic 2 1970/1971 no. 4, 419-439.

Cooper, S. B. Partial degrees and the density problem. J. Symbolic Logic 47 (1982), no. 4, 854-859 (1983).

Cooper, S. B. Partial degrees and the density problem. II. The enumeration degrees of the Sigma2 sets are dense. J. Symbolic Logic 49 (1984), no. 2, 503-513.

Davis, Martin Computability and unsolvability. McGraw-Hill Series in Information Processing and Computers McGraw-Hill Book Co., Inc., New York-Toronto-London 1958 xxv+210 pp.

Friedberg, Richard M.; Rogers, Hartley, Jr. Reducibility and completeness for sets of integers. Z. Math. Logik Grundlagen Math. 5 1959 117-125.

Gutteridge, Lance Some results on enumeration reducibility. Ph.D. thesis Simon Fraser University (Canada). 1971.

Jockusch, Carl G., Jr. . Semirecursive sets and positive reducibility. Trans. Amer. Math. Soc. 131 1968 420-436.

Kent, Thomas F.; Lewis, Andrew E. M.; Sorbi, Andrea Empty intervals in the enumeration degrees. Ann. Pure Appl. Logic 163 (2012), no. 5, 567-574.

Kleene, Stephen Cole Introduction to metamathematics. D. Van Nostrand Co., Inc., New York, N. Y., 1952. x+550 pp.

Lachlan, Alistair H. and Shore, Richard A. The n-rea enumeration degrees are dense. Arch. Math Log 31(4) 1992 277-285.

Lagemann, Jay John Tuthill Embedding theorems in the reducibility ordering of partial degrees. Ph.D. thesis, MIT, 1971 43 pp.

McEvoy, Kevin Jumps of quasiminimal enumeration degrees. J. Symbolic Logic 50 (1985), no. 3, 839-848.

Myhill, John Note on degrees of partial functions. Proc. Amer. Math. Soc. 12 1961 519-521.

Sasso, Leonard P., Jr. A minimal partial degree below zero prime. Proc. Amer. Math. Soc. 38 (1973), 388-392.

Sasso, Leonard P., Jr. A survey of partial degree.J. Symbolic Logic 40 (1975), 130-140.

Selman, Alan L. Arithmetical reducibilities. I. Z. Math. Logik Grundlagen Math. 17 (1971), 335-350.

Slaman, Theodore A.; Sorbi, Andrea A note on initial segments of the enumeration degrees. J. Symb. Log. 79 (2014), no. 2, 633-643.

Soskov, Ivan N. A jump inversion theorem for the enumeration jump. Arch. Math. Logic 39 (2000), no. 6, 417-437.

Soskov, I. N.; Baleva, V. Regular enumerations. J. Symbolic Logic 67 (2002), no. 4, 1323-1343.