Item Successfully Added to Cart
An error was encountered while trying to add the item to the cart. Please try again.
OK
Please make all selections above before adding to cart
OK
Share this page via the icons above, or by copying the link below:
Copy To Clipboard
Successfully Copied!
Complexity of Proofs and Their Transformations in Axiomatic Theories
 
Complexity of Proofs and Their Transformations in Axiomatic Theories
Hardcover ISBN:  978-0-8218-4576-9
Product Code:  MMONO/128
List Price: $165.00
MAA Member Price: $148.50
AMS Member Price: $132.00
eBook ISBN:  978-1-4704-4536-2
Product Code:  MMONO/128.E
List Price: $155.00
MAA Member Price: $139.50
AMS Member Price: $124.00
Hardcover ISBN:  978-0-8218-4576-9
eBook: ISBN:  978-1-4704-4536-2
Product Code:  MMONO/128.B
List Price: $320.00 $242.50
MAA Member Price: $288.00 $218.25
AMS Member Price: $256.00 $194.00
Complexity of Proofs and Their Transformations in Axiomatic Theories
Click above image for expanded view
Complexity of Proofs and Their Transformations in Axiomatic Theories
Hardcover ISBN:  978-0-8218-4576-9
Product Code:  MMONO/128
List Price: $165.00
MAA Member Price: $148.50
AMS Member Price: $132.00
eBook ISBN:  978-1-4704-4536-2
Product Code:  MMONO/128.E
List Price: $155.00
MAA Member Price: $139.50
AMS Member Price: $124.00
Hardcover ISBN:  978-0-8218-4576-9
eBook ISBN:  978-1-4704-4536-2
Product Code:  MMONO/128.B
List Price: $320.00 $242.50
MAA Member Price: $288.00 $218.25
AMS Member Price: $256.00 $194.00
  • Book Details
     
     
    Translations of Mathematical Monographs
    Volume: 1281993; 153 pp
    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.

    Readership

    Research mathematicians.

  • Table of Contents
     
     
    • 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
  • Requests
     
     
    Review Copy – for publishers of book reviews
    Permission – for use of book, eBook, or Journal content
    Accessibility – to request an alternate format of an AMS title
Volume: 1281993; 153 pp
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.

Readership

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
Review Copy – for publishers of book reviews
Permission – for use of book, eBook, or Journal content
Accessibility – to request an alternate format of an AMS title
Please select which format for which you are requesting permissions.