Skip to main content
3 of 3
edited tags
Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331

Number of models vs. complexity for SOL theories

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.

Noah Schweber
  • 21.1k
  • 10
  • 110
  • 331