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.

There has recently been developed a system of computational logic to which was given an interpretation in terms of the 2-valued propositional calculus. The object of the present paper is to give the corresponding theory for 3-valued logic. We use the same notation as Levin, except that instead of using the numeral “2” as a constant, we use “3”.

In lectures at Notre Dame University in 1948 I presented what was essentially a semantical analysis of the propositions formed from the elementary propositions of a formal system by compounding with propositional connectives and quantifiers. The system LD is one of the systems treated there in the chapter on negation. It is substantially the minimal calculus with excluded middle, and was first considered by Johansson. It corresponds semantically to the situation where we have refutability with completeness, and so it may be regarded as the natural system of strict implication. This paper gives the details of certain results concerning this system which have been reported elsewhere. Some related remarks concerning other systems will also be included. Acquaintance with the lectures cited is presupposed; they are referred to as TFD.

Since the Hilbert substitution method has been applied by Ackermann to the formalism Z of number theory in [3], we shall give the no-counter-example interpretation for extensions (c) of Z, e.g. Zμ. The work required on top of Ackermann's investigations to check conditions (α) and (β), consists only in a suitable definition of a class of recursive functional. The verification of (γ) and (δ) is much more difficult, and requires the ideas of paras. 32 and 33 in the preceding section.