7.5 Reasoning about Relative Likelihood

7.5 Reasoning about Relative Likelihood

The language ^QU_n is not appropriate for reasoning about representations of likelihood whose range is not the reals. For example, it is clearly inappropriate for reasoning about plausibility measures, since a formula like ℓ_i(Φ) = 1/2 does not make sense for an arbitrary plausibility measure; plausibility values may not be real numbers. But even in the case of ranking functions, a formula such as that is not so interesting. Since ranks are nonnegative integers, it is impossible to have ℓ_i(Φ) = 1/2 if ℓⁱ represents a ranking function.

To reason about ranking functions, it seems more appropriate to consider a variant of ^QU_n that restricts the coefficients in likelihood formulas to ^*. There is no difficulty in obtaining a complete axiomatization for this language with respect to ranking structures. It is very similar to that for possibility structures, except that QU2 and QU5 needs to be changed to reflect the fact that for ranking structures, 0 and ∞ play the same role as 1 and 0 do in possibility structures, and QU7 needs to be modified to use min rather than max. Rather than belaboring the details here, I instead consider a more restricted sublanguage of ^QU_n that is appropriate not just for ranking, but also for reasoning about relative likelihood as discussed in Section 2.7. In this sublanguage, denoted ^RL_n, linear combinations of likelihood terms are not allowed. All that is allowed is the comparison of likelihood between two formulas. That is, ^RL_n is the sublanguage of ^QU_n that is formed by starting with primitive propositions and closing off under conjunction, negation, and restricted likelihood formulas of the form ℓ_i(Φ)>ℓ_i(ψ).

^RL_n can be interpreted in a straightforward way in preferential structures, that is, structures where there is a partial preorder ≽ on worlds that can be lifted to an ordering on sets as discussed in Section 2.7. Recall that in Section 2.7 I actually considered two different ways of defining a preorder on sets based on ≽; one was denoted ≽^e and the other ≽^s. Thus, there are two possible semantics that can be defined for formulas in ^RL_n, depending on whether ≽^e or ≽^s is used as the underlying preorder on sets.

Formally, a preferential structure is a tuple M = (W, O₁, …, O_n, π), where for each world w ∊ W, O_i (w)is a pair (W_{w, i}, ≽_{w, i}), where W_{w, i} ⊆ W and ≽_{w, i} is a partial preorder on w_{w, i}. Let ^pref_n denote the class of all preferential structures for n agents; let ^tot_n be the subset of ^pref_n consisting of all total structures, that is, structures where ≽_{w, i} is a total preorder for each world w and agent i. If M is a preferential structure, then

where ≽^e_{w, i} is the partial order on 2^{W_{w, i}} determined by ≽_{w, i}. The superscript e in ⊨_e is meant to emphasize the fact that ≥ is interpreted using ≽^e. Another semantics can be obtained using ≽^s in the obvious way:

Note that in preferential structures, (M, w) ⊨^x (ℓ_i( Φ) = ℓ_i(false)) exactly if [[ φ]]_M ∩ W_{w, i} =∅, both if x = e and if x = s. This, in turn, is true exactly if W_{w, i} ⊆ [[φ]]_M. That is, (M, w) ⊨^x ℓ_i( Φ) = ℓ_i(false) if and only if W_{w, i} ⊆ [[φ]]_M. Thus, ℓ_i( Φ) = ℓ_i(false) can be viewed as a way of expressing K_iφ in ^RL_n. From here on, I take K_iφ to be an abbreviation for ℓ_i( Φ) = ℓ_i(false) when working in the language ^RL_n.

Let AX^RLe consist of the following axioms and inference rules:

• Prop. All substitution instances of tautologies of propositional logic.

• RL1. ℓ_i(Φ) ≥ ℓ_i(Φ).

• RL2. [(ℓ_i(Φ₁) ≥ ℓ_i(Φ₂)) ∧ (ℓ_i(Φ₂) ≥ ℓ_i(Φ₃))] ⇒ (ℓ_i(Φ₁) ≥ ℓ_i(Φ₃)).

• RL3. K_i(Φ ⇒ ψ) ⇒ (ℓ_i(ψ) ≥ ℓ_i(Φ)).

• RL4. [(ℓ_i(Φ₁) ≥ ℓ_i(Φ₂)) ∧ (ℓ_i(Φ₁) ≥ ℓ_i(Φ₃))] ⇒ (ℓ_i(Φ₁) ≥ ℓ_i(Φ₂ ∨ φ₃)).

• MP. From φ and φ ⇒ ψ infer ψ (Modus Ponens).

• Gen. From φ infer K_iφ (Knowledge Generalization).

In the context of preferential structures, these axioms express the properties of relative likelihood discussed in Section 2.7. In particular, RL1 and RL2 say that ≽^e is reflexive and transitive (and thus a preorder), RL3 says that it respects subsets, and RL4 says that it satisfies the finite union property.

Let AX^RLTe consist of AX^RLe together with the following axiom, which says that ≽^e is total:

Finally, let AX^RLs and AX^RLTs be the result of adding the following axiom, which characterizes the qualitative property, to AX^RLe and AX^RLTe, respectively.

Note that if (M, w) ⊨ K_i( (Φ ∧ ψ)), then [[φ]]_M ∩ W_{w, i} and [[ψ]]_M ∩ W_{w, i} are disjoint. Thus, the antecedent in RL5 is really saying that (the intensions of) the formulas φ₁, φ₂, and φ₃ are pairwise disjoint. It should be clear that the rest of the axiom characterizes the qualitative property.

Theorem 7.5.1

For the language ^RL_n:

1. AX^RLe is a sound and complete axiomatization for the ⊨^e semantics with respect to ^pref_n;

2. AX^RLTe is a sound and complete axiomatization for the ⊨^e semantics with respect to ^tot_n;

3. AX^RLs is a sound and complete axiomatization for the ⊨^s semantics with respect to ^pref_n;

4. AX^RLTs is a sound and complete axiomatization for the ⊨^s semantics with respect to ^tot_n.

Proof The soundness of these axioms follows almost immediately from Theorems 2.7.1 and 2.7.5, which characterize the properties of ≽^e and ≽^s semantically. I leave the formal details to the reader (Exercise 7.14). The completeness proof for AX^RLs uses Theorem 2.7.6, although the details are beyond the scope of this book. One subtlety is worth noting. Two properties used in Theorem 2.7.6 have no corresponding axiom: the fact that ≽^s is conservative and that it is determined by singletons.

What happens if formulas in ^RL_n are interpreted with respect to arbitrary plausibility measures? A plausibility structure has the form (W, 풫₁,… 풫_n, π), where 풫_i is a plausibility assignment; a measurable plausibility structure is one where _w,i = 2^Ww,i. Let ^plaus_n and ^plaus,meas_n denote the class of plausibility structures and measurable plausibility structures, respectively. Formulas in ^RL_n are interpreted in measurable plausibility structures in the natural way. (Later I will also talk about ^plaus_n, the class of all ranking structures. I omit the obvious definitions here.)

It is easy to see that RL1–3 are sound for arbitrary measurable plausibility structures, since ≥ is still a preorder, and Pl3 guarantees RL3. These axioms, together with Prop, Gen, and MP, provide a sound and complete axiomatization for the language ^RL_n with respect to measurable plausibility structures. Let AX^ord_n consist of Prop, RL1–3, MP, and Gen.

Theorem 7.5.2

AX^ord_n is a sound and complete axiomatization with respect to ^plaus,meas_n for the language ^RL_n.

Proof Again, soundness is straightforward and completeness is beyond the scope of the book.

Of course, additional axioms arise for particular subclasses of plausibility structures. Interestingly, as far as reasoning about relative likelihood goes, possibility structures and ranking structures are characterized by precisely the same axioms. Moreover, these are the axioms that characterize ≽^e in totally preordered relative likelihood, that is, the axiom system AX^RLTe. The extra structure of the real numbers (in the case of possibility measures) or ^* (in the case of ranking functions) plays no role when reasoning about statements of relative likelihood.

Theorem 7.5.3

AX^RLTe is a sound and complete axiomatization for the language ^RL_n with respect to ^rank_n and ^poss_n.

Proof It is not hard to show that the same formulas in the language ^RL_n are valid in each of ^rank_n, ^poss_n, and ^tot_n (using the ⊨^e semantics) (Exercise 7.16). Thus, it follows from Theorem 7.5.1 that AX^RLTe is sound and complete with respect to all three classes of structures.

What about ^meas_n, ^prob_n, ^bel_n, and ^lp_n? Clearly all the axioms of AX^ord_n hold in these subclasses. In addition, since the plausibility ordering is total in all these subclasses, RL5 holds as well. (It does not hold in general in ^plaus,meas_n, since the domain of plausibility values may be partially ordered.) It is easy to check that none of the other axioms in AX^RLTs is sound. However, AX^ord ∪ {RL5} is not a complete axiomatization with respect to ^meas_n, ^prob_n, ^bel_n, or ^lp_n for the language ^RL_n. For example, a formula such as ℓ(p)>ℓ_i( p) is true at a world w in a structure M ∊ ^meas_n iff μ_{w, i}([[p]]_M) > 1/2. Thus, the following formula is valid in ^meas_n:

However, this formula is not provable in AX^RLTs, let alone AX^ord_n ∪{RL5} (Exercise 7.17). This example suggests that it will be difficult to find an elegant collection of axioms that is complete for ^meas_n with respect to ^RL_n. Even though this simple language does not have facilities for numeric reasoning, it can still express some non-trivial consequences of numeric properties. Other examples can be used to show that there are formulas valid in ^prob_n, ^bel_n, and ^lp_n that are not provable in AX^RLTs Exercise 7.18). Finding a complete axiomatization for ^RL_n with respect to any of ^meas_n, ^prob_n, ^bel_n and ^lp_n remains an open problem.