A lesser-known but quite interesting contribution of Hilary Putnam to mathematical logic concerns the complexity of models of schemata of the predicate calculus, that is, first-order quantificational schemata. To frame his results, let me start by recalling what might be dubbed the Hilbert–Bernays Theorem, namely, that any satisfiable schema of quantification theory has a model over \(\mathbb {N}\) (or a finite subset of \(\mathbb {N}\)) in which the predicate letters are interpreted as \(\Delta _2\) relations. (A \(\Delta _2\) relation is one that can be defined as both a \(\Pi _2\) relation \(\forall x \exists y Q\) and a \(\Sigma _2\) relation \(\exists x \forall y R\), where Q and R are recursive relations.) The proof is sketched in Hilbert and Bernays (1939), pp. 243–252; it proceeds by arithmetizing Gödel’s completeness proof (1930). The argument is elaborated rigorously in Kleene (1952) , pp. 389–394. Kleene’s proof is very complex, but a much simpler one is now available (Ebbs and Goldfarb 2018).

In the 1950s, there was attention to the question of whether the Hilbert–Bernays Theorem could be improved: could one always find number-theoretic interpretations of lesser complexity than \(\Delta _2\)? Kreisel (1953) and Mostowski (1953) independently showed that there were satisfiable schemata of quantification theory that could not be satisfied over \(\mathbb {N}\) with recursive relations, that is, had no recursive models. Those proofs used set-theoretic means, but in Mostowski (1955) gave a more elementary argument that used only recursion-theoretic concepts.

Putnam’s first result (1957) strengthened this: a restriction to relations that are either \(\Sigma _1\) or \(\Pi _1\) would also not suffice. (\(\Sigma _1\) relations are existential quantifications of recursive relations, usually called “recursively enumerable” or “computably enumerable”; \(\Pi _1\) relations are the complements of \(\Sigma _1\) relations, and sometimes called “co-r.e”. or “co-c.e”.) The argument is simple and elegant. Putnam starts with a schema that has no recursive model, and constructs from it a schema that cannot have a model when its predicate is either \(\Sigma _1\) or \(\Pi _1\). Assuming the predicates of the given schema that has no recursive models are dyadic \(P_1, \ldots , P_n\), first introduce new constants \(a_1, \ldots a_n, b_1, \ldots b_n\) and a triadic predicate Q, then replace each occurrence of \(P_i(x,y)\) with \(Q(x,y,a_i)\), and conjoin the resulting formula with

$$\forall x \forall y\left( \bigwedge _i Q(x,y,a_i) \leftrightarrow \lnot Q(x,y,b_i)\right) $$

Since a \(\Sigma _1\) set with \(\Sigma _1\) complement is recursive, it follows that if Q is interpreted as either a \(\Sigma _1\) or \(\Pi _1\) relation, then it must in fact be recursive, which would then yield recursive interpretations of \(P_1, \ldots , P_n\). So if the given schema has no recursive models, then the new schema cannot have a model with Q interpreted as either \(\Sigma _1\) or \(\Pi _1\).

Putnam obtained his other, more important, result a few years later; it is published as (1965) . This is a positive theorem: he improved the Hilbert–Bernays Theorem by showing that a model could always be obtained using relations that were boolean combinations of \(\Sigma _1\) relations. The notation he used for this class of relations was \(\Sigma _{1}^*\). This yields a sharp characterization in terms of the Kleene arithmetical hierarchy: one-quantifier forms do not suffice, but boolean combinations of one-quantifier forms do.

As we shall see, Putnam’s argument, unlike the original Hilbert–Bernays Theorem, applies only to quantification theory without identity, that is, what is called the “restricted functional calculus” in Hilbert and Ackermann (1928) .

Putnam’s argument is quite ingenious. Here I present a streamlined version in more modern notation. We are given a satisfiable schema S. In the interest of simplicity of exposition, Putnam invoked a well-known reduction due originally to Herbrand (1931), which allows him to assume that S contains only one predicate letter P (the method is a generalization of the reduction above of several dyadic predicate letters to one triadic letter). Suppose P is n-adic.

The first lemma needed for Putnam’s proof is comes from the basic model theory of quantification theory. Suppose \(\mathfrak {M}\) is a model for a schema with universe \(\mathbb {N}\), and suppose \(\varphi : \mathbb {N} \rightarrow \mathbb {N}\) is onto. Define \(\mathfrak {N}\) also with universe \(\mathbb {N}\) so that the interpretation of each predicate letter is the preimage under \(\varphi \) of its interpretation in \(\mathfrak {M}\). Then \(\mathfrak {N}\) is also a model for the schema. This elementary fact is easily shown by induction on the logical complexity of the schema. In the case we are considering, in which the schema contains one predicate letter P, the preimage interpretation is this: \(P^{\mathfrak {N}}\) holds of an n-tuple \((i_1, \ldots i_n)\) iff \(P^{\mathfrak {M}}\) holds of \((\varphi (i_1), \ldots \varphi (i_n))\). That \(\varphi \) is required only to be onto and not also one-one is what limits the scope of the lemma to quantification theory without identity; if “\(=\)” were allowed and \(\varphi \) were not one-one, the lemma would fail.

The ingenuity in the proof lies in a second lemma. Putnam started by showing that an n-adic number-theoretic relation R is \(\Delta _2\) iff there is an \((n+1)\)-adic recursive function f such that \(R(i_1,\ldots ,i_n)\) holds iff the limit of \(f(i_1,\ldots ,i_n,y)\) as y goes to infinity is 1, and does not hold if that limit is 0. He called such a function a “trial and error function”, although that name has not stuck. Nowadays, this result is considered a standard one in recursion theory. In fact it was already known before Putnam’s paper, as it follows quickly from Shoenfield (1959). But in fact this result is not necessary for his theorem, because the simplified proof of the Hilbert–Bernays Theorem mentioned above establishes first that the predicate letters of any satisfiable quantificational schema can be interpreted as limits of trial-and-error functions, and only subsequently infers from this that they are \(\Delta _2\). Thus one can simply start with those functions and avoid the detour through \(\Delta _2\) (see Ebbs and Goldfarb 2018).

Now if f is an \((n+1)\)-adic trial-and-error function, then for all \(i_1, \ldots i_n\) there is some k such that \(f(i_1,\ldots , i_n,y)\) changes its value at most k times as y increases. Putnam’s innovation was to reverse the quantifiers, that is, to consider recursive functions f with the property that there exists a k such that \(f(i_1,\ldots , i_n,y)\) changes its value at most k times, no matter what \(i_1,\ldots i_n\) are. Putnam called these “k-trial” functions, and the n-adic relations they define in their limit, “k-trial predicates”. Several years later, k-trial functions also found application in the theory of tilings of the plane; see Hanf (1974).

Putnam then noted that, for any k, k-trial relations are boolean combinations of r.e. relations. The boolean complexity of the relation is straightforwardly dependent on k. For example, suppose g(i, j, y) is a 2-trial function. The relation R(i, j) that it defines in the limit can be specified thus: there are two numbers y at which g(i, j, y) changes value, and at the greater of them the value is 1; or there aren’t two numbers y such that g(i, j, y) changes value at y but there is one number y at which g(i, j, y) changes value, and then its value is 1, or there is no number y at which g(i, j, y) changes value, and g(i, j, 0) is 1. Each of these clauses can be expressed as either an r.e. relation or a co-re. relation.

Now let \(\mathfrak {M}\) be a model for S for which \(P^\mathfrak {M}\) is defined as the limit of a trial-and-error function f. Given the above, it suffices to find an onto mapping \(\varphi \) such that the \(\varphi \)-preimage of \(P^\mathfrak {M}\) can be defined as the limit of a k-trial function for some k.

For any \(i_1, \ldots , i_n\), an \((i_1, \ldots , i_n)\)-modulus is any number b such that \(f(i_1, \ldots , i_n,b) = f(i_1, \ldots , i_n,y)\) for all \(y \ge b\). Since \(f(i_1, \ldots , i_n, y)\) has a limit as y goes to infinity, there always exists an \((i_1, \ldots , i_n)\)-modulus. For any i, an i-modulus is a number b that is an \(i_1, \ldots ,i_n\)-modulus for all \(i_1, \ldots , i_n \le i\). Thus for every i there exists an i-modulus.

Let \(\langle i,j \rangle \) be a standard primitive recursive one-one onto pairing function. Let \(\varphi \) be the one-place function such that, for all i and b, \(\varphi (\langle i,b \rangle ) = i\) if b is an i-modulus, and = 0 if not. It follows that \(\varphi \) is onto.

Now let \(h(i,b,y) = i\) if for all z, \(b \le z \le y\) and all \(i_1,\ldots ,i_n \le i\),

$$ f(i_1,\ldots ,i_n,b) = f(i_1,\ldots ,i_n,z)$$

otherwise let \(h(i,b,y) = 0\). Note that if \(h(i,b,y) = 0\) then \(h(i,b,y') = 0\) for all \(y' \ge y\). Thus for \(i \ne 0\), h(i, b, y) can change its value for increasing y at most only once: from i to 0. Moreover, for \(i \ne 0\), \(h(i,b,y) = i\) for every y iff b is an i-modulus. (For \(i = 0\), h(i, b, y) is always 0.) Hence

$$\varphi (\langle i,b \rangle ) = \lim _{y \rightarrow \infty } h(i,b,y)$$

We now define an \((n+1)\)-place function g, which we show to be a n-trial function and to define, in its limit, the \(\varphi \)-preimage of \(P^\mathfrak {M}\). Let \(b_0\) be any 0-modulus, that is, any number such that, for all \(y \ge b_0, f(0, \ldots , 0,b_0) = f(0, \ldots , 0,y)\). Let \(i_1, \ldots , i_n\) and \(b_1, \ldots , b_n\) be any integers. Then let

$$g(\langle i_1,b_1 \rangle , \ldots , \langle i_n,b_n \rangle , y) = f((h(i_1,b_1,y), \ldots , h(i_n,b_n,y), b_p)$$

where \(p=0\) if \(h(i_m,b_m,y) = 0\) for each \(m, 1 \le m \le n\); and p is such that \(i_p\) is the largest among \(i_1, \ldots , i_n\) for which \(h(i_p,b_p,y) \ne 0\) otherwise.

Note first that g is an n-trial function. For as noted above, h(i, b, y) can change its value at most once, from nonzero to zero. Hence the arguments of f on the righthand side of the definition of g can change their values at most n times.

Moreover, g defines, in the limit, just the \(\varphi \)-preimage of \(P^\mathfrak {M}\). That is, as y goes to infinity the limit of \(g(\langle i_1,b_1 \rangle , \ldots \langle i_1,b_1 \rangle , y)\) is the same as that of \(f(\varphi (\langle i_1,b_1 \rangle ), \ldots , \varphi \langle i_1,b_1 \rangle ),y)\). For let y be any number large enough that, for all \(y' \ge y\), \(h(i_m,b_m,y') = \varphi (\langle i_m,b_m \rangle )\) for each \(m \le n\). Then, for all \(y' \ge y\), \(g(\langle i_1,b_1 \rangle , \ldots \langle i_n,b_n \rangle , y') = f(\varphi (\langle i_1,b_1 \rangle ), \ldots , \varphi (\langle i_n,b_n \rangle ),b_p)\), where \(p = 0\) if all the \(\varphi (\langle i_m,b_m \rangle )\) are 0, and otherwise p is such that \(i_p\) is the largest among \(i_1, \ldots , i_n\) such that \(\varphi \langle i_p,b_p \rangle ) \ne 0\). In either case \(b_p\) is an i-modulus for some i such that \(\varphi (\langle i_m,b_m \rangle ) \le i\) for each m, so that \(f(\varphi (\langle i_1,b_1 \rangle ), \ldots , \varphi (\langle i_n,b_n \rangle ),b_p) = f(\varphi (\langle i_1,b_1 \rangle ), \ldots , \varphi (\langle i_n,b_n \rangle ),y')\) for all \(y' \ge b_p\); hence the two limits are identical. This completes the proof.

Since g is an n-trial function, and the boolean complexity of the defined predicate depends only on n, we see that the boolean complexity of the \(\Sigma _1^*\) relations depends only on the number of argument places of the predicate letter and not on anything further about the logical structure of the schema S.

As mentioned above, this proof applies only to quantification theory without identity. Strictly speaking, the theorem is false for quantification theory with identity, since there are schemata which have only finite models, and hence no model over all of \(\mathbb {N}\). If we restrict attention to those schemata that do have infinite models, then it is an open question as to whether the result holds.

Putnam’s theorem is not widely known, I think, for two reasons. First, due to the growth of model theory, by the late 1960s logicians who studied quantification theory began taking quantification theory with identity as a more basic object of study than the “restricted functional calculus”. (To see the shift, one need only compare the introduction of quantification theory in Kleene (1952) or Church (1956) with that in Enderton (1972).) Second, advances in recursion theory caused more emphasis to be put on Turing degree rather than position in the arithmetical hierarchy as a measure of complexity. Here the crucial result was the Low Basis Theorem of Jockusch and Soare (1972). This theorem states that any recursive infinite binary tree has an infinite path whose jump is Turing equivalent to K. By applying the same arithmetization of Gödel’s completeness proof as Hilbert and Bernays had done, this yields – for quantification theory with identity – the same Turing degree for the interpretations of predicate letters in models over \(\mathbb {N}\). This characterization lies athwart Putnam’s characterization, since there are low sets that are \(\Delta _2\) but not \(\Sigma _1^*\).

Nonetheless, I believe, there are open problems stemming from his result that are worth investigating. First, as mentioned above, there is the question of whether Putnam’s result can be extended to quantification theory with identity. His technique certainly cannot be, and I am doubtful that the result holds there. It should, however, be settled one way or the other. Second, because the function \(\varphi \) used in the proof is ordinarily not recursive, one cannot extract from the Low Basis Theorem information about the Turing degree of the interpretation. Hence, the question remains: if we restrict ourselves to \(\Sigma _{1}^*\) interpretations, are there schemata which require relations that are Turing equivalent to K? Finally, in the model constructed for the Hilbert–Bernays Theorem, even though the predicates are not interpreted recursively, there are recursive Skolem functions (this is built in to Gödel’s completeness proof) . This is not preserved by \(\varphi \)-preimages, but then the question remains as to whether one can obtain recursive Skolem functions in \(\Sigma _1^*\) models, and if not, how great their computational complexity might have to be.Footnote 1