Harvey Friedman, Ohio State University
October 26, 2:50 PM, Rutgers Univ. Hill Center Room 705
Abstract.
We survey a number of innocent looking finite combinatorial theorems whose
associated lower bounds are demonstrably enormous. Most of the lower bound
results are stated in conventional terms. However, logic is needed to
describe the higher levels of enormousness among the enormous. In these
contexts, one can see an intimate relationship between the level of
enormousness and the level of nonconstructivity in the proof. Contexts in
order of increasing enormousness include:
The equation f(x_1,...,x_k) = f(x_2,....,x_k+1)
Estimates in Bolzano-Weierstrass
Walks in the lattice points
Specific finite trees
Algebraic approximations to algebraic sets
Divisibility in sets of integers
Blocks in finite sequences of k letters
The inequality |f(x_1,...,x_k)| <= min(x_1,...,x_k)