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
    Commented 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$ Commented 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
    Commented 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
    Commented 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$ Commented 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$ Commented Feb 18, 2022 at 20:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .