FOM: first order and second order logic: once more

[H. Enderton]

Martin Davis writes:
>3. In this last connection, it may be worth observing that the set of 
>second-order valid sentences does not merely fail to be r.e.: it has a very 
>high degree of unsolvability, that of true arithmetic. Or stated in terms 
>of the halting problem, to get its degree you must iterate omega times the 
>operation ("jump") of forming the halting set for a Turing machine 
>provided  with a given set as "oracle".

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.

--Herb Enderton
hbe at math.ucla.edu