Material for a course on meta-theory
Here is a question for the readers. What are good books for an intermediate level course on meta-theory (honours level)? St Andrews has run a course like this before using, I think, the well-known Computability and Logic and also Hunter's Metalogic. However, I'm not completely satisfied with either of them, so if anyone's got other proposals I would be interested.
The book ought to cover basic limitative results for classical logic, up to and including incompleteness. It should be suitable for students who have done a course covering basic proof- and model-theory.
The book ought to cover basic limitative results for classical logic, up to and including incompleteness. It should be suitable for students who have done a course covering basic proof- and model-theory.
Posts
12 comments:
How about Smith's Intro to Godel's theorems?
The worry is, Smith's book focuses on arithmetics Godel's stuff, and it's not obvious you want to do that in a standard metatheory course.
So yes, in Smith's book you get to undecidability but only in a late chapter (30.5, 33.3), and this depends to large extend on previous material, which for a standard course in metatheory of first-order logic, strictly speaking, is not always necessary.
There is some material on Turing machines in it, but it quickly moves to a discussion of the relation between Turing computability and mu-recursiveness (now, do you wanna get into recursion in the course?)
There is a neat discussion of Church-Turing thesis, and some very nice bits on metatheory here and there, but unless you want to explain recursion and get into arithmetics and incompleteness, you might not want to use the whole book, but rather use some parts of it in addition to another book.
Moreover, Smith's book doesn't discuss soundness and completeness of first-order logic (not to mention propositional logic) in much detail (well, it's mentioned in footnote 11 on p. 25...).
Having said that, it's an excellent book when you want to teach Godel's theorems and related stuff.
Neat proof systems and fairly simple proofs of basic metatheoretic facts are in Kaye's The Logic of Mathematics (although, the material gets quite dense here and there). As for a detailed treatment of first-order logic and its metatheory, the first volume of Tourlakis is nice (he doesn't do that much of Turing machines, though).
If you want to get deeper into second-order logic, I recommend Manzano's "Extensions of first-order logics". This book nicely discusses how change of semantics gets you (or takes away) the completeness for second-order logic.
That's off the top of my head. good luck!
My bad, Kaye's book is "The Mathematics of Logic", rather then "The Logic of Mathematics". `The A of B' titles always confuse me.:)
Yeah, you're right, Smith wasn't a great suggestion. When I took that course we used Hunter supplemented with Read's own notes. There's also Hedman's 'A First Course in Logic', which covers more suitable material, but I can see that being frustrating in various ways. In particular, he covers a lot of ground you'd probably like to be able to presuppose towards the beginning of the book, but the presentation's a little idiosyncratic, and so you might have to use up some time covering it before you got to the actual metatheory sections.
Yes, Peter Smith's book was something I thought about, but I also concluded that it might be a bit too specialised for a standard meta-theory course. But perhaps it's just a matter of digging out the right sections etc.
I'll check out the other suggestions -- thanks!
There certainly is some good stuff in Smith, but afaik he simply doesn't do soundness/completeness/compactness/Lowenheim-Skolem proofs for classical logic. For those, you'd have to look somewhere else.
Oh, one more thing. For incompleteness of arithmetic, Franzen's book seems a nice lecture as well (I mean the incomplete guide, not inexhaustibility). A neat thing about it is it discusses philosophical applications/misapplications of theorems. {in the same vein: Panu Raatikainen and Jeff Ketland wrote a few pieces about Godel-inspired arguments in phil of mind).
I like Enderton's Mathematical Introduction to Logic. It's the standard at Stanford, at least it was when I was there. Some may find it a bit dated though, and it doesn't include lots of things you might want (such as natural deduction and sequent calculus, might not even do Turing machines, I forget).
I did a survey a while back of what various departments cover and the texts they use
Thanks Richard,
That's very useful. Didn't know about the survey -- quite interesting. I'm checking out the Enderton book as soon as I can get a copy from the library.
I am a bit concerned about proof-theory, of course. But it's hard to find a book that combines good proof theory with standard metatheory material.
The Ebbinghaus & Flum is nice. I also prefer Mendelson to Enderton partly because of the breadth.
Of course, the idea of using Smith's book is an utterly splendid one :-)
You don't say how mathematically ept your class is going to be -- or what you can presuppose. When you say "students who have done a course covering basic proof- and model-theory", how much exactly is that? What book have they covered so far?
Everyone, thanks again for the contributions.
Peter: The students have done a introductory logic class consisting of tree method for propositional and 1st order classical logic. No real model-theory at that point. (I think the book might be 'Logic with Trees' by Howson.)
Then they do a second year intro to nonclassical logics which is largely based on Priest's book (2nd ed), but with natural deduction in addition. Here they also do some model-theory for classical logic and for a range of modal logics.
However, the students have only a superficial acquaintance with soundness and completeness (that is, the notions are introduced, but we don't run over proofs).
Of course, some students have a math background (and might have taken a discrete math course), but this certainly won't hold in general.
Does that help? After the plan Colin Caret and myself will run a metatheory course in the next spring semester. So any advice is greatly appreciated.
Post a Comment