This paper examines the questions of functional completeness and canonical completeness in many-valued logics, offering proofs for several theorems on these topics.

A skeletal description of the domain for these theorems is as follows. We are concerned with a proper logic L, containing a denumerably infinite class of propositional symbols, P, Q, R, …, a finite set of unary operations, U1, U2,…, Ub, and a finite set of binary operations, B1, B2, …, Bc. Well-formed formulas in L are recursively defined by the conventional set of rules. With L there is associated an integer, M ≧ 2, and the integers m, where (1 ≦m≦M), are the truth values of L.

We assume familiarity with the canonical languages of Post (cf. [1], [2]).

A set S of strings is said to be representable in a canonical system (F) if there is a string π such that for every string X, X ∈ S if and only if πX is provable in (F).

Suppose that K is a finite alphabet containing at least 2 symbols, and that W is a set of strings in (the symbols of) K. If W is representable in some canonical system, is it necessarily representable in a canonical system which uses only the symbols of K ? We answer this question affirmatively. Thus, e.g., it is possible to construct a 2-sign universal system over its own alphabet.2

It has been shown in Dummett [1] that the system LC given by Heyting's Calculus plus the additional axiom ACpqCqp is complete with respect to the model having as truth values the integers 0, 1,2, … and ω, 0 being the designated value, with

In this system CCCpqrCCCqprr is equivalent to ACpqCqp, and the purpose of this paper is to show that the implicational fragment of Heyting's Calculus plus the additional axiom CCCpqrCCCqprr yields the implicational fragment of LC.

By a theory is meant an applied first-order predicate calculus with at least one predicate symbol and perhaps some individual constants and function symbols and a specified set of axioms. In addition to the terms defined by means of the individual variables, constants, and function symbols a theory may also include among its terms those constructed by means of operators such as the epsilon or iota operators; that is, expressions like (εχΡ) or (οχΡ), where P is a well formed formula (wff) of the theory, may also be terms. A constant term of a theory F is then a term in which no variable occurs free. We are interested only in theories which have at least one constant term so that if a theory doesn't have any individual constants it must necessarily admit as terms expressions constructed by means of operators. A sentence of a theory F is a closed wff.

Anyone who reads Aristotle, knowing something about modern logic and nothing about its history, must ask himself why the syllogistic cannot be translated as it stands into the logic of quantification. It is now more than twenty years since the invention of the requisite framework, the logic of many-sorted quantification.

In the familiar first-order predicate logic generality is expressed by means of variables and quantifiers, and each interpretation of the system is based upon the choice of some class over which the variables may range, the only restriction placed on this ‘domain of individuals’ being that it should not be empty.

The present paper concerns the relation of relative interpretability introduced in [8], and arises from a question posed by Tarski: are there two finitely axiomatizable subtheories of the arithmetic of natural numbers neither of which is relatively interpretable in the other? The question was answered affirmatively (without proof) in [3], and the answer was generalized in [4]: for any positive integer n, there exist n finitely axiomatizable subtheories of arithmetic such that no one of them is relatively interpretable in the union of the remainder. A further generalization was announced in [5] and is proved here: there is an infinite set of finitely axiomatizable subtheories of arithmetic such that no one of them is relatively interpretable in the union of the remainder. Several lemmas concerning the existence of self-referential and mutually referential formulas are given in Section 1, and will perhaps be of interest on their own account.

The object of this note is to extend to Post's m-valued propositional calculus1 the axiomatization by Anderson and Belnap2 of the 2-valued propositional calculus.

Notation and definitions. We shall use the symbols ∼ and v for the primitives of Post and shall otherwise, except as stated below, use the same notation and definitions as in the previous paper.

In a paper in this Journal [1], McKinsey used as a criterion for the independence (non-definability) of a connective F in a propositional calculus L, the existence of a matrix for L in which the functions corresponding to all the connectives other than F are class-closing over some subset S of the elements, while the function corresponding to F is not class-closing over S (i.e., for a certain choice of arguments in S its value is not in S).

If numbers be used to designate classes, there can be derived from a conjunct of classes numbers corresponding to the expanded product classes.

For example, let the product classes ābc and āb be designated by numbers I and 5 as in the following matrix:

By using 1 (20) instead of a, 2 (21) instead of b, 4 (22) instead of c, etc., the following relationship emerges between the designation of the conjunct of classes (take 12) and the product classes (I and 5): the product class(es) of any conjunct of classes is (are) (1) the sum of any negated class numbers and (2) seven less the sum of any unnegated class numbers.

There is a distinction within the natural language between those singular terms which designate and those which do not. On the basis of this distinction there arise irregularities both in the assignment to expressions of semantical properties and relations and in the presumed attribution of existence to individuals. Although such irregularities are characteristic of the employment of singular terms, they are not reproduced either for or within the usual formalized languages. Accordingly, we construct a formalized language for which the mentioned irregularities are reproduced — hence, a language which in this respect mirrors more faithfully than is customary the structure of the natural language.