November 9, 1995 4:00 412 SEO
Speaker: Roger Maddux (Iowa State University)
Title: On the number of variables required in proofs
Abstract: Choose a standard textbook axiomatization for the logical validities in a first-order language with equality and binary relation symbols. For every logically valid formula f let N(f) be the greatest integer n such that every proof of f contains an ``n-formula'' (a formula that contains at least n variables). N(f) is the smallest number of variables required to prove f . A natural and as yet unproved conjecture, originating with J.D.Monk in 1969, is that for every n>3 there is a logically valid 3-formula f with N(f)=n. This talk will include: more precise formulation of the problem; explanation of the role of 3; partial results whose proofs use these combinatorial facts: the Bruck-Ryser Theorem, Ramsey's Theorem, 3-element sets outnumber 2-element sets, the Pigeonhole Principle; some current approaches toward a solution.