[FOM] quantifiers as sentential operators
Vaughan Pratt
pratt at cs.stanford.edu
Tue May 5 06:18:20 EDT 2009
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.
More information about the FOM
mailing list