Skip to Main Content

Proceedings of the American Mathematical Society

Published by the American Mathematical Society, the Proceedings of the American Mathematical Society (PROC) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6826 (online) ISSN 0002-9939 (print)

The 2020 MCQ for Proceedings of the American Mathematical Society is 0.85.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

Cohesive avoidance and strong reductions
HTML articles powered by AMS MathViewer

by Damir D. Dzhafarov PDF
Proc. Amer. Math. Soc. 143 (2015), 869-876 Request permission

Abstract:

An open question in reverse mathematics is whether the cohesive principle, $\mathsf {COH}$, is implied by the stable form of Ramsey’s theorem for pairs, $\mathsf {SRT}^2_2$, in $\omega$-models of $\mathsf {RCA}_0$. One typical way of establishing this implication would be to show that for every sequence $\vec {R}$ of subsets of $\omega$, there is a set $A$ that is $\Delta ^0_2$ in $\vec {R}$ such that every infinite subset of $A$ or $\overline {A}$ computes an $\vec {R}$-cohesive set. In this article, this is shown to be false, even under far less stringent assumptions: for all natural numbers $n \geq 2$ and $m < 2^n$, there is a sequence $\vec {R} = \langle {R_0,\ldots ,R_{n-1}}\rangle$ of subsets of $\omega$ such that for any partition $A_0,\ldots ,A_{m-1}$ of $\omega$ hyperarithmetical in $\vec {R}$, there is an infinite subset of some $A_j$ that computes no set cohesive for $\vec {R}$. This complements a number of previous results in computability theory on the computational feebleness of infinite sets of numbers with prescribed combinatorial properties. The proof is a forcing argument using an adaptation of the method of Seetapun showing that every finite coloring of pairs of integers has an infinite homogeneous set not computing a given non-computable set.
References
Similar Articles
Additional Information
  • Damir D. Dzhafarov
  • Affiliation: Department of Mathematics, University of California, Berkeley, Berkeley, California 94720
  • MR Author ID: 781680
  • ORCID: 0000-0003-4921-7561
  • Email: damir@math.berkeley.edu
  • Received by editor(s): March 18, 2013
  • Received by editor(s) in revised form: May 15, 2013
  • Published electronically: October 23, 2014
  • Additional Notes: The author was partially supported by an NSF Postdoctoral Fellowship and by the John Templeton Foundation
  • Communicated by: Mirna Dz̆amonja
  • © Copyright 2014 American Mathematical Society
    The copyright for this article reverts to public domain 28 years after publication.
  • Journal: Proc. Amer. Math. Soc. 143 (2015), 869-876
  • MSC (2010): Primary 03D80, 03F35, 05D05, 05D10
  • DOI: https://doi.org/10.1090/S0002-9939-2014-12261-1
  • MathSciNet review: 3283673