Raymond Smullyan

Proof by legerdemain

Peli Grietzer shared a blog post by David Auerbach on Twitter yesterday containing the following lovely quote about Smullyan and Carnap:

I particularly delighted in playing tricks on the philosopher Rudolf Carnap; he was the perfect audience! (Most scientists and mathematicians are; they are so honest themselves ‘that they have great difficulty in seeing through the deceptions of others.) After one particular trick, Carnap said, “Nohhhh! I didn’t think that could happen in any possible world, let alone this one!”


In item # 249 of my book of logic puzzles titled What Is the Name of This Book?, I describe an infallible method of proving anything whatsoever. Only a magician is capable of employing the method, however. I once used it on Rudolf Carnap to prove the existence of God.


“Here you see a red card,” I said to Professor Carnap as I removed a card from the deck. “I place it face down in your palm. Now, you know that a false proposition implies any proposition. Therefore, if this card were black, then God would exist. Do you agree?”


“Oh, certainly,” replied Carnap, “if the card were black, then God would exist.”


“Very good,” I said as I turned over the card. “As you see, the card is black. Therefore, God exists!”


“Ah, yes!” replied Carnap in a philosophical tone. “Proof by legerdemain! Same as the theologians use!”


Raymond Smullyan, 5000 BC and Other Philosophical Fantasies. New York: St. Martin’s Press, 1983, p. 24.

See Auerbach’s post for more Carnap and Smullyan anecdotes.

Why φ?

Yesterday, @gravbeast asked on Twitter,

Does anyone know why we traditionally use Greek phi and psi for metasyntactic variables representing arbitrary logic formulas? Is it just because ‘formula’ begins with an ‘f’ sound? And chi was being used for other things?

Although Whitehead and Russell already used φ and ψ for propositional functions, the convention of using them specifically as meta-variables for formulas seems to go back to Quine’s 1940 Mathematical Logic. Quine used μ, ν as metavariables for arbitrary expressions, and reserved α, β, γ for variables, ξ, η, σ for terms, and φ, χ, ψ for statement. (ε, ι, λ had special roles.) Why φ for statements? Who knows. Perhaps simply because Whitehead and Russell used it for propositional functions in Principia? Or because “p” for “proposition” was entrenched, and in classic Greek, φ was a p sound, not f?

The most common alternative in use at the time was the use of Fraktur letters, e.g., \(\mathfrak{A}\) as a metavariable for formulas, and A as a formula variable; x as a bound variable and \(\mathfrak{x}\) as a metavariable for bound variables. This was the convention in the Hilbert school, also followed by Carnap. Kleene later used script letters for metavariables and upright roman type for the corresponding symbols of the object language. But indicating the difference by different fonts is perhaps not ideal, and Fraktur may not have been the most appealing choice anyway, both because it was the 1940s and because the type was probably not available in American print shops.

Logic Colloquium, Udine

The European Summer Meeting of the Association of Symbolic Logic will be in Udine, just north of Venice, July 23-28. Abstracts for contributed talks are due on April 27. Student members of the ASL are eligible for travel grants!



The Significance of Philosophy to Mathematics

If you wanted to explain how philosophy has been important to mathematics, and why it can and should continue to be, it would be hard to do it better than Jeremy Avigad. In this beautiful plea for a mathematically relevant philosophy of mathematics disguised as a book review he writes:

Throughout the centuries, there has been considerable interaction between philosophy and mathematics, with no sharp line dividing the two. René Descartes encouraged a fundamental mathematization of the sciences and laid the philosophical groundwork to support it, thereby launching modern science and modern philosophy in one fell swoop. In his time, Leibniz was best known for metaphysical views that he derived from his unpublished work in logic. Seventeenth-century scientists were known as natural philosophers; Newton’s theory of gravitation, positing action at a distance, upended Boyle’s mechanical philosophy; and early modern philosophy, and philosophy ever since, has had to deal with the problem of how, and to what extent, mathematical models can explain physical phenomena. Statistics emerged as a response to skeptical concerns raised by the philosopher David Hume as to how we draw reliable conclusions from regularities that we observe. Laplace’s Essai philosophique sur la probabilités, a philosophical exploration of the nature of probability, served as an introduction to his monumental mathematical work, Théorie analytique des probabilités.


In these examples, the influence runs in both directions, with mathematical and scientific advances informing philosophical work, and the converse. Riemann’s revolutionary Habilitation lecture of 1854, Über die Hypothesen welche der Geometrie zu Grunde liegen (“On the hypotheses that lie at the foundations of geometry”), was influenced by his reading of the neo-Kantian philosopher Herbart. Gottlob Frege, the founder of analytic philosophy, was a professor of mathematics in Jena who wrote his doctoral dissertation on the representation of ideal elements in projective geometry. Late nineteenth-century mathematical developments, which came to a head in the early twentieth-century crisis of foundations, provoked strong reactions from all the leading figures in mathematics: Dedekind, Kronecker, Cantor, Hilbert, Poincaré, Hadamard, Borel, Lebesgue, Brouwer, Weyl, and von Neumann all weighed in on the sweeping changes that were taking place, drawing on fundamentally philosophical positions to support their views. Bertrand Russell and G. H. Hardy exchanged letters on logic, set theory, and the foundations of mathematics. F. P. Ramsey’s contributions to combinatorics, probability, and economics played a part in his philosophical theories of knowledge, rationality, and the foundations of mathematics. Alan Turing was an active participant in Wittgenstein’s 1939 lectures on the foundations of mathematics and brought his theory of computability to bear on problems in the philosophy of mind and the foundations of mathematics.

Go and read the whole thing, please. And feel free to suggest other examples!

The book reviewed is Proof and Other Dilemmas: Mathematics and Philosophy, Bonnie Gold and Roger A. Simons, eds., Mathematical Association of America, 2008

[Photo: Bertrand Russell and G. H. Hardy as portrayed by Jeremy Northam and Jeremy Irons in The Man Who Knew Infinity, via MovieStillsDB]

Ptolemaic Astronomy

Working on the chapters on counterfactual conditionals for the Open Logic Project, I needed some illustrations for David Lewis’s sphere models, which he jokingly called “Ptolemaic astronomy.” Since Franz Berto joked that this should just require \usepackage{ptolemaicastronomy}, I wrote some LaTeX macros to make this easier using TikZ. You can download ptolemaicastronomy.sty (it should work independently of OLP); examples are in the OLP chapter on minimal change semantics (PDF, source).

(This will probably interest a total of two people other than me so I didn’t spend much time documenting it, but if you want to use it and need help just comment here.)

Update: it’s now in its own github repository and properly documented.

A New University of Calgary LaTeX Thesis Class based on Memoir

The University of Calgary provides a LaTeX thesis class on its website. That class is based on the original thesis class, modified over the years to keep up with changes to the thesis guidelines of the Faculty of Graduate studies. It produces atrocious results. Chapter headings are not aligned properly. Margins are set to 1 inch on all sides, which results in unreadably long lines of text. The template provided sets the typeface to Times New Roman. Urgh.  A better class (by Mark Girard) is already available, which however also sets the margins to 1 inch. FGS no longer requires that the margins be exactly 1 inch, just that they are at a minimum 1 inch. So we are no longer forced to produce that atrocious page layout.

I made a new thesis class. It’s based on memoir, which provides some nice functionality to compute an attractive page layout. By default, the class sets the thesis halfspaced, 11 point type, and with about 65 characters per line. This produces a page approximating a nicely laid out book page.  The manuscript class option sets it up for 12 point, double spaced, with 72 characters per line, and 25 lines per page. That’s still readable, but gives you extra space between the lines for annotations and editing marks, and wider margins. There are also class options to load some decent typefaces (palatino, utopia, garamond, libertine, and, ok, times).

Once upon a time, theses were typed on a typewriter and submitted to the examination committee in hardcopy. Typewriter fonts are “monospaced,” i.e., every character takes the same amount of space. “Elite” typewriters would print 12 characters per inch, or 72 characters per 6 inch line, and “Pica” typewriters 10 cpi, or 60 characters per line. Typewriters fit 6 lines into a vertical inch, or 25 lines per double-spaced page. A word is on average 5 characters long, hence we get about 250 words per manuscript page.

Noone uses typewriters anymore to write theses, but thesis style guidelines are still a holdover from the time we did. The guidelines still require that theses be halfspaced or double spaced. But of course they allow use of word processing software. Those don’t use monospaced typewriter fonts, and the recommended typefaces such as Times Roman are much more narrow and proportionally spaced. That means even with 12 point type, a 6” line now contains 89 characters on average, rather than 60. (Chris Pearson has estimated “character constants” for various typefaces which you can use to estimate the average number of characters per inch in various type sizes. For Times New Roman, the factor is 2.48. At a line length of 6”, i.e., 432 pt, and 12 pt type that gives 432 × (2.48/12)=89.28 characters per line. With minimal margins of 1” you get 96 characters per line.)

Applying typewriter rules to electronically typeset manuscripts results in lines that are very long—and that means they are hard to read. Ideally, there should be anywhere between 50 and 75 characters per line, and 66 characters is widely considered ideal. Readability is a virtue you want your thesis to have. And the thesis guidelines, thankfully, no longer set the margins, but only require minimum margins of 1” on all sides.


Modal Logic! Propositional Logic! Tableaux!

Lots of new stuff in the Open Logic repository! I’m teaching modal logic this term, and my ambitious goal is to have, by the end of term or soon thereafter, another nicely organized and typeset open textbook on modal logic. The working title is Boxes and Diamonds, and you can check out what’s there so far on the builds site. This project of course required new material on modal logic.  So far this consists in revised and expanded notes by our dear late colleague Aldo Antonelli. These now live in content/normal-modal-logic and cover relational models for normal modal logics, frame correspondence, derivations, canonical models, and filtrations. So that’s one big exciting addition. Since the OLP didn’t cover propositional logic separately, I just now added that part as well so I can include it as review chapters. There’s a short chapter on truth-value semantics in propositional-logic/syntax-and-semantics. However, all the proof systems and completeness for them are covered as well. I didn’t write anything new for those, but rather made the respective sections for first-order logic flexible. OLP now has an FOL “tag”: if FOL is set to true, and you compile the chapter on the sequent calculus, say, you get the full first-order version with soundness proved relative to first-order structures. If FOL is set to false, the rules for the quantifiers and identity are omitted, and soundness is proved relative to propositional valuations. The same goes for the completeness theorem: with FOL set to false, it leaves out the Henkin construction and constructs a valuation from a complete consistent set rather than a term model from a saturated complete consistent set. This works fine if you need only one or the other; if you want both, you’ll currently get a lot of repetition. I hope to add code so that you can first compile without FOL then with, and the second pass will refer to the text produced by the first pass rather than do everything from scratch. You can compare the two versions in the complete PDF. Proofs systems for modal logics are tricky; and many systems don’t have nice, say, natural deduction systems. The tableau method, however, works very nicely and uniformly. The OLP didn’t have a chapter on tableaux, so this motivated me to add that as well. Tableaux are also often covered in intro logic courses (often called “truth trees”), so having them as a proof system included has the added advantage of tying in better with introductory logic material. I opted for prefixed tableaux (true and false are explicitly labelled, rather than implicit in negated and unnegated formulas), since that lends itself more easily to a comparison with the sequent calculus, but also because it extends directly to many-valued logics. The material on tableaux lives in first-order-logic/tableaux. Thanks to Clea Rees for the the prooftrees package, which made it much easier to typeset the tableaux, and to Alex Kocurek for his tips on doing modal diagrams in Tikz.

Logic Courseware?

Kit Fine asked me for suggestions of online logic materials that have some interactive component, i.e., ways for students to build truth-tables, evaluate arguments, translate sentences, build models, and do derivations; ideally it would not just provide feedback to the student but also grade problems and tests. There is of course Barwise & Etchemendy’s Language, Proof, and Logic, which comes with software to do these things very well and also has a grading service. But are there things that are free, preferably online, preferably open source?

  • First we have David Kaplan’s Logic 2010. It’s written in Java, runs on Windows and Mac, is free but not open source, and has a free online grading component. It goes with Terry Parson’s An Exposition of Symbolic Logic, which is also free. To use the software and grading service, you’d have to make arrangements with David. The text does propositional and first-order logic including models and Kalish-Montague derivations. I haven’t tried the software, but it’s used in a number of places.
    [Free software Free book Online ✗ Open source ✗]
  • UPDATE: Carnap is an open source framework for writing webapps for teaching logic written by Graham Leach-Krouse and Jake Ehrlich. It comes with a (free, but not openly licensed) online book, and currently can check truth tables, translations, and Kalish-Montague derivations (and they are working on first-order models). Students can have accounts and submit exercises. The software is written in Haskell and is open-source (see Github). It’s used at Kansas Sate and the University of Birmingham.
    [Free software Free book Online Open source ]
  • Kevin Klement is teaching logic from the (free) book by Hardegree, Symbolic Logic: A First Course. (There’s a newer version that doesn’t seem to be freely available.) He has an online component (exercises and practice exams) with multiple-choice questions, truth tables, translations, and Fitch-style derivations. I’m not sure if the backend code for all of this is available and could be adapted to your own needs. He has provided a version of the proof checker that works with the Cambridge and Calgary versions of forall x, and that code is open source, however. I’m not sure if it’s possible to add the functionality he has on the UMass site for saving student work. Neither the book nor the online exercises cover models for first-order logic.
    [Free software ✓ Free book ✓ Online ✓ Open source ?]
  • The Logic Daemon by Colin Allen and Chris Menzel accompanies Allen and Michael Hand’s Logic Primer. It can check truth-tables, models, and Suppes-Lemmon derivations, and generate quizzes. The interface is basic but the functionality is extensive. There doesn’t seem to be a grading option, however. Software seems to be written in Perl, I didn’t see the source code available.
    [Free software ✓ Free book ✗ Online ✓ Open source ✗]
  • Then there is Ray Jennings and Nicole Friedrich’s Project Ara, which includes Simon, a logic tutor, and Simon Says, a grading program. The textbook is Proof and Consequence, published by Broadview (ie, not free). It does truth-tables, translations, and Suppes-style derivations, and also no models. It requires installing software on your own computer, but it’s free and runs on Windows, Mac, and Linux. The software is free but not open source. I haven’t tried it out. (That website though!)
    [Free software ✓ Free book ✗ Online ✗ Open source ✗]
  • Wilfried Sieg’s group has developed AProS, which includes proof and counterexample construction tools. I don’t think these are openly available, however. It’s used in Logic & Proofs, offered through CMU’s Open Learning Initiative. According to the description, it’s available both as a self-paced course and for other academic institutions to use for a self-paced format or for a traditional course with computer support. Not sure what the conditions are, whether it’s free or not, and have inspected neither the texts nor tried out the software.
    [Free software ? Free book ? Online ✗ Open source ✗]

Do you know of anything else that could be used to teach a course with an online or electronic component? Any experience with the options above?