4
$\begingroup$

(Previously asked and bountied at MSE:)


Let $\Sigma$ be the language consisting of a single binary relation symbol. Second-order logic can "detect" second-order-elementary-equivalence of $\Sigma$-structures in the following sense:

There is a finite language $\Sigma'\supseteq \Sigma\sqcup\{X,Y\}$, with $X,Y$ unary relation symbols and a $\Sigma'$-sentence $\eta$ such that for all $\Sigma$-structures $\mathfrak{A},\mathfrak{B}$ the following are equivalent:

  • $\mathfrak{A}\equiv_{\mathsf{SOL}}\mathfrak{B}$.

  • There is an $\mathfrak{M}\models\eta$ with $X^\mathfrak{M}\upharpoonright\Sigma\cong\mathfrak{A}$ and $Y^\mathfrak{M}\upharpoonright\Sigma\cong\mathfrak{B}$.

Roughly speaking, we just "piggyback" on the analogous result (via Fraisse's theorem) for first-order logic, using the facts that $(i)$ powersethood is second-order definable and $(ii)$ second-order-equivalence amounts to first-order-equivalence of "powerstructures." However, this approach via the obvious auxiliary constructions results in significant blow-up, since the witnessing $\mathfrak{M}$ for a pair of countable $\mathsf{SOL}$-equivalent structures will have size continuum.

I'm curious if we can do better. Let the scaffold number for second-order logic be the smallest cardinal $\xi$ with the following property:

There is a finite language $\Sigma'\supseteq \Sigma\sqcup\{X,Y\}$, with $X,Y$ unary relation symbols and a $\Sigma'$-sentence $\eta$ such that for all countable $\Sigma$-structures $\mathfrak{A},\mathfrak{B}$ the following are equivalent:

  • $\mathfrak{A}\equiv_{\mathsf{SOL}}\mathfrak{B}$.

  • There is an $\mathfrak{M}\models\eta$ with cardinality less than $\xi$ such that $X^\mathfrak{M}\upharpoonright\Sigma\cong\mathfrak{A}$ and $Y^\mathfrak{M}\upharpoonright\Sigma\cong\mathfrak{B}$.

Trivially we have $\omega_1\le\xi\le\mathfrak{c}^+$. Meanwhile, assuming $\mathsf{V=L}$ we have that $\equiv_\mathsf{SOL}$ and $\cong$ coincide for countable structures, so $\omega_1=\xi=\mathfrak{c}<\mathfrak{c}^+$ is also consistent.

Beyond this, however, not much is clear to me. In particular, I'm curious whether $\xi$ can be small even if the continuum is large and we have large cardinals:

Is it consistent with $\mathsf{ZFC}$ + a proper class of Woodins (although I'm not wedded to that specifically) that $\omega_1=\xi<\mathfrak{c}$?

$\endgroup$

0

You must log in to answer this question.