Source author record

Peter A. Cholak

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.LO

Catalog footprint

Research overview

6works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Some results concerning the $\mathsf{SRT}^2_2$ vs. $\mathsf{COH}$ problem

The $\mathsf{SRT}^2_2$ vs.\ $\mathsf{COH}$ problem is a central problem in computable combinatorics and reverse mathematics, asking whether every Turing ideal that satisfies the principle $\mathsf{SRT}^2_2$ also satisfies the principle $\mathsf{COH}$ . This paper is a contribution towards further developing some of the main techniques involved in attacking this problem. We study several principles related to each of $\mathsf{SRT}^2_2$ and $\mathsf{COH}$ , and prove results that highlight the limits of our current understanding, but also point to new directions ripe for further exploration.

preprint2016arXiv

Generics for Mathias forcing over general Turing ideals

In Mathias forcing, conditions are pairs $(D,S)$ of sets of natural numbers, in which $D$ is finite, $S$ is infinite, and $\max D < \min S$ . The Turing degrees and computational characteristics of generics for this forcing in the special (but important) case where the infinite sets $S$ are computable were thoroughly explored by Cholak, Dzhafarov, Hirst, and Slaman~\cite{CDHS-2014}. In this paper, we undertake a similar investigation for the case where the sets $S$ are members of general countable Turing ideals, and give conditions under which generics for Mathias forcing over one ideal compute generics for Mathias forcing over another. It turns out that if $\mathcal{I}$ does not contain only the computable sets, then non-trivial information can be encoded into the generics for Mathias forcing over $\mathcal{I}$ . We give a classification of this information in terms of computability-theoretic properties of the ideal, using coding techniques that also yield new results about introreducibility. In particular, we extend a result of Slaman and Groszek and show that there is an infinite $Δ^0_3$ set with no introreducible subset of the same degree.

preprint2012arXiv

On Mathias generic sets

We present some results about generics for computable Mathias forcing. The $n$ -generics and weak $n$ -generics in this setting form a strict hierarchy as in the case of Cohen forcing. We analyze the complexity of the Mathias forcing relation, and show that if $G$ is any $n$ -generic with $n \geq 3$ then it satisfies the jump property $G^{(n-1)} = G' \oplus \emptyset^{(n)}$ . We prove that every such $G$ has generalized high degree, and so cannot have even Cohen 1-generic degree. On the other hand, we show that $G$ , together with any bi-immune set $A \leq_T \emptyset^{(n-1)}$ , computes a Cohen $n$ -generic set.

preprint2011arXiv

Computably enumerable partial orders

We study the degree spectra and reverse-mathematical applications of computably enumerable and co-computably enumerable partial orders. We formulate versions of the chain/antichain principle and ascending/descending sequence principle for such orders, and show that the former is strictly stronger than the latter. We then show that every $\emptyset'$ -computable structure (or even just of c.e.\ degree) has the same degree spectrum as some computably enumerable (co-c.e.)\ partial order, and hence that there is a c.e.\ (co-c.e.)\ partial order with spectrum equal to the set of nonzero degrees.

preprint2010arXiv

On n-Tardy Sets

Harrington and Soare introduced the notion of an n-tardy set. They showed that there is a nonempty $\mathcal{E}$ property Q(A) such that if Q(A) then A is 2-tardy. Since they also showed no 2-tardy set is complete, Harrington and Soare showed that there exists an orbit of computably enumerable sets such that every set in that orbit is incomplete. Our study of n-tardy sets takes off from where Harrington and Soare left off. We answer all the open questions asked by Harrington and Soare about n-tardy sets. We show there is a 3-tardy set A that is not computed by any 2-tardy set B. We also show that there are nonempty $\mathcal{E}$ properties $Q_n(A)$ such that if $Q_n(A)$ then A is properly n-tardy.

preprint2007arXiv

The Complexity of Orbits of Computably Enumerable Sets

The goal of this paper is to announce there is a single orbit of the c.e. sets with inclusion, $\E$, such that the question of membership in this orbit is $Σ^1_1$ -complete. This result and proof have a number of nice corollaries: the Scott rank of $\E$ is $\wock +1$; not all orbits are elementarily definable; there is no arithmetic description of all orbits of $\E$; for all finite $α\geq 9$ , there is a properly $Δ^0_α$ orbit (from the proof). A few small corrections made in this version

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Peter A. Cholak

Research overview

Is this your work?

6 publications

Some results concerning the $\mathsf{SRT}^2_2$ vs. $\mathsf{COH}$ problem

Generics for Mathias forcing over general Turing ideals

On Mathias generic sets

Computably enumerable partial orders

On n-Tardy Sets

The Complexity of Orbits of Computably Enumerable Sets

See the researcher in context

Building this map preview

Peter A. Cholak

Research overview

Is this your work?

6 publications

Some results concerning the SRT22\mathsf{SRT}^2_2SRT22​ vs. COH\mathsf{COH}COH problem

Generics for Mathias forcing over general Turing ideals

On Mathias generic sets

Computably enumerable partial orders

On n-Tardy Sets

The Complexity of Orbits of Computably Enumerable Sets

See the researcher in context

Building this map preview

Some results concerning the $\mathsf{SRT}^2_2$ vs. $\mathsf{COH}$ problem