Choice revision

Abstract

Choice revision is a sort of non-prioritized multiple revision, in which the agent partially accepts the new information represented by a set of sentences. We investigate the construction of choice revision based on a new approach to belief change called descriptor revision. We prove that each of two variants of choice revision based on such construction is axiomatically characterized with a set of plausible postulates, assuming that the object language is finite. Furthermore, we introduce an alternative modelling for choice revision, which is based on a type of relation on sets of sentences, named multiple believability relation. We show without assuming a finite language that choice revision constructed from such relations is axiomatically characterized with the same sets of postulates that we proposed for the choice revision based on descriptor revision, whenever the relations satisfy certain rationality conditions.

1 Introduction

Belief change¹ theory studies how a rational agent changes her belief state when she is exposed to new information. Studies in this field have traditionally had a strong focus on two types of change: contraction in which a specified sentence has to be removed from the original belief state, and revision in which a specified sentence has instead to be consistently added. This paper is mainly concerned with the latter.

Alchourrón, Gärdenfors and Makinson (AGM) performed the pioneering formal study on these two types of change in their seminal paper (Alchourrn et al. 1985). In the AGM theory of belief change, the agent’s belief state is represented by a set of sentences from some formal language ${\mathcal {L}}$, usually denoted by K. The new information is represented by a single sentence in ${\mathcal {L}}$. Belief revision and contraction on K are formally represented by two operations $*$ and $\div$, mapping from a sentence $\varphi$ to a new set of sentences $K *\varphi$ and $K \div \varphi$ respectively. Alchourrn et al. (1985) postulated some conditions that a rational revision or contraction operation should satisfy, which are called AGM postulates on revision and contraction.²

Furthermore, Alchourrn et al. (1985) showed that contraction and revision satisfying AGM postulates could be precisely constructed from a model based on partial meet functions on remainder sets. After that, many alternative models (Alchourrón and Makinson 1985; Grove 1988; Gärdenfors and Makinson 1988; Hansson 1994, etc.) have been proposed to construct the operations characterized by these postulates. Although these models look entirely different on the surface, most of them employ the same select-and-intersect strategy (Hansson 2017, p. 19). For example, in partial meet construction for contraction (Alchourrn et al. 1985), a selection is made among remainders and in sphere modelling for revision (Grove 1988), a selection is made among possible worlds. The intersection of the selected objects is taken as the outcome of the operation in both cases.

Although the AGM theory has virtually become a standard model of theory change, many researchers are unsatisfied with its settings in several aspects and have proposed several modifications and generalizations to that framework (see Fermé and Hansson 2011 for a survey). Here we only point out two inadequatenesses of the AGM theory.

On the one hand, in the original AGM model, the input is represented by a single sentence. This is unrealistic since agents often receive more than one piece of information at the same time. In order to cover these cases, we can generalize sentential revision to multiple revision, where the input is a finite or infinite set of sentences. On the other hand, in AGM revision, new information has priority over original beliefs. This is represented by the success postulate: $\varphi \in K *\varphi$ for all $\varphi$. The priority means that the new information will always be entirely incorporated, whereas previous beliefs will be discarded whenever the agent need do so in order to incorporate the new information consistently. This is a limitation of AGM theory since in real life it is a common phenomenon that agents do not accept the new information that they receive or only accept it partially. As a modification, we can drop the success postulate and generalize prioritized revision to non-prioritized belief revision.

In this contribution, we will put these two generalizations together and consider the so called non-prioritized multiple belief revision. In Falappa et al. (2012), two different kinds of such generalized revision are distinguished:

• 1. Merge: K and A are symmetrically treated, i.e., sentences of K and A could be accepted or rejected.

• 2. Choice revision³: some sentences of A could be accepted, some others could be rejected.

We use $*_c$ to denote a choice revision operation. Falappa et al. (2012) investigated the formal properties of merge but left the study on choice revision as future work. As far as we know, little work has been done on this kind of revision in the literature. This fact can be partly explained by that the operation $*_c$ has the unusual characteristic that the standard select-and-intersect approach is not in general applicable. To see why, let the set K of original beliefs not contain any element of $A =\{ \varphi , \lnot \varphi \}$. We are going to construct a set $K *_cA$ which incorporates $\varphi$ or its negation. Suppose that we do that by first selecting a collection $\mathbb {X} =\{X_1, X_2, X_3, \ldots \}$ of sets of beliefs, each of which satisfies the success condition for choice revision with A, i.e. $X_i \cap A \ne \emptyset$ for each $X_i$. Then it may be the case that $\varphi \in X_1$ and $\lnot \varphi \in X_2$. Given that $X_1$ and $X_2$ are consistent, it follows that the intersection $\cap \mathbb {X}$ cannot satisfy the success condition, i.e. it contains neither $\varphi$ or $\lnot \varphi$.

Therefore, to develop a modelling for choice revision, we need to choose another strategy than the select-and-intersect method. Hansson (2013) introduced a new approach of belief change named “descriptor revision”, which employs a “select-direct” methodology: it assumes that there is a set of belief sets as potential outcomes of belief change, and the belief change is performed by a direct choice among these potential outcomes. Furthermore, this is a very powerful framework for constructing belief change operations since success conditions for various types of belief changes are described in a general way with the help of a metalinguistic belief operator ${\mathfrak {B}}$. For instance, the success condition of contraction by $\varphi$ is $\lnot {\mathfrak {B}} \varphi$, that of revision by $\varphi$ is ${\mathfrak {B}} \varphi$. Descriptor revision on a belief set K is performed with a unified operator $\circ$ which applies to any success condition that is expressible with ${\mathfrak {B}}$. Hence, choice revision $*_c$ with a finite input set can be constructed from descriptor revision in the way of $K *_c\{\varphi _1, \varphi _2, \ldots , \varphi _n\} = K \circ \{{\mathfrak {B}} \varphi _1 \vee {\mathfrak {B}} \varphi _2 \vee \cdots \vee {\mathfrak {B}} \varphi _n \}$ (Hansson 2017, p. 130).

Although the construction of choice revision in the framework of descriptor revision has been introduced in Hansson (2017), the formal properties of this type of belief change are still in need of investigation. The main purpose of this contribution is to conduct such an investigation. After providing some formal preliminaries in Sect. 2, we will review how to construct choice revision in the framework of descriptor revision in Sect. 3. More importantly, in this section, we will investigate the postulates on choice revision which could axiomatically characterize these constructions. In Sect. 4 we will propose an alternative modelling for choice revision, which is based on multiple believability relations, a generalized version of believability relation introduced in Hansson (2014) and further studied in Zhang (2017). We will investigate the formal properties of this modelling and prove the associated representation theorems. Section 5 concludes and indicates some directions for future work. All proofs of the formal results are placed in the “Appendix”.

2 Preliminaries

The object language ${\mathcal {L}}$ is defined inductively by a set v of propositional variables $\{p_0 ,\, p_1, \, \ldots , \, p_n, \, \ldots \}$ and the truth-functional operations $\lnot , \wedge , \vee$ and $\rightarrow$ in the usual way. ${\scriptstyle \top }$ is a tautology and ${\scriptstyle \perp }$ a contradiction. ${\mathcal {L}}$ is called finite if v is finite. Sentences in ${\mathcal {L}}$ will be denoted by lower-case Greek letters and sets of such sentences by upper-case Roman letters.

$\mathrm {Cn}$ is a consequence operation for ${\mathcal {L}}$ satisfying supraclassicality: if $\varphi$ can be derived from A by classical truth-functional logic, then $\varphi \in \mathrm {Cn}(A)$, compactness: if $\varphi \in \mathrm {Cn}(A)$, then there exists some finite $B \subseteq A$ such that $\varphi \in \mathrm {Cn}(B)$, and the deduction property: $\varphi \in \mathrm {Cn}(A \cup \{\psi \}$) if and only if (henceforth iff for short) $\psi \rightarrow \varphi \in \mathrm {Cn}(A)$. $X\Vdash \varphi$ and $X \nVdash \varphi$ are alternative notations for $\varphi \in \mathrm {Cn}(X)$ and $\varphi \notin \mathrm {Cn}(X)$ respectively. $\{ \varphi \} \Vdash \psi$ is rewritten as $\varphi \Vdash \psi$ for simplicity. And $\varphi \dashv \Vdash \psi$ means $\varphi \Vdash \psi$ and $\psi \Vdash \varphi$. $A \equiv B$ holds iff for every $\varphi \in A$, there exists some $\psi \in B$ such that $\varphi \dashv \Vdash \psi$ and vice versa.

For all finite A, let $\&A$ denote the conjunction of all elements in A. For any A and B, . We write and and for simplicity.

The set of beliefs an agent holds is represented by a belief set, which is a set $X \subseteq {\mathcal {L}}$ such that $X = \mathrm {Cn}(X)$. K is fixed to denote the original beliefs of the agent. We assume that K is consistent, i.e. $K \nVdash {\scriptstyle \perp }$, unless stated otherwise.

3 Choice revision based on descriptor revision

Before investigating the properties of choice revision constructed in the framework of descriptor revision, we first present some formal basics of this framework, which is mainly based on Hansson (2013).

3.1 Basics of descriptor revision

An atomic belief descriptor is a sentence ${\mathfrak {B}}\varphi$ with $\varphi \in {\mathcal {L}}$, which can be interpreted as “believing proposition $\varphi$”. A descriptor is a set of truth-functional combinations of atomic descriptors. ${\mathfrak {B}}\varphi$ is satisfied by a belief set X iff $\varphi \in X$. Conditions of satisfaction for truth-functional combination of atomic descriptors are defined inductively. X satisfies a descriptor $\varPhi$ (denoted by $X \vDash \varPhi$ ) iff it satisfies all its elements. Descriptor revision on a belief set K is performed with a unified operator $\circ$ such that $K \circ \varPhi$ is an operation with descriptor $\varPhi$ representing its success condition. Hansson (2013) introduces several constructions for descriptor revision operations, of which the relational model defined as follows has a canonical status.

Definition 1

(Hansson 2013) $(\mathbb {X}, \leqq )$ is a relational select-direct model (in short: relational model) with respect to K iff it satisfies⁴:

• $(\mathbb {X} 1)$$\mathbb {X}$ is a set of belief sets.

• $(\mathbb {X} 2)$$K \in \mathbb {X}$.

• $(\leqq 1)$$K \leqq X$ for every $X \in \mathbb {X}$.

• $(\leqq 2)$ For any descriptor $\varPhi$, if $\{X \in \mathbb {X} \mid X \vDash \varPhi \}$ (we denote it as ${\mathbb {X}}^{\varPhi }$) is not empty, then it has a unique $\leqq$-minimal element denoted by ${\mathbb {X}}^{\varPhi }_{<}$.

A descriptor revision $\circ$ on K is based on (or determined by) some relational model $({\mathbb {X}},\leqq )$ with respect to K iff for any descriptor $\varPhi$,

⁵

$\mathbb {X}$ is the outcome set which includes all the potential outcomes under various belief change patterns. The ordering $\leqq$ (with the strict part <) brings out a direct-selection mechanism, which selects the final outcome among candidates satisfying a specific success condition. We call descriptor revision constructed in this way relational descriptor revision. In so far as the selection mechanism is concerned, descriptor revision is at a more abstract level in comparison to the AGM revision. In the construction of descriptor revision $\circ$, “it assumes that there exists an outcome set which contains all the potential outcomes of the operation $\circ$, but it says little about what these outcomes should be like” (Zhang 2017, p. 41). In contrast, in the AGM framework, the belief change is supposed to satisfy the principle of consistency preservation and the principle of the informational economy (Gärdenfors 1988). Therefore, the intersection step in the construction of belief change in the AGM framework becomes dispensable in the descriptor revision approach.

3.2 Choice revision constructed from descriptor revision

The success condition for choice revision $*_c$ with a finite input could be easily expressed by descriptor $\{ {\mathfrak {B}} \varphi _0 \vee \cdots \vee {\mathfrak {B}} \varphi _n \}$. So, it is straightforward to construct choice revision through descriptor revision as follows.

Definition 2

(Hansson 2017) Let $\circ$ be some descriptor revision. A choice revision $*_c$ on K is based on (or determined by) $\circ$ iff for any finite set A,

$$\begin{aligned} {\langle \circ ~\mathrm {to}~*_c\rangle }\,\,\,\,\,\,\, K *_cA= {\left\{ \begin{array}{ll} K \circ \{ {\mathfrak {B}} \varphi _0 \vee \cdots \vee {\mathfrak {B}} \varphi _n \} &{} \text{ if } A = \{\varphi _0 , \ldots , \varphi _n \} \ne \emptyset ,\\ K &{} \text{ otherwise }. \end{array}\right. } \end{aligned}$$

Henceforth, we say $*_c$ is based on (or determined by) some relational model if it is based on the descriptor revision determined by the same model. The main purpose of this section is to investigate the formal properties of choice revision based on such models.

3.3 Postulates and representation theorem

It is observed that the choice revision determined by relational models should satisfy a set of arguably plausible postulates on choice revision.

Observation 1

Let $*_c$ be a choice revision determined by any relational descriptor revision $({\mathbb {X}},\leqq )$. Then it satisfies the following postulates:

• $\mathrm {(*_c1)}$$\mathrm {Cn}(K *_cA) = K *_cA$. $(*_c$-closure)

• $\mathrm {(*_c2)}$$K *_cA = K$ or $A \cap (K *_cA) \ne \emptyset$. $(*_c$-relative success)

• $\mathrm {(*_c3)}$ If $A \cap (K *_cB) \ne \emptyset$, then $A \cap (K *_cA) \ne \emptyset$. $(*_c$-regularity)

• $\mathrm {(*_c4)}$ If $A \cap K \ne \emptyset$, then $K *_cA = K$. $(*_c$-confirmation)

• $\mathrm {(*_c5)}$ If $(K *_cA) \cap B \ne \emptyset$ and $(K *_cB) \cap A \ne \emptyset$, then $K *_cA = K *_cB$. $(*_c$-reciprocity)

Moreover, another plausible condition on choice revision follows from this set of postulates.

Observation 2

If $*_c$ satisfies $*_c$-closure, relative success, regularity and reciprocity, then $*_c$ satisfies:

• If $A \equiv B$, then $K *_cA = K *_cB$. $(*_c$-syntax irrelevance)

It is easy to see that the postulates in above are natural generalizations of the following postulates on sentential revision:

• $\mathrm {(*1)}$$\mathrm {Cn}(K *\varphi )=K *\varphi$ ($*$-closure)

• $\mathrm {(*2)}$ If $K *\varphi \ne K$, then $\varphi \in K *\varphi$ ($*$-relative success)

• $\mathrm {(*3)}$ If $\varphi \in K$, then $K *\varphi = K$ ($*$-confirmation)

• $\mathrm {(*4)}$ If $\psi \in K *\varphi$, then $\psi \in K *\psi$ ($*$-regularity)

• $\mathrm {(*5)}$ If $\psi \in K *\varphi$ and $\varphi \in K *\psi$, then $K*\varphi = K *\psi$ ($*$-reciprocity⁶)

and

• If $\varphi \dashv \Vdash \psi$, then $K*\varphi = K *\psi$.⁷ ($*$-extensionality)

The above postulates on choice revision are as intuitively plausible as their correspondents on sentential revision, except that the meaning of $*_c$-reciprocity seems not so transparent as that of $*$-reciprocity. However, given some weak conditions, we can show that the $*_c$-reciprocity postulate is equivalent to a more understandable condition as follows.

Observation 3

Let choice operation $*_c$ satisfy $*_c$-relative success and $*_c$-regularity. Then it satisfies $*_c$-reciprocity iff it satisfies:

• If $A \subseteq B$ and $(K *_cB) \cap A \ne \emptyset$, then $K *_cA =K *_cB$. $(*_c$-cautiousness)

The postulate $*_c$-cautiousness reflects a distinctive characteristic of choice revision modelled by relational models: the agent who performs this sort of belief change is cautious in the sense of not doing more than what is necessary to incorporate one of the elements of the input. It follows immediately from $*_c$-relative success and $*_c$-cautiousness that if $A \cap (K *_cA) \ne \emptyset$, then $K *_cA = K *_c\{\varphi \}$ for some $\varphi \in A$. Thus, it is not surprising that the following postulate follows.

Observation 4

If $*_c$ satisfies $*_c$-relative success, regularity and reciprocity, then $*_c$ satisfies:

• $K *_c(A \cup B) = K *_cA$ or $K *_c(A \cup B) = K *_cB$. $(*_c$-dichotomy)

In contrast to $(*_c1)$ through $(*_c5)$, postulates $*_c$-cautiousness and $*_c$-dichotomy do not have directly corresponding postulates in the context of sentential revision. This suggests that though $(*_c1)$ through $(*_c5)$ naturally generalize $(*1)$ through $(*5)$, this sort of generalization is not so trivial as we may think of. As another evidence for this, the following observation shows that the properties of $(*1)$ through $(*5)$ and those of their generalizations are not always paralleled.

Observation 5

Let $*_c$ satisfy $*_c$-regularity. Then it satisfies $*_c$-reciprocity iff it satisfies

• For any $n \ge 1$, if $(K *_cA_1 ) \cap A_0 \ne \emptyset$, $\ldots$, $(K *_cA_{n} ) \cap A_{n-1} \ne \emptyset$, $(K *_cA_{0} ) \cap A_{n} \ne \emptyset$, then $K *_cA_0 = K *_cA_1 = \cdots = K *_cA_n$. $(*_c$-strong reciprocity)

$*$-strong reciprocity is a generalization of the following postulate on sentential revision:

• For any $n \ge 1$, if $\varphi _0 \in K \star \varphi _{1}$, $\ldots$, $\varphi _{n-1} \in K *\varphi _n$ and $\varphi _n \in K \star \varphi _0$, then $K \star \varphi _0 = K \star \varphi _2= \cdots = K \star \varphi _n$. ($*$-strong reciprocity⁸)

However, in contrast to the result in Observation 5, $*$-strong reciprocity is not derivable from $(*1)$ through $(*5)$.⁹

After an investigation on the postulates $(*_c1)$ through $(*_c5)$ satisfied by choice revision based on rational models, the question raises naturally whether the choice revision could be axiomatically characterized by this set of postulates. We get a partial answer to this question: a representation theorem is obtainable when ${\mathcal {L}}$ is finite.

Theorem 1

Let ${\mathcal {L}}$ be a finite language. Then, $*_c$ satisfies $(*_c1)$ through $(*_c5)$ iff it is a choice revision based on some relational model.

3.4 More properties of choice revision

In this subsection, we will study additional properties of choice revision from the point of view of postulates. The postulates introduced in the previous subsection do not necessarily cover all the reasonable properties of this operation. In what follows we are going to investigate some additional ones, in particular, the following:

• If $A \ne \emptyset$, then $A \cap (K *_cA) \ne \emptyset$. ($*_c$-success)

• If $A \not \equiv \{{\scriptstyle \perp }\}$, then $K *_cA \nVdash {\scriptstyle \perp }$. ($*_c$-consistency)

To some extent, $*_c$-success is a strengthening of $*_c$-relative success and $*_c$-regularity, but it does not say anything about the limiting case in which the input is empty. To cover this limiting case, we need the following postulate:

• If $A = \emptyset$, then $K *_cA = K$. ($*_c$-vacuity)

The interrelations among $*_c$-success, $*_c$-relative success and $*_c$-regularity are summarized as follows.

Observation 6

Let $*_c$ be some choice revision on K.

• 1. If $*_c$ satisfies relative success, then it satisfies vacuity.

• 2. If $*_c$ satisfies success and vacuity, then it satisfies relative success.

• 3. If $*_c$ satisfies success, then it satisfies regularity.

$*_c$-consistency is a plausible constraint on a rational agent. While accepting $*_c$-success and $*_c$-consistency as “supplementary” postulates for choice revision $*_c$, the corresponding relational model on which $*_c$ is based will also need to satisfy some additional properties. We use the following representation theorem to conclude this subsection.

Theorem 2

Let ${\mathcal {L}}$ be a finite language and $*_c$ some revision operation on $K \subseteq {\mathcal {L}}$. Then, $*_c$ satisfies $*_c$-closure, $*_c$-success, $*_c$-vacuity, $*_c$-confirmation, $*_c$-reciprocity and $*_c$-consistency iff it is a choice revision determined by some relational model which satisfies the following two condition:

• $(\mathbb {X} 3)$$\mathrm {Cn}(\{ {{\scriptstyle \perp }}\}) \in \mathbb {X}$;

• $(\leqq 3)$${\mathbb {X}}^{{\mathfrak {B}} \varphi } \ne \emptyset$ and ${\mathbb {X}}^{{\mathfrak {B}} \varphi }_{<} < \mathrm {Cn}(\{ {{\scriptstyle \perp }}\})$ for every $\varphi$ such that $\varphi \nVdash {\scriptstyle \perp }$.

4 An alternative modelling for choice revision

In this section, we propose an alternative modelling for choice revision, which is based on so-called multiple believability relations. A believability relation $\preceq$ is a binary relation on sentences of ${\mathcal {L}}$. Intuitively, $\varphi \preceq \psi$ means that the subject is at least as prone to believing $\varphi$ as to believing $\psi$.¹⁰ We can generalize $\preceq$ to a multiple believability relation $\preceq _{*}$ which is a binary relation on the set of all finite subsets of ${\mathcal {L}}$ satisfying:

• $\langle \preceq _{*}$$\mathrm {to}$$\preceq \rangle$      $\varphi \preceq \psi$ iff $\{\varphi \} \preceq _{*} \{\psi \}$.

This kind of generalization can be done in different ways, and at least two distinct relations can be obtained, namely package multiple believability relations, denoted by $\preceq _{p}$, and choice multiple believability relations, denoted by $\preceq _{c}$ (with symmetric part $\simeq _{c}$ and strict part $\prec _{c}$). Intuitively, $A \preceq _{p}B$ means that it is easier for the subject to believe all propositions in A than to believe all propositions in B and $A \preceq _{c}B$ means that it is easier for the subject to incorporate the plausible information in A than that in B.

$\preceq _{p}$ is of little interest since $A \preceq _{p}B$ can be immediately reduced to $\&A \preceq \&B$, given that A and B are finite. In what follows, multiple believability relations (or multi-believability relations for short) only refer to choice multiple believability relations $\preceq _{c}$. ($\{\varphi \} \preceq _{c}A$ and $A \preceq _{c}\{\varphi \}$ will be written as $\varphi \preceq _{c}A$ and $A \preceq _{c}\varphi$ respectively for simplicity.)

4.1 Postulates on multi-believability relations

Recall the following postulates on believability relations $\preceq$ introduced in Zhang (2017):

• $\preceq$-transitivity If $\varphi \preceq \psi$ and $\psi \preceq \lambda$, then $\varphi \preceq \lambda$.

• $\preceq$-weak coupling If $\varphi \simeq \varphi \wedge \psi$ and $\varphi \simeq \varphi \wedge \lambda$, then $\varphi \simeq \varphi \wedge (\psi \wedge \lambda )$.

• $\preceq$-coupling If $\varphi \simeq \psi$, then $\varphi \simeq \varphi \wedge \psi$.

• $\preceq$-counter dominance If $\varphi \Vdash \psi$, then $\psi \preceq \varphi$.

• $\preceq$-minimality$\varphi \in K$ iff $\varphi \preceq \psi$ for all $\psi$.

• $\preceq$-maximality If $\psi \preceq \varphi$ for all $\psi$, then $\varphi \dashv \Vdash {\scriptstyle \perp }$.

• $\preceq$-completeness$\varphi \preceq \psi$ or $\psi \preceq \varphi$

Transitivity is assumed for almost all orderings. In virtue of the intuitive meaning of believability relation, $\varphi \simeq \varphi \wedge \psi$ represents that the agent will accept $\psi$ in the condition of accepting $\varphi$. Thus, the rationale for $\preceq$-weak coupling is that if the agent will consequently add $\psi$ and $\lambda$ to her beliefs when accepting $\varphi$, then she also adds the conjunction of them to her beliefs in this case. This is reasonable if we assume that the beliefs of the agent are closed under the consequence operation. The justification of $\preceq$-counter dominance is that if $\varphi$ logically entails $\psi$, then it will be a smaller change and hence easier for the agent to accept $\psi$ rather than to accept $\varphi$, because then $\psi$ must be added too, if we assume that the beliefs of the agent are represented by a belief set. $\preceq$-coupling is a strengthening of $\preceq$-weak coupling.¹¹ It says that if $\varphi$ is equivalent to $\psi$ in believability, then the agent will consequently add $\psi$ to her beliefs in case of accepting $\varphi$ and vice versa. $\preceq _{c}$-minimality is justifiable since nothing needs to be done to add $\varphi$ to K if it is already in K. $\preceq$-maximality is justifiable since it is reasonable to assume that it is strictly more difficult for a rational agent to accept ${\scriptstyle \perp }$ than to accept any non-falsum. $\preceq$-completeness seems a little bit strong. It says that all pairs of sentences are comparable in believability. In accordance with Zhang (2017), we call relations satisfying all these postulates quasi-linear believability relations.

We can generalize these postulates on believability relations in a natural way to postulates multi-believability relations as follows¹²:

• $\preceq _{c}$-transitivity If $A \preceq _{c}B$ and $B \preceq _{c}C$, then $A \preceq _{c}C$.

• $\preceq _{c}$-weak coupling If and , then .

• $\preceq _{c}$-coupling If $A \simeq _{c}B$, then .

• $\preceq _{c}$-counter dominance If for every $\varphi \in B$ there exists $\psi \in A$ such that $\varphi \Vdash \psi$, then $A \preceq _{c}B$.

• $\preceq _{c}$-minimality$A \preceq _{c}B$ for all B iff $A \cap K \ne \emptyset$.

• $\preceq _{c}$-maximality If B is not empty and $A \preceq _{c}B$ for all non-empty A, then $B \equiv \{{\scriptstyle \perp }\}$.

• $\preceq _{c}$-completeness$A \preceq _{c}B$ or $B \preceq _{c}A$.

These postulates on multi-believability relations can be understood in a similar way that their correspondents on believability relations are understood.

Furthermore, we propose the following two additional postulates on multi-believability relations:

• $\preceq _{c}$-determination$A \prec _{c}\emptyset$ for every non-empty A.

• $\preceq _{c}$-union$A \preceq A \cup B$ or $B \preceq A \cup B$.

At least on the surface, these two could not be generalizations of any postulate on believability relation. In some sense the meaning of $\preceq _{c}$-determination is correspondent to that of $*_c$-success, since if it is a strictly smaller change for the agent to accept some sentences from a non-empty A rather than to take some sentences from the empty set, which is obviously impossible, then it seems to follow that the agent will successfully add some sentences in A to her original beliefs when exposed to the new information represented by A, and vice versa. Similarly, there is an obvious correspondence between the forms and meanings of $\preceq _{c}$-union and $*_c$-dichotomy. They both suggest that to partially accept a non-empty A is equivalent to accept some single sentence in A. This is plausible if we assume that the agent is extremely cautious to the new information.

Observation 7

Let $\preceq _{c}$ be some multi-believability relation satisfying $\preceq _{c}$-transitivity and $\preceq _{c}$-counter dominance. If it satisfies $\preceq _{c}$-union in addition, then

• 1. It satisfies $\preceq _{c}$-completeness.

• 2. It satisfies $\preceq _{c}$-weak coupling iff it $\preceq _{c}$-satisfies coupling.

Observation 7 indicates that $\preceq _{c}$-union is strong. It should be noted that for a believability relation, neither $\preceq$-completeness nor $\preceq$-coupling can be derived from $\preceq$-transitivity, $\preceq$-counter dominance and $\preceq$-weak coupling.¹³

In what follows, we name multi-believability relations satisfying all the above postulates standard multi-believability relations.

4.2 Translations between believability relations and multiple believability relations

In this subsection, we will show that although it is impossible to find a postulate on believability relations that corresponds to $\preceq _{c}$-determination or $\preceq _{c}$-union, there exists a translation between quasi-linear believability relations and standard multi-believability relations.

Observation 8

Let $\preceq _{c}$ satisfy $\preceq _{c}$-determination, $\preceq _{c}$-transitivity and $\preceq _{c}$-counter dominance. Then, for any non-empty finite sets A and B,

• 1. $A \preceq _{c}B$ iff there exists $\varphi \in A$ such that $\varphi \preceq _{c}B$.

• 2. $A \preceq _{c}B$ iff $A \preceq _{c}\varphi$ for all $\varphi \in B$.

This observation suggests that $\preceq$ and $\preceq _{c}$ can be linked through the following two transitions:

• $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$      $\varphi \preceq \psi$ iff $\{\varphi \} \preceq _{c}\{\psi \}$.

• $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$      $A \preceq _{c}B$ iff $B = \emptyset$ or there exists $\varphi \in A$ such that $\varphi \preceq \psi$ for every $\psi \in B$.

This is confirmed by the following theorem.

Theorem 3

• 1. If $\preceq$ is a quasi-linear believability relation and $\preceq _{c}$ is constructed from $\preceq$ through the way of $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$, then $\preceq _{c}$ is a standard multi-believability relation and $\preceq$ can be retrieved from $\preceq _{c}$ in the way of $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$.

• 2. If $\preceq _{c}$ is a standard multi-believability relation and $\preceq$ is constructed from $\preceq _{c}$ through $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$, then $\preceq$ is a quasi-linear believability relation and $\preceq _{c}$ can be retrieved from $\preceq$ through $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$.

4.3 Choice revision constructed from multi-believability relations

Now we turn to the construction of choice revision through multi-believability relations. Recall that a sentential revision $*$ can be constructed from a believability relation $\preceq$ in this way (Zhang 2017):

$$\begin{aligned} {\langle \preceq ~\mathrm {to}~*\rangle }\,\,\,\,\,\,\,K *\varphi = \{ \psi \mid \varphi \simeq \varphi \wedge \psi \} \end{aligned}$$

As we have explained, $\varphi \simeq \varphi \wedge \psi$ could be understood as that the agent will consequently accept $\psi$ in case of accepting $\varphi$. So, the set $\{ \psi \mid \varphi \simeq \varphi \wedge \psi \}$ is just the agent’s new set of beliefs after she performed belief revision with input $\varphi$. Thus, we can similarly construct choice revision from multi-believability relations in the following way.

Definition 3

Let $\preceq _{c}$ be some multi-believability relation. A choice revision $*_c$ on K is based on (or determined by) $\preceq _{c}$ iff: for any finite A,

The primary results of this section are the following two representation theorems. In comparison with Theorems 1 and 2, these two theorems are applicable to more general cases since they do not assume that the language ${\mathcal {L}}$ is finite. These two theorems demonstrate that multi-believability relations provide a fair modelling for choice revision characterized by the set of postulates mentioned in Sect. 3.

Theorem 4

Let $*_c$ be some choice revision on K. Then, $*_c$ satisfies $(*_c1)$ through $(*_c5)$ iff it is determined by some multi-believability relation $\preceq _{c}$ satisfying $\preceq _{c}$-transitivity, $\preceq _{c}$-weak coupling, $\preceq _{c}$-counter-dominance, $\preceq _{c}$-minimality and $\preceq _{c}$-union.

Theorem 5

Let $*_c$ be some choice revision on K. Then, $*_c$ satisfies $*_c$-closure, $*_c$- success, $*_c$-vacuity, $*_c$-confirmation, $*_c$-reciprocity and $*_c$-consistency iff it is determined by some standard multi-believability relation.

Considering the translation between multi-believability relations and believability relations (Theorem 3), it seems that these results can be easily transferred to the context of believability relations. However, if we drop some postulates on multi-believability relation such as $\preceq _{c}$-determination, the translation between multi-believability relation and believability relation will not be so transparent, at least it will not be so straightforward as $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$ and $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$. As a consequence, the result in Theorem 4 may not be possible to transfer to believability relations in a straightforward way. Moreover, compared with postulates on believability relations, postulates on multi-believability relations such as $\preceq _{c}$-determination and $\preceq _{c}$-union can present our intuitions on choice revision in a more direct way. Thus, the multi-believability relation is still worth to be studied in its own right.

5 Conclusion and future work

As a generalization of traditional belief revision, choice revision has more realistic characteristics. The new information is represented by a set of sentences and the agent could partially accept these sentences as well as reject the others. From the point of technical view, choice revision is interesting since the standard “select-and-intersect” methodology in modellings for belief change is not suitable for it. But instead, it can be modelled by a newly developed framework of descriptor revision, which employs a “select-direct” approach. After reviewing the construction of choice revision in the framework of descriptor revision, under the assumption that the language is finite, we provided two sets of postulates as the axiomatic characterizations for two variants of choice revision based on such constructions (in Theorems 1 and 2). These postulates, in particular, $*_c$-cautiousness and $*_c$-dichotomy, point out that choice revision modelled by descriptor revision has the special characteristic that the agent who performs this sort of belief change is cautious in the sense that she only accepts the new information to the smallest possible extent.

For AGM revision and contraction, there are various independently motivated modellings which are equivalent in terms of expressive power. In this contribution, we also propose an alternative modelling for choice revision. We showed that multi-believability relations can also construct the choice revision axiomatically characterized by the sets of postulates proposed for choice revision based on descriptor revision (Theorems 4 and 5). Moreover, these results are obtainable without assuming that the language is finite. This may indicate that multi-believability relations are an even more suitable modelling for choice revision.

The study in this contribution can be developed in at least three directions. First, the cautiousness constraint on choice revision, reflected by $*_c$-cautiousness, certainly could be loosened. We think it is an interesting topic for future work to investigate the modeling and axiomatic characterization of more “reckless” variants of choice revision. Secondly, as it was showed in Zhang (2017) that AGM revision could be reconstructed from believability relations satisfying certain conditions, it is interesting to ask which conditions a multi-believability relation should satisfy so that its generated choice revision coincides with an AGM revision when the inputs are limited to singletons. Finally, it is technically interesting to investigate choice revisions with an infinite input set, though they are epistemologically unrealistic.

Appendix: Proofs

Lemma 1

Let $\preceq _{c}$ be some multiple believability relation which satisfies $\preceq _{c}$-counter-dominance and $\preceq _{c}$-transitivity. Then,

• 1. If $\preceq _{c}$ satisfies $\preceq _{c}$-union, then for every non-empty A, there exists some $\varphi \in A$ such that $\varphi \simeq _{c}A$.

• 2. For every $\varphi \in A$, iff $\varphi \simeq _{c}A$.

Proof (For Lemma 1)

• 1. We prove this by mathematical induction on the size n ($n \ge 1$) of A. Let $n = 1$, then it follows immediately. Suppose hypothetically that it holds for $n = k$ ($k \ge 1$). Let $n = k+1$. Since $k \ge 1$, there exists a non-empty set B containing k elements and a sentence $\varphi$ such that $A = B \cup \{\varphi \}$. By $\preceq _{c}$-counter dominance and $\preceq _{c}$-union, (i) $A \simeq _{c}\{\varphi \}$ or (ii) $A \simeq _{c}B$. The case of (i) is trivial. In the case of (ii), by the hypothetical supposition, there exists some $\psi \in B \subseteq A$ such that $A \simeq _{c}B \simeq _{c}\psi$. So, by $\preceq _{c}$-transitivity, $A \simeq _{c}\varphi$. To sum up (i) and (ii), there always exists some $\varphi \in A$ such that $\varphi \simeq _{c}A$.

• 2. From left to right Let $\varphi \in A$ and . By $\preceq _{c}$-counter dominance, $A \preceq _{c}\varphi$ and . And it follows from and that $\varphi \preceq _{c}A$ by $\preceq _{c}$-transitivity. Thus, $\varphi \simeq _{c}A$. From right to left Let $\varphi \in A$ and $\varphi \simeq A$. By $\preceq _{c}$-counter-dominance, . So by $\preceq _{c}$-transitivity. Moreover, by $\preceq _{c}$-counter-dominance. Thus, .    $\square$

Proof (For Observation 1)

It is easy to see that $*_c$ satisfies $*_c$-closure and $*_c$-relative success. We only check the remaining three postulates. We let ${\mathfrak {B}}^{\vee }{A}$ denote the descriptor $\{ {\mathfrak {B}} \varphi _0 \vee \cdots \vee {\mathfrak {B}} \varphi _n\}$ when $A = \{ \varphi _0 , \ldots , \varphi _n\} \ne \emptyset$.

$*_c$-regularity Let $(K *_cB) \cap A \ne \emptyset$. It follows that $A \ne \emptyset$ and ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}} \ne \emptyset$. So $K *_cA = {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}_{<}$ by the definition of $*_c$. Thus, $(K *_cA) \cap A \ne \emptyset$.

$*_c$-confirmation Let $A \cap K \ne \emptyset$. Then $A \ne \emptyset$ and $K \in {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}$. It follows from $(\leqq 1)$ and $(\leqq 2)$ that K is the unique $\leqq$-minimal element in ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}$. Thus, $K *_cA = {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}_{<} = K$.

*c-reciprocity Let $(K *_cA_0 ) \cap A_1 \ne \emptyset$ and $(K *_cA_{1} ) \cap A_{0} \ne \emptyset$. Let $i \in \{0,1\}$. It follows that $A_i \ne \emptyset$ and ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{(}A_i)} \ne \emptyset$ and hence $K *_cA_i = {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{(}A_i)}_{<}$ by the definition of $*_c$. So it follows from ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_0}}_{<} \cap A_1 \ne \emptyset$ and ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_1}}_{<} \cap A_{0} \ne \emptyset$ that ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_0}}_{<} \in {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_1}}$ and ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_1}}_{<} \in {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_0}}$ and hence ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_0}}_{<} \leqq {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_1}}_{<} \leqq {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_0}}_{<}$ by $(\leqq 2)$. Since the minimal element in ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{(}A_0)}$ is unique by $(\leqq 2)$, it follows that ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_0}}_{<} = {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A_1}}_{<}$, i.e. $K *_cA_{0} = K *_cA_{1}$. $\square$

Proof (For Observation 2)

Let $A \equiv B$. Suppose $A \cap (K *_cA) = \emptyset$, then $A \cap (K *_cB) = \emptyset$ due to $*_c$-regularity. Hence, $B \cap (K *_cB) = \emptyset$ by $*_c$-closure. It follows that $K *_cA = K *_cB = K$ by $*_c$-relative success. Suppose $A \cap (K *_cA) \ne \emptyset$, then $B \cap (K *_cA) \ne \emptyset$ by $*_c$-closure, so $B \cap (K *_cB) \ne \emptyset$ by $*_c$-regularity, and hence $A \cap (K *_cB) \ne \emptyset$ by $*_c$-closure. It follows that $K *_cA = K *_cB$ by $*_c$-reciprocity. Thus, $*_c$ satisfies syntax irrelevance in any case. $\square$

Proof (For Observation 3)

From left to right Let $A \subseteq B$ and $(K *_cB) \cap A \ne \emptyset$. Then, $A \ne \emptyset$ and hence $(K *_cA) \cap A \ne \emptyset$ by $*_c$-regularity. Since $A \subseteq B$, it follows that $(K *_cA) \cap B \ne \emptyset$. Thus, $K *_cA =K *_cB$ by $*_c$-reciprocity.

From right to left Let $A \cap (K *_cB) \ne \emptyset$ and $B \cap (K *_cA) \ne \emptyset$. It follows that $(A \cup B) \cap (K *_cB) \ne \emptyset$. By $*_c$-regularity, it follows that $(A \cup B) \cap (K *_c(A \cup B)) \ne \emptyset$. So $A \cap (K *_c(A \cup B)) \ne \emptyset$ or $B \cap (K *_c(A \cup B)) \ne \emptyset$. Without loss of generality, let $A \cap (K *_c(A \cup B)) \ne \emptyset$, then $K *_cA = K *_c(A \cup B)$ by $*_c$-cautiousness. It follows that $B \cap (K *_c(A \cup B)) = B \cap (K *_cA) \ne \emptyset$ and hence $K *_cB = K *_c(A \cup B)$ by $*_c$-cautiousness. So $K *_cA = K *_c(A \cup B) = K *_cB$. $\square$

Proof (For Observation 4)

Suppose $(A \cup B) \cap (K *_c(A\cup B)) = \emptyset$, then $(A \cup B) \cap (K *_cA) = (A \cup B) \cap (K *_cB)= \emptyset$ by $*_c$-regularity. So $A \cap (K *_cA) = B \cap (K *_cB) = \emptyset$ and hence $K *_c(A \cup B) = K *_cA = K *_cB = K$ by $*_c$-relative success. Suppose $(A \cup B) \cap (K *_c(A\cup B)) \ne \emptyset$, then $A \cap (K *_c(A\cup B)) \ne \emptyset$ or $B \cap (K *_c(A\cup B)) \ne \emptyset$. Let $A \cap (K *_c(A\cup B)) \ne \emptyset$, then $A \cap (K *_cA) \ne \emptyset$ by $*_c$-regularity and hence $(A \cup B) \cap (K *_cA) \ne \emptyset$. It follows that $K *_c(A \cup B) = K *_cA$ by $*_c$-reciprocity. Similarly, we can show that $K *_c(A \cup B) = K *_cB$ holds in the case of $B \cap (K *_c(A\cup B)) \ne \emptyset$. Thus, $*_c$ satisfies $*_c$-dichotomy in any case. $\square$

Proof (For Observation 5)

From right to left It follows immediately.

From left to right Assume $(\star )$ that $(K *_cA_1 ) \cap A_0 \ne \emptyset$, $\ldots$, $(K *_cA_n ) \cap A_{n-1} \ne \emptyset$ and $(K *_cA_{0} ) \cap A_{n} \ne \emptyset$ for some $n \ge 1$. We prove that $K *_cA_0 = K *_cA_1 = \cdots = K *_cA_n$ by mathematical induction on n. For $n =1$, this follows immediately from $*_c$-reciprocity. Let us hypothetically suppose that it holds for $n = k$ ($k \ge 1$), then we should show that it also holds for $n = k+1$.

Let $A = \bigcup _{0 \le i \le k+1} A_{i}$.¹⁴ It follows from $(\star )$ that $A \cap (K *_cA_i) \ne \emptyset$ for every $0 \le i \le k+1$. So $A \cap (K *_cA) \ne \emptyset$ by $*_c$-regularity. It follows that there exists some j with $0 \le j \le k+1$ such that $A_j \cap (K *_cA) \ne \emptyset$. Moreover, according to $(\star )$, if $j = 0$ then $A_{k+1} \cap (K *_cA_j) \ne \emptyset$ else $A_{j-1} \cap (K *_cA_j) \ne \emptyset$. It follows that $A \cap (K *_cA_j) \ne \emptyset$ in any case. So $K *_cA_j = K *_cA$ by $*_c$-reciprocity. Hence, as $A \cap (K *_cA_i) \ne \emptyset$ for every $0 \le i \le k+1$, it follows from $(\star )$ and $*_c$-reciprocity that if $0<j \le k+1$, then $K *_cA_j =K *_cA = K *_cA_{j-1}$ else $K *_cA_j =K *_cA = K *_cA_{k+1}$. In each case, the length of the loop is reduced to k. So, it follows from the hypothetical supposition that $K *_cA_0 = K *_cA_1 = \cdots = K *_cA_{k+1}$. Thus, $*_c$ satisfies strong reciprocity.    $\square$

Proof (For Theorem 1)

• From construction to postulates See Observation 1.

• From postulates to construction Let $\mathbb {X}=\{ K*_cA \mid A \subseteq {\mathcal {L}} \text{ and } A \text{ is } \text{ finite }\}$. Let $\leqq ^{\prime }$ be a relation on $\mathbb {X}$ defined as $X \leqq ^{\prime } Y$ iff there exist elements $A_0$, $\ldots$, $A_n$ of ${\mathcal {L}}$ such that $X = K *_cA_0$, $Y = K *_cA_n$ and $(K *_cA_1 ) \cap A_0 \ne \emptyset$, $\ldots$, $(K *_cA_n ) \cap A_{n-1} \ne \emptyset$. We first show that $\leqq ^{\prime }$ is a partial order:

• Reflexivity Let $X = K *_cA$. If $X =K$, since K is belief set, $X = K *_c\{{\scriptstyle \top }\}$ by $*_c$-confirmation. Moreover, by $*_c$-closure, ${\scriptstyle \top }\in K *_c\{{\scriptstyle \top }\}$. So $X \leqq ^{\prime } X$. If $X \ne K$, then $A \cap (K *_cA) \ne \emptyset$ by relative success. It follows immediately that $X \leqq ^{\prime } X$. Thus, $X \leqq ^{\prime } X$ holds for every $X \in \mathbb {X}$.

• Transitivity It follows immediately from the definition of $\leqq ^{\prime }$.

• Anti-symmetry By Observation 5, $*_c$ satisfies $*_c$-strong reciprocity. It follows immediately from this and the definition of $\leqq ^{\prime }$ that $\leqq ^{\prime }$ is anti-symmetric. So, given the axiom of choice, there exists a linear order $\leqq$ such that $\leqq ^{\prime } \subseteq \leqq$.¹⁵ We will show that $(\mathbb {X}, \leqq )$ is the relational model we are looking for.

• $(\mathbb {X} 1)$: It is immediate from $*_c$-closure.

• $(\mathbb {X} 2)$: It is immediate from that $K *_c\emptyset \in \mathbb {X}$ and $*_c$ satisfies $*_c$-relative success.

• $(\leqq 1)$: Since K is a belief set, $K = K *_c\{{\scriptstyle \top }\}$ by $*_c$-confirmation. Moreover, by $*_c$-closure, ${\scriptstyle \top }\in X$ for every $X \in \mathbb {X}$. So $K \leqq ^{\prime } X$ for for every $X \in \mathbb {X}$. Thus, as $\leqq ^{\prime } \subseteq \leqq$, $K \leqq X$ for every $X \in \mathbb {X}$.

• $(\leqq 2)$: Since ${\mathcal {L}}$ is finite, it is easy to see that the quotient of its power set under the equivalence relation $\equiv$ is finite. Moreover, by Observation 2, $*_c$ satisfies syntax-irrelevance. It follows that $\mathbb {X}$ is finite. And as we have proved, $\leqq$ is a linear order. So $\leqq$ is well-ordered and hence $(\leqq 2)$ holds. In order to show that $*_c$ is based on $({\mathbb {X}},\leqq )$, we need to consider two cases:

• (i) $K *_cA =K$: In this case, we just need to prove that if $A \ne \emptyset$ and ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}} \ne \emptyset$, then $K \in {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}$. It follows from $A \ne \emptyset$ and ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}} \ne \emptyset$ that there exists some B such that $A \cap (K *_cB )\ne \emptyset$. So $A \cap (K *_cA) \ne \emptyset$ by $*_c$-regularity. So, $A \cap K \ne \emptyset$ and hence $K \in {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}$.

• (ii) $K *_cA \ne K$: In this case, we only need to show that ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}} \ne \emptyset$ and $K *_cA = {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}_{<}$. Since $K *_cA \ne K$, $(K *_cA) \cap A \ne \emptyset$ by $*_c$-relative success. So ${\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}} \ne \emptyset$ and $K *_cA \leqq ^{\prime } X$ for every $X \in {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}$. This means that $K *_cA \leqq X$ for every $X \in {\mathfrak {B}}^{\vee }{\varPhi (A)}$ since $\leqq ^{\prime } \subseteq \leqq$. Moreover, as we have shown, $\leqq$ is a linear order. Thus, $K *_cA = {\mathbb {X}}^{{\mathfrak {B}}^{\vee }{A}}_{<}$. To sum up (i) and (ii), $*_c$ is based on $({\mathbb {X}},\leqq )$.    $\square$

Proof (For Observation 6)

• 1. Let $A \ne \emptyset$, then $A \cap (K *_cA) = \emptyset$. So, by $*_c$-relative success, $K *_cA = K$.

• 2. Let $A \cap (K *_cA) = \emptyset$. Then, by $*_c$-success, it follows that $A = \emptyset$. So, by vacuity, $K *_cA = K$.

• 3. Let $A \cap (K *_cB) \ne \emptyset$, then $A \ne \emptyset$. So, by $*_c$-success, $A \cap (K *_cA) \ne \emptyset$.

$\square$

Proof (For Theorem 2)

• From right to left We only need to check success, vacuity and consistency.

• $*_c$-success: It follows immediately from $(\mathbb {X} 3)$.

• $*_c$-vacuity: It follows immediately from ${\langle \leqq \mathrm {to}~\circ \rangle }$ and ${\langle \circ ~\mathrm {to}~*_c\rangle }$.

• $*_c$-consistency: It follows immediately from $(\leqq 3)$. From left to right Let $({\mathbb {X}},\leqq )$ be defined in the same way as the relational model constructed in the proof of Theorem 1. By Observation 6, $*_c$ satisfies all postulates listed in Theorem 1. So it is also true that $({\mathbb {X}},\leqq )$ constructed in this way is indeed a relational model from which a choice revision $*_c$ can be derived. In order to complete the proof, we only need to check that $({\mathbb {X}},\leqq )$ satisfies $(\mathbb {X} 3)$ and $(\leqq 3)$: Since $*_c$ satisfies $*_c$-success and $*_c$-closure, $K *_c\{{\scriptstyle \perp }\} = \mathrm {Cn}(\{ {{\scriptstyle \perp }}\}) \in \mathbb {X}$, i.e. $(\mathbb {X} 3)$ holds of $({\mathbb {X}},\leqq )$. Moreover, since $*_c$ satisfies $*_c$-consistency, $K *_c\{\varphi \} \ne \mathrm {Cn}(\{ {{\scriptstyle \perp }}\})$ for every $\varphi \not \equiv {\scriptstyle \perp }$. It follows that $K *_c\{\varphi \} = {\mathbb {X}}^{{\mathfrak {B}} \varphi }_{<} < \mathrm {Cn}(\{ {{\scriptstyle \perp }}\})$. So, $(\leqq 3)$ also holds of $({\mathbb {X}},\leqq )$.

$\square$

Proof (For Observation 7)

• 1. It follows from $\preceq _{c}$-counter dominance that $A \cup B \preceq _{c}A$ and $A \cup B \preceq _{c}B$. Moreover, by $\preceq _{c}$-union, $A \preceq _{c}A\cup B$ or $B \preceq _{c}A \cup B$. So $A \preceq _{c}B$ or $B \preceq _{c}A$ by $\preceq _{c}$-transitivity.

• 2. From left to right: We first prove that $\preceq _{c}$-coupling holds for all singletons, i.e. if $\varphi \simeq _{c}\psi$, then $\varphi \simeq _{c}\varphi \wedge \psi$. Let $\varphi \simeq _{c}\psi$ and $A = \{\varphi , \psi \}$. Since it is immediate from $\preceq _{c}$-counter dominance that $\varphi \preceq _{c}\varphi \wedge \psi$, we only need to show $\varphi \wedge \psi \preceq _{c}\varphi$. By the first item of Lemma 1 and $\preceq _{c}$-transitivity, $A \simeq _{c}\varphi$ and $A \simeq _{c}\psi$. So, by the second item of Lemma 1, and . So, by $\preceq _{c}$-weak coupling, . By $\preceq _{c}$-counter dominance, . So and hence $\varphi \wedge \psi \preceq _{c}\varphi$ by $\preceq _{c}$-transitivity.

Now we prove that $\preceq _{c}$-coupling holds in general. Let $A \simeq _{c}B$. If $A = \emptyset$, it follows immediately from $\preceq _{c}$-counter-dominance that . If $B = \emptyset$, it follows from $A \simeq _{c}B = \emptyset$ that . If $A \ne \emptyset$ and $B \ne \emptyset$, then there exist $\varphi \in A$ and $\psi \in B$ such that $\varphi \simeq _{c}A$ and $\psi \simeq _{c}B$ by the first item of Lemma 1. So, by $\preceq _{c}$-transitivity, $\varphi \simeq _{c}\psi$. So $\varphi \simeq _{c}\varphi \wedge \psi$ as we have shown that $\preceq _{c}$-coupling holds for all singletons. Moreover, by $\preceq _{c}$-counter-dominance. So and hence by $\preceq _{c}$-transitivity. Moreover, by $\preceq _{c}$-counter-dominance. Thus, .

From right to left Let and . By $\preceq _{c}$-transitivity, . So by $\preceq _{c}$-coupling and hence by $\preceq _{c}$-transitivity. In order to complete the proof, we only need to show that . If $A = \emptyset$ or $B = \emptyset$ or $C = \emptyset$, then by $\preceq _{c}$-counter-dominance. If they are all non-empty, it also follows immediately from $\preceq _{c}$-counter-dominance that . $\square$

Proof (For Observation 8)

• 1. From left to right Let $A \preceq _{c}B$. By the first item of Lemma 1, there exists some $\varphi$ in A such that $\varphi \simeq _{c}A$. Thus, $\varphi \preceq _{c}B$ by $\preceq _{c}$-transitivity. From right to left Suppose there exists some $\varphi \in A$ such that $\varphi \preceq _{c}B$. By $\preceq _{c}$-counter dominance, $A \preceq _{c}\varphi$. Thus, $A \preceq _{c}B$ by $\preceq _{c}$-transitivity.

• 2. From left to right Let $A \preceq _{c}B$. By $\preceq _{c}$-counter dominance, $B \preceq _{c}\varphi$ for every $\varphi \in B$. Thus, by $\preceq _{c}$-transitivity, $A \preceq _{c}\varphi$ for all $\varphi \in B$. From right to left Let $A \preceq _{c}\varphi$ for all $\varphi \in B$. By the first item of Lemma 1, there exists some $\psi$ in B such that $\psi \simeq _{c}B$. So $A \preceq _{c}\psi \simeq _{c}B$ and hence $A \preceq _{c}B$ by $\preceq _{c}$-transitivity.

$\square$

Proof (For Theorem 3)

• 1. Let $\preceq$ be a quasi-linear believability relation and $\preceq _{c}$ constructed from $\preceq$ through $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$. We first check that $\preceq _{c}$ is a standard multiple believability relation.

  • $\preceq _{c}$-determination It follows immediately from $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$ that $\emptyset \not \preceq _{c}A$ and $A \preceq _{c}\emptyset$ for every non-empty A. Thus, $\emptyset \prec _{c}A$ for every non-empty A.

  • $\preceq _{c}$-union If $A = \emptyset$ and $B = \emptyset$, then it follows immediately from $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$ that $\preceq _{c}$-union holds for $\preceq _{c}$. If $A \ne \emptyset$ or $B \ne \emptyset$, then $A \cup B \ne \emptyset$. Since both A and B are finite and $\preceq$ satisfies $\preceq$-completeness, there exists some $\varphi \in A \cup B$ such that $\varphi \preceq \lambda$ for every $\lambda \in A \cup B$. It follows that there exists some $\varphi \in A$ such that $\varphi \preceq \lambda$ for every $\lambda \in A \cup B$ or there exists some $\varphi \in B$ such that $\varphi \preceq \lambda$ for every $\lambda \in A \cup B$. So, by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$, $A \preceq _{c}A \cup B$ or $B \preceq _{c}A \cup B$.

  • $\preceq _{c}$-transitivity Let $A \preceq _{c}B$ and $B \preceq _{c}C$. If $C = \emptyset$, then it follows immediately from $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \preceq _{c}C$. If $C \ne \emptyset$, then $A \ne \emptyset$ and $B \ne \emptyset$ since $A \preceq _{c}B$, $B \preceq _{c}C$ and $\preceq _{c}$ satisfies $\preceq _{c}$-determination as we have shown. So, by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$, there exists some $\varphi \in A$ such that $\varphi \preceq \psi$ for every $\psi \in B$ and there exists some $\psi \in B$ such that $\psi \preceq \lambda$ for every $\lambda \in C$. So, by $\preceq$-transitivity, there exists some $\varphi \in A$ such that $\varphi \preceq \lambda$ for every $\lambda \in C$. Thus, $A \preceq _{c}C$ by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$.

  • $\preceq _{c}$-counter-dominance Assume $(\star )$ that for every $\varphi \in B$, there exists some $\psi \in A$ such that $\varphi \Vdash \psi$. If $B = \emptyset$, then it follows directly from $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \preceq _{c}B$. If $B \ne \emptyset$, since B is finite and $\preceq$ satisfies $\preceq$-completeness, there exists some $\varphi \in B$ such that $\varphi \preceq \lambda$ for every $\lambda \in B$. Moreover, by $(\star )$, there exists some $\psi \in A$ such that $\varphi \Vdash \psi$, and hence $\psi \preceq \varphi$ by $\preceq$-counter dominance. So, by $\preceq$-transitivity, $\psi \preceq \lambda$ for every $\lambda \in B$. Thus, $A \preceq _{c}B$ by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$.

  • $\preceq _{c}$-coupling Let $A \simeq _{c}B$. If $A = \emptyset$, then it follows directly from $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$ that . If $B = \emptyset$, then it follows immediately from $A \simeq _{c}B = \emptyset$ that . If $A \ne \emptyset$ and $B\ne \emptyset$, since $\preceq _{c}$ satisfies $\preceq _{c}$-union, $\preceq _{c}$-transitivity and $\preceq _{c}$-counter dominance as we have shown, by the first item of Lemma 1, there exist $\varphi \in A$ and $\psi \in B$ such that $\varphi \simeq _{c}A$ and $\psi \simeq _{c}B$. So, by $\preceq _{c}$-transitivity, $\varphi \simeq _{c}\psi$ and hence $\varphi \simeq \psi$ by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$. It follows that $\varphi \simeq \varphi \wedge \psi$ by $\preceq$-coupling. So $\varphi \simeq _{c}\varphi \wedge \psi$ by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$. Moreover, by $\preceq _{c}$-counter dominance. So, and hence by $\preceq _{c}$-transitivity. It is immediate from $\preceq _{c}$-counter dominance that . Thus, .

  • $\preceq _{c}$-minimalityFrom left to right Suppose $A \preceq _{c}B$ for all B. It follows that $A \preceq _{c}{\scriptstyle \top }$. So there exists some $\varphi \in A$ such that $\varphi \preceq {\scriptstyle \top }$ by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$. So $\varphi \preceq \psi$ for all $\psi$ by $\preceq$-counter dominance and $\preceq$-transitivity. So, by $\preceq$-minimality, $\varphi \in K$. Thus, $A \cap K \ne \emptyset$. From right to left Let $A \cap K \ne \emptyset$, i.e. there exists some $\varphi \in A \cap K$. Since $\varphi \in K$, $\varphi \preceq \psi$ for all $\psi$ by $\preceq$-minimality. So $A \preceq _{c}B$ for all B by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$.

  • $\preceq _{c}$-maximality Let A be non-empty and $B \preceq _{c}A$ for all non-empty B. Then, $\perp \preceq _{c}A$ and hence by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$${\scriptstyle \perp }\preceq \varphi$ for every $\varphi \in A$. So, due to $\preceq$-counter dominance and $\preceq$-transitivity, for every $\varphi \in A$, $\psi \preceq \varphi$ for all $\varphi \in {\mathcal {L}}$. Hence, for every $\varphi \in A$, $\varphi \dashv \Vdash {\scriptstyle \perp }$ due to $\preceq$-maximality. Thus, $A \equiv \{{\scriptstyle \perp }\}$.

  • Let $\preceq ^{\prime }$ be the believability relation derived from $\preceq _{c}$ through $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$. It is easy to see that $\varphi \preceq \psi$ iff $\varphi \preceq _{c}\psi$ iff $\varphi \preceq ^{\prime } \psi$. Thus, $\preceq$ can be retrieved from $\preceq _{c}$ through $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$.

• 2. It is easy to see that $\preceq$ satisfies $\preceq$-transitivity, $\preceq$-counter dominance, $\preceq$-coupling and $\preceq$-completeness. In what follows we only check $\preceq$-minimality and $\preceq$-maximality.

  • $\preceq$-minimalityFrom left to right Let $\varphi \in K$. Then, $\varphi \preceq _{c}\psi$ for all $\psi$ due to $\preceq _{c}$-minimality. Thus, $\varphi \preceq \psi$ for all $\psi$ by $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$. From right to left Let $\varphi \preceq \psi$ for all $\psi$. Then $\varphi \preceq _{c}\psi$ for all $\psi$ by $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$. So, by the second item of Observation 8, $\varphi \preceq _{c}B$ for all non-empty B. Moreover, due to $\preceq _{c}$-counter-dominance, $\varphi \preceq _{c}\emptyset$. Thus, by $\preceq _{c}$-minimality, $\varphi \in K$.

  • $\preceq$-maximality Let $\psi \preceq \varphi$ for all $\psi$. Then $\psi \preceq _{c}\varphi$ for all $\psi$ by $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$. So, by the first item of Observation 8, $B \preceq _{c}\varphi$ for all non-empty B. So, due to $\preceq _{c}$- maximality, $\varphi \dashv \Vdash {\scriptstyle \perp }$.

    In order to prove that $\preceq _{c}$ can be retrieved from $\preceq$ through $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$, let $\preceq _{c}^{\prime }$ be the multi-believability relation derived from $\preceq$ through $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$. We need to show that $A \preceq _{c}B$ iff $A \preceq _{c}^{\prime } B$.

  • From left to right Let $A \preceq _{c}B$. If $B = \emptyset$, it follows directly from $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \preceq _{c}^{\prime } B$. If $A = \emptyset$, then $B= \emptyset$ by $\preceq _{c}$-determination. It also follows immediately from $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \preceq _{c}^{\prime } B$. If $A \ne \emptyset$ and $B \ne \emptyset$, then, by Observation 8, there exists some $\varphi \in A$ such that $\varphi \preceq _{c}\psi$ for all $\psi \in B$. So, by $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$, there exists some $\varphi \in A$ such that $\varphi \preceq \psi$ for all $\psi \in B$. Hence, by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$, $A \preceq _{c}^{\prime } B$.

  • From right to left Let $A \preceq _{c}^{\prime } B$. If $B = \emptyset$, then it follows directly from $\preceq _{c}$-counter dominance that $A \preceq _{c}B$. If $B \ne \emptyset$, then there exists some $\varphi \in A$ such that $\varphi \preceq \psi$ for all $\psi \in B$ by $\langle \preceq$$\mathrm {to}$$\preceq _{c}\rangle$. So there exists some $\varphi \in A$ such that $\varphi \preceq _{c}\psi$ for all $\psi \in B$ by $\langle \preceq _{c}$$\mathrm {to}$$\preceq \rangle$. Hence, by Observation 8, $A \preceq _{c}B$. $\square$

Proof (For Theorem 4)

• From construction to postulates$*_c$-closure We need to prove that $K *_cA$ is a belief set for every A. If $\emptyset \preceq _{c}A$, it follows from $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$ that $K *_cA = K$. So $K *_cA$ is belief set since K is belief set. If $\emptyset \not \preceq _{c}A$, then $A \prec _{c}\emptyset$ by $\preceq _{c}$-counter dominance and hence by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. Moreover, it follows from $\emptyset \not \preceq _{c}A$ and $\preceq _{c}$-counter dominance that $A \ne \emptyset$. So, by Lemma 1, . Let $\varphi \in K *_cA$, $\psi \in K *_cA$ and $\varphi \wedge \psi \Vdash \lambda$, in order to complete the proof, we need to show that $\lambda \in K *_cA$. By $\preceq _{c}$-weak coupling, it follows from and that . By $\preceq _{c}$-counter dominance and $\varphi \wedge \psi \Vdash \lambda$, . So by $\preceq _{c}$-transitivity. Moreover, by $\preceq _{c}$-counter dominance. Thus, , i.e. $\lambda \in K *_cA$.

• $*_c$-relative success Let $K *_cA \ne K$. Then, by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$, $A \prec _{c}\emptyset$. So, by $\preceq _{c}$-counter dominance, $A \ne \emptyset$ and hence, by Lemma 1, there exists some $\varphi \in A$ such that . Moreover, by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$, when $A \prec _{c}\emptyset$. Thus, $A \cap K *_cA \ne \emptyset$.

• $\preceq _{c}$-confirmation Let $A \cap K \ne \emptyset$, i.e. there exists some $\psi \in A \cap K$. Suppose $A \not \prec _{c}\emptyset$, then it follows immediately from $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$ that $K *_cA =K$. Suppose $A \prec \emptyset$, then, by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$, we only need to show that . From left to right inclusion direction Let $\lambda \in K$. By $\preceq _{c}$-counter dominance, . Since K is a belief set, it follows from $\lambda \in K$ and $\psi \in K$ that $\lambda \wedge \psi \in K$. Hence, $\lambda \wedge \psi \preceq _{c}A$ by $\preceq _{c}$-minimality. So by $\preceq _{c}$-transitivity. Moreover, by $\preceq _{c}$-counter dominance. So, . From right to left inclusion direction Let . By $\preceq _{c}$-counter dominance, and $A \preceq _{c}\psi$. So, and hence $\lambda \preceq _{c}\psi$ by $\preceq _{c}$-transitivity. Since $\psi \in K$, $\psi \preceq _{c}B$ for all B by $\preceq _{c}$-minimality. So, by $\preceq _{c}$-transitivity, $\lambda \preceq _{c}B$ for all B and hence $\lambda \in K$ by $\preceq _{c}$-minimality. To sum up (i) and (ii), when $A \prec _{c}\emptyset$.

• $*_c$-regularity Let $A \cap (K *_cB) \ne \emptyset$. (i) Let $K *_cB = K$, then $A \cap K = A \cap (K *_cB) \ne \emptyset$. As we have shown that $*_c$-confirmation holds of $*_c$, it follows that $K *_cA =K$. So $A \cap (K *_cA) = A \cap K = A \cap (K *_cB) \ne \emptyset$. (ii) Let $K *_cB \ne K$, then $B \prec _{c}\emptyset$ and by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. It follows from $A \cap (K *_cB) \ne \emptyset$ and that there exists some $\psi \in A$ such that . By $\preceq _{c}$-counter dominance, $A \preceq _{c}\psi$ and . So, and hence $A \preceq _{c}B$ by $\preceq _{c}$-transitivity. Moreover, it follows from $B \prec _{c}\emptyset$ that $\emptyset \not \preceq _{c}B$. So, by $\preceq _{c}$-transitivity, $\emptyset \not \preceq _{c}A$. By $\preceq _{c}$-counter dominance, $A \preceq _{c}\emptyset$. So, $A \prec _{c}\emptyset$ and hence by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. Also, $A \ne \emptyset$ since $A \cap (K *_cB) \ne \emptyset$. So, by Lemma 1, . To sum up (i) and (ii), $*_c$-regularity holds of $*_c$.

• $*_c$-reciprocity Let $A \cap (K *_cB) \ne \emptyset$ and $B \cap (K *_cA) \ne \emptyset$. (i) Let $K *_cA =K$ or $K *_cB = K$, then it follows immediately from $A \cap (K *_cB) \ne \emptyset$ and $B \cap (K *_cA) \ne \emptyset$ that $K *_cA = K *_cB = K$ by $*_c$-confirmation, which has been proved. Suppose $K *_cA \ne K$ and $K *_cB \ne K$, then and by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. Next we show that $K *_cA \subseteq K *_cB$. (The converse direction can be proved in the same way.) Let . As it is immediate from $\preceq _{c}$-counter dominance that , we only need to show that . Since $B \cap (K *_cA) \ne \emptyset$, there exists some $\psi \in B$ such that . By the second item of Observation 7, $\preceq _{c}$ satisfies $\preceq _{c}$-weak coupling, so . Due to $\preceq _{c}$-counter dominance, . So $\varphi \wedge \psi \preceq _{c}A$ by $\preceq _{c}$-transitivity. Furthermore, since $A \cap (K *_cB) \ne \emptyset$, there exists some $\lambda \in A$ such that . By $\preceq _{c}$-counter dominance, . So $\varphi \wedge \psi \preceq _{c}B$ by $\preceq _{c}$-transitivity. Moreover, due to $\psi \in B$, by $\preceq _{c}$-counter dominance. So, by $\preceq _{c}$-transitivity, . To sum up (i) and (ii), $*_c$-reciprocity holds of $*_c$.

From postulates to construction Let $*_c$ be a choice revision operation satisfying $(*_c1)$ through $(*_c5)$. Let $\preceq _{c}$ be a relation derived from $*_c$ in the following way:

• $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$      $A \preceq _{c}B$ iff either (i) $B \cap (K *_cB) = \emptyset$ or (ii) $A \cap (K *_cA) \ne \emptyset$ and there exists $A_0, \ldots , A_n$ such that $K *_cA= K *_cA_0$, $K *_cB= K *_cA_n$ and $A_0 \cap (K *_cA_1) \ne \emptyset , \ldots , A_{n-1} \cap (K *_cA_n) \ne \emptyset$.

Let us first prove the following proposition:

• $(\star )$ Let $*_c$ be a operation satisfying basic postulates on choice revision and $\preceq _{c}$ constructed from $*_c$ in the way of $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, then $K *_cA = K *_cB$ whenever $A \simeq _{c}B$.

Proof of Proposition$(\star )$: Let $A \simeq _{c}B$. There are two cases. (i) $B \cap (K *_cB) = \emptyset$. Then it follows from $B \preceq _{c}A$ and $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \cap (K *_cA) = \emptyset$. So $K *_cA = K *_cB =K$ by $*_c$-relative success. (ii) $B \cap (K *_cB) \ne \emptyset$. Then it follows from $A \preceq _{c}B$ and $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \cap (K *_cA) \ne \emptyset$ and there exist $A_0, \ldots , A_n$ such that $K *_cA= K *_cA_0$, $K *_cB= K *_cA_n$ and $A_0 \cap (K *_cA_1) \ne \emptyset , \ldots , A_{n-1} \cap (K *_cA_n) \ne \emptyset$. Since $A \cap (K *_cA) \ne \emptyset$, it follows from $B \preceq _{c}A$ and $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that there exist $B_0, \ldots , B_m$ such that $K *_cB= K *_cB_0$, $K *_cA= K *_cB_m$ and $B_0 \cap (K *_cB_1) \ne \emptyset , \ldots , B_{m-1} \cap (K *_cB_m) \ne \emptyset$. So, it holds that $A \cap (K *_cA_0) \ne \emptyset , \, A_0 \cap (K *_cA_1) \ne \emptyset , \ldots , A_{n-1} \cap (K *_cB) \ne \emptyset , \, B \cap (K *_cB_0) \ne \emptyset , \, B_0 \cap (K *_cB_1) \ne \emptyset , \ldots , \text{ and } B_{m-1} \cap (K *_cA) \ne \emptyset$. By Observation 5, $*_c$ satisfies $*_c$-strong reciprocity. So it follows that $K *_cA =K *_cB$.

Now we turn back to check the properties of the derived $\preceq _{c}$.

• $\preceq _{c}$-transitivity Let $A \preceq _{c}B$ and $B \preceq _{c}C$. There are two cases. (i) $C \cap (K *_cC) = \emptyset$. Then, it follows immediately from $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \preceq _{c}C$. (ii) $C \cap (K *_cC) \ne \emptyset$. Then it follows from $B \preceq _{c}C$ and $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $B \cap (K *_cB) \ne \emptyset$ and there exist $B_0, \ldots , B_n$ such that $K *_cB= K *_cB_0$, $K *_cC= K *_cB_n$ and $B_0 \cap (K *_cB_1) \ne \emptyset , \ldots , B_{n-1} \cap (K *_cB_n) \ne \emptyset$. Since $B \cap (K *_cB) \ne \emptyset$, it follows from $A \preceq _{c}B$ and $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \cap (K *_cA) \ne \emptyset$ and there exist $A_0, \ldots , A_m$ such that $K *_cA= K *_cA_0$, $K *_cB= K *_cA_m$ and $A_0 \cap (K *_cA_1) \ne \emptyset , \ldots , A_{m-1} \cap (K *_cA_m) \ne \emptyset$. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, $A \preceq _{c}C$.

• $\preceq _{c}$-coupling Let $A \simeq _{c}B$. There are three cases. (i) $A \cap (K *_cA) = \emptyset$. Then, . Otherwise, it follows from that by $*_c$-closure, and hence $A \cap (K *_cA) \ne \emptyset$ by $*_c$-regularity, which contradicts that $A \cap (K *_cA) = \emptyset$. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, . (ii) $B \cap (K *_cB) =\emptyset$. Then, it follows from $B \preceq _{c}A$ and $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \cap (K *_cA) =\emptyset$. So, this case is reducible to (i). (iii) $A \cap (K *_cA) \ne \emptyset$ and $B \cap (K *_cB) \ne \emptyset$. By Proposition $(\star )$, it follows from $A \simeq _{c}B$ that $K *_cA =K *_cB$. So $B \cap (K *_cA) = B \cap (K *_cB) \ne \emptyset$. It follows from $A \cap (K *_cA) \ne \emptyset$ and $B \cap (K *_cA) \ne \emptyset$ that by $*_c$-closure. So, by $*_c$-regularity, and hence by $*_c$-closure. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, .

• $\preceq _{c}$-counter dominance Let A and B satisfy $(\dagger )$: for every $\varphi \in B$ there exists $\psi \in A$ such that $\varphi \Vdash \psi$. Suppose $B \cap (K *_cB) = \emptyset$, then it follows directly from $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \preceq _{c}B$. Suppose $B \cap (K *_cB) \ne \emptyset$, then $A \cap (K *_cB) \ne \emptyset$ by $\dagger$ and $*_c$-closure. Furthermore, $A \cap (K *_cA) \ne \emptyset$ by $*_c$-regularity. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, $A \preceq _{c}B$.

• $\preceq _{c}$-minimalityFrom left to right Let $A \preceq _{c}B$ for all B. Then, $A \preceq _{c}{\scriptstyle \top }$. Since ${\scriptstyle \top }\in K *_c{\scriptstyle \top }$ by $*_c$-closure, it follows from $A \preceq _{c}{\scriptstyle \top }$ and $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $A \cap (K *_cA) \ne \emptyset$ and there exist $A_0, \ldots , A_n$ such that $K *_cA= K *_cA_0$, $K *_c{\scriptstyle \top }= K *_cA_n$ and $A_0 \cap (K *_cA_1) \ne \emptyset , \ldots , A_{n-1} \cap (K *_cA_n) \ne \emptyset$. Moreover, by $*_c$-closure, ${\scriptstyle \top }\in K *_cA_0$. By Observation 5, $*_c$-strong reciprocity holds of $*_c$, so $K *_cA = K *_c{\scriptstyle \top }$. As K is a belief set, by $*_c$-confirmation, $K *_c{\scriptstyle \top }= K$. So, $A \cap K = A \cap (K *_c{\scriptstyle \top }) = A \cap (K *_cA) \ne \emptyset$. From right to left Let $A \cap K \ne \emptyset$. Then $K *_cA = K$ by $*_c$-confirmation. So $A \cap (K *_cA) = A \cap K \ne \emptyset$. Moreover, since K is a belief set, by $*_c$-confirmation, $K *_c{\scriptstyle \top }= K = K *_cA$. By $*_c$-closure, ${\scriptstyle \top }\in K *_cB$ for all B. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, $A \preceq _{c}B$ for all B.

• $\preceq _{c}$-union Suppose $(A \cup B) \cap (K *_c(A \cup B)) = \emptyset$, then $\preceq _{c}$-union follows immediately from $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$. Suppose $(A \cup B) \cap (K *_c(A \cup B)) \ne \emptyset$, then $A \cap (K *_c(A \cup B)) \ne \emptyset$ or $B \cap (K *_c(A \cup B)) \ne \emptyset$. Let $A \cap (K *_c(A \cup B)) \ne \emptyset$, then $A \cap (K *_cA) \ne \emptyset$ by $*_c$-regularity. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, $A \preceq _{c}A\cup B$. Similarly, $B \preceq _{c}A \cup B$ follows from $B \cap (K *_c(A \cup B)) \ne \emptyset$. So, it holds that $A \preceq _{c}A\cup B$ or $B \preceq _{c}A \cup B$.

Finally, we show that $*_c$ can be retrieved from $\preceq _{c}$ through $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. Let $*_c^{\prime }$ be the operation constructed from $\preceq _{c}$ by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. We will show that $*_c= *_c^{\prime }$.

Suppose $A \prec \emptyset$, then $A \cap (K *_cA) \ne \emptyset$ by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ and by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. (i) Let $\varphi \in K *_cA$, then by $*_c$-closure. So by $*_c$-regularity, and hence by $*_c$-closure. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, , i.e. $\varphi \in K *_c^{\prime } A$. (ii) Let $\varphi \in K *_c^{\prime } A$, then . It follows from this and $A \prec _{c}\emptyset$ that by $\preceq$-transitivity. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, . It follows that by $*_c$-closure. Moreover, by Proposition $(\star )$, it follows from that . So, $\varphi \in K *_cA$. To sum up (i) and (ii), $K *_cA = K *_c^{\prime } A$.

Suppose $A \not \prec _{c}\emptyset$, then $K *_c^{\prime } A = K$ by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. Moreover, due to $\preceq _{c}$-counter dominance, it follows from $A \not \prec _{c}\emptyset$ that $A \simeq _{c}\emptyset$. So, by Proposition $(\star )$, $K *_cA = K *_c\emptyset$. Since $\emptyset \cap (K *_c\emptyset ) = \emptyset$, $K *_c\emptyset = K$ by $*_c$-relative success. So, $K *_cA= K *_c\emptyset =K =K *_c^{\prime } A$.

Thus, $K *_cA = K *_c^{\prime } A$ for all A. $\square$

Proof (For Theorem 5)

• From construction to postulates As we have proved Theorem 4, here we only check $*_c$-vacuity, $*_c$-success and $*_c$-consistency.

• $*_c$-vacuity It is immediate from Observation 6.

• $*_c$-success Let $A \ne \emptyset$. By $\preceq _{c}$-determination, $A \prec _{c}\emptyset$. So, by $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$, . Hence, by Lemma 1, $A \cap (K *_cA) \ne \emptyset$.

• $*_c$-consistency Let $A \not \equiv \{{\scriptstyle \perp }\}$. There are two cases. (i) $A = \emptyset$. Then $K *_cA = K$ by $*_c$-vacuity which has been shown holding of $*_c$. That $K *_cA$ is consistent follows immediately from our assumption that K is consistent. (ii) $A \ne \emptyset$. Then $A \prec _{c}\emptyset$ by $\preceq _{c}$-determination. So, . Suppose towards contradiction that $K *_cA \Vdash {\scriptstyle \perp }$. It follows from $K *_cA \Vdash {\scriptstyle \perp }$ and $*_c$-closure that . So, by $\preceq _{c}$ counter dominance and $\preceq _{c}$-transitivity, ${\scriptstyle \perp }\preceq _{c}A$ and hence $B \preceq _{c}A$ for all non-empty B. So, by $\preceq _{c}$-maximality, it follows that $A \equiv \{{\scriptstyle \perp }\}$, which contradicts $A \not \equiv \{{\scriptstyle \perp }\}$. Thus, $*_c$-consistency holds of $*_c$.

2. From postulates to construction Let $\preceq _{c}$ be derived from $*_c$ in the way of $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$. Given Theorem 4, in order to show that $\preceq _{c}$ is a standard multiple believability relation, we only need to check $\preceq _{c}$-maximality and $\preceq _{c}$-determination.

• $\preceq _{c}$-maximality Let $B \ne \emptyset$ and $A \preceq _{c}B$ for all non-empty A. Then, $\{{\scriptstyle \perp }\} \preceq _{c}B$. Moreover, by $*_c$-success, $B \cap (K *_cB) \ne \emptyset$ and ${\scriptstyle \perp }\in K *_c\{{\scriptstyle \perp }\}$. So, by $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$, there exist $A_0, \ldots , A_n$ such that $K *_c\{{\scriptstyle \perp }\}= K *_cA_0$, $K *_cB= K *_cA_n$ and $A_0 \cap (K *_cA_1) \ne \emptyset , \ldots , A_{n-1} \cap (K *_cA_n) \ne \emptyset$. By $*_c$-success and closure, $K *_c\{{\scriptstyle \perp }\} = {\mathcal {L}}$, so $B \cap K *_c\{{\scriptstyle \perp }\} \ne \emptyset$. It follows that $K *_cB = K *_c\{{\scriptstyle \perp }\}$ since $*_c$ satisfies $*_c$-strong reciprocity according to Observation 5. So, $K *_cB \Vdash {\scriptstyle \perp }$. Hence, by $*_c$-consistency, $B \equiv \{{\scriptstyle \perp }\}$.

• $\preceq _{c}$-determination Let $A \ne \emptyset$. It follows immediately from $*_c$-success and $\langle *_c$$\mathrm {to}$$\preceq _{c}\rangle$ that $\emptyset \not \preceq _{c}A$. Moreover, $A \preceq _{c}\emptyset$ by $\preceq _{c}$-counter dominance. So $A \prec _{c}\emptyset$.

Furthermore, by the same argument that was presented in the proof of Theorem 4, it follows that $*_c$ can be retrieved from $\preceq _{c}$ through $\langle \preceq _{c}$$\mathrm {to}$$*_c\rangle$. $\square$