Urn Logic, Quantification and Modal Logic

March 13, 2015

One of the great pleasures of doing logic is finding problems in one area which can be solved using the techniques and insights from another. What I want to briefly mention here is a neat example of this involving an interesting approach to quantificational logic due to Veikko Rantala called ‘Urn Logic’. The core idea behind urn logic’s semantics for the quantifiers is that the objects which the quantifiers range over can vary over the course of the evaluation of a formula, depending on which objects are selected from the domain by earlier quantifiers. Veikko’s original semantics for this is in the style of Hintikka’s game theoretic semantics, and I’ve proposed a more standard version of the semantics in my ‘A Sequent Calculus for Urn Logic’. What I’m interested in here, though, is a ‘classical’ semantics for Urn Logic proposed by Max Cresswell, and how a question he asks about the expressivity of this semantics can be answered using a very familiar construction from modal logic.

Cresswell’s ‘Classical Exposition’

Cresswell’s semantics for Urn logic, which he articulates in his excellent paper Urn Models: A Classical Exposition, are as follows. A model is a triple $\langle A, D, V\rangle$, with $A$ being a set of individuals (approximately, our initial domain), and $V$ an assignment of extensions to predicate letters (done in the usual manner). All the action in the semantics concerns $D$, which is a function from sequences of objects from $A$ to subsets of $A$. We also change the recursive clause for the quantifiers as follows $$ \langle A, D, V\rangle\models \forall x \varphi[s] \iff \langle A, D, V\rangle\models \varphi[s’] $$
where $s’$ is an $x$-variant of $s$ s.t. $s’(x)\in D(\langle s(x_{1}), \ldots, s(x_{n})\rangle)$ where $x_{1}, \ldots, x_{n}$ are the free-variables in $\forall x\varphi$. For convenience (so that we don’t have to make some kind of choice concerning the order of the free-variables in formulas) we also need to impose the constraint that $D(\langle a_{1}, \ldots, a_{n}\rangle) = D(\langle b{1}, \ldots, b{n}\rangle)$ whenever $b{1}, \ldots, b{n}$ is a permutation of $a_{1}, \ldots, a_{n}$.

What we’re going to focus on here is a constraint on Urn Models which Cresswell singles out in the course of his completeness proof, which we’ll call (Dist.) (in Cresswell’s paper it appears as 4.3)

(Dist.) If $b \in D(\langle a_{1}, \ldots, a_{n}\rangle)$ then $b$ is distinct from each $a_{1}, \ldots, a_{n}$.

Concerning this condition Cresswell has the following to say:

“The satisfaction of [(Dist.)] is interesting because it is not a condition one would want to put on all urn models. This means that there would seem to be no formula which entails that $a_{i} \in D(\langle a_{1}, \ldots, a_{n}\rangle)$ for $1 \leq i \leq n$.” (Cresswell 1982, p.121)

Cresswell is indeed right that (Dist.) is not a condition we want to place on all our urn models. As it happens, though, placing this constraint on our models doesn’t make a difference to the validities of the logic as, given a model $\mathcal{M}$ which doesn’t satisfy (Dist.) we can always construct a model $\mathcal{M^{d}}$ so that for every $\mathcal{M}$-assignment, there is a $\mathcal{M^{d}}$-assignment s.t. $\mathcal{M}$ and $\mathcal{M^{d}}$ agree on which formulas are satisfied.

To demonstrate this we just need to use a construction which is reminiscient of the ‘unravelling’ construction which is often used to show that the class of all irreflexive frames is not modally definable—which is not entirely surprising, considering the extent to which (Dist.) looks like a combination of irreflexivity and antisymmetry on our ‘accessibility relation’. The construction is relatively simple. First let us establish some notation. Given a sequence $s$ and a sequence $s’$ let $s\ast s’$ be the concatenation of $s$ and $s’$, similarly given an object $a$ let $s\ast a$ be the result of concatenating $a$ to the end of $s$. Given a sequence of sequences $s = \langle s_{1}, \ldots, s_{n}\rangle$ say that $s_{i}$ is the maximal element of $s$ iff $s{i}$ is the longest member of $s$. Finally, given a sequence $s$ let $s^{l}$ be the final element of $s$.

The Construction

Suppose that $\mathcal{M} = \langle A, D, V\rangle$ is an urn model. Let $\mathcal{M}^{d} = \langle A^{d}, D^{d}, V^{d}\rangle$ be defined as follows:

It should be fairly obvious to see that $\mathcal{M}^{d}$ is an urn model (all we need to do is check that it satisfies the permutation condition). Readers who are familiar with the model theory for modal logic will notice the striking resemblence between this model construction and the unravelling construction (due, to the best of my knowledge, to either Henrik Sahlqvist or M. Dummett and E.J. Lemmon) which we can use to show (for example) that the smallest normal modal logic K is determined by the class of all trees.

Given urn models $\mathcal{M}$ and $\mathcal{M}^{d}$ let us say that a $\mathcal{M}^{d}$-assignment $s’$ is safe relative to $x1, \ldots xn$ for a $\mathcal{M}$-assignment $s$ if and only if there is a sequence $\langle s{1}, \ldots, s{n-1}\rangle$ of length $n-1$ constructed out of $s(x_{i})$ ($1\leq i \leq n$), and some ordering $\langle a_{x_1}, \ldots, a_{x_n}\rangle$ of $x_{1}, \ldots, x_{n}$, $s’(a_{x_i})=\langle s{1}, \ldots, s{i-1}\rangle \ast\langle s(a_{x_i})\rangle$. Approximately speaking assignments which are safe relative to some variables are ones where the values assigned to those variables could have come from some sequence of legal selections of objects from our model. With this in hand we can then prove that, for all urn models $\mathcal{M}$, assignments $s$ and formulas $\varphi$ we have $$ \mathcal{M}\models\varphi[s] \iff \mathcal{M}^{d}\models\varphi[s’] $$ where $s’$ is safe relative to the free-variables in $\varphi$ for $s$. Given that the condition that $s’$ be safe relative to the free-variables in $\varphi$ for $s$ is vacuously satisfied in the case where $\varphi$ is a sentence we can quite easily conclude that there is no sentence which is true in precisely those urn models in which for all $n$ we have $a_{i} \in D(\langle a_{1}, \ldots, a_{n}\rangle)$ for $1 \leq i \leq n$. In order to show that there is no such formula of any kind we would need to show that for every set of variables $x_1, \ldots x_{n}$ and $\mathcal{M}$-assignment $s$ there is a $\mathcal{M}^{d}$-assignment $s’$ which is safe for $x_1, \ldots x_{n}$. In the great tradition of leaving unknowns as exercises, I leave this as an exercise to the reader.