Hostname: page-component-848d4c4894-wzw2p Total loading time: 0 Render date: 2024-06-01T03:52:29.473Z Has data issue: false hasContentIssue false
  • English
  • Français

On direct products of theories

Published online by Cambridge University Press:  12 March 2014

Andrzej Mostowski
Andrzej Mostowski*
Affiliation:
University of Warsaw
Get access Rights & Permissions [Opens in a new window]

Extract

This paper deals with the notion of direct product in the theory of decision problems.

Elementary mathematical theories are always concerned with certain functions defined in a set I (called the universe of discourse of the theory) and certain relations with the common domain I. The notions of functions and relations are known to be reducible to each other. To avoid duplication of definitions and proofs we shall eliminate the former notion in favor of the latter and consider only theories in which all the primitive terms are of the type of relations (with an arbitrary number of arguments).

It is easy to define for relations the notion of a direct product in the way which is usual in abstract algebra. We are led to this definition in a very natural way when we reflect that relations are but a particular case of functions, and the direct product of an arbitrary number of functions is defined in algebra.

A relation which is representable as a product of an arbitrary number of pairwise identical relations is called the power-relation, and the relations which occur as factors are called the base-relations.

The content of the present paper can now be characterized more precisely as follows.

We shall discuss a theory of which the primitive notions are representable as powers of certain base-relations, and shall try to reduce all the problems concerning this theory (in particular the decision problem) to problems concerning the theory of the base-relations. It will be seen that this reduction is in fact possible, and that several particular cases of the decision problem, the solutions of which are known from the literature, can be included in the general scheme established in the present paper.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 17 , Issue 1 , March 1952 , pp. 1 - 31
Copyright
Copyright © Association for Symbolic Logic 1952

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

BIBLIOGRAPHY

[1]Church, Alonzo. Introduction to mathematical logic, Part I. Annals of mathematics studies, number 13, Princeton 1944.Google Scholar
[2]Hausdorff, Felix. Mengenlehre. 3rd edition. J. Springer, Berlin 1935.Google Scholar
[3]Robinson, Julia. Definability and decision problems in arithmetic, this Journal, vol. 14 (1949), pp. 98–114.Google Scholar
[4]Skolem, Thoralf. Untersuchungen über die Axiome des Klassenkalküls und über “Produktations- und Summationsprobleme”, welche gewisse Klassen von Aussagen betreffen, Skrifter utgit av Videnskapsselskapet i Kristiania, I. klasse, no. 3, Oslo 1919.Google Scholar
[6]Skolem, Thoralf. Über gewisse Satzfunktionen in der Arithmetik, Skrifter utgit av Videnskapsselskapet i Kristiania, I. klasse, no 7, 1930.Google Scholar
[7]Szmielew, Wanda. Decision problem in group theory, Proceedings of the Tenth International Congress of Philosophy, vol. I, Amsterdam 1949, pp. 763–766.Google Scholar
[7]Tarski, Alfred. Der Wahrheitsbegriff in den formalisierten Sprachen, Studia philosophica, vol. 1 (1935), pp. 261–405.Google Scholar
[8]Tarski, Alfred. Grundzüge des Systemenkalküls, zweiter Teil, Fundamenta mathematicae, vol. 26 (1936), pp. 283–301.CrossRefGoogle Scholar
[9]Tarski, Alfred. A decision method for elementary algebra and geometry. Rand Corporation, Santa Monica, California, 1948.Google Scholar
[10]Tarski, Alfred. Cardinal algebras. Oxford University Press, New York 1949.Google Scholar