Question by Fenrong Liu: Today we celebrate our successfully finishing the translation work by having this small workshop, so that we can talk face to face. The translated works are 13 papers of yours on modal logic. You have divided them into four sections by themes, namely, basic theory, modal logic and computation, modal logic and information, and modal logic and games. The publishing span of the papers runs from 1970s to now. Moreover, I noticed that those papers are cited very often in the literature. Can you briefly explain the development of your ideas over the years on modal logic? What were the biggest challenging questions over time?

Answer: Let me first thank you all for this initiative! ‘A Door to Logic’ is a great opportunity to work closely with clever nice young people, a chance to reach a new audience for logic in China, and a welcome opportunity to reflect on where my own work and my field is going. I hope this interview will show a bit of all of these things.

Let me start with my own development. What were the main lines and challenges? Life goes so fast that much is not so well-planned and rational. I often still think of myself as a young student who just started, and then realize to my own surprise that I have become an ’authority’. The good thing about that is that I can sympathize with the Chinese students which I met at our Workshop and other events in Beijing. How to find your way into the world of research? In my case, I had a joint interest in philosophy and mathematics, and modal logic was an excellent compromise between the two. (This was my own choice: my professors were not all that happy with it.) The origins of modal logic are philosophical, in the study of necessity, possibility, time, and causality. Frege and Russell had thrown these intensional notions out of their modern logic, rejecting Kant’s Table of Categories – but they came back through the work of philosophical logicians in the early 20^th century, and have stayed since then. But also, in my student days, a new movement was starting. Much philosophical logic had become a ‘cottage industry’, away from the logical mainstream, while it occurred to me and others that modal logics were really a special kind of classical systems which could be studied by standard techniques. This led to a mathematical theory of modal logic in the 1970s by my generation, and I still remember the excitement of those days. Major questions for me were exact correspondences between the expressive power of modal languages over relational models and classical, first-order and higher-order, languages describing the same. Others were more into axiomatic completeness, an art I have also practiced, but less often. In the process, a modal model theory was created, as well as systematic connections with universal algebra.

In the 1980s, I spent most of my time on logic and natural language, then a highly exciting new interface, and I lived ‘another life’ studying generalized quantifiers, categorial grammars, and natural logic. But around 1990, I returned to modal logic, partly because some very good students insisted it was my duty to supervise them in areas where I had once been active myself. One’s past always catches up! I found how much things had changed, with computer science becoming a major influence in addition to philosophy and mathematics. In particular, my dissertation work on what is now called bisimulation had been rediscovered in computational process theories, while people were also creating new systems in between modal and classical logic, with a delicate balance between expressive power and computational complexity. (There is a wonderful survey of three independent discoveries of bisimulation in a new LICS paper by Davide SanGiorgi from Pisa.) Through the 1990s, I then worked on understanding this balance of expressive power and complexity, which seems crucial to me in understanding what logical systems are and do. One discovery worth mentioning is the ‘Guarded Fragment’, a very large decidable system in between modal logic and first-order logic whose existence had remained unknown until then.

Right now, most of my work with modal logic is about informational processes and games for rational agents, since I have come to believe that ‘intelligent interaction’ is the heart of logic. This is connected with the spread of logical games for evaluation and bisimulation. And more importantly, this line of research goes back to the original philosophical motivation for modal logic as conceptual analysis of key structures in human cognition. But that is a larger story, which I will not spell out here.

That is it, in a nutshell. There is more about topics and challenges in the introductions which I wrote for this Translations book. If you want to read still more, try the Introduction to the “Handbook of Modal Logic”, written with Patrick Blackburn and Frank Wolter to give a fair impression of the many faces of the field today, and the major interdisciplinary connections influencing it. It may still be a bit in ‘Amsterdam style’, while there are other stories to tell about modal logic, e.g., with more emphasis on algebraic methods. Modal logic is not one unified country. But you can enter it with one story, and once inside, appreciate the other stories of the field.

But really, many challenges in one’s research are just due to chance encounters with students or colleagues who ask unexpected questions, and they also arise through collaborations with people that you respect and, very importantly: like!

Question by Jiangjie Qiu: This is a follow-up to Fenrong’s question. One can talk about the future once one knows about the history. You have been involved in the development of modal logic. Could you tell us what you think of the future of modal logic?

Answer: Jiangjie, I guess you mean that, when meeting one’s mother-in-law for the first time, one’s future suddenly becomes crystal-clear from seeing the past. I am not sure how true this is, but here are some thoughts that your question raises to me.

It has often been said that modal logic had no future, being about to die. When I first came to Stanford in 1983, Situation Theory was the new paradigm, which had won major battles against modal logic, and all that remained to be done were a few mopping-up operations against the last pockets of resistance. But nothing like that has happened! Modal Logic is about patterns of expression and reasoning which are so ubiquitous that they come up in new guises all the time. Ever since it was proposed around 1920, it has kept finding new uses. Some of the latest are ‘description logics’ in knowledge representation around 1990, grammar logics for sentence structure around 1995, and even web languages like XML from around 2000 turn out to have a modal logic core. Moreover, new connections with philosophy are still coming up, witness recent work on logics of freedom and social choice, and the same is true for mathematics, where just last year, new modal results became available about sheaves. I see no signs that this applicability of modal logic is diminishing at all. Indeed, and victory is sweet here, the best mathematical treatises on Situation Theory in the 1990s by Barwise and others turned out to revolve around, essentially, modal techniques!

In particular, I expect that modal logic will play an important role in creating a new theory of ‘intelligent interaction’ with broad sweep and impact. The most elegant systems of information flow and communication today are dynamic and epistemic logics, and also current connections between logic and game theory often run via modal logic. As I said already, this trend continues philosophical logic, and I expect a re-invigorated return to classical questions about modality, predication, and attitudes.

One deep issue are the future mathematical foundations of modal logic. Here I am not so sure what to predict. Modal model theory and algebra is still alive and kicking, witness the new Lindström theorems of my recent work with Balder ten Cate and Jouko Väänänen. But there is also another possible future history for the field, with a paradigm shift (though bisimulation is still there). This is the spectacular work on co-algebra, infinite streams, automata theory, and category theory in recent years. But then, co-algebra also links up with modal fixed-point logics such as the mu-calculus, which are a central theme also in the model-theoretic tradition. Time will tell!

Question by Meiyun Guo: As we can see from our translation project, modal logic has many applications in computer science. In particular, I noticed that in the recently appeared Handbook of Modal Logic, many chapter authors are computer scientists; does this mean that it is getting hard for philosophers to contribute in the study of modal logic? What are the remaining questions that the philosophers still can contribute to? You might know that there are many logicians who work in the department of philosophy in China; can you give us some advice?

Answer: Meiyun, I would say: open the doors! Surely, most logic research today is in computer science, and some people even say that the most innovative logic of today comes from there. But let’s get straight on what this means, and does not mean.

‘Computer science’ today has far outgrown the narrower technical study of programs and machines. Indeed, it has been claimed that computer science is just philosophy ‘continued by other means’. Just go to a conference on Knowledge Representation or on Agents, and you will find that there is some truth to this! I think that philosophers should be allies of computer scientists: at least, of the broad-minded visionary ones. And it is a small scandal that philosophy in the 20^th century has largely ignored the most striking intellectual revolution of all, viz. the tandem of information technology in society and the computational paradigm in Academia. Only now, ‘Philosophy of Information’ is coming to the fore, witness the Handbook on this topic co-edited with my colleague Pieter Adriaans, a classical philosopher who became a successful IT entrepreneur, and afterwards, a professor of learning systems in computer science. Boundaries do not mean all that much today, and philosophers can thrive anywhere!

Now about what you can do as a philosopher. Do not try to be a small mathematican proing the ‘easy theorems’ left over by technical logicians. Of course, it is good to do some technical work to get first-hand inside experience with mathematical methods. And technical experience also helps see through impressive formulas and theorems, and see the real ideas and abstractions. But the best contributions by philosophers use talents that they themselves are best at, such as conceptual analysis, new puzzles, and seeing new perspectives that plain ‘theorem provers’ need not be good at at all. For instance, in modern epistemology or philosophy of action, young philosophers are exploring an ‘open space’of notions with wonderful sensitivity to the subtleties of rational agency and intelligent interaction. Logicians benefit from this in their system construction, but the ideal is really a fruitful symbiosis between equal partners. Indeed, some of the main advances in Amsterdam were contributions by professors and students of philosophy. Think of ’dynamic semantics’ in the study of natural language, or the powerful update schemes of current dynamic-epistemic logic.

In other words, logic gives you a method and abstract iscipline, but do not compete with the mathematicians, and approach things with philosophical sensibility!

Question by Junwei Yu: I want to ask a more concrete question. I have translated your chapter “modal correspondence theory”, first published in the Handbook of Philosophical Logic. In that chapter your studied the relationship between modal logic and first order logic mainly, but what about the correspondence between modal logic and higher order logic?

Answer: Good question. I wrote a bit on this in my introduction to our translations Book. Also relevant is the Appendix in the Correspondence Chapter you translated. But let me try once more, as directly as I can – because you raise a subtle point.

Correspondence Theory is past of the general model theory of modal logic. Now that theory comes in two flavours: first-order over models, and second-order over frames. The first style is the 'standard story' of bisimulation invariance, expressive power vs. computational complexity, and fine-structure of first-order logic, which I mentioned in my answer to Fenrong, and which is also the main line of the “Handbook of Modal Logic”. By now we know a lot about it. The second style, and the main thrust of my book "Modal Logic and Classical Logic", is the fine-structure of (monadic) second-order logic, viewing modal formulas as defining special frame properties. I see this area of as under-developed, partly because classical model-theoretic methods are not available – and Correspondence Theory has not yet blossomed the way I originally hoped for. We have some old landmark results, of course, and Balder ten Cate solved some open problems in his recent ILLC thesis, which won the Ackermann Award of the European Association for Theoretical Computer Science. And there is much other work, for instance, on modal logics over topological spaces, which looks relevant to me. But we do not yet have a good sense of ‘modal fragments’ of second-order logic, partly because we do not know the relevant 'hierarchies'.

Nevertheless, I am also somewhat optimistic. Only recently, I published two papers which showed that there is a genuine hierarchy ‘first-order’, ‘fixed-point-definable’, ‘essentially higher-order’ among modal frame properties, and this throws new light on old correspondence-theoretic questions. In particular, there are lots of questions to ask about fixed-point extensions of the earlier Correspondence Theory. As a by-product of independent interest, Albert Visser and I found that, when viewed in this way, the two major modal-style fixed-point logics, mu-calculus and provability logic, are really very closely related. I think a lot more is waiting to be discovered here!

Question by Xinwen Liu: There is another thing I want to raise, though I am not sure whether my observation is correct or not. When I read papers in modal logic, the issue of complexity is always important. This is different from earlier logic research, which did not pay much attention to complexity. Is this related to the application of modal logics? As there are many such systems, do we need to compare them in terms of complexity?

Answer: Yes, complexity was not on the radar in my youth. We already felt quite virtuous when a logic was decidable in principle! You might think that this new theme is purely practical, but I do not think so. Complexity Theory has made us sensitive to the mathematical fine-structure of decidability, extending Recursion Theory which is mainly about undecidable processes, with its own natural levels and deep questions. In particular, it is a fundamental issue to understand the balance between semantic and algorithmic aspects of any logical system, i.e., the earlier-mentioned expressive power versus computational ‘difficulty’. I would even say that philosophers should pay much more attention to these notions, since complexity is an important notion all across cognitive tasks, interaction, and even organization. Developing huge formal systems without thinking about how they might work seems to do only half the job.

I myself was influenced a lot by our student Edith Spaan who wrote a dissertation in 1993 on complexity of modal logics. Instead of the usual business of results for one system after another, she proved very general theorems analyzing which features of a modal language determine its computational behaviour. That, of course, is what we should be aiming for – and especially, understanding the factors that lead to jumps in complexity from one system to another. Let me be a little bit more precise here. Any logical system has a ‘complexity profile’ for its three core tasks: model checking, satisfiability testing, and model comparison (testing elementary equivalence on finite models). For first-order logic, that profile is, in that task order: ‘Pspace-complete, Undecidable, NP’. For propositional logic, the profile runs: ‘Ptime, NP-complete, and Ptime’. Basic modal logic lies in between, it has less expressive power than first-order logic, but in return, its profile is nicer: ‘Ptime, Pspace-complete, Ptime’. To me, these facts seem a natural companion to expressive power, bisimulation, and other semantic themes. Moreover, they are intertwined. seeing why model-checking modal formulas is not exponential in the modal operator depth, unlike with first-order quantifiers, really gives you an important additional insight in how a modal language works.

Computational complexity is still a new topic, missing in standard logic textbooks. I have been experimenting with introducing it into basic logic courses. E.g., I want to make students see that propositional logic, instead of being just a stepping stone, is itself a rich theory of computation, once you understand the reductions betweenmodel checking and Ptime problems, and satisfiability and NP-problems, as explained in the great textbook by Papadimitriou. And I want them to understand the ‘balance’ and ‘complexity jumps’. But so far, it has not been easy. Maybe you can help!

Question by Meiyun Guo: In recent years you have been analyzing social phenomena by using modal logical tools. But I sometimes feel a little bit worried, since notions like preference, beliefs, expectation, and intention are subjective, does logic really helps us here, and how?

Answer: Aha, ‘soft facts, weak theory’? Or ‘real life, no logic’? Well, I am not guaranteeing success, just claiming that the time is ripe for more ambitious endeavours. And in this, I am not advocating anything idiosyncratic. The move from a focus on mathematical proof and machine computation to describing rational agency in social settings seems quite natural to me. It has been happening in many areas, and the recent convergences between computer science, logic, and game theory show that there is formal substance here. Moreover, I see this research as totally in line with traditional philosophical logic, which has always tried to analyze human-style notions like knowledge, belief, intention, duty, etc. These may be subjective notions, but their theory can be quite precise, witness the work of Hintikka, Kripke, Lewis, Stalnaker, and others. Likewise, even though agents preferences may be totally subjective, the logical theory of those preferences can be very objective! Moreover, studying agency seems a natural continuation of the traditional ‘core agenda’ of logic, as arising out of the study of political debate and legal procedure: both highly interactive social processes. I have argued for this view in a number of programmatic papers, a few of which have appeared or will appear in China, including my lecture at the DLMPS Congress in Beijing, August of this year. In particular, the logical systems describing this social dynamics still conform to all standards of precision that we know.

But your question is also: ‘What good does logic do when applied to human reality’? Well, at a fundamental level, it gives us models for thinking about human behaviour, and bringing out key features. Of course, these models do not capture every part of that behaviour: if you see a person in tears agonizing about a personal decision, decision, theory, logic, and game theory are surely not the whole story. Maybe a poet would do a better job at capturing the essence of that situation. But like game theory, logic offers at least some vantage points from which to understand what is happening, and as such, it adds to our repertoire for seeing us as what we are. Practically, I would even say that this style of analysis might help us improve our styles of behaviour and organization, in line with the ‘social software’ ideas of Rohit Parikh. But these are all words. The proof of ‘fit’ is in looking at what logical analysis actually does! Jan van Eijck and Rineke Verbrugge are editing a book with “Dialogues” following a project on logic and social software at the Netherlands Institute for Advanced Studies in 2006, with many illustrations. You can be the judge of their quality for yourself.