[FOM] An example of an axiomatizable second order theory that is complete but non-categorical?

[Marcin Mostowski]

As I understand the problem is the following: 

Give a second order theory T such that 

1.	T is axiomatizable (so recursively enumerable);
2.	T is complete;
3.	T is not categorical. 

The question should be made a little more precise. Firstly, in which 
language? If you take full second order language SO then this is impossible. 

T should describe an infinite model, otherwise if T is complete then T is 
categorical. In this case you can embed all arithmetical truths into T. Then 
T cannot be arithmetical. This is only because the set of all purely logical 
SO-sentences true in any infinite model is not arithmetical. For the 
argument see e.g. the paper by Konrad Zdanowski and me Archive for 
Mathematical Logic 2004. 

Then you can consider candidates between some logics weaker than SO, e.g. 
MSO (monadic second logic) or some logics with generalized quantifiers. 

Take any finite monadic vocabulary s (with only monadic predicates). Take 
any infinite model M for the vocabulary s. Let T be MSO theory of M. T is 
complete but not categorical . has a model of any infinite cardinality. 
However this is so for very simple reason: MSO in vocabulary s is equivalent 
to first order logic FO in vocabulary s. Nevertheless you can improve the 
example, take as underlying logic L(D) . the divisibility logic, FO enriched 
by all the divisibility quantifiers D_n, for n = 2,3,. .
D_n x F means that the set definable by F with respect to x can be split 
into n equicardinal parts.
L(D) in vocabulary s is not equivalent to FO. Now let T be the theory of the 
above M in the logic L(D). T is decidable because L(D) is decidable . I 
presented the proof at Logic Colloquium 1992 Vesprem . then T is recursively 
enumerable and axiomatizable. 

Of course you can consider essentially stronger sublogics of SO e.g. logics 
with Henkin quantifiers. In the above mentioned paper with Konrad Zdanowski 
you can find a few interesting examples. In quite recent paper by Amelie 
Gheerbrandt and me (MLQ 2006) it is observed that a few natural 
(syntactically defined) sublogics of SO, which are not decidable, have 
either the same degree of unsolvability as SO or just 0.. So a natural 
question is the following: 

ARE THERE ANY NONRECURSIVE AXIOMATIZABLE SUBLOGICS OF SO?
(formulated in the paper by Michal Krynicki and me, APAL 1992) 

And suggested by the last remarks: 

ARE ANY NATURAL (SYNTACTICALLY DEFINED) SUBLOGICS WITH DEGREES DIFFERENT 
THAN 0, 0., AND THAT OF SO? 


> 
> On Fri, 12 May 2006, Aatu Koskensilta wrote: 
> 
>> Call a second order theory T complete if for every A either T |= A or T
>> |= ~A. A simple cardinality argument shows that there are complete but
>> non-categorical second order theories, but is there any nice example of
>> an axiomatizable second order theory that is complete but
>> non-categorical? 
>>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
 


_____________________ 

Marcin Mostowski
Department of Logic
Institute of Philosophy
Warsaw University