11
$\begingroup$

I know that if two mathematical structures are isomorphic, then they satisfy the same first-order sentences. The converse is false.

This is probably a completely obvious question, but is it true that whenever two mathematical structures are isomorphic, they satisfy the same second-order sentences? And if so, does the converse hold?

$\endgroup$
  • 1
    $\begingroup$ whar are first and second order sentences? $\endgroup$ – Jorge Fernández Hidalgo Jul 7 '13 at 6:56
  • $\begingroup$ @Omnitic, first note that there's a distinction between first-order logic and second-order logic. Consider an example from the theory of Abelian groups. The statement, 'for all $x$ we have $x+0=x$' is first-order, since we're not quantifying over sets. The statement 'for all non-empty subsets $A$, if $A$ is closed under addition and negation, then $0 \in A$' is second order, since we're quantifying over subsets. $\endgroup$ – goblin Jul 7 '13 at 7:04
  • $\begingroup$ Furthermore, both these statements are sentences, since there's no free variables. Contrast this with the statement '$x+0=0$' which has a free variable (namely $x$) and is therefore not a sentence. $\endgroup$ – goblin Jul 7 '13 at 7:05
  • $\begingroup$ hmm, I am not sure if this is true if the models are isomorphic, but it is definitely not true if the two models are just elementarily equivalent. For example, the standard natural numbers $\mathbb{N}$ are a well-order whereas, the non-standard naturals $\mathbb{N}^{*}$ (created by ultrapowers or compactness theorem) are not well-ordered. See en.wikipedia.org/wiki/Non-standard_model_of_arithmetic. Another example would be the reals and the hyperreals (the reals are archimedean whereas the hyperreals are not). These are both second-order properties. $\endgroup$ – Ryan Sullivant Jul 7 '13 at 7:21
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ My understanding is that $(\mathbb{Q},<)$ is not isomorphic to $(\mathbb{R},<)$, since they have different cardinalities. $\endgroup$ – goblin Jul 7 '13 at 6:59
  • $\begingroup$ I'm sorry you are right. $\endgroup$ – fnimic Jul 7 '13 at 7:01
  • $\begingroup$ I mistook isomorphism as an elementary equivalence. I have rewritten my answer. $\endgroup$ – fnimic Jul 7 '13 at 7:49
9
$\begingroup$

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.

$\endgroup$
  • 7
    $\begingroup$ The converse is false by a counting argument: in a given language (finite, for the sake of simplicity) there are countably many second-order sentences, so continuum-many sets of sentences. But there are proper-class-many isomorphism classes of structures. $\endgroup$ – Chris Eagle Jul 7 '13 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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