Hostname: page-component-78c5997874-g7gxr Total loading time: 0 Render date: 2024-11-05T13:54:14.783Z Has data issue: false hasContentIssue false
  • English
  • Français

On the reduction of the decision problem

Published online by Cambridge University Press:  12 March 2014

László Kalmár  and
János Surányi
László Kalmár
Affiliation:
The Bolyai Institute, University Of Szeged
János Surányi
Affiliation:
The Bolyai Institute, University Of Szeged
Get access Rights & Permissions [Opens in a new window]

Extract

In the first paper of the above main title, one of us has proved that any formula of the first order predicate calculus is equivalent (as to being satisfiable or not) to some binary first order formula having a prefix of the form (Ex1)(x2)(Ex3) … (xn) and containing a single predicate variable. This result is an improvement of a theorem of Ackermann stating that any first order formula is equivalent to another with a prefix of the above form but saying nothing about the number of predicate variables appearing therein. Hence the question arises if other theorems reducing the decision problem to the satisfiability question of the first order formulas with a prefix of a special form can be improved in like manner. In the present paper we shall answer this question concerning Gödel's reduction theorem stating that any first order formula is equivalent to another the prefix of which has the form

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 12 , Issue 3 , September 1947 , pp. 65 - 73
Copyright
Copyright © Association for Symbolic Logic 1947

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1 Kalmár, László, On the reduction of the decision problem, first paper, Ackermann prefix, a single binary predicate, this Journal, vol. 4 (1939), pp. 1–9.Google Scholar

2 Ackermann, Wilhelm, Beiträge zum Entscheidungsproblem der mathemalischen Logik, Mathematische Annalen, vol. 112 (1936), pp. 419–432.CrossRefGoogle Scholar

3 Gödel, K., Zum Entscheidungsproblem des logischen Funklionenkalküls, Monatshefte für Mathematik und Physik, vol. 40 (1933), pp. 433–443.CrossRefGoogle Scholar

4 In its more complete form: any first order formula is equivalent to a binary one having a prefix of the form (1).

5 This device is generally used in papers dealing with the reductions of the decision problem to the case of formulas containing a single, binary, predicate variable; see e. g. Herbrand, Jacques, Sur le problème fondamental de la logique mathématique, Sprawozdania z posiedzeń Towarzystwa Naukowego Warszawskiego, wydzial III, vol. 24 (1931), pp. 12–56Google Scholar, especially pp. 39–41; Kalmár, László, Zwückführung des Entscheidungsproblems auf den Fall von Formeln mit einer einzigen, binären, Funktionsvariablen, Compositie mathematica, vol. 4 (1936), pp. 137–144Google Scholar; Skolem, Th., Einige Reduktionen des Entscheidungsproblems, Avhandlinger utgitt av det Norske Videnskaps-Akademi i Oslo mat naturvklasse, 1936, no. 6, pp. 1–17Google Scholar; Kalmár, László, Zur Reduktion des Entscheidungsproblems, Norsk matematisk tidsskrift, vol. 19 (1937), pp. 121–130Google Scholar; and loc. cit. in the footnote 1.

6 This idea is due to Kalmár. See also Surányi, János, A logikai függvénykalkulus eldöntés-problémájának redukciójáról (in Hungarian with German abstract: Zur Reduktion des Entschcidungsproblems des logischen Funktionenkalküls), Matematikai és fizikai lapok, vol. 50 (1943), pp. 51–74Google Scholar, especially pp. 66 et seq. (The paper quoted there in footnote 10 as “to be published in the Acta Sci. Math.” is identical with the present paper.)—By means of the idea in question, Kalmár has proved a theorem analogous to that of the present paper, but with four universal quantifiers instead of three. Then, Surányi made some suggestions (see footnotes 11 and 12 below) leading to the present form of the theorem.

7 We cannot characterize Φ2 on the same lines as Φ3, …, Φ1. Indeed, Φ2 cannot be characterized by the predicate Ψ(χ, Φ1), because this holds for Φ1 too; and Φλ cannot be characterized by because this holds for Φλ-1 too (λ = 3 , …, λ). Of course, we could characterize Φ2 also as the only χ for which holds; however, this idea would not lead to a simpler proof.

8 We treat the predicates Φ1, …, Φ1 as if they were different. If some of them are identical, the above conditions for Φ may bo inconsistent. Therefore, in the detailed proof, we shall replace Φ1, …, Φ1 by different elements φ1, …, φ1, …, φ1

9 For this purpose, we shall use (Ψ(x,z) ∼ Ψ(y, z)) & (Ψ(z, y)), with a free variable z, as a symbolization of the identity of two elements x and y of J.

10 See László Kalmár, Zur Reduktion des Entscheidungsproblems, loc. cit. in footnote 5. In that paper, it was proved that any first order formula is equivalent to another having a prefix of the form (Ex 1) … (Exk) (x k+1) (x k+4) (Ex k+5) … (Ex n) and containing a single, binary, predicate variable. The initial existential quantifiers are due to the fact that the above idea of interchanging them with the universal ones was not used.

11 This idea is due to Skolem. He used it to give a simpler proof of Gödel's reduction theorem; see Skolem, Th., Ein Satz über Zählausdrūcke, Acta scientiarum mathematicarum, vol. 7 (1934–1935), pp. 193–199.Google Scholar The use of this idea for getting over the above difficulty was suggested by Surányi.

12 This decisive idea was also suggested by Surányi.

13 As a matter of fact, we have also to suppose that I does not contain any element in common with T or U, i.e., any element of the form (x, y, 1) or (x, y, 2), where x and y are also elements of I. Since we can replace I by any set of the same cardinal number, there is no harm in supposing this.

14 For the sake of simplicity, we omit (or we replace by a dot) the conjunction sign. A conjunction and a disjunction with many terms are abbreviated by the signs Π and Σ, respectively.

15 We observe that I and T are abbreviations for formulas containing the only predicate Ψ.