New examples of degrees of categoricity

Abstract: We confirm a conjecture by Csima and Ng that if $\mathbf d$ is a Turing degree with $\mathbf 0^{(\alpha)}\leq \mathbf d\leq \mathbf 0^{(\alpha+1)}$ for some computable $\alpha$, then $\mathbf d$ is a degree of categoricity. For $\alpha\geq 2$ we modify a technique developed by Dan Turetsky to code paths through trees into the automorphisms of structures. This allows us to obtain structures with these degrees of categoricity that are rigid and have computable dimension $2$. For both properties, this is the least $\alpha$ where we can obtain this result. Goncharov showed that if a structure is $\mathbf 0'$-computably categorical, then it can not have finite computable dimension other than $1$. Bazhenov and Yamaleev constructed a properly d-c.e.\ degree $\mathbf d$, that is not the degree of categoricity of a rigid structure. We combine their construction with true stages to obtain a degree $\mathbf d$, $\mathbf 0'<\mathbf d< \mathbf 0''$ that is not the degree of categoricity of a rigid structure. This is joint work with Barbara Csima.

logic

Audience: researchers in the topic

Computability theory and applications

Series comments: Description: Computability theory, logic

The goal of this endeavor is to run a seminar on the platform Zoom on a weekly basis, perhaps with alternating time slots each of which covers at least three out of four of Europe, North America, Asia, and New Zealand/Australia. While the meetings are always scheduled for Tuesdays, the timezone varies, so please refer to the calendar on the website for details about individual seminars.