[FOM] reducing higher to second order?
H. Enderton
hbe at math.ucla.edu
Sat Dec 20 23:33:21 EST 2003
Todd Wilson wrote:
>I have seen passing references in the literature to a reduction of
>higher-order logic to second-order logic, but ...
I think of that as Montague's result, but Vaught and (independently)
Hintikka might be mentioned.
Lemma: In second-order logic, you can express "A is the power set
of B" (using a binary predicate symbol to simulate epsilon).
Consequence: The set of validities of k-order logic is recursively
isomorphic to the set of second-order validities.
Here k can have quite a variety of values. Need not be finite!
I'll send a reference later, when I'm in the office.
Vaught once commented that studying second-order logic was like
"studying the standard model of set theory." That is because
by iterating the above lemma (into the tranfinite), you can describe
a fair amount of the cumulative hierarchy.
--Herb Enderton
More information about the FOM
mailing list