Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 6 down vote accepted

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

share|improve this answer
    
Great answer! Thanks –  Carlos Sáez Aug 11 '11 at 16:28

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 $ZFC$ that the second order theory of every countable structure (in a countable vocabulary) is categorical. See this FOM-post of mine for a reference.

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.