FOM: Questions on higher-order logic
H. Enderton
hbe at math.ucla.edu
Fri Sep 1 12:56:34 EDT 2000
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
More information about the FOM
mailing list