Is there a good textbook on Second Order Logic?

Question

There are plenty of First Order Logic textbooks, that is, including definitions, exercises, and even many of them are at the same time very pedagogical as well as mathematically challenging. Are there Second Order Logic textbooks with these features? (Are there textbooks on Second Order Logic at all, including at least exercises?)

Answer 1

Unfortunately, there are no such books that I'm aware of. (I assume you're thinking about second-order logic with the standard semantics, as opposed to Henkin semantics; otherwise, there are multiple sources such as Manzano's Extensions of first-order logic.)

The problem is that there is very little accessible-but-nontrivial to prove about SOL. It's easy to prove that SOL can pin down structures like $\mathbb{N}$ and $\mathbb{R}$ up to isomorphism, and once you've done that it's almost hard not to show that it lacks both the compactness and Lowenheim-Skolem properties; meanwhile, it does have the interpolation property but only in the silliest possible way. The interesting results about SOL are generally quite hard to prove; witness for example Shelah's There are just four second-order quantifiers.

I learned about SOL by combining several papers and sections of books. In particular, the first couple chapters of Manzano's above-mentioned book, the later chapters of Ebbinghaus/Flum/Thomas, and some sections from the Barwise/Feferman collection will get you rather far.

Very quickly, however, you will run into a need for serious set theory before you can progress further into the study of SOL. Both forcing and large cardinals play significant roles, and are massive topics of their own; see Kanamori's book The higher infinite.

---

Incidentally, while it is a book devoted to SOL I do not think Shapiro's Foundations without foundationalism fits your question. This is because it's primarily concerned with the philosophical issues around SOL, and while those are very substantive this isn't quite what you asked.

EDIT: in response to Peter Smith's answer, let me say a bit about what Shapiro's book includes and explain why he's quite right but I'm still not a huge fan of it for this purpose. Up to chapter 6, the only technical results on SOL with the standard semantics presented are the failure of Lowenheim-Skolem, compactness, and (any reasonable form of) completeness, as well as a couple standard examples of the expressive power of SOL (e.g. minimal closure). But chapter 6 - "Advanced Metatheory" - definitely deserves its name: it treats cardinal invariants (e.g. Hanf and Lowenheim-Skolem numbers), the odd situation with results such as Craig interpolation and Beth definability (and the redundancy with third-order logic), and at the very end a cute result of Ajtai and Magidor.

I had forgotten about chapter 6 when I first wrote this answer, so let me say a bit more about it here. The Beth/Craig stuff is very well treated, but the whole thrust of the section is that they are for SOL of secondary relevance (as opposed to the situation with FOL). The Ajtai/Magidor result is not treated in any significant detail. Finally, the material on cardinal invariants is presented in a much less concise way than it appears in e.g. Kanamori's book.

Ultimately, I still think that the "right" book on standard-semantics SOL is yet to be written; to my mind, such a book would comprise:

• An introductory section showing - quite quickly! - the expressive power of SOL in terms of things like minimal closure, and the corresponding failure of tameness properties like LS and compactness.

• A subsequent section on definability results - exactly the Tarski/Beth/Craig material presented as in Shapiro - and perhaps some connections with Henkin semantics could go here too.

• Next, getting into the real set theory, a pair of sections on cardinal invariants; first the "naive" theory, i.e. that part which can be treated without forcing or inner model theory, and then the more technically intricate theory (Ajtai/Magidor would go here). In this latter section, proofs would all assume a fair amount of background in pure set theory but they would appear; the point of this part would be to not make the reader go paper-hunting. Personally I would treat chapters 5-7 of Kunen's Set theory: an introduction to independence proofs as prerequisites.

• Up next is the part of the subject where SOL diverges meaningfully from FOL, not just in results but in topic. There's a sense in which everything up to this point has been wrongheaded (truth and necessity notwithstanding): SOL is so dramatically different from FOL that the questions we're used to shouldn't be expected to paint the same sort of picture. Shelah's "four quantifiers" result is the sort of thing I refer to here; it answers a question about SOL that just wouldn't even crop up for FOL. I would also put here material relating SOL and other strong logics (e.g. infinitary logics). One real difficulty here is that a lot of the things I'd want to include here don't seem to exist yet; SOL is in many ways still terra incognita, even granting whatever set-theoretic hypotheses you happen to like! The material that does exist - that I'm aware of at least - is mostly to be found in the Barwise/Feferman collection, but again part of the point of this ideal book would be to save the reader from having to search elsewhere.

Answer 2

It of course depends quite what you are looking for and what background you have. But I do think there could more to be said for Shapiro's classic Foundations without foundationalism in the Oxford Logic Guides series than Noah allows.

Part II of that book -- some 110 pages -- comprises four formal chapters which make a very clear introduction, well worth tackling before other formal reading to get the basics firmly in place.

Yes, these core chapters are wrapped around by two shorter Parts of more conceptual/historical discussion about why we might think that second or higher order logics provide a natural framework for mathematical reasoning, about why first-order logic historically became dominant, etc. But even if you want to concentrate on the formal side, it is surely worth getting some sense of context, of why these things might matter, and Shapiro will help with that.

(And if you don't know it, can I also recommend -- for more useful framing of the issues and pointers to some of the technical complexities -- the substantial article on Second-order and Higher-order Logic in the Stanford Encyclopaedia?)