Bounds and permutations
Anne S. Troelstra, H. Schwichtenberg · Cambridge University Press eBooks · 2000
This chapter is devoted to two topics: the rate of growth of deductions under the process of cut elimination, and permutation of rules. It is not hard to show that there is a hyperexponential upper bound on the rate of growth of the depth of deductions under cut elimination. For propositional logic much better bounds are possible, using a clever strategy for cut elimination. This contrasts with the situation for normalization in the case of N-systems (chapter 6), where propositional logic is as bad as predicate logic in this respect. In contrast to the case of normalization for N-systems, it is not easy to extract direct computational content from the process of cut elimination for G-systems, since as a rule the process is non-deterministic, that is to say the final result is not a uniquely defined “value”. Recent proof-theoretical studies concerning linear logic (9.3) lead to a more or less satisfactory analysis of the computational content in cut elimination for C (and I); in these studies linear logic serves to impose a “fine structure” on sequent deductions in classical and linear logic (some references are in 9.6.5). We also show that in a GS-system for Cp with Cut there are sequences of deduction with proofs linearly increasing in size, while the size of their cutfree proofs has exponentially increasing lower bounds. These results indicate that the use of “indirect proof”, i.e. deductions that involve some form of Cut play an essential role in formalized versions of proofs of theorems from mathematical practice, since otherwise the length of proofs would readily become unmanageable.