Book cover

Sets, Logic, Computation. An Open Introduction to Metalogic

Sets, Logic, Computation is an introductory textbook on metalogic. It covers naive set theory, first-order logic, sequent calculus and natural deduction, the completeness, compactness, and Löwenheim-Skolem theorems, Turing machines, and the undecidability of the halting problem and of first-order logic. The audience is undergraduate students with some background in formal logic, e.g., what is covered by forall x.

LINK

Book cover

forall x: Calgary. An Introduction to Formal Logic

forall x: Calgary is a full-featured textbook on formal logic. It covers key notions of logic such as consequence and validity of arguments, the syntax of truth-functional propositional logic TFL and truth-table semantics, the syntax of first-order (predicate) logic FOL with identity (first-order interpretations), translating (formalizing) English in TFL and FOL, and Fitch-style natural deduction proof systems for both TFL and FOL. It also deals with some advanced topics such as truth-functional completeness. Exercises with solutions are available. It is provided in PDF (for screen reading, printing, and a special version for dyslexics) and in LaTeX source code.

LINK

BibTeX-friendly PDF management with Zotero

For years I’ve been jealous of colleagues with Macs who apparently all use BibDesk for managing their article PDF collections and BibTeX citations in one nice program. I think I’ve finally figured out how to do both things on Linux: Zotero, with the Better BibTeX and ZotFile add-ons.

Zotero is first of all a citation management system. It’s multi-platform, open-source, not tied to a commercial publisher, widely used and well-supported. Your article database lives on your computer, but is synced with a central server. So any changes you make to the citation database gets automatically mirrored to your other computers (even if they run different OSs), and you can access it online as well. The browser extension Zotero Connector lets you import & download references and PDFs from publishers’ websites, JSTOR, etc., with a single click. It does everything a reference manager does, e.g., give you bibliographies and citations in Word or LibreOffice.

Zotero manages PDFs in one of two ways: you can store a PDF in Zotero, or you can add links to PDFs on your local drive. The former option manages the PDFs for you, syncs them across computers, etc. But you only get 300MB of online storage for free, and that’s gone quickly. But if you keep your PDF directory synced across computers (e.g., if it lives in your Dropbox), linking the PDFs is just as good. If you add a PDF, Zotero will look up the metadata for you and add a reference to your database. It keeps an index of the content of PDFs, so search will pick up hits in the PDFs and not just in the metadata. If you have a reference already, Zotero can look it up online and help you find the PDF (or library call number). The ZotFile add-on makes this even easier. For instance, with one click you can add the most recently downloaded file to a reference item, move it into your PDF directory, and rename it according to some standard schema, say “Author – Year – Title.pdf”.

All of this has worked to some extent for a while, and also works with other reference managers. What has kept me from using them is that I want my reference manager to play nice with BibTeX. That means it should export BibTeX files with (a) proper capitalization, (b) LaTeX code where necessary (e.g., mathematical formulas in titles), (c) keep track of BibTeX fields like the crossref and note fields, which may contain LaTeX code itself (e.g., “Reprinted in \cite{...}“), and (d) not change cite keys on you. On the other hand, the database itself should look as normal as possible and avoid LaTeX code whenever possible (e.g., I want Gödel’s papers to be indexed under “Gödel”, not under “G{\”o}del”). When I tried Zotero the last time (and other reference managers), it would deal with (a) by enclosing the entire title field in braces. That meant BibTeX would not lowercase anything; and sometimes the style does require lowercasing things. I don’t remember if (b) or (c) ever worked.

Anyway, Zotero’s Better BibTeX extension does an excellent job.  You can put in “Gödel” as the author name, and it will export to “G{\”o}del”. It assigns cite keys according to a configurable pattern, but it keeps cite keys the same when importing BibTeX files. You can change them manually, and it will remember them. Additional BibTeX fields not already supported by Zotero are saved on import and included on export.  It will convert HTML tags (which Zotero understands as well) to LaTeX code on export (e.g., <i>...</i> to \emph{...}). If you need LaTeX code, just enclose it in <pre>...</pre> tags. It does a very good job with capitalization and is even smart enough to do its transformations only to English language titles. Especially nice: Better BibTeX will keep your exported BibTeX files up to date. So, e.g., you can put all the references for a paper you’re working on in a Zotero “collection”, tell Better BibTeX to export it, and the .bib file will stay up to date if you change or add something to the collection in Zotero.

Want to try it?

  • Install Zotero Standalone and Connector
  • Install ZotFile
  • Install Better BibTeX
  • Check your preferences, e.g., whether you want Zotero to rename PDFs or look up metadata when saving them.
  • If you want your PDFs to be linked and collected in, say, your Dropbox, set the attachment base directory in Preferences: Advanced: Files and Folders.
  • Tell ZotFile where your downloaded files and your PDF direcories are, so it knows where to look for the most recent PDF to attach (in Tools > ZotFile preferences) and where to move them to. Make sure you set the ZotFile PDF naming pattern there to something you like.
  • Set up an account on zotero.org and link your library to it in Preferences: Sync (but uncheck “Sync attachment files” if you don’t want your PDFs on zotero.org)
  • Tweak your Better BibTeX settings, esp. the cite key pattern to make sure imported cite keys are the way you want them.

Indian Conference on Logic and its Applications 2019

The Association for Logic in India (ALI) announces the eighth edition of its biennial International Conference on Logic and its Applications (ICLA), to be held at the Indian Institute of Technology Delhi from March 3 to 5, 2019.

ICLA is a forum for bringing together researchers from a wide variety of fields in which formal logic plays a significant role, along with mathematicians, computer scientists, philosophers and logicians studying foundations of formal logic in itself. A special feature of this conference is the inclusion of studies in systems of logic in the Indian tradition and historical research on logic.

As in the earlier events in this series, we shall have eminent scholars as invited speakers. Details of the last ICLA 2017 may be found at https://icla.cse.iitk.ac.in. See http://ali.cmi.ac.in for information on past events as well as updates on this conference.

The call for papers is here: https://easychair.org/cfp/icla2019

PhD, Postdoc with Rosalie Iemhoff

Postdoc position in Logic at Utrecht University, the Netherlands.

The postdoc is embedded in the research project “Optimal Proofs” funded by the Netherlands Organization for Scientific Research led by Dr. Rosalie Iemhoff, Department of Philosophy and Religious Studies, Utrecht University. The project in mathematical and philosophical logic is concerned with formalization in general and proof systems as a form of formalization in particular. Its mathematical aim is to develop methods to describe the possible proof systems of a given logic and establish, given various criteria of optimality, what the optimal proof systems of the logic are. Its philosophical aim is to develop general criteria for faithful formalization in logic and to thereby distinguish good formalizations from bad ones. The mathematical part of the project focusses on, but is not necessarily restricted to, the (non)classical logics that occur in computer science, mathematics, and philosophy, while the philosophical part of the project also takes into account domains where formalization in logic is less common. The postdoc is expected to contribute primarily to the mathematical part of the project. Whether the research of the postdoc also extends to the philosophical part of the project depends on his or her interests.

Continue reading

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.

Rumfitt on truth-grounds, negation, and vagueness

Philosophical Studies 175 (2018) 2079–2089

In The Boundary Stones of Thought (2015), Rumfitt defends classical logic against challenges from intuitionistic mathematics and vagueness, using a semantics of pre-topologies on possibilities, and a topological semantics on predicates, respectively. These semantics are suggestive but the characterizations of negation face difficulties that may undermine their usefulness in Rumfitt’s project.

DOI: 10.1007/s11098-018-1114-7

Preprint

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!

lc18.uniud.it

 

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.

sample-thesis