Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-12T21:28:32.405Z Has data issue: false hasContentIssue false
  • English
  • Français

The decision problem for some classes of sentences without quantifiers

Published online by Cambridge University Press:  12 March 2014

J. C. C. McKinsey
J. C. C. McKinsey*
Affiliation:
The University of California
Get access Rights & Permissions [Opens in a new window]

Extract

In this paper we shall be concerned with questions regarding decision problems for certain classes of sentences (without quantifiers) of various kinds of algebra. In the first section we shall establish a result of a general nature, which enables one, in a number of cases, to reduce a decision problem of the type considered to a somewhat simpler problem. In the second section we formulate a rather broad sufficient condition for the existence of a decision method for sentences without quantifiers; and in the last section we show that this condition holds of lattices.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 8 , Issue 3 , September 1943 , pp. 61 - 76
Copyright
Copyright © Association for Symbolic Logic 1943

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

2 This term is sometimes used in a more general sense (see, for example, Birkhoff's, Garrett paper, On the combination of subalgebras, Proceedings of the Cambridge Philosophical Society, vol. 29 (1933), pp. 441–464CrossRefGoogle Scholar). Thus we could allow more than one class K, or we could allow there to be infinitely many operations, or operations not of a finite character. For our present purpose, however, such generality would lead only to superfluous complications.

3 As in Tarski's, A. paper, Der Wahrheitsbegriff in den formalisierien Sprachen, Studia philosophica, vol. 1 (1936), pp. 261–405.Google Scholar

4 See Gödel, Kurt, Die Vollständigkeit der Axiome des logischen Funktionenkalküls, Monatshefte für Mathematik und Physik, vol. 37 (1930), pp. 349–360CrossRefGoogle Scholar; or Hilbert, and Ackermann, , Grundzüge der theoretischen Logik, 2nd edn., Berlin 1938, pp. 74–81CrossRefGoogle Scholar.

5 See Reidemeister, Kurt, Einführung in die kombinatorische Topologie, Braunschweig 1932, p. 56.Google Scholar Reidemeister solves here the problem of deciding whether an arbitrary equation is true of an Abelian group with a finite number of generating relations. It is easily shown that this is equivalent to the decision problem for conditional equations in Abelian groups. The problem solved here by Reidemeister is usually called the “word problem,” though Church uses the term in a somewhat wider sense, since he admits also infinitely many generating relations (see his abstract, Combinatory logic as a semigroup, Bulletin of the American Mathematical Society, vol. 43 (1937), p. 333). The word problem for general groups is unsolved.

6 This principle has been known for a long time, though perhaps not in quite the general form in which it is here formulated. It was employed by L. Löwenheim to solve the decision problem for the sentences of the restricted function calculus which contain only one-place predicates (see Hilbert and Ackermann, loc. cit., p. 95). The author also made use of it in his paper, A solution of the decision problem for the Lewis systems S2 and S4, with an application to topology, this Journal, vol. 6 (1941), pp. 117–134.

7 See Hilbert and Ackermann, loc. cit., p. 92.

8 These axioms are given by Garrett Birkhoff. See his book, Lattice theory, New York 1940, p. 19, and p. 74.

9 The results of this section include, but are more general than, some previously established results. A decision method for equations in lattices was given by Whitman, Philip M. in his paper: Free lattices, Annals of mathematics, ser. 2 vol. 42 (1941), pp. 325–330.CrossRefGoogle Scholar Some special cases of the decision problem for open sentences in distributive lattices were solved in Th. Skolem, Untersuchungen über die Axiome des Klassenkalkuls und über Produktationsund Summationsprobleme, welche gewisse Klassen von Aussagen betreffen, Skrifter utgit av Videnskapsselskapet i Kristiania, I. Matematisk-naturvidenskabelig klasse 1919, no. 3 (1919), 37 pp.