Hilary Putnam has died. There is a notice on the AMS website and an obituary in the New York Times. Wikipedia has a long entry for Putnam. He was widely known as a philosopher, but he was also an active mathematician. He was a student of Hans Reichenbach, who was also active in both mathematics and philosophy. Putnam has 52 publications in MathSciNet. Putnam also wrote more than a dozen reviews for Mathematical Reviews.
Putnam’s first review was for the paper “Constructive versions of ordinal number classes” by Kreider and Rogers, published in the Transactions of the AMS, 100, 1961 325–369. This was squarely a paper about logic and foundations. His second review was of a paper by Dana Scott on constructing models for arithmetic, which is a mix of model theory and number theory. A little later, Putnam reviewed a paper by Martin Davis, “Applications of recursive function theory to number theory”, from the volume Recursive Function Theory, published in 1962 by the AMS. This paper is a precursor to the paper by Davis, Putnam, and Robinson, The decision problem for exponential diophantine equations, Ann. of Math. (2) 74 1961 425–436, which gives a negative answer to a problem very close to Hilbert’s tenth problem. Putnam reviewed the published version of Julia Robinson‘s lecture at the 1960 ICM on their work. The Hilbert problem was finally put to rest by Yuri Matiyasevich in his article published in Doklady in 1970, which relied on the results of Davis, Putnam, and Robinson. His last review was published in 1965, the same year Putnam joined the faculty at Harvard. The review was of the paper by Pour-El and Howard, “A structural criterion for recursive enumeration without repetition”, published in Zeitschrift für Mathematische Logik und Grundlagen der Mathematik in 1964.
Note: Putnam maintained a blog, Sardonic Comment. The last entry on the blog was posted September 13, 2015.
Here, for your reading pleasure, are the texts of Putnam’s reviews mentioned above.
MR0151396 (27 #1381)
Kreider, Donald L.; Rogers, Hartley, Jr.
Constructive versions of ordinal number classes.
Trans. Amer. Math. Soc. 100 1961 325–369.
02.70 (04.00)
This paper extends the “higher constructive number classes” out to what has been called the first “recursively inaccessible” ordinal. Both the Church-Kleene systems $S_1$ and $S_3$ are extended. In this review only the extension of $S_1$ is described; the extension of $S_3$ is similar except that the predicate $<_0$ is also extended beyond 0. However, all such extensions lose the attractive tree-like structure of $S_3$, even in the third constructive number class, as the authors point out.
As in $S_1$ and $S_3$, 1 is the unique notation for the ordinal 0 and $2^x$ is a notation for $|x|+1$ if $x$ is a notation for an ordinal $|x|$. In addition, if $g$ is a partial recursive function which provides an order-preserving cofinal mapping (o.p.c.m.) from the integers making up a constructive number class (i.e., the integers $x$ such that $|x|<|3^a 5^i|$, for some notation $3^a5^i$) into ${xbig||x|<alpha}$ for some ordinal $alpha$, then $3^a5^b$ is a notation for $alpha$, where (1) $3^a5^i$ is a notation for the least ordinal greater than the number class in question, (2) $i$ is a Gödel number of the identity function, and (3) $b$ is a Gödel number of $g$. “Order-preserving” means that if $|x|<|y|<|3^a5^i|$, then $g(x)$, $g(y)$ are defined and $|g(x)|<|g(y)|$. “Cofinal” means that there are $y,z$ such that $beta<|z|$, $|y|<|3^a5^i|$, and $g(y)=z$, for all ordinals $beta<alpha$. Lastly, if $alpha$ is an ordinal such that notations have already been defined for all ordinals $<alpha$, but there is no general recursive o.p.c.m. from ${xbig||x|<|3^a5^i|}$ into ${xbig||x|<alpha}$ for any $a$ such that $|3^a5^i|<alpha$, then $3^e5^i$ is a notation for $alpha$, where $e$ is any notation for the least ordinal $beta<alpha$ such that no notation for $beta$ has previously been used as an exponent of 3 in a notation $3^a5^i$. In addition, $3^e5^n$ is also a notation for $alpha$ where $n$ is any Gödel number of a function which provides an o.p.c.m. of ${xbig||x|<alpha}$ itself. If no ordinal $beta$ with the property mentioned exists, then no notation for $alpha$ is defined.
It is easily seen that (i) $3cdot 5^i$ is a notation for $omega$; (ii) $3^25^i$ is a notation for $omega_1$ (here the least non-constructive ordinal). Thus (iii) the ordinals $|3^35^i|,|3^45^i|,cdots$ may justifiably be called “(recursive) $omega_2,omega_3,cdots$”. (iv) There are notations $3^a5^b$ for $omega_omega$ (= limit $omega,omega_1,omega_2,cdots$) such that $b$ is the Gödel number of an o.p.c.m. from $omega$ into ${xbig||x|<omega_omega}$ (one such o.p.c.m. is the function $f(x)=3^x5^i$). The ordinals $|3^a5^i|$ are the recursive analogues of regular limit numbers.
If the hyperjump operation is iterated through the system of notations just described in the familiar Davis-Mostowski fashion, only sets in $Sigma_2{}^1capPi_2{}^1$ are obtained. Moreover, the set of all notations defined by the above inductive definition is in $Sigma_2{}^1capPi_2{}^1$, as is the predicate $|x|<|y|$. This is the main result of the paper, and the proof involves an intricate argument of some ten printed pages. However, a short proof of a general theorem which includes this result will appear in a paper by the reviewer [Proc. Amer. Math. Soc. 15 (1964)]. The present paper concludes with a stimulating list of open problems.
MR0152445 (27 #2423)
Scott, Dana
On constructing models for arithmetic. 1961 Infinitistic Methods (Proc. Sympos. Foundations of Math., Warsaw, 1959) pp. 235–255 Pergamon, Oxford; Państwowe Wydawnictwo Naukowe, Warsaw
02.57
This is a general discussion of the difficulties in constructing non-standard models for first-order arithmetic, and in using such models for independence proofs. The following very elegant characterization of a class of non-standard models is the main result: Let $Z$ be the ring of integers, $I$ an infinite set (without loss of generality, a segment of the ordinals), $Z^I$ the ring of functions from $I$ into $Z$, $P$ an ideal in $Z^I$. Then $Z^I/P$ is an (uncountable) non-standard model for arithmetic if and only if $P$ is a non-principal minimal prime ideal. Idea of the proof: For $xin Z^I$, let $e(x)=lambda_y$ ($0$ if $x(y)=0,&,1$ if $x(y)neq 0$). Then $e(x)$ is always a characteristic function. The set of these is just the set $J$ of all idempotents of $Z^I$. $J$ is itself a ring of idempotents, using addition modulo 2, and hence a Boolean algebra. Using the ingenious lemma that a prime ideal $P$ is minimal if and only if $e(P)subseteq P$, the author obtains that $e$ gives a one-to-one correspondence between the minimal prime ideals of $Z^I$ and the maximal ideals of the Boolean algebra $J$ which makes principal ideals correspond to principal ideals. (Note that $J$ is, up to isomorphism, the Boolean algebra of all subsets of $I$.) If $P$ is a minimal non-principal prime ideal, let $frak P$ be the corresponding maximal ideal in $J$. Then $overline{frak P}$ is an ultrafilter, and $Z^I/P$ is easily seen to be isomorphic to the ultrapower $Z^I/overline{frak P}$, and thus (up to isomorphism) an elementary extension of $Z$. Proof of uncountability is not given. The idea of making minimal prime ideals in a ring correspond to complements of ultrafilters is new, and seems important to the reviewer.
Other results: (1) No non-standard model can be finitely generated (using first-order definable functions and elements of the model); (2) There are discretely ordered domains which cannot be extended to models of arithmetic; (3) Let $t$ be an unknown. If $R$ is a formally real domain (0 is not a finite sum of non-zero squares), and every non-negative element in $D$ is a sum of squares, where $Dsubseteq R[t]$, then $Dsubseteq R$. (4) (Tennenbaum’s theorem) No non-standard model is a recursive ring. This paper is recommended for its overall view of the situation, as well as for the main result mentioned above.
MR0151380 (27 #1365)
Davis, Martin
Applications of recursive function theory to number theory. 1962 Proc. Sympos. Pure Math., Vol. V pp. 135–138 American Mathematical Society, Providence, R.I.
02.70 (10.80)
This paper contains an exceptionally clear account of the work done to date trying to establish the recursive unsolvability of Hilbert’s Tenth Problem. That problem is to give an algorithm whereby one can tell, given an arbitrary Diophantine equation, if it has a solution or not. “Diophantine equation” is usually taken in a narrow sense in connection with this problem: an equation of the form $P(x_1,x_2,cdots,x_n)=0$, $P$ a polynomial (i.e., no variable exponents). If we allow variable exponents, we obtain what have been called exponential Diophantine equations. Since the notion of an “algorithm” has been made precise in recursive function theory, it has been shown by Davis, Julia Robinson, and the reviewer that the analogue of Hilbert’s Tenth Problem for exponential Diophantine equations has a negative solution: there is no decision-algorithm, even for the class of all equations of the form: $P(x_1,x_2,cdots,x_n,2^{x_1})=0$, $P$ a polynomial in $n+1$ variables. However, the original Hilbert problem remains open. The author gives a series of unproved number-theoretic hypotheses which imply a negative solution. Among these are: (1) Existence of a polynomial $P(y,z,x_1,cdots,x_n)$ in $n+2$ variables such that $P(y,z,x_1,cdots,x_n)=0$ implies $y<z^z$, but does not imply $y<z^m$ (for all values of $y,z,x_1,cdots,x_n$) when $m=1,2,3,cdots$; (2) That $Ax^3-By^3=C$, $C=1$ or $3$, does not always imply that $x<(AB)^m$ for $m=1,2,3,cdots$.
Let $xi$ be the fundamental unit in the number domain $R(AB^2)^{1/3}$. Nagell has shown that for a solution of $Ax^3-By^3=C$ ($C=1$ or $3$), $$ frac 1{C}(xA^{1/3}-yB^{1/3})=xi^{2^n} tag i $$ for some value of $n$. Hypothesis (2) would be implied by the statement that, for arbitrarily large values of $n$, there exist $A,B,C$ ($C=1$ or $3$), $x,y$ satisfying (1). Unfortunately, Ljunggren showed in 1953 that $n=0$ or $1$ when (1) is satisfied. However, it is not known whether Hypothesis (2) is true or false.
No proofs are given.
MR0168461 (29 #5724)
Robinson, Julia
The undecidability of exponential Diophantine equations. 1962 Logic, Methodology and Philosophy of Science (Proc. 1960 Internat. Congr.) pp. 12–13 Stanford Univ. Press, Stanford, Calif.
02.74 (10.80)
This paper announces the negative solution (obtained by the author jointly with Martin Davis and the reviewer) of the decision problem for exponential Diophantine equations (i.e., Diophantine equations in which exponentiation as well as addition and multiplication is permitted). The result is a consequence of the stronger result, obtained by the above authors, that every recursively enumerable set or relation is exponential Diophantine. Indeed, it has even been shown by Davis, the reviewer and the author that every recursively enumerable set is just the set of non-negative values taken on by an exponential polynomial, and analysis of the proof shows that a function $f(x_1,cdots,x_n,2^y)$ will always suffice, $f$ a polynomial. Whether or not every recursively enumerable set is Diophantine is still unknown; indeed, it is not even known whether or not there is a polynomial $f$ (in $n$ variables) whose non-negative values are just the prime numbers.
MR0168457 (29 #5720)
Pour-El, Marian Boykan; Howard, William A.
A structural criterion for recursive enumeration without repetition.
Z. Math. Logik Grundlagen Math. 10 1964 105–114.
02.70
The authors generalize the result that the recursively enumerable sets are recursively enumerable without repetition (Friedberg) in the following way: any recursively enumerable class $F$ with a partial recursive height function is recursively enumerable without repetition. By a height function is meant a function $h$ defined on the finite subsets of members of $F$ with the properties: (1) monotonicity: if $Asubseteq B$, then $h(A)leq h(B)$; (2) convergence (the authors call this “the ascending chain condition”): if $A_1subseteq A_2subseteq A_3subseteqcdots$ is an ascending sequence of finite subsets of a fixed member of $F$, then the associated sequence of heights $h(A_1),h(A_2),cdots$ eventually becomes constant; (3) unboundedness: for every finite subset $A$ of a member of $F$, there exists a finite subset $B$, not necessarily of the same member of $F$, such that $Asubset B$, $h(A)<h(B)$.
The proof is by a complicated “priority” argument. In following the proof, the following remarks may be of help (the authors give little motivation). The first two conditions enable one to associate a “height” with each member of $F$, namely, if $Sin F$ is finite, “height” $(S)=h(S)$; if $Sin F$ is infinite, “height”$(S)=max(h(S_i))$, $S_i$ a finite subset of $S$. It can easily be proved from (1) and (2) that this maximum exists. Note that the “height” of $Sin F$ can be successively approximated from below by taking finite subsets, and that the approximations must eventually all be correct. The condition (3) implies that a finite subset of any member of $F$ is also a finite subset of some member of $F$ with “height” as great as one pleases. These facts allow one to modify Friedberg’s original proof to obtain the theorem.
Several corollaries are obtained by the authors, including Friedberg’s original result.
