Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

February 25, 2011

Tarski’s Two Approaches to Modal Logic

Posted by David Corfield

Can anyone help me out on the question of how Tarski’s work with McKinsey on topological semantics of modal logic connects to Tarski’s work with Jónsson on a duality between modal algebras and (descriptive) general frames.

The Tarski-McKinsey work from 1944 established that

For any consistent theory TT extending the modal logic S4, there exists a topological model (X,𝒪X,[])(X, \mathcal{O}X, [-]) (where [][-] satisfies certain conditions to make it an interpretation) that validates all and only theorems of TT.

A proposition is interpreted as a subset of XX, and interior plays the role of the necessity operator. A proposition, PP, is necessarily true at a world if there’s an open neighbourhood of worlds containing that world, at each of which PP is true.

You can read all about this result and more in Topology and modality: The topological interpretation of first-order modal logic, where Awodey and Kishida prove an analogous result for first-order logic using neighbourhood sheaf models. The worlds are the points of a space, fibres of which are models for the first-order logic.

Now, Tarski also worked on Boolean algebras with operators (BAOs) with Jónsson. This work has has been taken up by the coalgebra community. For example, in Stone Coalgebras the authors show that descriptive general frames are coalgebras for a certain (Vietoris) endofunctor on the category of Stone spaces. Dual to this we find modal algebras (a kind of BAO) as algebras for the opposite endofunctor on Stone opStone^{op} which is equivalent to the category of Boolean algebras.

I suppose a way to compare approaches would come from seeing a topological space as a coalgebra for the functor on SetsSets which sends a set to the set of filters on it. These slides – Topo-bisimulations are coalgebraic – by Christoph Schubert seem to be exactly what I need to look at.

As I was suggesting here, if there’s something to the coalgebraic approach to modal propositional logic, there ought to be a way of taking it over to first-order modal logic, which ought then to bear a resemblance to Awodey and Kishida’s semantics. This would rely on some kind of categorified Stone duality, perhaps one of those described by Forssell and Awodey, or the one Mike tell’s us about here, if that’s distinct.

There’s some idea about that Tarski didn’t see the connection between the two approaches to modal semantics, in which he played such a prominent part. According to Robert Goldblatt here

It appears then that in developing his ideas on BAO’s Tarski was coming from a different direction: modal logic was not on the agenda. According to [Copeland, 1996b, p. 13], Tarski told Kripke in 1962 that he was unable to see a connection with what Kripke was then doing. (p. 18)

This is when Kripke was developing his frame semantics for modal logic.

Posted at February 25, 2011 2:02 PM UTC

TrackBack URL for this Entry:

8 Comments & 1 Trackback

Re: Tarski’s Two Approaches to Modal Logic

Taking a frame as a set of worlds, WW, and an accessibility relation, RR, on WW, we can generate the Alexandroff topology on WW, generated by opens of the form {y|xRy}\{y|x R y\} for worlds xx.

I don’t suppose ionads could figure in a first-order modal logic. After all, the interior operator, IntInt is a finite meet-preserving comonad on the power set of XX, and an ionad is a set XX together with a finite limit-preserving comonad IntXInt X on the category Set XSet^X.

Posted by: David Corfield on February 26, 2011 12:08 PM | Permalink | Reply to this

Re: Tarski’s Two Approaches to Modal Logic

A follow up to the thought that ionads might come into the picture. We have Awodey and Kishida writing

The topological interpretation of this paper was originally formulated in terms of category and topos theory; this paper has served to reformulate it purely in terms of elementary (point-set) topology. In the original expression, we consider the geometric morphism from the topos Sets/|X|Sets/|X| of sets indexed over a set |X||X| to the topos Sh(X)Sh(X) of sheaves over a topological space induced by the (continuous) identity map id:|X|Xid: |X| \to X. The modal operator \Box is interpreted by the interior operation intint that the comonad id *id *id^{\ast} \circ id_{\ast} induces on the Boolean algebra Sub Sets/|X|(id *F)𝒫(F)Sub_{Sets/|X|}(id^{\ast} F) \cong \mathcal{P}(F) of subsets of FF.(p.21)

Although the topological formulation presented here is more elementary and perspicuous, the topos-theoretic one in more useful for generalizations. For example, we see from it that any geometric morphism of toposes (not just id *id *id^{\ast} \dashv id_{\ast}) induces a modality on its domain. This immediately suggests natural models for intuitionistic modal logic, typed modal logic, and higher-order modal logic. (p.22)

Meanwhile in Garner’s paper, an ionad is given by a set XX of points together with a cartesian (i.e., finite limit preserving) comonad I X:Set XSet XI_X: Set^X \to Set^X. The category of opens O(X)O(X) of an ionad XX is the category of I XI_X-coalgebras.

…given any surjective geometric morphism f:Set Xf: Set^X \to \mathcal{E}, we obtain an ionad (X,f *f *)(X, f^{\ast}f_{\ast}) whose category of open sets is equivalent (by surjectivity of ff) to \mathcal{E}. (p. 5)

Posted by: David Corfield on March 1, 2011 10:48 PM | Permalink | Reply to this

Re: Tarski’s Two Approaches to Modal Logic

David wrote:

I don’t suppose ionads could figure in a first-order modal logic.

Should we interpret that as

I do suppose ionads could perhaps figure in a first-order modal logic

? Otherwise it seems a strange thing to mention.

(I ask as a fellow Englishman…)

Posted by: Tom Leinster on March 1, 2011 11:26 PM | Permalink | Reply to this

Re: Tarski’s Two Approaches to Modal Logic

‘You don’t suppose…’ is more standard, I guess, meaning ‘Could it possibly be that…’.

After the two extracts above, I would now opt for ‘It’s very likely that ionads could figure in a first-order modal logic’.

Posted by: David Corfield on March 2, 2011 10:25 AM | Permalink | Reply to this

Re: Tarski’s Two Approaches to Modal Logic

And reassuringly, Mike agrees.

Posted by: David Corfield on March 14, 2011 4:16 PM | Permalink | Reply to this

Re: Tarski’s Two Approaches to Modal Logic

Some references, if I have the chance to come back to this:

  1. A First Order Modal Logic and its Sheaf Models by Barnaby P. Hilken and David E. Rydeheard
  2. Modal and tense predicate logic: Models in presheaves and categorical conceptualization by S. Ghilardi and G. C. Meloni
  3. The Temporal Logic of Coalgebras via Galois Algebras by Bart Jacobs
  4. A Note on Coalgebras and Presheaves by James Worrell, (“…it would be of interest to compare Jacobs’ coalgebraic semantics for modal logic with the analysis of Ghilardi and Meloni.”)
Posted by: David Corfield on March 14, 2011 4:13 PM | Permalink | Reply to this

Re: Tarski’s Two Approaches to Modal Logic

item (1) (Hilken and Rydeheard) is from 1999, I believe. The question of completeness posed at the end of section 4 is answered by the completeness result in the following paper:

Topology and modality: The topological interpretation of first-order modal logic. S. Awodey and K. Kishida, The Review of Symbolic Logic, 2008.

which is here:

Posted by: Steve Awodey on March 17, 2011 4:47 AM | Permalink | Reply to this

Re: Tarski’s Two Approaches to Modal Logic

Yes, I mentioned that paper and result in the main post.

While you’re here, do you have an opinion on fitting Garner’s ionads in with your modal logic semantics?

Posted by: David Corfield on March 17, 2011 9:47 AM | Permalink | Reply to this
Read the post Category Theoretic Modal Logic
Weblog: The n-Category Café
Excerpt: Category theoretic ideas on modal logic
Tracked: April 4, 2011 5:10 PM

Post a New Comment