FOM: second-order logic lives...

[Randall Holmes]

(editorial comment: some comments by Harvey Friedman were misattributed
to Steve Simpson in an earlier version of this posting; there may be
remaining problems related to this, though I think I tracked them all down!)

I apologize for getting so annoyed at Simpson in my previous post.
I think I am beginning to see what the substantive points of disagreement
are between us, and on this basis I no longer think that Simpson is
deliberately misunderstanding me.

Point 1:  Does second-order logic have rules of inference?

Second order logic is not defined by any complete set of rules of
inference.  It is defined semantically.  But there are rules of
inference which are sound for it.  These include the usual first-order
rules, the analogues for second-order quantifiers of the first-order
rules for quantifiers and comprehension axioms.  These rules do not
constitute second order logic but they are valid from a second-order
standpoint.  Simpson appears to object to this because of his
definition of the word "logic" as "the science of valid inference".  I
have noted that there are more general definitions of what "logic" is
that do support the idea that second-order logic is a logic.  I won't
reiterate arguments about this point here.

Clarification re point 1: My "second-order standpoint" properly
extends a first-order standpoint; I assume availability of a partial
formalization of rules of inference, including but not necessarily
restricted to the axioms and rules of inference of the two-sorted
first-order system commonly referred to as "second-order logic".

Also, in response to a point raised by Simpson in a recent post which
I do not quote, I may be regarded as assuming that there are
infinitely many objects (so that the definition of the natural
numbers, for example, succeeds); I tend not to regard this as a
genuinely "logical" assumption, but it is convenient to make it.

Point 2: Does first-order ZFC support definitions of familiar
mathematical structures?

I claim that it does not, and if Simpson understands what I mean by
this, he cannot disagree with me (the question is whether it is clear
to him what I mean).

I take the natural numbers as an example.

We certainly can define in ZFC a structure commonly called "the
natural numbers".  It is the intersection of all sets containing the
von Neumann ordinal 0 (the empty set) and closed under the ordinal
successor operation (x -> x u {x}).

I agree heartily with Simpson that first-order ZFC is a beautiful
system for proving theorems about the (true!) natural numbers.  If we
interpret the true natural numbers as the elements of the set defined
above in ZFC and the properties of natural numbers as being suitably
correlated with the elements of the power set of the "natural numbers"
of ZFC then every theorem of second order arithmetic whose
interpretation in ZFC can be proved in ZFC is true.  Moreover, the set
of theorems of second order arithmetic whose interpretations are
provable in ZFC is quite large; it is, for example, larger than the
set of theorems provable in the first order two-sorted theory usually
called "second-order arithmetic".

However, I claim that we cannot justify the assertion that the true
natural numbers are implemented by the set of ZFC whose definition is
outlined above in terms of first-order ZFC alone.  First-order ZFC, if
it is consistent, has models in which the set defined above does not
have the order type of the true natural numbers.  This is a familiar
mathematical fact.

The reason that these models of ZFC have nonstandard natural numbers
is that there are inductive subsets of the "set of naturals" in the
model which do not correspond to any set of the model.  In other
words, the reason that a model of first-order ZFC may have nonstandard
natural numbers is that it fails to be a model of second-order ZFC --
its "sets of natural numbers" are not all the sets of its "natural
numbers".  Again, there is nothing here which Simpson and I should
disagree about.

The conclusion which I draw from all this which Simpson evidently does
not draw or simply does not understand is that the reason that we
regard ZFC as providing us with a definition of the natural numbers is
that we are implicitly appealing to an intended interpretation of the
language of ZFC as referring to _second-order ZFC_.  In second-order
ZFC, all the axioms and rules of inference of first-order ZFC are
valid (in fact, one obtains the axioms of Kelley-Morse set theory as
well), so everything we can do formally in first-order ZFC is still
available in second-order ZFC.

A recent posting of Friedman (received while I was writing this
posting) is making it quite clear to me what is going on (if Simpson's
opinions are similar, which they might not be, of course).  Friedman
thinks that "to express something in first-order ZFC" means exactly
what I think is meant by "to express something in second-order ZFC".
I think that this is wrong-headed, and I will try to explain why
below.

Thus Harvey Friedman:

Holmes uses an inappropriate notion of "expressed" here and throughout his
postings. The appropriate way to look at this is as follows. There is the
first order language of set theory. It is then trivial to express such
concepts as "inductive number system" in this first order language of set
theory. Since there are no axioms and rules of inference involved here,
there is no issue as to "nonstandard models" and the like. And this is the
normal concept of "express" that mathematicians use.

Holmes replies:

I think this is _really_ the crux of the matter.  Friedman appears to
think that the language of first-order set theory has an "intended
interpretation" which requires no formal justification.  I think that
the meaning of the terms in any formal system is implicitly defined
(as far as it can be defined) by the axioms and rules of inference of
the formal system.  The symbols of a formal language considered in
isolation from the axioms, rules of inference, etc. have no built-in
meaning.  This is a standard viewpoint (though certainly not
the only one) in philosophy of mathematics, ably expounded by
Mayberry, for example.

It is of course easy to express the notion of "the set of natural
numbers" (the intersection of all inductive sets) in the first-order
language of set theory, if we understand the symbols of the language
"naively" (is this what Friedman (and/or Simpson?) is saying we should
do?).  If this language is understood to refer to models of
second-order ZFC, the definition succeeds: the referent of our "set of
natural numbers" in any such model will be an implementation of the
set of natural numbers.  In some models of first-order ZFC, the
referent of the "set of natural numbers" thus defined will not be an
implementation of the set of natural numbers.  This is the precise
sense in which I say that second-order ZFC allows us to express the
notion "the set of natural numbers" and first-order ZFC does not.  In
fact, I would say that the "naive" understanding of the symbols to
which I think Friedman appeals is essentially the same as what I'm
calling the interpretation in second-order ZFC; this is the content of
my conjecture that Friedman's view (or Simpson's) is founded on an
equivocation between first-order and second-order ZFC.

In any case, no language has semantics in the absence of a given
interpretation or interpretations.  If I can define "the set of
natural numbers" in a language, the only way this definition can be
correct or incorrect is insofar as it refers or fails to refer to the
object(s) to which it is intended to refer in the interpretation(s) of
the language I consider.  The intended class of models is _always_
relevant (and the axioms and rules of inference (and other semantic
constraInts in the case of second-order logic) implicitly determine
the intended class of models).  (This entire paragraph is of course a
statement from a particular philosophical point of view, which can be
disputed!)

I would like to ask Friedman how he thinks the symbols of a formal
system acquire meaning?  In particular, where do the meanings of the
symbols of first-order ZFC, considered as a foundation for
mathematics, come from?

Friedman comments on a Holmes remark:

>(in
>this thread; I am fond of (first-order!) extensions of NFU as working
>foundations).

This is very bad.

Holmes replies (aside -- not really relevant to this thread):

It is demonstrably a matter of taste.  I actually agree that ZFC
foundations are better overall.  Part of the reason that I think this
has to do with the much better interface between ZFC and second order
logic :-) (speaking loosely; I would be happy to make this more
precise, but this is not relevant to the current thread).  But I think
that it is useful to develop foundations, however peculiar, that
differ from the standard ones; comparison of foundational approaches
helps us to see what foundations do for us.  I do _not_ agree that NFU
foundations are "very bad"; I think they do have some merit, but they
also have disadvantages.

Friedman responds to Holmes earlier:

>One possible position (I think that this is John
>Mayberry's position (?))  which would have very little effect on the
>way mathematics looks in practice is to adopt second-order ZFC (and
>extensions as desired) as one's working foundation,
>using the proof
>machinery of the first-order theory (which is of course sound for the
>second-order theory).  I'm not entirely comfortable with this because
>the ontological commitments of second-order ZF are very strong.

If I understand this correctly, it would be trivially equivalent to
adopting first-order ZFC (and extensions as desired) as one's working
foundation. I don't see the difference. If you do, spell out the
difference.

Holmes replies:

I have done so above.  This statement of yours confirms my impression
that the differences between our positions (and perhaps between mine
and Simpson's) are largely ones of terminology.  I think that some of
these differences are nonetheless important.

Friedman replies to Holmes:

>It is
>also fascinating to study the model theory of ZFC.  But it doesn't do
>everything that we need for a foundation of mathematics.

What is missing? Of course, large cardinals and other related issues are
missing. But what are you referring to?

Holmes replies:

I am referring to the inability to define familiar mathematical
structures such as the natural numbers.  This has to do with my
peculiar usage of the words "express" and "define".

Friedman replies to Holmes:

>The point which is
>being belabored is that the reference of mathematical language is
>an important foundational issue.

OK, let's talk about it more sensibly.

Holmes replies:

I would be delighted to have a sensible discussion about the reference
of mathematical language (this is one of my favorite topics); as long
as everyone understands what everyone else is saying!  Since you do
seem to understand me, it should be possible to communicate (as long
as each of us makes it clear what we mean).

I now switch to analysis of a reply by Simpson to Mayberry:

Simpson responds to Mayberry:

 > ZFC does not provide the foundation for mathematics. *Set theory*
 > provides the foundation for mathematics, and ZFC is a first order
 > formalisation of set theory.

Yes, your distinction between set theory and its first-order
formalizations may be valid at some level, at least for realists or
Platonists.  However, the fruitful approach that has yielded a lot of
serious insight (G"odel, Cohen, ...) is to study the first-order
formalizations.  Experience has shown that alternative approaches via
second-order logic are ultimately sterile, because they are
disconnected from inference.

Holmes comments:

The issue of realism is obviously important here (the issue of the
reference of mathematical language...)

I agree that the study of the first-order formalizations is fruitful.
It remains possible (and fruitful) from a second-order standpoint
(which does admit partial formalizations of inference).

Simpson replies to Mayberry:

 > The very same formal axioms and rules that are complete for Henkin
 > semantics are *sound* for standard semantics.

No, these axioms are not necessarily sound for standard semantics.

It depends on the metatheory.  For example, suppose the axiom of
choice fails in the metatheory.  (The metatheory might reasonably be
something like ZF + DC + AD, which is generally regarded as providing
an interesting alternative to the axiom of choice.)  Suppose also that
our axioms of second-order logic include a choice scheme, as in
Shapiro's system D2, for instance.  Then the axioms for second-order
logic will *not* be sound for the standard semantics.  To say that
Shapiro's choice scheme is sound for the standard semantics is easily
seen to be equivalent to the axiom of choice holding in the
metatheory.  We know that this need not be the case, thanks to modern
f.o.m. research, specifically to Cohen's important work on the axiom
of choice in the context of (first-order!) f.o.m.  Thus Cohen's work
can save us from embarrassment and confusion, provided we take it to
heart.

Holmes comments:

This is a very nice point.  One does need to be careful about this
kind of thing.  I would not include a choice scheme in my second-order
logic.  As I noted above, I have never claimed that Cohen's work (or
other modern f.o.m. research) was not applicable from (and to) a
second-order standpoint (nor has Mayberry); it is you who have claimed
that!

Simpson replies to Mayberry:

 > What makes the formal theory ZFC so important for foundations is
 > the fact that any proof in ordinary mathematics has a formal
 > counterpart in ZFC.

This statement of the importance of ZFC is inadequate.  There's more
to it than that, especially from the Platonist or realist viewpoint.
Not only can ZFC formalize all mathematical proofs, but in addition,
ZFC is the strongest axiomatic theory that we can write down in the
language {epsilon,=} that is directly based on certain informal
insights or naive intuitions about the universe of set theory
(informal replacement, informal axiom of choice, etc).  Thus ZFC is
unique in an appropriate, relevant sense.  This should be viewed as
another aspect of why ZFC is so important for f.o.m.

Holmes comments: The informal theory you are describing is
what I would call "second-order ZFC"!

Mayberry goes on to guess that Simpson's view is "old-fashioned formalism".
I'm not sure this is the case; I'm not sure what Simpson's positions are
on the substantive philosophical questions, because it has hitherto been
very hard to communicate with him.  I hope that this is about to improve.

I would like Friedman to explain why he thinks that it is so easy to
define the set of natural numbers in the language of first-order set
theory.  How do we see that the definition captures our pre-formal
notion of what a natural number is?  How do we understand what the
primitives of first-order ZFC mean?  I'd like to ask Simpson whether
his apparent problems with understanding what I am saying are based on
similar issues.

And God posted an angel with a flaming sword at | Sincerely, M. Randall Holmes
the gates of Cantor's paradise, that the       | Boise State U. (disavows all) 
slow-witted and the deliberately obtuse might | holmes at math.idbsu.edu
not glimpse the wonders therein. | http://math.idbsu.edu/~holmes