A sequent calculus demonstration of Herbrand's theorem

Details A sequent calculus demonstration of Herbrand's theorem A sequent calculus demonstration of Herbrand's theorem

2010-07-20

arxiv.org/abs/1007.3414v1

Mathematics

Logic

Scientific paper

Herbrand's theorem is often presented as a corollary of Gentzen's sharpened Hauptsatz for the classical sequent calculus. However, the midsequent gives Herbrand's theorem directly only for formulae in prenex normal form. In the Handbook of Proof Theory, Buss claims to give a proof of the full statement of the theorem, using sequent calculus methods to show completeness of a calculus of Herbrand proofs, but as we demonstrate there is a flaw in the proof. In this note we give a correct demonstration of Herbrand's theorem in its full generality, as a corollary of the full cut-elimination theorem for LK. The major difficulty is to show that, if there is an Herbrand proof of the premiss of a contraction rule, there is an Herbrand proof of its conclusion. We solve this problem by showing the admissibility of a deep contraction rule.

Affiliated with

Also associated with

No associations

Rating

A sequent calculus demonstration of Herbrand's theorem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A sequent calculus demonstration of Herbrand's theorem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A sequent calculus demonstration of Herbrand's theorem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-125921