Informatik, TU Wien

Concrete Mathematical Incompleteness

Kurt Goedel Society Lecture


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 by the mathematical logic community.

The highlight of the talk is the presentation of unprovable theorems stated in terms of fixed points; cliques in graphs; kernels in directed graphs.

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. 6 is BRT (Boolean Relation Theory).

1. Patterns in finite sequences from a finite alphabet.
2. Pointwise continuous embeddings between countable sets of reals (or more concretely, rationals).
3. Relations between f(n_1,...,n_k) and f(n_2,...,n_k+1).
4. Homeomorphic embeddings between finite trees.
5. Borel sets in the plane and graphs of one dimensional Borel functions.
6. Boolean relations between sets of integers and their images under integer functions.


Harvey M. Friedman is Distinguished University Professor of Mathematics,Philosophy, and Computer Science at The Ohio State University in Columbus,Ohio, USA. He was the recipient of the 1984 Waterman Award given annuallyto one researcher covering all fields of science and engineering, for "hisrevitalization of the foundations of mathematics, his penetratinginvestigations into the Goedel incompleteness phenomena, and hisfundamental contributions to virtually all areas of mathematical logic".Friedman is best known for his creation of Reverse Mathematics, wherebylogical equivalences between theorems and axioms are systematicallyestablished, and Concrete Mathematical Incompleteness, whereby Goedel'sincompleteness phenomena is systematically extended to various contexts inBorel measurable, discrete, and finite mathematics. His research monographBoolean Relation Theory and Incompleteness will appear in the LectureNotes in Logic series of the Association of Symbolic Logic.