[FOM] quantifiers as sentential operators

[Vaughan Pratt]

On 4/29/2009 12:18 PM, Alasdair Urquhart wrote:
> It definitely makes sense, because that is exactly the approach
> taken in the theory of cylindric algebras.  It can be
> considered as a form of multimodal logic, where you have
> countably many S5 modal operators, one for each variable.

Oddly the connection with modal logic was not made in Part I of 
"Cylindric Algebras" (1971) [1] and is mentioned briefly in part II 
(1985) [4] only in the last section of the last chapter.

On 5/1/2009 9:21 AM, G. Aldo Antonelli wrote:
> In terms of Kripke frames this is a form of confluence: if you can get
> from world w to world w' by following an x-transition composed with a
> y-transition, then it must be possible to get from w to w' also
> following a y-transition composed with an x-transition.
>
> And since we are pushing the analogy -- what would the worlds be? It's
> clear that they must be assignments to the variables, where an
> x-transition takes you from an assignment w to an x-variant w'.
>
> An interesting line of thought, it seems to me.

In [2], which introduces dynamic logic, I answered Aldo's question "what 
would the worlds be?" with the definition at the bottom of p. 109 of a 
world as an interpretation of symbols.  The translation of \exists X as 
the modal operator <X <-- RANDOM> of dynamic logic first appears on p. 
112 and is subsequently developed in more detail on p. 116, where I 
interpret

"the logical axiom [a](P --> Q) --> ([a]P --> [a]Q) and the non-logical 
\forall Frame Axiom" (namely P --> \forall x.P subject to certain 
syntactic conditions on the appearance of x in P)

as a modal "separation" (deconstruction?) of the axiom

\forall x(P --> Q) --> (P --> \forall x Q) (subject to x not appearing 
free in P)

appearing in Mendelsohn's system K (for the pure predicate calculus) in 
his "Introduction to Mathematical Logic" (1964).

As I put it then, "Despite the elegance of such a compression [of the 
two modal axioms into one predicate calculus axiom], we feel there is 
some intrinsic merit in our [deconstruction]."

In retrospect I could have expressed the meaning of the nondeterministic 
assignment statement "X <-- RANDOM" more formally as the equivalence 
relation relating all pairs of worlds differing only in their 
interpretation of the variable X.  That this is an equivalence relation 
then makes it obvious that [X <-- RANDOM] and <X <-- RANDOM> are S5 
modalities.  (In those days I tended to take for granted as "obvious" a 
lot more than I would now.)

The confluence Aldo refers to above is a consequence of (a) the fact 
that composition of binary relations is commutative for equivalence 
relations, and (b) the dynamic logic laws [a;b]p = [a][b]p and <a;b>p = 
<a><b>p.

In the same year, 1976, Freeman pointed out connections between 
cylindric algebra and modal logic in [3].  But although he mentions 
certain binary relations I didn't recognize any of them as corresponding 
to the relation I called X <-- RANDOM.

Vaughan Pratt


[1]  Henkin, Monk and Tarski, "Cylindric Algebras, Part I", 
North-Holland 1971.

[2]  Pratt, V., Semantical considerations on Floyd-Hoare logic, Proc. 
17th Ann. IEEE Symp. on Foundations of Comp. Sci., 109-121, 1976, online 
as http://boole.stanford.edu/pub/semcon.pdf .

[3]  Freeman, J., Algebraic semantics for modal predicate logic, Z. 
Math. Logic Grundlag. Math., 22, 523-552, 1976 (MR 56#11753), online as 
http://www3.interscience.wiley.com/cgi-bin/fulltext/113465784/PDFSTART 
for institutional subscribers.

[4]  Henkin, Monk and Tarski, "Cylindric Algebras, Part II", 
North-Holland 1985.