Studying Logic

is a study diary for my work in logic (with some philosophy/mathematics). This is much more relaxed than it sounds: study is just a very serious form of gossip. I'm currently reading Philosophical Devices and Topics in Modern Logic.

[eatsleepmath]

Finding a problem to solve is rarely a problem itself. Every field is brimming with open problems. If finding a problem is hard, you’re in the wrong field. The real hard part, of course, is solving an open problem. After all, if someone could tell you how to solve it, it wouldn’t be open. To survive this period, you have to be willing to fail from the moment you wake to the moment your head hits the pillow. You must be willing to fail for days on end, for months on end and maybe even for years on end. The skill you accrete during this trauma is the ability to imagine plausible solutions, and to estimate the likelihood that an approach will work. If you persevere to the end of this phase, your mind will intuit solutions to problems in ways that it didn’t and couldn’t before. You won’t know how your mind does this. (I don’t know how mine does it.) It just will.

Matt Might, Perseverance (via eatsleepmath)

[defunctlogicblog-blog]

...there is a puzzle called "The Gödelian Forest" in Smullyan's book To Mock a Mockingbird. The object is to prove, from a certain set of axioms, that a certain forest contains at least one bird that sings, but is not a nightingale. There is an unstated correspondence:

x is a bird corresponds to x is a proposition x sings corresponds to x is true x is a nightingale corresponds to x is provable

and, of course, one of the axioms guarantees that all nightingales sing.

http://www.math.niu.edu/~rusin/known-math/98/mockingbird

[defunctlogicblog-blog]

What is logic about?

Logic is about many different things. One of the things logic is about is the notion of proof. Greg Restall, “Normal Proofs, Cut Free Derivations and Structural Rules,” Studia Logica 102:6 (2014) 1143–1166. I am grateful to Tim, as my teacher in logic, for emphasizing that its main notions are relational: ‘ϕ is deducible from ∆’ and ‘ϕ is a logical consequence of ∆’. The notions ‘ϕ is a theorem’ and ‘ϕ is logically true’ are special cases. In the early 1970s Tim gave a formative series of lectures emphasizing how proofs are to be understood as perfected arguments, in Aristotle’s sense. ‘Inferential Semantics’ , in Jonathan Lear and Alex Oliver, eds., The Force of Argument: Essays in Honor of Timothy Smiley, Routledge, pp. 223-257. Logic is not a way of compiling a special corpus of truths, the logical truths, but rather an instrument (organon) for deriving consequences from assumptions in all fields of thought. We get logical truths as a by-product: given a set of valid inferences, there are methods for reducing the set of assumptions employed while still leaving the inferences valid, and repeated application of these methods leaves us with truths that rest on no prior assumptions at all. With such a general view of logic one would give prominence...to natural-deduction methods like Gentzen's. Review of Entailment: The Logic of Relevance and Necessity, Vol. 1. P. T. Geach (1977). Philosophy, 52, pp 493-495 doi:10.1017/ S0031819100029028

[defunctlogicblog-blog]

Tautological implication (Makinson 1.1a)

We say that one formula tautologically implies another iff there is no assignment of truth values to propositional letters upon which the first formula comes out true and the second comes out false.

So writes Makinson in Topics in Modern Logic, p. 2. This definition seems to coincide with our normal idea of model-theoretic consequence: q is a model-theoretic consequence of p iff in all models where p is true, q is true as well. The only difference is that Makinson is dealing with propositional logic at this stage, so he talks about assignments of truth-values instead of models. In other words, his tautological entailment coincides with what we would symbolize as \(\models\).

So far so good. But then he starts talking about axiomatizing this relation with axiom schemata such as \[\alpha \wedge\ \beta \rightarrow \alpha\] \[\neg \neg \alpha \rightarrow \alpha\] where \(\rightarrow\) is not the conditional, but tautological implication. Which just seems to be wildly confused. You can't have axiom schemata of the form \[\neg \neg\ \alpha\ \models \alpha\] because axioms are meant to be purely proof-theoretic, and \(\models\) is a model-theoretic notion.

So there are two questions here: How did this confusion arise in the first place, and how are we meant to interpret these axioms sensibly?

How did this confusion arise in the first place?

This seems very similar to another confusion in Kleene: http://math.stackexchange.com/questions/577072/virtues-of-presentation-of-fo-logic-in-kleenes-mathematical-logic/577175#577175. In this case, Kleene mixes up

a Hilbert-style axiomatic proof system with an overlay of derived rules which look rather natural-deduction-like...the way he presents FOL perhaps reflects a transitional stage in our understanding of the relations between different types of logical theory.

So I think something similar is going on here, except with proof-theoretic and model-theoretic ideas: where Kleene mixes up Hilbert and Gentzen, Makinson mixes up proof theory and model theory.

How are we to interpret this sensibly?

Makinson also gives us a few derivation rules with his axiom system, for example

\[\textrm{From } \alpha \rightarrow \beta \textrm{ and } \beta \rightarrow \gamma \textrm{ to } \alpha \rightarrow \gamma\]

So it seems like we can charitably take Makinson to be presenting a Hilbert-Gentzen mashup like Kleene. So I suggest we take all of the axiom schemas to be of the form \(\Gamma \supset \beta\) whenever he writes \(\Gamma \rightarrow \beta\). And we can take his derivation rules to be of the form \(\frac {\alpha \quad \beta}{\gamma}\), such that the above rule turns out to be \[\frac {\alpha\rightarrow\beta\quad\beta\rightarrow\gamma}{\alpha\rightarrow\gamma}\]

Alternatively, we can take all axioms to be derivation rules as well, but...well, that's on my to do list - take an axiom system, change all schemas to natural deduction inferential rules, and see what happens. I think it should still be sound and complete, but I should see what else changes. (I remember discussing this with my logic lecturer, and he said that it was similar to something Gentzen did, but that he had forgotten the exact details.)

[defunctlogicblog-blog]

Why do we teach what we teach in logic?

“...how come we learn Boolean logic but not Pearlean causation or even probability theory; how come you should expect a philosophy major to know set theory, but not computational complexity theory? Answer: because philosophers are a bunch of cliquey highschoolers.” “I think there are "scaffolding" problems with most philosophy major curricula that are also in the way. We see this with the way that basic logic is taught with classical logic as the default. Departments are responsible for providing something like a "well-rounded" philosophy education, and for the most part departments scaffold their courses so that what students learn coheres with what they'll need to understand to advance their understanding of philosophical texts in a wide variety of areas. Basic classical logic makes sense to emphasize and teach from this perspective, and "innovations" are put off "until later." Usually to graduate study or to advanced courses (if one's department has the faculty and student demand to run them). I've seen individual faculty introduce "innovations" (Probability theory, Relevance Logics) beautifully -- it CAN BE DONE -- but departments as a whole in such cases need to capitalize more on why changing basic logic curricula helps students. It's a tough road to travel.” “I think it's also partly historical: deductive reasoning (and hence formal logic) is something that philosophers have been studying for a very long time - in part because of the fascination with valid arguments, and in part because it's obvious what there is. But probability theory (or decision theory, or Bayesianism, etc.) is much more slippery - it developed later, and so philosophical teaching hasn't really caught up with it.” “With reference to [the second] comment, I've also seen individual innovations in teaching non-classical logic to first year students (instead of as a second course in logic). For example, there's Eric Schechter's book "Classical & Nonclassical Logics" (Princeton University Press, 2005) which teaches classical and then non-classical logic at the propositional level, and Diderik Batens' paper "Propositional logic extended with a pedagogically useful relevant implication", which is about teaching relevant logic to undergrads. But for the most part, classical logic still dominates first-year courses, and I've never actually seen a course in which first-years are exposed to non-classical logic.” Diderik Batens' paper: http://apcz.pl/czasopisma/index.php/LLP/article/view/1604 An argument for metalogic in basic logic courses: http://logicae.usal.es/TICTTL/actas/GabrielaHernandez.pdf From: https://www.facebook.com/groups/124530507743865/permalink/367161246814122/

[defunctlogicblog-blog]

Logic Study Plans [2015/1]

My reading in logic is rather inconsistent, as is my knowledge - I have a tendency to start books, work halfway through them, and not finish them. (The same is true of my non-logic reading, but anyways.) So my plan is to go through a few short intermediate books thoroughly. Intermediate, because that's the level I'm at, and short, so that I actually work through them. I plan to go through

Philosophical Devices: Proofs, Probabilities, Possibilities and Sets, by David Papineau (Oxford UP, 2012), and

Topics in Modern Logic, by David Makinson (Methuen, 1973).

The Papineau book is rather basic and introductory, and I'm probably already familiar with most of the material, but I think it's a good idea for me to go through it. Topics in Modern Logic is no longer quite so modern, but I've heard good things about it and I think it should give me a firm grounding for further study. Then, there's

Philosophical Logic, by John Burgess (Princeton UP, 2009).

I plan to read that for non-classical logic; printing errors are listed on the website. For introductory computability theory, there's

Gödel's Incompleteness Theorems, by Raymond M. Smullyan (Oxford UP, 1992).

Incompleteness in the Land of Sets, by Melvin Fitting (College Publications, 2007).

There are two other which don't really fit in anywhere, at the moment:

How to Play Dialogues: An Introduction to Dialogical Logic, by Juan Redmond and Matthieu Fontaine (College Publications, 2011).

Logic: The Basics, by JC Beall (Routledge, 2010).

There's another rather more specific reason why I'm going through Philosophical Devices and Topics in Modern Logic first: apart from them being at the right level, they also have extremely convenient chapter lengths. Philosophical Devices has twelve chapters; Topics in Modern Logic has fifteen sections. I'm hoping that the routine of doing a chapter a week for Papineau and a section a week for Makinson will help me be steady with my studying.

There are omissions on the list, most notably proof theory - but I'll remedy that when I feel like I've understood enough of the basics: all things excellent are as difficult as they are rare.

Why am I noting this here? As http://www.logicmatters.net/2014/05/30/parsons-1-predicativity/ puts it: ". . .promising to comment here is a good way of making myself read through the book reasonably carefully. Whether this is actually going to be a rewarding exercise — for me as writer and/or you as reader — is as yet an open question: here’s hoping!"

Of course, there's more to working than just making a good environment for it: “Air and light and time and space have nothing to do with it and don’t create anything except maybe a longer life to find new excuses for.” But at the same time, there's no harm in making sure that you're more likely to get things done, and this is my way of doing that.