FOM: first order and second order logic: once more

[Till Mossakowski]

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 informatik.uni-bremen.de           
P.O.Box 330440, D-28334 Bremen  http://www.informatik.uni-bremen.de/~till
-----------------------------------------------------------------------------