# Does "agreement on cardinalities" imply second-order elementary substructurehood?

Say that a logic $$\mathcal{L}$$ satisfies the weak test property iff for all $$\mathfrak{A}\subseteq\mathfrak{B}$$ we have $$(1)\implies(2)$$ below:

1. For each $$\mathcal{L}$$-formula $$\varphi$$ with parameters from $$\mathfrak{A}$$ we have $$\vert\varphi^\mathfrak{B}\cap\mathfrak{A}^{arity(\varphi)}\vert=\vert\varphi^\mathfrak{B}\vert.$$ (In this case write "$$\mathfrak{A}\trianglelefteq_{\mathcal{L}}^{\mathsf{Card}}\mathfrak{B}$$.")

2. $$\mathfrak{A}\preccurlyeq_\mathcal{L}\mathfrak{B}$$.

This is a massive weakening of the Tarski-Vaught test, which says that we get elementarity merely from $$\varphi^\mathfrak{B}\cap\mathfrak{A}^{arity(\varphi)}$$ being nonempty whenever $$\varphi^\mathfrak{B}$$ is nonempty. By contrast, $$\mathfrak{A}\trianglelefteq_\mathcal{L}^\mathsf{Card}\mathfrak{B}$$ is a highly restrictive hypothesis (and so the corresponding implication is weaker): as long as $$\mathcal{L}$$ is "reasonable" it immediately implies, for example, that $$\vert\mathfrak{A}\vert=\vert\mathfrak{B}\vert$$ via the formula $$x=x$$.

My question is:

Does second-order logic have the weak test property?

Producing interesting instances of $$\trianglelefteq_{\mathsf{SOL}}^\mathsf{Card}$$, even before trying to also prevent $$\preccurlyeq_{\mathsf{SOL}}$$, seems very difficult; on the other hand, I see absolutely no reason why $$\mathsf{SOL}$$ should have the weak test property.

In fact there is a whole spectrum of variants of the test property which seem interesting to me. For each class $$X$$ of cardinals and pair of structures $$\mathfrak{A}\subseteq\mathfrak{B}$$, say $$\mathfrak{A}\trianglelefteq_\mathcal{L}^X\mathfrak{B}$$ iff for each $$\mathcal{L}$$-formula $$\varphi$$ with parameters from $$\mathfrak{A}$$ and each $$\kappa\in X$$ we have $$\vert\varphi^\mathfrak{B}\cap\mathfrak{A}^{arity(\varphi)}\vert<\kappa\iff \vert\varphi^\mathfrak{B}\vert<\kappa$$; then the weak test property at $$X$$ is the implication $$\trianglelefteq_\mathcal{L}^X\implies \preccurlyeq_\mathcal{L}$$. The Tarski-Vaught test itself corresponds to $$X=\{1\}$$, while the weak test property corresponds to $$X=\mathsf{Card}$$. If the main question above happens to have a positive answer - which would surprise me quite a bit! - I would be further interested in which $$X$$s are "sufficient" to ensure $$\preccurlyeq_\mathcal{L}$$.

• Just to be clear, what is your notion of second-order substructure? Is it the one where you just look at formulas with element free-variables (and no set free-variables)? Nov 22, 2021 at 19:55
• @WillBoney Yes, $\preccurlyeq_{\mathsf{SOL}}$ only uses first-order variables/parameters. (This is what you get if you use the abstract Barwise/Ebbinghaus/etc. notion of $\preccurlyeq_\mathcal{L}$ for an arbitrary regular logic $\mathcal{L}$, in the special case $\mathcal{L}=\mathsf{SOL}$.) Nov 22, 2021 at 19:57
• It feels like the test property at $\kappa$ corresponds to the Tarski-Vaught Test for the cardinality quantifiers at $\kappa$ and below. So my guess is no, and that a counter-example can be cooked out of some logic outside of $\bL(Q_\kappa)$ and inside $\bL^2$ like cofinality quantifiers or $\bL(aa)$. But this elementarity for $\bL^2$ is hard for me to wrap my head around enough to cook up a proof... Nov 22, 2021 at 20:15
• Was the logic used for the formulas condition 1 really intended to be the same as that whose elementarity is in question in condition 2? If they are both SOL, don’t we easily get a c.e. to condition 1 if elementarity fails? (unless I’m missing something) i.e. just use the disagreement to get a formula in param’s in $A$ which is true for every element when interpreted in $A$, but false of every element when interpreted in $B$. Dec 14, 2021 at 0:51
• @FarmerS Looking back after the fact, I made a very silly typo - fixed now, and hopefully nontrivial! Feb 14, 2022 at 19:09

No, second order logic does not have the weak test property: let $$\mathfrak{B}=(\mathbb{R},{<})$$ (that is, the real numbers with the only predicate being the usual "less than" order) and let $$\mathfrak{A}=(\mathbb{R}\backslash\{0\},{<})$$. Then $$\mathfrak{B}\models$$"I am a complete linear order" (completeness as in "for every $$<$$-downward closed set $$X$$ such that $$X\neq\mathbb{R}$$, there is a least upper bound for $$X$$, and likewise symmetrically"), whereas $$\mathfrak{A}$$ does not satisfy this, so $$\mathfrak{A}\not\equiv_{\mathrm{SOL}}\mathfrak{B}$$, and hence $$\mathfrak{A}\not\preccurlyeq_{\mathrm{SOL}}\mathfrak{B}$$. But property 1 does hold for $$(\mathfrak{A},\mathfrak{B})$$. For for simplicity let's first consider the case that the arity of $$\varphi$$ is 1. Let $$x_1 be elements of $$\mathbb{R}\backslash\{0\}$$. Then the only subsets $$X\subseteq\mathbb{R}$$ which are second-order definable over $$(\mathbb{R},{<})$$ from $$(x_1,\ldots,x_n)$$ are finite unions of intervals with endpoints in $$\{-\infty,x_1,\ldots,x_n,\infty\}$$, and therefore, if $$0\in X$$, then there is an non-empty open interval $$(-\varepsilon,\varepsilon)\subseteq X$$, so $$\varphi^{\mathfrak{B}}$$ and $$\varphi^{\mathfrak{B}}\cap\mathfrak{A}$$ both have cardinality continuum. (E.g. if $$\varepsilon>0$$ is small enough then for each $$x\in(-\varepsilon,\varepsilon)$$ we can produce an automorphism $$\pi:\mathfrak{B}\to\mathfrak{B}$$ which fixes $$x_1,\ldots,x_n$$ but with $$\pi(0)=x$$.) For arity $$k>0$$ it is similar, with $$k$$-dimensional rectangles.
• Nice! And this isn't limited to $\mathsf{SOL}$, since we can reason about automorphically-fixed sets more generally: no "reasonable" logic $\mathcal{L}$ capable of defining Dedekind-completeness has the weak test property. Feb 18, 2022 at 20:33