# 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
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.