FOM: Questions on higher-order logic
Robert M. Solovay
solovay at math.berkeley.edu
Wed Sep 6 02:22:07 EDT 2000
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
More information about the FOM
mailing list