Zobrazeno 1 - 10
of 187
pro vyhledávání: '"Hirschfeldt, Denis"'
In this paper we examine the reverse mathematical strength of a variation of Hindman's Theorem HT constructed by essentially combining HT with the Thin Set Theorem TS to obtain a principle which we call thin-HT. thin-HT says that every coloring $c: \
Externí odkaz:
http://arxiv.org/abs/2203.08658
We say that a set $S$ is $\Delta^0_{(n)}(X)$ if membership of $n$ in $S$ is a $\Delta^0_{n}(X)$ question, uniformly in $n$. A set $X$ is low for $\Delta$-Feiner if every set $S$ that is $\Delta^0_{(n)}(X)$ is also $\Delta^0_{(n)}(\emptyset)$. It is e
Externí odkaz:
http://arxiv.org/abs/2110.06402
The coarse similarity class $[A]$ of $A$ is the set of all $B$ whose symmetric difference with $A$ has asymptotic density 0. There is a natural metric $\delta$ on the space $\mathcal{S}$ of coarse similarity classes defined by letting $\delta([A],[B]
Externí odkaz:
http://arxiv.org/abs/2106.13118
Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between $\Pi^1_2$ principles over $\omega$-models of $\mathsf{RCA}_0$. They
Externí odkaz:
http://arxiv.org/abs/2008.00907
Autor:
Hirschfeldt, Denis R.
Publikováno v:
J. symb. log. 85 (2020) 531-537
We show that there is a minimal pair in the nonuniform generic degrees, and hence also in the uniform generic degrees. This fact contrasts with Igusa's result that there are no minimal pairs for relative generic computability, and answers a basic str
Externí odkaz:
http://arxiv.org/abs/1910.05825
The $\mathsf{SRT}^2_2$ vs.\ $\mathsf{COH}$ problem is a central problem in computable combinatorics and reverse mathematics, asking whether every Turing ideal that satisfies the principle $\mathsf{SRT}^2_2$ also satisfies the principle $\mathsf{COH}$
Externí odkaz:
http://arxiv.org/abs/1901.10326
Autor:
Davis, Caleb, Hirschfeldt, Denis R., Hirst, Jeffry L., Pardo, Jake, Pauly, Arno, Yokoyama, Keita
We consider two combinatorial principles, ${\sf{ERT}}$ and ${\sf{ECT}}$. Both are easily proved in ${\sf{RCA}}_0$ plus ${\Sigma^0_2}$ induction. We give two proofs of ${\sf{ERT}}$ in ${\sf{RCA}}_0$, using different methods to eliminate the use of ${\
Externí odkaz:
http://arxiv.org/abs/1812.09943
This paper concerns algorithms that give correct answers with (asymptotic) density $1$. A dense description of a function $g : \omega \to \omega$ is a partial function $f$ on $\omega$ such that $\left\{n : f(n) = g(n)\right\}$ has density $1$. We def
Externí odkaz:
http://arxiv.org/abs/1811.07172
We study the positions in the Weihrauch lattice of parallel products of various combinatorial principles related to Ramsey's theorem. Among other results, we obtain an answer to a question of Brattka, by showing that Ramsey's theorem for pairs ($\mat
Externí odkaz:
http://arxiv.org/abs/1804.10968