Does having many models yield complex second-order theories?

146 Views Asked by At

Below, $T$ is a complete first-order theory in a finite language with no finite models.

Also asked at MO.


Question

Suppose $T$ has continuum-many countable models. 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$.


Some comments

  • 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 $Th(L_\alpha)$, which in turn computes every real in $L_\alpha$ 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.