FOM: first order and second order logic: once more

Till Mossakowski till at Informatik.Uni-Bremen.DE
Fri Sep 1 06:59:46 EDT 2000

Herb Enderton writes:

>Much worse than that.  The set of second-order validities is a *very*
>complex set.  Not Sigma^m_n for any m or n.  And that's just for
>starters.  It's way beyond true arithmetic.

In which sense is the "set of (standard) second-order validities"
a precisely defined set? After all, it "pre-supposes a *given* model (X,E) of
(first-order) set theory ", as Matt Insall writes on 29-Aug.

So consequently, one should talk about *a* standard semantics for
SOL, since there are many of them (one for each (X,E)). Of course,
this points out that the word "standard" is unfortunate in this
context here. Is there a better word?

Thus it seems that the question of the complexity of
"the set of (standard) second-order validities" really
is a question about the set of sets

{ {phi | phi is valid in SOL based on (X,E)} | (X,E) is a model of ZF}

Now the arithmetical hierarchy is a *lower bound*  for the complexities 
of these sets, while an exact complexity measure seems to be difficult here.

Till Mossakowski

Till Mossakowski                Phone +49-421-218-4683, monday: +49-4252-1859
Dept. of Computer Science       Fax +49-421-218-3054
University of Bremen            till at           
P.O.Box 330440, D-28334 Bremen

More information about the FOM mailing list