8
$\begingroup$

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}$.

$\endgroup$
7
  • $\begingroup$ 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)? $\endgroup$
    – Will Boney
    Nov 22, 2021 at 19:55
  • $\begingroup$ @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}$.) $\endgroup$ Nov 22, 2021 at 19:57
  • $\begingroup$ 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... $\endgroup$
    – Will Boney
    Nov 22, 2021 at 20:15
  • $\begingroup$ 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$. $\endgroup$
    – Farmer S
    Dec 14, 2021 at 0:51
  • $\begingroup$ @FarmerS Looking back after the fact, I made a very silly typo - fixed now, and hopefully nontrivial! $\endgroup$ Feb 14, 2022 at 19:09

1 Answer 1

5
+200
$\begingroup$

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<x_2<\ldots<x_n$ 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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Feb 18, 2022 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.