Motivating Advanced Logic

At the Logic Education session at the APA/ASL meeting last week, Branden Fitelson made an excellent suggestion for teachers of graduate level logic courses in philosophy: One of the main problems is that it is often hard to see for students why the stuff they have to learn is relevant to philosophy (or to CS or linguistics, for that matter). Branden’s suggestion is that one should start each topic in such a course with a philosophy paper, or a passage from a philosophy paper, in which the relevant topics are used or referred to. So, e.g., you’d pick a passage from Lewis, or Putnam, and motivate the following topic (completeness, or possible worlds semantics, or what have you) as “we’re now going to figure out what Lewis is saying here.” Now it would be nice to have a repository of such passages/papers–if you have ideas, please post a comment. Here are some examples:

  • Quine, The ways of paradox (Ch. 1 in The Ways of Paradox) has a section on Gödel’s incompleteness theorem.
  • Lucas, Mind, machines and Gödel, Philosophy 36 (1961) for obvious reasons.

Off to San Francisco

I’m off to the APA Pacific/ASL Spring meeting in San Fran. Look for me in the picket line outside the St Francis (and, ok, well, maybe I’ll also go to the receptions–Friday 5-7 at the ASL Reception, and then 8-10 at the Presidential Reception). If I manage to steal internet access somewhere, I’ll report on interesting logic talks. And do come to the Logic Education session if you’re there.

Logic Education Session at the San Francisco APA/ASL meeting this Saturday

One last plug for the Logic Instruction and Philosophy Graduate Training session at this week’s APA/ASL meeting in San Francisco: It will take place as scheduled in the evil St. Francis hotel. Nevertheless, we hope you can all come. Note that Delia Graff won’t be joining us, unfortunately; but Brian Weatherson has agreed to participate in her stead. An extended abstract follows, note the plan of the session at the end.

UPDATE: Materials from the session are online.

ANDREW ARANA (CO-CHAIR), MICHAEL GLANZBERG, BRIAN WEATHERSON, TED SIDER, AND RICHARD ZACH (CO-CHAIR), Special Session on Logic Instruction and Philosophy Graduate Training. Session X-K, Saturday, March 26, 2005, 2-5 pm.

Formal Logic in the Philosophy Curriculum. Over more than half a century, formal logic has held an important position in analytic philosophy and consequently in the philosophy curriculum at English-speaking philosophy programs, both at the undergraduate and graduate level. Typically, undergraduates are required to complete a first course in formal logic covering semantics and proof theory of classical first-order logic. A graduate course on metalogic dealing with completeness and Löwenheim-Skolem theorems, undecidability and often also Gödel’s Incompleteness Theorems is a standard requirement in Ph.D. programs.

The Special Session on Philosophy and Logic Education provides a forum for reflection on and evaluation of the form and content of such courses, and the place and role formal logic courses play or should play in training in philosophy, especially at the graduate level.

Logic and Philosophy. One issue explored at the session is the question of how formal logic relates to other areas of philosophy, and how logic courses and requirements should relate to other courses and requirements in Ph.D. programs. On the one hand, working in formal logic is certainly a different kind of enterprise than, say, working in metaphysics or ethics. At the introductory level, the main motivation to require courses in logic is simply that it trains students in reasoning and assessing arguments. Logic provides the tools (formalization, deductive proofs, truth tables and interpretations) to do this. At this level, logic courses are more in the business of imparting skills than of a body of knowledge. The situation is somewhat different regarding requirements at the graduate level, where logic training presupposes those skills to a large extent, and students are taught results, such as the completeness theorem, and their proofs. And as these are in the first instance mathematical results, the question might be raised, “Why burden philosophy Ph.D. students by requiring such courses?”

Methodology. There are undeniably similarities in the methodology of formal logic and philosophical methodology: often, the limitative results of metalogic have served as examples for how questions could be made precise so that they are amenable to a (often negative) solution, and how to give such solutions with mathematical rigor. One motivation for requiring metalogic in philosophy graduate training then is that it imparts to students an appreciation for limitative results, and how they can be proved.

Content. There are also connections between formal logic and other areas of philosophy in terms of content. This is most obviously so in the philosophy of logic (e.g., theories of truth), the philosophy of mathematics (e.g., Gödel’s theorems as refutation of logicism and formalism), and the philosophy of language (formal semantics), but also in other areas. One might think of Lucas’ argument against mechanism, Putnam’s model-theoretic argument, or the contributions of formal logic in illuminating modality, the logic of knowledge, mereology, etc. Philosophy Ph.D.’s arguably should be able to understand, appreciate, and apply such results, and acquire the foundation necessary for further training enabling them to contribute to this literature. A more specific question for the panel then is how a graduate logic course would best accomplish this. Which results should be taught? How should they be taught? What is the relative importance of the topics now standard in graduate logic courses and more recent developments such as formal theories of truth or intensional logics and possible worlds semantics? Which recent developments should be taught, in what form, and where (required courses, supplementary courses, or incorporated into subject-specific courses, e.g., possible worlds semantics in metaphysics courses)?

History of Analytic Philosophy. The history of philosophy is rightfully considered a central part of the philosophy curriculum. As the history of analytic philosophy matures as a recognizable field of study (and teaching), a background in logic and metalogic becomes increasingly important. For the major figures in early (Frege, Russell, Wittgenstein) and more recent (Carnap, Quine, Lewis) analytic philosophy, logic was a central tool in philosophy and an area to which they themselves contributed. On the one hand, this raises similar questions as above: What to include or emphasize in graduate logic courses so to enable graduate students to understand, e.g., Russell’s theory of types, or what Frege’s Axiom V says? On the other hand, perhaps graduate logic courses should incorporate the philosophical aspects of the development of logic in the 19th and 20th century?

Additional Questions. (1) Textbooks: To some extent, the form and content of courses is influenced by the available textbooks. In graduate level logic courses, the two most popular texts are probably Boolos, Burgess, and Jeffrey’s Computability and logic and Enderton’s A mathematical introduction to logic. In light of the issues outlined above, how do they and other texts serve the purpose? What would an ideal graduate level logic text for philosophy look like? (2) Logic in the Profession: One important aspect of graduate training is, of course, preparation to teach. How important is it to have received advanced training in logic in order to effectively teach an introductory course? How can graduate training in logic enhance the effectiveness of introductory logic teachers?

Plan of the Session. Richard Zach will introduce the panelists and the questions and discuss the role of logic in the history of analytic philosophy. Michael Glanzberg will address some of the “content” issues: areas of logic which are closely related to philosophical concerns where there are some relatively accessible results, but also, where the more you look, the more interesting logic there is to be found. This includes, in particular, theories of truth and quantifiers, and their relation to definability theory and finite model theory. Brian Weatherson will speak on the place of teaching modal logic and non-classical logics in graduate courses. Andy Arana will talk about the lasting importance of the traditional metalogical results (completeness, incompleteness, Löwenheim-Skolem), what philosophical application they have, as well as about the general significance of limitative results is, and what it takes to get to a point where one can prove them. Finally, Ted Sider will talk about a graduate course on “philosophically useful logic” he has been developing, and generally on what logic is useful in philosophy. The session will end in an open discussion with the audience.

Complexity measures of proofs

In the last post, I pointed to some interesting work on cut-elimination and complexity of proofs. This reminded me of Richard Statman’s wonderful dissertation (Structural complexity of proofs, Ph.D. thesis, Stanford University, 1974). The two most widely investigated measures of proof complexity are size (number of symbols) and length (number of steps). Statman and Orevkov’s speedup results for sequent calculus concern length. In one chapter of the thesis, Statman considers another measure, which applies to proofs in natural deduction: Consider a proof tree in natural deduction, this gives you a graph (inferences are nodes, edges connect two inferences if the premise of one is the conclusion of the other). Now also connect each assumption in the proof (leaves of this tree) with the inference at which it is discharged. This, in contrast to the plain proof tree just considered, is no longer a planar graph: some edges cross. So you can now consider the genus of the resulting graph as a complexity measure: the minimum number of handles on the sphere so that you can embed the graph without edges crossing. Statman showed that normal proofs have superexponential speedup over non-normal proofs with respect to the genus measure. (Unfortunately, Statman never published this, to the best of my knowledge. My copy is back home and I unfortunately can’t check the details.) There is some related recent work on geometric considerations in proof complexity, e.g., Girard’s proof nets and the logical flow graphs considered by Buss and Carbone. Now I just found a recent PhD thesis by Anjolina Grisi de Oliveira which looks at these things. (See also this paper.) Would be nice if I had time to read it; maybe someone else does and wants to let me know what’s in it.

Eliminating cuts

If you’ve wondered what all this “cut elimination” business is about, here’s a nice blog entry (on That Logic Blog) which gives a nice introduction. Jon points out that proofs with cut have (at least–depends on the logic) exponential speedup over proofs with cut. This result is due to Statman and Orevkov. Jon points to a really good piece by Alessandra Carbone. She has done really excellent work on proof complexity; y’all should check it out. An interesting investigation of the complexity of cut-elimination (in classical first-order logic) is in “Cut normal forms and proof complexity“, Annals of Pure and Applied Logic 97, by Matthias Baaz and Alexander Leitsch. See also Boolos’s “Don’t eliminate Cut”, Journal of Philosophical Logic 13 (1984) 373-378 (reprinted in Logic, Logic, and Logic). An interesting and underexamined topic is the reverse of cut-elimination: how do you actually make proofs shorter by introducing cuts? Matthias and I have an old paper on that (which I should convert to PDF…). By the way, the deadline for the Studia Logica special issue on cut elimination is fast approaching!

CiteULike is The Coolest Thing!

Wow. CiteUlike is the best thing since Brian’s OPP blog. Here’s what it does: There are feeds for journals from all major publishers, plus arXiv and such. You can set up a watchlist of journal and other feeds, or other user’s libraries, and then build your own library of online papers, with keywords, comments, and ratings from “top priority!” to “I don’t really want to read it.” You can add articles via a bookmarklet even when you’re browsing JSTOR, arXiv, or publishers’ sites. Of course, you can also add individual papers. Your library, your watchlist, tables of contents of recent journals, etc., are all available as RSS feeds. Plus, you can export citations in BibTeX and EndNote format.

Begging the Question

John asks if logicians should give in in the face of rising acceptance of the use of “begging the question” for “raising the question.” I agree with the commenters: we should not. Also check out this delightful (and correct) use of “begs the question,” posted by Sean Carroll:

I once heard an astrophysics seminar with the title “Does the Milky Way galaxy have a bar?” introduced as “A talk whose subject is begged by the question, ‘Where should we go for a drink in the Milky Way?'” Wouldn’t want to give up the capability for lines like that.

Charset Problem Fixed

I’ve been irritated for a long time that the “ö” in “Gödel” doesn’t show up right on this blog. The problem was caused by the web server setting the charset in the header, thus overriding the UTF-8 charset declaration in the pages themselves. It should be fixed now, but let me know if I still don’t see the o-umlauts.

New Blog, Tonk, and Normalization

Another logic/language/philosophy of math blog started up yesterday: It’s still anonymous, but the author wrote over at that she’ll put up contact details soon. One of the first posts discusses the fact that natural deductions for ordinary propositional logic normalizes (well, at least without negation it does), but it doesn’t when you add the intro and elim rules for Prior’s tonk.

Philosophia Mathematica now online through OUP

Philosophia Mathematica, the only (and hence, the) journal on philosophy of mathematics, is now being published/distributed by Oxford University Press (for cooperation with the Canadian Society for History and Philosophy of Mathematics/Société canadienne d’histoire et de philosophie des mathématiques. That means, in particular, that it’s now (finally!) available online. The latest issue (February 2005) even seems to be available for free; it contains three interesting essays on category theory by Colin McLarty, Stewart Shapiro and my colleague Elaine Landry‘s “Category Theory Manifesto” (joint with Jean-Pierre Marquis), plus reviews of Calixto Badesa’s book on Löwenheim and Skolem, Charles Chihara’s newest book on structuralism in math, and Dennis Hesseling’s book on Brouwer. Hopefully they’ll add previosu issues to the archive, too.