2.7 Relative Likelihood

All the approaches considered thus far have been numeric. But numbers are not always so easy to come by. Sometimes it is enough to have just relative likelihood. In this section, I consider an approach that again starts with a set of possible worlds, but now ordered according to likelihood.

Let ≽ be a reflexive and transitive relation on a set W of worlds. Technically, ≽ is a partial preorder. It is partial because two worlds might be incomparable as far ≽ as goes; that is, it is possible that w  w′ and w′  w for some worlds w and w′. It is a partial preorder rather than a partial order because it is not necessarily antisymmetric. (A relation ≽ is antisymmetric if w ≽ w′ and w′ ≽ w together imply that w = w′; that is, the relation is antisymmetric if there cannot be distinct equivalent worlds.) I typically write w ≽ w′ rather than (w, w′) ∈ ≽. (It may seem strange to write (w, w′) ∈ ≽, but recall that ≽ is just a binary relation.) I also write w ≻ w′ if w ≽ w′ and it is not the case that w′ ≽ w. The relation ≻ is the strict partial order determined by ≽: it is irreflexive and transitive, and hence also antisymmetric (Exercise 2.41). Thus, ≻ is an order rather than just a preorder.

Think of ≽ as providing a likelihood ordering on the worlds in W. If w ≽ w′, then w is at least as likely as w′. Given this interpretation, the fact that ≽ is assumed to be a partial preorder is easy to justify. Transitivity just says that if u is at least as likely as v, and v is at least as likely as w, then u is at least as likely as w; reflexivity just says that world w is at least as likely as itself. The fact that ≽ is partial allows for an agent who is not able to compare two worlds in likelihood.

Having an ordering ≽ on worlds makes it possible to say that one world is more likely than another, but it does not immediately say when an event, or set of worlds, is more likely than another event. To deal with events, ≽ must be extended to an order ▹ on sets. Unfortunately, there are many ways of doing this; it is not clear which is "best." I consider two ways here. One is quite natural; the other is perhaps less natural, but has interesting connections with some material discussed in Chapter 8. Lack of space precludes me from considering other methods; however, I don't mean to suggest that the methods I consider are the only interesting approaches to defining an order on sets.

Define ≽^e (the superscript e stands for events, to emphasize that this is a relation on events, not worlds) by taking U ≽^e V iff (if and only if) for all v ∈ V, there exists some u ∈ U such that u ≽ v. Let ≻^e be the strict partial order determined by ≽^e. Clearly ≽^e is a partial preorder on sets, and it extends ≽ : u ≽ v iff {u} ≽^e {v}. It is also the case that ≻^e extends ≻.

I now collect some properties of ≽^e that will prove important in Chapter 7; the proof that these properties hold is deferred to Exercise 2.42. A relation ▹ on 2^W

respects subsets if U ⊇ V implies U ▹ V;
has the union property if, for all index sets I, if U ▹ V_i for all i ∈ I, then U ▹ ∪_iV_i;
is determined by singletons if U ▹ {v} implies that there exists some u ∈ U such that {u} ▹ {v};
is conservative if ∅ ▲V for V ≠∅.

It is easy to check that ≽^e has all of these properties. How reasonable are these as properties of likelihood? It seems that any reasonable measure of likelihood would make a set as least as likely as any of its subsets. The conservative property merely says that all nonempty sets are viewed as possible; nothing is a priori excluded. The fact that ≽^e has the union property makes it quite different from, say, probability. With probability, sufficiently many "small" probabilities eventually can dominate a "large" probability. On the other hand, if a possibility measure satisfies Poss3⁺, then likelihood as determined by possibility does satisfy the union property. It is immediate from Poss3⁺ that if Poss(U) ≥ Poss(V_i) for all i ∈ I, then Poss(U) ≥ Poss(∪_iV_i). Determination by singletons also holds for possibility measures restricted to finite sets; if U is finite and Poss(U) ≥ Poss(v), then Poss(u) ≥ Poss(v) for some u ∈ U. However, it does not necessarily hold for infinite sets, even if Poss3⁺ holds. For example, if Poss(0) = 1 and Poss(n) = 1 − 1/n for n > 0, then Poss({1, 2, 3, …}= 1 ≥ Poss(0), but Poss(n) < Poss(0) for all n > 0. Determination by singletons is somewhat related to the union property. It follows from determination by singletons that if U ∪ U′ ≽^e {v}, then either U ≽^e {v} or U′ ≽^e {v}.

Although I have allowed ≽ to be a partial preorder, so that some elements of W may be incomparable according to ≽, in many cases of interest, ≽ is a total preorder. This means that for all w, w′ ∈ W, either w ≽ w′ or w′ ≽ w. For example, if ≽ is determined by a possibility measure Poss, so that w ≽ w′ if Poss(w) ≥ Poss(w′), then ≽ is total. It is not hard to check that if ≽ is total, then so is ≽^e.

The following theorem summarizes the properties of ≽^e:

Theorem 2.7.1

The relation ≽^e is a conservative partial preorder that respects subsets, has the union property, and is determined by singletons. In addition, if ≽ is a total preorder, then so is ≽^e.

Proof See Exercise 2.42.

Are there other significant properties that hold for ≽^e? As the following theorem shows, there are not. In a precise sense, these properties actually characterize ≽^e.

Theorem 2.7.2

If ▹ is a conservative partial preorder on 2^W that respects subsets, has the union property, and is determined by singletons, then there is a partial preorder ≽ on W such that ▹= ≽^e. If in addition ▹ is total, then so is ≽.

Proof Given ▹, define a preorder on worlds by defining u ≽ v iff {u} ▹ {v}. If ▹ is total, so is ≽. It remains to show that ▹= ≽^e. I leave the straightforward details to the reader (Exercise 2.43).

If ≽ is total, ≻^e has yet another property that will play an important role in modeling belief, default reasoning, and counterfactual reasoning (see Chapter 8). A relation ▹ on 2^W is qualitative if, for disjoint sets V₁, V₂, and V₃, if (V₁ ∪ V₂) ▹ V₃ and (V₁ ∪ V₃) ▹ V₂, then V₁ ▹ (V₂ ∪ V₃). If ▹ is viewed as meaning "much more likely," then this property says that if V₁ ∪ V₂ is much more likely than V₃ and V₁ ∪ V₃ is much more likely than V₂, then most of the likelihood has to be concentrated in V₁. Thus, V₁ must be much more likely than V₂ ∪ V₃.

It is easy to see that ≽^e is not in general qualitative. For example, suppose that W ={w₁, w₂}, w₁ ≽ w₂, and w₂ ≽ w₁. Thus, {w₁} ≽^e {w₂} and {w₂} ≽^e {w₁}. If ≽^e were qualitative, then (taking V₁, V₂, and V₃ to be ∅, {w₁}, and {w₂}, respectively), it would be the case that ∅ ≽^e {w₁, w₂}, which is clearly not the case. On the other hand, it is not hard to show that ≻^e is qualitative if ≽ is total. I did not include this property in Theorem 2.7.1 because it actually follows from the other properties (see Exercise 2.44). However, ≻^e is not in general qualitative if ≽ is a partial preorder, as the following example shows:

Example 2.7.3

Suppose that w₀ ={w₁, w₂, w₃}, where w₁ is incomparable to w₂ and w₃, while w₂ and w₃ are equivalent (so that w₃ ≽ w₂ and w₂ ≽ w₃). Notice that {w₁, w₂} ≻^e {w₃} and {w₁, w₃} ≻^e {w₂}, but {w₁} ^e{w₂, w₃}. Taking V_i ={w_i}, i = 1, 2, 3, this shows that ≻^e is not qualitative.

The qualitative property may not seem so natural, but because of its central role in modeling belief, I am interested in finding a preorder ≽^s on sets (the superscript s stands for set) that extends ≽ such that the strict partial order ≻^s determined by ≽^s has the qualitative property. Unfortunately, this is impossible, at least if ≽^s also respects subsets. To see this, consider Example 2.7.3 again. If ≽^s respects subsets, then {w₁, w₂} ≽^s {w₁} and {w₁, w₂} ≽^s {w₂}. Thus, it must be the case that {w₁, w₂} ≻^s {w₂}, for if {w₂} ≽^s {w₁, w₂}, then by transitivity, {w₂} ≽^s {w₁}, which contradicts the fact that ≽^s extends ≽. (Recall that w₁ and w₂ are incomparable according to ≽.) Since {w₁, w₂}≻^s {w₂} and {w₂} ≽^s {w₃}, it follows by transitivity that {w₁, w₂} ≻^s {w₃}. A similar argument shows that {w₁, w₃} ≻^s {w₂}. By the qualitative property, it follows that {w₁} ≻^s {w₂, w₃}. But then, since ≽^s respects subsets, it must be the case that {w₁} ≻^s {w₂}, again contradicting the fact that ≽^s extends ≽.

Although it is impossible to get a qualitative partial preorder on sets that extends ≽, it is possible to get the next best thing: a qualitative partial preorder on sets that extends ≻. I do this in the remainder of this subsection. The discussion is somewhat technical and can be skipped on a first reading of the book.

Define a relation ≽^s on sets as follows:

U ≽^s V is for all υ ∊ V −U, there exists u ∊ U such that u ≻ υ and u dominates V − U, where u dominates a set X if it is not the case that x ≻ u for any element x ∊ X.

Ignoring the clause about domination (which is only relevant in infinite domains; see Example 2.7.4), this definition is not far off from that of ≽^e. Indeed, it is not hard to check that U ≽^e V iff for all v ∈ V − U, there exists u ∈ U such that u ≽ v (Exercise 2.45). Thus, all that has really happened in going from ≽^e to ≽^s is that has been replaced by ≻. Because of this change, ≽^s just misses extending . Certainly if {u} ≽^s {v} then u ≻ v; in fact, u ≻ v. Moreover, it is almost immediate from the definition that {u} ≻^s {v} iff u ≻ v. The only time that ≽^s disagrees with ≽ on singleton sets is if u and v are distinct worlds equivalent with respect to ≽; in this case, they are incomparable with respect to ≽^s. It follows that if ≽ is a partial order, and not just a preorder, then ≽^s does extend ≽. Interestingly, ≻^e and ≻^s agree if ≽ is total. Of course, in general, they are different (Exercise 2.46).

As I said, the requirement that u dominate V is not relevant if W is finite (Exercise 2.47); however, it does play a significant role if W is infinite. Because of it, ≽^s does not satisfy the full union property, as the following example shows:

Example 2.7.4

Let V_∞ ={w₀, w₁, w₂, …}, and suppose that ≽ is a total preorder on W such that

Let W₀ ={w₀, w₂, w₄, …} and W₁ ={w₁, w₃, w₅, …}. Then it is easy to see that w₀ ≻^s {w_j} for all w_j ∈ W₁; however, it is not the case that W₀ ≽^s W₁, since there is no element in w₀ that dominates w₁. Thus, ≽^s does not satisfy the union property.

It is easy to check that ≽^s satisfies a finitary version of the union property; that is, if U ≽^s V₁ and U ≽^s V₂, then U ≽^s V₁ ∪ V₂. It is only the full infinitary version that causes problems.

The following theorem summarizes the properties of ≽^s:

Theorem 2.7.5

The relation ≽^s is a conservative, qualitative partial preorder that respects subsets, has the finitary union property, and is determined by singletons. In addition, if ≽ is a total preorder, then so is ≽^s.

Proof See Exercise 2.48.

The original motivation for the definition of ≽^s was to make ≻^s qualitative. Theorem 2.7.5 says only that ≽^s is qualitative. In fact, it is not hard to check that ≻^s is qualitative too. (See Exercise 2.49 for further discussion of this point.)

The next theorem is the analogue of Theorem 2.7.2, at least in the case that W is finite.

Theorem 2.7.6

If W is finite and ▹ is a conservative, qualitative partial preorder that respects subsets, has the finitary union property, and is determined by singletons, then there is a partial preorder ≽ on W such that ▹=≽^s. If in addition ▹ is a total preorder, then ≽^s can be taken to be a total as well.

Proof Given ▹, define a preorder ≽ on worlds by defining u ≽ v iff {u} ▹ {v}.If ▹ is total, modify the definition so that u ≽ v iff {v} ⋫ {u}. I leave it to the reader to check that ▹=≽^s, and if ▹ is total, then so is ≽ (Exercise 2.50).

I do not know if there is an elegant characterization of ≽^s if W is infinite. The problem is that characterizing dominance seems difficult. (It is, of course, possible to characterize ≽^s by essentially rewriting the definition. This is not terribly interesting though.)

Given all the complications in the definitions of ≽^e and ≽^s, it seems reasonable to ask how these definitions relate to other notions of likelihood. In fact, ≽^e can be seen as a qualitative version of possibility measures and ranking functions. Given a possibility measure Poss on W, define w ≽ w′ if Poss(w) ≥ Poss(w′). It is easy to see that, as long as Poss is conservative (i.e., Poss(w) > 0 for all w ∈ W ), then U ≽^e V iff Poss(U) ≥ Poss(V) and U ≻^e V iff Poss(U) > Poss(V) (Exercise 2.51). Since ≽ is a total preorder, ≻^s and ≻^e agree, so Poss(U) > Poss(V) iff U ≻^s V. It follows that Poss is qualitative; that is, if Poss(U₁ ∪ U₂)> Poss(U₃) and Poss(U₁ ∪ U₃)> Poss(U₂), then Poss(U₁)> Poss(U₂ ∪ U₃). (It is actually not hard to prove this directly; see Exercise 2.52.) Ranking functions also have the qualitative property. Indeed, just like possibility measures, ranking functions can be used to define an ordering on worlds that is compatible with relative likelihood (Exercise 2.53).