Zobrazeno 1 - 10
of 166
pro vyhledávání: '"Andrews, Uri"'
Autor:
Andrews, Uri, Mauro, Luca San
Coskey, Hamkins, and Miller [CHM12] proposed two possible analogues of the class of countable Borel equivalence relations in the setting of computable reducibility of equivalence relations on the computably enumerable (c.e.) sets. The first is based
Externí odkaz:
http://arxiv.org/abs/2409.17018
We answer two questions on the complexities of decision problems of groups, each related to a classical result. First, C. Miller characterized the complexity of the isomorphism problem for finitely presented groups in 1971. We do the same for the iso
Externí odkaz:
http://arxiv.org/abs/2403.02492
A partial order $(P,\le)$ admits a jump operator if there is a map $j\colon P \to P$ that is strictly increasing and weakly monotone. Despite its name, the jump in the Weihrauch lattice fails to satisfy both of these properties: it is not degree-theo
Externí odkaz:
http://arxiv.org/abs/2402.13163
We investigate the descriptive complexity of the set of models of first-order theories. Using classical results of Knight and Solovay, we give a sharp condition for complete theories to have a $\boldsymbol\Pi_\omega^0$-complete set of models. We also
Externí odkaz:
http://arxiv.org/abs/2402.10029
Autor:
Andrews, Uri, Ho, Meng-Che "Turbo"
The study of the word problems of groups dates back to Dehn in 1911, and has been a central topic of study in both group theory and computability theory. As most naturally occurring presentations of groups are recursive, their word problems can be th
Externí odkaz:
http://arxiv.org/abs/2402.01882
Autor:
Andrews, Uri, Mauro, Luca San
We answer several questions about the computable Friedman-Stanley jump on equivalence relations. This jump, introduced by Clemens, Coskey, and Krakoff, deepens the natural connection between the study of computable reduction and its Borel analog stud
Externí odkaz:
http://arxiv.org/abs/2206.11540
We examine the degree structure $\mathbf{ER}$ of equivalence relations on $\omega$ under computable reducibility. We examine when pairs of degrees have a join. In particular, we show that sufficiently incomparable pairs of degrees do not have a join
Externí odkaz:
http://arxiv.org/abs/2105.12534
Autor:
Andrews, Uri, Mermelstein, Omer
We show that for a model complete strongly minimal theory whose pregeometry is flat, the recursive spectrum (SRM($T$)) is either of the form $[0,\alpha)$ for $\alpha\in \omega+2$ or $[0,n]\cup\{\omega\}$ for $n\in \omega$, or $\{\omega\}$, or contain
Externí odkaz:
http://arxiv.org/abs/2104.14550
Publikováno v:
In Advances in Mathematics January 2024 436
We show that the theory of the partial order of computably enumerable equivalence relations (ceers) under computable reduction is 1-equivalent to true arithmetic. We show the same result for the structure comprised of the dark ceers and the structure
Externí odkaz:
http://arxiv.org/abs/1909.09401