Source author record

Damir Dzhafarov

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

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

COH, SRT22, and multiple functionals

We prove the following result: there is a family $R = \langle R_0,R_1,\ldots \rangle$ of subsets of $ω$ such that for every stable coloring $c : [ω]^2 \to k$ hyperarithmetical in $R$ and every finite collection of Turing functionals, there is an infinite homogeneous set $H$ for $c$ such that none of the finitely many functionals map $R \oplus H$ to an infinite cohesive set for $R$ . This extends the current best partial results towards the $\mathsf{SRT}^2_2$ vs. $\mathsf{COH}$ problem in reverse mathematics, and is also a partial result towards the resolution of several related problems, such as whether $\mathsf{COH}$ is omnisciently computably reducible to $\mathsf{SRT}^2_2$ .

preprint2020arXiv

The determined property of Baire in reverse math

We define the notion of a determined Borel code in reverse math, and consider the principle $DPB$ , which states that every determined Borel set has the property of Baire. We show that this principle is strictly weaker than $ATR$ . Any $ω$ -model of $DPB$ must be closed under hyperarithmetic reduction, but $DPB$ is not a theory of hyperarithmetic analysis. We show that whenever $M\subseteq 2^ω$ is the second-order part of an $ω$ -model of $DPB$ , then for every $Z \in M$ , there is a $G \in M$ such that $G$ is $Δ^1_1$ -generic relative to $Z$ .

preprint2016arXiv

Coloring trees in reverse mathematics

The tree theorem for pairs ( $\mathsf{TT}^2_2$ ), first introduced by Chubb, Hirst, and McNicholl, asserts that given a finite coloring of pairs of comparable nodes in the full binary tree $2^{<ω}$ , there is a set of nodes isomorphic to $2^{<ω}$ which is homogeneous for the coloring. This is a generalization of the more familiar Ramsey's theorem for pairs ( $\mathsf{RT}^2_2$ ), which has been studied extensively in computability theory and reverse mathematics. We answer a longstanding open question about the strength of $\mathsf{TT}^2_2$ , by showing that this principle does not imply the arithmetic comprehension axiom ( $\mathsf{ACA}_0$ ) over the base system, recursive comprehension axiom ( $\mathsf{RCA}_0$ ), of second-order arithmetic. In addition, we give a new and self-contained proof of a recent result of Patey that $\mathsf{TT}^2_2$ is strictly stronger than $\mathsf{RT}^2_2$ . Combined, these results establish $\mathsf{TT}^2_2$ as the first known example of a natural combinatorial principle to occupy the interval strictly between $\mathsf{ACA}_0$ and $\mathsf{RT}^2_2$ . The proof of this fact uses an extension of the bushy tree forcing method, and develops new techniques for dealing with combinatorial statements formulated on trees, rather than on $ω$ .

preprint2014arXiv

Notions of robust information coding

We introduce and study several notions of computability-theoretic reducibility between subsets of $ω$ that are "robust" in the sense that if only partial information is available about the oracle, then partial information can be recovered about the output. These are motivated by reductions between $Π^1_2$ principles in the context of reverse mathematics, and also encompasses generic and coarse reducibilities, previously studied by Jockusch and Schupp (2012).

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.