most recent 30 from http://mathoverflow.net 2013-06-20T05:46:23Z http://mathoverflow.net/feeds/question/70993 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70993/proof-systems-and-their-hierarchy v sairam 2011-07-22T15:10:03Z 2011-08-26T09:05:15Z

<p>Why ZFC is placed in top of the proof system hierarchy? How it can p-simulate other systems?</p>

http://mathoverflow.net/questions/70993/proof-systems-and-their-hierarchy/70994#70994 Kaveh 2011-07-22T15:17:30Z 2011-07-22T15:24:53Z

<p>It is an open problem if there is an optimal propositional proof system. Therefore we don't know if ZFC as a propositional proof system is optimal either.</p> <p>ZFC as propositional proof system can p-simulate any propositional proof system whose soundness (if there is proof for a formula then the formula is true) as a propositional proof system is provable in ZFC. The trick (which I think is due to Steve Cook) is based on the fact that proofs are concrete finite objects, if there is a proof for a formula in a proof system, then ZFC can prove its existence (i.e. ZFC is $\Sigma_1$-complete), combining this with the provability of the soundness we derive the truth of the encoded formula in ZFC. The rest of the argument is translating this first order proof in ZFC to a propositional proof in ZFC as propositional proof system and proving the equivalence of a propositional formula with the formula itself in the proof system. This can be done in $\mathsf{TC^0}$-Frege and any system that contains it. See <a href="http://www.cs.toronto.edu/~sacook/homepage/book" rel="nofollow">Logical Foundations of Proof Complexity</a>, 2010 by Cook and Nguyen for the details.</p>

http://mathoverflow.net/questions/70993/proof-systems-and-their-hierarchy/73748#73748 v sairam 2011-08-26T09:05:15Z 2011-08-26T09:05:15Z

<p>Iam really sorry for this delayed reply...I just digged up a bit on this topic. Here are 'my views' , Iam novice in this area, if I am wrong correct me.</p> <p>Frege systems ( also hilbert systems) is a better proof system than Gentzen systems as it captures "Human thinking" also. Now, if we add some rules which , say act as lemmas, they readily help us in proving a problem in the proof system. This lemma need not be proved in this problem again , we can just quote it.The Frege + rules = EXTENDED FREGE system.</p> <p>There is strong parallelism between Proof system and Circuit complexity proof system wherein we can simulate one problem into other.The circuit complexity class heirarchy is like Ac , NC , P/poy , TC . We concentrate on P\Poly what it means. P\poly solves the problem in polynomial time given "some polynomial time advice function". </p> <p>If we closely observe these advice functions, they are similar to 'lemmas' or 'rules' in extended frege system. Thus P\poly is equivalent to Extended Frege system.Is this the best proof system ? I think no because if we want to compare two outputs produced by applying different lemmas in this system we don;t have any parameter to compare. So we have Zorn's Lemma in our hand where it says that if we have upper bound in every chain, then we have maximal element in that set. This for us nothing but the "Axiom Of Choice". The proof system with the axoim of choice is ZFC. IS THIS THE ULTIMATUM ? No one knows......</p>