FOM: NYC logic conference and panel discussion

[Sam Buss]

  This is in reply to Steve's comments on the panel discussion
at the recent NYC Logic Conference on "The Role of Set Theory
and its Alternatives in the Foundations of Mathematics".  In particular,
Steve asked my to clarify my own comments (made as a member of the
audience).  I made two comments, one on foundations of mathematics
and one on the possible future computerized theorem provers; but I will
only discuss the first topic below.

   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.
   Remark: I should make it clear that when I say "first-order logic" I allow
more generally any logic that can be recursively axiomatized, including
multi-sorted logic and even second-order logic, but I am restricting to
classical logics.  That is to say, I am saying the real foundations of
mathematics is the use of the kind of rigor and reasoning that is 
formalized by first-order logic, regardless of whether this rigor is 
applied to first-order systems or to systems which have stronger 
expressive power.

   To bolster this (perhaps surprising?) assertion, one can make
several observations:

  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.  For instance,
	how many mathematicians pay attention to when they use the axiom
	of choice?  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?  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.)
	  It is also rare for mathematical theorems to depend on large
	cardinal axioms.  (Some people, notably Harvey Friedman, are trying
	to change this situation.)
 	  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.  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). 
  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.
   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.
   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.)  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.
   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).
      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."  
	   [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.

------

Some time ago there was a lot of fom discussion on the nature of
mathematics and "What is Mathematics, Really".  I'd like to offer
my own definition:

    "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." 

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

 --- Sam Buss

I am supposed to say something about my background:
My job title is: Professor, Mathematics and Computer Science, UCSD
My research intesests include proof theory and theoretical computer science.