Raymond Smullyan, 1919–2017
Serious work amid the puzzles and jokes.
When Raymond Smullyan was born, Emanuel Lasker was still the world chess champion. Indeed, of the 16 universally recognized champions, only the first, Wilhelm Steinitz, lived outside Smullyan’s lifetime. Smullyan passed away a week ago Monday at age 97.
Today, Dick and I wish to add some thoughts to the many comments and tributes about Smullyan.
He was known for many things, but his best-known contributions were books with titles like: “What Is the Name of This Book?” Besides their obit in Sunday’s paper, the New York Times ran a sample of puzzles from these books. No doubt many enjoyed the books, and many may have been moved to study “real” logic and mathematics. His book To Mock a Mockingbird dressed up a serious introduction to combinatory logic. This logic is as powerful as normal predicate calculus but has no quantified variables. So making it readable to non-experts is a tribute to Smullyan’s ability to express deep ideas in ways that were so clear.
Smullyan earned his PhD under the guidance of Alonzo Church in 1959 at age 40. When I (Ken) was an undergrad at Princeton, I remember thinking, “gee, that’s old.” Well there’s old and there’s old… As we noted in our profile of him 19 months ago, he was still writing books at a splendid pace at age 95, including a textbook on logic.
Neither of us met him, so we never experienced his tricks and riddles firsthand, but we had impressions on the serious side. Here are some of Dick’s, first.
A Great Book
Smullyan and Melvin Fitting, who was one of his nine PhD students, wrote a wonderful book on set theory: Set Theory and the Continuum Problem (Oxford Logic Guides), 1996.
The blurb at Amazon says:
Set Theory and the Continuum Problem is a novel introduction to set theory … Part I introduces set theory, including basic axioms, development of the natural number system, Zorn’s Lemma and other maximal principles. Part II proves the consistency of the continuum hypothesis and the axiom of choice, with material on collapsing mappings, model-theoretic results, and constructible sets. Part III presents a version of Cohen’s proofs of the independence of the continuum hypothesis and the axiom of choice. It also presents, for the first time in a textbook, the double induction and superinduction principles, and Cowen’s theorem.
The blurb at Amazon says:
A lucid, elegant, and complete survey of set theory [in] three parts… Part One’s focus on axiomatic set theory features nine chapters that examine problems related to size comparisons between infinite sets, basics of class theory, and natural numbers. Additional topics include author Raymond Smullyan’s double induction principle, super induction, ordinal numbers, order isomorphism and transfinite recursion, and the axiom of foundation and cardinals. The six chapters of Part Two address Mostowski-Shepherdson mappings, reflection principles, constructible sets and constructibility, and the continuum hypothesis. The text concludes with a seven-chapter exploration of forcing and independence results.
Wait—are these the same book? Yes they are, and this is one way of saying the book is chock full of content while being self-contained. Neither blurb mentions the part that most grabbed me (Dick). This is their use of modal logic to explain forcing.
Modal logic has extra operators which is usually interpreted as “Necessarily ” and meaning “Possibly “; like the quantifiers and they obey the relation
Saul Kripke codified models as directed graphs whose nodes each have an interpretation of . Then holds at a node if all nodes reachable from satisfy (and hence ), while holds at if holds at some node reachable from . The nodes are “possible worlds.”
What Fitting and Smullyan do is define a translation from set theory to their modal logic such that is valid if and only if . Then the game is to build a node such that every Zermelo-Fraenkel axiom gets a but the translated continuum hypothesis fails in some world reachable from .
One reprinting of the book posed an inadvertent puzzle: many mathematical symbols were omitted. Symbols for set membership, subset, quantifiers, and so on were missing. As one online reviewer noted, “it really does make the book useless.” My copy at least was unaffected.
Rudimentary, My Dear
A week after our 7/28/15 Smullyan post mentioned above, I (Ken again) went with my family to Oregon for vacation. This included a trip to Powell’s Books in Portland, which may be the largest independent bookstore in the world. The math and science sections were larger and more eclectic than any Barnes or college bookstores I’ve seen. There were several copies of the 1961 Princeton Annals paperback edition of Smullyan’s PhD thesis, Theory of Formal Systems, on sale for $20. I felt spurred to buy one and felt it could be useful because of Smullyan’s penchant for combinatorial concreteness.
Sure enough, section B of Chapter IV formulates the rudimentary relations crisply and clearly. Here are Smullyan’s words atop page 78 on their motivation:
As remarked in the Preface, our proof follows novel lines in that all appeal to the traditional number theory devices … in the past—e.g., prime factorization, congruences and the Chinese remainder theorem—are avoided. Thus Gödel’s program of establishing incompleteness, even of first-order theories involving plus and times as their some arithmetical primitives, can, by the methods of this section, be carried out without appeal to number theory.
Simply said: Smullyan avoids all the complicated numerical machinery needed in the usual treatments and makes them—like magic—disappear. The main predicate needed by Smullyan is is a power of , provided is prime. From that he defined a predicate meaning that the binary representation of is the concatenation of those of and . The formal language is still that of logic and numbers but the operations are really manipulating strings. His predicates were able to fulfill all roles for which the class of primitive recursive relations and subclasses involving and had previously been employed.
Smullyan was writing in 1959. Turing machine complexity had not even been defined yet. It transpired later that Smullyan’s class contains nondeterministic logspace and equals the alternating linear time hierarchy. Linear time by itself is annoyingly dependent on machine details, but once you have a couple levels of quantifier alternation the class becomes very robust. Dick employed tricks with alternating linear time in some papers, and such alternation is used to amplify the time hierarchy theorem so that for multitape Turing machines leads to a contradiction higher up. It is also intriguing to see Smullyan write on page 81:
We do not know whether or not all constructive arithmetic attributes are rudimentary. Quine […] has shown that plus and times are first order definable from [concatenation] … but this leaves unanswered the question as to whether plus and times are themselves rudimentary.
The thesis has a footnote saying this had been done for plus, and times follows from remarks above, but whether the predicate is in deterministic linear time remains open. It is likely that Smullyan went through similar concrete thinking as Juris Hartmanis and Richard Stearns when they conjectured no. We wonder if anyone thought to ask Smullyan about this and wish we had.
Our condolences go to his family along with our appreciation for his writings.
Emanuel Lasker philosophized in his 1906 book Struggle about perfect strategists in any walk of life, calling them Macheeides after Greek for “battle species.” An improved edition of Google DeepMind’s AlphaGo probably joined their ranks by beating top human players 60-0 in games played via online servers, not counting one game disrupted by connection failure. The top ranked player, Ke Jie, lost 3 games and landed in the hospital, but desires a 4th try. Where will computer Macheeides strike next?