# What is a logic ?

I am not interested in the philosophical part of this question :-)

When I look at mathematics, I see that lots of different logics are used : classical, intuitionistic, linear, modal ones and weirder ones ...

For someone new to the field, it is not easy to really see what they have in common for justifying the use of the word "logic". Is it just because of a filiation with classical logic ?

I have attempted to find an answer in the literature. Some papers are telling me that a logic is a pre-order. It is not a satisfactory answer to me. I imagined that it may be related to the use of some specific connectors : but linear logic is telling me it is not so simple. I imagined that it may be related to some symmetry properties of the rules of the system : but it is dependent on how the logic is formalized. Then, I had the crazy idea (after discovering the Curry-Howard isomorphism) that it may be related to the computational content of the system. But, it is obviously wrong.

So, I have not progressed and I am still wondering if there may be a point of view allowing to see what all these systems have in common ?

I have avoided the use of the word "truth" in this question. I am expecting a mathematical answer if there is one. There are too many philosophical problems related to the notion of truth.

But, perhaps my question is a naive one ...

-
One modern approach to the question is known as topos theory; see for instance math.ucr.edu/home/baez/topos.html – Harrison Brown Dec 14 '09 at 17:11
"What is an logic?" – Harry Gindi Dec 15 '09 at 6:56
You might be interested in en.wikipedia.org/wiki/… if you haven't seen it already. – Qiaochu Yuan Dec 15 '09 at 15:01

-
I just had a look and I think it is exactly what I was looking for. So I guess my question is still a research problem. – alpheccar Dec 15 '09 at 21:26

Logic is the construction and study of models for reasoning.

There are many logics, because we reason in different ways, depending on the context. Modality shows up because there are contexts in which out statements are qualified (I can be rich, but I can also be very rich, and there is a difference between the two statements, and a connection of modality between the two, not captured by classical logic); temporality shows up because we sometimes reason with time; linear logic shows up (among other reasons) because we need to reason about resources (If I have a dollar, I can buy one candy — but we all know that we do not get to use the statement "I have a dollar" more than once... and this is different from "There are infinitely many primes", which has not ceased to be true for a loooong time, and we do not expect it to); paraconsistent logics show up because we need to be able to reason in the presence of conflicting information, simply because we tend to have conflicting information; and so on.

Of course, one wonders why logicians do not get their act together and come up with one logic to rule them all... Well, they may be waiting for physicists to wrap up their grand unified theory first!

(N.B.: all of this is prefixed by a huge "In my opinion", of course)

-
I feel like the application of formal logic to places where we don't have precise definitions is just sophistry. – Harry Gindi Dec 14 '09 at 19:25
Well, there are places where we do not have clear cut definitions, and we are often forced to reason in them, so the human enterprise of trying to understand those situations better is not entirely devoid of interest! – Mariano Suárez-Alvarez Dec 14 '09 at 19:29
Of course, I am not expecting a grand unified theory of logic :-) I am just trying to understand what is the lowest common denominator between all of them and/or the relationships between them. Studying topos theory may not be a bad idea after all ... – alpheccar Dec 14 '09 at 19:32
That is more of a philosophical answer, explaining logic in terms of its external applications. But if I understand correctly, the original question was about what is common to logics internally. Consider, for example, that a large number of useful algebraic structures are in fact algebras, in the sense of universal algebra. This distills out much of what it means for something to be an algebraic structure. Is there something similar for logic? – Dan Piponi Dec 14 '09 at 20:02

I think there is supposed to be a correspondence between logics and kinds of category, e.g.,

(higher order?) classical logic        elementary topos with some extra properties?
(higher order?) intuitionistic logic   elementary topos
linear logic                           symmetric monoidal category with a dualizing object
modal logic                            ?


I'm not sure exactly how much one can say about the entries on the right, but as a start, they are all 2-categories. So maybe a logic can be viewed as a (certain kind of) 2-category.

I would be grateful if an expert on the subject could expand this into a real answer! There is something similar on the nlab page for internal logic, but it does not seem to be geared specifically for the question as phrased here.

-
Thanks. It is what I am looking for : a framework allowing me to understand what's different or common to all logics. – alpheccar Dec 15 '09 at 6:53

Are you familiar with Lindström's theorems?

You can define a "logic" L by giving the collection EC(L) of all classes of models which are "L-axiomatizable," and we assume that EC(L) has a few nice closure properties (closure under finite intersections, taking complements within the class of all structures with a given signature, closure under taking reducts to smaller signatures, and isomorphism invariance).

Say that a logic L_2 is stronger than a logic L_1 iff every class in EC(L_1) is also in EC(L_2). Then one of Lindström's theorems says that any logic which is stronger than first-order logic and satisfies the compactness theorem and Löwenheim-Skolem must be the same as first-order logic. (See Ebbinghaus and Flum's Mathematical Logic, chapter 12, for a proof.)

This doesn't seem to apply directly to your question about modal and linear logics, but at least for modal logics, people have worked on generalizing Lindström's results, e.g. here:

http://users.soe.ucsc.edu/~btencate/papers/lics2007full.pdf

-
It does not apply directly to my question but it is nevertheless very interesting. Thanks for the link to the paper. – alpheccar Dec 14 '09 at 20:52
Thinking about this some more, this approach to identifying "logics" with the classes they axiomatize seems ill-suited to intuitionistic logic, but maybe it's reasonable for modal logics. – John Goodrick Dec 14 '09 at 22:55

There may be a problem with looking at modal logic outside of philosophy. According to the wikipedia article "A modal logic is any system of formal logic that attempts to deal with modalities. Modals qualify the truth of a judgment." It is hard to qualify the truth of a judgment totally outside the context of philosophy. Some forms of logic involve formalizing philosophical issues such as truth. In that case it is hard to ignore the philosophical issues involved. To get a purely mathematical answer the question may have to be restricted to systems of logic formalizing purely mathematical areas or else questions in areas outside of mathematics may arise.

-
Indeed, it is difficult at some point to avoid philosophical questions. But even with modal logics, I am optimistic I can keep them in the scope of my question. With Kripke semantic, it looks like there is a link with Topos theory too. – alpheccar Dec 15 '09 at 19:43

Here are three research traditions that both illustrate how the problem can be approached, and give rather different perspectives on what counts as a logic.

(this really is just to complement Dan Piponi's answer).

1. Tarski's consequence relations and abstract algebraic logic

Tarski's basic idea was to define a logic as an abstract pair of the form $\langle \mathcal{F},C\rangle$ where $\mathcal{F}$ is a free algebra of formulas and $C$ is an operator on $\mathcal{P}(\mathcal{F})$ [I write $\mathcal{F}$ for the domain of the free algebra]. For any set of formulas $A$, the set $C(A)\subseteq\mathcal{F}$ is meant to represent the 'consequences' of $A$ -- so that $C$ generates a consequence relation $\vdash_{C}$ defined as $A\vdash_{C} B$ iff $B\subseteq C(A)$.

Next, Tarski gave several structural conditions that the operator $C$ ought to satisfy in order for the resulting consequence relation to count as well-behaved, or logical (roughly, those conditions consist of reflexivity, monotonicity, compactness, as well as invariance under uniform substitution of variables). See here for more detail.

This view really treats logic as a (very special) branch of abstract algebra. One idea is to try to differentiate between logics, and classify them, by looking at their different algebraic properties. It was one of the earliest systematic attempts at answering the question of 'what a logic is' in such general terms.

On the other hand, this framework is generally too weak to account for quantification of any sort; the attention is almost exclusively restricted to propositional logics.

(NB. Tarski's approach eventually gave rise to some very interesting work on the general process of algebraization of a logic, under the guise of Abstract Algebraic Logic -- see, e.g. here. Interesting monographs on the topic include Rasiowa and Sikorski's An Algebraic Approach to Non-Classical Logics as well as Blok and Pigozzi's Algebraizable Logics.)

1. Model-theoretic logics, generalized quantifiers

For an introduction see this book. The model-theoretic approach studies various extensions of first-order logic: predominantly infinitary logics of the form $\mathcal{L}_{\alpha\kappa}$, where $\alpha, \kappa$ are ordinals (the logic $\mathcal{L}_{\alpha\kappa}$ allows conjunctions/disjunctions of less than $\alpha$-many formulas, and quantification over less than $\kappa$-many variables). It also covers topics like abstract characterisations of first-order logic (cf. Lindstrom's theorem mentioned in John Goodrick's answer) as well as connections with probabilistic logics.

There is related research on what makes a quantifier 'logical'. The idea is to characterise the logical quantifiers as operations of a certain type that are invariant under certain groups of transformations -- there appears to be some controversy about what exact transformations truly define the 'logical' operations (see here).

1. Applied logics

Another approach that gives a slightly different perspective on what counts as a logic is work in `applied' logic: this is a broad field of study which has at its root a dynamic view of logic (see here). Here, one uses so-called 'dynamic' modal logics to model processes that change over time, such as transitions between the states of a program (see Propositional Dynamic Logic) or informational states of agents (see Dynamic Epistemic Logic). Those logics are studied either for their intrinsic mathematical interest, or can also be applied to the study of information exchange protocols in game theory, cryptography, and various topics in formal philosophy.

The approach here is less algebraic, but focused more on model-theoretic and computational aspects. This research often bears close links to computer science and philosophy.

-

I think the framework you are looking for may be found in thinking about the "logic" of mathematics in terms of a "formal language." See the articles on formal languages in the Encyclopedia of Mathematics and in MathWorld and Wikipedia.

-

Logic is the normative science whose object is truth, in other words, true representations of reality.

In general, a normative science seeks knowledge of how we ought to conduct our activities in order to achieve a specific goal. To mention the other two classical examples, ethics is the normative science whose object is justice and aesthetics is the normative science whose object is beauty.

In its practical application, logic pursues knowledge of how we ought to conduct our thoughts in order to achieve the object of thinking. That makes logic a special case of ethics, since ethics pursues fitness of action in general, and thinking is a special case of action.

-
I really don't think that was the intent of the question. It seems to me that the OP wants a Bourbaki-style definition, e.g. "a logic is a set with..." – Qiaochu Yuan Dec 15 '09 at 5:10
-1: Your response misses essential parts of the poster's question, e.g. that s/he did not want a philosophical answer. – Pete L. Clark Dec 15 '09 at 5:18
The "essential" parts of a question are those that are given definition. – Jon Awbrey Dec 17 '09 at 21:00