FOM: Questions on higher-order logic

[Robert M. Solovay]

Joe,

	I've thought some more about your question 5). I can now give a
much more informative answer.

	Let me begin by quoting your question:

5) Let X be the set of second-order validities.  Let Y be the set of
statements "phi is a second-order validity" for phi in X.  Let Z be the
closure of Y under logical implication.  Are any theorems of ZFC outside
of Z?  (Such a theorem would refute a form of logicism.)

	Observation 1: Each sentence in Y is Pi_2 in the Levy Hierarchy.

	[For example, we can express a sentence in Y by saying that a
certain sentence holds in every V(alpha) for alpha a limit ordinal greater
than omega. But this is clearly Pi_2.]

	Let kappa be an infinite cardinal. By H(kappa) I mean the set of
all x such that the transitive closure of x has cardinality less than
kappa. [This is standard notation.]

	Basic fact (due to Levy). Let kappa be an uncountable
cardinal. Let S be a Sigma_1 assertion [possibly involving parameters from
H(kappa). Then S is true in V iff S holds in H(kappa).

	Corollary: Any Pi_2 sentence true in V holds in H(kappa) for any
uncountable cardinal kappa.. Hence any such H(kappa) is a model of Z.

	So an example of a sentence provable from ZFC but not in Z is
"There is an uncountable cardinal". [Take kappa = aleph_1.]

	One can ask an analogous question about the following class of
sentences:

	X' is the set of satisfiable sentences of SOL [say in a single
binary predicate plus =].

	Y' consists of all formalizations of "phi is satisfiable in
SOL" for phi in X'.

	Z' is the set of logical consequences [with respect to
first-order-logic] of the sentences of Y'.


	Recall from my previous letter the ordinal gamma. This is the sup
of the characterizable ordinals. It is easily seen that gamma is a
cardinal and in fact a Beth fixed point. Moreover, it is easy to see that
if kappa is a cardinal >= gamma, then H(kappa) is a model for Z'. Hence it
is easy to see that the following sentences  are theorems of ZFC which are
not in Z':

	For every cardinal, there is a strictly larger cardinal.

	Every set has a power set.

	--Bob Solovay