Serious work amid the puzzles and jokes.

 Amazon source

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 ${\Box\phi}$ which is usually interpreted as “Necessarily ${\phi}$” and ${\diamond\phi}$ meaning “Possibly ${\phi}$“; like the quantifiers ${\forall}$ and ${\exists}$ they obey the relation

$\displaystyle \Box \phi \longleftrightarrow \neg\diamond\neg\phi.$

Saul Kripke codified models as directed graphs whose nodes each have an interpretation of ${\phi}$. Then ${\Box\phi}$ holds at a node ${u}$ if all nodes reachable from ${u}$ satisfy ${\phi}$ (and hence ${\Box\phi}$), while ${\diamond\phi}$ holds at ${u}$ if ${\phi}$ holds at some node reachable from ${u}$. The nodes are “possible worlds.”

What Fitting and Smullyan do is define a translation ${\phi \rightarrow \phi'}$ from set theory to their modal logic such that ${\phi}$ is valid if and only if ${\Box\phi'}$. Then the game is to build a node ${u}$ such that every Zermelo-Fraenkel axiom gets a ${\Box}$ but the translated continuum hypothesis fails in some world reachable from ${u}$.

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 ${R(p,x) =}$ ${x}$ is a power of ${p}$, provided ${p}$ is prime. From that he defined a predicate ${C(x,y,z)}$ meaning that the binary representation of ${z}$ is the concatenation of those of ${x}$ and ${y}$. 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 ${\times}$ 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 ${\mathsf{RUD}}$ 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 ${\mathsf{NLIN = DLIN}}$ 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 ${x*y = z}$ 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.

## Open Problems

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?

February 14, 2017 9:02 pm

When I was only 6 years old, I got “What Is the Name of This Book” (Chinese version). I was really into those logic problems, like who is saying truth and who is lying. And I even tried to understand the rough idea of Godel’s incompleteness theorems. I think that book inspired my interests in math.

I’m so sad that Smullyan passed away. R.I.P.

2. February 15, 2017 10:08 am

The book that struck the deepest chord with me was To Mock a Mockingbird : And Other Logic Puzzles Including an Amazing Adventure in Combinatory Logic, Alfred A. Knopf, New York, NY, 1985.

I once attended a conference at Michigan State on “Creativity in Logic and Math” or some such theme and there was another conference going on down the hall on Birdcalls — seriously — complete with sound effects all afternoon. It made me wonder a little …

At any rate, I found much study there —

February 16, 2017 2:55 pm

The book with Fitting is in the Oxford Logic Guides series. Smullyan had three other books in that series, all quite remarkable.

The connection with modal logic was very well known at the time, but not really written up. Cohen’s original proof relied on intuitionistic logic, which is very close to modal logic. Scott redid Cohen’s proof to use classical logic, and we all follow Scott when forcing, while Kripke exploited Cohen’s proof to introduce his models which provided the first philosophically natural proofs of completeness theorems for intuitionistic and modal logic. Fitting then wrote a short book on forcing and intuitionistic logic (available for free download, somewhat unreadable in my opinion). The S&F book is a major expansion and translation of Fitting’s book into modal logic. While readable, I would not recommend it as an introduction to forcing. There’s something bizarre about forcing, whereby the intuitively plausible approaches (e.g., Boolean-valued models) are much more difficult to learn, verify, and apply than the standard, but a priori less intuitive, poset approach.

As to the base-p approach to encoding sequences and concatenation in Peano arithmetic, note that this actually does involve approximately the same amount of number theory as the classical coding. The difference is that mathematically minded readers all learn (without proofs) the facts of life regarding base-p expansions very early on, but typically do not learn the Chinese remainder theorem until grad school, and then only if you choose to learn it. (Similarly, the Cantor diagonalization argument, when phrased in terms of decimal expansions, seems completely trivial when compared to other proofs of the uncountability of the real line, but only because we all learn about decimal expansions at an early age.)

It’s a bit of a mystery as to who devised base-p encoding. Smullyan credits it to X, X credits it to Y, and Y credits it to Smullyan. (Unfortunately, I do not remember who X and Y are, I think one of them was Quine. I recall that Smullyan mentioned this issue in his Gödel’s Incompleteness Theorems.)