# rigorous definition of a “logic”

It's been a couple of years since I've had a course in logic (the course was propositional and first order logic, up to Gödel's completeness theorem). I've been looking at some papers online, and they seem to talk about systems of logic like $\mathrm K$ and $\mathrm{S4}$ as "logics" (the noun). What does this mean? A quick Google search doesn't seem to have turned up anything useful. Is it just the set of well-formed formulas in the system using the language, inference rules, and starting with some basic axioms? Feel free to redirect me to a source—for some reason I feel like this should be in some book…. And thanks for any answers or advice!

Sincerely,

John

These terms are subject to some amount of variability, but what follows is a common way of defining “a logic.” A logic is a logical language (as described in the linked notes) that defines the sentences of the language. Along with the logical language, a provability relationship is defined, often by defining inference rules and axiom schemata, by which sentences may be derived in a proof.

A related, and often present, feature of a logic is that of a semantics for the logic. The notion that $Q$ is derivable from $P \land Q$ by the inference rule $\land$-elimination is purely syntactic; it is concerned only with the manipulation of strings of symbols. A semantics for a logic is a way of saying, “a sentence of a particular form has this meaning, or this interpretation.” With those sorts of notions, we can say things like ”the interpretation of a sentence $\phi \land \psi$ is true if and only if the interpretation makes $\phi$ true and makes $\psi$ true.” In a logic with a semantics, we can talk about more properties of the logic. For instance, we can talk about the soundness of inference rules; an inference rule is said to be sound if and only if its conclusion must be true if all of its premises are true. We can also talk about the completeness of a proof calculus (i.e., a set of rules for constructing proofs); a proof calculus is complete if every sentence which must, by the semantics, be true, is also provable. (There are actually other notions of complete as well, some of which are more syntactic in nature. See this question for more details.)

Each of the following is an example of a logic: propositional calculus, first order logic, $\mathrm K$, and $\mathrm{S4}$. In each case, there is a set of rules for constructing sentences of the logical system, and a set of inference rules and axiom schemata (or natural deduction proof systems, etc.) for inferring new sentences from base principles. All of those logics also have associated semantics. Some of the logics were developed before they had semantics; i.e., they were developed as syntactic systems, and semantic interpretations were only developed later.

In all of these cases, there are various formalizations of the logics and associated semantics. For instance: provably equivalent axiomatizations of of propositional calculus; logical languages that take certain connectives as primitives and logical languages that take them as abbreviations for other combinations of connectives (e.g., taking $\phi \to \psi$ as a primitive, or taking it as an abbreviation for $\lnot \phi \lor \psi$); various semantics for modal logics (the Kripke semantics are popular, but there are plenty of alternatives, too).

Regarding in particular the systems K and S4, these are both modal logics. Modal logics add modal operators, e.g. $\Box$, $\Diamond$, which allows you to evaluate the truth value of propositions at different states. Example: often times, $\Box p$ is meant to be read as "Necessarily, $p$", i.e. "In every possible world, $p$ is true." If you've brushed up on your basic logic from your course, then this might be a useful survey to look into: SEP's article on modal logic. If you want a more in-depth introduction (say in a book), I'd recommend van Benthem's Modal Logic for Open Minds, or even Chellas's Modal Logic: An Introduction.

For the purposes of modal logic, these systems like K and S4 can be thought of as a set of axioms (in some given language) which are to taken to govern the behavior of modal operators like $\Box$, $\Diamond$.

• thanks for the references! – john doe Jun 23 '13 at 5:06