FOM: Questions on higher-order logic

[Allen Hazen]

On questions about second-order and higher-order logics.  References.
---(1) Stuart Shapiro's book "Foundations without Foundationalism: a case
for second-order logic" (Oxford: Clarendon Press, 1991.  Volume 17 in
"Oxford Logic Guides" series.  ISBN 0-19-853391-8.) is a good-- accessibly
written-- reference on many results about Second-Order logic, with useful
bibliography.  I have philosophical differences with Shapiro <grin>, but I
think this book is worth a look-- and maybe even a careful read-- for
anyone interested in Second-Order Logic.
---(2) On the particular question of whether validity for Third (or highe)
Order Logic is further away from constructivity (i.e. of a worse degree of
undecidability) than validity, Herbert Enderton's post gives what I think
is the right answer: NO.  Think of the higher-type objects in a (standard)
model of higher-order logic, over a given domain of individuals, as just
more individuals, so the whole model is a structure in the sense of
first-order model theory (with, say, membership as primitive relation).
Second-Order Logic can axiomatize the theory of such models, so every valid
sentence, S, of Umpteenth Order Logic is "represented" by a valid sentence
of Second-Order Logic that says, in effect, "S holds in any standard model
of Umpteenth Order Logic."  This result, I think, is due to Hintikka,
"Reductions in the Theory of Types," in "Acta Philosophica Fennica, vol. 8
(1955), pp. 57-115.  Hintikka's paper was reviewed in JSL v. 31 (1966), p.
660.
   (Sorry to be such a compulsive!  I learned about Hintikka's result when
I was a student, and for some reason I've always been fond of it.)
--
Allen Hazen
Philosophy Department
University of Melbourne