Safe Contraction Revisited

Abstract

Modern belief revision theory is based to a large extent on partial meet contraction that was introduced in the seminal article by Carlos Alchourrón, Peter Gärdenfors, and David Makinson that appeared in 1985. In the same year, Alchourrón and Makinson published a significantly different approach to the same problem, called safe contraction. Since then, safe contraction has received much less attention than partial meet contraction. The present paper summarizes the current state of knowledge on safe contraction, provides some new results and offers a list of unsolved problems that are in need of investigation.

Appendix: Proofs

Proof of Theorem 1. It was shown by Alchourrón, Gärdenfors and Makinson (1985, Observation 3.3) that (K7) and (K7P) are equivalent, and by Rott (1992b, Lemma 2) that (K7) and (K7p) are equivalent. QED

Proof of Theorem 2. (i) (K8r) implies (K8r$'$): By (K6) and (K8r), we get that . Now let . Thus, by the compactness of $\mathrm {Cn}$, we have finite sets and such that $M\cup N \vdash \chi$. Now define $\xi$ to be $(\bigwedge M)\vee \chi$ and $\rho$ to be $(\bigwedge N)\vee \chi$. By (K1), $\xi$ is in and $\rho$ is in . Furthermore, we have $\chi \dashv \vdash \xi \wedge \rho$, as required by (K8r$'$).

(K8r$'$) implies (K8r): Let . By (K2), $\chi \in K$, so by (K5) and (K1), and . Thus contains $\lnot (\phi \vee \psi )\vee \chi$. In order to show that it contains $\chi$, it is thus sufficient to show that it also contains $\phi \vee \psi \vee \chi$. By (K1), , and by (K6), . Now we are ready to apply (K8r$'$) and get that there are $\xi$ and $\rho$ such that $(\phi \vee \psi \vee \chi ) \dashv \vdash \xi \wedge \rho$ and and . That is, by (K1), and . Hence, and, finally, , as desired.

(ii) (K8wd) implies (K8p): Let . Then by (K8wd), or , which simplifies to or .

(K8p) implies (K8wd): Let . Then by (K1) and (K6) . Thus by (K8p) or . Which reduces by (K6) to or . By (K2) and (K5), and . By (K1), it follows that or .

(iii) For the non-obvious direction, suppose to the contrary that (K8d) holds but not (K8d$'$). Since (K8d$'$) does not hold there are $\alpha$, $\beta$, $\phi$, and $\psi$ such that , , , and . It follows from (K1) that , , and , contrary to (K8d).

(iv) Suppose that . We want to show that either or . By (K1), , and by (K6), . So by (K8p) which we already proved to be relatively equivalent with (K8wd), either or . By (K8c), this reduces to either or . Using (K1), we get that either or . But by (K2) and (K5), both and . So by (K1) again, either or , as desired.

Fig. 3

The Hasse diagram for a contraction function over $K=K_\bot$ that satisfies (K1) – (K7), (K8c) and (K8r), but not (K8wd). Read “” as“

(v) Figure 3 depicts a contraction function over $K=K_\bot$ that satisfies (K1) – (K7), (K8c) and (K8r), but not (K8wd). This contraction function derives from the (vacuously transitive) partial ordering $\leftarrow$ between the four possible worlds $pq$, $p\overline{q}$, $\overline{p}q$ and $\overline{p}\overline{q}$ that is fully specified by $pq \leftarrow \overline{p}\overline{q}$ and $p\overline{q} \leftarrow \overline{p}q$ (where the arrows point to the “more plausible” worlds). Having Grovean semantics for AGM in mind, it can be recognized as a partial meet contraction based on a transitive strict preference relation, and thus Theorem 14 (ii) applies (a similar example is given in Rott 2001, p. 164).²⁹ The violation of (K8wd) is this: We have but neither nor . QED

Proof of Theorem 3. (i) To prove (KAcyc), suppose for reductio that and $\nvdash \phi _i\wedge \phi _{i+1}$ for all $i=1$, ..., $n-$1, and that and $\nvdash \phi _n\wedge \phi _1$. By (K7p) which is equivalent with (K7), it follows that for all $i=1,\dots ,n-1$, and . Thus, by (K1), . But since clearly $\nvdash \phi _1\wedge \dots \wedge \phi _n$, this contradicts (K4).

(ii) To prove (KTrans), we assume that , $\nvdash \phi \wedge \psi$, , and $\nvdash \psi \wedge \chi$. Applying (K7p) and (K6) to we obtain , to which we apply (K8c) and (K6) to obtain . We also have which with (K7p) and (K6) yields . We can finally combine this with and obtain as desired. It remains to be shown that $\not \vdash \phi \wedge \chi$. Suppose for reductio that $\vdash \phi \wedge \chi$. Then we can conclude from $\vdash \phi$ and (K6) that . In combination with the assumption this yields . Then (K4) yields $\vdash \psi$. Thus $\vdash \phi \wedge \psi$, contradicting one of our assumptions. QED

Proof of Theorem 6. We give an example of a contraction function satisfying (K1) – (K6) that cannot be represented as a safe contraction. Consider the language $\mathcal {L}$ that has only two propositional variables, $p$ and $q$. Let $K= \mathrm {Cn}(\{p,q\})$. Consider now a basic AGM contraction function with the following values:

There is nothing in (K1) – (K6) that prevents a contraction function from having these values. The values for other sentences are irrelevant. We now show that such a function cannot be generated through safe contraction.

Consider first . Besides the singleton $p$-kernels $\{p\wedge q\}$ and $\{p\}$, there are four $p$-kernels of $K$ (modulo logical equivalence), viz.,

$$ \begin{array}{c@{\ ,\ }c} \{p\vee q, p\vee \lnot q\} &{} \{p\vee q, p\leftrightarrow q\}\ ,\\ \{q, p\vee \lnot q\} &{} \{q, p\leftrightarrow q\}\\ \end{array} $$

Suppose that the contraction function is a safe contraction associated with a hierarchy $\prec$. Notice that $\lnot p\vee q$, being a consequence of $\lnot p$, is $\prec$-safe with respect to $p$ anyway. Notice also that since , $p\vee \lnot q$ and $p\leftrightarrow q$ must not be $\prec$-safe with respect to $p$. Since , either $p\vee q$ or $q$ itself has to be $\prec$-safe with respect to $p$. Inspecting the four kernels, we realize that this means that

$$ \begin{array}{rccc} \mathrm{{(A1)}} &{} p\vee \lnot q \prec p\vee q &{} \quad \text {and} \quad p\leftrightarrow q \prec p\vee q &{} \ or\\ \mathrm{{(A2)}} &{} p\vee \lnot q \prec q &{} \quad \text {and} \quad p\leftrightarrow q \prec q &{} \end{array}$$

Second, we consider . By exactly the same argument that we have just applied, we get that

$$ \begin{array}{rccc} \mathrm{{(B1)}} &{} p\vee q \prec \lnot p\vee q &{}\quad \text {and} \quad p \prec \lnot p\vee q &{} \ or\\ \mathrm{{(B2)}} &{} p\vee q \prec p\leftrightarrow q &{}\quad \text {and} \quad p \prec p\leftrightarrow q &{} \end{array} $$

Third, we consider . Applying the same argument a third time, we get that

$$ \begin{array}{rccc} \mathrm{{(C1)}} &{} \lnot p\vee q \prec p\vee \lnot q &{}\quad \text {and} \quad q \prec p\vee \lnot q &{} \ or\\ \mathrm{{(C2)}} &{} \lnot p\vee q \prec p &{}\quad \text {and} \quad q \prec p &{} \end{array} $$

Assume, for the first part, that (A1) is true. Then, by the asymmetry of $\prec$, (B2) cannot be true. So (B1) is true. But then, again by the asymmetry of $\prec$, (C2) cannot be true. So (C1) is true as well. But from (A1), (B1) and (C1), we get the cycle

$$ p\vee \lnot q \prec p\vee q \prec \lnot p\vee q \prec p\vee \lnot q $$

So assume for the first part that (A2) is true. Then, by the asymmetry of $\prec$, (C1) cannot be true. So (C2) is true. But then, again by the asymmetry of $\prec$, (B1) cannot be true. So (B2) is true. But from (A2), (C2) and (B2), we get the cycle

$$ p\leftrightarrow q \prec q \prec p \prec p\leftrightarrow q $$

So either way, we have found a cycle, which is forbidden by the assumption that $\prec$ is a hierarchy. We have found a contradiction and proved that cannot be a safe contraction associated with $\prec$. QED

Proof of Theorem 8. That satisfies (K7) is proven in Observation 5.3 of Alchourrón and Makinson (1985). It remains to verify (K8r). Let $\chi$ be in . That is, there is a set $M$ of $\phi \wedge \psi$-safe elements such that $M\vdash \chi$. In order to show that $\chi$ is in , it suffices to show that there are sets $N_1$ of $\phi$-safe and $N_2$ of $\psi$-safe elements such that $N_1 \cup N_2 \vdash \chi$. But since $\prec$ continues down $\vdash$ over $K$, each $\phi \wedge \psi$-safe element is either $\phi$-safe or $\psi$-safe, by Corollary 5.4 of Alchourrón and Makinson (1985). So $M$ can easily be split up into sets $N_1$ and $N_2$ as desired. QED

Proof of Theorem 9. That satisfies (K7) is proven in Observation 4.3 of Alchourrón and Makinson (1985). It remains to verify (K8c). Let $\psi$ and $\chi$ be in . That is, there are sets $M$ and $N$ of $\phi \wedge \psi$-safe elements such that $M\vdash \psi$ and $N\vdash \chi$. Let $M$ and $N$ be chosen minimal, so that they are finite, by compactness. We want to show that $\chi$ is in as well, that is, that there is a set $P$ of $\phi$-safe elements such that $P\vdash \chi$. Put $P=N$. Now suppose that there is a set $R$ such that $R \vdash _{min} \phi$. By compactness, $R$ is finite. Let $\xi \in N$ be in $R$. We need to show that there is a $\rho$ in $R$ such that $\rho \prec \xi$. Clearly, $M\cup R \vdash \phi \wedge \psi$. Define $M' = \{(\bigwedge R) \!\rightarrow \!\sigma : \sigma \in M\}$. Then clearly, $M'\cup R \vdash \phi \wedge \psi$. Since the elements of $M$ are $\phi \wedge \psi$-safe and $\prec$ continues up $\vdash$ over $K$, the elements of $M'$ are $\phi \wedge \psi$-safe as well, by Lemma 4.1 of Alchourrón and Makinson (1985). Take a subset $S$ of $M'\cup R$ that minimally implies $\phi \wedge \psi$. Notice that $R\subseteq S$, because if some $\alpha$ from $R$ were missing from $S$, then $S$ could not imply $\psi$. For suppose that $(R-\{\alpha \})\cup M' \vdash \phi \wedge \psi$. Then, since $\lnot \phi$ is logically stronger than $\lnot \bigwedge R$ and thus than $M'$, we get that $(R-\{\alpha \})\cup \{\lnot \phi \} \vdash \phi \wedge \psi$, and thus $R-\{\alpha \} \vdash \phi$, contradicting the minimality of $R$.

Now since $S \vdash _{min} \phi \wedge \psi$, we can apply the fact that $\xi \in N$ is $\phi \wedge \psi$-safe and conclude that there is a $\rho ^0$ in $S$ such that $\rho ^0 \prec \xi$. Now this $\rho ^0$ is either in $R$ or in $M'$. But if it is in $M'$, we can, by the fact that the elements of $M'$ are $\phi \wedge \psi$-safe, find another sentence $\rho ^1$ with $\rho ^1\prec \rho ^0$ which again is either in $R$ or in $M'$. If $\rho ^1$ is in $M'$, we repeat the process again, and so on. Since $M'$ is finite and $\prec$ is acyclic and transitive, there must finally be a $\rho ^n$ with $\rho ^n\prec \xi$ which is not in $M'$ but in $R$. This is the $\rho$ we have been looking for. QED

Proof of Lemma 10. In the presence of the basic AGM postulates including (K4), Definition 4 above is equivalent to Definition 17 of Rott (2001, p. 229). Thus, the hierarchies obtained by (CH) are relations of epistemic entrenchment. With the exception of (v) and (vi), the claims of Lemma 10 are all listed in part (ii) of Observation 68 of Rott (2001, p. 263), although (viii) is a slightly strengthened form for the present context. (v) is trivial. We prove (vi). Suppose that $\phi \wedge \psi \prec \chi$ and $\nvdash \chi$. This means, by (CH), that and $\nvdash \phi \wedge \psi$. By (K8r), it follows that . By the compactness of $\mathrm {Cn}$, there are finite sets and such that $M\cup N \vdash \chi$. By (K1), we have , and $\chi \dashv \vdash ((\bigwedge M) \vee \chi ) \wedge ((\bigwedge N) \vee \chi )$. Let $\xi$ be $(\bigwedge M) \vee \chi$ and $\rho$ be $(\bigwedge N) \vee \chi$. Since both $\xi$ and $\rho$ are in $\mathrm {Cn}(\chi )$, we have, by (K6), and . Thus, since $\nvdash \phi \wedge \chi$ and $\nvdash \psi \wedge \chi$, $\phi \wedge \chi \prec \xi$ and $\psi \wedge \chi \prec \rho$, as desired. QED

Proof of Theorem 11. The hierarchy $\prec$ defined by (CH) can be used to reconstruct the given contraction function as a safe contraction, provided that has the properties mentioned. The properties of $\prec$ are listed in Lemma 10.

The main claim is:

      iff

there is a set $M$ elements in $K$ that are of $\prec$-safe with respect to $\phi$ and jointly entail $\psi$       iff

there is an $M\subseteq K$ such that $M \vdash \psi$ and for all $N\subseteq K$ such that $N \vdash _{min} \phi$ and all $\chi \in N\cap M$ there is a $\xi \in N$ such that $\xi \prec \chi$       iff

there is an $M\subseteq K$ such that $M \vdash \psi$ and for all $N\subseteq K$ such that $N \vdash _{min} \phi$ and all $\chi \in N\cap M$ there is a $\xi \in N$ such that and $\nvdash \xi$

This claim is trivially satisfied if $\phi \notin K$, since then (K3) and the fact that $K$ is logically closed entail that both the left-hand side and the right-hand side are equivalent to $\psi \in K$. So we suppose that $\phi \in K$ in the following.

(i) From left to right, the general case. Suppose that . Take the set $M = \{\phi \vee \psi , \lnot \phi \vee \psi \}$. By (K1) and (K2), $M\subseteq K$. As a consequence of $\lnot \phi$, $\lnot \phi \vee \psi$ is not in any minimal set entailing $\phi$, so it is $\prec$-safe with respect to $\phi$. It remains to check $\phi \vee \psi$. Suppose $N \vdash _{min} \phi$ with $\phi \vee \psi$ in $N\subseteq K$. We want to show that there is a $\xi$ in $N$ such that and $\nvdash \xi$. (Notice that the minimality condition will not be used again for this direction.)

By (K1), we can infer from that . So by the Partial antitony condition (K7P) which is equivalent with (K7), we get , or, by (K6), . By (K8p) which is equivalent with (K8wd), for some $\xi$ in $N$. And by the minimality of $N$,  $\nvdash \xi$, as desired.

From right to left. Suppose that there is an $M\subseteq K$ such that $M \vdash \psi$ and for all $N\subseteq K$ such that $N \vdash _{min} \phi$ and all $\chi \in N\cap M$ there is a $\xi \in N$ such that and $\nvdash \xi$. Notice that $\psi$ is in $K$, by (K1).

In the limiting case $\vdash \phi$, we have $N\vdash _{min}\phi$ if and only if $N=\emptyset$. So the supposition reduces to $K\vdash \psi$ or, by the fact that $K$ is logically closed, $\psi \in K$. But by (K5), , so , as desired. So let us now turn to the principal case in which $\nvdash \phi$.

Let $M'$ be a subset of $M$ such that $M' \vdash _{min} \phi \vee \psi$. From the supposition it follows that for all $N\subseteq K$ such that $N \vdash _{min} \phi$ and all $\chi \in N\cap M'$ there is a $\xi \in N$ such that and $\nvdash \xi$. By Partial antitony (K7P), we get that for all $N\subseteq K$ such that $N \vdash _{min} \phi$ and all $\chi \in N\cap M'$, . In short, by (K1), for all $N\subseteq K$ such that $N \vdash _{min} \phi$, .

Suppose for reductio that $M' \vdash \phi$. Then, since $\nvdash \phi$, also $\nvdash \bigwedge M'$. It follows from $M' \vdash _{min} \phi \vee \psi$ that $M' \vdash _{min} \phi$, and we get , contradicting (K4). So $M' \nvdash \phi$.

Now consider the set $N_0 = M' \cup \{\psi \!\rightarrow \!\phi \}$. Since $K$ is logically closed and $\phi \in K$, $N_0 \subseteq K$. We show that $N_0 \vdash _{min} \phi$. Since $M'\vdash _{min}\phi \vee \psi$, clearly $N_0\vdash \phi$. Since $M' \nvdash \phi$, $\psi \!\rightarrow \!\phi$ is not redundant. But neither is any element $\rho$ of $M'$ redundant. For suppose that $(M'-\{\rho \}) \cup \{\psi \!\rightarrow \!\phi \} \vdash \phi$. Then $M'-\{\rho \} \vdash (\psi \!\rightarrow \!\phi )\!\rightarrow \!\phi$, i.e., $M'-\{\rho \} \vdash \phi \vee \psi$, contradicting the minimality of $M'$.

From the above, we get . Now we have $M' \subseteq N_0$, thus $\bigwedge (N_0\cap M') = \bigwedge M'$ and . Equivalently, by (K6), . So by (K4) and (K8d), or alternatively by (K8c), , and by (K1) . Finally, by (K5) and (K1), , as desired.

(ii) The case of a logically finite belief set $K$, from left to right. Suppose that . Let $\mathrm {Coatoms}_K(\phi \vee \psi )$ denote the set of co-atoms of $K$, i.e., the logically weakest non-tautological elements of $K$, that are implied by $\phi \vee \psi$, and take the set $M = \mathrm {Coatoms}_K(\phi \vee \psi ) \cup \{\lnot \phi \vee \psi \}$. As a consequence of $\lnot \phi$, $\lnot \phi \vee \psi$ is not in any minimal set entailing $\phi$, so it is $\prec$-safe with respect to $\phi$. It remains to check for every co-atom $\alpha$ in $\mathrm {Coatoms}_K(\phi \vee \psi )$ that it is $\prec$-safe with respect to $\phi$. Suppose $N \vdash _{min} \phi$ with $\alpha$ in $N$. We want to show that there is a $\xi$ in $N$ such that and $\nvdash \xi$.

By (K1), we can infer from that . So by $\phi \vdash \alpha$ and Partial antitony (K7P) which is equivalent with (K7), we get , or, by (K6), . By (K8r), . Since $\alpha$ is a co-atom of $K$, for some $\xi$ in $N$, by Boolean considerations.

The right-to-left direction of the case of a logically finite belief set $K$, is proven literally as in the general case. QED

Proof of Lemma 18. (i) Suppose that $\phi <\psi$ and $\psi <\phi$. Then, by Intersubstitutivity, $\phi <(\psi \wedge \psi )$ and $\psi <(\phi \wedge \phi )$, so by the left-to-right direction of Choice $(\phi \wedge \psi )<\psi$ and $(\psi \wedge \phi )<\phi$. By Intersubstitutivity again, $((\phi \wedge \psi )\wedge \phi )<\psi$ and $((\phi \wedge \psi )\wedge \psi )<\phi$. By the right-to-left direction of Choice, $(\phi \wedge \psi )<(\phi \wedge \psi )$. But this contradicts Irreflexivity. (ii)–(vi) are easy. (vii) For transitivity, let $\phi <\psi$ and $\psi <\chi$. Then, by Continuing down, $\phi \wedge \chi <\psi$ and $\phi \wedge \psi <\chi$. By the right-to-left direction of Choice, it follows that $\phi <\psi \wedge \chi$. So by Continuing up, $\phi <\chi$. Acyclicity follows from Transitivity and Irreflexivity. (viii) For the first part, assume that for all $\beta _j$ there is an $\alpha _i$ such that $\alpha _i < \beta _j$. By Continuing down, for all $\beta _j$, it holds that $\bigwedge \alpha _i < \beta _j$. So by Conjunction up, which follows from Continuing down and the right-to-left direction of Choice (see part (iv) of this lemma), $\bigwedge \alpha _i < \bigwedge \beta _j$, as desired. For the second part, assume that $\bigwedge \alpha _i < \bigwedge \beta _j$. By Continuing up, $\bigwedge \alpha _i < \beta _j$ for all $\beta _j$. Take an arbitrary such $\beta _j$. Now repeated application of (EII$^-$) tells us that there are sentences $\phi _j^1, \dots , \phi _j^k$ such that $\beta _j \dashv \vdash \phi _j^1\wedge \dots \wedge \phi _j^k$ and for all $i=1,\dots ,n$, $\alpha _i\wedge \beta _j < \phi _j^i$. But since $\beta _j$ is a co-atom of $K$, it follows from Boolean considerations that each $\phi _j^i$ is either a tautology or equivalent with $\beta _j$ and that in fact at least one of the $\phi _j^i$’s is equivalent with $\beta _j$. It follows from Intersubstitutivity that $\alpha _i\wedge \beta _j < \beta _j$ for at least one $i$, and the right-to-left direction of Choice and Intersubstitutivity once more that $\alpha _i < \beta _j$ for at least one $\alpha _i$. But this is what we wanted to prove. QED

Proof of Lemma 19. That (ii) implies (i) is trivial. Take $M$ from (ii) and notice that every $N$ that minimally implies $\phi \wedge \psi$ obviously implies $\phi$.

Now we show that (i) implies (ii), given Transitivity and Continuing down for $\prec$. Take $M$ from (i) and let $M'$ be a subset of $M$ that minimally implies $\psi$. Obviously $M'$ also satisfies (i), and by compactness, $M'$ is finite. Suppose that $N\vdash \phi$. Put $N' = \{(\bigwedge M') \!\rightarrow \!\xi : \xi \in N\}$. Since $M'\cup N\vdash \phi \wedge \psi$, also $M'\cup N'\vdash \phi \wedge \psi$. Let $S$ be a minimal subset of $M'\cup N'$ that implies $\phi \wedge \psi$. First notice that $M'\subseteq S$, because if some $\chi$ from $M'$ were missing from $S$, then $S$ could not imply $\phi$. For suppose that $(M'-\{\chi \})\cup N' \vdash \phi \wedge \psi$. Then, since $\lnot \psi$ is logically stronger than $\lnot \bigwedge M'$ and thus than $N'$, we get that $(M'-\{\chi \})\cup \{\lnot \psi \} \vdash \phi \wedge \psi$, and thus $M'-\{\chi \} \vdash \psi \vee (\phi \wedge \psi )$, contradicting the minimality of $M'$. So since $S\vdash _{min}\phi \wedge \psi$, we can apply (i) and find that $S$ is non-empty and for every $\chi$ in $M'\cap S = M'$ there is a $\xi$ in $S$ such that $\xi \prec \chi$. Now this $\xi$ is either in $M'$ or in $N'$. But if it is in $M'$, we can apply (i) again and find another sentence $\xi ^1$ with $\xi ^1\prec \xi$ which again is either in $M'$ or in $N'$. If $\xi ^1$ is in $M'$, we repeat the process again, and so on. Since $M'$ is finite and $\prec$ is acyclic and transitive, there must finally be a $\xi ^n$ with $\xi ^n\prec \chi$ which is not in $M'$ but in $N'$. This $\xi ^n$ is of the form $(\bigwedge M') \!\rightarrow \!\rho$ for some $\rho$ in $N$. Since, finally, this $\rho$ implies $\xi ^n$ and $\prec$ continues down $\vdash$ over $K$, $\rho \prec \chi$, as desired. QED

Proof of Theorem 21. By Theorem 4, every safe contraction function over $K$ satisfies (K1) $-$ (K6). We now show that (EC) follows from (CE), provided that satisfies (K1), (K2), (K5) and (K6).³⁰ (CE) gives us:

By (K6), this is equivalent with

For (EC), we need to show that

       iff $\psi \in K$ and either $\phi < \phi \vee \psi$ or $\vdash \phi$

Let . By (K2), $\psi \in K$. By (K1), . Suppose that $\nvdash \phi$. Then, by ($\dag$), $\phi < \phi \vee \psi$, as desired.

For the converse, let $\psi \in K$ and either $\phi < \phi \vee \psi$ or $\vdash \phi$. If firstly $\phi < \phi \vee \psi$, then by ($\dag$) . Since $\psi \in K$, we get , by (K5) and (K1). Thus by (K1) , as desired. If secondly $\vdash \phi$, then , by (K5), so again , as desired. QED

Proof of Theorem 22. Since $<$ is a generalized entrenchment relation, it is acyclic, by Lemma 18 (vii), and can thus be used as a hierarchy for a safe contraction. Let $\psi$ be in $K$. The case when $\vdash \psi$ is trivial so we assume that $\nvdash \psi$. Then acccording to the entrenchment-based contraction (EC) iff

(i) $\phi <\phi \vee \psi$

$\psi$ is in acccording to the safe contraction defined in Definition 2 iff

(ii) there is a set $M$ of $\phi$-safe elements such that $M\vdash \psi$

First, we show that (i) implies (ii). Suppose that $\phi <\phi \vee \psi$. From this we get, by Intersubstitutivity and the right-to-left direction of Choice, $\phi \vee \lnot \psi < \phi \vee \psi$. Now consider the set $M = \{\phi \vee \psi , \lnot \phi \vee \psi \}$. We show that this set is suitable for (ii). $\lnot \phi \vee \psi$ is $\phi$-safe anyway, because it is a consequence of $\lnot \phi$ and thus will not be included in any minimal set implying $\phi$. It remains to show that $\phi \vee \psi$ is $\phi$-safe as well. Suppose that $\phi \vee \psi$ is in $N$ for some $N$ such that $N \vdash _{min} \phi$. Notice that $N$ is finite and that $N-\{\phi \vee \psi \} \vdash \phi \vee \lnot \psi$. Thus, by Continuing down, $\bigwedge (N-\{\phi \vee \psi \}) < \phi \vee \psi$, and by repeated application of (EII), we get that there is some $\chi$ in $N-\{\phi \vee \psi \}$ such that $\chi < \phi \vee \psi$. Thus $\phi \vee \psi$ is $\phi$-safe, and this proves (ii).

Second, we show that (ii) implies (i). Pick an $M$ from (ii). If $N \vdash _{min} \phi$ and $\chi$ is in $M\cap N$, then there is a $\xi$ in $N$ such that $\xi < \chi$. Take some subset $M'\subseteq M$ such that $M' \vdash _{min} \phi \vee \psi$. Then, if $N \vdash _{min} \phi$ and $\chi$ is in $M'\cap N$, there is a $\xi$ in $N$ such that $\xi < \chi$. By Continuing down, $\bigwedge N < \chi$. By repeated application of Conjunction up, which follows from Continuing down (by Lemma 18 (iv)), $\bigwedge N < \bigwedge (M'\cap N)$.

Now we show that $M' \nvdash \phi$. Suppose for reductio that $M' \vdash \phi$. Then, since $\nvdash \phi$, also $\nvdash \bigwedge M'$. It follows from $M' \vdash _{min} \phi \vee \psi$ that $M' \vdash _{min} \phi$, and we get , contradicting (K4).

Now consider the set $N_0 = M' \cup \{\psi \!\rightarrow \!\phi \}$. It follows from $M' \vdash \phi \vee \psi$ that $N_0 \vdash \phi$. Since $M' \nvdash \phi$, $\psi \!\rightarrow \!\phi$ is not redundant. Suppose that some $\rho \in M'$ is redundant. Then $M'-\{\rho \} \cup \{ \psi \!\rightarrow \!\phi \} \vdash \phi$ and consequently $M'- \{\rho \} \vdash \phi \vee \psi$, contrary to $M' \vdash _{min} \phi \vee \psi$. We therefore have $N_0 \vdash _{min} \phi$.

This gives us $\bigwedge N_0 < \bigwedge (M'\cap N_0)$ and since $N_0 = M' \cup \{\psi \!\rightarrow \!\phi \}$, $\bigwedge N_0 < \bigwedge M'$. By the right-to-left direction of Choice, $\psi \!\rightarrow \!\phi < \bigwedge M'$, and by Continuing up and Continuing down $\phi < \phi \vee \psi$, i.e. we have (i) as desired. QED

Proof of Theorem 27. Let the language have only the two propositional variables $p$ and $q$, and let $K = \mathrm {Cn}(p \wedge q)$. Let $*$ be a revision function on $K$ such that $K*\lnot p = Cn(\lnot p \wedge q)$, $K*\lnot q = Cn(\lnot p \wedge \lnot q)$, and $K*\lnot (p\leftrightarrow q) = Cn( p \wedge \lnot q)$.

$K\bot p = \{\mathrm {Cn}(q), \mathrm {Cn}(p\leftrightarrow q)\}$, and therefore is either $\mathrm {Cn}(q)$, $\mathrm {Cn}(p \leftrightarrow q)$, or $\mathrm {Cn}(p \rightarrow q)$. Of these only $\mathrm {Cn}(q)$ satisfies the Levi identity . Thus .

$K\bot q = \{\mathrm {Cn}(p), \mathrm {Cn}(p\leftrightarrow q)\}$, and therefore is either $\mathrm {Cn}(p)$, $\mathrm {Cn}(p \leftrightarrow q)$, or $\mathrm {Cn}(q \rightarrow p)$. Of these only $\mathrm {Cn}(p \leftrightarrow q)$ satisfies the Levi identity . Thus .

$K\bot (p \leftrightarrow q)= \{\mathrm {Cn}(p), \mathrm {Cn}(q)\}$, and therefore is either $\mathrm {Cn}(p)$, $\mathrm {Cn}(q)$, or $\mathrm {Cn}(p \vee q)$. Of these only $\mathrm {Cn}(p)$ satisfies the Levi identity . Thus .

Thus we have , , and . It was shown in the proof of Theorem 6 that this contraction function is not reconstructible as a safe contraction, and consequently $*$ is not reconstructible as a safe revision. QED