Thin set theorems and cone avoidance
Cholak, Peter ; Patey, Ludovic
HAL, hal-02118615 / Harvested from HAL
The thin set theorem $\mathsf{RT}^n_{<\infty,\ell}$ 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 $n \geq 1$, $\mathsf{RT}^n_{<\infty, \ell}$ admits strong cone avoidance if and only if $\ell \geq d_n$ and cone avoidance if and only if $\ell \geq d_{n-1}$. We say that a set $A$ is $\mathsf{RT}^n_{<\infty, \ell}$-encodable if there is an instance of $\mathsf{RT}^n_{<\infty, \ell}$ such that every solution computes $A$. The $\mathsf{RT}^n_{<\infty, \ell}$-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} \leq \ell < d_n$, and the computable sets if and only if $d_n \leq \ell$.
Publié le : 2019-05-03
Classification:  [MATH.MATH-LO]Mathematics [math]/Logic [math.LO]
@article{hal-02118615,
     author = {Cholak, Peter and Patey, Ludovic},
     title = {Thin set theorems and cone avoidance},
     journal = {HAL},
     volume = {2019},
     number = {0},
     year = {2019},
     language = {en},
     url = {http://dml.mathdoc.fr/item/hal-02118615}
}
Cholak, Peter; Patey, Ludovic. Thin set theorems and cone avoidance. HAL, Tome 2019 (2019) no. 0, . http://gdmltest.u-ga.fr/item/hal-02118615/