2 Autograph letters signed to Martin Davis, plus file copies of Davis's replies.

Publisher Information: Madison, WI: 1983.

Rosser, J. Barkley (1907-89). Two autograph letters signed to Martin Davis (1928-2023), together with Davis’s file copies of his replies. 6pp. on 4 sheets total. 3 January – 23 February 1983. 282 x 220 mm. Light creasing but very good.

From mathematical logician J. Barkley Rosser, known for the Kleene-Rosser paradox showing that Alonzo Church’s original lambda-calculus was inconsistent; also for his part in the Church-Rosser theorem in lambda-calculus and for his proof of Rosser’s theorem in number theory. His correspondent was Martin Davis, a mathematician and logician who made important contributions to computability theory. Davis’s work on Hilbert’s tenth problem—asking for a general algorithm to decide the solvability of Diophantine equations—led to the Matiyasevich-Robinson-Davis-Putman (MRDP) theorem implying that a solution to this problem is impossible.

The correspondence offered here concerns Martin Davis’s paper, “Why Gödel didn’t have Church’s Thesis” (Information and Control 54 [1982]: 3-24), a historical paper outlining the development of -definability and recursive function theory by Gödel, Church, Turing, Kleene, Post and others in the 1930s. Rosser, who had received a typescript version of Davis’s paper from Kleene, objected to some of the paper’s statements:

"Steve Kleene lent me a copy of your article . . . Imagine my surprise when I read your Footnote 4 (on p. 30 of the typescript I have). You include me among the logicians who have seriously proposed a system of logic that later turned out to be inconsistent! What system do you have in mind? I find it hard to believe that anyone who found an inconsistency in a system which I had seriously proposed would fail to inform me of the matter . . ."

Davis replied:

"The system to which I referred is NF+AC which you very “seriously proposed” in your well known book Logic for Mathematicians. As I am sure you know very well, this system was proved inconsistent by Specker many years ago . . ."

Rosser countered that “If you look on p. 512 of ‘Logic for Mathematicians,’ you will find that I did NOT propose NF+AC as a foundation for mathematics . . . Since I explicitly refrained from assuming AC, and stressed repeatedly that many uses of AC can be replaced by weaker versions or avoided altogether, it is disheartening to be accused of espousing AC . . .” Several weeks later Davis responded: “I answered your first letter quite hastily, not wanting to leave it while I was abroad . . . you are quite right to object that you had never proposed NF+AC as a ‘foundation for mathematics’ . . . Nevertheless, I hold to my original statement that placed your name on the ‘honor roll’ of those ‘seriously proposing’ systems of symbolic logic that later turned out to be inconsistent . . ..

Book Id: 51698

Price: $1,500.00

See all items by