6
$\begingroup$

it's known that there are non-isomorphic structures that satisfy the same first-order sentences. Likewise it's known (by cardinality arguments) that there are non-isomorphic structures that satisfy the same second-order sentences, and more generally, that safisfy the same nth-order logic sentences, for all n.

TWo questions:

Is it known a concrete example of a complete but non-categorical second-order theory, or n-th order theory (i.e. two structures that satisfy the same second-order sentences, yet not isomorphic)?

Is there a logic that can distinguish between any two non-isomorphic structures (i.e. complete theories of this logic are always categorical)?

Thanks in advance

EDIT: I've found the answer to my second question. By the same cardinality arguments for the second-order case, the set of sentences of the logic must be a proper class. But if we use the "limit" logic of the infinitary logics $\mathcal{L}_{\kappa \kappa}$, we can distinguish between two non-isomorphic structures by using the same argument we use to show that in first-order logic, finite structures can be characterized up to isomorphism by a single first-order sentence (i.e. the sentence says what is the cardinality of the structure, and the behaviour of the non-logical symbols under the structure interpretation.

My first question still remains.

  • 0
    How do you propose to distinguish between two models of the empty theory over the trivial language?2011-08-06
  • 1
    @Zhen: The empty theory is not complete over $\{=\}$, since either $\exists a\exists b(\lnot(a=b))$ and $\exists a\forall b(a=b)$ are consistent.2011-08-06
  • 0
    @Asaf: Ah. I didn't notice that the question specified complete theories. I really should read more carefully...2011-08-06
  • 0
    @Charlie: In FOL finite structures can be identified up to isomorphism by a single sentence, see more [in my answer here](http://math.stackexchange.com/questions/53898). Using infinitary logic you can only specify the cardinality of your structure up to some point, this is completely analogous to finitary logic.2011-08-06
  • 1
    Shelah has put a significant amount of work in verifying that strong logics (or other equivalences) do not suffice to characterize structures up to isomorphism. See for instance "Theories with EF-Equivalent Non-Isomorphic Models" and "On the number of $L_{\infty,\omega_1}$-equivalent non-isomorphic models" at http://shelah.logic.at/listb.html2014-03-29

1 Answers 1