April 10, 1997

Harvey Friedman, Ohio State University
"Unprovable theorems in discrete mathematics"

Abstract:

An "unprovable theorem" is a mathematical result that cannot be proved using the commonly accepted axioms for mathematics (Zermelo-Frankel plus the axiom of choice), but can be proved by using the higher infinities known as large cardinals. Large cardinal axioms have been the main proposal for new axioms, going back to Godel.

Godel's famous incompleteness theorems from the 1930's demonstrated the possibility of unprovable theorems in discrete and finite mathematics. However, there has not been any real example of an unprovable theorem in discrete or finite mathematics from the mathematical point of view.

We begin by discussing theorems of the following flavor: "every discrete function is well behaved over a finite set of specified size." Such theorems have been a major theme in combinatorics - in particular, in Ramsey theory. We present some new theorems of this kind involving shift invariance, thus providing a new view of some aspects of classical Ramsey theory.

We then move to the context of operators on the space of finite self maps in Cartesian powers of the natural numbers. We discuss regularity conditions on such operators that are sufficient to ensure the existence of fixed points.

One of the regularity conditions is of special importance, and is called "inductively decreasing." This simple condition ensures the existence of a rich collection of fixed points.

We present unprovable theorems in discrete mathematics to the effect that:
*) "every inductively decreasing operator has a fixed point which is very well behaved over a finite set of specified size."

This statement is proved from the existence of large cardinals by first proving the set theoretic theorem that:
**) "every appropriate function on a suitably large cardinal is very well behaved over a finite set of specified size."

*) is to be viewed as a discrete form of **).

It is a theorem of set theory that **) requires a suitably large cardinal that goes well beyond the usual axioms of mathematics. The main result is that its consequence, *), also requires use of the same suitably large cardinal despite the fact that *) lives in discrete mathematics.

These unprovable theorems in discrete mathematics have obvious finite forms which can be shown to be equivalent using straightforward compactness arguments. These finite forms assert that "every inductively decreasing operator on the self maps living in a sufficiently large initial segment of the natural numbers has a fixed point which is very well behaved over a set of specified size."