Peter Cholak


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

Office: 122 Hayes-Healy
Phone: (574) 631-6507
Fax: (574) 631-6579

For additional information see Peter Cholak’s Personally Maintained Page.

Research Interests

The area of mathematics that I am most interested in is Computability Theory, which is also known as 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

  • Cholak, Peter A.; Downey, Rodney; Harrington, Leo A. On the orbits of computably enumerable sets. J. Amer. Math. Soc. 21 (2008), no. 4, 1105--1135.

  • Cholak, Peter; Downey, Rod; Greenberg, Noam Strong jump-traceabilty. I. The computably enumerable case. Adv. Math. 217 (2008), no. 5, 2045--2074.

  • Cholak, Peter A.; Harrington, Leo A. Extension theorems, orbits, and automorphisms of the computably enumerable sets. Trans. Amer. Math. Soc. 360 (2008), no. 4, 1759--1791.

  • Cholak, Peter; Greenberg, Noam; Miller, Joseph S. Uniform almost everywhere domination. J. Symbolic Logic 71 (2006), no. 3, 1057--1072

If you have access to MathSciNet you can see a complete list of publications.

Please direct questions and comments to: