FOM: Questions on higher-order logic

[Robert M. Solovay]

Joe,

	There are a number of technical errors in your comment on my last
posting which I am going to point out. As per my usual custom, I shall
abstain from "discussing the philosophy".

On Tue, 5 Sep 2000 JoeShipman at aol.com wrote:

> 
> Comment:
> This shows that the set of second-order validities is a very informative set 
> indeed, and that practically all mathematical questions not involving higher 
> set theory are determined by (2nd-order) logic alone.  I am wondering if 
> Borel Determinacy, which requires UNcountable ranks, might be the lowest 
> reasonable exception (see further comments at question 5).
> 
	Any assertion about what happens in an V(alpha) for alpha weakly
characterizable can be phrased as saying that a closely related phi is
second-order valid. In particular, Borel determinacy can be expressed as
the fact that a certain sentence holds in V(omega+1).

> 
> Comment:
> This is so high up that it is not easy to make the case that SOL is 
> "reducible to set theory".  By the way, your last sentence implies that there 
> are at most kappa "elementary equivalence classes" for kappa the first strong 
> cardinal; how much can this be improved?  (Obviously there are at most 
> continuum-many possible truth sets for V(delta) as delta ranges over the 
> ordinals, but elementary equivalence is a stronger property than having the 
> same true sentences.)
> 

	1) It is completely trivial to "reduce SOL to set-theory". That
is, for each sentence phi of SOL, there is a closely related sentence phi'
such that phi is valid in SOL iff phi' holds in V.

	Of course, it is certainly *not* true that all second-order
validities are provable in ZFC. This is an immediate consequence of the 
unsolvability of the halting problem for TM's and Godel's work on the
expressibility of arithmetic. [Godel beta function, etc.]

	2) It is standard to say that two structures are elemntarily
equivalent iff they have the same sentences obtaining in them. Thus a
trivial upper bound on the elementary equivalence classes of V(alpha)'s is
c. In L, this bound is obtained. In the model where we start with L and
generically collapse aleph_1 to aleph_0, the cardinality of this set is
aleph_0. It is also trivial that there are always at least aleph_0 such
elementary equivalence classes.
> 
> This is the answer I expected but I am surprised that the theorem is so 
> elaborate and  artificial.  It would be nice to be able to point to such a 
> theorem that was of independent interest (such as Borel determinacy, which 
> requires uncountably many iterations of the powerset operation to prove and 
> so is not obviously equivalent to the validity of a sentence of SOL).

	You are confusing two things:
	1) To prove Borel determinacy [in first order logic] one needs to
assume the existence of aleph_1 ranks. In particular it can't be proved in
second-order number theory. 
	2) Borel determinacy is easily reformulated as saying that a
certain sentence of SOL is valid. Here is how this is done.

	(a) One can find a second-order sentence Phi_1[for structures with
a single binary predicate] whose only models are structures isomorphic to
a V(alpha) [for alpha a non-zero ordinal].
	(b) One can find a sentence Phi_2 such that models of Phi_1 and
Phi_2 are isomorhpic to the **real** V(omega+1).
	(c) Then BD is true iff it holds in every model of V(omega + 1).

	[Actually, a little massage of BD is needed to express it in
V(omega + 1). This sort of technical detail is well-known and I shall
ignore it.]

> Conclusion:
> 
> 
> 2) On the other hand, there ARE theorems of ZFC which could not be derived 
> even with an oracle for second-order validity, so the ZFC approach is 
> stronger in a sense (my 5th question was to clarify this, though I'd like to 
> see a simpler example).

	Let's put it this way. If I had an oracle for the truth of
second-order validities, all my practical curiosities about mathematical
questions would be settled. There is much more information contained in
the set of second order validiteies than in the theorems of ZFC. In
particular, any question about V(omega + omega) would be settled. All the
questions that concern Harvey's "ordinary mathematician" live there.

 > >-- Joe Shipman 

	--Bob Solovay