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

Since it's not stable, $PA$ fails at being categorical in a power in the worst possible way, having $2^{\lambda}$ models in any uncountable $\lambda$. But $PA$ regains its categoricity in the move to second order logic, by which I mean, once we replace the induction schema with a single, second-order axiom. Are there natural examples of unstable first-order theories for which categoricity is not recoverable in this way?

If the restriction to unstable $T$ is too strong, are there natural examples of complete, non-categorical first-order $T$ which are also non-categorical as second-order theories?

I'm struggling to think of such examples because I don't know of any axiomatizable, semantically complete but non-categorical second-order theory. Also, of course, unlike $PA$, not every theory has a natural second-order extension.

Thanks.

share|improve this question
    
By categorical you mean $\omega$-categorical? Also, it is not clear what it means to extend a complete first order theory to second order. Perhaps you want to ask about complete second order theories and their restrictions to first order, but then the question has nothing to do with "recovering" categoricity, instead your are just looking for a complete non-categorical second order theory. –  Ramiro de la Vega May 2 '12 at 12:06
    
I interpret categoricity here for second-order theories as true categoricity, meaning that the theory has only one model up to isomorphism. After all, the notion of $\kappa$-categoricity in first-order logic is used only as an approximation to true categoricity, which is generally unattainable for first-order theories by the Lowenheim-Skolem theorem. –  Joel David Hamkins May 2 '12 at 12:35
    
Ramiro, thanks. Yes, I did worry that the second-order extension was perhaps unclear/confused. I didn't specify a power because of the possibility of having absolute categoricty for second-order theories. –  Kate Hodesdon May 3 '12 at 19:58
add comment

2 Answers

up vote 8 down vote accepted

You had asked for theories that do not have a categorical second-order completion, but here is an answer to the dual question:

Theorem. Every consistent first order theory $T$ with an infinite model has a second-order completion that is not categorical.

Proof. Consider all the models of $T$. By the Lowenheim-Skolem theorem, there are such models of every infinite cardinality above the size of the language. For any such model $M\models T$, consider the second order theory $\text{Th}_2(M)$ of this model. Since there are a proper class of models $M$, but only a set of possible second-order theories, it follows by the infinitary pigeon-hole principle that there must be two models $M$ and $N$ of $T$ with the same second-order theory $\bar T=\text{Th}_2(M)$. Indeed, there must be such a theory $\bar T$ with a proper class of distinct models. Thus, $\bar T$ is a second-order completion of $T$, but not categorical because it has non-isomorphic models. QED

The move from PA to the second-order Peano theory is not really one of deduction so much as family resemblence---we choose the second-order Peano theory, which is categorical, because it is true in the intended model we had in mind for the first theory. But my argument above shows that we might have chosen differently, and arrived at a non-categorical second-order completion of PA or even of TA = True Arithmetic (first-order).

Meanwhile, if you are willing to expand the language to include an order relation, then indeed one can always find a categorical second-order completion.

Theorem Every consistent theory $T$ with a countable model has a second-order completion $\bar T$, in an expansion of the language by an order relation, such that $\bar T$ is categorical.

Proof. Suppose $M$ is a countable model of $T$. Let $\lt$ be an order relation on $M$ with order type $\omega$, or finite if $M$ is finite, and let $\bar T$ be the second-order theory of $\langle M,\lt\rangle$. Note that every element of $M$ is definable in $\langle M,\lt\rangle$, and further by the categoricity of second-order Peano, all models of $\bar T$ come equipped with an order $\lt$ of order type $\omega$ (or finite if $M$ is finite), and this provides an isomorphism of that model to $\langle M,\lt\rangle$. So $\bar T$ is categorical as a second-order theory. QED


Update. Here is an example perhaps along the lines you want. The ZFC axioms of set theory are first order, but have a second-order analogue ZFC2 which is obtained in much the same way as your move from PA to second-order PA, namely, we replace the first-order schemes of ZFC, such as the replacement axiom scheme, with the natural second-order counterpart. Now, Zermelo famously proved that the models of ZFC2 are precisely the models of the form $\langle V_\kappa,{\in}\rangle$, where $\kappa$ is an inaccessible cardinal. If there are at least two inaccessible cardinals, then ZFC2 is not categorical, since these models disagree with each other on the number of inaccessible cardinals. But if there is only one inaccessible cardinal, then ZFC2 IS categorical. So in the case of ZFC, the answer to your question is that it depends on the large cardinal background.

share|improve this answer
    
I'm not actually sure if we need the order $\lt$ in the second theorem. Perhaps the second-order theory of a countable structure is always categorical? Hmmm... –  Joel David Hamkins May 2 '12 at 13:00
1  
Consider the second order language consisting of a binary relation $<$. There is a "concrete" biyection between sentences and natural numbers, so there is a "concrete" function from countable ordinals into the reals (to each ordinal, assign its second order theory) $Th : \omega_1 \to \mathbb{R}$. Being concrete, I would guess $Th$ cannot be injective, so there are two countable ordinals with the same theory. –  Ramiro de la Vega May 2 '12 at 14:23
    
Ramiro, that is a very interesting idea. But the second order theory of a countable structure is not very concrete, because one can have alternations of the second order quantifier, placing it beyond the projective hierarchy. So it isn't clear to me whether different countable ordinals can have the same second-order theory. –  Joel David Hamkins May 2 '12 at 15:05
2  
Yes, it is definable in ZF. It is not absolute to different models of set theory, however, since one can change the second-order theory of a countable structure by forcing. Thus, the second-order theory of a countable structure depends on the set-theoretic background in which it is computed. –  Joel David Hamkins May 2 '12 at 16:14
2  
The first thing that this question made me think of is the Hanf number $H$ of second order logic - the cardinality such that any second-order theory with a model larger than that cardinality has second-order models of arbitrarily large cardinalities. The proof that this number exists is analogous to the proof of the first theorem. The first theorem itself is an immediate consequence of the existence of the Hanf number, just take the second-order theory of any first-order model of cardinality larger than $H$, and that theory cannot be categorical in second-order logic. –  Carl Mummert May 3 '12 at 12:27
show 4 more comments

Another spin on this question, that gets around the fact that there are only countably many second order sentences, is to look at categoricity in $L^2_{\kappa,\omega}$ where we allow conjunctions of size less that $\kappa$ and second order quantifiers. Hyttinen, Kangas and Vaananen (see http://www.math.helsinki.fi/logic/people/jouko.vaananen/HytKanVaa.pdf) show that, for suitable cardinals $\kappa$, all models of a complete first order theory $T$ of size $\kappa$ are characterized by and $L^2_{\kappa,\omega}$-sentence if and only if $T$ is ``classifiable" in the sense of Shelah's Main-Gap i.e., $T$ is stable, NDOP, shallow, and NOTOP.

share|improve this answer
    
aha! thank you! –  Kate Hodesdon May 3 '12 at 20:03
add comment

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.