# The (non-)absoluteness of second-order elementary equivalence

Elementary equivalence is set-theoretically absolute between any two transitive models of set theory; this is also true for the infinitary logics - e.g., $\mathcal{L}_{\omega_1\omega}$ - at least, assuming the models in question have all the relevant infinitary formulas. In both cases, the easiest way to prove this is to prove that the satisfaction of a given sentence in a given structure is absolute (note http://arxiv.org/abs/1312.0670 by Joel David Hamkins and Ruizhi Yang, which justifies my restriction to transitive models).

This latter statement is of course false for second-order logic: the statements "the Continuum Hypothesis holds" and "this model is countable" are both expressible by second-order sentences, and their truth values depend on the ambient universe, with the former being being a "switch" and the latter a "button" in the sense of the modal logic of forcing.

However, this alone does not show that second-order elementary equivalence, "$\equiv_{II}$", is not absolute. The simplest way I know to show that $\equiv_{II}$ is not absolute is to consider a pair of models $A, B$ whose cardinalities have different set-theoretic properties; for example, take $A$ and $B$ to be pure sets with cardinalities $\aleph_0$ and $\aleph_1$, respectively. Then the former satisfies "I am countable" while the latter does not, and this is expressible by a second-order sentence, so they are not second-order elementarily equivalent; however, by collapsing $\omega_1$ we make $A$ and $B$ isomorphic.

This leaves open, however, two classes questions about the non-absoluteness of second-order elementary equivalence. I'll mention a couple in each class.

First, how much of this depends on cardinality?

Are there equinumerous $A$, $B$ such that the second-order elementary equivalence of $A$ and $B$ is not absolute between transitive models of set theory containing $A$ and $B$?

And the stronger version:

Are there countable such $A$ and $B$?

Second, what kind of "switching behavior" is possible? The example given above shows that we can "turn $\equiv_{II}$ on," but in that example we cannot turn it off again. An example where we can "turn $\equiv_{II}$ off" is the following: take pure sets $A$ and $B$ of cardinalities $\vert A\vert<\vert B\vert$ which are second-order elementarily equivalent; by the pigeonhole principle, we can in fact find such $A$ and $B$ of cardinality $\le 2^{\aleph_0}{}^+.$ Now consider a forcing extension $V[G]$ in which $\vert A\vert$ is made countable but $\vert B\vert$ is not; in $V[G]$, $A\not\equiv_{II}B$. This raises a couple interesting questions.

First, note that in the above example, we can turn $\equiv_{II}$ back on again by collapsing $\vert B\vert$ to $\omega$. So it makes sense to ask:

Suppose $A\equiv_{II} B$ in $V$. Is it the case that for every generic extension $V[G]$, there is a further generic extension $V[G][H]$ in which $A\equiv_{II} B$?

Second, the only examples I've found so far involve collapsing cardinals. This, of course, runs out when everything reaches $\omega$. So we can ask:

Is there a pair of structures $A, B\in V$ and an $\omega$-sequence of models $V=V_0<V_1<V_2< . . .$ (where "$W<W'$" means "$W'$ is a generic extension of $W$") such that $V_i\models A\equiv_{II}B$ exactly when $i$ is even? In general, what sort of 'alternating behavior' is possible?

This is of course a long list of questions, and I don't expect them all to be answered here. Basically, I'm interested in everything around this issue, so I'll accept any answer which helps me understand the general picture of things.

-

In this edit I have modified my previous argument, and added the appropriate conditions to Harrington's theorem.

I will explain below why it is possible to arrange a model $M$ of $ZFC$ that:

(a) contains two nonisomorphic countable structures $\cal{A}$ and $\cal{B}$ (in a finite vocabulary) that share the same second order theory, and

(b) $M$ has a generic extension in which $\cal{A}$ and $\cal{B}$ differ in their seond order theory.

(1) By a theorem of Marek, if there is a second-order definable well-ordering of the continuum, then as soon as two countable structures are elementarily equivalent in second order logic, then they are isomorphic.

(2) On the other hand, by a result of Ajtai, if $G$ is Cohen generic over a model $M$ of $ZFC$, then in $M[G]$ there will be two countable models $\cal{A}$ and $\cal{B}$ in a finite vocabulary that share the same second order theory (indeed they form a pair of indiscernibles in $M$ and share the same theory in many other logics beyond second order logic).

$\cal{A}$ is the structure $(F^{G} \cup \omega, <_{\omega}, P_{G})$, where $F^{G}$ is the collection of all subsets of $\omega$ that differ in finitely many places with $G$, and $P_{G}$ is the relation that specifies which natural numbers belong to which subsets in $F^{G}$. $\cal{B}$ is defined similarly, with $\omega \setminus G$ swapped for $G$.

Since $\omega$ is rigid, $\cal{A}$ and $\cal{B}$ are nonisomorphic, and moreover, remain nonisomorphic in any generic extension.

(For proofs and references for (1) and (2) above, see Theorems 2.3 and 2.13 of this manuscript by Lauri Keskinen, which I believe is his Ph.D. dissertation at ILLC Amsterdam).

(3) By a theorem of Harrington, if $M$ is a countable model of $ZFC$ in which (a) $2^{\aleph_0}$ is a regular cardinal, (b) $2^{\aleph_0} > \aleph_1$, and (c) $\aleph_1 = \aleph_1^{\bf{L}}$, then $M$ has a generic extension $M[G]$ in which there is a second order definable well-ordering of the continuum ((more precisely, a $\Delta^1_3$ one).

(See Theorem 2.1 of Harrington's Long projective well-orderings, Annals of Math. Logic, 1977; the specific conditions on $M$ are stated on p.8, at the beginning of the proof of Theorem 2.1).

Based on (2), we can arrange a model $M$ of $ZFC$ in which there are two nonisomorphic countable structures $\cal{A}$ and $\cal{B}$ as described in (2) that share the same second order theory, such that $M$ satisfies conditions (a), (b), and (c) of Harrington's theorem (say by adding $\aleph_2$ cohen reals to a model of $ZF + V=L$). Then by using (3) and invoking (1) we obtain a model of $ZFC$ in which two nonisomorphic structures that used to have the same second order theory now have different second order theories, since they remain nonisomorphic, as explained at the end of (2).

In light of Joel Hamkins' answer I should point out that Section 4 of Keskinen's aforementioned manuscript also addresses the effect of large cardinals on the issues discussed here.

You may also find my answer to this question to be of interest.

-
This is really interesting - thank you very much! –  Noah S Mar 28 at 18:39
This is a really beautiful argument. One quick question: in the resulting $M[G]$, can the two now-non-equivalent ordinals be made second-order equivalent once again? (Really, that should be "for some $M$ . . .") –  Noah S Mar 29 at 8:37
Noah, I revamped my argument since contrary to my initial claim, Harrington's theorem has a limitation on $M$ (which makes perfect sense in light of the considerations of projective absoluteness discussed in Joel's answer). At the moment I do not know if the countable structures can be arranged to be ordinals. I also do not know the answer to your "quick question". –  Ali Enayat Mar 29 at 14:17
I'm still interested in the remaining questions, but this is certainly enough for now! –  Noah S Apr 16 at 5:45

Let me make some very general observations that address some of your questions, including the switching possibilities you mention at the end.

First, I claim that under the hypothesis of projective absoluteness, we have your desired absoluteness of second-order elementary equivalence for countable structures, to all forcing extensions. Projective absoluteness, a consequence of the existence of sufficient large cardinals, asserts that the truth value of projective statements (with real parameters) cannot change by forcing. But the point now is that for countable $A$ and $B$, the assertion $A\equiv_{II} B$ is determined by projective statements, since each second order assertion is essentially quantifying over the subsets of $A$ or $B$ and hence by countability equivalent to quantifying over the reals. So if we cannot change projective statements with parameters coding $A$ and $B$, then we cannot affect the truth of any second-order assertion in $A$ or $B$, and so $A\equiv_{II} B$ is absolute to forcing extensions.

Second, and a bit more generally, I claim that if the maximality principle $\text{MP}(\mathbb{R})$ holds and the truth value of $A\equiv_{II} B$ can change at all by forcing, where $A$ and $B$ are countable, then in fact we get the full switching behavior that you asked about; we can keep switching on and off as long as desired (an in particular, attain the even/odd pattern at the end). The maximality principle (see my paper A simple maximality principle, also independent work of Stavi and Väänänen) asserts that any forceably necessary statement (with real parameters) is already necessary, or in other words, if $\varphi(z)$ is a statement which can be forced in such a way that it remains true in all further forcing extensions, is already true in all forcing extensions. In this case, the point is that if $A$ and $B$ are countable, then we can use them as parameters, and if $A\equiv_{II} B$ cannot perpetually be changed by forcing, then either $A\equiv_{II} B$ or $A\not\equiv_{II} B$ is a forceably necessary statement, since we can make it stabilize, and so by $\text{MP}(\mathbb{R})$ the statement must therefore already be true and unchangeable by forcing.

-
Is it known if "$MP(\mathbb{R})+$there are such switching $A$ and $B$" is consistent with $ZFC$? –  Noah S Mar 29 at 2:09
I don't know, but I suspect yes. I do know that $\text{MP}(\mathbb{R})$ does not necessarily imply projective absoluteness, because there is a mis-match in the large cardinal strength. Thus, projective truth can be changeable by forcing, even when $\text{MP}(\mathbb{R})$ holds, and this seems close to what you want. –  Joel David Hamkins Mar 29 at 2:15