In [2] E. L. Post defined a many-valued propositional logic to be functionally complete if, for every function on the set of truth-values, there exists a formula of the logic having that function as its associated truth-value function. He proved that the logic with truth-values 1, 2, …, m and (i) a unary connective ∼ such that ∼p has truth-value i+1 (mod m) when p has truth-value i, (ii) a binary connective ∨ such that p ∨ q has truth-value min(i, j) when p, q have truth-values i, j respectively, is functionally complete.

The many-valued logics described by Łukasiewicz and Tarski [1] are not functionally complete. These logics have truth-values 1, 2, …, m and (i) a unary connective ~ such that ~p has truth-value m−i+1 when p has truth-value i, (ii) a binary connective → such that if p, q have truth-values i, j respectively, then p → q has truth-value 1 for i ≧ j, and truth-value 1 for i ≧ j. The functional incompleteness of these logics is immediate, since there exists no formula in p having truth-value i (≠ 1 or m) when p has truth-value 1.

In [4] Słupecki showed that if a new unary connective T, such that T(p) has truth-value 2 for all truth-values assigned to p, is added to the 3-valued Łukasiewicz-Tarski logic, then the resulting logic is functionally complete. In [3] Rosser and Turquette proved this result for the m-valued (m ≧ 3) logic.

Professor R. L. Goodstein's neat proposal for formalising and proving the Policeman — the logical truth mentioned in my paper — illustrates the main thesis of that paper, viz., that in formalising the logic of indirect discourse one needs to avoid assigning what was said, and the report that it was said, to different levels of a semantical hierarchy. But there are two main difficulties in his proposal:

1. It is not quite clear whether the axioms and rules of Prof. Goodstein's system are to be such that substitutivity of the biconditional is maintained for all wff. If so, the system takes no account of the referentially opaque quality of indirect discourse. For example, the analogue for “If Sir Walter Scott always says the same as the author of Waverley, then George III says that anything Sir Walter Scott says is true if and only if George III says that anything the author of Waverley says is true” would be provable, though this statement is not logically true. If “A(x){Bx→x)” is well-formed (as it must be for Professor Goodstein's proof), the corresponding theorem is

2. In interpreting the letters “A”, “B”, etc. as operators, so that sentences are the substitution-instances both for variables like “x” and for schematic functions of those variables like “Ax”, Professor Goodstein's system does not provide for formalising logical truths in which ordinary predication also plays a part: e.g., “If the policeman says that all women are dangerous drivers and anything the policeman says is true, then no non-dangerous drivers are women”.

The basic aim of the present paper is to simplify the axioms for many-valued quantification theory which were developed by Rosser and Turquette in Many-valued logics ([10], pp. 33–34 and pp. 63–64). The simplification which is achieved results not only from a reduction in the number of axiom schemes and rules of inference, but also by obtaining greater formal similarity to some elegant axioms for standard 2-valued quantification theory. This result will not be accomplished by establishing the formal interdeducibility between our simplified axioms and the Rosser-Turquette set. On the contrary, it will be shown that these two sets of axioms are not formally interdeducible.

What will be shown is that whenever the Rosser-Turquette axioms are used to define a plausible set of statements, this set of statements can be defined using our simplified axioms. The exact meaning of “plausible” will become clear from what follows, so for the moment it will be sufficient to remark that a set of statements is plausible if and only if each statement of the set is analytic in the sense that the statements take designated truth-values exclusively. In general, a Rosser-Turquette set of axioms would be used to define a set of plausible statements, and in such a case our simplified axioms could be used to achieve the same result.

On sait que la conjonction et la négation constituent un système de connecteurs suffisant pour formuler le calcul des propositions classiques. Un certain intêrêt s'attache à ces formulations par suite des faits suivants: – les thèses du calcul intuitioniste qui ne comprennent pas d'autres connecteurs que la conjonction et la négation sont identiques aux thèses classiques;

– Lewis ayant formulé ses calculs modaux en prenant la conjonction, la négation et la possibilité comme connecteurs primitifs (voir Lewis-Langford 1932, ch. VI) et ayant été suivi par beaucoup de chercheurs s'occupant de modalités, le calcul classique fondé sur la conjonction et la négation est contenu dans la plupart des systèmes modaux que l'on trouve dans la littérature.

Un système logistique pour le calcul classique fondé sur la conjonction et la négation a été étudié par Rosser (voir Rosser 1953, ch. 4; aussi Copi 1954, ch. 7).

Dans cet article je vais définir cinq autres systèmes logistiques fondés sur les mêmes connecteurs, démontrer leur suffisance (en utilisant les résultats publiés de Rosser et de Copi), et — sauf un cas — démontrer l'indépendance des axiomes de chacun de ces systèmes.

In this paper an affirmative solution is given for the following problem in many-valued logic posed by Rosser and Turquette in [6] p. 110:

For every triple ‹s, t, m› with 1 ≤ s < t < m, is it possible to define a system of m-valued logic which satisfies the following conditions? I. Every statement which always takes values ≦ s is provable. II. No statement which ever takes a value > t is provable. III. Of those statements which always take values ≤ t and sometimes take a value > s, some are provable and some are not.

We state now, temporarily deferring comment, a more demanding alternative to Condition III: III′. For every truth value k such that s < k ≦ t, there are statements P and Q such that each takes the value k at least once, but never takes a value > k, and P is provable and Q is not.

In § 2 a solution is given on the level of the statement calculus. The remainder of the present section is devoted to some negative results which serve to clarify the problem, and one positive result which shall cause us to replace Condition III by III′. We confine our attention to the statement calculus.

In 1951, Horn obtained a sufficient condition for an arithmetical class to be closed under direct product. A natural question which arose was whether Horn's condition is also necessary. We obtain a negative answer to that question.

We shall discuss relational systems of the form

where A and R are non-empty sets; each element of R is an ordered triple 〈a, b, c〉, with a, b, c ∈ A.1 If the triple 〈a, b, c〉 belongs to the relation R, we write R(a, b, c); if 〈a, b, c〉 ∉ R, we write (a, b, c). If x0, x1 and x2 are variables, then R(x0, x1, x2) and x0 = x1 are predicates. The expressions (x0, x1, x2) and x0 ≠ x1 will be referred to as negations of predicates.

We speak of α1, …, αn as terms of the disjunction α1 ∨ … ∨ αn and as factors of the conjunction α1 ∧ … ∧ αn. A sentence (open, closed or neither) of the form

where each Qi (if there be any) is either the universal or the existential quantifier and each αi, l is either a predicate or a negation of a predicate, is said to be in prenex disjunctive normal form.

The principal aim of the present paper is to sketch some mathematical applications of the work of the Hilbert school in the foundations of mathematics. Most of them depend on the ε-theorems of Hilbert-Bernays II [6], or of Ackermann [1], but instead the work of Gentzen [5] or Schütte [25], which does not use the ε-symbol, could have been applied.

The avowed purpose of all this work is described in the introduction to volume I of Hilbert-Bernays: the consistency of the usual principles of proof is to be established by means of finitist methods, or at least, by means of methods which are more “evident” or more “constructive” than the principles under discussion. This formulation seems to have several defects:

• (1) Since the notion of constructive proof is vague, the whole formulation of the program is vague; and though an exact formulation constitutes, of course, an interesting problem for the logician, because of this vagueness the mathematician does not find the program attractive.

• (2) The formulation does not cover too well the actual substance of the material contained in [6]; e.g. the ε-theorems for the predicate calculus go far beyond establishing mere consistency of the predicate calculus. It is significant that it is precisely these theorems which lead to the more interesting applications, e.g. the use of the ε-theorems with equality in the solution of Hilbert's 17th problem given below.

Kleene-Post [10], Spector [14] and Friedberg [3, 4], have given a number of examples of functions which have incomparable degrees of recursive unsolvability satisfying various additional conditions. Our present purpose is to determine to what extent some of these incomparability theorems can be generalized by substituting for “α. is recursive in β” other relations Q(α, β) such as “α is hyperarithmetical in β” (which we shall think of as “α ≦ β”), and to determine what restrictions, if any, need be imposed on Q. As a consequence of our investigation we shall show that there are incomparable hyperdegrees as defined in [9] and [13].

By a theory we shall always mean one of first order, having finitely many non-logical constants. Then for theories with identity (as a logical constant, the theory being closed under deduction in first-order logic with identity), and also likewise for theories without identity, one may distinguish the following three notions of axiomatizability. First, a theory may be recursively axiomatizable, or, as we shall say, simply, axiomatizable. Second, a theory may be finitely axiomatizable using additional predicates (f. a.+), in the syntactical sense introduced by Kleene [9]. Finally, the italicized phrase may also be interpreted semantically. The resulting notion will be called s. f. a.+. It is closely related to the modeltheoretic notion PC introduced by Tarski [16], or rather, more strictly speaking, to PC∩ACδ.

For arbitrary theories with or without identity, it is easily seen that s. f. a.+ implies f. a.+ and it is known that f. a.+ implies axiomatizability. Thus it is natural to ask under what conditions the converse implications hold, since then the notions concerned coincide and one can pass from one to the other.

Kleene [9] has shown: (1) For arbitrary theories without identity, axiomatizability implies f. a.+. It also follows from his work that : (2) For theories with identity which have only infinite models, axiomatizability implies f. a.+.

Hilbert's tenth problem is to find an algorithm for determining whether or not a diophantine equation possesses solutions. A diophantine predicate (of positive integers) is defined to be one of the form

where P is a polynomial with integral coefficients (positive, negative, or zero). Previous work has considered the variables as ranging over nonnegative integers; but we shall find it more useful here to restrict the range to positive integers, no essential change being thereby introduced. It is clear that the recursive unsolvability of Hilbert's tenth problem would follow if one could show that some non-recursive predicate were diophantine. In particular, it would suffice to show that every recursively enumerable predicate is diophantine. Actually, it would suffice to prove far less.

In this paper we shall prove three theorems about recursively enumerable sets. The first two answer questions posed by Myhill [1].

The three proofs are independent and can be presented in any order. Certain notations will be common to all three. We shall denote by “Re” the set enumerated by the procedure of which e is the Gödel number. In describing the construction for each proof, we shall suppose that a clerk is carrying out the simultaneous enumeration of R0, R1, R2, …, in such a way that at each step only a finite number of sets have begun to be enumerated and only a finite number of the members of any set have been listed. (One plan the clerk can follow is to turn his attention at Step a to the enumeration of Re where e+1 is the number of prime factors of a. Then each Re receives his attention infinitely often.) We shall denote by “Rea” the set of numbers which, at or before Step a, the clerk has listed as members of Re. Obviously, all the Rea are finite sets, recursive uniformly in e and a. For any a we can determine effectively the highest e for which Rea is not empty, and for any a, e we can effectively find the highest member of Rea, just by scanning what the clerk has done by Step a. Additional notations will be introduced in the proofs to which they pertain.

We consider two formal systems for the theory of (natural) numbers, both of which are applied second-order functional calculi with equality and the description operator. The two systems have the same primitive symbols, rules of formation, and axioms, differing only in the rules of inference.

The primitive logical symbols of the systems are the improper symbols (,), the prepositional connectives ∨, &, ⊃, ≡, ~, the quantifiers ( ), (E), the equality symbol =, the description operator ι,-infinitely many distinct individual (or number) variables, and for each positive integer k infinitely many distinct k-place function variables. Our systems have in addition the following four primitive nonlogical (or arithmetical) constants:0, 1, +, ×.

The classes of “number formulas” (nfs) and “propositional formulas” (pfs) are defined inductively as the least classes of formal expressions (i.e. of concatenations of primitive symbols) satisfying the following conditions:

(1) 0, 1, and the number variables are nfs.