6
$\begingroup$

This was previously asked at MSE without success.

Suppose $T$ is a complete first-order theory with continuum-many countable models up to isomorphism. We define two sets of Turing degrees associated to $T$ via second-order logic:

  • $SecTh(T)$ is the set of Turing degrees of second-order theories of models of $T$.

  • $SecTh_0(T)$ is the set of Turing degrees of second-order theories of countable models of $T$.

I'm interested in how simple these sets can be. Specifically:

Is there a $T$ such that $SecTh(T)$ is not cofinal in the Turing degrees? If not, what about $SecTh_0(T)$?

Recall that $X$ is cofinal in the Turing degrees if every Turing degree is below some element of $X$.

Here's what I've been able to figure out already:

  • Assuming $V=L$, the answer is negative for $SecTh_0$ (and hence $SecTh$ a fortiori). The key point is that under $V=L$ the set of pointwise-definable levels of $L$ is unbounded in $\omega_1$. Given a countable $\mathcal{A}\models T$, let $\alpha_\mathcal{A}$ be the least index of a pointwise-definable level of $L$ containing an isomorphic copy of $\mathcal{A}$. The second-order theory of $\mathcal{A}$ computes the first-order theory of $L_{\alpha_\mathcal{A}}$, which in turn computes every real in $L_{\alpha_\mathcal{A}}$ by pointwise definability. Now simply use the fact that $\{\alpha_\mathcal{A}:\mathcal{A}\models T\}$ is unbounded in $\omega_1$. (Note that this is a "naive" version of the idea behind mastercodes.)

  • I don't actually see an immediate argument that $SecTh(T)$ need be uncountable! A priori, $Th_2(\mathcal{A})$ may not be enough to build a concrete copy of $\mathcal{A}$ in any sense that I can see. It is consistent that $SecTh_0(T)$ (and hence $SecTh(T)$) is always uncountable, since it's consistent that no two countable structures are second-order elementarily equivalent (see Marek's theorem mentioned here), but that's the best I know.

  • Under sufficiently strong large cardinal hypotheses, $SecTh_0(T)$ is subject to Martin's Cone Theorem, and hence for an affirmative answer for the second question it would be enough to find a $T$ such that $SecTh_0(T)$ does not contain an upper cone. Under such hypotheses and replacing $\mathsf{ZFC}$ with $\mathsf{ZF}$ + Turing Determinacy the same would hold for $SecTh(T)$, but I don't immediately see how to get this stronger result without determinacy.

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm not practiced at working with 2nd order theories, but my first thought is the theory of a discrete linear order without endpoints, i.e. T = Th($\mathbb{Z}$). The models are linear orders of the form $\mathbb{Z}\cdot L$, but it's not clear to me the second order theory of a model will let you recover $L$, or have any particular computational power. $\endgroup$
    – Dan Turetsky
    Commented Aug 13, 2020 at 10:54
  • $\begingroup$ @DanTuretsky I don't think that will work. In a second-order way we can indeed recover $A$ from $\mathbb{Z}\cdot A$ (I want to reserve "$L$" for the constructible hierarchy): it's just $\mathbb{Z}\cdot A$ modulo the finite distance relation, and the latter is second-order definable. And this lets us get a lot of power out of the second-order theories of models of $Th(\mathbb{Z},<)$, since in particular whenever $\alpha$ is a countable ordinal we'll be able to compute $L_\alpha$ from $Th_2(\mathbb{Z}\cdot\alpha,<)$. $\endgroup$
    – Noah Schweber
    Commented Aug 13, 2020 at 14:09

0

Reset to default

You must log in to answer this question.