User v sairam - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T16:57:54Z http://mathoverflow.net/feeds/user/17398 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/70993/proof-systems-and-their-hierarchy/73748#73748 Answer by v sairam for Proof systems and their hierarchy 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> http://mathoverflow.net/questions/70993/proof-systems-and-their-hierarchy 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>