×

Contributions of Polish logicians to decidability theory. (English) Zbl 0844.01010

The paper gives a comprehensive survey on Polish contributions to the decidability problem (Entscheidungsproblem) between the 1920s and the 1960s. The author shows that the overall trend from research on the decidability of theories to research on the undecidability of theories can also be observed in Poland.
Most of the Polish contributions to the decidability of theories came from A. Tarski and his school. Their main device was “effective quantifier elimination” used to characterize definability and applied in completeness and decidability proofs. This device was used, e.g., to show the decidability of various theories, e.g., the theory of dense linear order and the theory of well-ordering (cf. pp. 43-49).
With the results of Gödel, Church and Rosser the logicians’ interest shifted towards undecidability results. The author presents Tarski’s and A. Mostowski’s considerations concerning a general method of proving undecidability and its applications to particular theories.
A special section is devoted to the reducibility results of J. Pepis (who was killed by the Gestapo in 1941). Pepis distinguished three versions of decidability problems (pp. 56): 1. tautology decision problem (Allgemeingültigkeitsproblem), 2. the satisfiability decision problem (Erfüllbarkeitsproblem) and 3. the deducibility decision problem (beweistheoretisches Entscheidungsproblem). He especially worked on an elaboration of the second approach.
In the last section further incompleteness proofs by A. Tarski, A. Mostowski, and A. Ehrenfeucht are described. The author concludes with the observation that Tarski and his school were not interested in the philosophical character of the decidability problems: “For them, logic and foundations of mathematics constituted a separate field having its own problems and methods, a field developing independently of other branches of mathematics and philosophy” (p. 62).

MSC:

01A60 History of mathematics in the 20th century
03-03 History of mathematical logic and foundations
03B25 Decidability of theories and sets of sentences