As I’ve noted, it is time to update the much-downloaded Teach Yourself Logic Study Guide for 2016, and I’ve recently made a start working through the current version. So far, the editorial tinkering has been plentiful but minor as far as content is concerned, and even after quite a bit of thought I’m not yet finding myself inclined to make changes to the main recommendations in the early chapters (though this could alter: I’ve still some possible readings to [re]consider). As for form, I’ve decided to keep the one-big-PDF format, rather than go over to a suite of webpages: but I hope the new version will be just a bit easier to find your way around (even such a simple thing as setting off main recommendations in text boxes makes the Guide look less daunting, more navigable).
But now I ask again: any suggestions for additions, improvements? In particular, are there any sets of freely available online lecture notes (your own or by others!) that are especially good and appropriate for self-study?
To repeat, suggestions from logicians at any stage of their career, whether taking first steps or on their zimmer frame, will be most welcome — either in the comments below, or by email (address at the bottom of my “about” page here).
Another book that I haven’t sem mentioned, and that covers a lot in very short space is Srivastava’s A Course on Mathematical Logic; it’s definitely not for the fainted hearted, though! For instance, when remarking that the book requires some knowledge of algebra, the author recommends Lang’s Algebra as a reference text (not exactly the most elementary source). From what I glanced, it seems a bit brisk, but it may serve as good consolidation for someone who has already seen the material before—-and has some serious mathematical background (e.g. Exercise 2.8.12 asks the reader to prove that the Zariski closed subsets of K^n for a field K forms a basis for the closed sets of a topology on K^n, i.e. the Zariski topology; that’s not terribly difficult, but it may need some familiarity with manipulating polynomials in order to do it properly).
Yes, Srivastava’s A Course on Mathematical Logic is on my list of texts to do a Book Note on. One day!
(Sorry for the triple post)
I have a question/reference request. In his (draft) article on “Arithmetic and Incompleteness”, Richard Kaye mentions that, in order to arithmetize (is that a verb?) syntax, we don’t need the full class of p. r. functions; the polynomial-time computable functions should suffice for that. Do you know any references for this result? Or, at least, a reference that gave a clear presentation of such functions, in such a way that the result is readily retrievable from this characterization? Also, do you think it would be pedagogically useful to mention this in an intro course to Gödel’s incompleteness theorems?
I’ll need to check this out when I get back from Italy to books, laptop, and a decent internet connection …!
I’ll venture giving some intuition and discussion, hoping it’s helpful.
– “Finitist” or “proof-theoretic” means roughly “you can implement it on a computer”, while “syntax” means roughly “computer data structures” (to a colleague computer scientist, I’d say “algebraic data type”).
Loading data on a computer and reading memory as a binary number easily produces a natural. I believe this can be very helpful to somebody who already understands programming.
(Actual computers are irrelevant of course — “computer science is not about computer” — but I’ll consciously ignore this point).
– We have reasonably efficient interactive proof assistants, and they implement many meta-theoretic operations on syntax in a reasonably efficient way.
– It’s not obvious that all relevant algorithms are polynomial (as opposed to exponential). Still, we’re far away from the complexity class of all p.r. functions.
– In particular, proof assistants don’t implement actual set theory and FOL, but other systems, also to avoid exponential algorithms. This issue is hinted at, for instance, in this brief notice:
http://www.ams.org/journals/notices/200811/tx081101370p.pdf
I understand that Boolos “Don’t eliminate cut” discusses one specific important aspect.
I think those issues don’t affect the theoretical complexity of arithmetization, simply because arithmetization runs after such algorithms, but this shows some potential pitfalls. And for instance, if you want to implement a verifier that checks the validity of a proof, you can’t use cut elimination, because it _doesn’t_ have polynomial complexity (checking the proof before cut elimination, instead, avoids this problem).
Speaking of the Halmos book, I’m not sure it is all that clear. (For a brief, readable text at a similar level, though covering a different range of topics, I prefer Kaplansky’s Set Theory and Metric Spaces.) Quite a few people struggle with his proof of Zorn’s lemma from AC, for example; and while it’s written in a conversational style unusual for a maths text, not everyone will find it appealing or his presentation easy to follow.
It’s also missing an awful lot even at the level of the ‘elements of set theory’ you list in the Guide. For instance, it shows how to construct / represent the natural numbers, but not the rationals or reals. In the Guide you say the cumulative hierarchy “is nowadays familiar to every beginner”; but it’s not described in Halmos. He also doesn’t show that ordinals can be considered order types.
The book probably has to be mentioned, but I can’t help wondering what people would think of it if it appeared now, without its status as a ‘classic’.
(I don’t seem to be able to edit my posts, btw, or I’d fix the “remember” that should be “remembered” in my previous one.)
While thinking about the lack of exercises in Halmos, Naive Set Theory, I remember this book: Problems and Theorems in Classical Set Theory by Peter Komjath and Vilmos Totik — “classical in the sense that independence methods are not used, but also classical in the sense that most results come from the period, say, 1920-1970.” It reaches some fairly advanced topics such as stationary sets.
Each chapter begins was a concise presentation of the relevant material, followed by problems. A Part II provides solutions. The Preface says: There are no drill exercises, and only a few can be solved with just understanding the definitions. Most problems require work, wit, and inspiration.
I’ve given it only a quick look so far, but I find it very appealing.
*
There used to a book of exercises at a much more elementary level that was meant to accompany Halmos’s book, but it is out of print and looks hard to obtain. The book I describe above has no connection to the Halmos text beyond its role in my chain of thoughts.
Many thanks for the reminded about this. Komjath and Totik’s book is actually on my shelves, and I thought it terrific when I looked at it a couple of years ago. I can’t remember why I didn’t mention it in the Guide!
I found this online: Sets, Models and Proofs by I. . Moerdijk and J. van Oosten, Department of Mathematics, Utrecht University
http://www.staff.science.uu.nl/~ooste110/syllabi/setsproofs15.pdf
It looks interesting and covers a lot in 113 pages.
Many thanks for this. Oosten also has useful looking notes on formal arithmetics.
Honestly I had just checked the Coursera outlines to see if the same subject matter is covered at all … but neglected to compare the depth of study. Pedagogically, my intent was to offer variety. As you seem to be building a compendium of sorts, glossing the relevant peaks of interest with outlines and suggested readings, I presumed that any manner of conveyance might help. So, while I stand by that suggestion for further review, it is certainly within your purview to dismiss any means of learning that fail to adhere to the standard of which you are confident.
As for myself, watching Restall’s videos specifically were a nice companion to lecture in an undergrad nonclassical logic course. Alternate modes of explanation (e.g. videos, podcast, etc. vs. text or symbolics) can lend substantively insightful perspectives when a concept is otherwise insufficiently understood. Sometimes just hearing a different explanation can help immensely. Also, shifting gears can aid in mitigating burnout.
Regarding the “baby logic” concern, suppose that there are free online courses or videos that cover the appropriate topics at a level competitive to advanced undergraduate offerings. Is it within the scope of the guide to possibly recommend such resources?
As to your objection about slower absorption rates, how do you validate lectures or seminars then? Or is that why we’re all here?
I don’t want to extend the Guide to cover “Baby Logic”: per Partly that’s laziness — there are so many options to review. But partly I’m not sure that I could write anything widely useful: people just disagree so much about what to cover, and how to cover it. I have strong views, of course: but then so does everyone else! Once you get past that level, however, there’s much more agreement about what needs to be covered in a first serious FOL course, about what needs to be covered in intro set theory, and so on. And so Guide to how well the different options might succeed at introducing the standard topics (in a way suitable for self-study) becomes more useful.
As to lectures, I do think that old-style lectures where notes are written up by the lecturer and copied down by the students are in the main a pretty inefficient use of everyone’s times. What lectures, I agree, can be very good for is giving arm-waving motivational chat of a kind that embroiders terse handouts or a dense textbook! (“Look, think of it like this …”, “This is isn’t strictly correct, but gives you a handle on why the theorem works,” “Ok, we obviously need to hit this with Theorem 7, but the details get messy so go away and read the handout,” etc. etc. — fine things to say if you have handouts or your own or someone else’s textbook to provide the real core of the course.)
Consider free online videos or courses, such as:
Greg Restall’s videos …
https://vimeo.com/consequently
Coursera – Intro to Logic, Logic: Language and Information 1 & 2, Intro to Mathematical Philosophy, Intro to Mathematical Thinking, etc. …
https://www.coursera.org/browse/math-and-logic
Another way to mine for decent study material is to search any recently published logician’s website. For example, Restall’s personal website … http://consequently.org/ … offers more than most, actually you may want to start there before getting to his Vimeo videos or Coursera courses.
I confess I’m not usually a fan of videos — the ratio of the time that has to be spent watching to the information conveyed/understanding acquired is pretty unadvantageous. There are exceptions, of course, like Eugenia Cheng’s Catster’s videos.
I think (unless I’ve missed something — and please correct me if I have) that the Coursera logic offerings are mostly at the ‘baby logic’ level, while the TYL Guide starts a level up from that.
I follow Greg Restall’s blog, but I’ll take another look.
My main recommendation is George Tourlakis’s Set Theory. I think it’s one of the clearer and more interesting set theory books, and it’s one of the relatively few that goes as far as constructible sets and forcing. It made it as far as one of the small-type notes in an earlier edition of the Guide, but then it seemed to fall between two stools because, since it was officially a Volume 2 of Lectures in Logic and Set Theory, it could seem to belong in the ‘Big Books’. It can, however, stand alone as a set theory text.
Speaking of Big Books, Yu Manin’s A Course in Mathematical Logic now exists as A Course in Mathematical Logic for Mathematicians with collaboration from Boris Zilber. In the set theory parts, it also goes into constructible sets and forcing (boolean-valued models version), and it deals with with Hilbert’s 10th problem and the MRDP theorem as well as a wide and somewhat idiosyncratic range of other topics.
Rebecca Weber’s Computability Theory looks interesting and is reasonably short (206 pages).
Finally, there’s A Guide to Classical and Modern Model Theory by Annalisa Marcja and Carlo Toffalori.
Many thanks for this!
This is very minor, but since Marker’s book is on the recommendation list for “advanced” model theory, perhaps it’d be a good idea to emphasize that it really isn’t for beginners, that is, it assumes that you know a fair amount of model theory already. I mention this because Marker can be incredibly sloppy or overly terse with his definitions, so you must have a rather competent grasp of the material before checking it out. Three examples: (i) his treatment of M^{eq} is *very* terse and (ii) his definition of consequence covers only sentences, not formulas, which leaves one a bit lost when considering quantifier elimination; also, (iii) I found his treatment of back-and-forth a bit sloppy, specially in defining with partial embeddings).
I like Marker’s book because of the many mathematical examples, as well as the nice set of problems, but it doesn’t seem suited to a person trying to teach herself advanced model theory. I’d probably recommend Poizat or Rothmaler instead (if the person is feeling adventurous, perhaps Tent and Ziegler). I know that you mention that one should read Marker after, say, Hodges’s little book, which does help a lot (I’m studying Marker together with Hodges’s big book and I must say I’m learning *a lot*) but even so I feel that a warning regarding that could be useful.
Very helpful, and actually I’m inclined to agree (having had occasion to dip into Marker again a few months ago).
It would be nice to have more resources for ordinal analysis.
It would indeed! Any suggestions, anyone?
Are there any? The only book (that I know of!) which treats ordinal analysis in depth and that’s not in the guide is Schütte’s Proof Theory…
Apparently there’s also a book by Jervell, Proof Theory, which seems to give an introduction to ordinal analysis, but I haven’t been able to check it out yet.
Thanks for this, not a book I’ve come across.
Possibly Where is the Gödel-point Hiding: Gentzen’s Consistency Proof of 1936 and His Representation of Constructive Ordinals by Anna Horská.
I have found Tony Roy’s Symbolic Logic quite the thing for self-study.
http://rocket.csusb.edu/~troy/SLmain.pdf
Yes, thanks for the reminder about this, which is on my list of things to look at next!
And Tony Roy says on page 746 “Smith’s online, “Teach Yourself Logic” is an excellent comprehensive guide to further resources.”