Session 3

In today’s session, we will tackle the second half of the representation theorem introduced last time: the “completeness” part. Specifically, we will prove that if a revision operator $\ast$ satisfies the six basic and two supplementary postulates, then for any belief set $B$, we can construct a corresponding ordering ${⪯}_B$. This ordering will satisfy the four structural properties outlined in the previous session and guarantee that:

$$B\ast \varphi =T(\underset{B}{\min }([\varphi ]))$$

I have pasted the full statement of the theorem below as a refresher. In the following section, we will dive directly into the proof.

Representation Theorem for Belief Revision

Let $\mathcal{L}$ be the propositional language defined previously and $W$ be the corresponding space of possible worlds. Let $B\subseteq \mathcal{L}$ be a belief set.

(1) If ${⪯}_B$ is a plausibility ordering on $W$ that satisfies Connectedness, Transitivity, Centeredness, and the Limit Assumption, then the revision operator $\ast$ defined by: $B\ast \varphi :=T({\min }_B([\varphi ]))$ satisfies all basic and supplementary AGM postulates.

(2) Assume $\Phi$ is finite. If $\ast$ is a revision operator on $B$ that satisfies all eight AGM postulates, then there exists a plausibility ordering ${⪯}_B$ on $W$ satisfying Connectedness, Transitivity, Centeredness, and the Limit Assumption, such that for every formula $\varphi \in \mathcal{L}$: $B\ast \varphi =T({\min }_B([\varphi ]))$

Link to original

Part Two: “Completeness” (Finite Language)

Introduction

Let us now prove the second half of the Representation Theorem—the “Completeness” direction. This result establishes that any belief revision operator $\ast$ satisfying the eight AGM postulates discussed in Session 1 can be reconstructed using our possible worlds semantics.

To proceed with this proof, we must now explicitly assume that our propositional language $\mathcal{L}$ is finite. This assumption allows us to construct formulas that isolate specific sets of possible worlds.

Let $\Phi =\{p_1,\dots ,p_n\}$ be the finite set of propositional variables generating $\mathcal{L}$. For any world $w\in W$, we define the state description ${\delta }_w$ as the conjunction of all literals satisfied by $w$:

$${\delta }_w:=\underset{p\in \Phi }{\bigwedge }{l}_p\text{where }{l}_p=\{\begin{array}{ll}p& \text{ if }w\models p\\ \neg p& \text{ if }w/\models p\end{array}$$

We define the function $form:\mathcal{P}(W)\to \mathcal{L}$ such that for any subset of worlds $V\subseteq W$:

$$form(V):=\underset{w\in V}{\bigvee }{\delta }_w$$

For a single world $w$, we simply write $form(w)$ instead of $form(\{w\})$.

A Technical Detail on $form$

Strictly speaking, defining $form(V)$ as simply ${\bigvee }_{w\in V}{\delta }_w$ does not yield a mathematically well-defined function. Syntactically, the formula $p_1\vee \neg p_2$ is a completely different string than $\neg p_2\vee p_1$, even though they are logically and semantically identical. To make $form$ a proper function that maps to a unique formula, we would need to specify a strict lexicographical ordering for how the disjuncts are arranged.

Because the AGM postulates guarantee that our revision operator treats logically equivalent formulas identically (Postulate 6), we can safely abstract away from these syntactic details for the remainder of the proof.

To see how this works, consider a language $\mathcal{L}$ generated by the propositional variables $\Phi =\{a,b,c,d\}$. Recall that a possible world for $\mathcal{L}$ is a valuation function $w:\{a,b,c,d\}\to \{0,1\}$. Consider the possible world $w$ such that:

1. $w(a)=1$
2. $w(b)=0$
3. $w(c)=1$
4. $w(d)=0$

(Recall that $w(a)=1$ is strictly equivalent to saying $w\models a$, and $w(a)=0$ is equivalent to saying $w⊭a$.)

Thus, $w$ satisfies $a$ and $c$, and falsifies $b$ and $d$. Recall that ${\delta }_w$ is the conjunction of literals $l_p$, for all $p\in \Phi$, such that $l_p=p$ iff $w\models p$, and $l_p=\neg p$ iff $w⊭p$. Therefore, we have that:

$${\delta }_w=a\wedge \neg b\wedge c\wedge \neg d$$

This conjunction is the state description of $w$.

Now, consider the set of worlds $\{w,w^{\prime }\}$, where $w^{\prime }$ is identical to $w$ except that it satisfies $b$ (i.e., $w^{\prime }(b)=1$). The state description for $w^{\prime }$ is therefore ${\delta }_{w^{\prime }}=a\wedge b\wedge c\wedge \neg d$.

By definition, $form(\{w,w^{\prime }\})$ is equal to the disjunction of their individual state descriptions:

$$(a\wedge \neg b\wedge c\wedge \neg d)\vee (a\wedge b\wedge c\wedge \neg d)$$

Because the variable $b$ takes opposite truth values across the two disjuncts while all other variables remain constant, this is logically equivalent to the much simpler and more readable formula:

$$a\wedge c\wedge \neg d$$

Now that we have clarified the mechanics of ${\delta }_w$ and $form(\cdot )$, before proving the completeness part of the Representation Theorem, let me state a crucial lemma that we will need later on.

Lemma

Let $\mathcal{L}$ be finite and let $form$ be the function defined above.

$$\text{For all }{w}^{\prime }\in W:w^{\prime }\models form(w)⟺w^{\prime }=w$$

bproof Let $w\in W$. By definition, $form(w)$ is the conjunction of all literals satisfied by $w$. Let $w^{\prime }\in W$ be an arbitrary world.

• ($⟸$) If $w^{\prime }=w$, $w^{\prime }$ assigns the exact same truth values to all propositional variables as $w$. Hence, it satisfies every literal in $form(w)$, meaning $w^{\prime }\models form(w)$.
• ($⟹$) If $w^{\prime }\ne w$, there must be at least one propositional variable $p\in \Phi$ on which they differ. Without loss of generality, suppose $w\models p$ and $w^{\prime }/\models p$. Then the literal $p$ is a conjunct in $form(w)$. Since $w^{\prime }/\models p$, $w^{\prime }$ fails to satisfy this conjunct, and therefore $w^{\prime }/\models form(w)$.

Thus, $w^{\prime }\models form(w)$ if and only if $w^{\prime }=w$. eproof

In other words, Lemma ^b4ff45 shows that the formula $form(w)$ uniquely characterizes the world $w$. There exists exactly one possible world in $W$ that satisfies $form(w)$: $w$ itself. (Differently but equivalently put, any world that satisfies $form(w)$ must be identical to $w$).

This lemma has a very important corollary, which will play a crucial role in our completeness proof.

Corollary

Let $\mathcal{L}$ be finite, let $form$ be the function defined above, and let $[\cdot ]$ be the truth-set function.

$$\text{For all }V\subseteq W:[form(V)]=V$$

bproof We prove this equality by mutual inclusion. Recall that by definition, $form(V)={\bigvee }_{w\in V}form(w)$.

• ($\subseteq$) Suppose $w^{\prime }\in [form(V)]$. By the definition of the truth-set function, $w^{\prime }\models {\bigvee }_{w\in V}form(w)$. By the semantics of disjunction, there exists at least one world $w\in V$ such that $w^{\prime }\models form(w)$. By Lemma ^b4ff45, this strictly entails $w^{\prime }=w$. Since $w\in V$, it follows that $w^{\prime }\in V$.
• ($\supseteq$) Suppose $w^{\prime }\in V$. By Lemma ^b4ff45, we know that $w^{\prime }\models form(w^{\prime })$. Because $form(w^{\prime })$ is one of the disjuncts in the formula ${\bigvee }_{w\in V}form(w)$, classical semantics guarantees that $w^{\prime }\models {\bigvee }_{w\in V}form(w)$. Thus, $w^{\prime }\models form(V)$, which means $w^{\prime }\in [form(V)]$.

Therefore, $[form(V)]=V$. eproof

In other words, for a finite language, $form(\cdot )$ and $[\cdot ]$ (i.e., the truth-set function) act as inverses of each other up to logical equivalence. By this, we mean that while translating a set of worlds into a formula and back returns the exact same set of worlds (i.e., $[form(V)]=V$), translating a formula into its truth-set and back yields a formula that is logically equivalent to the original, even if it is not necessarily the exact same syntactic string (i.e., $form([\varphi ])⊣⊢\varphi$, though generally $form([\varphi ])\ne \varphi$). (Find an example to convince yourself that this is true.) These functions thus allow us to translate between subsets of worlds and syntactic formulas without losing any semantic information.

Note that this holds only for a finite language. If $\mathcal{L}$ were an infinite language, ${\delta }_w$ would not be a well-formed formula, as its construction would require infinitely long conjunctions, which our syntax prohibits.

(N.b., a similar point was made in Lemma 4 (point 3) of the previous session, where it is shown that $T(\cdot )$ and $[\cdot ]$ act as inverses of each other if and only if $\mathcal{L}$ is a finite language.)

The Completeness Proof

Completeness

Let $\mathcal{L}$ be a finite propositional language and $W$ be the corresponding space of possible worlds. Let $B\subseteq \mathcal{L}$ be a belief set. If $\ast$ is a revision operator on $B$ that satisfies all eight AGM postulates, then there exists a plausibility ordering ${⪯}_B$ on $W$ satisfying Connectedness, Transitivity, Centeredness, and the Limit Assumption, such that for every formula $\varphi \in \mathcal{L}$: $B\ast \varphi =T({\min }_B([\varphi ]))$

bproof Assume $B\subseteq \mathcal{L}$ is a belief set, and let $\ast$ be a revision operator on $B$ that satisfies all eight AGM postulates. Because $\mathcal{L}$ is finite, we can define the weak plausibility ordering ${⪯}_B$ on $W$ directly from the revision operator using the exact method of Katsuno and Mendelzon (1991). For any $w_1,w_2\in W$:

$$w_1{⪯}_B{w}_2:⟺w_1\in [B]\text{ or }{w}_1\in [B\ast form(\{w_1,w_2\})]$$

Now, let us prove that Connectedness, Transitivity, Centeredness, and the Limit Assumption hold for ${⪯}_B$.

NOTE

In fact, K&M’s definition of ${⪯}_B$ is redundant, for it could have been the following:

$$w_1{⪯}_B{w}_2:⟺w_1\in [B\ast form(\{w_1,w_2\})]$$

The reason is that, if $w_1\in [B]$, then by Vacuity $w_1\in [B\ast form(\{w_1,w_2\})]$.

bproof Suppose that $w_1\in [B]$, that ${\le }_B$ is defined as above, and that $\ast$ satisfies AGM’s postulates for revision. Then, $B⊬form(\{w_1,w_2\})$, i.e. there exists a possible world that is both in $[B]$ and $[form(\{w_1,w_2\})]=\{w_1,w_2\}$ (by ^62aec5), i.e. $w_1$. By the Vacuity, it follows that $B\ast form(\{w_1,w_2\})=Cn(B\cup \{form(\{w_1,w_2\})\})$. In set-theoretic terms, it means that

$$\begin{array}{rl}[B\ast form(\{w_1,w_2\})]& =[B]\cap [form(\{w_1,w_2\})]\\ & =[B]\cap \{w_1,w_2\}\end{array}$$

Recall that $w_1\in [B]$ and obviously $w_1\in \{w_1,w_2\}$. Therefore, $w_1\in [B\ast form(\{w_1,w_2\})]$. eproof

Despite this result, I will nonetheless use K&M’s original, redundant version.

I. Part One: Properties of ${⪯}_B$.

1. Connectedness. We must show that for any $w_1,w_2\in W$, either $w_1{⪯}_B{w}_2$ or $w_2{⪯}_B{w}_1$. If either $w_1\in [B]$ or $w_2\in [B]$, then the condition is trivially satisfied by definition.

Suppose neither world is in $[B]$. Let $\psi =form(\{w_1,w_2\})$. Since $[\psi ]=\{w_1,w_2\}\ne \varnothing$, Postulate 5 (Consistency) ensures that $[B\ast \psi ]\ne \varnothing$. By Postulate 2 (Success), $B\ast \psi ⊢\psi$, which semantically means $[B\ast \psi ]\subseteq [\psi ]=\{w_1,w_2\}$. Because $[B\ast \psi ]$ is a non-empty subset of $\{w_1,w_2\}$, it must contain $w_1$, $w_2$, or both.

1. If $w_1\in [B\ast form(\{w_1,w_2\})]$, then $w_1{⪯}_B{w}_2$.
2. Suppose that $w_2\in [B\ast form(\{w_1,w_2\})]$. Note that $form(\{w_1,w_2\})$ may be distinct but is logically equivalent to $form(\{w_2,w_1\})$. By Postulate 6 (Congruence), logically equivalent formulas yield identical revised belief sets. Thus, $w_2\in [B\ast form(\{w_2,w_1\})]$, meaning $w_2{⪯}_B{w}_1$.

Therefore, ${⪯}_B$ is connected.

2. Transitivity. Suppose $w_1{⪯}_B{w}_2$ and $w_2{⪯}_B{w}_3$. We must show $w_1{⪯}_B{w}_3$.

Case 1: $w_1\in [B]$. By definition, $w_1{⪯}_B{w}_3$ immediately follows.

Case 2: $w_1\notin [B]$. We need to prove that $w_1\in [B\ast form(\{w_1,w_3\})]$.

First, since $w_1{⪯}_B{w}_2$ and $w_1\notin [B]$, our definition requires $w_1\in [B\ast form(\{w_1,w_2\})]$.

Second, notice that we must also have $w_2\notin [B]$. Suppose to the contrary that $w_2\in [B]$. First, it immediately follows that $[B]\cap [form(\{w_1,w_2\})]\ne \varnothing$, for by ^62aec5 $[form(\{w_1,w_2\})]=\{w_1,w_2\}$. This entails that $B⊬\neg form(\{w_1,w_2\})$. By Postulate 4 (Vacuity), it follows that:

$$B\ast form(\{w_1,w_2\})=Cn(B\cup \{form(w_1,w_2)\})$$

which implies:

$$[B\ast form(\{w_1,w_2\})]=[Cn(B\cup \{form(w_1,w_2)\})]$$

Now, by Session 2 – Lemma 2, it follows that:

$$[B\ast form(\{w_1,w_2\})]=[B]\cap \{w_1,w_2\}$$

Since $w_1\notin [B]$ and, ex hypothesi, $w_2\in [B]$, it follows that $[B\ast form(\{w_1,w_2\})]=[B]\cap \{w_1,w_2\}=\{w_2\}$, which contradicts $w_1\in [B\ast form(\{w_1,w_2\})]$. Therefore, $w_2\notin [B]$.

Thirdly, since $w_2{⪯}_B{w}_3$ and $w_2\notin [B]$, it must be that $w_2\in [B\ast form(\{w_2,w_3\})]$. Again, it must be the case that $w_3\notin [B]$. (We can show in a similar way as above that, if $w_3\in [B]$, a contradiction follows.)

Now that we have collected many pieces of information regarding $w_1,w_2,w_3$:

1. $w_1{⪯}_B{w}_2$ and $w_2{⪯}_B{w}_3$,
2. $w_1,w_2,w_3\notin [B]$, and
3. $w_1\in [B\ast form(\{w_1,w_2\})]$ and $w_2\in [B\ast form(\{w_2,w_3\})]$.

So, we can finally prove the statement we need, i.e. $w_1\in [B\ast form(\{w_1,w_3\})]$. To do so, we proceed as follows. First, we let $\psi =form(\{w_1,w_2,w_3\})$. Then, we show that, since $w_1{⪯}_B{w}_2{⪯}_B{w}_3$, it must be the case that $w_1\in [B\ast \psi ]$. Then, since obviously $w_1\in [B\ast \psi ]\cap \{w_1,w_3\}$, where $\{w_1,w_3\}=[form(\{w_1,w_3\})]$, we can apply the supplementary postulates to show that $w_1\in [B\ast form(\{w_1,w_3\})]$.

First of all, since $[\psi ]\ne \varnothing$, by Postulate 5 (Consistency) $[B\ast \psi ]\ne \varnothing$. By Postulate 2 (Success), $[B\ast \psi ]\subseteq \{w_1,w_2,w_3\}$. In other words, $[B\ast \psi ]$ must be a non-empty subset of $\{w_1,w_2,w_3\}$.

We evaluate which worlds are in $[B\ast \psi ]$ via three exhaustive subcases:

Subcase 2.1: $w_2\in [B\ast \psi ]$. This means $[B\ast \psi ]\cap [form(\{w_1,w_2\})]\ne \varnothing$. This means that the antecedent of Postulate 8 holds, i.e. that $B\ast \psi ⊬\neg form(\{w_1,w_2\})$. By applying both Postulate 7 (Superexpansion) and Postulate 8 (Subexpansion), we obtain the following:

$$B\ast (\psi \wedge form(\{w_1,w_2\}))=Cn(B\ast \psi \cup \{form(\{w_1,w_2\})\})$$

This immediately yields:

$$[B\ast (\psi \wedge form(\{w_1,w_2\}))]=[Cn(B\ast \psi \cup \{form(\{w_1,w_2\})\})]$$

and Session 2 – Lemma 2 yields the following: $[B\ast (\psi \wedge form(\{w_1,w_2\}))]=[B\ast \psi ]\cap [form(\{w_1,w_2\})]$

Since $\psi \wedge form(\{w_1,w_2\})$ is logically equivalent to $form(\{w_1,w_2\})$, Postulate 6 allows us to simplify the LHS:

$$[B\ast form(\{w_1,w_2\})]=[B\ast \psi ]\cap \{w_1,w_2\}$$

We established earlier that $w_1\in [B\ast form(\{w_1,w_2\})]$. Therefore, $w_1\in [B\ast \psi ]\cap \{w_1,w_2\}$, which entails $w_1\in [B\ast \psi ]$.

Subcase 2.2: $w_3\in [B\ast \psi ]$. This means $[B\ast \psi ]\cap [form(\{w_2,w_3\})]\ne \varnothing$. Applying Postulates 7 and 8 exactly as above yields:

$$[B\ast form(\{w_2,w_3\})]=[B\ast \psi ]\cap \{w_2,w_3\}$$

From our initial premise $w_2{⪯}_B{w}_3$ and $w_2\notin [B]$, we know $w_2\in [B\ast form(\{w_2,w_3\})]$. Therefore, $w_2\in [B\ast \psi ]\cap \{w_2,w_3\}$, which strictly entails $w_2\in [B\ast \psi ]$. Now, because $w_2\in [B\ast \psi ]$, the intersection $[B\ast \psi ]\cap [form(\{w_1,w_2\})]$ is non-empty. Applying Postulates 7 and 8 to this intersection yields: $[B\ast form(\{w_1,w_2\})]=[B\ast \psi ]\cap \{w_1,w_2\}$ From our initial premise $w_1{⪯}_B{w}_2$, we know $w_1\in [B\ast form(\{w_1,w_2\})]$. Thus, $w_1\in [B\ast \psi ]\cap \{w_1,w_2\}$, proving that $w_1\in [B\ast \psi ]$.

Subcase 2.3: Neither $w_2$ nor $w_3$ is in $[B\ast \psi ]$. Since $[B\ast \psi ]$ is a non-empty subset of $\{w_1,w_2,w_3\}$, its only remaining possible element must be $w_1$. Thus, $w_1\in [B\ast \psi ]$.

In all possible subcases, we have proved that $w_1\in [B\ast \psi ]$.

Finally, since $w_1\in \{w_1,w_3\}$, the intersection $[B\ast \psi ]\cap [form(\{w_1,w_3\})]$ is non-empty. Applying Postulates 7 and 8 one last time yields: $[B\ast form(\{w_1,w_3\})]=[B\ast \psi ]\cap \{w_1,w_3\}$ Because $w_1\in [B\ast \psi ]$ and $w_1\in \{w_1,w_3\}$, it follows that $w_1\in [B\ast form(\{w_1,w_3\})]$.

Conclusion. Since in all subcases, $w_1\in [B\ast form(\{w_1,w_3\})]$, we conclude that $w_1{⪯}_B{w}_3$.

3. Centeredness. We need to establish two claims:

1. If $w_1,w_2\in [B]$, then $w_1{⪯}_B{w}_2$.
2. If $w_1\in [B]$ and $w_2\notin [B]$, then $w_1{\prec }_B{w}_2$.

Claim (1) follows immediately from the definition above—more precisely, from $w_1,w_2\in [B]$ it follows not only that $w_1{⪯}_B{w}_2$, but also that $w_2{⪯}_B{w}_1$.

Let us prove Claim (2). Suppose that $w_1\in [B]$ and $w_2\notin [B]$. From the first half of our definition of ${⪯}_B$, it follows immediately that $w_1{⪯}_B{w}_2$ (since $w_1\in [B]$). Secondly, note that $B⊬\neg form(\{w_1,w_2\})$, because the intersection $[B]\cap [form(\{w_1,w_2\})]=[B]\cap \{w_1,w_2\}=\{w_1\}$ is non-empty. Thus, the new formula is consistent with $B$. By the Vacuity postulate,

$$[B\ast form(\{w_1,w_2\})]=[B]\cap \{w_1,w_2\}=\{w_1\}$$

Because $w_2$ is not in this truth-set, $w_2\notin [B\ast form(\{w_1,w_2\})]$. Since we also know $w_2\notin [B]$, it fails both conditions of our definition, meaning $w_2{⋠}_B{w}_1$. Since $w_1{⪯}_B{w}_2$ and $w_2{⋠}_B{w}_1$, it strictly follows that $w_1{\prec }_B{w}_2$.

We have established Claim (2), and hence Centeredness.

4. Limit Assumption. Let us now prove that the Limit Assumption holds for ${⪯}_B$. Note that, in a sense, the Limit Assumption is “useless” in this specific setting. It is usually assumed in order to rule out the existence of infinitely descending ${\prec }_B$-chains. However, since $\Phi$ (the set of propositional variables) is finite, $W$ is finite as well, which inherently rules out the possibility of infinitely descending chains.

Still, let us formally prove that LA holds using basic set theory. Recall that the LA reads as follows: For any sentence $\varphi \in \mathcal{L}$, if $[\varphi ]\ne \varnothing$, then there exists at least one world $w_1\in [\varphi ]$ such that $w_1{⪯}_B{w}_2$ for all $w_2\in [\varphi ]$.

Let $\varphi \in \mathcal{L}$ be such that $[\varphi ]\ne \varnothing$. We need to prove that there exists a minimum world in this set under the total preorder ${⪯}_B$.

Suppose for reductio that no such minimum exists. That is, suppose that, for all $w\in [\varphi ]$, there exists a world $w^{\prime }\in [\varphi ]$ such that $w{⋠}_B{w}^{\prime }$. Since ${⪯}_B$ is connected, either $w{⪯}_B{w}^{\prime }$ or $w^{\prime }{⪯}_{B}w$, and so from $w{⋠}_B{w}^{\prime }$ it follows that $w^{\prime }{⪯}_{B}w$, i.e., $w^{\prime }{\prec }_{B}w$. So, the reductio assumption amounts to the assumption that, for all $w\in [\varphi ]$, there exists a world $w^{\prime }\in [\varphi ]$ such that $w^{\prime }{\prec }_{B}w$.

Let $n$ be the total number of distinct possible worlds in the finite set $[\varphi ]$. Since $[\varphi ]$ is non-empty, we can pick some world in it, and call it $x_1\in [\varphi ]$. By our reductio assumption, there exists $x_2\in [\varphi ]$ such that $x_2{\prec }_B{x}_1$. In turn, there exists $x_3\in [\varphi ]$ such that $x_3{\prec }_B{x}_2$, and so on.

If we repeat this process $n$ times, we generate a strictly descending chain containing exactly $n+1$ entries: $x_{n+1}{\prec }_B{x}_n{\prec }_B\cdots {\prec }_B{x}_3{\prec }_B{x}_2{\prec }_B{x}_1$

Because our generated sequence contains $n+1$ entries, but the set $[\varphi ]$ only contains $n$ distinct worlds, it is mathematically impossible for every world in the chain to be unique. There must be some world that appears at least twice in the sequence, meaning we have $x_j=x_i$ for some step $j>i$.

By the transitivity of strict preference, the chain $x_j{\prec }_B\cdots {\prec }_B{x}_i$ strictly entails $x_j{\prec }_B{x}_i$. But since $x_j=x_i$, this means $x_i{\prec }_B{x}_i$. This is a direct contradiction, as $x_i{\prec }_B{x}_i$ means $x_i{⪯}_B{x}_i$ and $x_i{⋠}_B{x}_i$, an out-and-out contradiction.

Therefore, we must reject the reductio assumption. There must exist at least one world $w_1\in [\varphi ]$ that has no strictly more plausible world below it. Because ${⪯}_B$ is connected, this minimal world must be at least as plausible as all other worlds in the set: $w_1{⪯}_B{w}_2$ for all $w_2\in [\varphi ]$. Thus, the Limit Assumption holds.

II. Part Two: Proving the equality $B\ast \varphi =T({\min }_B([\varphi ]))$.

Having established that the defined relation ${⪯}_B$ satisfies all the required structural properties (Connectedness, Transitivity, Centeredness, and the Limit Assumption), we can now prove the following equality:

$$B\ast \varphi =T(\underset{B}{\min }([\varphi ]))$$

Because we are operating in a finite language, Session 2 - Lemma 4 established that we can perfectly translate between syntax and semantics without losing information. Specifically, Property 2 of that lemma states that $T([\Gamma ])=\Gamma$ if and only if $\Gamma$ is a belief set. Since the Closure postulate guarantees that the revised set $B\ast \varphi$ is a logically closed belief set, it strictly follows that $T([B\ast \varphi ])=B\ast \varphi$.

Therefore, to prove our target equality, it is strictly sufficient to prove the corresponding identity:

$$[B\ast \varphi ]=\underset{B}{\min }([\varphi ])\text{\hspace{1em}(C)}$$

For if $[B\ast \varphi ]={\min }_B([\varphi ])$ holds, $T([B\ast \varphi ])=T({\min }_B([\varphi ]))$ holds as well. But $T([B\ast \varphi ])=B\ast \varphi$ by Session 2 - Lemma 4 and the fact that $B\ast \varphi$ is a belief set by Closure. (Recall that we are assuming $\ast$ satisfies all AGM postulates.)

First, consider the edge case where $\varphi$ is unsatisfiable ($[\varphi ]=\varnothing$). By the Success postulate, $B\ast \varphi ⊢\varphi$, meaning $[B\ast \varphi ]\subseteq [\varphi ]=\varnothing$. Thus, $[B\ast \varphi ]=\varnothing$. Since there are no worlds in $[\varphi ]$, the set of minimal worlds ${\min }_B([\varphi ])$ is trivially $\varnothing$ as well. Thus, $(C)$ holds.

Henceforth, assume $\varphi$ is satisfiable ($[\varphi ]\ne \varnothing$). We prove the identity by mutual inclusion.

1. Prove $[B\ast \varphi ]\subseteq {\min }_B([\varphi ])$. Suppose for reductio that $w\in [B\ast \varphi ]$ but $w\notin {\min }_B([\varphi ])$.

By the Success postulate, $B\ast \varphi ⊢\varphi$, meaning $[B\ast \varphi ]\subseteq [\varphi ]$. Thus, $w\in [\varphi ]$. Since $w\in [\varphi ]$ but is not minimal in it, there must exist some world $w^{\prime }\in [\varphi ]$ such that $w^{\prime }{\prec }_{B}w$.

We evaluate this across two cases based on whether $w^{\prime }$ is a model of our original belief set $B$:

• Case 1: $w^{\prime }\in [B]$. Since $w^{\prime }\in [\varphi ]$ as well, the intersection $[B]\cap [\varphi ]$ is non-empty. By the Vacuity postulate, this guarantees that $[B\ast \varphi ]=[B]\cap [\varphi ]$. Because we assumed at the outset that $w\in [B\ast \varphi ]$, it follows that $w\in [B]$. However, by Centeredness, any two worlds in $[B]$ are equally plausible, meaning $w{⪯}_B{w}^{\prime }$. This strictly contradicts the fact that $w^{\prime }{\prec }_{B}w$.

• Case 2: $w^{\prime }\notin [B]$. Because $w^{\prime }{\prec }_{B}w$, we know $w^{\prime }{⪯}_{B}w$ and $w{⋠}_B{w}^{\prime }$. By the definition of our ordering ${⪯}_B$, the fact that $w^{\prime }$ is strictly preferred to $w$ means that $[B\ast form(\{w,w^{\prime }\})]=\{w^{\prime }\}$. Since both $w$ and $w^{\prime }$ are models of $\varphi$, the formula $\varphi \wedge form(\{w,w^{\prime }\})$ is logically equivalent to $form(\{w,w^{\prime }\})$. Therefore, their truth-sets are identical. By the Superexpansion postulate (which holds unconditionally), it follows that:

$$[B\ast \varphi ]\cap [form(\{w,w^{\prime }\})]\subseteq [B\ast (\varphi \wedge form(\{w,w^{\prime }\}))]$$

Which simplifies to:

$$[B\ast \varphi ]\cap \{w,w^{\prime }\}\subseteq [B\ast form(\{w,w^{\prime }\})]$$

Since we established the right side is exactly $\{w^{\prime }\}$, we have:

$$[B\ast \varphi ]\cap \{w,w^{\prime }\}\subseteq \{w^{\prime }\}$$

Recall our starting assumption: $w\in [B\ast \varphi ]$. Since $w$ is also obviously in $\{w,w^{\prime }\}$, it must be that $w\in [B\ast \varphi ]\cap \{w,w^{\prime }\}$. The subset inclusion above thus implies $w\in \{w^{\prime }\}$, meaning $w=w^{\prime }$. Therefore, since $w^{\prime }{\prec }_{B}w$, it follows that $w{\prec }_{B}w$, which is an out-and-out contradiction.

In both cases, we reach a contradiction. Thus, we reject the reductio assumption. The inclusion $[B\ast \varphi ]\subseteq {\min }_B([\varphi ])$ holds.

2. Prove ${\min }_B([\varphi ])\subseteq [B\ast \varphi ]$. Suppose for reductio that $w\in {\min }_B([\varphi ])$ but $w\notin [B\ast \varphi ]$. Since we assumed $\varphi$ is satisfiable, the Consistency postulate guarantees that $B\ast \varphi$ is consistent, meaning $[B\ast \varphi ]\ne \varnothing$. Therefore, there exists at least one world $w^{\prime }\in [B\ast \varphi ]$.

Since $w^{\prime }\in [B\ast \varphi ]$ and (by Success) $[B\ast \varphi ]\subseteq [\varphi ]$, both $w$ and $w^{\prime }$ are models of $\varphi$. Thus, exactly as before, $[\varphi \wedge form(\{w,w^{\prime }\})]=[form(\{w,w^{\prime }\})]=\{w,w^{\prime }\}$. Because $w^{\prime }\in [B\ast \varphi ]$ and $w^{\prime }\in \{w,w^{\prime }\}$, the intersection $[B\ast \varphi ]\cap [form(\{w,w^{\prime }\})]$ is strictly non-empty.

Because this intersection is non-empty, it means that the revised belief set $B\ast \varphi$ is consistent with the formula $form(\{w,w^{\prime }\})$, i.e., $B\ast \varphi ⊬\neg form(\{w,w^{\prime }\})$. This perfectly satisfies the prerequisite for the Subexpansion postulate. Therefore, Superexpansion and Subexpansion together guarantee exact equality: $[B\ast \varphi ]\cap [form(\{w,w^{\prime }\})]=[B\ast form(\{w,w^{\prime }\})]$

Recall our reductio assumption: $w\notin [B\ast \varphi ]$. This means $w$ cannot be in the intersection on the left side, meaning $w\notin [B\ast form(\{w,w^{\prime }\})]$. Since the right side must be a non-empty subset of $\{w,w^{\prime }\}$, and we just established it cannot contain $w$, we are strictly left with: $[B\ast form(\{w,w^{\prime }\})]=\{w^{\prime }\}$

Because $\{w^{\prime }\}$ is the sole minimal world in this restricted set, it follows by our definition of the ordering that $w^{\prime }{⪯}_{B}w$. On the other hand, since $w$ is minimal in $[\varphi ]$ (by our starting assumption) and $w^{\prime }\in [\varphi ]$, it must be that $w{⪯}_B{w}^{\prime }$.

Since $w{⪯}_B{w}^{\prime }$ holds, but $w\notin [B\ast form(\{w,w^{\prime }\})]$, the only way our definition of ${⪯}_B$ allows $w{⪯}_B{w}^{\prime }$ to be true is if its first clause is satisfied: namely, $w\in [B]$.

If $w\in [B]$, then since $w\in [\varphi ]$, the intersection $[B]\cap [\varphi ]$ is non-empty. By the Vacuity postulate, a non-empty intersection guarantees $[B\ast \varphi ]=[B]\cap [\varphi ]$. Since $w\in [B]$ and $w\in [\varphi ]$, it necessarily follows that $w\in [B\ast \varphi ]$.

This directly contradicts our reductio assumption that $w\notin [B\ast \varphi ]$. Thus, we reject the assumption, and the second inclusion ${\min }_B([\varphi ])\subseteq [B\ast \varphi ]$ holds.

3. Conclusion of Part II. Having established both $[B\ast \varphi ]\subseteq {\min }_B([\varphi ])$ and ${\min }_B([\varphi ])\subseteq [B\ast \varphi ]$, we conclude that the semantic identity $(C)$ holds: $[B\ast \varphi ]={\min }_B([\varphi ])$

As shown at the outset of this proof, this identity guarantees our target: $B\ast \varphi =T({\min }_B([\varphi ]))$

This completely proves the second half of the Representation Theorem. eproof