A Characterization Theorem for Trackable Updates

The information available to some agents can be represented with several mathematical models, depending on one’s purpose. These models differ not only in their level of precision, but also in how they evolve when the agents receive new data. The notion of tracking was introduced to describe the matching of information dynamics, or ‘updates’, on different structures.

We expand on the topic of tracking, focusing on the example of plausibility and evidence models, two central structures in the literature on formal epistemology. Our main result is a characterization of the trackable updates of a certain class, that is, we give the exact condition for an update on evidence models to be trackable by a an update on plausibility models. For the positive cases we offer a procedure to compute the other update, while for the negative cases we give a recipe to construct a counterexample to tracking. To our knowledge, this is the first result of this kind in the literature.

1. 1.

   In the literature plausibility models are sometimes assumed to have a complete and/or well-founded relation, we drop these assumptions here, adopting the definition of [4].

2. 2.

   Evidence models contain more information than plausibility models; such information is captured by operators such as the evidence modality. See [4, 5] for a discussion on the relationship between these models. The sphere systems of [9] also constitute an example of neighborhood models with a close tie to relational structures.

3. 3.

   Alternatively one could consider plausibility models with a different relation for each world, this generalization does not add much depth to our results, so we employ the simpler models.

4. 4.

   We ambiguously use the same symbol for the corresponding semantic and the syntactic objects; the context will disambiguate.

Authors and Affiliations

1. ILLC, University of Amsterdam, Amsterdam, The Netherlands

   Giovanni Cinà

Corresponding author

Correspondence to Giovanni Cinà .

Editors and Affiliations

1. Institute for Logic, Language and Computation, University of Amsterdam , Amsterdam, Noord-Holland, The Netherlands

   Alexandru Baltag

2. Department of Philosophy, The University of Auckland, Auckland, Auckland, New Zealand

   Jeremy Seligman

3. Graduate School of Letters, Hokkaido University , Sapporo, Japan

   Tomoyuki Yamada

A Appendix: Application of Theorem 2

In this appendix we show how our main result can be applied, deriving the update ‘collapse of X’ (Definition 7) from the update ‘evidence weakening of X’ (Definition 6). This will showcase how our characterization result solves the problem of finding the tracking companion for a given update.

We start by encoding evidence weakening in a formula \(\alpha \) of the evidence language, using P as the unary predicate that is meant to be interpreted on X:

Intuitively this formula is saying ‘a set n is a piece of evidence in the updated model iff there exists an evidence set \(n'\) in the original model such that \(n = n'\cup X\)’. Note that this is a simple update, where \(\phi (x, n', P) = (x\in n'\vee Px)\) and \(\theta (x, n', P) = \top \).

Evidence weakening satisfies the premises of our Theorem; this ensures that we can apply the procedure to find its tracking companion. As we know from Proposition 4, it is sufficient to show that, for \(\alpha (n, P, \mathcal {E})\) as above, the formula

is equivalent to a formula \(\beta (x, y, P, \le _{\mathcal {E}})\in FOL(P, \le _{\mathcal {E}})\). Thus we proceed manipulate the formula syntactically exploiting various first-order and propositional laws. Starting from

we plug in \(\alpha \) and obtain

From this formula we extract the existential quantifier:

Now we eliminate the quantifier over n exploiting the bi-conditional, substituting the instances of \(x\in n\) and \(y\in n\):

We proceed to split the first disjunction into two implications.

We can then distribute the outermost implication and the quantifier over the conjunction, obtaining

The next step is to rewrite the innermost disjunctions as implications.

Since \(n'\) does not feature in the literals Px or Py or their negations, we can pull out these formulas from the quantifications.

Finally, using the definition of \(\le _{\mathcal {E}}\), we can rewrite the last formula as

The equivalence of \(\forall z\, x\le _{\mathcal {E}} z\) and \(\forall n' (\mathcal {E}(n')\rightarrow x\in n')\) over evidence models is an easy check.

Proposition 4 argued that the tracking companion of evidence weakening is defined by \(\beta (x, y, P, \le )\) (which is just \(\beta (x, y, P, \le _{\mathcal {E}})\) where we have substituted the relation \(\le _{\mathcal {E}}\) with \(\le \)). In this case this means that two elements a and b are in the new, updated relation if and only if they satisfy \(\beta (x, y, P, \le )\). Is is easy to see that \(\beta (x, y, P, \le )\) defines exactly the collapse update of Definition 7: \((a, b)\in coll(\le ) \) if and only if \(\beta (x, y, P, \le )\) is true when instantiated to (a, b) if and only if one of the following is the case

• \(a\in X\) (recall that P is interpreted on the set X);

• \(a\not \in X\), \(b\not \in X\) and \(a \le b\);

• \(a\not \in X\), \(b\in X\) and \(\forall z\, a \le z\).

The reader is invited to contrast this with Definition 7. The manipulations showed in this section are part of a general strategy to reduce the updates of the right shape into formulas of the fragment \(FOL(P, \le _{\mathcal {E}})\), giving us a procedure to compute the tracking companion.

Reprints and permissions

© 2017 Springer-Verlag GmbH Germany

Policies and ethics