{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,6]],"date-time":"2024-09-06T22:48:36Z","timestamp":1725662916495},"publisher-location":"Berlin, Heidelberg","reference-count":4,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540108566"},{"type":"electronic","value":"9783540387695"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1981]]},"DOI":"10.1007\/3-540-10856-4_116","type":"book-chapter","created":{"date-parts":[[2012,2,25]],"date-time":"2012-02-25T17:33:46Z","timestamp":1330191226000},"page":"483-490","source":"Crossref","is-referenced-by-count":0,"title":["On existence of complete predicate calculus in metamathematics without exponentiation"],"prefix":"10.1007","author":[{"given":"V.Yu.","family":"Sazonov","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2005,6,3]]},"reference":[{"key":"47_CR1","doi-asserted-by":"crossref","unstructured":"Cook, S. and Reckhow, R., On the Lengths of Proofs in the Propositional Calculus. Preliminary Version. Conference Record of 6th ACM STOC (1974), 135\u2013148.","DOI":"10.1145\/1008311.1008313"},{"key":"47_CR2","doi-asserted-by":"crossref","first-page":"562","DOI":"10.1007\/BFb0022533","volume":"88","author":"V. Y. Sazonov","year":"1980","unstructured":"Sazonov, V. Yu., A Logical Approach to the Problem \"P = NP?\", Proc. of MFCS'80, Lecture Notes in Computer Sci. 88 (1980), 562\u2013575. (Corrections. 1. In this paper Lemma 5.4(4) is given without formal proof, and, as the author has understood, he cannot give such a proof at this moment. Therefore, the strong form of Main Result represented by theorems 1.1, 1.3, 3.7 and 5.1 and depending on this Lemma is actually not proved. However, its weakened form given by Theorem 3.8 is proved correctly. Theorems 1.1, 1.3 and 5.1 should also be correspondingly weakened. (Substitute TQ in place of T.) Note that the damage proof of 5.1 contains useful Lemma 5.2 and demonstrates what can be done in theories TO and T. 2. In the proof of theorem 2.3 it is not exactly said that \u03be n x may be defined as a subsequence of $$\\tilde \\xi _n^x$$ . It should be taken $$\\xi _\\Lambda ^x = \\tilde \\xi _\\Lambda ^x$$ and $$\\xi _{n + 1}^x = \\underline {if} \\tilde \\xi _{n + 1}^x \\notin \\{ \\xi _i^x \/i \\leqslant n\\}$$ then $$\\tilde \\xi _{n + 1}^x$$ else the first Bj\u2209{\u03be i x | i\u2a7dn} (it is obvious that j\u2a7dn+1). Then $$\\tilde \\xi _n^x = \\xi _{q(n,x)}^x$$ for some P-function q(n,x)\u2a7dn. Addition. With the contrast to the hypothesis on page 565 it can actually be proved that the linear and the lexicographical inductions for quantifier free formulas are equivalent.)","journal-title":"Proc. of MFCS'80, Lecture Notes in Computer Sci."},{"issue":"7","key":"47_CR3","first-page":"319","volume":"16","author":"V. Y. Sazonov","year":"1980","unstructured":"Sazonov, V. Yu., Polynomial Computability and Recursivity in Finite Domains. EIK 16 (1980) 7, 319\u2013323.","journal-title":"EIK"},{"key":"47_CR4","volume-title":"Mathematical Logic","author":"S. C. Kleene","year":"1967","unstructured":"Kleene, S. C., Mathematical Logic, J.Wiley & Sons, INC, New York-London-Sydney, 1967."}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 1981"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-10856-4_116.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,17]],"date-time":"2020-11-17T20:03:59Z","timestamp":1605643439000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-10856-4_116"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1981]]},"ISBN":["9783540108566","9783540387695"],"references-count":4,"URL":"https:\/\/doi.org\/10.1007\/3-540-10856-4_116","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[1981]]}}}