[FOM] An example of an axiomatizable second order theory that is complete but non-categorical?
Marcin Mostowski
m.mostowski at uw.edu.pl
Mon May 15 20:19:55 EDT 2006
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
More information about the FOM
mailing list