# A logic that can distinguish between two structures

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)?

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.

-
How do you propose to distinguish between two models of the empty theory over the trivial language? –  Zhen Lin Aug 6 '11 at 13:43
@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. –  Asaf Karagila Aug 6 '11 at 14:06
@Asaf: Ah. I didn't notice that the question specified complete theories. I really should read more carefully... –  Zhen Lin Aug 6 '11 at 14:20
@Charlie: In FOL finite structures can be identified up to isomorphism by a single sentence, see more in my answer here. Using infinitary logic you can only specify the cardinality of your structure up to some point, this is completely analogous to finitary logic. –  Asaf Karagila Aug 6 '11 at 22:17
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 shelah.logic.at/listb.html –  Andres Caicedo Mar 29 '14 at 17:48

EDIT: I think this answers your main question. (I've pushed my original answer to below the line.) In 1979, Miklos Ajtai published a paper "Isomorphism and Higher Order Equivalence" (Annals of Mathematical Logic, 16(3) 1979; sadly, I can't find an online copy) which proves that the statement $$(*)\quad\text{"Countable second-order-equivalent structures in a finite language are isomorphic"}$$ is independent of $ZFC$.
This to me means that the answer to your question is "no," since there can be no absolute example. Of course, this hinges on what "concrete" means to you. In the opposite direction, there are models of $ZFC$ with two distinct countable ordinals which are second-order equivalent, and maybe that counts as concrete? Note that the version of $(*)$ restricted to well-orderings - called "Fraisse's Hypothesis" by Wiktor Marke ("Sur la consistance d'une hypothese de Fraıssé sur la definiss- abilite dans un langage du second ordre," C. R. Acad. Sci. Paris Ser. A-B 276 (1973), which I also can't find online) - is also independent of $ZFC$.
In general, I think Lauri Keskinen's thesis (https://www.mittag-leffler.se/preprints/files/IML-0910f-34.pdf) - in which the statement $(*)$ above is called "Ajtai's Hypothesis" - is a good place to look for answers to questions like this. Also, you may be interested in a question I asked at the sister site MathOverflow: http://mathoverflow.net/questions/161676/the-non-absoluteness-of-second-order-elementary-equivalence.
By the counting argument you mention, there are two models of cardinality at most $2^{\aleph_0}$ which are non-isomorphic but have the same second-order theory. I don't know if an explicit (i.e., independent of ambient set theory) example of such "small" structures is known/can exist, however.
Towards a somewhat explicit example: I vaguely recall that Magidor showed that if $\kappa, \lambda$ are supercompact cardinals, then they (as pure sets) have the same second-order theory (I'm trying to track down a citation for this; I'll put it in once/if I find it). Of course, we know without any large cardinal assumption that a pair of pure sets of different cardinality but having the same second-order theory exists, but what that pair is may depend on the ambient set theory, since second-order notions are highly non-absolute. For example, the Lowenheim number of second-order logic is above the first of each kind of "small" large cardinal (e.g., inaccessible, measurable, etc.) which exists, even though it also exists just by a counting argument, so I'm not sure one can hope for a much better answer.