×

A calculus for finitely satisfiable formulas with identity. (English) Zbl 0262.02013

In an earlier abstract [IV Internat. Congr. Logic, Methodology and Philos. Sei., Bucharest, 1971, 14–15], later published in extended form [Notre Dame J. formal Logic 14, 373–376 (1973; Zbl 0236.02014)], the authors showed that it was possible to generate the finitely satisfiable formulae of the first order predicate calculus, the result being obtained in the context of results of other authors that finite validity was a recursively undecidable property and that the set of finitely invalid formulae could be (recursively) generated, and therefore that the set of finitely valid formulae could not be generated. The present paper shows that the set of finitely satisfiable formulae of the first order predicate calculus with equality can be generated, a result not directly obtainable from the previous ones. A modified form of the ideas of the earlier paper is used to obtain the required proof.
Reviewer: R. Harrop

MSC:

03B10 Classical first-order logic
03D25 Recursively (computably) enumerable sets and degrees

Citations:

Zbl 0236.02014
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Bullock, A. M., Schneider, H. H.: A calculus for finitely satisfiable formulas. Abstracts of the IV tn International Congress for Logic, Methodology and Philosophy of Science, Bucharest 1971; pp. 14–15.
[2] Hailperin, Th.: A complete set of axioms for logical formulas invalid in some finite domain. Zeitschr. f. Math. Logik und Grundlagen d. Math.,7 (1961), 84–96. · Zbl 0111.00803 · doi:10.1002/malq.19610070603
[3] Hasenjaeger, G., Scholz, H.: Grundzüge der mathematischen Logik. Springer-Verlag Berlin 1961. · Zbl 0137.00401
[4] Hermes, H.: Einflührung in die mathematische Logik. Teubner-Verlag Stuttgart 1963. · Zbl 0115.00503
[5] Trahtenbrot, B. A.: Impossibility of an algorithm for the decision problem in finite classes. (Russian). Doklady Akad. Nauk SSSR70 (1950), 559–572.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.