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 informatik.uni-bremen.de
P.O.Box 330440, D-28334 Bremen http://www.informatik.uni-bremen.de/~till
-----------------------------------------------------------------------------
More information about the FOM
mailing list