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



Categoricity in second order logic
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).


