Contexts in Dynamic Predicate Logic.
In this paper we introduce a notion of context for Groenendijk & Stokhofs Dynamic Predicate Logic DPL. We use these contexts to give a characterization of the relations on assignments that can be generated by composition from tests and random resettings in the case that we are working over an infinite domain. These relations are precisely the ones expressible in DPL if we allow ourselves arbitrary tests as a starting point. We discuss some possible extensions of DPL and the way these extensions interact with our notion of context.
Introduction
Dynamic Predicate Logic (DPL) was invented by Jeroen Groenendijk and Martin Stokhof (see [1], see
also our section 2) as a specification language (or better: as a module for a specification language)
of meanings for fragments of natural language. Most of the research concerning DPL has gone into
integrating it with versions of Montague Grammar (see [5]) and into integrating it with Frank Veltmans
Update Semantics (see [6]).
DPL is a theory of testing and resetting of variables/registers. These are fundamental operations
in computer science. Thus, apart from its use in Logical Semantics, DPL is a simple theory of these
basic operations. 1
DPL is a natural variant of Predicate Logic. It mainly differs in the treatment of the scope of the
existential quantifier. Certain basic truths about variables in Predicate Logic, however, fail in DPL
(see section 2, see also [2] for similar observations on DPLE). The study of DPL and its kin makes the
dependence of these truths on the specific choice of scoping mechanisms in standard Predicate Logic
visible.
In the light of the varied interest of DPL, it seems a good idea to make a closer study of its
metamathematical properties. We focus on the closely related questions:
ffl Which relations between assignments are definable in DPL (in a sense we will specify later)?
ffl How does DPL treat its variables?
To throw some light on both questions a good notion of context in DPL is indispensable. When
studying classical DPL, which is based on total assignments, contexts appear as objets trouv'es. They
are not part of the design of the language, but -as will become clear in the paper- can be viewed
as the result of 'abstracting away' or `erasing' certain properties of the predicate logical language
(both vocabulary and structure), thus yielding an underspecified language. Underspecification simply
means here that the denotations or meanings of the contexts are properties of relations, rather than
relations.
1 DPL is just one theory in a family of alternatives to predicate logic. In these alternatives 'resetting a register' is
replaced by other related actions, like 'create a new register'. See section 7 for references.
We can view what happens in the paper in a different light. Our deeper interest is in such grand
questions as:
ffl What should a general theory of information processing look like?
ffl What is the nature of the variable?
It seems to me that these questions are closely related and that ideas involving both Dynamics and
Contexts should play a role in the answer. The study of DPL, here, is analogous to the study of a
fruitfly in a laboratory situation. It allows us to focus on problems involving dynamics, variables,
information processing. Still, these problems remain feasible.
We end this introduction with a brief sketch of the paper. Section 2 is a straightforward introduction
to predicate logic. It contains all the technical material the reader needs to know. For a discussion of
the applications to discourse phenomena, however, the reader should consult [1]. Section 3 presents
our theory of contexts in DPL. We study contexts as mathematical objects in their own right and
establish their connections to language and semantics. Some materials concerning the information
ordering on contexts are placed in an appendix. In section 4, we treat the Switching Propery. This
property is characteristic for the DPL-definable relations. Section 5 contains the main result of the
paper: a relation over an infinite domain is DPL-definable iff it 'has' a context and satisfies the
Switching Property. In the next section, we touch on the subject of extending the DPL-language
with new operations such as conjunction and disjunction. We consider the question whether such
extensions support a good theory of contexts. We will produce two extensions that are complete for
all relations that have a context. In other words: all such relations are definable in those extensions.
Our last section 7 is devoted to the idea of making the context part of the semantics.
2 What is Dynamic Predicate Logic?
We provide the basic definitions of DPL. Nothing in this section pretends to be original. We start by
introducing some basic relational notions.
Definition 2.1 Let X be any non-empty set. Rel(X) is the set of binary relations on X , i.e.,
X). Let R; S 2 Rel(X ). We define:
1. The composition R ffi S of R and S is defined by: x(R ffi S)y :, 9z xRzSy. Note that composition
is in the order of application.
2. The dynamic implication (R!S) between R and S is defined by:
x(R!S)y
Our use of ! here overloads the symbol, since we also use it for implication in the objectlanguage.
We write :(R) for (R ! ;)
3. id X is the identity relation. R is a condition or test if R ' id X .
4. Consider Y ' X . We define diag(Y g.
5. dom(R) := fx2X j 9y xRyg and cod(R) := fy2X j 9x xRyg.
The notion of dynamic implication was first introduced by Hans Kamp in his pioneering paper [4].
Note dom(R). The relations in the range of diag are precisely the
conditions. Writing (Y ! Z) := (XnY ) [Z, we have:
Thus, diag is a homomorphic embedding of the structure h-X ; in the structure
We will sometimes confuse, in the relational context, the set X with
the relation diag(X). We need some further relational notions specifically concerned with relations
between assignments.
Definition 2.2 Let D be a non-empty domain and let Var be a set of variables. Let R2Rel(D Var ),
We define:
is the result of changing the values of f on the v i to d i .
I VarnV . We write [v] for: [fvg].
ffl Y is an hV i-set if f 2 Y and fI V g ) finitely restricted if Y is a hIi-set for some
finite I . A condition is finitely restricted iff it is the image of a finitely restricted set.
If we want to make the dependence of I or [:] on Var or D visible, we add them as subscripts.
We collect some simple facts concerning these notions. We have:
Note that the classical meaning of the existential quantifier as a 'cylindrification' can be given as:
We turn to the definition of DPL.
Definition 2.3 A DPL-language L is a structure hPred ; Ar ; Var ; Coni, where Pred is a set of predicate
symbols; Ar is a function from Pred to the natural numbers (including 0); Var is a, possibly
empty, set of variables, Con is a, possibly empty, set of constants. Let Ref := Var [Con be the set
of referents. We will use v; constants and referents. The set
of L-formulas, For L , is the smallest set such that:
are in For L for
ffl If OE; / 2 For L , then so are OE:/ and (OE ! /)
I feel that it is more faithful to the semantics to leave out the brackets in the formation rule for
the dot officially, but nothing important hangs on this choice in this paper. We get an ambiguous
syntax, but still unique meanings, since the operation of composition -the semantic counterpart of
"."- is associative. An alternative notation for 9v, is [v :=?] (random reset). We use :(OE) and 8v(OE)
as abbreviations of, respectively, (OE ! ?) and (9v ! OE). If x 2 Var and r 2 Ref and x and r are
distinct, we write [x := r] for:
Definition 2.4 A DPL-model M for a DPL-language L is a structure hD; Ii, where D is a non-empty
set, the domain of M; I is a function which assigns to each predicate symbol P of Pred L an Ar(P)-ary
relation on D and to each constant c an element of D. AssM , the set of assignments for M, is D Var .
Consider r 2 Ref . We define:
ae
The interpretation function [:] M : For
We write OE jM / for [OE] . We define validity in DPL by:
As usual, OE appropriate for the given language.
binary relation R is definable in a DPL-model M for a language L if there is an L-formula OE,
which defines R, i.e.,
We will often suppress the subscript M, when the model is clear from the context. We could extend
the DPL-language with function symbols by copying the way this is done in ordinary predicate logic.
However, for the kind of result we are after such an extension is immaterial, since the usual trick to
eliminate function symbols works also in DPL -with a small twist. E.g., P (f(g(x))) will be translated
to: ::(9u:G(x; u):9v:F (u; v):P (v)).
We remind the reader of Geach's Donkey Sentence: If a farmer owns a donkey, he beats it. This
sentence can be translated into DPL in a compositional way as:
One striking feature of DPL is that it is not 'structural': the values the predicate symbols may
assume are not all the possible meaning objects provided by the semantics; we only allow tests. A
second striking feature is the time symmetry of resetting and composition, which constrast strongly
with our time asymetric intuition about, say, the meaning of P (x):9x:Q(x). The asymmetry of our
intuition may be explained by the fact that we tend to think more in terms of successful resetting,
just in terms of what the resetting relation is.
Ordinary predicate logic can be interpreted in DPL as follows. We suppose that the predicate
logical language has as connectives and quantifiers: ?, ?, -, !, 9x. We translate as follows:
ffl (:)   commutes with atomic formulas and with !
We find: [OE   is the usual valuation function of Predicate Logic. Our
translation is compositional. It shows that we may consider Predicate Logic as a subsystem of DPL.
There is also a kind of inverse translation (:) ffi , which satisfies: [[OE
involves renaming of variables and cannot be taken to show that DPL is a subsystem of Predicate
Logic.
3 Contexts for Dynamic Predicate Logic
In this section, we study the notion of context and its connections with relations and language. We
placed some materials concerning the information ordering on contexts in an appendix, since, on the
one hand, they are conceptually relevant and have a clear place in the total picture, but, on the other
hand, they have no direct bearing upon the main results of the paper.
3.1 Introductory remarks
To motivate our notion of contexts, we first give an intuitive discussion about substitution and kinds of
variable occurrences in DPL. 2 In Predicate Logic variables may occur in a formula in two ways: freely
and bound. The free variables admit (under certain conditions) substitution. The bound variables
may be renamed salva significatione (ff-conversion). Let's write oe t
x (OE) for: the result of substituting
t for x in OE. In Predicate Logic we have, e.g.,
f I(c)
What is the proper analogue of this fact for DPL? To simplify the discussion we will only treat a special
case and refrain from giving official definitions. Consider the DPL-formula P (x):9x:Q(x):9x:R(x). We
1. f I(c)
2. f [P (x):9x:Q(x):9x:R(x)] M g I(c)
Meditation upon (1) and (2) suggests, that, in DPL, we have to distinguish two kinds of substitution
left substitution and right substitution and corresponding to these kinds two kinds of 'free occurrence':
right free. We also speak of input occurrences and output occurrences. Following temporal
intuitions -ignoring the essentially time-symmetric character of resetting and composition- we may
also call the left free occurrences simply free and the right free occurrences actively bound. Now
consider the following formula, say OE 0 , in which we have tagged occurrences of x with superscript
numerals.
We see that x 1 is a (left) free or input occurrence. Left substitution for x will cause it to be replaced. If
we form T in the semantics the values assigned to x 0 and x 1 will be unified. If we form 9x:OE 0 ,
x 1 will be 'bound' or `initialized' by the new 'quantifier'. Symmetrically, x 7 is right free or actively
bound. It will be in the scope of right substitution. If we form OE 0 :T the values of x 7 and x 0 will
be unified, If we form OE 0 :9x, x 7 will be 'aborted'. Neither x 1 nor x 7 are open to ff-conversion salva
significatione. x 3 is not accessible for substitution, nor is it ff-convertible: replacing x 2 , x 3 and x 4 by,
say, y, will result in a formula that resets y, which OE 0 doesn't do. We call x 3 a garbage occurrence:
it is something that 'exists', but is no longer `used'. 3 x 6 is also inaccessible for substitution, but in
addition it can be ff-converted: replacing x 5 and x 6 by y does not change the meaning of OE 0 . We say
that x 6 is clasically bound. Finally, we consider x 2 , x 4 and x 5 . These are 'occurrences' in a purely
syntactical sense only: they do not represent 'files' carrying information, but just signal that incoming
files labeled x should not be 'unified' with outgoing files labeled x. We say that these `occurrences'
are blockers. x 5 is not a blocker in OE 0 as a whole. 4
2 The subject of kinds of variables and substitution would merit a far more extensive discussion. Regrettably, such a
discussion is beyond the scope of the present paper.
3 The notion of garbage is studied in [8] and in [9]
4 Even if Vermeulens DPLE (see [7]) is quite close to DPL, the discussion of kinds of occurrences would be very
different.
Contexts, in our present set-up, signal the presence of input occurrences, of blockers and of output
occurrences. 5 They are abstract -in comparison with formulas- in the sense that they contain no information
about the number or the place of these occurrences. Contexts can be studied independently
from their connection with the logical language.
Contexts are familiar from Predicate Logic. There the context associated to a formula OE is simply
the set F of free variables of OE. 6 A salient property of contexts in Predicate Logic is as follows.
Suppose F is a context for OE, then
Most of the work in this section will be devoted to proving the appropriate DPL-analogue of this
property of Predicate Logic.
3.2 Contexts, considered by themselves
In this subsection, we treat contexts as mathematical objects in their own right. The natural connection
with DPL will surface in the subsequent subsections.
Definition 3.1 A DPL-context is a triple hI ; B; Oi, where I , B and O are finite sets of variables
and where equivalently, I [B. The set I is the input set, i.e., the set on
which the incoming assignments are constrained. The set O is the output set, i.e. the set on which
the outgoing assignments are constrained. Finally, the set B is the set of blocks. This is the set
of variables for which the identity between input and output value is cut through. The 'block' is a
barrier between past and future, breaking the link between input- and output-value. We write # for
is defined or converges, and " for is undefined or diverges. Define:
ffl id := h;; ;; ;i
" is a partial operation on contexts, defined by:
" otherwise
We will use c, d, . as variables over contexts. We write I c for the first component of c, etcetera.
The meanings of these objects, relations and operations will become apparent in subsection 3.3.
Lemma 3.2 The operations ffl, ! and " are well defined.
Proof
To see that ffl is well defined, note that:
5 In fact, there are good reasons also to put witnesses of garbage into the contexts. We will do not this in the present
paper, since it is not necessery for our results here. Moreover, adding garbage leads to considerable complication of the
framework and it necessitates bringing in Category Theory. We refer the reader further to [9].
6 The reader is referred to [3] for a category-theoretical framework appropriate for the study of contexts in Predicate
Logic.
It is trivial that ! is well defined. For the proof that " is well defined we refer the reader to the
appendix. 2
Theorem 3.3 The contexts with id and ffl form a monoid. Moreover, - is a partial ordering.
The proof of the theorem is easy. In the appendix we will show that " , if defined, is the infimum,
w.r.t.
Consider the monoid of contexts. It can be represented in an alternative way, as follows. The
monoid A is the monoid on two generators a and b, given by the equations: a ffl a
b. The tabel of the monoidal operation ffl is a follows.
ffl e a b ab ba aba
e e a b ab ba aba
a a a ab ab aba aba
ab ab aba ab ab aba aba
ba ba ba b b ba ba
aba aba aba ab ab aba aba
The monoid of contexts is now given as the set of functions from Var to A that are on all, but finitely
many arguments equal to e. We put: (f ffl g)(v) := f(v) ffl g(v). A triple hI ; B; Oi 'translates' to a
function f with, e.g., translates to a triple
abag, etcetera. It is easily seen that these 'translations'
give us an isomorphism of monoids between the representations. A is in fact isomorphic to the monoid
of contexts in the case that fxg. The alternative representation is possible by the fact that in
our monoidal operation treats all variables 'independently'. It is not difficult to extend the structure
on to get a function representation also for !, - and " .
In this paper we will stick to the set representation, since this representation is closest to the
relational notions we will need to formulate our theorem on contexts and relations -the theorem that
tells us what the contexts do. The function representation, however, has two advantages. First, it
is easier to use for doing computations 'in the head'. Secondly, its connection with the framework
developed in [9] to study contexts, is more perspicuous.
3.3 Contexts and relations
We turn to the connection between contexts and relations. 7 We show that this connection 'commutes'
w.r.t. ffl=ffi, !=! and -='. We fix a non-empty domain D.
Definition 3.4 Consider a relation R on D Var . R is an hI ; B; Oi-relation if
We say that c is a context for R, if R is an c-relation. R is an IBO-relation if R is an hI ; B; Oi-
relation for some hI ; B; Oi. We assign to each context c the property or 'meaning' fcg D , the set of all
c-relations on D Var . (We will often suppress the subscript D.)
The heuristic for this property is as follows. R is means that R is only concerned with the
values of the incoming assignment on I ; R only cares about the values of the outgoing assingment on
O; all this under the constraint that in going from input to output only values of variables in B are
changed. Before proving some facts about the notion introduced above, we sample some immediate
insights.
7 The semantics for contexts given here certainly does not exhaust all possible uses of contexts. E.g., the problem of
explaining what it is to be a variable occurrence of a certain kind is left untouched. Undoubtedly, contexts will play a
role in solving this problem.
ffl R is a hI ; ;; Ii-relation precisely if R is an hIi-condition.
We show that - on contexts describes the 'information ordering' on contexts. The idea is simply that
c is more informative than d if fcg ' fdg.
Theorem 3.5 1. c - d ) fcg ' fdg.
2. Suppose jDj - 2. Then: fcg ' fdg ) c - d.
Proof
We prove (1). Let c - d and R 2 fcg. We want to show:
Trivially, R is contained in (I I 0 show I I 0
. It is immediate, that f 0 I I fRgIO g 0 . We show that f [B]g.
Suppose
since fRg, R ' [B] and v 62 B. Finally, . Since R is a c-relation, we may
conclude that f 0 Rg 0 .
We prove (2). We write X c for VarnX . Let jDj - 2 and fcg ' fdg. Since, [B] 2 fcg, we have
fdg. Hence, using the facts of page 3, we find:
[B [O
Now it is immediate
The arguments that I ' I 0 and that O ' O 0 are analogous to one another. We give the argument
for the I-case. Suppose, for a reductio, that v 2 InI 0 . Let d and e be distinct elements of D. We
for the test: is f(v)=d?. Consider the relation R :=
so, R 2 fdg. Consider f with In case v 2 B 0 , we have: f e
I I 0 fRgIO 0 g. Since, as we have
already shown,
]g. Hence, since R 2 fdg, we have f d
Rg. Quod non. We turn
to the case that v 62 B 0 . Since I 0 nB
I I 0 fRgIO 0 g e
we find f e
. Thus, since R 2 fdg, we have f d
v . Quod non. 2
Theorem 3.5 shows clearly that contexts stand in a many-many relation to relations. Thus, the
question What is the context of R? has no definite answer. In the appendix we show that, but for one
notable exception, every relation has a most informative context. The next lemma may be used in
some cases to simplify the verification that a relation is hI ; B; Oi.
Lemma 3.6 R is a Oi-relation
Proof
It is clearly sufficient to show that for any R ' [B]:
I
?From left to right is immediate, since IO ' IO " B . For the converse, suppose f 0 I I fRgIO " B g 0 and
We have to show: gIO g 0 . Consider v 2 O. In case v 2 B, we have
I . Also since fRg, R ' [B] and v 62 B. Putting the identities together, we find
The following lemma is quite useful in applications (see example 3.14). We write A := I [B.
Lemma 3.7 Suppose R is an hI ; B; Oi-relation and f 0 I I fRg. Then there is a unique g 0 , such that
g. This g 0 has the following property: for any set of variables J , if f 0 I J f , then g 0 I J g. As a
consequence, we find that g 0 I I g and, hence, g 0 IA g. So, also, g 0 IO g.
Proof
Let R be an hI ; B; Oi-relation with f 0 I I fRg. Any g 0 with f 0 Rg 0 IB g, must satisfy: f 0 [B]g 0 IB g. So
the only possible choice of such a We verify that g 0 , thus defined, satisfies
. It is sufficient to show that gIO g 0 . This, in its turn, follows immediately from the property in
the last part of the theorem.
Consider any set J such that f 0 I J f . Suppose v 2 J . In case v 2 B, we have (v). In case
Finally f 0
since v 62 B. Putting things together, we find
Note that in the lemma O plays no significant role. Due to the 'forward looking' and time asymmetric
nature, however, of the definitions of implication and validity in DPL, it is sufficient for most
applications. An immediate consequence of the lemma is that if R is an hI ; B; Oi-relation, then
dom(R) is an hIi-condition and (by symmetry) cod(R) is an hOi-condition.
Theorem 3.8 Suppose R is a c-relation and S is a d-relation. Then R ffi S is a c ffl d-relation.
Proof
It is easy to see
(R
For the converse, suppose that f 0 [B 00
We have to show: f 0 (R ffi S)g 0 . For some h, we have fRhSg. We
partition Var into three sets
We show that f 0 Rh 0 Sg 0 . We first prove that f 0 Rh 0 . We check
the conditions for applying the fact that R is an hI ; B; Oi-relation.
1. f 0 I I 00 f and, hence, since I ' I 00 , f 0 I I f .
2. fRh.
3. hIO[ I 0 h 0 and, hence, hIOh 0 .
4. We show that f 0 [B]h 0 . Consider a variable v not in B. We have to show f 0 (v). We can
only run into trouble in case v is not in X 3 , i.e., if v is in BnB 0 or in O [ I 0 . The first possibility is
excluded, by the fact that v is not in B. Suppose v is in O [ I 0 . Then: h 0
R is an hI ; B; Oi-relation, so R ' [B]. We may conclude that In case
I 00 . In case v 2 I 0 , we find: v 2 I 0 nB ' I 00 . So in both
cases: v 2 I 00 . Since f 0 I I 00 f , it follows that (v). Composing the identities, we find
By (1)-(4), we may conclude that f 0 Rh 0 . Next, we check the conditions for applying the fact that S
is an hI
1. We have hIO[ I 0 h 0 and, hence, h 0 I I 0 h.
2. hSg.
3. We have gIO 00 g 0 and, hence, since O 0 ' O 00 , gIO 0 g 0 .
4. We show that h 0 [B 0 ]g 0 . Consider a variable v not in B 0 . We have to show h 0
Inspecting the definition of h 0 , we see that our desired identity can only fail if either v 62 B or
. We consider the case that v 62 B. We already showed that f 0 [B]h 0 .
Moreover, we assumed f 0 [B 00
we find: h 0 (v). Next, we consider the case that v 2 B and v 2 O [ I 0 [B
we choose v outside of B 0 , we need only consider the possibility that v 2 O [ I 0 . We have, by
our early assumption, gIO 00 g 0 ,
where O
we have v 2 I 0 nB (v). Putting the identities together,
we find h 0
By (1)-(4), we have: h 0 Sg 0 . 2
Theorem 3.9 Suppose R is a c-relation and S is a d-relation. Then R ! S is a c!d-relation.
Proof
Suppose R is a c-relation and S is a d-relation. Let
Trivially, (R ! S) ' [;]. Moreover, since id ' I I 00 , (R
To prove the converse, suppose f 0 I I 00 f and f(R ! S)f . We have to show that f 0 (R ! S)f 0 .
Suppose f 0 Rg 0 . By lemma 3.7, there is a g such that fRgI I 00 [B g 0 . It follows that g 0 I I 0 g. Since
, we can find an h, such that gSh. Again applying lemma 3.7, we find an h 0 with g 0 Sh 0 .We close this subsection with a language-free soundness result.
Definition 3.10 A relation on D Var is DPL-definable over D iff it can be generated by composition
from resettings [v] and finitely restricted conditions over D
Theorem 3.11 Every DPL-definable relation over D is an IBO-relation.
The proof is an obvious induction on the way the relation is generated.
3.4 Contexts and language
We turn to our discussion of how contexts are connected to formulas.
Definition 3.12 We assign to every DPL-formula OE a context c OE . Define:
We write I OE for I c OE
, etcetera.
Note that the definition correctly defines a function, by the associativity of ffl. We now prove the main
theorem of this section.
Theorem 3.13 For every formula OE, [OE] is a c OE -relation on D Var .
Proof
The proof is by induction on OE using theorems 3.8 and 3.3. The atomic cases are easy. 2
We obtain the following picture of the way contexts work: OE is mapped to c OE by abstracting both from
part of the vocabulary and part of the structure. c OE is mapped to fc OE g D , a property of relations. Via
a different route OE is mapped to the relation [OE] M . The two routes are connected by the theorem that
Note that c OE is not always the -minimal context of [OE] M , as is witnessed by the fact that c
is the identity on D Var , thus admitting the context h;; ;; ;i
Example 3.14 We provide two examples of how theorem 3.13 in combination with lemma 3.7 can
be used to verify a valid principle for DPL. We first prove:
Suppose [-:OE]g. We have to produce an h with g[OE]h. Since f [-:OE]g, we can find
a j with j[OE]g. By theorem 3.13: j[B OE ]g. I OE j. So, gI I OE j[OE]g. By
theorem 3.13 and lemma 3.7 we can find an h with g[OE]h.
As a second example we prove:
Suppose [-]g. We have to produce an h with f [/]h. By our assumptions,
there are i and j such that f [OE]i[/]j. Hence, f [B OE ]i and so fI I /
i. Thus, fI I /
i[/]j. We may conclude
that there is an h with f [/]h.
The examples demonstrate the role contexts must play in the formulation of schematic principles
for DPL.
4 The Switching Property
In section 3 we introduced contexts or IBO's as properties of relations and showed that every [OE] is an
IBO-relations. A first conjecture for characterizing the DPL-definable relations would be that these
are precisely the IBO-relations. We will see, however, that this conjecture is false. To characterize
the DPL-definable relations we need one extra property: the Switching Property. In the present
section we will prove that the DPL-definable relations do have the Switching Property (soundness).
In section 5 will will show that every IBO-relation on an infinite domain that has the Switching
Property is DPL-definable (completeness).
Definition 4.1 A relation R on D Var has the switching property if it is either a condition or there
are variables x and y (not necessarily distinct), such that cod(R). If the
second case obtains, we call the variables x and y involved a pair of switching variables. There might
be more than one pair of switching variables.
There are various other ways to define the Switching Property, but, I submit, the one presented here
is the most natural one. In the lemma below, we collect some helpful insights.
Lemma 4.2 Suppose R is a relation on D Var
1.
2. Suppose R is C are conditions and where T is a relation. Then
dom(R)
3. Suppose C is a condition. Then, C
The easy proof is left to the reader.
Theorem 4.3 Every DPL-definable relation over D has the switching property.
Proof
In case R is a condition, we are done. Suppose R is not a condition. As is easily seen, R must be of
the form C y, some conditions C, C 0 , and some relation S.
(In a formula OE defining R, x would correspond to the first existential quantifier occurring in OE, y to
the last. Note that we allow x and y to be the same variable and even the first and last existential
quantifier occurrence to be the same occurrence.) We have, using lemma 4.2:
dom(R)
dom(R)
dom(R)
dom(R) RThe results of section 3 and of this section combine to the obvious 'soundness'-result:
Theorem 4.4 Every DPL-definable relation over D is an IBO-relation with the Switching Property.
Example 4.5 We show how to use the Switching Property to prove that certain relations are not
DPL-definable. Suppose jDj - 2.
ffl Let R := [x :=
x;y . R is an IBO-relation,
with context hfx; yg; fx; yg; fx; ygi. Suppose R has the Switching Property. R is evidently not
a condition. Let v; w be a pair of switching variables. Let fRg, d, and d 6= e. Using the
fact that the domain of R is the set of all assignments, we find:
Hence, by the switching property: f e
Rg. But R is obviously injective. So we have a contradiction

Suppose our model M is the usual structure of the natural numbers. Let S := [x := x
x . S is an IBO-relation with context hfxg; fxg; fxgi. S
does not have the Switching Property since: S is not a condition; S has as domain the set of all
assignments; S is injective.
is an IBO-relation. Surprisingly, the best
context we can find for it is hfx; yg; fx; yg; fx; ygi. 8 Suppose that T has the Switching Property.
T is not a condition, so we can find switching variables v and w. By symmetry we may assume
that v 6= x. We can find f and g with fSg and f(x) 6= g(x). Choose d with d 6= g(v). Using the
fact that the domain of T is the set of all assignments, we find:
f d
By the Switching Property: f d
g. But we have two distinct variables x and v such that
f d
g(v). This is clearly impossible.
8 We will discuss this fenomenon in more detail in subsection 6.3.
5 The DPL-definable relations on an infinite domain
In sections 3 and 4 we have seen that the DPL-definable relations are IBO-relations with the Switching
Property. Here we show the converse -for the case that the domain, D, is infinite.
Theorem 5.1 Let D be an infinite set. Then the DPL-definable relations over D are precisely the
IBO-relations with the switching property on D Var .
Proof
One direction is by our previous results. Let R be an hI ; B; Oi-relation with the switching property.
In case R is a condition we are done. Suppose R is not a condition and let x, y be a pair of switching
variables. By the switching property cod(y). Note that dom(R) is an
hIi-condition and that cod(R) is an hOi-condition. Thus, it is sufficient to show that [x]
DPL-definable. [x] is an hInfxg; B; Onfygi-relation, where x; y 2 B. After renaming, we
see that it is sufficient to prove that any hI ; B; Oi-relation R, with x; y 2 B and x 62 I and y 62 O is
DPL-definable.
We will assume x 6= y. In case y, the proof is simpler. To increase readability, we will specify
R in a DPL-language that we introduce along the way. Suppose
g. Here the i k are supposed to be mutually distinct and similarly for the
other sets. Since D is infinite there is a coding of finite sequences of elements of D in D. Par abus de
langage, we will confuse this coding with our ordinary sequences of elements of D. Our language has
an (m 1)-ary predicate symbol P , where:
Remember that [y := x] is short for 9y:y = x. The formula OE is given by:
Here stands for the obvious condition. Note that [OE] is an hI ; B; Oi-relation. We
claim that R = [OE]. Suppose first that fRg. Take:
x .
Remember that x 62 g. We have:
Clearly, f and g witness that hf(i 1 )ii is in I(P ). Next we set:
y
We find (using y 62
Since f [B]g, it is easy to see that
For the converse, suppose f 0 [OE]g 0 . Let h 1
, be such that:
We are going to apply the fact that R is an hI ; B; Oi-relation. By the fact that h 1
and by the definition of P , we can find f and g such that fRg, f(i 1
(x). Since x 62
, it follows that f 0 I I f . Collecting what
we have, we see:
fRg.
By lemma 3.6 we need to check:
Consider
y 62 O, we find: h 3
Finally, v is not among the b
Putting the itemized insights together, we may conclude: f 0 Rg 0 . 2
6 Extensions of the DPL-language
We consider three extensions of the DPL-language. One with conjunction interpreted as intersection
of relations, one with a new quantifier 99 and one with disjunction interpreted as union of relations. We
will show that our contexts work for each of these extensions. The contexts provided for disjunction
are not optimally informative and intuitively queer, however. We will give some hints on how we think
this apparent defect should be repaired. We show that 99 is definable using - and that in the system
with 99 all IBO-relations are definable.
6.1 Conjunction
We study the effect of adding intersection of relations to the DPL-repertoire. One way of of thinking
about R " S is as: reset simultaneously via R and via S, and compare the results. If they are equal,
make the output of our new relation the shared output, otherwise abort. At the syntactical level, we
reflect the new operation by extending the language of DPL by adding the clause:
ffl If OE; / 2 L, then (OE-/) 2 L.
We will call the new language: L(-). The semantic clause is: [OE-/] := [OE] " [/]. We define intersection
of contexts as follows.
Note that:
I
So - is a well-defined operation on contexts. We define:
Note the difference between - and -. It is easy to see that - is precisely the infimum with respect to
-.
Theorem 6.1 Let R be a c-relation and let S be a d-relation. Then, R " S is a (c-d)-relation.
Proof
Suppose that the conditions of the theorem are fulfilled. Let
. Suppose f(R " S)g. It follows that f ([B] " [B 0 ])g,
(R " S) ' (I I 00
For the converse, suppose f 0 I I 00 f ,
We extend the definition of c OE to the new language by adding the clause c (OE-/)
Theorem 6.1
immediately yields the next theorem.
Theorem 6.2 [OE] is a c OE -relation for every OE2L(-).
We consider an example. Let c
g. Let / := (OE:9b 1
We have:
Thus, in this example our conjunction on contexts, gives us the 'intuitive result', i.e., [/] is an I-
condition.
Let's say that the DPL(-relations over a given domain D are the relations on this domain generated
by finitely restricted conditions and resettings using composition and intersection. The results of the
present section show that the DPL(-relations are all IBO-relations. The results of the next section,
will imply that, conversely, every IBO-relation is DPL(-).
6.2 A new existential quantifier
We define: 99x(R) := ([x] In case R is an hI ; B; Oi-relation, we see that 99x(R) := ([x] ffi
" [Bnfxg]. It follows -by the result of subsection 6.1- that 99(R) is an hInfxg; Bnfxg; Onfxgi-
relation.
We extend the language of DPL by adding the clause:
ffl If OE 2 L and v 2 Var then 99v(OE) 2 L
Note the overloading of notations. The new language will be L(99). The new semantical clause is
the obvious: [99vOE] . 99v is definable in L(-) as follows. Suppose c
then we can put (9x:OE:9x - 9b
Theorem 6.3 For any non-empty domain D, the DPL(99)-definable relations are precisely the IBO-
relations.
Proof
[Sketch] We have already seen that every DPL(99)-definable relation is IBO. For the converse, suppose
that R is an g.
Here the i k are supposed to be mutually distinct and similarly for the other sets. Take a DPL(99)-
language with an (m p)-ary predicate symbol P , where:
and f(o 1
Let be variables disjoint from I [B [O. Let OE be given by:
Clearly, that [OE] is an hI ; B; Oi-relation. The verification that R = [OE] is along the lines of the proof
of theorem 5.1. 2
Example 6.4 We show how to define the three relations of example 4.5. We do a bit more than the
theorem promises, because we give explicit descriptions of the 'P '.
can be defined by:
Note that this gives us the expected context: hfx; yg; fx; yg; fx; ygi.
can be defined (Strictly speaking we are working
in a relational language, so suggestive notation for, say, S(v; x).) The context
produced by the formula is as expected.
ffl We can define [(9x-9y)] by:
This gives us the context hfx; yg; fx; yg; fx; ygi. We will discuss this context in the next subsection

Since 99 is definable using -, the 'expressive completeness' of 99 w.r.t. the IBO-relations implies the
'expressive completeness' of -. Finally, we can translate Predicate Logic into DPL(-), by changing the
9-clause of our earlier translation to: (9(OE))   := 99(OE   ). Remarkably, the old and the new translation
produce precisely the same relations at the semantical level.
Operations like !, - and thereis are not themselves actions in the sense of our semantics. They
are transformers of actions. Yet there is a tendency to understand 99x(OE) dynamically as a sequence
of actions: reset x; execute OE; set x back to its original value. The problem with this way of viewing
things is summarized with the question: where do we store the original value of x, so that we can
restore it at the end? DPL-semantics does not supply the right kind of 'memory' to realize 99(OE) as a
sequence of actions. We can do that (or, rather, something very much like it) in the richer semantics
of Kees Vermeulen's DPLE (see [7]), where under a variablename we do not store just one value, but
a stack of values. Here the original value of x is simply stored 'under' the new one.
RELATIONS IN CONTEXT 17
6.3 Disjunction
In this section we have a brief look at the problem of adding disjunction/union to DPL. Adding
disjunction/union evokes problems that are definitely beyond the scope of the present paper. So we
can only offer some tantalizing remarks.
One way of of thinking about R[S is as: Choose between R and S, and reset via the relation chosen.
At the syntactical level, we reflect the new operation by extending the language of DPL by adding
the clause:
ffl If OE; / 2 L, then (OE-/) 2 L.
We will call the new language: L(-). The semantic clause is: [OE-/] := [OE] [ [/].
What could be a context for [x] [ [y]? Some experimentation shows that the best we can do is:
This seems a wasteful way to represent the variable handling of this relation.
Our intuition tells us that [x] [ [y] is a pure resetter and not something that 'constrains' w.r.t. x and
y. The resetting part of our contexts is somehow too crude to represent 'choice' well. The example
does not tell us that in any strict sense our present framework is wrong. It just suggests that, possibly,
we could do better. We might try out richer notions of context. The most obvious proposal is to take
as a context in the new sense a set of contexts in the old sense, where the set is given 'disjunctive
reading'. 9 So, e.g., we would have:
c (9x-9y):P (x;y)
Note that e.g. the second occurrence of x in (9x-9y):P (x; y) seems to be ambiguous between free
and actively bound. So what is an ambiguous occurrence and how do we handle it theoretically? We
propose to addres this question elsewhere.
7 Relations in context
In DPL meanings are relations. The contexts we studied appear as properties of these relations.
We could give an alternative semantics for DPL by building the context into the meaning. Thus
we take as meanings pairs hc; Ri, where R 2 fcg. Let's call such a pair a c-relation. We define:
The new domain of meanings is, on the one hand, essentially richer than
the old one, since the same relation falls under several contexts. On the other hand, we threw all
non-IBO-relations away. We can 'lift' the notions intoduced in this paper to c-relations:
ffl A c-condition is a c-relations of the form hhI ; ;; Ii; Ri.
ffl If diag(dom(R))i. Similarly for cod.
ffl A c-relation R has the Switching Property if it is either a c-condition or there are variables v
and w such that:
ffl A c-relation is DPL-definable (over a given domain D) if it can be generated using ffl from
c-conditions and resettings
9 In fact, I think, this proposal is in the right direction, but still not quite right.
I am convinced that the enriched semantics is better than the usual one, but I will not argue the case here.
RELATIONS IN CONTEXT
In a similar way we can upgrade - and 99. Inspection of the proofs in this paper shows that, in
case D is infinite, the DPL-definable c-relations are precisely the ones with the Switching Property.
Moreover, all c-relations over the given domain -infinite or not- are DPL(99)-definable. We consider
an example. Remember that:
Let a model with domain D be given. We assume that D has at least two elements. Let id := id D Var .
We consider three c-relations with associate relation id.
1.
2.
3.
(1) and (2) are c-conditions and, hence DPL-definable. In fact, they can be defined in the language
by ?, respectively In contrast, (3) is not a condition. It is easy to see that (3) does not have
the Switching Property, since the domain of its internal relation id consists of all assignments and id
is injective. Hence (3) is not DPL-definable. Note that hh;; fxg; ;i; idi is not a c-relation at all.
A further step in modifying our semantics is to make the assignments 'local'. The idea is that the
context 'provides' the files/discourse referents/variables on which the variables are defined. Thus,
our meaning objects would be of the form hhI ; B; Oi; Ri, where R would be a relation taking input
assignments defined on I and yielding output assignments defined on O. This approach leads to a
semantics very much like Vermeulen's Referent Systems (see [8]). One effect of this further modification
is that it leads to a somewhat different view of contexts. In the local approach, contexts are the central
'engines' that manage the flow of the files in the interactions of meanings. This more dramatic view
of contexts is elaborated in [9].
Concluding remarks
In this paper we introduced a notion of context and specified its connections with relational semantics
and language. We used these contexts to prove a characterization of the DPL-definable relations.
Moreover, we illustrated the usefulness of contexts both in formulating and in verifying valid sequents
of DPL. We illustrated the fact that 'understanding of what is going on' is not automatically preserved
if we extend the DPL-language. E.g., adding disjunction leads to ambiguous occurrences of variables.
This observation tells us that the study of extensions will provide us clues regarding the question:
what is it to be a variable occurrence of a certain kind?
So -apart from the concrete results- what general conclusions may we draw from the paper? A
first one is, surely, that a study of the elementaria of DPL is both necessary and rewarding. Questions
on the nature of variable occurrences, the proper notion of syntactic substitution, etcetera, appear in
a new light. The fruitfulness of the study of DPL is independent of the question whether DPL is really
the best choice as a medium for representing dynamic phenomena. One reason is that, in a sense, the
relational semantics of DPL is very simple and that it is, therefore, easier to make progress. A second
conclusion is that it is rewarding to engage in a study that stresses the differences between DPL and
Predicate Logic. Much effort has gone into integrating DPL into the classical Montague framework.
This project has unavoidably a conservative flavour. The result has been that the unfamiliarity, the
strangeness of DPL has been underadvertised. Precisely mastering the strangeness provides us with
better insight into the formerly familiar notions. My third conclusion is simply: contexts are essential
in the study of DPL and its kin. We may want to vary the contexts, e.g., we may want to add 'garbage
elements' or to ignore the O-component, but contexts per se are there to stay. Our third conclusion
points to a larger programmatic point: the study of contexts and the way they are contexts of their
contents should be one of the central endeavors of the study of Information Processing and Dynamics.
REFERENCES 19

Acknowledgements

I thank Kees Vermeulen for many enlightening conversations and for his careful reading of a version
of this paper. I am grateful the students of various classes in Dynamic Logic both in Amsterdam and
in Utrecht for providing a critical forum for some of my ideas on DPL and Dynamics.



--R

Dynamic predicate logic.
Counting variables in a dynamic setting.
Categorical Type Theory.
A theory of truth and semantic representation.
Anaphora and the logic of change.
Defaults in update semantics.
Sequence semantics for dynamic predicate logic.
Merging without mystery
Dynamic bracketing and discourse representation.
--TR

--CTR
C. F. M. Vermeulen, Variables as Stacks, Journal of Logic, Language and Information, v.9 n.2, p.143-167, April 2000
C. F. M. Vermeulen, Text Structure and Proof Structure, Journal of Logic, Language and Information, v.9 n.3, p.273-311, July 2000
variable;expressability;predicate logic;resetting;dynamics;context;register;relation;definability