Hi,
It's shown by an easy cardinality argument that there are complete secondorder 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
Hi, It's shown by an easy cardinality argument that there are complete secondorder 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 


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) nonisomorphic such structures, one for each choice of $P$. Let $F$ be the function assigning to each subset $P$ of $\mathcal P(N)$ the complete secondorder theory of the corresponding structure, considered, via Gödelnumbering, 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 onetoone, but you want an explicit failure of onetooneness. 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) 237239). 





There must be two ordinals $\alpha$ and $\beta$ whose corresponding wellorder structures $\langle\alpha,\lt\rangle$ and $\langle\beta,\lt\rangle$ have the same complete secondorder 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.
But I have a feeling, nevertheless, that you may want more specificity that these examples provide. 

