Thin set theorems and cone avoidance

DOI10.1090/TRAN/7987zbMATH Open1442.03007arXiv1812.00188OpenAlexW2978274064WikidataQ127231999 ScholiaQ127231999MaRDI QIDQ5218249FDOQ5218249

Authors: Peter A. Cholak, Ludovic Patey 

Publication date: 2 March 2020

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

Abstract: The thin set theorem $mathsf{RT}_{<infty,ell}^n$ asserts the existence, for every $k$-coloring of the subsets of natural numbers of size $n$, of an infinite set of natural numbers, all of whose subsets of size $n$ use at most $ell$ colors. Whenever $ell=1$, the statement corresponds to Ramsey's theorem. From a computational viewpoint, the thin set theorem admits a threshold phenomenon, in that whenever the number of colors $ell$ is sufficiently large with respect to the size $n$ of the tuples, then the thin set theorem admits strong cone avoidance. Let $d_0,d_1,dots$ be the sequence of Catalan numbers. For $ngeq1$, $mathsf{RT}_{<infty,ell}^n$ admits strong cone avoidance if and only if $ellgeq{d}_n$ and cone avoidance if and only if $ellgeq{d}_{n-1}$. We say that a set $A$ is $mathsf{RT}_{<infty,ell}^n$-encodable if there is an instance of $mathsf{RT}_{<infty,ell}^n$ such that every solution computes $A$. The $mathsf{RT}_{<infty,ell}^n$-encodable sets are precisely the hyperarithmetic sets if and only if $ell<2^{n-1}$, the arithmetic sets if and only if $2^{n-1}leqell<d_n$, and the computable sets if and only if $d_{n}leqell$.

Full work available at URL: https://arxiv.org/abs/1812.00188

Recommendations

• Some logically weak Ramseyan theorems
• Ramsey's theorem and cone avoidance
• Ramsey-like theorems and moduli of computation
• Ramsey's theorem for computably enumerable colorings
• The weakness of being cohesive, thin or free in reverse mathematics

zbMATH Keywords

Catalan numberreverse mathematicsRamseythin setDNChyperarithmetic setarithmetic setcone avoidanceDGAPdiagonal noncomputability

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Applications of computability and recursion theory (03D80) Second- and higher-order arithmetic and fragments (03F35)

Cites Work

• Subsystems of second order arithmetic
• Title not available (Why is that?)
• ∏ 0 1 Classes and Degrees of Theories
• On degrees of unsolvability
• Catalan Numbers
• Title not available (Why is that?)
• Ramsey's theorem and recursion theory
• Primitive recursion and the chain antichain principle
• Open questions in reverse mathematics
• Bounding prime models
• On the strength of Ramsey's theorem
• Title not available (Why is that?)
• Generics for computable Mathias forcing
• Some logically weak Ramseyan theorems
• Classifying model-theoretic properties
• On uniform relationships between combinatorial problems
• Iterative forcing and hyperimmunity in reverse mathematics
• Hyperarithmetically Encodable Sets
• The weakness of being cohesive, thin or free in reverse mathematics
• Partial orders and immunity in reverse mathematics
• Relationships between computability-theoretic properties of problems

Cited In (8)

• Title not available (Why is that?)
• On the thinness of non-tangential sets
• Relationships between computability-theoretic properties of problems
• Lawvere-Tierney topologies for computability theorists
• The weakness of the pigeonhole principle under hyperarithmetical reductions
• Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective
• Ramsey-like theorems and moduli of computation
• Two counterexamples to Cornea's conjecture on thin sets

This page was built for publication: Thin set theorems and cone avoidance

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5218249)