Session 2

In our last session, I introduced the standard AGM theory of belief revision from an axiomatic perspective. We saw how an agent’s belief revision in light of new information can be represented through set-theoretic operations. Specifically, I showed you that:

1. Our ideal agent’s epistemic state can be represented by a belief set, i.e., a set $B\subseteq \mathcal{L}$ (where $\mathcal{L}$ is our formal language) that is closed under logical consequence.
2. The new information the agent receives is represented by a sentence $\varphi \in \mathcal{L}$.
3. The agent’s act of revising their original beliefs $B$ by $\varphi$ simply amounts to “dropping” $B$ and “adopting” a new belief set, $B\ast \varphi$.

But this is just the beginning of the story. I also emphasized that whatever the actual mechanics of revision are, on the standard (AGM) approach, the revision process must obey certain rules. The revision operator $\ast$, which maps a belief set $B$ and a sentence $\varphi$ to a new belief set $B\ast \varphi$, must satisfy the following six foundational postulates:

$$\begin{array}{cl}B\ast \varphi \text{ is a belief set}& \text{(Closure)}\\ & \\ \varphi \in B\ast \varphi & \text{(Success)}\\ & \\ \text{If }\varphi ⊬\perp \text{, then }Cn(B\ast \varphi )\ne \mathcal{L}& \text{(Consistency)}\\ & \\ B\ast \varphi \subseteq Cn(B\cup \{\varphi \})& \text{(Inclusion)}\\ & \\ \text{If }B⊬\neg \varphi \text{, then }B\ast \varphi =Cn(B\cup \{\varphi \})& \text{(Vacuity)}\\ & \\ \text{If }Cn(\{\varphi \})=Cn(\{\psi \})\text{, then }B\ast \varphi =B\ast \psi & \text{(Congruence)}\end{array}$$

Furthermore, to properly handle composite information, we want $\ast$ to validate two supplementary postulates:

$$\begin{array}{cl}B\ast (\varphi \wedge \psi )\subseteq (B\ast \varphi )+\psi & \text{(Superexpansion)}\\ & \\ \text{If }B\ast \varphi ⊬\neg \psi \text{, then }(B\ast \varphi )+\psi \subseteq B\ast (\varphi \wedge \psi )& \text{(Subexpansion)}\end{array}$$

Until now, our study of belief revision has been highly abstract. We have essentially treated the revision operator $\ast$ as a black box: we defined the class of available inputs (belief sets and sentences), the kind of outputs it returns (new belief sets), and the higher-order rules it must respect. However, we have not provided a concrete construction for this operator—a method that, given a specific belief set $B$ and a specific sentence $\varphi$, actually allows us to compute $B\ast \varphi$.

Today, we will open that black box and study one such construction.

The Value of the Axiomatic Approach

The fact that we treated $\ast$ as a black box should not make you think our previous endeavors were useless! In fact, characterizing $\ast$ purely in terms of the rules it must respect has already given us a massive theoretical advantage:

1. Deriving New Rules: It allowed us to prove a host of derivative rules that $\ast$ must also respect.
2. Generality: Working at the abstract level of postulates means that if we prove a theorem based only on those axioms (e.g., the basic six postulates), we have ipso facto proved that any suitable (!) construction for $\ast$ must validate that consequence. We secure results that are completely independent of the underlying mechanics. Conversely, if we start with a specific construction for $\ast$ and prove a property, we cannot guarantee that property holds for other suitable (!) constructions, even if both validate the basic postulates.

Before moving on, make sure that you remember the notions we are keeping in the background, that is:

1. our boolean language $\mathcal{L}$ (definition);
2. the notion of interpretation (or valuation, or possible world) (definition);
3. logical consequence relation (definition) and operator (definition);
4. belief sets (definition); and
5. the properties of classical consequence relations and operator.

1. Constructing the Belief Revision Operator: Introduction

There are many ways in which we can construct a concrete belief revision operator. We can generally group them into two main categories: syntactic and semantic approaches.

Syntactic Approaches. In the syntactic approach, the belief revision operator $\ast$ is obtained as a result of some manipulation of sentences, or sets of sentences, within our belief set $B$. There are two main methods within this category:

1. “Selection Function” approach: On this approach, when we want to revise $B$ by $\varphi$, we perform two operations . First, we perform a contraction: we take $B$ and single out all the maximal subsets of $B$ that do not entail $\neg \varphi$ (i.e., we single out the largest possible subsets of $B$ that are logically compatible with the new information $\varphi$). Because there might be several such maximal subsets, we use a “selection function” to pick the “best” ones—or we take their intersection—to form a contracted, consistent base. Second, we perform an expansion: we simply add the new sentence $\varphi$ to this contracted base and close it under logical consequence to obtain $B\ast \varphi$ .
2. Epistemic Entrenchment: This approach represents the agent’s doxastic state by pairing the belief set $B$ with an entrenchment ordering over the sentences in the language . This ordering reflects how firmly the agent holds specific beliefs. When the agent receives new information $\varphi$ that contradicts the current belief set, the entrenchment ordering determines which beliefs must be surrendered first . The least entrenched beliefs are discarded to restore consistency, while the more entrenched ones are preserved . The revised belief set $B\ast \varphi$ is constructed by keeping all old beliefs that are strictly more entrenched than $\neg \varphi$, and then expanding by $\varphi$ .

Semantic Approaches. In the semantic approach, the revision operator is constructed not by directly manipulating sentences, but by evaluating the possible worlds (or models) that make those sentences true.

1. Implausibility Orderings and Ranking Functions: The space of possible worlds is equipped with an implausibility ordering, where worlds are ranked according to their implausibility. The center consists of the least implausible worlds, representing the current belief set . When revising by $\varphi$, the new belief set is determined by the theory of the least implausible possible worlds in which $\varphi$ is true .

Today, we will discuss a “semantic” construction.

2. Plausibility Orderings

Recall that when we introduced our propositional language $\mathcal{L}$ and its logical consequence relation $⊢$, we defined a set, $W$, of all possible valuations for $\mathcal{L}$. This set contains all possible functions $w:\Phi \to \{0,1\}$—that is, all possible assignments of truth values to the atomic propositions in $\mathcal{L}$, which in turn recursively determine the truth value of any complex sentence in $\mathcal{L}$.

Conceptually, these abstract objects can be understood as possible worlds. A valuation function $w$ describes a maximally specific way things could be (given the expressive limits of $\mathcal{L}$) because it takes a stance on every “fact” expressible in the language. To emphasize this philosophical interpretation, I will refer to $W$ as the set of possible worlds from now on.[^1]

As anticipated in Session 1, §1.1, every sentence $\varphi \in \mathcal{L}$ corresponds to a specific subset of $W$ called its truth-set—the set of all worlds where $\varphi$ is true. Philosophically, this set is often identified with the proposition expressed by $\varphi$, representing its “content.” Regardless of the philosophical backstory, this extensional notion is mathematically crucial for the constructions we will explore.

Truth-Set

Let $\varphi \in \mathcal{L}$. The truth-set function $[\cdot ]:\mathcal{L}\to \mathcal{P}(W)$ maps a sentence to the set of its models:

$$[\varphi ]:=\{w\in W:w\models \varphi \}$$

We can extend the domain of $[\cdot ]$ to include sets of sentences. Let $\Gamma \subseteq \mathcal{L}$ be a set of sentences. Its truth-set is the intersection of the truth-sets of all its members:

$$[\Gamma ]:=\bigcap _{\varphi \in \Gamma }[\varphi ]=\{w\in W:w\models \varphi \text{ for all }\varphi \in \Gamma \}$$

With a slight abuse of notation, I have extended the function $[\cdot ]$ so that it takes sets of sentences as arguments, not just individual sentences. Intuitively, this intersection yields the exact set of worlds where every sentence in $\Gamma$ is simultaneously true. This semantic mapping gives rise to the following fundamental properties that are crucial for the proofs ahead.

Lemma

Let $\varphi ,\psi \in \mathcal{L}$ and let $\Gamma ,\Delta \in \mathcal{P}(\mathcal{L})$. The semantic sets behave according to the following logical rules:

$$\begin{array}{rl}1.& \varphi ⊢\psi ⟺[\varphi ]\subseteq [\psi ]\\ 2.& \Gamma \subseteq \Delta ⟹[\Delta ]\subseteq [\Gamma ]\\ 3.& \Gamma \subseteq \Delta ⟺[\Delta ]\subseteq [\Gamma ]\text{(if }\Delta \text{ is a belief set)}\\ 4.& [Cn(\Gamma \cup \Delta )]=[\Gamma ]\cap [\Delta ]\end{array}$$

bproof See the solutions to the exercises. eproof

Now, we are ready to see exactly how to construct the revision operator $\ast$ using possible worlds. Let’s start with the informal intuition before diving into the formal mathematical construction.

In real-world scenarios, we rarely restrict our beliefs solely to what is strictly entailed by our evidence. We regularly make inferences that go “beyond” the evidence—accepting the risk that our beliefs might be false despite the evidence we possess. However, when we reason inductively like this, we do not just believe anything. That would be irrational. Instead, we constrain these “inductive leaps”: we believe those things that, given our evidence, are as plausible as they can possibly be.

This informal but highly intuitive idea validates the following powerful claim:

Claim

Given your evidence $E$, it is rational to believe any proposition that is true across all the most plausible possible worlds, given $E$.

Clearly, to have a fully-fledged theory of rational inductive belief, we would eventually need to define exactly what “plausibility” amounts to. However, the beauty of the representation result we are about to prove is that we can discover profound results without providing a concrete characterization of plausibility just yet. Specifically, the theorem will show that if rational belief (and belief revision) behaves according to ^348642, then imposing certain structural properties on this abstract “plausibility” ordering will generate a revision operator $\ast$ that perfectly satisfies the standard AGM postulates.

Just to give you an idea of what plausibility could mean in practice, it might be interpreted as:

1. Probability: Under this view, ^348642 states that it is rational to believe whatever is most probable given $E$.
2. Normality (in Martin Smith’s sense): Under this view, ^348642 states that you should believe whatever is true in the set of worlds that demand the fewest explanations (i.e., the most “normal” worlds).
3. Modality/Similarity (in Duncan Pritchard and Jaakko Hirvelä’s sense): Under this view, ^348642 states that you should believe whatever is true in the possible worlds that are most similar to the actual world.[^2]

To generate a belief revision operator $\ast$ that “corresponds” to the AGM postulates (in a formal sense we will clarify later), we must assume that the possible worlds in $W$ can be ordered by a relation $⪯$, and that this relation satisfies specific structural properties.

It is crucial to emphasize a conceptual point here: we treat the plausibility ordering $⪯$ mathematically as a relative ordering rather than an absolute one. The relative plausibility of two worlds $w_1,w_2$ strictly depends on the agent’s current background belief set $B$. Formally, this means:

1. We assume that every belief set $B$ has an associated ordering ${⪯}_B$ satisfying certain structural properties.
2. We do not assume that ${⪯}_B={⪯}_{B^{\prime }}$ for distinct belief sets $B\ne B^{\prime }$, nor do we enforce that they must be different.

By remaining agnostic on this, the results we prove will be entirely independent of this debate. Our theorems hold perfectly whether you interpret plausibility as an absolute, objective hierarchy or as an evidence-relative relation.

(Note: The idea that plausibility shifts based on current evidence is highly intuitive. Consider probability theory: an agent can define entirely different probability distributions over the exact same space of possible worlds simply by conditioning on different prior evidence.)

Because the ordering is tied to a specific belief set $B$, we will write ${⪯}_B$ when the context requires strict precision. Otherwise, to keep the notation clean, I will simply write $⪯$.

The following structural properties are required to characterize the AGM belief revision operator $\ast$ in terms of possible world plausibility. In words, we assume that plausibility has the following properties:

1. All worlds are comparable in terms of plausibility.
2. Plausibility is transitive.
3. All and only the models of our current belief set $B$ are the most plausible worlds.
4. There is always at least one “most plausible” world among the models of any consistent sentence.

Let us flesh out these properties in a more precise way. Let $B$ be a belief set and ${⪯}_B$ be its associated plausibility ordering (where $w_1{⪯}_B{w}_2$ is read as ”$w_1$ is at least as plausible as $w_2$”, and we write $w_1{\prec }_B{w}_2$ for strict plausibility):

1. Connectedness: For any worlds $w_1,w_2\in W$: Either $w_1{⪯}_B{w}_2$ or $w_2{⪯}_B{w}_1$.
2. Transitivity: For any worlds $w_1,w_2,w_3\in W$: If $w_1{⪯}_B{w}_2$ and $w_2{⪯}_B{w}_3$, then $w_1{⪯}_B{w}_3$.
3. Centeredness:
   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$.
4. Limit Assumption: 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 ]$.

If ${⪯}_B$ satisfies (1)-(2), then ${⪯}_B$ is a total preorder.

Now, before stating and proving our representation theorem, we must clarify how we build $B\ast \varphi$ given our plausibility ordering $⪯$. The intuitive idea is that when we revise $B$ by $\varphi$, the set of sentences $B\ast \varphi$ (i.e., the set of all the ideal agent’s beliefs) will be the set of all and only the sentences $\psi$ that are true throughout the most plausible worlds $w$ in $[\varphi ]$ given ${⪯}_B$. That is, we want our new belief set to accept the sentence $\varphi$, but also to do so in the most parsimonious way possible: we take as the “world basis” for $B\ast \varphi$ all and only those $\varphi$-worlds that are most plausible according to our initial belief set $B$.

Define:

$$\underset{B}{\min }([\varphi ]):=\{w\in [\varphi ]:\text{For all }{w}^{\prime }\in [\varphi ],w{⪯}_B{w}^{\prime }\}$$

That is, ${\min }_B([\varphi ])$ selects the set of most plausible worlds $w$ that satisfy $\varphi$.

Next, define the theory function $T:\mathcal{P}(W)\to \mathcal{P}(\mathcal{L})$ such that, for any $V\subseteq W$:

$$T(V):=\{\varphi \in \mathcal{L}:V\subseteq [\varphi ]\}$$

In other words, $T$ takes a world-base $V$ and returns the set of sentences $\varphi \in \mathcal{L}$ that are true in all the worlds in $V$. There are three important properties connecting our semantic sets and our theory function to be aware of:

Lemma

Let $V,V_1,V_2\subseteq W$ be any sets of worlds, and $\Gamma ,\Delta \subseteq \mathcal{L}$ be any sets of sentences.

1. $T(V)$ is a belief set, i.e. $T(V)=Cn(T(V))$.
2. $T([\Gamma ])=Cn(\Gamma )$. Consequently, $T([\Gamma ])=\Gamma ⟺\Gamma$ is a belief set.
3. $V\subseteq [T(V)]$. Furthermore, the equality $[T(V)]=V$ holds for all $V\subseteq W$ if, and only if, $\Phi$ is finite.
4. If $V_1\subseteq V_2$, then $T(V_2)\subseteq T(V_1)$.

bproof See the solutions to the exercises. eproof

This third property is conceptually crucial. It shows that while we can map sentences to worlds and back without losing anything (provided the sentences are logically closed), moving from arbitrary sets of worlds to syntax and back generally results in a loss of information—unless our language is strictly constrained to be finite.

Finally, we define our revision operator $\ast$. Assuming that for every belief set $B\in \mathbf{B}$ there exists an associated plausibility ordering ${⪯}_B$, we can define the global revision function $\ast :\mathbf{B}\times \mathcal{L}\to \mathbf{B}$ as follows:

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

Informally, the revised belief set $B\ast \varphi$ is exactly the set of sentences $\psi$ that are true throughout ${\min }_B([\varphi ])$—that is, the set of sentences true in the most $B$-plausible worlds that satisfy $\varphi$.

Before moving to the formal statement of the theorem and the first part of its proof, let us look at a concrete example to see exactly how this semantic revision operator works in practice.

2.1. Example

Imagine a biology professor who is currently waiting to hear whether their new research project will be approved. To model the epistemic state they are in, we can construct a space of possible worlds $W$ using just four propositional variables:

• $p$: The research project is approved.
• $f$: The project’s funding is secured.
• $h$: Hiring for the project is permitted.
• $l$: Lab space is allocated.

Our agent firmly believes two conditional “laws” about how the university operates. The first is a university-wide rule, while the second is a departmental rule. Consequently, the agent holds the first law to be significantly “more important” than the second.

1. Law 1 (University Policy): If a project is approved, funding must be secured. $L_1:=p\to f$
2. Law 2 (Department Practice): If funding is secured, hiring is permitted and lab space is allocated. $L_2:=f\to (h\wedge l)$

Note: These “laws” are not necessary, logical truths—you can easily point to logically possible worlds where they fail. Instead, they should be understood as ceteris paribus laws, or extremely robust generalizations the professor has come to trust after years of administrative experience.

Now, let us assume the agent’s initial belief set $B$ consists of these two laws, plus the belief that the project is approved ($\neg p$).

$$\begin{array}{rl}B& =Cn(\{L_1,L_2,\neg p\})\\ & =Cn(\{\neg p\wedge (f\to (h\wedge l))\})\end{array}$$

By the Centeredness property, the most plausible worlds in $W$ are exactly those inside the truth-set $[B]$. These are the worlds where no project is approved and the laws hold. They sit at the very bottom of the ordering ${⪯}_B$.

Now, imagine that our biology professor receives an email from the dean with new information $\varphi$: the new project has just been approved, but no new hiring is permitted.

$\varphi :=p\wedge \neg h$

Before we dive into the formal details, let us informally summarize what should happen. The agent started out believing they did not get the project approved ($\neg p$) and that two laws hold, with $L_1$ being more important than $L_2$. Upon learning from the dean that $p$ and $\neg h$ are true, they must revise their beliefs in a conservative way: they must accept $p$ and $\neg h$, and to make room for this, they will retain the strong university rule $L_1$ while dropping the weaker departmental rule $L_2$. In other words, given the dean’s email, the professor expects to get the funding ($f$) and simply accepts that the standard department practice ($L_2$) has been overridden (for they won’t be permitted to hire new people for the moment).

Let us now see how the formal possible-worlds construction predicts this intuitive result.

Clearly, $\varphi$ is false in $[B]$. Therefore, the most plausible worlds where $\varphi$ is true cannot be worlds inside $[B]$, for every world in $[B]$ satisfies $\neg p$, and hence $\neg \varphi$. As a result, our proposed construction requires us to step outside the set of most plausible worlds (i.e., the $B$-worlds). We must move away from the center of the plausibility ordering and inspect the truth-set $[\varphi ]$.

First, let us graphically represent the space of possible worlds, highlighting which worlds are in $[B]$ and which are in $[\varphi ]$:

$$\begin{array}{rcccccc}& p& f& h& l& \in [B]& \in [\varphi ]\\ w_1& 1& 1& 1& 1& & \\ w_2& 1& 1& 1& 0& & \\ w_3& 1& 1& 0& 1& & ✓\\ w_4& 1& 1& 0& 0& & ✓\\ w_5& 1& 0& 1& 1& & \\ w_6& 1& 0& 1& 0& & \\ w_7& 1& 0& 0& 1& & ✓\\ w_8& 1& 0& 0& 0& & ✓\\ w_9& 0& 1& 1& 1& ✓& \\ w_{10}& 0& 1& 1& 0& & \\ w_{11}& 0& 1& 0& 1& & \\ w_{12}& 0& 1& 0& 0& & \\ w_{13}& 0& 0& 1& 1& ✓& \\ w_{14}& 0& 0& 1& 0& ✓& \\ w_{15}& 0& 0& 0& 1& ✓& \\ w_{16}& 0& 0& 0& 0& ✓& \end{array}$$

Notice that in all four worlds in $[\varphi ]=\{w_3,w_4,w_7,w_8\}$, at least one of the laws $L_1$ or $L_2$ (which the agent initially believed) is falsified:

• In $w_3$ and $w_4$, $L_2$ is flouted, because the funding is secured ($f$) but hiring is not permitted ($\neg h$). However, $L_1$ is still true.
• In $w_7$ and $w_8$, $L_1$ is flouted, because the research project is approved ($p$) but the funding is not secured ($\neg f$).

How does the plausibility ordering ${⪯}_B$ rank these four worlds? We want this ordering to reflect the agent’s expectations. Because $L_1$ is a university-wide mandate, while $L_2$ is merely a departmental rule, worlds where the university rule $L_1$ holds ($w_3$ and $w_4$) are more plausible than worlds where $L_1$ fails ($w_7$ and $w_8$).

To visualize this, we can map out the relevant tiers of the plausibility ordering. Below, worlds that are equally plausible are piled up vertically. The worlds in $[B]$ sit at the left, followed by the increasingly less implausible tiers (using $[\dots ]$ for intermediate worlds that are not relevant to our current discussion):

$$\begin{array}{c}\begin{array}{c}{w}_9\\ w_{13}\\ w_{14}\\ w_{15}\\ w_{16}\end{array}{\prec }_B\begin{array}{c}\\ \\ [\dots ]\\ \\ \end{array}{⪯}_B\begin{array}{c}\\ \\ w_3\\ w_4\\ \end{array}{\prec }_B\begin{array}{c}\\ \\ [\dots ]\\ \\ \end{array}{⪯}_B\begin{array}{c}\\ \\ w_7\\ w_8\\ \end{array}{⪯}_B\begin{array}{c}\\ \\ [\dots ]\\ \\ \end{array}\\ \\ \begin{array}{l}\text{Legend}\\ ■\text{Worlds in }[B]\\ ■\text{Worlds in }[\varphi ]\end{array}\end{array}$$

Because $w_3$ and $w_4$ sit strictly to the left of $w_7$ and $w_8$, we know that $w_3{⪯}_B{w}_7$, $w_4{⪯}_B{w}_7$, and so on. Now, to compute the new belief set $B\ast \varphi$, we apply our formula:

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

1. First, we identify ${\min }_B([\varphi ])$. Based on our ordering, the most plausible worlds in $[\varphi ]$ are those that preserve the stronger law $L_1$. Thus,

$$\underset{B}{\min }([\varphi ])=\{w_3,w_4\}$$

2. Second, we extract the theory of this set:

$$T(\{w_3,w_4\})=Cn(\{p\wedge f\wedge \neg h\})$$

Therefore, the revised belief set $B\ast \varphi$ encodes the following epistemic attitudes:

1. The agent believes the project is approved ($p$) and that hiring is not permitted ($\neg h$). This is the information $\varphi$ they received.
2. The agent believes that the funding is secured ($f$). This is a consequence of $L_1$.
3. The agent suspends judgment on whether the lab space is allocated ($l$ is true at $w_3$ and false at $w_4$, meaning neither $l$ nor $\neg l$ is true across ${\min }_B([\varphi ])=\{w_3,w_4\}$).

Note that law $L_2$ has been surrendered to accommodate the new information (i.e., the agent now believes $\neg L_2$).

Finally, notice a crucial philosophical feature of this mathematical construction: the agent is permitted to rationally believe more than what the new evidence strictly entails. The email ($\varphi$) only entails $p\wedge \neg h$. It says absolutely nothing about funding ($f$). Yet, the agent still ends up believing $f$. Why? Because $f$ is true in all the most plausible $\varphi$-worlds ($w_3$ and $w_4$).

3. The Representation Theorem

In the previous section, we saw how to construct a candidate revision operator $\ast$ using possible worlds and plausibility orderings ${⪯}_B$. We also worked through examples to see exactly how this semantic machinery behaves in practice.

Now, it is time to step back up to the theoretical level. The main result we are going to prove is that the plausibility-based construction perfectly captures the rational constraints we previously defined using axioms. The Representation Theorem formally proves this exact equivalence.

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 ]))$

4. Part One: “Soundness”

Let us first prove the first half of the Representation Theorem ^97e681. This result establishes that our semantic construction $\ast$ qualifies as a belief revision operator, for it successfully validates all the AGM postulates we discussed in Session 1.

Soundness

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. 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 eight basic and supplementary AGM postulates.

bproof Assume that $B\subseteq \mathcal{L}$ is a belief set and ${⪯}_B$ (or simply $⪯$) is a plausibility ordering on $W$ satisfying Connectedness, Transitivity, Centeredness, and the Limit Assumption. We must show that the revision operator defined by

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

satisfies the AGM postulates.

1. Closure. We must show that $B\ast \varphi$ is a logically closed belief set, i.e., $B\ast \varphi =Cn(B\ast \varphi )$. By substituting our definition of $\ast$, this amounts to showing:

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

Recall from our earlier results (see ^3c7168 ) that for any arbitrary set of worlds $V\subseteq W$, its theory $T(V)$ is automatically a logically closed belief set. Since ${\min }_B([\varphi ])$ is simply a set of worlds, its theory is logically closed.

2. Success. We must show that $\varphi \in B\ast \varphi$. By the definition of the theory function:

$$T(\underset{B}{\min }([\varphi ]))=\{\psi \in \mathcal{L}:\underset{B}{\min }([\varphi ])\subseteq [\psi ]\}$$

By definition, ${\min }_B([\varphi ])$ selects minimal worlds within $[\varphi ]$. Thus, ${\min }_B([\varphi ])\subseteq [\varphi ]$ is true. Therefore, $\varphi \in T({\min }_B([\varphi ]))$.

3. Inclusion. We must show that $B\ast \varphi \subseteq Cn(B\cup \{\varphi \})$. Let $\psi \in B\ast \varphi$, which means $\psi \in T({\min }_B([\varphi ]))$, i.e., ${\min }_B([\varphi ])\subseteq [\psi ]$. We need to prove that $\psi \in Cn(B\cup \{\varphi \})$. First, recall the semantic equivalence for logical consequence:

$$B\cup \{\varphi \}⊢\psi ⟺[B]\cap [\varphi ]\subseteq [\psi ]$$

So, it suffices to prove that $[B]\cap [\varphi ]\subseteq [\psi ]$. We evaluate this by looking at two cases.

1. Case One: Suppose $[B]\cap [\varphi ]=\varnothing$ (i.e., $B⊢\neg \varphi$). The empty set is trivially a subset of any set, so $[B]\cap [\varphi ]\subseteq [\psi ]$ automatically holds.
2. Case Two: Suppose $[B]\cap [\varphi ]\ne \varnothing$. We will prove that, in this case, $[B]\cap [\varphi ]={\min }_B([\varphi ])$.
   • $(\subseteq )$ Let $w\in [B]\cap [\varphi ]$. Because $w\in [B]$, Centeredness dictates that $w⪯w^{\prime }$ for all $w^{\prime }\in W$. Thus, $w⪯w^{\prime }$ for all $w^{\prime }\in [\varphi ]$. Since $w\in [\varphi ]$ and is at least as plausible as any other world in $[\varphi ]$, we have $w\in {\min }_B([\varphi ])$.
   • $(\supseteq )$ Let $w\in {\min }_B([\varphi ])$. Clearly, $w\in [\varphi ]$. Is $w\in [B]$? Suppose for contradiction that $w\notin [B]$. Since we are in Case Two, we know there is at least one world $w^{\ast }\in [B]\cap [\varphi ]$. By Centeredness, any model of $B$ is strictly more plausible than any non-model, meaning $w^{\ast }\prec w$. But since $w^{\ast }\in [\varphi ]$, this strictly contradicts the assumption that $w$ is minimal in $[\varphi ]$. Hence, $w$ must be in $[B]$, meaning $w\in [B]\cap [\varphi ]$.
   • So, we have established ${\min }_B([\varphi ])=[B]\cap [\varphi ]$. Recall that, ex hypothesi, $\psi \in B\ast \varphi$, meaning that ${\min }_B([\varphi ])\subseteq [\psi ]$. So, it follows immediately that $[B]\cap [\varphi ]\subseteq [\psi ]$.

In both cases, we established $[B]\cap [\varphi ]\subseteq [\psi ]$, which means $B\cup \{\varphi \}⊢\psi$. Since $\psi$ is an arbitrary formula in $B\ast \varphi$, we conclude $B\ast \varphi \subseteq Cn(B\cup \{\varphi \})$.

4. Vacuity. Suppose that $B⊬\neg \varphi$, meaning that $[B]⊈[\neg \varphi ]=W\setminus [\varphi ]$. In other words, there exists at least one world $w\in [B]$ which is also in $[\varphi ]$, i.e. $[B]\cap [\varphi ]\ne \varnothing$.

As I have shown in Case Two of step (3), if $[B]\cap [\varphi ]\ne \varnothing$, it follows that

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

Hence, it follows that

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

By definition, $T({\min }_B([\varphi ]))=B\ast \varphi$. Let me show that $T([B]\cap [\varphi ])=Cn(B\cup \{\varphi \})$.

• $(\subseteq )$ Suppose $\psi \in T([B]\cap [\varphi ])$. By definition, $[B]\cap [\varphi ]\subseteq [\psi ]$. Again by definition, $B\cup \{\varphi \}⊢\psi$. Hence, $\psi \in Cn(B\cup \{\varphi \})$.
• $(\supseteq )$ Suppose $\psi \in Cn(B\cup \{\varphi \})$. By definition, $B\cup \{\varphi \}⊢\psi$. Again by definition, $[B]\cap [\varphi ]\subseteq [\psi ]$. Hence, $\psi \in T([B]\cap [\varphi ])$.

Therefore, $T([B]\cap [\varphi ])=Cn(B\cup \{\varphi \})$. Substituting in the equivalence above, we get

$$B\ast \varphi =Cn(B\cup \{\varphi \})$$

5. Consistency. Suppose $\varphi ⊬\perp$. Note that $\varphi ⊬\perp$ is equivalent to the claim that $[\varphi ]⊈[\perp ]=\varnothing$, which in turn is strictly equivalent to $[\varphi ]\ne \varnothing$.

We need to prove that $Cn(B\ast \varphi )\ne \mathcal{L}$. Since it is trivially true that $Cn(B\ast \varphi )\subseteq \mathcal{L}$, we must prove that $Cn(B\ast \varphi )\subset \mathcal{L}$. This means there exists some $\psi \in \mathcal{L}$ such that $\psi \notin Cn(B\ast \varphi )$. Because $B\ast \varphi$ is a logically closed belief set, $Cn(B\ast \varphi )=B\ast \varphi$. Thus, we must find some $\psi \in \mathcal{L}$ such that $\psi \notin B\ast \varphi$. Semantically, this requires finding a $\psi$ such that ${\min }_B([\varphi ])⊈[\psi ]$.

Recall that $Cn(B\ast \varphi )=\mathcal{L}$ means $B\ast \varphi$ is inconsistent. The proof is complete if we can show that $B\ast \varphi$ does not entail a blatant contradiction. Consider the contradiction $p\wedge \neg p\in \mathcal{L}$ (for some atomic $p\in \Phi$).

Obviously, $[p\wedge \neg p]=\varnothing$. So, we must prove:

$$\underset{B}{\min }([\varphi ])⊈[p\wedge \neg p]=\varnothing$$

Since the only set that is a subset of the empty set is the empty set itself, this inclusion fails if and only if ${\min }_B([\varphi ])\ne \varnothing$.

To prove that this set is non-empty, we will proceed by reductio ad absurdum. Suppose that ${\min }_B([\varphi ])=\varnothing$.

By definition, a world is in the minimal set iff there is no strictly more plausible world in the truth-set. If the minimal set is empty, it means that no world in $[\varphi ]$ is minimal. Consequently, for every world $w\in [\varphi ]$, there must exist a distinct world $w^{\prime }\in [\varphi ]$ such that $w^{\prime }{\prec }_{B}w$.

This implies that any $w\in [\varphi ]$ is merely a link in an infinite, strictly descending chain of ever-more-plausible worlds:

$$\cdots {\prec }_B{w}_5{\prec }_B{w}_4{\prec }_B{w}_3{\prec }_B{w}_2{\prec }_B{w}_1{\prec }_{B}w$$

However, the Limit Assumption explicitly forbids the existence of such chains without a lower bound. Recall that the Limit Assumption reads as follows:

$$\text{For any sentence }\varphi \in \mathcal{L}\text{: If }[\varphi ]\ne \varnothing \text{, there exists }{w}^{\ast }\in [\varphi ]\text{ such that }{w}^{\ast }{⪯}_{B}x\text{ for all }x\in [\varphi ]$$

Since we know from our initial premise that $[\varphi ]\ne \varnothing$, the Limit Assumption guarantees the existence of this world $w^{\ast }$.

Since $w^{\ast }\in [\varphi ]$ and we assumed that for every world in $[\varphi ]$ there is a strictly more plausible one, there must exist some world $w^{†}\in [\varphi ]$ such that $w^{†}{\prec }_B{w}^{\ast }$. Recall that $w^{†}{\prec }_B{w}^{\ast }$ means $w^{†}{⪯}_B{w}^{\ast }$ and $w^{\ast }{⋠}_B{w}^{†}$. But the Limit Assumption stated that $w^{\ast }{⪯}_{B}x$ for all $x\in [\varphi ]$, which strictly entails $w^{\ast }{⪯}_B{w}^{†}$.

We have derived both $w^{\ast }{⋠}_B{w}^{†}$ and $w^{\ast }{⪯}_B{w}^{†}$: contradiction.

Therefore, we must reject the reductio assumption. The set ${\min }_B([\varphi ])$ is non-empty. Because it is non-empty, it implies that ${\min }_B([\varphi ])⊈[p\wedge \neg p]=\varnothing$, meaning that $p\wedge \neg p\notin B\ast \varphi$. Because there is at least one formula in $\mathcal{L}$ not entailed by $B\ast \varphi$, we conclude that $Cn(B\ast \varphi )\ne \mathcal{L}$.

6. Congruence. Suppose that $Cn(\{\varphi \})=Cn(\{\psi \})$. Therefore, we have $\varphi ⊢\psi$ and $\psi ⊢\varphi$, meaning that

$$[\varphi ]=[\psi ]$$

Hence, since ${\min }_B(\cdot )$ is a function, we have that

$$\begin{array}{rl}B\ast \varphi & =T(\underset{B}{\min }([\varphi ]))\\ & =T(\underset{B}{\min }([\psi ]))\\ & =B\ast \psi \end{array}$$

7. Superexpansion. We must prove that $B\ast (\varphi \wedge \psi )\subseteq (B\ast \varphi )+\psi$.

Let $\chi \in B\ast (\varphi \wedge \psi )$. By definition, this assumption means $\chi \in T({\min }_B([\varphi \wedge \psi ]))$, i.e.:

$$\underset{B}{\min }([\varphi ]\cap [\psi ])\subseteq [\chi ]$$

Boolean and Set-Theoretic Operations

Although we did not prove this together, it is straightforward to verify that, by means of the truth-set function $[\cdot ]$, there exists a “correspondence” between Boolean operators (i.e., the connectives of our language $\mathcal{L}$, $\wedge ,\vee ,\neg ,\to ,\leftrightarrow$) and set-theoretic operators (i.e., $\cup ,\cap {,}^c$). (N.b., recall that for any universe set $U$ and set $A\subseteq U$, $A^c=U\setminus A$.)

$$\begin{array}{rl}[\neg \varphi ]& =[\varphi {]}^c=W\setminus [\varphi ]\\ [\varphi \wedge \psi ]& =[\varphi ]\cap [\psi ]\\ [\varphi \vee \psi ]& =[\varphi ]\cup [\psi ]\\ [\varphi \to \psi ]& =[\varphi {]}^c\cup [\psi ]\\ [\varphi \leftrightarrow \psi ]& =\left([\varphi ]\cap [\psi ]\right)\cup \left([\varphi {]}^c\cap [\psi {]}^c\right)\end{array}$$

In the following, I will make use of this correspondence.

We need to prove that $\chi \in (B\ast \varphi )+\psi$. By definition, $(B\ast \varphi )+\psi =Cn((B\ast \varphi )\cup \{\psi \})$. The problem here is that we cannot easily use the semantic definition of $\ast$ or the postulates we already proved directly on $Cn((B\ast \varphi )\cup \{\psi \})$. We need to find a way to “remove” $\{\psi \}$. Luckily, there exists a very straightforward way of doing so, which is the Deduction Theorem for classical logic – see Session 1 – which states that, for any $\Gamma \subseteq \mathcal{L}$ and $x,y\in \mathcal{L}$:

$$y\in Cn(\Gamma \cup \{x\})⟺x\to y\in Cn(\Gamma )$$

As stated above, we need to prove $\chi \in (B\ast \varphi )+\psi =Cn((B\ast \varphi )\cup \{\psi \})$. So, by the Deduction Theorem, we need to prove:

$$\begin{array}{rlrl}\chi \in Cn((B\ast \varphi )\cup \{\psi \})& ⟺\psi \to \chi \in Cn(B\ast \varphi )& & \\ & ⟺\psi \to \chi \in B\ast \varphi & & \text{for B∗ϕ is a belief set}\end{array}$$

So, I will prove that $\psi \to \chi$ is in $B\ast \varphi$. That is, we need to prove that $\psi \to \chi \in T({\min }_B([\varphi ]))$. Semantically, this means we must prove:

$$\underset{B}{\min }([\varphi ])\subseteq [\psi \to \chi ]$$

How can we further simplify the statement we need to prove, i.e., ${\min }_B([\varphi ])\subseteq [\psi \to \chi ]$? The easiest approach is to simplify the truth-set of the implication $\psi \to \chi$ by considering the conditions under which a world $w$ satisfies $\psi \to \chi$.

Recall the truth table for "$\to$". $\psi \to \chi$ is true iff either $\psi$ is false or $\chi$ is true. So, $[\psi \to \chi ]=(W\setminus [\psi ])\cup [\chi ]$, which we can write as $[\psi {]}^c\cup [\chi ]$. You can easily verify that a world $w$ is in $[\psi {]}^c\cup [\chi ]$ if, and only if, $w\models \psi \to \chi$.

So, we need to prove:

$$\underset{B}{\min }([\varphi ])\subseteq [\psi {]}^c\cup [\chi ]$$

Let $w$ be an arbitrary world in ${\min }_B([\varphi ])$. We want to show that $w\in [\psi {]}^c\cup [\chi ]$. We have two cases:

1. Case One: $w\notin [\psi ]$. Hence, $w\in [\psi {]}^c$. Therefore, $w\in [\psi {]}^c\cup [\chi ]$ trivially holds.
2. Case Two: $w\in [\psi ]$. In this case, $w\in {\min }_B([\varphi ])\cap [\psi ]\subseteq [\varphi ]\cap [\psi ]$. I will show that $w$ must actually be minimal in the intersection, i.e., $w\in {\min }_B([\varphi ]\cap [\psi ])$, which together with our assumption implies that $w\in [\chi ]$. Suppose the opposite is true, i.e. $w\notin {\min }_B([\varphi ]\cap [\psi ])$. So, there exists some world $w^{\prime }\in [\varphi ]\cap [\psi ]$ such that $w^{\prime }{\prec }_{B}w$. Since $w,w^{\prime }\in [\varphi ]$, the fact that $w^{\prime }{\prec }_{B}w$ contradicts our starting assumption that $w\in {\min }_B([\varphi ])$. Thus, no such $w^{\prime }$ exists, and $w\in {\min }_B([\varphi ]\cap [\psi ])$. Because we know from our initial premise that ${\min }_B([\varphi ]\cap [\psi ])\subseteq [\chi ]$, it follows that $w\in [\chi ]$. Therefore, $w\in [\psi {]}^c\cup [\chi ]$.

Either way, $w\in [\psi {]}^c\cup [\chi ]$. Since $w$ is an arbitrary world in ${\min }_B([\varphi ])$, we have established ${\min }_B([\varphi ])\subseteq [\psi \to \chi ]$. Hence, $(\psi \to \chi )\in T({\min }_B([\varphi ]))=B\ast \varphi$. This gives us $\chi \in (B\ast \varphi )+\psi$. Since $\chi$ is an arbitrary formula from $B\ast (\varphi \wedge \psi )$, we conclude $B\ast (\varphi \wedge \psi )\subseteq (B\ast \varphi )+\psi$. eproof

8. Subexpansion. Suppose that $\neg \psi \notin B\ast \varphi$. We must show that $(B\ast \varphi )+\psi \subseteq B\ast (\varphi \wedge \psi )$. First of all, let me clarify what exactly we need to prove here. As we did in the proof of Superexpansion, we need to “unpack” the statement "$(B\ast \varphi )+\psi \subseteq B\ast (\varphi \wedge \psi )$" into something easier to prove by applying the definitions.

$$\begin{array}{rl}(B\ast \varphi )+\psi \subseteq B\ast (\varphi \wedge \psi )& ⟺Cn(T(\underset{B}{\min }([\varphi ]))\cup \{\psi \})\subseteq T(\underset{B}{\min }([\varphi \wedge \psi ]))\\ & ⟺\text{For all }\chi :\chi \in Cn(T(\underset{B}{\min }([\varphi ]))\cup \{\psi \})⟹\chi \in T(\underset{B}{\min }([\varphi \wedge \psi ]))\\ & ⟺\text{For all }\chi :\psi \to \chi \in Cn(T(\underset{B}{\min }([\varphi ])))⟹\chi \in T(\underset{B}{\min }([\varphi \wedge \psi ]))\\ & ⟺\text{For all }\chi :\psi \to \chi \in T(\underset{B}{\min }([\varphi ]))⟹\chi \in T(\underset{B}{\min }([\varphi \wedge \psi ]))\\ & ⟺\text{For all }\chi :\underset{B}{\min }([\varphi ])\subseteq [\psi \to \chi ]⟹\underset{B}{\min }([\varphi \wedge \psi ])\subseteq [\chi ]\\ & ⟺\text{For all }\chi :\underset{B}{\min }([\varphi ])\subseteq [\psi {]}^c\cup [\chi ]⟹\underset{B}{\min }([\varphi \wedge \psi ])\subseteq [\chi ]\end{array}$$

Therefore, we need to prove that, for any sentence $\chi$, if ${\min }_B([\varphi ])\subseteq [\psi {]}^c\cup [\chi ]$, then ${\min }_B([\varphi \wedge \psi ])\subseteq [\chi ]$. So, let us suppose that ${\min }_B([\varphi ])\subseteq [\psi {]}^c\cup [\chi ]$, and let us go back to the starting premise we made at the beginning of this section. That premise may be unpacked as follows:

$$\begin{array}{rl}\neg \psi \notin B\ast \varphi & ⟺\neg \psi \notin T(\underset{B}{\min }([\varphi ]))\\ & ⟺\underset{B}{\min }([\varphi ])⊈[\psi {]}^c\\ & ⟺\underset{B}{\min }([\varphi ])\cap [\psi ]\ne \varnothing \end{array}$$

We need to prove that ${\min }_B([\varphi \wedge \psi ])\subseteq [\chi ]$, or alternatively that ${\min }_B([\varphi ]\cap [\psi ])\subseteq [\chi ]$. First of all, note that the following statement is true given our supposition that ${\min }_B([\varphi ])\subseteq [\psi {]}^c\cup [\chi ]$:

$$\underset{B}{\min }([\varphi ])\cap [\psi ]\subseteq [\chi ]\text{\hspace{1em}(I)}$$

For if $x$ belongs to the left-hand side, then in particular $x\in {\min }_B([\varphi ])$, and by our supposition $x\in [\psi {]}^c\cup [\chi ]$. But since $x$ is in the left-hand side, it must be that $x\in [\psi ]$, meaning $x\notin [\psi {]}^c$. Because $x\in [\psi {]}^c\cup [\chi ]$ and $x\notin [\psi {]}^c$, it strictly follows that $x\in [\chi ]$, thereby establishing the subset inclusion above.

So, to prove ${\min }_B([\varphi \wedge \psi ])\subseteq [\chi ]$, I will first prove the following identity:

$$\underset{B}{\min }([\varphi \wedge \psi ])=\underset{B}{\min }([\varphi ])\cap [\psi ]\text{\hspace{1em}(II)}$$

From $(I)$ and $(II)$ it follows immediately that our conclusion holds, i.e., that ${\min }_B([\varphi \wedge \psi ])\subseteq [\chi ]$. So, let us establish $(II)$.

$(\supseteq )$ Suppose for reductio that $w\in {\min }_B([\varphi ])\cap [\psi ]$ but $w\notin {\min }_B([\varphi \wedge \psi ])$. Because $w\in [\varphi ]$ and $w\in [\psi ]$, $w$ satisfies $\varphi \wedge \psi$. If it is not minimal in $[\varphi \wedge \psi ]$, there must exist some $w^{\prime }\in [\varphi \wedge \psi ]$ such that $w^{\prime }{\prec }_{B}w$. However, since $w^{\prime }\in [\varphi \wedge \psi ]$, we know $w^{\prime }\in [\varphi ]$. The fact that $w^{\prime }\in [\varphi ]$ and $w^{\prime }{\prec }_{B}w$ strictly contradicts our starting premise that $w\in {\min }_B([\varphi ])$.

Hence, no such $w^{\prime }$ exists, and $w\in {\min }_B([\varphi \wedge \psi ])$, which implies that:

$$\underset{B}{\min }([\varphi ])\cap [\psi ]\subseteq \underset{B}{\min }([\varphi \wedge \psi ])$$

$(\subseteq )$ Let us prove that the inclusion also holds the other way around. It is crucial to remember here that ${\min }_B([\varphi ])\cap [\psi ]\ne \varnothing$ (our initial assumption). Let us call $w^{†}$ a world in this intersection. Now, suppose for reductio that $w\in {\min }_B([\varphi \wedge \psi ])$ but $w\notin {\min }_B([\varphi ])\cap [\psi ]$. Since $w\in [\varphi \wedge \psi ]$, we know $w\in [\psi ]$. Therefore, the only way $w$ is excluded from the intersection is if $w\notin {\min }_B([\varphi ])$. If $w\notin {\min }_B([\varphi ])$, there must exist some $w^{\ast }\in [\varphi ]$ such that $w^{\ast }{\prec }_{B}w$. Now consider our three worlds:

1. Because $w\in {\min }_B([\varphi \wedge \psi ])$ and $w^{†}\in [\varphi \wedge \psi ]$, it must be that $w{⪯}_B{w}^{†}$.
2. Because $w^{†}\in {\min }_B([\varphi ])$ and $w^{\ast }\in [\varphi ]$, it must be that $w^{†}{⪯}_B{w}^{\ast }$.
3. By our assumption above, $w^{\ast }{\prec }_{B}w$.

Stringing these together yields $w{⪯}_B{w}^{†}{⪯}_B{w}^{\ast }{\prec }_{B}w$, which implies $w{\prec }_{B}w$. This is a contradiction, since $w{\prec }_{B}w$ means $w{⪯}_{B}w$ and $w{⋠}_{B}w$.

Thus, we reject the reductio assumption, meaning $w\in {\min }_B([\varphi ])\cap [\psi ]$, which implies that ${\min }_B([\varphi \wedge \psi ])\subseteq {\min }_B([\varphi ])\cap [\psi ]$.

Now that we have established ${\min }_B([\varphi \wedge \psi ])={\min }_B([\varphi ])\cap [\psi ]$, we can easily prove our desired claim. By $(II)$, ${\min }_B([\varphi \wedge \psi ])={\min }_B([\varphi ])\cap [\psi ]$ and by $(I)$, ${\min }_B([\varphi ])\cap [\psi ]\subseteq [\chi ]$. So, we conclude that:

$$\underset{B}{\min }([\varphi \wedge \psi ])\subseteq [\chi ]$$

Recall that $\chi$ is just an arbitrary formula in $\mathcal{L}$. So, we have proved that:

$$\text{For all }\chi :\underset{B}{\min }([\varphi ])\subseteq [\psi {]}^c\cup [\chi ]⟹\underset{B}{\min }([\varphi \wedge \psi ])\subseteq [\chi ]$$

which is logically equivalent to Subexpansion, as shown at the beginning of the sub-proof, and hence we have proved Subexpansion.

Conclusion. Therefore, we have proved that, for any belief set $B$ associated with an order ${⪯}_B$ on $W$ satisfying the properties listed above, and any proposition $\varphi$, if we define $B\ast \varphi$ as $T({\min }_B([\varphi ]))$, all the eight postulates of AGM belief revision are satisfied. eproof

5. Exercisess

1. Proofs. Prove all the lemmas and propositions we did not prove together. See this file for the solutions.