FOM: U Penn Rademacher Lectures September 17-20, 2002

[Andre Scedrov]

                      University of Pennsylvania 

                      Department of Mathematics

                       Hans Rademacher Lectures 

                       September 17 - 20, 2002

                      4:30 p.m., T-Th Sep 17-19
                         4:00 p.m., F Sep 20

       All lectures in room A-6 of the David Rittenhouse Laboratory, 
           first floor, 33-rd and Walnut Streets, Philadelphia


             DEMONSTRABLY NECESSARY USES OF ABSTRACTION

                         Harvey M. Friedman
                        University Professor
                       Ohio State University



RADEMACHER SERIES ABSTRACT.

There are many familiar theorems whose proofs use methods which are in some
appropriate sense substantially more "abstract" than its statement. Some
particularly well known examples come from the use of complex variables in
number theory. Sometimes such abstraction can be removed - for example by
the "elementary proof of the prime number theorem" - and sometimes no
appropriate removal is known. The interest in removing abstraction
typically varies, with no agreed upon criteria for appropriateness. E.g.,
the removal might sacrifice naturalness or intelligibility, or the result
of the removal criticized as being merely a thinly disguised form of the
original.

These Rademacher lectures focus on cases of demonstrable unremovability of
abstraction, primarily (but not solely) in the context of discrete
mathematics. These cases rely on a sharp, fully formalized, criteria for
removal, where a proof of unremovability has been found. The issue of
"natural" removal is finessed, as there is no removal, natural or
otherwise.

More specifically, in each case we begin with a theorem whose known proofs
use methods that are unexpectedly abstract relative to its statement. Next,
we delineate flexible and comprehensive methods of lower abstraction. Then
we present the result that the original theorem cannot be proved using only
these methods of lower abstraction.


LECTURE 1. DEMONSTRABLY NECESSARY USES OF ABSTRACTION.

In the first lecture, we introduce all of the examples of demonstrable
unremovability of abstraction under discussion. No formalisms will be
presented. The identification of methods and their levels of abstraction
will be given only at the informal mathematical level, without the use of
axiomatic systems. The examples include

1. Minimization in norm of integral polynomials.
2. Termination of lexicographic descent in the natural numbers.
3. Hilbert basis theorem.
4. Degrees of algebraic approximations to sets.
5. Comparison of blocks within finite sequences of natural numbers.
6. Comparison in sequences of finite trees, and within large finite trees.
7. Graph minors in sequences of finite graphs.
8. Continuous comparison of countable sets of reals.
9. Borel diagonalization for infinite sequences of reals.
10. Borel selection/antiselection in symmetric Borel sets.
11. Borel selection in Borel sets.
12. 6561 cases of Boolean relation theory.

The climax of the series is item 12, where the demonstrably necessary level
of abstraction is so immense that it is goes well beyond the usual accepted
axioms for mathematics. This is despite the fact that the context is that
of functions on the natural numbers.

LECTURE 2. POLYNOMIALS, TERMINATION, HILBERT BASES, DEGREES.

We will present an in depth discussion of the demonstrably necessary uses
of abstract methods in the minimization in norm of integral polynomials, in
the termination of lexicographic descent in the natural numbers, in the
Hilbert basis theorem, and in the degrees of algebraic approximations to
sets.

LECTURE 3. COMPARISON OF BLOCKS, TREES, GRAPHS, COUNTABLE POINTSETS.

We will present an in depth discussion of the demonstrably necessary uses
of abstract methods in the comparison of blocks within finite sequences of
natural numbers, in the comparison of terms in sequences of finite trees,
in the comparison of subtrees within large finite trees, in graph minors
within sequences of finite graphs, and in the continuous comparison of
countable sets of reals.

LECTURE 4. BOREL DIAGONALIZATION, BOREL SELECTION, BOOLEAN RELATION THEORY.

We will present an in depth discussion of the demonstrably necessary uses
of abstract methods in Borel diagonalization for infinite sequences of
reals, in Borel selection/antiselection in symmetric Borel sets of reals,
in Borel selection in Borel sets of reals, and finally in 6561 cases of
Boolean relation theory. In this last case, the demonstrably necessary
level of abstraction is so immense that it is goes well beyond the usual
accepted axioms for mathematics. This is despite the fact that the context
is that of functions on the natural numbers.