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 $T$ extending the modal logic S4, there exists a topological model $(X, \mathcal{O}X, [-])$ (where $[-]$ satisfies certain conditions to make it an interpretation) that validates all and only theorems of $T$.

A proposition is interpreted as a subset of $X$, and interior plays the role of the necessity operator. A proposition, $P$, is necessarily true at a world if there’s an open neighbourhood of worlds containing that world, at each of which $P$ 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^{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 $Sets$ 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:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/2362

Re: Tarski’s Two Approaches to Modal Logic

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

I don’t suppose ionads could figure in a first-order modal logic. After all, the interior operator, $Int$ is a finite meet-preserving comonad on the power set of $X$, and an ionad is a set $X$ together with a finite limit-preserving comonad $Int X$ on the category $Set^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|$ of sets indexed over a set $|X|$ to the topos $Sh(X)$ of sheaves over a topological space induced by the (continuous) identity map $id: |X| \to X$. The modal operator $\Box$ is interpreted by the interior operation $int$ that the comonad $id^{\ast} \circ id_{\ast}$ induces on the Boolean algebra $Sub_{Sets/|X|}(id^{\ast} F) \cong \mathcal{P}(F)$ of subsets of $F$.(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^{\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 $X$ of points together with a cartesian (i.e., finite limit preserving) comonad $I_X: Set^X \to Set^X$. The category of opens $O(X)$ of an ionad $X$ is the category of $I_X$-coalgebras.

…given any surjective geometric morphism $f: Set^X \to \mathcal{E}$, we obtain an ionad $(X, f^{\ast}f_{\ast})$ whose category of open sets is equivalent (by surjectivity of $f$) 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

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:

http://www.andrew.cmu.edu/user/awodey/preprints/FoS4.phil.pdf

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