Do isomorphic structures always satisfy the same second-order sentences?

Solution 1:

The answer is yes, trivially. This follows immediately from the definition of an isomorphism and the satisfaction relation.

An isomorphism means that there is a bijection which preserves the interpretation of the constant, relation and function symbols. This bijection can be "pulled up" to be a bijection between power sets, power of power sets, and so on and so forth.

Recall that if $M$ is a structure and $\varphi$ is a sentence in second-order logic (without adding new extralogical symbols, of course!) then we define $M\models\varphi$ by recursion over the structure of $\varphi$. This definition begins with atomic formulas and continue by making the formulas more and more complex. If you follow the definition more closely you will see that this is all isomorphism invariant.

And this is not only true for first/second-order logic. It is true for higher order logics, infinitary logics, and even abstract quantifiers (at least those that I am familiar with).

On the other hand, I don't know if the converse is true. It seems unlikely, but possible.

Solution 2:

The first statement is true. That is

Theorem. If two mathematical structures are isomorphic, they satisfy the same second-order sentences.

Proof. Let $\mathscr{A}, \mathscr{B}$ be two isomorphic models, with $f$ being the isomorphism between them. By induction on second order formula $\phi$, we can show that for all $x_1, \ldots, x_m \in A$ and all $X_1, \ldots, X_n \subseteq A$, $$\mathscr{A} \models \phi(x_1, \ldots, x_m, X_1, \ldots, X_n) \Leftrightarrow \mathscr{B} \models \phi(f(x_1), \ldots, f(x_m), f``X_1, \ldots, f``X_n).$$ The proof is identical to the first order case.

First prove that for all terms $t(v_1, \ldots, v_m, V_1, \ldots, V_n)$, we have that for all $x_1, \ldots, x_m \in A$ and all $X_1, \ldots, X_n \subseteq A$, $$f(t^\mathscr{A}(x_1, \ldots, x_m, X_1, \ldots, X_n)) = t^\mathscr{B}(f(x_1), \ldots, f(x_m), f``X_1, \ldots, f``X_n),$$ when $t$ is a first order term, and $$f``t^\mathscr{A}(x_1, \ldots, x_m, X_1, \ldots, X_n) = t^\mathscr{B}(f(x_1), \ldots, f(x_m), f``X_1, \ldots, f``X_n),$$ when $t$ is a second order term. This is easy. For example for $t = V$, where $V$ is a second order variable, we have that for all $X \subseteq A$, $$f``t^\mathscr{A}(X) = f``X = t^\mathscr{B}(f``X_1).$$

Now the proof of the induction for the formulas. The only different step from the first order case in the induction proof is the quantifier one. We have that \begin{align*} \mathscr{A} &\models \exists X \phi(X, x_1, \ldots, x_m, X_1, \ldots, X_n) \\ &\Leftrightarrow \text{ there exists } X \subseteq A \text{ s.t. } \mathscr{A} \models \phi(X, x_1, \ldots, x_m, X_1, \ldots, X_n) \\ &\Leftrightarrow \text{ there exists } f``X \subseteq B \text{ s.t. } \mathscr{B} \models \phi(f``X, f(x_1), \ldots, f(x_m), X_1, \ldots, f``X_n) \\ &\Leftrightarrow \mathscr{B} \models \exists X \phi(X, f(x_1), \ldots, f(x_m), f``X_1, \ldots, f``X_n). \end{align*} $\dashv$

Your second question is very interesting. The converse is false in general. I didn't know the answer, but I found an answer by Joel David Hamkins here https://mathoverflow.net/a/95761/35760. So

Theorem. Every consistent first order theory T with an infinite model has a second-order completion that is not categorical.

Which means that there exist models that are equivalent for second order formulas, but are not isomorphic. I had no idea this could happen.