Peter Cholak

Professor, Associate Chair

Education

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

Research Group

Logic

Research Area

Computability theory

Bio

Research Interests

Cholak works in computability theory. In particular, Cholak focuses on the relationship between computability and definability. A classic example is Post’s result that the set of integers accepted by a Turing machine is a $\Sigma^0_1$ definable set in arithmetic. Another example is the result of Cholak and his coauthors that the question of whether two c.e. sets are in the same orbit in the structure of c.e. sets is $\Pi^1_1$ complete. Cholak has also spent a lot of time and energy exploring what is possible in the orbits of c.e. sets. The answer is that basically anything is possible. Some other examples of the relationship between computability and definability from Cholak and his co­author include: Every computable two coloring of pairs of integers has a low$_2$ homogenous set. Then translated to reverse mathematics this implies the Ramsey Theorem for pairs and two colors is $\Pi^1_1 conservative over RCA_0 plus induction for $\Sigma^0_2$ formulas. A recent result shows that every effectively prime model are also effectively atomic. The best way to learn more about Cholak's mathematical interests is to explore his papers and talks which can be found on his personal website and on MathSciNet. You can start with the list below.

Selected Publications

• Peter Cholak, Rodney Downey, and Leo A. Harrington. On the orbits of computably enumerable sets. J. Amer. Math. Soc., 21(4):1105­1135, 2008. Pdf. MR MR2425182.
• Peter Cholak, Carl G. Jockusch, and Theodore A. Slaman. On the strength of Ramsey's theorem for pairs. J. Symbolic Logic, 66(1):1­55, 2001. Errata. Pdf. MR 2002c:03094.
• Peter Cholak, Peter Gerdes, and Karen Lange. The D­maximal sets. J. Symbolic Logic, 2015. Accepted. Pdf.
• Peter Cholak, Rod Downey, and Greg Igusa. Any FIP real computes a 1­generic. Submitted, 2015. Pdf.

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