Categoricity in second order logic

Question

Hi,

It's shown by an easy cardinality argument that there are complete second-order theories that are not categorical (have more than one model up to isomorphism). Anyone knows of a concrete example of such a theory?

Thanks in advance

Answer 1

I won't actually write down a concrete example (too much work), but here's how to get one. Work with the vocabulary (= language = signature) that has a constant symbol 0, a unary function symbol $S$, a binary predicate symbol $\in$, and two unary predicate symbols $N$ and $P$. The structures I want to consider look like this (up to isomorphism): The subset defined by $N$ is the set of natural numbers, with $0$ as zero and $S$ as successor function; the complement of $N$ is the collection $\mathcal P(N)$ of all subsets of the natural numbers (with $S$ defined in some trivial way there, say as the identity map); $\in$ is the membership relation between the natural numbers and the sets; and $P$ is an arbitrary subset of the complement of $N$. (All of this can be expressed in second order logic.) So there are $2^c$ (where $c$ is the cardinal of the continuum) non-isomorphic such structures, one for each choice of $P$. Let $F$ be the function assigning to each subset $P$ of $\mathcal P(N)$ the complete second-order theory of the corresponding structure, considered, via Gödel-numbering, as a set of natural numbers. So $F$ maps $\mathcal P(\mathcal P(N))$ into $\mathcal P(N)$. The cardinality argument mentioned in the question says that $F$ can't be one-to-one, but you want an explicit failure of one-to-one-ness. So the problem, in a somewhat more general formulation, is to go from an explicit function $F:\mathcal P(X)\to X$ (note that my $F$ is indeed explicit, once you fix a Gödel numbering) to an explicit pair of elements with the same image. Fortunately, that problem was solved by George Boolos, in the paper "Constructing Cantorian Counterexamples" (J. Philosophical Logic 26 (1997) 237-239).

Answer 2

A theory of the type you are asking cannot be that concrete, because:

1. By an old result of Victor Marek, it is consistent with the axioms of $\mathsf{ZFC}$ that the second order theory of every countable structure (in a finite vocabulary) is categorical. See this FOM-post of mine for a reference. It is well-known (and noted by Shelah) that this result outright fails in $\mathsf{ZFC}$ if the vocabulary is allowed to be infinite (see Lemma 1.2 of this paper by Lauri Keskinen).

2. In the above FOM-post, I conjectured that Marek's result can be extended to all Borel structures. This conjecture was verified by Harvey Friedman in this FOM-post.

3. In yet another FOM-post, Solovay showed that it is consistent with $\mathsf{ZFC}$ that as soon as a second order theory $T$ is both axiomatizable and complete, then $T$ is categorical. See also this other related FOM-post of Solovay.

For more on this topic, see this manuscript (Wayback Machine) by Lauri Keskinen, and this recent paper of Saarinen, Väänänen, and Woodin.

Answer 3

There must be two ordinals $\alpha$ and $\beta$ whose corresponding well-order structures $\langle\alpha,\lt\rangle$ and $\langle\beta,\lt\rangle$ have the same complete second-order theory, simply because there are only continuum many theories in a countable language, but more than this many ordinals.

But perhaps this is what you meant by the easy cardinality argument, and indeed, this easy argument doesn't seem to produce specific ordinals with the same second order theory.

So let me observe that a few large cardinal assumptions can make the situation somewhat more specific.

• If $0^\sharp$ exists, then every uncountable cardinal of $V$ is an order-indiscernible in $L$, and so inside $L$ the $V$-cardinals (as ordered structures) all have the same second order theory, but are not isomorphic. More generally, any structure $M$ in $L$ whose size is an order indiscernible there will have a non-categorical theory in $L$, since if $j:L\to L$ is an elementary embedding moving that indiscernible, then $j(M)$ will have the same theory.

• More generally, by increasing the large cardinal hypothesis, one can avoid the need to go to the inner model $L$. Specifically, if $\kappa$ is a $1$-extendible cardinal, then there is an elementary embedding $j:V_{\kappa+1}\to V_{\lambda+1}$ for some $\lambda=j(\kappa)\gt\kappa=\text{cp}(j)$. In this case, every structure $M$ on domain $\kappa$, in a language of size less than $\kappa$, has the same second order theory as $j(M)$, which has domain $\lambda$, which is strictly larger than $\kappa$ in cardinality. Thus, this is a cardinal $\kappa$ such that every second theory realized by a structure of size $\kappa$ is non-categorical, which seems like a remarkable property for the purposes of your question.

But I have a feeling, nevertheless, that you may want more specificity that these examples provide.