Logic List Mailing Archive

Hans Rademacher Lectures at U Penn Sep 17-20

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.
_______________________________________________
Please reply to Andre Scedrov scedrov@saul.cis.upenn.edu