Source author record

Carl G. Jockusch, Jr.

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

2works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Effectiveness of Hindman's theorem for bounded sums

We consider the strength and effective content of restricted versions of Hindman's Theorem in which the number of colors is specified and the length of the sums has a specified finite bound. Let $\mathsf{HT}^{\leq n}_k$ denote the assertion that for each $k$ -coloring $c$ of $\mathbb{N}$ there is an infinite set $X \subseteq \mathbb{N}$ such that all sums $\sum_{x \in F} x$ for $F \subseteq X$ and $0 < |F| \leq n$ have the same color. We prove that there is a computable $2$ -coloring $c$ of $\mathbb{N}$ such that there is no infinite computable set $X$ such that all nonempty sums of at most $2$ elements of $X$ have the same color. It follows that $\mathsf{HT}^{\leq 2}_2$ is not provable in $\mathsf{RCA}_0$ and in fact we show that it implies $\mathsf{SRT}^2_2$ in $\mathsf{RCA}_0$ . We also show that there is a computable instance of $\mathsf{HT}^{\leq 3}_3$ with all solutions computing $0'$ . The proof of this result shows that $\mathsf{HT}^{\leq 3}_3$ implies $\mathsf{ACA}_0$ in $\mathsf{RCA}_0$ .

preprint2015arXiv

Asymptotic density and the coarse computability bound

For $r \in [0,1]$ we say that a set $A \subseteq ω$ is \emph{coarsely computable at density} $r$ if there is a computable set $C$ such that $\{n : C(n) = A(n)\}$ has lower density at least $r$ . Let $γ(A) = \sup \{r : A \hbox{ is coarsely computable at density } r\}$ . We study the interactions of these concepts with Turing reducibility. For example, we show that if $r \in (0,1]$ there are sets $A_0, A_1$ such that $γ(A_0) = γ(A_1) = r$ where $A_0$ is coarsely computable at density $r$ while $A_1$ is not coarsely computable at density $r$ . We show that a real $r \in [0,1]$ is equal to $γ(A)$ for some c.e.\ set $A$ if and only if $r$ is left- $Σ^0_3$ . A surprising result is that if $G$ is a $Δ^0_2$ $1$ -generic set, and $A \leq\sub{T} G$ with $γ(A) = 1$ , then $A$ is coarsely computable at density $1$ .

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.