We present a detailed proof of the admissibility of cut in sequent calculus for some congruent modal logics. The result was announced much earlier during the Trends in Logic Conference, Toruń 2006 and the proof for monotonic modal logics was provided already in Indrzejczak [5]. Also some tableau and natural deduction formalizations presented in Indrzejczak [6] and Indrzejczak [7] were based on this result but the proof itself was not published so far. In this paper we are going to fill this gap. The delay was partly due to the fact that the author from time to time was trying to improve the result and extend it to some additional logics by testing other methods of proving cut elimination. Unfortunately all these attempts failed and cut elimination holds only for these logics which were proved to satisfy this property already in 2005.
In 1934 Jaśkowski and Gentzen independently published the first work on natural deduction. Since then a lot of work has been done on both practical and theoretical aspects of natural deduction, but the original ideas of both authors are still alive and involved in recent work. In this survey paper we characterize the general idea of natural deduction, briefly compare the original systems of Jaśkowski and Gentzen, and sketch the main lines of later developments.
In 1934 Gentzen developed sequent calculus as a technical device for the study of natural deduction. Soon it turned out to be one of the most important tools of modern proof theory. In this survey paper we characterize the general idea of sequent calculi and some of their important features, in particular cut elimination and its consequences. We also briefly characterize some recent results, such as the generalized sequent calculi and the development of substructural logics.
JavaScript is turned off in your web browser. Turn it on to take full advantage of this site, then refresh the page.