FOM: Questions on higher-order logic

[H. Enderton]

Joe Shipman raises several questions about second-order logic
(i.e., real second-order, with the standard semantics).

>1)  For which ordinals alpha is the the truth set for V(alpha) Turing 
>reducible to the set of second-order validities? 

The best reference for this is Richard Montague's paper from the
1963 Model Theory Symposium:
    Reductions of higher-order logic, in The Theory of Models,
    North-Holland, 1965, pp. 251-264. 
See especially Theorem 7 on page 263.  Vaught also contributed to
this work.

Montague was fond of saying that the set of second-order validities
did not belong to any Kleene hierarchy, "past, present, or future."
Vaught once commented that studying second-order logic was like
studying "the standard model of set theory."  

>3) Is the set of validities for 3rd-order-logic or for type theory
>stronger under Turing reducibility than the set of validities for SOL?

No, I don't think so.  The key fact is that in a second-order language
you can say "A is the power set of B."  This lets you get any order you
might want, within second order.

--Herb Enderton
  hbe at math.ucla.edu