FOM: Consistency / Combinatorial

[Sam Buss]

  I've been travelling for the past few weeks, and haven't followed the
entire FOM discussion on the status of ConZFC as a combinatorial principle,
so my apologies if this message duplicates earlier ones.
My own opinion is that ConZFC is clearly a combinatorial principle, but
of course it is not esthetically "natural" from a combinatorial point of view.

   Along these lines, no one seems to have mentioned the recent paper 
of J. Avigad which recasts the consistency of extended Frege (eF) systems 
as a combinatorial principle about directed acyclic graphs.  The
extended Frege systems are standard formulations of propositional
logic formulated with modus ponens.  The combinatorial
principle is shown to be equivalent to the Con(eF), so of course its
combinatorial content is the same as that of Con(eF).  
  It is entirely plausible that a similar combinatorial
reformulation of ConZFC could be found in the future, which
would be "natural" from a combinatorial point of view.

The paper is:

   J. Avigad, Plausibly Hard Combinatorial Tautologies,
	in: Proof Complexity and Feasible Arithmetics,
	P Beame, S Buss, eds, DIMACS Series, Vol 39,
	American Mathematical Society, 1998, pp.1-12.


 --- Sam Buss