LOGIC SEMINAR<br>

November 9, 1995 4:00 412 SEO
<br>
Speaker: Roger Maddux (Iowa State University)<br>

Title: On the number of variables required in proofs<br> 

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.