The Limits of Proof

Explore the foundations and limitations of mathematical proofs in this 56-minute lecture by Paul Beame from the University of Washington. Delve into formal proofs, examining the contributions of influential figures like Gottlob Fraga, David Hilbert, Bertrand Russell, and Alfred North Whitehead. Investigate propositional logic, Boolean formulas, and various proof systems including textbook proofs, truth tables, and inference systems. Analyze advanced topics such as resolution proofs, DPLC, CDCL, and random formulas. Examine proof complexity, polynomial calculus, optimization techniques, and cutting planes. Discover higher degree proof systems, positive selling sets, sum of squares proofs, extension complexity, and dynamic systems. Gain insights into the limits and capabilities of general proof systems in this comprehensive exploration of mathematical reasoning.

Introduction
Formal Proofs
Gottlob Fraga
David Hilbert
Bertrand Russell
Alfred North Whitehead
girdle
Hilbert
Finiteness
Propositional Logic
Boolean Formulas
Textbook Proofs
Truth Tables
Inference Systems
Linear Time Transformation
Resolution Proofs
DPL
CDCL
Random formulas
Frege systems
Proof complexity
Polynomial calculus
optimization
cutting planes
higher degree proof systems
positive selling sets
sum of squares proofs
sum of squares
extension complexity
dynamic systems
general proof systems