An error was encountered while trying to add the item to the cart. Please try again.
The following link can be shared to navigate to this page. You can select the link to copy or click the 'Copy To Clipboard' button below.
Copy To Clipboard
Successfully Copied!
Complexity of Proofs and Their Transformations in Axiomatic Theories

Available Formats:
Hardcover ISBN: 978-0-8218-4576-9
Product Code: MMONO/128
153 pp
List Price: $84.00 MAA Member Price:$75.60
AMS Member Price: $67.20 Electronic ISBN: 978-1-4704-4536-2 Product Code: MMONO/128.E 153 pp List Price:$79.00
MAA Member Price: $71.10 AMS Member Price:$63.20
Bundle Print and Electronic Formats and Save!
This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version.
List Price: $126.00 MAA Member Price:$113.40
AMS Member Price: $100.80 Click above image for expanded view Complexity of Proofs and Their Transformations in Axiomatic Theories Available Formats:  Hardcover ISBN: 978-0-8218-4576-9 Product Code: MMONO/128 153 pp  List Price:$84.00 MAA Member Price: $75.60 AMS Member Price:$67.20
 Electronic ISBN: 978-1-4704-4536-2 Product Code: MMONO/128.E 153 pp
 List Price: $79.00 MAA Member Price:$71.10 AMS Member Price: $63.20 Bundle Print and Electronic Formats and Save! This product is available for purchase as a bundle. Purchasing as a bundle enables you to save on the electronic version. List Price:$126.00
MAA Member Price: $113.40 AMS Member Price:$100.80
• Book Details

Translations of Mathematical Monographs
Volume: 1281993
MSC: Primary 03;

The aim of this work is to develop the tool of logical deduction schemata and use it to establish upper and lower bounds on the complexity of proofs and their transformations in axiomatized theories. The main results are establishment of upper bounds on the elongation of deductions in cut eliminations; a proof that the length of a direct deduction of an existence theorem in the predicate calculus cannot be bounded above by an elementary function of the length of an indirect deduction of the same theorem; a complexity version of the existence property of the constructive predicate calculus; and, for certain formal systems of arithmetic, restrictions on the complexity of deductions that guarantee that the deducibility of a formula for all natural numbers in some finite set implies the deducibility of the same formula with a universal quantifier over all sufficiently large numbers.

Research mathematicians.

• Chapters
• Introduction
• Chapter I. Upper bounds on deduction elongation in cut elimination
• Chapter II. Systems of term equations with substitutions
• Chapter III. Logical deduction schemata in axiomatized theories
• Chapter IV. Bounds for the complexity of terms occurring in proofs
• Chapter V. Proof strengthening theorems
• Request Review Copy
• Get Permissions
Volume: 1281993
MSC: Primary 03;

The aim of this work is to develop the tool of logical deduction schemata and use it to establish upper and lower bounds on the complexity of proofs and their transformations in axiomatized theories. The main results are establishment of upper bounds on the elongation of deductions in cut eliminations; a proof that the length of a direct deduction of an existence theorem in the predicate calculus cannot be bounded above by an elementary function of the length of an indirect deduction of the same theorem; a complexity version of the existence property of the constructive predicate calculus; and, for certain formal systems of arithmetic, restrictions on the complexity of deductions that guarantee that the deducibility of a formula for all natural numbers in some finite set implies the deducibility of the same formula with a universal quantifier over all sufficiently large numbers.