Introduction to the study of logics

Question

Rather than study FOL and it’s properties, I’m looking for some references to study the relationships between logics, the associated ideas with these relationships, and properties of categories of logics. For example, the idea of modality is a property of some logics, or the idea of certain logics being extensions of other logics.

Essentially, rather than study a logic and the structures associated with it, I’m looking for a reference where the structures being studied are different logics. Is there any such reference?

Answer 1

Great question!

For good or ill (I'd argue for good) there is no single formal definition of "logic" which is universally accepted, and as such there isn't really a unified "study of logics." However, there are various areas where one particular notion shines. Below I'll describe a few of these.

Before I do that, though, here's my concrete reading advice. I tend to think of three "strands" here - pure semantics-first, pure syntax-first, and applied (especially to theoretical computer science) - which while not unrelated do have fundamentally different aesthetics. I think the first step you should do is read a bit about each, to get a sense of what you're interested in:

• For a taste of the semantics-first approach, look at the end of Ebbinghaus-Flum-Thomas where they treat Lindstrom's theorem, or at the first two chapters of Model-theoretic logics which outline the nature of the subject and treat Lindstrom's theorem more seriously.

• For a taste of the syntax-first approach, look at Blok/Pigozzi's book or the introduction to Czelakowski's subsequent book.

• For a taste of how the idea of "general logics" can be applied in CS, I think this paper of Halpern et al is a quite good introduction, but I'm not nearly competent enough in this area to be confident that it's the right choice - hopefully someone will mention a better one.

If you have a decent background in classical first-order logic and in abstract algebra, this should give you a good sense of where your own aesthetics lie at the moment.

---

Now in a bit more detail:

• Abstract model theory. Largely holding the semantics unchanged (we're still looking at the same structures as first-order logic), abstract model theory focuses mostly on strengthenings of first-order logic. In the AMT context a logic $\mathcal{L}$ is thought of purely semantically: ignoring set/class issues for the moment, $\mathcal{L}$ consists of a map $Sent$ sending each language $\Sigma$ to the collection of $\Sigma$-sentences in the sense of $\mathcal{L}$ and a relation $\models$ between $\Sigma$-structures and $\Sigma$-sentences. The pairs we're interested in - called regular logics - are those satisfying some nice properties. Most of these are extremely basic, like "Every $\Sigma$-sentence should be a $\Sigma'$-sentence when $\Sigma\subseteq\Sigma'$" and "For every $\Sigma$-sentence $\varphi$ there should be a $\Sigma$-sentence $\psi$ which is true in exactly those structures not satisfying $\varphi$;" there is one more subtle requirement (relativization) which is less obvious at first, but playing around with the notion will quickly convince you of its importance. The end of Ebbinghaus/Flum/Thomas discusses regular logics, and in particular Lindstrom's theorem (= there is no strengthening of first-order logic which retains the Lowenheim-Skolem and compactness properties). After reading that, the collection Model-theoretic logics is all about abstract model theory and covers a gigantic range of material.

  • A confession is due here. Abstract model theory largely lost steam a couple decades ago; I'm not a historian, but I'll tentatively claim that a big part of this was an initial over-selling of the promise of the subject coupled with just how hard it turned out to be. This isn't totally negative, though: the reason for that optimism was the profound success of one particular extension of first-order logic, namely the simplest infinitary logic $\mathcal{L}_{\omega_1,\omega}$, in many different areas. So while you've stated an interest in the general side, it's also worth mentioning that the particular case of infinitary logic is well worth your time; see the discussion here for some sources.

• Algebraic logic. Here, as the name suggests a logic is thought of primarily as an algebraic entity. Specifically, in contrast to abstract model theory, in algebraic logic any semantics is secondary and the main object of study is the internal deductive structure of logics. As such, logics are initially thought of as simply deduction relations on sets of sentences. There is a gigantic amount of material here. Both seriously and for funsies I'll recommend Humberstone's book The Connectives, which is $\sim$$1500$ pages long and doubles as submarine ballast; more feasibly, Halmos' expository article is quite good despite being old.

  • Going more specific: one major question which emerges at this point (maybe the first?) is "When does a logic admit an algebraic semantics?" with the motivating examples being Boolean algebras for classical propositional logic, Heyting algebras for intuitionistic propositional logic, and cylindrical algebras for classical first-order logic; this question leads to a number of dividing lines amongst logics. I strongly recommend Blok/Pigozzi's monograph, and the introduction to the subsequent book by Czelakowski is also a great read.

• Fragments of first-order logic. More generality isn't always a good thing. Focusing specifically on fragments of first-order logic, or logics equivalent to such in some sense, yields a rich and valuable theory as well. For example, there is a tight connection between modal logic and intuitionistic logic, which is explored in great detail in Chagrov/Zakharyaschev. Even weaker fragments are treated throughout computer science, where I'm even less qualified to recommend texts; however, this article of van Bentham/ten Cate/Vaanaanen is a good read if you already know about Lindstrom's theorem.

  • And for that matter, there's also a spiritual connection between CS and abstract model theory, as logics stronger than first-order logic restricted to finite structures play a significant role in complexity theory via descriptive complexity theory. In some sense that's far from the study of fragments, but they have interestingly overlapping areas of application; I'm not remotely competent to speak on their relationship but I suspect they have nontrivial overlap.