Complexity of proofs and their transformations in axiomatic theories
Author(s)
Bibliographic Information
Complexity of proofs and their transformations in axiomatic theories
（Translations of mathematical monographs, v. 128）
American Mathematical Society, c1993
- Other Title
-
Сложность доказательств и их преобразований в аксиоматизированных теориях
Slozhnostʹ dokazatelʹstv i ikh preobrazovaniĭ v aksiomatizirovannykh teorii︠a︡kh
Available at / 43 libraries
-
Hokkaido University, Library, Graduate School of Science, Faculty of Science and School of Science図書
dc20:511.3/or32070273001
-
No Libraries matched.
- Remove all filters.
Note
Includes bibliographical references (p. 151-153)
Description and Table of Contents
Description
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.
Table of Contents
Introduction Upper bounds on deduction elongation in cut elimination Systems of term equations with substitutions Logical deduction schemata in axiomatized theories Bounds for the complexity of terms occurring in proofs Proof strengthening theorems References.
by "Nielsen BookData"
