Concrete mathematical incompleteness

Concrete mathematical incompleteness

-
Harvey Friedman, Columbia University
Fine Hall 224

An unprovable theorem is a theorem about basic mathematical objects that can only be proved using more than the usual axioms for mathematics (ZFC = Zermelo Frankel set theory with the Axiom of Choice) — and that has been proved using standard extensions of ZFC generally adopted in the mathematical logic community. The highlight of the talk is the presentation of a new unprovable theorem concerning the structure of maximal cliques in certain graphs on Cartesian powers of the rational numbers. We first review some previous examples of unprovable theorems. 1-5 are unprovable in the weaker sense that any proof demonstrably requires some use of logical principles transcendental to the problem statement. These previous contexts includePatterns in finite sequences from a finite alphabet.
Pointwise continuous embeddings between countable sets of reals (or, more concretely, rationals).
Relations between $f(n_1,...,n_k)$ and $f(n_2,...,n_k+1)$.
Homeomorphic embeddings between finite trees.
Borel sets in the plane and graphs of one dimensional Borel functions.
Boolean relations between sets of integers and their images under integer functions.