FOM: Role of ZFC and logic in f.o.m.

[Harvey Friedman]

Sam Buss wishes to draw a sharp distinction between the role of set theory
and ZFC axioms in f.o.m. and the role of first order logic in f.o.m. Among
other things, he cites the different way mathematicians handle these two
matters. I am not convinced of this sharp distinction, and regard set
theory and first order logic as inseparable components of f.o.m. In
particular, I am not sure that Buss makes an appropriate distinction
between the various forms of implicit and explicit use mathematicians make
of first order logic and set theory.

In particular, many mathematicians are generally comfortable with and
understand explicit uses of the simpler axioms of set theory, and are
comfortable citing them if need be. Far fewer could cite logical axioms and
rules, as they rarely have a sufficient conscious understanding of the
structure of mathematical assertions in order to even formulate any logical
axioms and rules.

E.g., the axiom of pairing and the axiom of power set are more friendly to
them than the axiom of existential generalization and the rule of universal
generalization.

Sam Buss writes 4:51PM 12/6/99:

>   My basic assertion was that the real foundations of mathematics
>is first-order logic, or the use of rigorous reasoning and mathematical
>rigor that can be formalized in first logic.  This is in contrast
>to the usual point of view that set theory is the foundations of mathematics.

But this does not take into account the fact that there is a substantial
amount of common background material that is assumed no matter what a
mathematics course is. And I believe that if you examine what is really in
common with all serious mathemtatics courses, it is essentially set theory
and the set theoretic definitions of various set theoretic notions such as
sequences, functions, etcetera.

This basic common core stuff does not seem to me to be only first-order
logic. It seems to be elementary set theory.

On the other hand, if you are talking about a wider community - say all of
mathematical science, including staistics and computer science, then your
case is better - although not entirely convincing since the basic common
core stuff still might have to include arithmetic and some finite set
theory.

Buss continues:

>  1. Nearly every mathematicians is quite comfortable with set notation
>	and informal set formation; however, few mathematicians are
>	familiar with the formalization of mathematics in ZFC.

The fair comparison might be: how familiar are they with set theory axioms
such as power set and separation, versus how familiar are they with logical
axioms and rules such as existential instantiation and universal
generalization. Answer: they are allergic to both, but more directly
familiar with and comfortable with the former.

Buss continues:

>For instance,
>	how many mathematicians pay attention to when they use the axiom
>	of choice?

But how many pay attention to when they use the law of excluded middle?
Remember my point at the top of the posting - that I am not convinced of
the sharp distinction you wish to draw between set theory and first order
logic in terms of their role in f.o.m.

Buss continues:

>How many know the difference between the dependent
>	axiom of choice versus the full axiom of choice?  How many know
>	what the axiom of replacement is?

How many know the difference between proving notA by assuming A and getting
a contradiction, versus proving A by assuming notA and getting a
contradiction? We are both talking about this at the conscious level.

Buss continues:

>Furthermore, is there any
>	point to mathematicians watching out for these issues?  Shouldn't
>	they just take the axiom of choice as being obviously true?
>	(Unless they are being careful about constructivity, and even then
>	the axiom of choice is generally accepted as true.)

Before I respond to this, let me just say that I don't quite see how this
paragraph is a justification of your first paragraph.

Now for a response. If mathematicians are just interested in continuing a
long tradition of pure mathematics with its well defined established
culture, then there is no point in "watching out for these issues." It has
been clear for some time that the long tradition of pure mathematics with
its well defined established culture is in no danger of crisis for a long
time - although there is no question that I can imagine results that would
change this situation substantially, and I try to do this myself, expecting
that this shakeout will occur after I am no longer am around to see it.

On the other hand, a mathematician may feel that he/she is part of the
wider intellectual community. Then it is very natural to get interested in
a whole array of issues in f.o.m. because of their great general
intellctual interest.

Buss continues:

> 	  As additional evidence of the cultural fact that mathematicians no
>	longer use set theory essentially, note that (in the US at least), set
>	theory and mathematical logic are not commonly taught in either the
>	graduate or undergraduate curriculum.

There are some low powered foundations courses around for undergraduates,
where there is at least a practical, mostly set theoretic development of
arithmetic and the real number system, etcetera. Perhaps the mathematical
logic is not emphasized, but at least the real line gets defined and facts
are proved about it.

Buss continues:

>I have served on the graduate
>	student admissions committee here at UCSD and know from experience
>	that almost no prospective graduate students have studied logic or
>	set theory as undergraduates (well under 5%, I'd estimate).

But won't the undergraduates frequently have seen a reasonably careful
treatment of the number systems, etcetera, in set theoretic terms? E.g.,
Dedekind cuts, etcetera?

Buss continues:

>  2. The bulk of mathematics can be done in second-order logic rather than in
>	set theory --- however to really do mathematics in second-order logic
>	would be very awkward.  Take as an example the study of Banach spaces.
>	These are abstract spaces providing a very general framework for
>	theorems in analysis, differential equations, etc.  Nearly every
>	interesting example of a Banach space is definable in higher-logic
>	over the reals.  However, it is far better to formalize
>	Banach spaces in a general setting with no reference to higher-order
>	logic over the reals.  This is generally done in an informal
>	set-theoretic setting, but in practice it is done (a) by formulating
>	first-order axioms about Banach spaces and functions on Banach spaces,
>	and (b) taking the reals as given.

OK, but this is still in a set theoretic setting, and it is implicit in the
setup that the set theoretic treatment of the reals is something done at
the undergraduate level and can be built on top of. Set theory is still
there in this sense.

Buss continues:

>   3. The theory of the reals provides a good example of how both set theory
>	and first-order logic are used in foundations for mathematics.  Of
>	course the traditional foundations of the reals uses set theory:
>	Dedekind cuts or Cauchy sequences with the construction resting
>	ultimately on the definition of integers.  The integers themselves
>	can be defined in terms of sets (the von Neumann integers).
>	   However, it is also possible to formalize the integers in
>	first-order logic (Peano arithmetic).  And in fact, most mathematical
>	reasoning about first-order theorems about the integers is done
>	more in the style of Peano arithmetic, rather than in the style of
>	set theory.  Thus, it is common to think of induction as a
>	fundamental principle rather than a derived principle.  Also, it is
>	extremely rare for a mathematician to write an assertion like
>	"7 \in 9" which depends on the formalization of von Neumann integers.

A case can be made that it is best to do set theory with natural numbers as
urelements, since the purely set theoretic treatment of natural numbers has
a somewhat different character than other aspects of the set theoretic
treatment of mathematics. But set theory with natural numbers as urelements
is really awfully close to set theory.

By the way, if you do set theory with natural numbers as urelements, it is
natural to take induction as an axiom. But I would still call this set
theoretic foundations.

Buss continues:

>   4. One of the distinguishing features of mathematics is the use of
>	proof and of mathematically rigorous reasoning.  Especially noteworthy
>	is the fact that mathematicians will nearly always agree on whether a
>	given asserted theorem has been correctly proved.  When there are
>	agreements on whether a proof is correct, mathematicians try to
>	resolve their disagreement by breaking their argument into smaller
>	steps, down to the level of first-order logic if necessary (but
>	not down to the level of set theory.)

I would not characterize the way mathematicians try to resolve their
disagreements over correctness of proofs in the way that you are. The
process mathematicians most commonly use has nothing whatsoever to do with
first order logic, or no more than any other mathematics has to do with
first order logic. It is the following professional and mathematical
process:

1) first demand that there be a manuscript available;
2) try to reconstruct the proof, asking questions if necessary;

Assuming this fails,

3) try to give another proof;

Assuming this fails and one is suspicious,

4) give counterexamples to lemmas and/or other assertions in the
manuscript; and/or
5) prove that certain definitions are ill defined for various reasons.

In other words, the usual way to show that a proof Pi is incorrect is to
engage in normal mathematical activity without regard to first order logic
or ZFC. There is nothing formal about this process, and so it makes no
sense to me to compare the roles of set theory and first-order logic in
this process.

Buss continues:

>Lasting disagreements
>	on whether a proof is correct are rare; on the contrary, they can
>	usually be resolved to *everyone's* satisfaction.
>	   I believe that this fact is due directly to the fact that
>	mathematicians are reasoning with methods that are *formalizable
>	in principle* in a first-order system.  This makes the notion
>	of mathematical rigor a robust and objective concept.

I don't think this explains why things are so often fully resolved. For
instance, it is likely that one can decide *in principle* whether a comet
will destroy human life on this planet within 200 million years. Just wait
200 million years and see. However, that is too impractical a method, and
it doesn't prevent people from having sharply different views about this.

On the other hand, I have no doubt that ZFC and first order logic would
play a role in any sufficiently long dispute about the correctness of an
argument if the process I outlined above were to continue to fail over and
over again, even after the "proof" was cut up into manageable pieces and
examined independently. But it would come into play only as a last resort
and only when it can be applied to tiny subproofs.

Incidentally, my impression is that there have been several proofs within
the last ten years - even in recursion theory - where there is no agreement
on whether the proof is correct. They are just too long and complicated in
their present form. Limit cycles, sphere packing, Poincare conjecture,
automorphisms of degrees, etcetera.

Buss continues:

>   5. In defense of set theory, I should mention that it provides the best
>	general "ontology" for mathematics.  We have good
>	intuitive reasons for believing in the "existence" of mathematical
>	concepts such as the integers, the reals, functions on the reals,
>	etc.  Set theory has the advantage that it provides a single
>	framework for a Platonic view of *all* of mathematics.   In other
>words,
>	set theory may not be optimal foundation for common concepts such
>as the
>	integers or the reals (since we have clear direct intuitions of these
>	concepts that do not require the complexity of set theory), but
>	set theory has the generality to handle *all* mathematical
>	constructions.  This is a remarkable fact (and one that Haim
>	Gaifman made very clearly in his introductory remarks at the panel
>	discussion).

Hard to complain about this paragraph - even though I tried!

Buss continues:

>      Nonetheless, one can consider a thought-experiment: suppose that
>	the next generation were to stop thinking about sets for their
>	foundations.  Would this stop the study of mathematics?  Would this
>	necessarily fundamentally alter the nature of mathematics?  (Setting
>	aside the areas of the mathematics, such as set theory, that study
>	sets directly.)   I think that, as a thought-experiment, the answers
>	to these questions is "No."

At one time in the history of mathematics, before anybody thought of sets
as foundations, there was a great deal of heated argument and a great deal
of justified uneasiness. The answer can only be "No" if people are fully
aware that this has been thoroughly worked out already.

Buss continues:

>	   [Please note I am *not* predicting the demise of set theory,
>	I am only conducting a thought-experiment!  Set theory will clearly
>	be around at least until some clearly better alternative approach is
>	found, and such an alternative would obviously be a *major* innovation.
>	I suspect that any possible alternative would build heavily on the
>	highly successful example of set theory.]
>	    One the other hand, it is very difficult
>	to conceive of mathematics being carried out without the use of the
>	type of rigor inherent in first-order logical reasoning.

Look, I'll bet you can make a case that

1) mathematicians are not operating consciously in terms of sets; AND
2) mathematicians are not operating consciously in terms of first order
logic either.

You can make a case that they just feel their way through all this, with
mental images and notepads and scribbles.

What I am not clear about is how you so strongly distinguish the "logic" in
the background from the "sets" in the background.

After all, it seems to me that the mathematicians are much more *directly*
familiar with

i) the concept of set;
ii) the simpler of the axioms of set theory (certainly not all of them).

than they are with

iii) quantifiers and connectives;
iv) practically any axioms and rules involving quantifiers and connectives.

Buss continues:

>    "Mathematics is the study of objects and constructions, or of aspects of
>  objects and constructions, which are capable of being fully and completely
>  defined.  A defining characteristic of mathematics is that once mathematical
>  objects are sufficiently well-specified then mathematical reasoning can be
>  carried out with a robust and objective standard of rigor."

NOTE: I have the luxury of never really trying to define what mathematics
is on the FOM e-mail list. Sam doesn't have that luxury.
**********

The problem with this definition is that it is not easy to make a really
good case that, e.g., sets are "capable of being fully and completely
defined", or for that matter, that quantifiers are "capable of being fully
and completely defined." What are they going to be fully and completely
defined in terms of? Or are they already fully and completely defined
simply by mentioning their names?

Also, I am not sure how this definition plays out in computer science and
statistics. Whether you want to say that computer science and statistics
are mathematics, or perhaps that certain components of computer science and
statistics are mathematics? And which components are and are not
mathematics?

Buss remarks:

>(Please note that "objects" is intended to include non-physical objects!)

Yes, but if you are going to define mathematics, then your definition
should probably tell us where these non-physical objects come from. Are
they arbitrary mental constructions? Do they have an existence independent
of our minds? Etcetera. Do only certain mental constructions count as
mathematics, and which ones?

In addition, a definition of mathematics with teeth should tell us
something about the difference between good and bad mathematics, between
interesting and uninteresting mathematics, etcetera. And what the point of
mathematics is. Is mathematics a subject, or an activity, or a science, or
what?