Peter Cholak

Professor

B.S., Union College, 1984
M.S., M.A., University of Wisconsin, 1988
Ph.D., University of Wisconsin, 1991

Research Interests

The area of mathematics which I am most interested in is Computability Theory which is also known by the name of Recursion Theory. In particular, I am interested in the relationship between computational complexity and various other mathematical objects. (Two common measures of computation complexity are the Turing and polynomial-time reducibilities but there are many others.) Some examples of this relationship from my work: every non-trivial orbit in the lattice of enumerable sets contains a set with a high Turing degree, the question of whether a logic program is locally stratified is undecidable and the theory of the parameterized polynomial time degrees is undecidable and every computable 2 coloring of pairs of natural numbers has a low$_2$ homogeneous set. The last example is particularly interesting since its proof can be used to show the first-order consequences of Ramsey Theorem for pairs is a subset of the first-order consequences of RCA$_0$ plus induction for $\Sigma^0_3$ formulas. There are many other examples in the literature.

Selected Publications

• Computability Theory and Its Applications: Current Trends and Open Problems, (editor, with S. Lempp, M. Lerman and R. Shore), Contenporary Mathematics, 257. American Mathematical Society, Providence, RI, 2000. xvi+320 pages.
• Definable encodings in the computably enumerable sets, (with L. Harrington), J. Symbolic Logic 6:185 - 196, 2000.
• The Strength of Ramsey's Theorem for Pairs (with C. Jockusch and T. Slaman), Symbolic Logic 66:1-55, 2001.
• Automorphisms of the lattice of $\Pi_1^0$ classes; prefect thin classes and anc degrees, (with R. Coles, R. Downey and E. Herrmann), Trans. Amer. Math. Soc. 353 (2001), 4899-4924.
• Peter Cholak and Leo A. Harrington. On the definability of the double jump in the computably enumerable sets. J. Math. Log., 2(2):261–296, 2002.
• Peter Cholak, Rodney Downey, and Leo A. Harrington. On the orbits of computably enumerable sets. J. Amer. Math. Soc., 21 (4):1105-1135, 2008.
• Peter A. Cholak and Leo A. Harrington. Isomorphisms of splits of computably enumerable sets. J. Symbolic Logic, 68(3):1044–1064, 2003. .

Please direct questions and comments to: Peter.Cholak.1@nd.edu