1 Introduction
Belief Change is a multidisciplinary area that studies the dynamics of knowledge. One of the main goals underlying this area is to model how a rational agent updates his/her set of beliefs when confronted with new information. The most influential contribution in the literature to the study of belief change is the AGM model [Reference Alchourrón, Gärdenfors and Makinson1]. In all that follows we assume that the underlying propositional language
$\mathcal {L}$
contains the usual Boolean connectives
$\neg $
(negation),
$\wedge $
(conjunction),
$\vee $
(disjunction),
$\rightarrow $
(implication) and
$\leftrightarrow $
(equivalence), and by abuse of notation we shall represent the set of all sentences of that language also by
$\mathcal {L}$
. Additionally we shall make use of a consequence operation
$Cn$
that takes sets of sentences to sets of sentences and that satisfies the standard Tarskian properties [Reference Tarski16], namely: (i)
$A\subseteq Cn(A)$
(inclusion); (ii) If
$A\subseteq B$
, then
$Cn(A)\subseteq Cn(B)$
(monotony) and (iii)
$Cn(A)=Cn(Cn(A))$
(iteration). Furthermore we will assume that
$Cn$
satisfies the following three properties: (iv) If
$\alpha $
can be derived from A by classical truth-functional logic, then
$\alpha \in Cn(A)$
(supraclassicality); (v)
$\beta \in Cn(A\cup \{\alpha \})$
if and only if
$\alpha \rightarrow \beta \in Cn(A)$
(deduction) and (vi) If
$\alpha \in Cn(A)$
, then
$\alpha \in Cn(A')$
for some finite subset
$A'$
of A (compactness). We will use
$\mathbf {K}$
to represent a set of sentences that is closed under logical consequence (i.e.,
$\mathbf {K} = Cn(\mathbf {K})$
)—such a set is called a belief set. A belief change operator on a set A is a function
$\circ : \mathcal {L} \to \mathcal {P}(A)$
. In what follows, given a set A, a belief change operator,
$\circ $
, on A and a sentence
$\alpha $
, we shall denote the image of
$\alpha $
by
$\circ $
, i.e.,
$\circ (\alpha )$
, by
$A \circ \alpha $
. In the AGM framework beliefs are represented by sentences, the belief state of an agent is modelled by a belief set—i.e., a logically closed set of (belief-representing) sentences and epistemic inputs are represented by single sentences. The AGM model considers three kinds of belief change operators, namely expansion, contraction and revision. An expansion occurs when new information is added to the set of the beliefs of an agent. The expansion of a belief set
$\mathbf {K}$
by a sentence
$\alpha $
is the logical closure of
$\mathbf {K}\cup \{\alpha \}$
. A contraction occurs when information is removed from the set of beliefs of an agent. A revision occurs when new information is added to the set of the beliefs of an agent while retaining consistency if the new information is itself consistent. From the three above-mentioned operations, expansion is the only one that can be univocally defined. Contractions and revisions are characterized by a set of postulates and can be defined in terms of each other by means of the Harper and the Levi identities.
In [Reference Alchourrón, Gärdenfors and Makinson1] the following properties were proposed as being the characteristic properties of a contraction, where
$\mathbf {K}$
is a belief set:
-
(
$\mathbf {K} - 1$
)
$\mathbf {K} \div \alpha = Cn(\mathbf {K} \div \alpha )$
. (Closure) -
(
$\mathbf {K} - 2$
)
$\mathbf {K} \div \alpha \subseteq \mathbf {K}$
. (Inclusion) -
(
$\mathbf {K} - 3$
) If
$\alpha \not \in \mathbf {K}$
, then
$\mathbf {K} \div \alpha = \mathbf {K}$
. (Vacuity) -
(
$\mathbf {K} - 4$
) If
$\alpha \not \in Cn(\emptyset )$
, then
$\alpha \not \in \mathbf {K} \div \alpha $
. (Success) -
(
$\mathbf {K} - 5$
) If
$\alpha \leftrightarrow \beta \in Cn(\emptyset )$
, then
$\mathbf {K} \div \alpha = \mathbf {K} \div \beta $
. (Extensionality) -
(
$\mathbf {K} - 6$
)
$\mathbf {K} \subseteq Cn((\mathbf {K}\div \alpha ) \cup \{\alpha \})$
. (Recovery) -
(
$\mathbf {K} - 7$
)
$(\mathbf {K} \div \alpha ) \cap (\mathbf {K} \div \beta ) \subseteq \mathbf {K} \div (\alpha \wedge \beta )$
. (Conjunctive overlap) -
(
$\mathbf {K} - 8$
)
$\mathbf {K} \div (\alpha \wedge \beta ) \subseteq \mathbf {K} \div \alpha $
whenever
$\alpha \not \in \mathbf {K} \div (\alpha \wedge \beta )$
. (Conjunctive inclusion)
These conditions are usually designated by AGM postulates for contraction. Postulates (
$\mathbf {K} - 1$
)–(
$\mathbf {K} - 6$
) are called basic AGM postulates for contraction. Postulates (
$\mathbf {K} - 7$
) and (
$\mathbf {K} - 8$
) are designated by supplementary AGM postulates for contraction.
There are in the belief change literature several constructive methods for defining operators which satisfy all or at least some of the AGM postulates for contraction. Some of those models are the (transitively relational) partial meet contractions [Reference Alchourrón, Gärdenfors and Makinson1] and safe contraction [Reference Alchourrón and Makinson3, Reference Rott, Hansson and Hansson15], which we will recall in Section 2. Although the AGM model has quickly acquired the status of standard model of theory change, several researchers (for an overview see [Reference Fermé and Hansson6]) have proposed some extensions and variants to that framework. One of such variants is the use of belief bases, instead of belief sets, to model the belief state of an agent. The main motivation underlying the numerous models of belief base change that have been presented in the literature is the fact that the usage of belief sets to model the belief states may be undesirable for several reasons. Firstly, belief sets are very large entities (eventually even infinite), and its use is not adequate for computational implementations. The logical closure of belief sets raises other issues not related to computational implementations. Rott pointed out in [Reference Rott14] that the AGM theory is unrealistic in its assumption that epistemic agents are “ideally competent regarding matters of logic. They should accept all the consequences of the beliefs they hold (that is, their set of beliefs should be logically closed), and they should rigorously see to it that their beliefs are consistent.” Furthermore, belief sets make no distinction between different inconsistent belief states. They also make no distinction between basic beliefs and those that are inferred from them.
Several of the existing models of contraction for beliefs sets have been adapted to the case when belief states are represented by belief bases. For example, the partial meet contractions for belief bases were presented in [Reference Hansson8–Reference Hansson10] and the kernel contractions—which can be seen as a generalization of safe contractions—were introduced in [Reference Hansson11].
Given a set of sentences A the outcome of a partial meet contraction (PMC) of A by a sentence
$\alpha $
is essentially the result of the intersection of some of the maximal subsets of A that do not imply
$\alpha $
, usually called the remainders of A by
$\alpha $
. More formally, denoting by
$A \perp \alpha $
the set of remainders of A by
$\alpha $
—which is called the remainder set of A by
$\alpha $
—an operator
$\div $
on A is a partial meet contraction operator on A if, for any sentence
$\alpha $
,
$A \div \alpha = \cap \gamma (A \perp \alpha )$
, where
$\gamma $
is a function, which is called a selection function, which is such that
$\gamma (A \perp \alpha )$
is a set of some of the remainders of A by
$\alpha $
, whenever
$A \perp \alpha \neq \emptyset $
.
On the other hand, the outcome of a kernel contraction (KC) of a set sentences A by a sentence
$\alpha $
is a set that can be obtained from A by removing from it a set such that (i) it is formed by some of the sentences which are included in some of the minimal subsets of A that imply
$\alpha $
, usually called the
$\alpha $
-kernels of A, and (ii) it contains at least one element of each one of the (non-empty)
$\alpha $
-kernels of A. More formally, denoting by
$A\!\!\perp \!\!\!\perp \!\!\alpha $
the set of
$\alpha $
-kernels of A—which is called the kernel set of A by
$\alpha $
—an operator
$\div $
on A is a kernel contraction operator on A if, for any sentence
$\alpha $
,
$A \div \alpha = A \setminus \sigma (A\!\!\perp \!\!\!\perp \!\!\alpha )$
, where
$\sigma $
is a function, which is called an incision function, which is such that
$\sigma (A\!\!\perp \!\!\!\perp \!\!\alpha )$
is a subset of A which satisfies conditions (i) and (ii) above.
At this point we notice that the central constructs in the definitions of partial meet contractions and kernel contractions are the selection functions and the incision functions. These functions are such that:
-
• A selection function
$\gamma $
, associated to a partial meet contraction on a set A, is such that
$\gamma : \{A \perp \alpha : \alpha \in \mathcal {L}\} \to \mathcal {P}(\mathcal {P}(A))$
, i.e., its domain is the set of all remainder sets of A. -
• An incision function
$\sigma $
, associated to a kernel contraction on a set A, is such that
$\sigma : \{A\!\!\perp \!\!\!\perp \!\!\alpha : \alpha \in \mathcal {L}\} \to \mathcal {P}(A)$
, i.e., its domain is the set of all kernel sets of A.
In this paper we propose and axiomatically characterize two new classes of contraction operators, namely the generalized partial meet contractions (GPMC) and the generalized kernel contractions (GKC) which are broader than the classes of PMC and KC, respectively. The definitions of GPMC and GKC are similar to the definitions of partial meet contractions and kernel contractions, respectively, except for making use of sentence based selection functions instead of standard selection functions and sentence based incision functions instead of standard incision functions, respectively. The main difference between the sentence based selection and incision functions and the standard selection and incision functions is the fact that the domain of the former is
$\mathcal {L}$
(instead of
$\{A \perp \alpha : \alpha \in \mathcal {L}\}$
and
$\{A\!\!\perp \!\!\!\perp \!\!\alpha : \alpha \in \mathcal {L}\}$
, respectively).
The rest of the paper is organized as follows: In Section 2 we introduce the notations and recall the main background concepts that will be needed throughout this article and, in particular, we formally introduce some of the concepts mentioned in the text above. The readers who are well familiarized with the AGM framework and with the Hansson’s model of Kernel contraction may skip this section. In Section 3 we present the definition of sentence based selection functions, propose some properties that may be required from those functions and study the interrelation among these new functions and the standard selection functions. Afterwards, we present the definition of GPMC, obtain an axiomatic characterization for those operators, and identify, in the context of belief bases, two relevant strict subclasses of that class of functions (the smallest of which coincides with the class of partial meet contractions). At the end of Section 3, we present an analysis of the interrelations among some classes of GPMCs on belief sets and the classes of AGM contractions. In Section 4 we introduce the sentence based incision functions and the generalized kernel contractions and present a study of these functions which is the kernel contraction counterpart of the study carried out in the previous section regarding partial meet contraction. In Section 5 we present the interrelations in the sense of inclusion among all the newly defined classes of contractions on belief bases. Finally, in Section 6 we summarize and discuss the main contributions of the paper and their relevance. In the Appendix we provide proofs for all the original results presented.
2 Background
In order to make this paper self-contained, in this section we will essentially recall the main definitions and results from [Reference Alchourrón, Gärdenfors and Makinson1, Reference Alchourrón and Makinson3, Reference Hansson11]. The readers who are knowledgeable of these works may skip this section.
2.1 Basic notations and conventions
In this subsection we briefly introduce the notations and conventions that we will use throughout this paper (besides the ones already mentioned in the previous section). We will sometimes use
$Cn(\alpha )$
for
$Cn(\{\alpha \})$
,
$A \vdash \alpha $
for
$\alpha \in Cn(A)$
,
$\vdash \alpha $
for
$\alpha \in Cn(\emptyset )$
,
$A \not \vdash \alpha $
for
$\alpha \not \in Cn(A)$
, and
$\not \vdash \alpha $
for
$\alpha \not \in Cn(\emptyset )$
. The letters
$\alpha , \beta , \ldots $
(except for
$\gamma $
and
$\sigma $
) will be used to denote sentences of
$\mathcal {L}$
. Lowercase Latin letters such as
$p, q,\ldots $
will be used to denote atomic sentences of
$\mathcal {L}$
.
$A, B, \ldots $
shall denote sets of sentences of
$\mathcal {L}$
.
$\mathbf {K}$
is reserved to represent a belief set.
2.2 Belief base contraction
In this subsection we recall some postulates for base contraction and also several constructive models of contraction functions on belief bases.
2.2.1 Postulates for base contraction
The following are some well known postulates for belief base contraction:Footnote 1
Success: If
$\not \vdash \alpha $
, then
$A\div \alpha \not \vdash \alpha $
.
Inclusion:
$ A \div \alpha \subseteq A$
.
Failure: If
$\vdash \alpha $
then
$A \div \alpha = A$
.
Vacuity: If
$A\not \vdash \alpha $
, then
$A\subseteq A\div \alpha $
.
Relative Closure:
$A \cap Cn(A \div \alpha )\subseteq A \div \alpha .$
Relevance: If
$\beta \in A$
and
$\beta \not \in A \div \alpha $
then there is some set
$A'$
such that
$A \div \alpha \subseteq A' \subseteq {A}$
and
$\alpha \not \in Cn(A')$
but
$\alpha \in Cn( {A'} \cup \{\beta \}).$
Core-retainment: If
$\beta \in A$
and
$\beta \notin A \div \alpha $
then there is some set
$A'$
such that
$A' \subseteq A$
and
$\alpha \notin Cn(A')$
but
$\alpha \in Cn( A' \cup \{\beta \}).$
Extensionality: If
$\vdash \alpha \leftrightarrow \beta $
, then
$A\div \alpha =A\div \beta $
.
Uniformity: If it holds for all subsets
$A'$
of A that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
, then
$A\div \alpha = A\div \beta $
.
The following observation presents some relations between the belief base postulates for contraction mentioned above.
Observation 1 [Reference Hansson12]
Let A be a belief base and
$\div $
an operator on A. Then:
-
(a) If
$\div $
satisfies relevance, then it satisfies relative closure and core-retainment. -
(b) If
$\div $
satisfies inclusion and core-retainment, then it satisfies failure and vacuity. -
(c) If
$\div $
satisfies uniformity, then it satisfies extensionality.
In the rest of this section we recall some explicit definitions of contraction functions and their axiomatic characterizations.
2.2.2 Partial meet contraction
The first kinds of contraction operators that we will present are known as partial meet contractions and were originally presented in [Reference Alchourrón, Gärdenfors and Makinson1]. We start by recalling the concept of remainder set, that is the set of maximal subsets (of a given set) that fail to imply a given sentence. Formally:
Definition 1 [Reference Alchourrón, Makinson and Hilpinen2]
Let A be a set of sentences and
$\alpha $
a sentence. The set
$ {A}{ \perp } { \alpha }$
(A remainder
$\alpha $
) is the set of sets such that
$B \in {A}{ \perp } { \alpha }$
if and only if:
-
1.
$B \subseteq A$
. -
2.
$ B \not \vdash \alpha $
. -
3. If
$B \subset B' \subseteq A$
, then
$B' \vdash \alpha $
.
$ {A}{ \perp } { \alpha }$
is called remainder set of A by
$\alpha $
and its elements are called remainders (of A by
$\alpha $
).
It follows from compactness and Zorn’s lemma (cf. [Reference Alchourrón, Makinson and Hilpinen2, Proof of Observation 2.2]) that, given a set of sentences A and a sentence
$\alpha $
, every subset D of A that does not imply
$\alpha $
is contained in some remainder of A by
$\alpha $
. This property is known as upper bound property:
$$ \begin{align*} \text{If } D\subseteq A \text{ and } D\not\vdash\alpha, \text{ then there is some } D' \text{ such that } D\subseteq D' \in A\perp \alpha. \end{align*} $$
The partial meet contractions are obtained by intersecting some elements of the (associated) remainder set. The choice of those elements is performed by a selection function.
Definition 2. Let A be a set of sentences. A selection function for A is a function
$\gamma :\{A\perp \epsilon : \epsilon \in \mathcal {L}\}\longrightarrow \mathcal {P}(\mathcal {P}(A))$
such that for all sentences
$\alpha $
:
-
1. If
$A\perp \alpha \not =\emptyset $
, then
$\gamma (A\perp \alpha )$
is a non-empty subset of
$A\perp \alpha $
. -
2. If
$A\perp \alpha = \emptyset $
, then
$\gamma (A\perp \alpha )=\{A\}$
.
Definition 3 [Reference Alchourrón, Gärdenfors and Makinson1, Reference Hansson8]
The partial meet contraction operator on A based on a selection function
$\gamma $
is the operator
$\div _{\gamma }$
such that for all sentences
$\alpha $
,
$$ \begin{align*} { A} \div_{\gamma} \alpha = \cap \gamma( {A}{ \perp} { \alpha}). \end{align*} $$
An operator
$\div $
for a set A is a partial meet contraction if and only if there is a selection function
$\gamma $
for A such that
$A \div \alpha = A \div _{\gamma } \alpha $
for all sentences
$\alpha $
.
In the following observation we recall a characterization, in terms of postulates, of partial meet contraction operators.
Observation 2 [Reference Hansson8]
Let A be a belief base. An operator
$\div $
on
${A}$
is a partial meet contraction for A if and only if
$\div $
satisfies success, inclusion, uniformity and relevance.
2.2.3 Kernel contraction
As we mentioned previously the partial meet contraction operators of a given set by a sentence
$\alpha $
are based on a selection among the maximal subsets of that set that fail to imply
$\alpha $
. Another different proposal consists of constructing a contraction operator based on a selection of elements of A that are fundamental in some deduction of
$\alpha $
and then discarding them when contracting A by
$\alpha $
. Following this approach, Hansson, in [Reference Hansson11], introduced the kernel contraction operators.
Definition 4 [Reference Hansson11]
Let A be a set of sentences and
$\alpha $
be a sentence. Then
$A\!\!\perp \!\!\!\perp \!\!\alpha $
is the set such that
$B \in A\!\!\perp \!\!\!\perp \!\!\alpha $
if and only if:
-
1.
$B \subseteq A$
. -
2.
$B \vdash \alpha $
. -
3. If
$B'\subset B$
then
$B' \not \vdash \alpha $
.
$A\!\!\perp \!\!\!\perp \!\!\alpha $
is called the kernel set of A with respect to
$\alpha $
and its elements are the
$\alpha $
-kernels of A.
When contracting a belief
$\alpha $
from a set A we must give up sentences of each
$\alpha $
-kernel, otherwise
$\alpha $
would continue being implied by the outcome of the contraction. The so-called incision functions select the beliefs to be discarded.
Definition 5 [Reference Hansson11]
Let A be a set of sentences. Let
$A\!\!\perp \!\!\!\perp \!\!\alpha $
be the kernel set of A with respect to
$\alpha $
. An incision function for A is a function
$\sigma :\{A\!\!\perp \!\!\!\perp \!\!\epsilon : \epsilon \in \mathcal {L}\}\longrightarrow \mathcal {P}(A)$
such that for all sentences
$\alpha $
:
-
1.
$\sigma (A\!\!\perp \!\!\!\perp \!\!\alpha ) \subseteq \bigcup (A\!\!\perp \!\!\!\perp \!\!\alpha )$
. -
2. If
$\emptyset \not = B \in A\!\!\perp \!\!\!\perp \!\!\alpha $
, then
$B \cap \sigma (A\!\!\perp \!\!\!\perp \!\!\alpha ) \not = \emptyset $
.
Definition 6 [Reference Hansson11]
Let A be a set of sentences and
$\sigma $
be an incision function for A. The kernel contraction on A based on
$\sigma $
is the operator
$\div _{\sigma }$
such that for all sentences
$\alpha $
,
$$ \begin{align*} A\div_{\sigma}\alpha = A \setminus \sigma(A\!\!\perp\!\!\!\perp\!\!\alpha). \end{align*} $$
An operator
$\div $
for a set A is a kernel contraction if and only if there is an incision function
$\sigma $
for A such that
$A \div \alpha = A\div _{\sigma } \alpha $
for all sentences
$\alpha $
.
We now recall from [Reference Hansson11] an axiomatic characterization for kernel contractions defined on belief bases.
Observation 3 [Reference Hansson11]
Let A be a belief base. An operator
$\div $
on A is a kernel contraction if and only if it satisfies success, inclusion, uniformity and core-retainment.
Sometimes, when contracting a set by means of a kernel contraction, for some sentence
$\beta $
such that
$\beta \in A$
and
$\beta \in Cn(A\div \alpha )$
it may be the case that
$\beta \not \in A\div \alpha $
(see the example presented on [Reference Hansson12, p. 90]), i.e., some kernel contradictions do not satisfy the relative closure postulate. This undesirable situation can be avoided by considering only incision functions that satisfy the condition expressed in the following definition.
Definition 7 [Reference Hansson11]
An incision function
$\sigma $
for a set A is smooth if and only if it holds for all subsets
$A'$
of A that if
$A' \vdash \beta $
and
$\beta \in \sigma {(A\!\!\perp \!\!\!\perp \!\!\alpha )}$
then
$A' \cap \sigma {(A\!\!\perp \!\!\!\perp \!\!\alpha )} \neq \emptyset $
.
A kernel contraction is smooth if and only if it is based on a smooth incision function.
The following observation presents an axiomatic characterization for smooth kernel contractions.
Observation 4 [Reference Hansson11]
Let A be a belief base. An operator
$\div $
on A is a smooth kernel contraction if and only if it satisfies success, inclusion, uniformity, core-retainment and relative closure.
2.3 AGM contraction operators on belief sets
In this subsection we recall the definition and the axiomatic characterizations of some contraction operators on belief sets.
2.3.1 Partial meet contractions on belief sets
The definition of partial meet contraction operators was already presented in Section 2.2.2. In the following observation we recall from [Reference Alchourrón, Gärdenfors and Makinson1] a representation theorem for partial meet contraction operators on belief sets.
Observation 5 [Reference Alchourrón, Gärdenfors and Makinson1]
Let
$\mathbf {K}$
be a belief set and
$\div $
be a contraction operator on
$\mathbf {K}$
. Then
$\div $
is a partial meet contraction on
$\mathbf {K}$
if and only if it satisfies the basic AGM postulates for contraction.
A selection function is expected to pick up the best elements (in some sense) of the remainder set. If we consider a relation
$\sqsubseteq $
on subsets of A such that
$A_1\sqsubseteq A_2$
holds if and only if
$A_2$
is at least as much worth retaining as
$A_1$
, then we can define a selection function, based on
$\sqsubseteq $
, that chooses the “best” elements of
$A\perp \alpha $
, according to
$\sqsubseteq $
. A selection function that is based on a relation in this way is called relational:
Definition 8 [Reference Alchourrón, Gärdenfors and Makinson1]
A selection function
$\gamma $
for a set A is relational if and only if there is a relation
$\sqsubseteq $
over
$\bigcup \{A\perp \alpha :\alpha \in \mathcal {L}\}$
such that for all sentences
$\alpha $
, if
$A\perp \alpha $
is non-empty, then
$$ \begin{align*} \gamma(A\perp \alpha)=\{B\in A\perp \alpha: C \sqsubseteq B \textrm{ for all } C\in A\perp \alpha\}. \end{align*} $$
$\gamma $
is transitively relational if and only if this holds for some transitive relation
$\sqsubseteq $
.
A partial meet contraction function is relational (respectively transitively relational) if and only if it is determined by some relational (respectively transitively relational) selection function.
The following observation provides an axiomatic characterization for the class of transitively relational partial meet contraction operators.
Observation 6 [Reference Alchourrón, Gärdenfors and Makinson1]
Let
$\mathbf {K}$
be a belief set and
$\div $
be an operator on
$\mathbf {K}$
. Then
$\div $
is a transitively relational partial meet contraction if and only if it satisfies both the basic and the supplementary AGM postulates for contraction.
2.3.2 Smooth kernel contractions and safe contractions on belief sets
The definitions of kernel and smooth kernel contractions were already presented in Section 2.2.3. In the following observation we recall from [Reference Hansson11] a representation theorem for smooth kernel contraction operators on belief sets.
Observation 7 [Reference Hansson11]
Let
$\mathbf {K}$
be a belief set. Then
$\div $
is a smooth kernel contraction on
$\mathbf {K}$
if and only if it satisfies the basic AGM postulates for contraction.
In order to be able to define safe contraction in terms of kernel contractions we need to recall some additional concepts, namely the ones presented in the following five definitions:
Definition 9 [Reference Hansson12]
Let A be a set of sentences. A kernel selection function for A is a function s such that for all
$X\in \ A\!\!\perp \!\!\!\perp \!\!\alpha $
, for some sentence
$\alpha $
:
-
(a)
$s(X)\subseteq X$
; -
(b) If
$X\not = \emptyset $
, then
$s(X)\not =\emptyset $
.
Definition 10 [Reference Hansson12]
Let s be a kernel selection function for a set A. Then an incision function
$\sigma $
(for A) is the cumulation of s if and only if for all sentences
$\alpha $
,
$$ \begin{align*} \sigma(A\!\!\perp\!\!\!\perp\!\!\alpha)=\bigcup\{s(X):X\in A\!\!\perp\!\!\!\perp\!\!\alpha\}. \end{align*} $$
A kernel selection function s can be seen as a function that selects the sentences of each kernel that should be removed when performing a contraction. It seems natural that these sentences should be the least valuable elements of each kernel. Thus it seems natural that s should be based on a binary relation that orders sentences according to its epistemic value.
Definition 11 [Reference Hansson12]
A kernel selection function s for a set A is based on a relation
$\prec $
if and only if for all
$X\in A\!\!\perp \!\!\!\perp \!\!\alpha $
,
$$ \begin{align*} \beta\in s(X) \textrm{ if and only if } \beta \in X \textrm{ and there is no } \delta\in X \textrm{ such that } \delta \prec \beta. \end{align*} $$
An incision function is based on a relation
$\prec $
if and only if it is the cumulation of some kernel selection function that is based on
$\prec $
.
Definition 12 [Reference Hansson12]
Let A be a set of sentences and
$\prec $
be a relation on A. Then
$\prec $
satisfies acyclicity if and only if for all positive integers n, if
$\{\alpha _1,\dots ,\alpha _n\}\subseteq A$
, then it is not the case that
$\alpha _1\prec \alpha _2\prec \cdots \prec \alpha _n\prec \alpha _1$
.
We will consider that
$\prec $
treats logical equivalents sentences alike. An acyclic relation over a set A that satisfies this condition is called a hierarchy over A. Formally:
Definition 13 [Reference Alchourrón and Makinson3, Reference Hansson12]
A relation
$\prec $
over a set A is a hierarchy over A if and only if:
-
(a) it is acyclic;
-
(b) if
$\vdash \alpha \leftrightarrow \alpha '$
and
$\vdash \beta \leftrightarrow \beta '$
, then
$\alpha \prec \beta $
holds if and only if
$\alpha ' \prec \beta '$
holds.
In the following definition we present the notion of safe contraction.
Definition 14 [Reference Alchourrón and Makinson3]
Let
$\prec $
be a hierarchy over a set of sentences A. Let
$\sigma $
be the incision function that is based on
$\prec $
and
$\div _\sigma $
the kernel contraction based on
$\sigma $
. The operation of safe contraction
$\div _\prec $
based on
$\prec $
is defined as follows:
$$ \begin{align*} A\div_\prec \alpha=A\cap Cn(A\div_\sigma \alpha). \end{align*} $$
Definition 15 [Reference Alchourrón and Makinson4]
A relation
$\prec $
over a set A is regular if and only if it satisfies the following two properties:
Continuing-up: If
$\alpha \prec \beta $
and
$\beta \vdash \delta $
, then
$\alpha \prec \delta $
.
Continuing-down: If
$\alpha \vdash \beta $
and
$\beta \prec \delta $
, then
$\alpha \prec \delta $
.
As stated in [Reference Alchourrón and Makinson3], for a safe contraction based on a hierarchy
$\prec $
to satisfy
$(\div 8)$
it is enough that
$\prec $
satisfies either continuing-up or continuing-down as well as the following property:
Virtual connectivity: If
$\alpha \prec \beta $
, then either
$\alpha \prec \delta $
or
$\delta \prec \beta $
.
In the following observation we present an axiomatic characterization for safe contractions operator functions on a belief set based on a regular and virtual connected hierarchy.
Observation 8 [Reference Rott and Gärdenfors13].Footnote 2
Let
$\mathbf {K}$
be a belief set and
$\div $
be a contraction function on
$\mathbf {K}$
. Then
$\div $
is a safe contraction, based on a regular and virtually connected hierarchy, if and only if it satisfies both the basic and the supplementary AGM postulates for contraction.
3 Generalized partial meet contractions
In this section we present the definition and axiomatic characterization of a new type of contraction operators called generalized partial meet contractions.
3.1 Sentence based selection functions
In this subsection we introduce the sentence based selection functions, whose definition differs from the definition of the standard selection functions in the following aspect: The domain of the sentence based selection functions is the set
$\mathcal {L}$
of all sentences rather than
$\{A \perp \alpha : \alpha \in \mathcal {L}\}$
. We will also present some properties that may be naturally imposed to these functions and study the interrelation among these new sentence based functions and the standard selection functions.
Definition 16. Let A be a set of sentences. A sentence based function for A is a function f from
$\mathcal {L}$
to either
$\mathcal {P}(\mathcal {P}(A))$
or
$\mathcal {P}(A)$
.
A sentence based function f is extensional if and only if, for all sentences
$\alpha $
and
$\beta $
, if
$\vdash \alpha \leftrightarrow \beta $
, then
$f(\alpha )=f(\beta )$
.
A sentence based function f is uniform if and only if, for all sentences
$\alpha $
and
$\beta $
, if for all subsets
$A'$
of A it holds that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
, then
$f(\alpha )=f(\beta )$
.
The following observation states that any uniform sentence based function is extensional.
Observation 9. Let A be a set of sentences and f be a sentence based function for A. If f is uniform, then it is extensional.
Now we present the definition of sentence based selection functions.
Definition 17. Let A be a set of sentences. A sentence based selection function for A is a function
$\gamma :\mathcal {L}\longrightarrow \mathcal {P}(\mathcal {P}(A))$
such that for all sentences
$\alpha $
:Footnote
3
-
1. If
$A\perp \alpha \not =\emptyset $
, then
$\gamma (\alpha )$
is a non-empty subset of
$A\perp \alpha $
. -
2. If
$A\perp \alpha = \emptyset $
, then
$\gamma ( \alpha )=\{A\}$
.
The following observation states that, in the belief set context, any extensional sentence based selection function is uniform.
Observation 10. Let A be a belief set. If
$\gamma $
is an extensional sentence based selection function for A, then
$\gamma $
is uniform.
From the last observation, having in mind Observation 9, we can conclude that, in the context of belief sets,
$\gamma $
is an extensional sentence based selection function if and only if it is a uniform sentence based selection function.
We now present the definition of relational sentence based selection function.
Definition 18. A sentence based selection function
$\gamma $
for a set A is relational if and only if there is a relation
$\sqsubseteq $
over
$\bigcup \{A\perp \alpha :\alpha \in \mathcal {L}\}$
such that for all sentences
$\alpha $
, if
$A\perp \alpha $
is non-empty, then
$$ \begin{align*} \gamma(\alpha)=\{B\in A\perp \alpha: C \sqsubseteq B \textrm{ for all } C\in A\perp \alpha\}. \end{align*} $$
$\gamma $
is transitively relational if and only if this holds for some transitive relation
$\sqsubseteq $
.
The following theorems show how sentence based selection functions can be defined from standard selection functions and vice versa.
Theorem 1. Let A be a set of sentences and
$\gamma :\{A\perp \epsilon : \epsilon \in \mathcal {L}\}\longrightarrow \mathcal {P}(\mathcal {P}(A))$
be a selection function for A. Let
$\gamma '$
be such that
$\gamma '(\alpha )=\gamma (A\perp \alpha )$
(for all sentences
$\alpha $
).Footnote
4
Then it holds that:
-
1.
$\gamma '$
is a uniform sentence based selection function for A. -
2. If
$\gamma $
is a transitively relational selection function for A, then
$\gamma '$
is a uniform transitively relational sentence based selection function for A.
Theorem 2. Let A be a set of sentences and
$\gamma :\mathcal {L}\longrightarrow \mathcal {P}(\mathcal {P}(A))$
be a uniform sentence based selection function for A. Let
$\gamma '$
be such that
$\gamma '(A\perp \alpha )=\gamma (\alpha )$
(for all sentences
$\alpha $
).Footnote
5
Then it holds that:
-
1.
$\gamma '$
is a selection function for A. -
2. If
$\gamma $
is a uniform transitively relational selection function for A, then
$\gamma '$
is a transitively relational selection function for A.
3.2 Generalized partial meet contractions on belief bases
The definition of these operators is similar to the one presented for partial meet contractions, but instead of being defined by means of selection functions, generalized partial meet contraction operators, are defined by means of sentence based selection functions.
Definition 19. Let A be a set of sentences and
$\gamma :\mathcal {L}\longrightarrow \mathcal {P}(\mathcal {P}(A))$
be a sentence based selection function. The generalized partial meet contraction (GPMC) operator on A based on
$\gamma $
is the operator
$\div _{\gamma }$
such that for all sentences
$\alpha $
,
$$ \begin{align*} { A} \div_{\gamma} \alpha = \cap \gamma({\alpha}). \end{align*} $$
An operator
$\div $
for a set A is a GPMC operator if and only if there is a sentence based selection function
$\gamma $
for A such that
$A \div \alpha = A \div _{\gamma } \alpha $
for all sentences
$\alpha $
.
In the following theorem, we present an axiomatic characterization for GPMC operators.
Theorem 3. Let A be a belief base. An operator
$\div $
on
${A}$
is a GPMC for A if and only if
$\div $
satisfies success, inclusion and relevance.
A GPMC operator, in general, does not satisfy the irrelevance of syntax criteria according to which the outcome of a change should not depend on the syntax/representation of either the previous beliefs or the new information that triggers that change. For example, let
$A=\{r, r\rightarrow q\}$
. It holds that
$A\perp (\neg p\vee q)=A\perp (p \rightarrow q)=\{\{r\},\{r\rightarrow q\}\}$
. Now consider a sentence based selection function
$\gamma $
such that
$\gamma (p \rightarrow q)=\{\{r\}\}$
and
$\gamma (\neg p \vee q)=\{\{r\rightarrow q\}\}$
, and let
$\div $
be the GPMC based on
$\gamma $
. It holds that
$A\div (p \rightarrow q)=\{r\}$
and
$A\div (\neg p \vee q)=\{r\rightarrow q\}$
. Hence, although
$\vdash (\neg p\vee q)\leftrightarrow (p \rightarrow q)$
,
$A\div (p \rightarrow q) \neq A\div (\neg p \vee q)$
. In order to obtain an operation that satisfies that criteria, we will impose constrains on the sentence based selection function on which the operator is based.
Definition 20. An extensional GPMC operator on A is a GPMC operator on A which is based on an extensional sentence based selection function. A uniform GPMC operator on A is a GPMC operator on A which is based on a uniform sentence based selection function.
We now present axiomatic characterizations for the classes of operators mentioned in the above definition.
Theorem 4. Let A be a belief base and
$\div $
an operator on A. The following pair of conditions are equivalent.
-
(a)
$\div $
is an extensional GPMC operator. -
(b)
$\div $
satisfies success, inclusion, relevance and extensionality.
Theorem 5. Let A be a belief base and
$\div $
an operator on A. The following conditions are equivalent.
-
(a)
$\div $
is a uniform GPMC operator. -
(b)
$\div $
satisfies success, inclusion, relevance and uniformity. -
(c)
$\div $
is a partial meet contraction.
We finish this section by presenting an example that illustrates that, in general, the classes of extensional GPMC and of uniform GPMC do not coincide.
Example 1. Let
$A=\{r,r\rightarrow (p\wedge q)\}$
. For all subset B of A it holds that
$B\vdash p$
if and only if
$B\vdash q$
. On the other hand,
$A\perp p=A\perp q=\{\{r\},\{r\rightarrow (p\wedge q)\}\}$
. Let
$\gamma $
be an extensional sentence based selection function such that
$\gamma (p)=\{\{r\}\}$
and
$\gamma (q)=\{\{r\rightarrow (p\wedge q)\}\}$
. Thus the operator
$\div $
on A such that
$A\div \alpha =\bigcap \gamma (\alpha )$
(for all
$\alpha $
) is an extensional GPMC. However, it holds that
$A\div p=\{r\}$
and
$A\div q=\{r\rightarrow (p\wedge q)\}$
. Hence
$\div $
does not satisfy uniformity. Therefore,
$\div $
is an extensional GPMC but not a uniform GPMC.
3.3 Generalized partial meet contraction operators on belief sets
In this subsection we start by showing that, when considering the specific case of contractions on belief sets, the newly proposed classes of extensional GPMC and uniform GPMC are identical and, furthermore, they are also identical to the class of standard partial meet contractions.
Theorem 6. Let
$\mathbf {K}$
be a belief set and
$\div $
be a contraction operator on
$\mathbf {K}$
. Then the following conditions are equivalent:
-
(a)
$\div $
is an extensional GPMC. -
(b)
$\div $
is a uniform GPMC. -
(c)
$\div $
is a partial meet contraction. -
(d)
$\div $
satisfies the basic AGM contraction postulates.
Definition 21. A GPMC is relational respectively transitively relational if and only if it is determined by some relational respectively transitively relational sentence based selection function.
The following theorem asserts that the newly proposed classes of extensional and of uniform transitively relational GPMC (on belief sets) are identical and, furthermore, they coincide with the class of standard transitively relational partial meet contractions (and so they are axiomatically characterized by the basic and supplementary AGM contraction postulates).
Theorem 7. Let
$\mathbf {K}$
be a belief set and
$\div $
be a contraction operator on
$\mathbf {K}$
. Then the following conditions are equivalent:
-
(a)
$\div $
is an extensional transitively relational GPMC. -
(b)
$\div $
is a uniform transitively relational GPMC. -
(c)
$\div $
is a transitively relational partial meet contraction. -
(d)
$\div $
satisfies the basic and supplementary AGM contraction postulates.
4 Generalized kernel contractions
In this section we present the definition and axiomatic characterization of a new type of contraction operators called generalized kernel contraction operators.
4.1 Sentence based incision functions
In this subsection we present the definition of (several kinds) of sentence based incision functions and present some results that relate incision functions with sentence based incision functions.
Definition 22. Let A be a set of sentences. Let
$A\!\!\perp \!\!\!\perp \!\!\alpha $
be the kernel set of A with respect to
$\alpha $
. A sentence based incision function
$\sigma $
for A is a function
$\sigma :\mathcal {L}\longrightarrow \mathcal {P}(A)$
such that for all sentences
$\alpha $
:Footnote
6
-
1.
$\sigma (\alpha ) \subseteq \bigcup (A\!\!\perp \!\!\!\perp \!\!\alpha )$
. -
2. If
$\emptyset \not = B \in A\!\!\perp \!\!\!\perp \!\!\alpha $
, then
$B \cap \sigma (\alpha ) \not = \emptyset $
.
The following observation states that, in the belief set context, any extensional sentence based incision function is uniform.
Observation 11. Let A be a belief set. If
$\sigma $
is an extensional sentence based incision function for A, then
$\sigma $
is uniform.
From the above observation and Observation 9, it follows that, in the context of belief sets,
$\sigma $
is an extensional sentence based incision function if and only if it is a uniform sentence based incision function.
Next we present the definition of some subclasses of sentence based incision functions.
Definition 23. A sentence based smooth incision function for a set A is a sentence based incision function
$\sigma $
for A such that it holds for all subsets
$A'$
of A that if
$A' \vdash \beta $
and
$\beta \in \sigma {(\alpha )}$
then
$A' \cap \sigma {(\alpha )} \neq \emptyset $
.
Definition 24. Let s be a kernel selection function for a set A. Then a sentence based incision function
$\sigma :\mathcal {L}\longrightarrow \mathcal {P}(A)$
is the cumulation of s if and only if for all sentences
$\alpha $
,
$$ \begin{align*} \sigma(\alpha)=\bigcup\{s(X):X\in A\!\!\perp\!\!\!\perp\!\!\alpha\}. \end{align*} $$
Definition 25. A sentence based incision function is based on a relation
$\prec $
if and only if it is the cumulation of some kernel selection function that is based on
$\prec $
.
The following theorems show how sentence based incision functions can be defined from standard incision functions and vice versa.
Theorem 8. Let A be a set of sentences and
$\sigma :\{A\!\!\perp \!\!\!\perp \!\!\epsilon : \epsilon \in \mathcal {L}\}\longrightarrow \mathcal {P}(A)$
be an incision function for A. Let
$\sigma '$
be such that
$\sigma '(\alpha )=\sigma (A\!\!\perp \!\!\!\perp \!\!\alpha )$
(for all
$\alpha $
).Footnote
7
Then it holds that:
-
1.
$\sigma '$
is a uniform sentence based incision function for A. -
2. If
$\sigma $
is smooth, then
$\sigma '$
is a uniform sentence based smooth incision function for A. -
3. If
$\sigma $
is based on a regular and virtually connected hierarchy
$\prec $
, then
$\sigma '$
is a uniform sentence based incision function that is based on
$\prec $
.
Theorem 9. Let A be a set of sentences and
$\sigma :\mathcal {L}\longrightarrow \mathcal {P}(A)$
be a uniform sentence based incision function for A. Let
$\sigma '$
be such that
$\sigma '(A\!\!\perp \!\!\!\perp \!\!\alpha )=\sigma (\alpha )$
(for all
$\alpha $
).Footnote
8
Then it holds that:
-
1.
$\sigma '$
is an incision function for A. -
2. If
$\sigma $
is smooth, then
$\sigma '$
is a smooth incision function for A. -
3. If
$\sigma $
is based on a regular and virtually connected hierarchy
$\prec $
, then
$\sigma '$
is an incision function that is based on
$\prec $
.
4.2 Generalized kernel contractions on belief bases
The definition of the generalized kernel contraction operators is similar to the one presented for kernel contractions, but instead of being defined by means of incision functions these operators are defined by means of sentence based incision functions.
Definition 26. Let A be a set of sentences and
$\sigma :\mathcal {L}\longrightarrow \mathcal {P}(A)$
be a sentence based incision function for A. The generalized kernel contraction (GKC) operator on A based on
$\sigma $
is the operator
$\div _{\sigma }$
such that for all sentences
$\alpha $
:
$$ \begin{align*} A\div_{\sigma}\alpha = A \setminus \sigma(\alpha). \end{align*} $$
An operator
$\div $
for a set A is a GKC if and only if there is a sentence based incision function
$\sigma $
for A such that
$A \div \alpha = A\div _{\sigma } \alpha $
for all sentences
$\alpha $
.
In the following theorem, we present an axiomatic characterization for GKC operators.
Theorem 10. Let A be a belief base. An operator
$\div $
on A is a GKC if and only if it satisfies success, inclusion and core-retainment.
In the following definition we introduce less general classes of GKC operators.
Definition 27. An extensional GKC operator on A is a GKC operator on A which is based on an extensional sentence based incision function. A uniform GKC operator on A is a GKC operator on A which is based on a uniform sentence based incision function. A GKC operator is smooth if and only if it is based on a sentence based smooth incision function.
We now present axiomatic characterizations for the classes of operators mentioned in the above definition.
Theorem 11. Let A be a belief base and
$\div $
an operator on A. It holds that:
We finish this section by presenting two representation theorems. These theorems illustrate that the classes of uniform GKC and of uniform smooth GKC operators coincide, respectively, with the classes of kernel contraction and of smooth kernel contraction operators.
Theorem 12. Let A be a belief base and
$\div $
an operator on A. The following conditions are equivalent.
-
(a)
$\div $
is a uniform GKC operator. -
(b)
$\div $
satisfies success, inclusion, core-retainment and uniformity. -
(c)
$\div $
is a kernel contraction.
Theorem 13. Let A be a belief base and
$\div $
an operator on A. The following conditions are equivalent.
-
(a)
$\div $
is a uniform smooth GKC operator. -
(b)
$\div $
satisfies success, inclusion, core-retainment, uniformity and relative closure. -
(c)
$\div $
is a smooth kernel contraction.
4.3 Generalized smooth kernel and safe contraction operators on belief sets
We start this subsection with a theorem that states that when considering the specific case of contractions on belief sets, the classes of extensional smooth GKC, of uniform smooth GKC and of standard smooth kernel contractions are all identical.
Theorem 14. Let
$\mathbf {K}$
be a belief set and
$\div $
be a contraction operator on
$\mathbf {K}$
. Then the following conditions are equivalent:
-
(a)
$\div $
is an extensional smooth GKC. -
(b)
$\div $
is a uniform smooth GKC. -
(c)
$\div $
is a smooth kernel contraction. -
(d)
$\div $
satisfies the basic AGM contraction postulates.
In the following definition we introduce the definition of generalized safe contraction operator.
Definition 28. Let
$\prec $
be a hierarchy over a set of sentences A. Let
$\sigma $
be the sentence based incision function that is based on
$\prec $
and
$\div _\sigma $
the generalized kernel contraction based on
$\sigma $
. The operation of generalized safe contraction
$\div _\prec $
based on
$\prec $
is defined as follows:
$$ \begin{align*} A\div_\prec \alpha=A\cap Cn(A\div_\sigma \alpha). \end{align*} $$
The following theorem asserts that the newly proposed classes of extensional safe and of uniform safe contractions (on belief sets) based on a regular and virtually connected hierarchy are identical and, furthermore, that they are axiomatically characterized by the basic and supplementary AGM contraction postulates (just as it is the case regarding the standard safe contractions based on a regular and virtually connected hierarchy).
Theorem 15. Let
$\mathbf {K}$
be a belief set and
$\div $
be a contraction operator on
$\mathbf {K}$
. Then the following conditions are equivalent:
-
(a)
$\div $
is an extensional generalized safe contraction based on a regular and virtually connected hierarchy. -
(b)
$\div $
is a uniform generalized safe contraction based on a regular and virtually connected hierarchy. -
(c)
$\div $
is a safe contraction based on a regular and virtually connected hierarchy. -
(d)
$\div $
satisfies the basic and supplementary AGM contraction postulates.
5 Maps between belief base contraction operators
In this section, we study the interrelations among the classes of GPMC and GKC operators on belief bases introduced in the previous sections. The following observation presents those interrelations, which follow from Observation 1 and the representation theorems presented in Sections 3.2 and 4.2.
Observation 12. Let A be a belief base and
$\div $
be an operator on A. Then:
-
1. If
$\div $
is an extensional GPMC, then it is a GPMC. -
2. If
$\div $
is a uniform GPMC, then it is an extensional GPMC. -
3. If
$\div $
is an extensional smooth GKC, then it is a smooth GKC. -
4. If
$\div $
is a uniform smooth GKC, then it is an extensional smooth GKC. -
5. If
$\div $
is an extensional GKC, then it is a GKC. -
6. If
$\div $
is a uniform GKC, then it is an extensional GKC. -
7. If
$\div $
is a GPMC, then it is a smooth GKC. -
8. If
$\div $
is an extensional GPMC, then it is an extensional smooth GKC. -
9. If
$\div $
is a uniform GPMC, then it is a uniform smooth GKC. -
10. If
$\div $
is a smooth GKC, then it is a GKC. -
11. If
$\div $
is an extensional smooth GKC, then it is an extensional GKC. -
12. If
$\div $
is a uniform smooth GKC, then it is a uniform GKC.
In Figure 1 we present a diagram that summarizes the logical relationships between the operators of base contraction mentioned along this paper. The relationships in terms of set inclusion among the classes of operators represented in this diagram are exactly those indicated by arrows (and their transitive closure).
Logical relationships between different operations of base contraction. An arrow between two boxes symbolizes that the class of contraction operators at the origin of the arrow is a subclass of the class of contraction operators at the end of that arrow.
6 Summary, discussion and conclusion
The one that is currently considered the standard model of belief change is the AGM model, presented in [Reference Alchourrón, Gärdenfors and Makinson1]. In that seminal paper the class of partial meet contractions on belief sets was proposed and axiomatically characterized.
A partial meet contraction on a set of sentences A is essentially defined as a function which associates to each sentence
$\alpha $
the intersection of some non-empty family of remainders of A by
$\alpha $
(i.e., maximal subsets of A which do not imply
$\alpha $
). Hence, naturally, the basic construct underlying the definition of partial meet contractions on a set of sentences A is a selection function—which is, roughly speaking, a function that picks, for each remainder set of A, some of its elements. Not surprisingly these functions have been defined as functions from
$\{A \perp \alpha : \alpha \in \mathcal {L}\}$
to
$\mathcal {P}(\mathcal {P}(A))$
.
One of the main rationality principles that are usually required to be fulfilled by a (belief) change operation is known as irrelevance of syntax (e.g., [Reference Dalal5, Reference Gärdenfors7]) according to which the result of a (belief) change should not depend on the syntax (or representation) of neither the previous beliefs nor the new information (that causes the change). Of the postulates included in the axiomatic characterization of the operators of partial meet contraction (on belief sets) presented in [Reference Alchourrón, Gärdenfors and Makinson1], the one that captures the principle of irrelevance of syntax is extensionality, while the irrelevance of syntax postulate that is used in the axiomatic characterization of partial meet contraction on belief bases, presented in [Reference Hansson and Gärdenfors9], is uniformity.
Next we present a brief analysis of the usefulness of the postulates of extensionality and of uniformity in the (proofs for the) axiomatic characterizations of partial meet contraction on belief sets [Reference Alchourrón, Gärdenfors and Makinson1] and on belief bases [Reference Hansson and Gärdenfors9], respectively.
The selection function
$\gamma :\{A\perp \epsilon : \epsilon \in \mathcal {L}\}\longrightarrow \mathcal {P}(\mathcal {P}(A))$
that is presented in the postulates to construction part of the proof of the representation theorem for partial meet contractions (both on belief sets and on belief bases), is defined, using
$\div $
, by
$$ \begin{align*} \gamma(A\perp \alpha) = \begin{cases} \{X\in A\perp \alpha:A\div \alpha \subseteq X\}, & \; \text{if } A\perp \alpha\not=\emptyset,\\ A, & \; \text{ if } A\perp \alpha=\emptyset. \end{cases} \end{align*} $$
When A is a belief set, the assumption that
$\div $
satisfies extensionality is enough to assure that
$\gamma $
is a (well-defined) function. However, if A is not assumed to be a logically closed set, the postulate of extensionality is not strong enough to assure this. In that scenario the proof presented for the fact that
$\gamma $
is a function relies on the imposition that
$\div $
satisfies uniformity.
While the postulate of extensionality is a very intuitive and natural property to require from a belief change operator, the postulate of uniformity is much less intuitive. Indeed, while extensionality can be informally stated as “the outputs of contractions by equivalent sentences are identical,” the postulate of uniformity is a quite technical property which asserts that “the outputs of contractions by sentences which are implied by exactly the same subsets of the belief base A are identical.”
In this paper we have proposed a new kind of function, which we designated by sentence based selection functions, whose purpose is exactly the same of the standard selection functions (i.e., to choose some of the elements of any given remainder set), but which differ from the standard selection functions in the fact that, while the latter associate a set of remainders to each remainder set, the sentence based selection functions associate a set of remainders (directly) to each sentence, i.e., sentence based selection functions have been defined as functions from
$\mathcal {L}$
to
$\mathcal {P}(\mathcal {P}(A))$
. Then we have introduced a new class of contraction functions—the generalized partial meet contractions (GPMC)—whose definition is similar to that of the partial meet contractions but uses the sentence based selection functions instead of the standard ones. More precisely, while a partial meet contraction on a set A is an operator
$\div $
such that, for all sentences
$\alpha $
,
$A \div \alpha = \cap \gamma (A \perp \alpha )$
, for some selection function
$\gamma $
, a generalized partial meet contraction on a set A is an operator
$\div _G$
such that, for all sentences
$\alpha $
, the slightly simpler and more natural identity
$A \div _G \alpha = \cap \gamma _G(\alpha )$
holds, where
$\gamma _G$
is a sentence based selection function.
Some of the results presented in this paper show that, in the context of contractions on belief bases:
-
(i) GPMCs are axiomatically characterized by the postulates of success, inclusion and relevance, i.e., by the all the postulates that axiomatically characterize partial meet contractions except uniformity.
-
(ii) Extensional sentence based selection functions—which are sentence based selection functions that associate the same image to any two equivalent sentences—and uniform sentence based selection functions—which are sentence based selection functions that associate the same image to any two sentences that are implied by precisely the same subsets of the belief base A under consideration—give rise to the following particular kinds of GPMCs:
-
• Extensional GPMCs—the GPMCs that are based on an extensional sentence based selection function—which are axiomatically characterized by the postulates of success, inclusion, relevance and extensionality and may not satisfy uniformity. Hence the class of partial meet contractions is a strict subclass of the class of extensional GPMCs;
-
• Uniform GPMCs—the GPMCs that are based on a uniform sentence based selection function—which are axiomatically characterized by the postulates of success, inclusion, relevance and uniformity.
-
The above facts highlight that, while the class of uniform GPMCs coincides precisely with the class of partial meet contractions (although their definitions are different), the GPMCs and the extensional GPMCs constitute two novel types of contraction functions on belief bases, which differ from the partial meet contractions essentially in what concerns the way each of them addresses the principle of irrelevance of syntax. In what follows we present a brief analysis of each of those contraction functions from that perspective.
The GPMCs do not satisfy the irrelevance of syntax principle at all. In fact, given a GPMC
$\div _G$
on a set A and two logically equivalent sentences
$\alpha $
and
$\beta $
it may be the case that
$A \div _G \alpha \neq A \div _G \beta $
. Due to this fact the adequacy of GPMCs as (belief) contraction functions is naturally questionable. In this regard, and however this discussion is beyond the scope of this paper, we shall only remark that there are lots of contexts in which the irrelevance of syntax principle may be itself arguable. For example, in some belief change scenarios (or other similar contexts) it may be appropriate to treat differently the two sentences/beliefs “John does not dislike swimming” and “John likes swimming” (although these are two logically equivalent sentences).
On the other hand, extensional GPMCs constitute a new kind of belief base contraction function whose characterizing postulate of irrelevance of syntax is precisely the same one which occurs in the classical axiomatic characterization of partial meet contractions for belief sets. Therefore, we believe extensional GPMCs are more natural belief change functions on belief bases than partial meet contractions.
We have also shown that in the context of contractions on belief sets the classes of partial meet contractions, uniform GPMCs and extensional GPMCs are all identical. Furthermore, we have also shown that the class of transitively relational partial meet contractions is also a notable subclass of the class of GPMCs. Indeed it coincides with both the classes of extensional transitively relational GPMCs and of uniform transitively relational GPMCs.
At this point we would like to mention that, despite the above mentioned equivalence of definitions in the context of belief sets, in our opinion, also in that setting, the definition presented in the present paper is simpler and more natural than the classical definition of partial meet contraction. The main difference between the two definitions is the fact that one uses standard selection functions and the other one uses sentence based selection functions. While it is absolutely understandable why, in the original definition, the selection functions
$\gamma $
are assumed to be functions whose domain is the set of all remainder sets, we believe that when contracting a set A by a sentence
$\alpha $
it is more natural to use a function
$\gamma _S$
whose domain is
$\mathcal {L}$
, and which can be directly applied to
$\alpha $
rather that to
$A \perp \alpha $
. That is, we consider that it is more natural to define
${ A} \div \alpha $
by
$\cap \gamma _S(\alpha )$
than by
$\cap \gamma (A \perp \alpha )$
. In fact, when using a function
$\gamma _S$
from
$\mathcal {L}$
to
$\mathcal {P}(\mathcal {P}(A))$
the (GPMC) contraction of A by
$\alpha $
consists of a two step procedure (first compute
$\gamma _S(\alpha )$
and then obtain the intersection of all the sets there contained). On the other hand, when considering a function
$\gamma _S$
from
$\{A \perp \alpha : \alpha \in \mathcal {L}\}$
to
$\mathcal {P}(\mathcal {P}(A))$
, the process of (partial meet) contraction of A by
$\alpha $
comprises three steps (first obtain the remainder set
$A \perp \alpha $
, then compute
$\gamma (A \perp \alpha )$
and finally obtain the intersection of all the sets there contained).
However, as we have seen, in the context of belief sets these different definitions all turn out to be equivalent and, for this reason whichever would have been the first one of this definitions to be presented, it would naturally be accepted (because it would be proven to be characterized by the AGM postulates for contraction). In fact, since one of the basic AGM postulates is extensionality, we believe that if the AGM trio had first considered the contraction function
$\div $
, defined by
${ A} \div \alpha = \cap \gamma _S(\alpha )$
(where
$\gamma _S$
is a sentence based selection function), then they would have immediately required
$\gamma _S$
to be extensional (since that would be the most obvious way to proceed in order to assure the satisfaction of the postulate of extensionality by the induced contraction function). Nevertheless, we doubt the notion of uniform sentence based selection functions would ever have come to their mind (since in our opinion it not a very natural or intuitive notion).
Moreover, we conjecture that if the original definition of partial meet contractions on belief sets would have been presented with the formulation that we have used in the definition proposed in this paper for extensional GPMCs, then the contraction functions which are nowadays known as partial meet contractions on belief bases would probably never have appeared and, furthermore, even the postulate of uniformity might not have been proposed (yet). The definition of partial meet contractions on belief bases is simply identical to the classical definition of partial meet contraction (the only difference being the fact that the set to be contracted is assumed to be a belief base rather than a belief set). However, the postulate of extensionality is not a strong enough irrelevance of syntax postulate to characterize this operation and, for that purpose, Hansson [Reference Hansson and Gärdenfors9] needed to introduce the postulate of uniformity. Nevertheless, if the original definition of partial meet contractions on belief sets would have been presented with the alternative (but equivalent) formulation which we propose in the present paper as definition for the extensional GPMCs, then its direct translation to the context of belief bases would originate a class of functions—namely the class of extensional GPMCs on belief bases—which has the postulate of extensionality as its characteristic irrelevance of syntax postulate. If this had been the case, it seems to us there would not exist any motivation for introducing either the postulate of uniformity (which, as previously mentioned, is a quite technical and not at all intuitive property) or the class of uniform GPMCs (which coincides with the class of partial meet contractions on belief bases).
Apart from the above summarized and discussed definitions and results concerning partial meet contractions, in the present paper we have also presented an analogous study concerning kernel contraction [Reference Hansson11], another operation of belief contraction that has also acquired the status of a benchmark in the context of belief change operators.
Unlike partial meet contractions, kernel contractions were originally proposed as contraction functions defined on the more general setting of belief bases (rather than only on belief sets). However, their definition was strongly inspired by the definition of partial meet contractions. In fact, while a partial meet contraction of A by
$\alpha $
is based on a selection among the maximal subsets of A that do not imply
$\alpha $
, a kernel contraction is based on a selection among the elements of minimal subsets of A that imply
$\alpha $
, which are called
$\alpha $
-kernels of A. So, the main construct underlying the definition of kernel contractions on a set of sentences A is an incision function—which, roughly speaking, is a function that picks, for each kernel set of A, a set of sentences which (i) only contains sentences that are included in some of the members of that kernel set and (ii) contains at least one element of each one of the (non-empty) elements of that kernel set. Analogously to what had been the case regarding the definition of selection functions, the incision functions were originally presented as functions from
$\{A\!\!\perp \!\!\!\perp \!\!\alpha : \alpha \in \mathcal {L}\}$
to
$\mathcal {P}(A)$
.
Both the axiomatic characterization for partial meet contractions, and that for kernel contractions on belief bases (obtained in [Reference Hansson and Gärdenfors9, Reference Hansson11]respectively) contain exactly the same irrelevance of syntax postulate, namely uniformity.
Reasoning in an absolutely analogous way to the way we did regarding partial meet contractions, we have introduced the so-called sentence based incision functions, whose purpose is exactly the same of the standard incision functions, but which have
$\mathcal {L}$
(instead of
$\{A\!\!\perp \!\!\!\perp \!\!\alpha : \alpha \in \mathcal {L}\}$
) as their domain. Then we have defined the class of generalized kernel contractions (GKC), which are basically operators defined as kernel contractions but using sentence based incision functions instead of standard incision functions. That is, an operator
$\div $
is a GKC if, for every sentence
$\alpha $
,
$A \div \alpha = A\setminus \sigma (\alpha )$
, for some sentence based incision function
$\sigma $
. We have also considered several relevant subclasses of the class of GKC. The results that we have obtained regarding these operations are similar to the ones obtained regarding GPMCs and, in particular, allow us to conclude that:
-
• GKCs (resp. smooth GKCs) are axiomatically characterized by the postulates of success, inclusion and core-retainment (resp. by the postulates of success, inclusion, core-retainment and relative closure), i.e., by all the postulates that axiomatically characterize kernel (respectively, smooth kernel) except uniformity.
-
• Extensional GKCs (resp. extensional smooth GKCs)—which are the GKCs (resp. smooth GKCs) that are based on a sentence based incision function that associates the same image to any two equivalent sentences—are axiomatically characterized by the postulates of success, inclusion, core-retainment and extensionality (resp. by the postulates of success, inclusion, core-retainment, relative closure and extensionality) and may not satisfy uniformity. Hence the class of kernel contractions (resp. smooth kernel contractions) is a strict subclass of the class of extensional GKCs (resp. extensional smooth GKCs);
-
• The class of uniform GKCs (resp. uniform smooth GKCs)—which are the GKCs (resp. smooth GKCs) that are based on a sentence based incision function that associates the same image to any two sentences that are implied by precisely the same subsets of the set A under consideration—is identical to the class of kernel contractions (resp. smooth kernel contractions).
To finish we mention that our perspective over the newly proposed classes of GKCs is similar to the one we exposed above concerning GPMCs. In particular, we consider that extensional GKCs are more natural than kernel contractions, both in what concerns their definitions (since the definition of GKCs, which uses a sentence based incision function, is simpler and, furthermore, it encompasses a two step procedure while the definition of kernel contractions, for using a standard incision function, forces the performance of three steps whenever a contraction is carried out) and in what concerns their axiomatic characterizations (since extensionality is a much nicer postulate of irrelevance of syntax than uniformity).
It remains only to say that we are also convinced that it is only due to the fact that the original definition of partial meet contractions (on belief sets) was made by means of standard selection functions that the kernel contractions on belief bases (as we know them nowadays) have come to be defined. Indeed, if the definition of partial meet contractions had originally been proposed using extensional sentence based selection functions rather than standard selection functions, the reasoning that led to the appearance of kernel contractions would have rather led to the definition of the (operators that we have designated in the present paper by) extensional GKCs. Additionally, we believe that if that had been the case then the class of kernel contractions or, equivalently, the class of uniform GKCs, would never have come into play, since at first sight there is nothing that makes the operation of kernel contraction/uniform GKC more appealing or more interesting than the operation of extensional GKC.
Appendix: Proofs
Lemma 1 [Reference Alchourrón, Makinson and Hilpinen2, Observation 2.2]
Let A be a set of sentences and
$\alpha $
a sentence. Then,
$A\perp \alpha =\emptyset $
if and only if
$\vdash \alpha $
(provided that the consequence operation
$Cn$
is compact).
Lemma 2 [Reference Hansson11]
Let A be a set of sentences and
$\alpha $
and
$\beta $
be sentences. The following three conditions are equivalent:
-
1.
$A\perp \alpha = A\perp \beta $
. -
2.
$A\!\!\perp \!\!\!\perp \!\!\alpha =A\!\!\perp \!\!\!\perp \!\!\beta $
. -
3. For all subsets D of A:
$D \vdash \alpha $
if and only if
$D \vdash \beta $
.
Proof of Observation 9
Let A be a set of sentences and f a sentence based function for A. Assume that f is uniform. Let
$\vdash \alpha \leftrightarrow \beta $
. Hence it holds that for all subsets
$A'$
of A that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
. Since f is uniform it holds that
$f(\alpha )=f(\beta )$
. Therefore f is extensional.
Proof of Observation 10
Let A be a belief set and assume that
$\gamma $
is an extensional sentence based selection function. Assume that it holds that for all subsets
$A'$
of A that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
. We will consider two cases:
Case (1)
$A\vdash \alpha $
. Hence
$A\vdash \beta $
. Since A is a belief set, it holds that
$\alpha \in A$
and
$\beta \in A$
. It holds that
$\{\alpha \}\vdash \alpha $
and
$\{\beta \} \vdash \beta $
from which it follows, by hypothesis, that
$\{\alpha \}\vdash \beta $
and
$\{\beta \} \vdash \alpha $
. Hence
$\vdash \alpha \leftrightarrow \beta $
. Since
$\gamma $
is an extensional sentence based selection function, it follows that
$\gamma (\alpha )=\gamma (\beta )$
.
Case (2)
$A\not \vdash \alpha $
. Hence
$A\not \vdash \beta $
. Thus
$A\perp \alpha =\{A\}=A\perp \beta $
. Therefore, according to condition (1) of Definition 17 it follows that
$\gamma (\alpha )=\gamma (\beta )=\{A\}$
.
Proof of Theorem 1
Let A be a set of sentences and
$\gamma :\{A\perp \epsilon : \epsilon \in \mathcal {L}\}\longrightarrow \mathcal {P}(\mathcal {P}(A))$
be a selection function for A. Let
$\gamma '$
be such that
$\gamma '(\alpha )=\gamma (A\perp \alpha )$
(for all sentences
$\alpha $
). It holds that, for every
$\alpha \in \mathcal {L}$
,
$\gamma '(\alpha )\in \mathcal {P}(\mathcal {P}(A))$
.
-
1. We must prove that: (i)
$\gamma '$
is a (well-defined) function; (ii)
$\gamma '$
satisfies conditions (1) and (2) of Definition 17; (iii)
$\gamma '$
is uniform.(i) and (ii) Follow immediately from the definition of
$\gamma '$
and the fact that
$\gamma $
is a selection function.(iii) Assume that it holds that for all subsets D of A that
$D \vdash \alpha $
if and only if
$D \vdash \beta $
. By Lemma 2 it follows that
$A\perp \alpha =A\perp \beta $
. Since
$\gamma $
is a function, it holds that
$\gamma '(\alpha )=\gamma (A\perp \alpha )=\gamma (A\perp \beta )=\gamma '(\beta )$
.
Proof of Theorem 2
Let A be a set of sentences and
$\gamma :\mathcal {L}\longrightarrow \mathcal {P}(\mathcal {P}(A))$
be a uniform sentence based selection function for A. Let
$\gamma '$
be such that
$\gamma '(A\perp \alpha )=\gamma (\alpha )$
(for all sentences
$\alpha $
).
It holds that, for every
$\alpha \in \mathcal {L}$
,
$\gamma '(A\perp \alpha )\in \mathcal {P}(\mathcal {P}(A))$
.
-
1. We must prove that: (i)
$\gamma '$
is a (well-defined) function and (ii)
$\gamma '$
satisfies conditions (1) and (2) of Definition 2.-
(i) Let
$A\perp \alpha =A\perp \beta $
. By Lemma 2 it follows from
$A\perp \alpha =A\perp \beta $
that for all subsets D of A that
$D \vdash \alpha $
if and only if
$D \vdash \beta $
. Since
$\gamma $
is uniform, it follows that
$\gamma (\alpha )=\gamma (\beta )$
. Thus
$\gamma '(A\perp \alpha )=\gamma (\alpha )=\gamma (\beta )=\gamma '(A\perp \beta )$
. Thus
$\gamma '$
is a well defined function. -
(ii) Follows immediately from the definition of
$\gamma '$
and the fact that
$\gamma $
is a sentence based selection function.
-
Proof of Theorem 3
Let A be a belief base.
Construction to postulates:
Success: Let
$\not \vdash \alpha $
. Hence
$A\perp \alpha \not =\emptyset $
. By definition of sentence based selection function it follows that
$\gamma (\alpha )$
is a non-empty subset of
$A\perp \alpha $
. Let
$X\in \gamma (\alpha )$
, hence
$X\in A\perp \alpha $
. From which it follows that
$X\not \vdash \alpha $
. Hence it follows, from
$\bigcap \gamma (\alpha )\subseteq X$
, that
$A\div \alpha =\bigcap \gamma (\alpha )\not \vdash \alpha $
.
Inclusion: We will consider two cases:
Case (1)
$\vdash \alpha $
. Hence
$A\perp \alpha =\emptyset $
. Thus
$\gamma (\alpha )=\{A\}$
. From which it follows that
$A\div \alpha =\bigcap \gamma (\alpha )=A$
.
Case (2)
$\not \vdash \alpha $
. Hence
$A\perp \alpha \not =\emptyset $
. It holds that
$\gamma (\alpha )$
is a non-empty subset of
$A\perp \alpha $
. All elements of
$A\perp \alpha $
are subsets of A. Therefore
$\bigcap \gamma (\alpha )\subseteq A$
.
Relevance: Let
$\beta \in A\setminus A\div \alpha $
. Thus
$A\div \alpha \not =A$
, from which it follows that
$A\perp \alpha \not =\emptyset $
. It holds that
$\gamma (\alpha )$
is a non-empty subset of
$A\perp \alpha $
. It follows from
$\beta \not \in A\div \alpha =\bigcap \gamma (\alpha )$
that there exists some
$X\in \gamma (\alpha )$
such that
$\beta \not \in X$
. It holds that
$X\in A\perp \alpha $
. Hence
$X\not \vdash \alpha $
and
$X\subset X\cup \{\beta \}\subseteq A$
. From
$X\in A\perp \alpha $
and
$\beta \in A\setminus X$
it follows that
$X\cup \{\beta \}\vdash \alpha $
. On the other hand, from
$X\in \gamma (\alpha )$
it follows that
$A\div \alpha =\bigcap \gamma (\alpha )\subseteq X$
.
Postulates to construction:
Assume that
$\div $
is an operator on A that satisfies success, inclusion and relevance.
Let
$\gamma $
be such that, for any sentence
$\alpha \in \mathcal {L}$
:
-
1. If
$A\perp \alpha \not =\emptyset $
, then
$\gamma (\alpha )=\{X\in A\perp \alpha :A\div \alpha \subseteq X\}$
. -
2. If
$A\perp \alpha =\emptyset $
, then
$\gamma (\alpha )=\{A\}$
.
It holds, for every
$\alpha \in \mathcal {L}$
, that
$\gamma (\alpha )\in \mathcal {P}(\mathcal {P}(A))$
.
We need to show that: (i)
$\gamma $
is a sentence based selection function and (ii)
$\bigcap \gamma (\alpha )=A\div \alpha $
.
(i) We start by showing that
$\gamma $
is a well-defined function.
Let
$\alpha =\beta $
. We will prove that
$\gamma (\alpha )=\gamma (\beta )$
. From
$\alpha =\beta $
it follows that
$A\perp \alpha =A\perp \beta $
. We will consider two cases:
Case (1)
$A\perp \alpha =\emptyset $
. Thus
$A\perp \beta =\emptyset $
. Hence
$\gamma (\alpha )=\{A\}=\gamma (\beta )$
.
Case (2)
$A\perp \alpha \not =\emptyset $
. Thus
$A\perp \beta \not =\emptyset $
. Since
$\div $
is an operator, it holds that
$A\div \alpha =A\div \beta $
. Hence
$\gamma (\alpha )=\{X\in A\perp \alpha :A\div \alpha \subseteq X\}=\{X\in A\perp \beta :A\div \beta \subseteq X\}=\gamma (\beta )$
. We will now prove that
$\gamma $
is a sentence based selection function. To do so we need to prove that:
-
(1) If
$A\perp \alpha \not =\emptyset $
, then
$\gamma (\alpha )$
is a non-empty subset of
$A\perp \alpha $
. -
(2) If
$A\perp \alpha = \emptyset $
, then
$\gamma ( \alpha )=\{A\}$
.
That (2) holds, follows trivially by definition of
$\gamma $
. Assume now that
$A\perp \alpha \not =\emptyset $
. That
$\gamma (\alpha )\subseteq A\perp \alpha $
follows by definition of
$\gamma $
. It remains to prove that
$\gamma (\alpha )\not =\emptyset $
. From
$A\perp \alpha \not =\emptyset $
it follows that
$\not \vdash \alpha $
. By
$\div $
success it follows that
$A\div \alpha \not \vdash \alpha $
and by
$\div $
inclusion it follows that
$A\div \alpha \subseteq A$
. By the upper bound property it follows that there exists some B such that
$A\div \alpha \subseteq B\in A\perp \alpha $
. Thus
$B\in \gamma (\alpha )$
, from which it follows that
$\gamma (\alpha )\not =\emptyset $
.
(ii) We need to prove that
$\bigcap \gamma (\alpha )=A\div \alpha $
.
We will consider two cases:
Case (1)
$\vdash \alpha $
. Hence
$A\perp \alpha =\emptyset $
. Thus
$\gamma (\alpha )=\{A\}$
. Thus
$\bigcap \gamma (\alpha )=A$
. From
$\div $
inclusion and relevance it follows that
$\div $
satisfies failure (Observation 1). From which it follows that
$A\div \alpha =A$
. Thus
$\bigcap \gamma (\alpha )=A\div \alpha $
.
Case (2)
$\not \vdash \alpha $
. Hence
$A\perp \alpha \not =\emptyset $
. Thus
$\gamma (\alpha )\not =\emptyset $
. According to the definition of
$\gamma $
it follows that
$A\div \alpha \subseteq X$
, for all
$X\in \gamma (\alpha )$
. Thus
$A\div \alpha \subseteq \bigcap \gamma (\alpha )$
.
Let
$\beta \not \in A\div \alpha $
. We are going to show that
$\beta \not \in \bigcap \gamma (\alpha )$
. This follows trivially if
$\beta \not \in A$
. Assume now that
$\beta \in A$
. By
$\div $
relevance it follows that there exists some set B such that
$A\div \alpha \subseteq B\subseteq A$
,
$B\not \vdash \alpha $
but
$B\cup \{\beta \}\vdash \alpha $
. It follows by the upper bound property that there exists some C such that
$B\subseteq C\in A\perp \alpha $
. It holds that
$\beta \not \in C$
(otherwise, it would follow from
$B\cup \{\beta \}\vdash \alpha $
and
$B\subseteq C$
that
$C\vdash \alpha $
, contrary to
$C\in A\perp \alpha $
). It follows from
$A\div \alpha \subseteq B\subseteq C$
and
$C\in A\perp \alpha $
that
$C\in \gamma (\alpha )$
. Thus
$\beta \not \in \bigcap \gamma (\alpha )$
.
Therefore
$\bigcap \gamma (\alpha )=A\div \alpha $
.
Proof of Theorem 4
Let A be a belief base.
(a) to (b):
By Theorem 3 it follows that
$\div $
satisfies success, inclusion and relevance. It remains to prove that
$\div $
satisfies extensionality.
It holds that, for any sentence
$\alpha $
,
$A\div \alpha =\bigcap \gamma (\alpha )$
, where
$\gamma $
is an extensional sentence based selection function. Assume that
$\vdash \alpha \leftrightarrow \beta $
. Thus
$\gamma (\alpha )=\gamma (\beta )$
. From which it follows that
$A\div \alpha =\bigcap \gamma (\alpha )=\bigcap \gamma (\beta )=A\div \beta $
.
(b) to (a):
Let
$\gamma $
be such that, for any sentence
$\alpha \in \mathcal {L}$
:
-
1. If
$A\perp \alpha \not =\emptyset $
, then
$\gamma (\alpha )=\{X\in A\perp \alpha :A\div \alpha \subseteq X\}$
. -
2. If
$A\perp \alpha =\emptyset $
, then
$\gamma (\alpha )=\{A\}$
.
We need to show that: (i)
$\gamma $
is an extensional sentence based selection function and (ii)
$\bigcap \gamma (\alpha )=A\div \alpha $
.
This is the construction used in the proof of Theorem 3. Thus according to that proof it follows that
$\gamma $
is a sentence based selection function and
$\bigcap \gamma (\alpha )=A\div \alpha $
. It remains to prove that
$\gamma $
is extensional.
Assume that
$\vdash \alpha \leftrightarrow \beta $
. By
$\div $
extensionality it follows that
$A\div \alpha =A\div \beta $
. On the other hand, it holds that
$A\perp \alpha =A\perp \beta $
. We will consider two cases:
Case (1)
$A\perp \alpha =\emptyset $
. Thus
$A\perp \beta =\emptyset $
. Therefore,
$\gamma (\alpha )=\{A\}=\gamma (\beta )$
.
Case (2)
$A\perp \alpha \not =\emptyset $
. Thus
$A\perp \beta \not =\emptyset $
. Therefore,
$\gamma (\alpha )=\{X\in A\perp \alpha :A\div \alpha \subseteq X\}=\{X\in A\perp \beta :A\div \beta \subseteq X\}=\gamma (\beta )$
.
Proof of Theorem 5
Let A be a set of sentences and
$\div $
be an operator on A.
(a) to (b):
By Theorem 3 it follows that
$\div $
satisfies success, inclusion and relevance. It remains to prove that
$\div $
satisfies uniformity.
It holds that, for any sentence
$\alpha $
,
$A\div \alpha =\bigcap \gamma (\alpha )$
, where
$\gamma $
is a uniform sentence based selection function. Assume that it holds for all subsets
$A'$
of A that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
. Thus
$\gamma (\alpha )=\gamma (\beta )$
. From which it follows that
$A\div \alpha =\bigcap \gamma (\alpha )=\bigcap \gamma (\beta )=A\div \beta $
.
(b) to (a):
Let
$\gamma $
be such that, for any sentence
$\alpha \in \mathcal {L}$
:
-
1. If
$A\perp \alpha \not =\emptyset $
, then
$\gamma (\alpha )=\{X\in A\perp \alpha :A\div \alpha \subseteq X\}$
. -
2. If
$A\perp \alpha =\emptyset $
, then
$\gamma (\alpha )=\{A\}$
.
We need to show that: (i)
$\gamma $
is a uniform sentence based selection function and (ii)
$\bigcap \gamma (\alpha )=A\div \alpha $
.
This is the construction used in the proof of Theorem 3. Thus according to that proof it follows that
$\gamma $
is a sentence based selection function and
$\bigcap \gamma (\alpha )=A\div \alpha $
. It remains to prove that
$\gamma $
is uniform.
Assume that it holds for all subsets
$A'$
of A that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
. By
$\div $
uniformity it follows that
$A\div \alpha =A\div \beta $
. On the other hand, by Lemma 2, it follows that
$A\perp \alpha =A\perp \beta $
. We will consider two cases:
Case (1)
$A\perp \alpha =\emptyset $
. Thus
$A\perp \beta =\emptyset $
. Therefore,
$\gamma (\alpha )=\{A\}=\gamma (\beta )$
.
Case (2)
$A\perp \alpha \not =\emptyset $
. Thus
$A\perp \beta \not =\emptyset $
. Therefore,
$\gamma (\alpha )=\{X\in A\perp \alpha :A\div \alpha \subseteq X\}=\{X\in A\perp \beta :A\div \beta \subseteq X\}= \gamma (\beta )$
.
(b) to (c) and (c) to (b): Follows by Observation 2.
Proof of Theorem 6
Let
$\mathbf {K}$
be a belief set and
$\div $
be an operator on
$\mathbf {K}$
.
According to Observation 5 conditions (c) and (d) are equivalent. On the other hand it follows immediately from Observations 9 and 10 that conditions (a) and (b) are equivalents. Therefore, to conclude this proof it is enough to show that conditions (b) and (c) are equivalents.
(c) to (b)
Let
$\div $
be a partial meet contraction. Hence there exists a selection function
$\gamma :\{\mathbf {K}\perp \epsilon : \epsilon \in \mathcal {L}\}\longrightarrow \mathcal {P}(\mathcal {P}(\mathbf {K}))$
such that
$\mathbf {K}\div \alpha =\bigcap \gamma (\mathbf {K}\perp \alpha )$
. Let
$\gamma '$
be such that
$\gamma '(\alpha )=\gamma (\mathbf {K}\perp \alpha )$
(for all
$\alpha $
). By Theorem 1,
$\gamma '$
is a uniform sentence based selection function. Thus
$\mathbf {K}\div \alpha =\bigcap \gamma (\mathbf {K}\perp \alpha )=\bigcap \gamma '(\alpha )$
. Hence
$\div $
is a uniform GPMC.
(b) to (c)
Let
$\div $
be a uniform GPMC. Hence there exists a uniform sentence based selection function
$\gamma $
such that
$\mathbf {K}\div \alpha =\bigcap \gamma (\alpha )$
. Let
$\gamma '$
be such that
$\gamma '(\mathbf { K}\perp \alpha )=\gamma (\alpha )$
(for all
$\alpha $
). By Theorem 2,
$\gamma '$
is a selection function. Thus
$\mathbf {K}\div \alpha =\bigcap \gamma (\alpha )=\bigcap \gamma '(\mathbf {K}\perp \alpha )$
. Hence
$\div $
is a partial meet contraction.
Proof of Theorem 7
Let
$\mathbf {K}$
be a belief set and
$\div $
be an operator on
$\mathbf {K}$
.
According to Observation 6 conditions (c) and (d) are equivalent. On the other hand it follows immediately from Observations 9 and 10 that conditions (a) and (b) are equivalents. Therefore, to conclude this proof it is enough to show that conditions (b) and (c) are equivalents.
(c) to (b)
Assume that
$\div $
is a transitively relational partial meet contraction. Hence there exists a transitively relational selection function such that
$\mathbf {K}\div \alpha =\bigcap \gamma (\mathbf {K}\perp \alpha )$
. Let
$\gamma '$
be such that
$\gamma '(\alpha )=\gamma (\mathbf {K}\perp \alpha )$
(for all
$\alpha $
). By Theorem 1,
$\gamma '$
is a uniform transitively relational sentence based selection function. It holds that
$\mathbf {K}\div \alpha =\bigcap \gamma (\mathbf {K}\perp \alpha )=\bigcap \gamma '(\alpha )$
. Hence
$\div $
is a uniform transitively relational GPMC.
(b) to (c)
Assume that
$\div $
is a uniform transitively relational GPMC. Hence there exists a uniform transitively relational sentence based selection function
$\gamma $
such that
$\mathbf {K}\div \alpha =\bigcap \gamma (\alpha )$
. Let
$\gamma '$
be such that
$\gamma '(\mathbf {K}\perp \alpha )=\gamma (\alpha )$
(for all
$\alpha $
). By Theorem 2,
$\gamma '$
is a transitively relational selection function. It holds that
$\mathbf { K}\div \alpha =\bigcap \gamma (\alpha )=\bigcap \gamma (\mathbf {K}\perp \alpha )$
. Hence
$\div $
is a transitively relational partial meet contraction.
Proof of Observation 11
Let A be a belief set and assume that
$\sigma $
is an extensional sentence based incision function. Assume that it holds that for all subsets
$A'$
of A that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
. We will consider two cases:
Case (1)
$A\vdash \alpha $
. Hence
$A\vdash \beta $
. Since A is a belief set, it holds that
$\alpha \in A$
and
$\beta \in A$
. It holds that
$\{\alpha \}\vdash \alpha $
and
$\{\beta \} \vdash \beta $
from which it follows, by hypothesis, that
$\{\alpha \}\vdash \beta $
and
$\{\beta \} \vdash \alpha $
. Hence
$\vdash \alpha \leftrightarrow \beta $
. Since
$\sigma $
is extensional, it follows that
$\sigma (\alpha )=\sigma (\beta )$
.
Case (2)
$A\not \vdash \alpha $
. Hence
$A\not \vdash \beta $
. Thus
$A\!\!\perp \!\!\!\perp \!\!\alpha =\emptyset =A\!\!\perp \!\!\!\perp \!\!\beta $
. Therefore, according to condition (1) of Definition 22, it follows that
$\sigma (\alpha )=\emptyset =\sigma (\beta )$
.
Proof of Theorem 8
Let A be a set of sentences and
$\sigma :\{A\!\!\perp \!\!\!\perp \!\!\epsilon : \epsilon \in \mathcal {L}\}\longrightarrow \mathcal {P}(A)$
be an incision function for A. Let
$\sigma '$
be such that
$\sigma '(\alpha )=\sigma (A\!\!\perp \!\!\!\perp \!\!\alpha )$
(for all
$\alpha $
).
It holds that, for every
$\alpha \in \mathcal {L}$
,
$\sigma '(\alpha )\in \mathcal {P}(A)$
.
-
1. We must prove that: (i)
$\sigma '$
is a (well-defined) function; (ii)
$\sigma '$
satisfies conditions (1) and (2) of Definition 22; and (iii)
$\sigma '$
is uniform.(i) and (ii) Follow immediately from the definition of
$\sigma '$
and the fact that
$\sigma $
is an incision function.(iii) Assume that it holds that for all subsets D of A that
$D \vdash \alpha $
if and only if
$D \vdash \beta $
. By Lemma 2 it follows that
$A\!\!\perp \!\!\!\perp \!\!\alpha =A\!\!\perp \!\!\!\perp \!\!\beta $
. Since
$\sigma $
is a function, it holds that
$\sigma '(\alpha )=\sigma (A\!\!\perp \!\!\!\perp \!\!\alpha )=\sigma (A\!\!\perp \!\!\!\perp \!\!\beta )=\sigma '(\beta )$
.
Proof of Theorem 9
Let A be a set of sentences and
$\sigma :\mathcal {L}\longrightarrow \mathcal {P}(A)$
be a uniform sentence based incision function for A. Let
$\sigma '$
be such that
$\sigma '(A\!\!\perp \!\!\!\perp \!\!\alpha )=\sigma (\alpha )$
(for all
$\alpha $
).
It holds that, for every
$\alpha \in \mathcal {L}$
,
$\sigma '(A\!\!\perp \!\!\!\perp \!\!\alpha )\in \mathcal {P}(A)$
.
-
1. We must prove that: (i)
$\sigma '$
is a (well-defined) function and (ii)
$\sigma '$
satisfies conditions (1) and (2) of Definition 5.-
(i) Let
$A\!\!\perp \!\!\!\perp \!\!\alpha =A\!\!\perp \!\!\!\perp \!\!\beta $
. It holds that
$\sigma '(A\!\!\perp \!\!\!\perp \!\!\alpha )=\sigma (\alpha )$
and
$\sigma '(A\!\!\perp \!\!\!\perp \!\!\beta )=\sigma (\beta )$
. On the other hand, by Lemma 2 it follows from
$A\!\!\perp \!\!\!\perp \!\!\alpha =A\!\!\perp \!\!\!\perp \!\!\beta $
that for all subsets D of A that
$D \vdash \alpha $
if and only if
$D \vdash \beta $
. Since
$\sigma $
is uniform, it follows that
$\sigma (\alpha )=\sigma (\beta )$
. Thus
$\sigma '(A\!\!\perp \!\!\!\perp \!\!\alpha )=\sigma (\alpha )=\sigma (\beta )=\sigma '(A\!\!\perp \!\!\!\perp \!\!\beta )$
. Thus
$\sigma '$
is a well defined function. -
(ii) Follows immediately from the definition of
$\sigma '$
and the fact that
$\sigma $
is a sentence based incision function.
-
Proof of Theorem 10
Let A be a set of sentences and
$\div $
be an operator on A.
Construction to postulates:
Inclusion: Follows immediately by definition of
$\div $
.
Success: Let
$\not \vdash \alpha $
. Assume by reductio ad absurdum that
$A\div \alpha \vdash \alpha $
. Then there exists
$B\subseteq A\div \alpha $
such that
$B\in A\!\!\perp \!\!\!\perp \!\!\alpha $
. From
$\not \vdash \alpha $
it follows that
$B\not =\emptyset $
. By the second clause of Definition 22 it follows that
$B \cap \sigma (\alpha ) \not = \emptyset $
. Thus there exists a sentence
$\beta $
such that
$\beta \in B$
and
$\beta \in \sigma (\alpha )$
. From the latter it follows that
$\beta \not \in A\div \alpha $
. Contradiction, since
$\beta \in B\subseteq A\div \alpha $
.
Core-retainment: Let
$\beta \in A\setminus A\div \alpha $
. Thus
$\beta \in \sigma (\alpha )$
. It holds that
$\sigma (\alpha ) \subseteq \bigcup (A\!\!\perp \!\!\!\perp \!\!\alpha )$
. Thus there exists
$B\in A\!\!\perp \!\!\!\perp \!\!\alpha $
such that
$\beta \in B$
. Let
$C=B\setminus \{\beta \}$
. Hence it holds that
$C\subseteq A$
,
$C\not \vdash \alpha $
and
$C\cup \{\beta \}\vdash \alpha $
.
Postulates to construction:
Assume that
$\div $
is an operator on A that satisfies success, inclusion and core-retainment.
Let
$\sigma $
be such that, for any sentence
$\alpha $
,
$\sigma (\alpha )=A\setminus A\div \alpha $
.
It holds, for every
$\alpha \in \mathcal {L}$
, that
$\sigma (\alpha )\in \mathcal {P}(A)$
.
We need to show that: (i)
$\sigma $
is a sentence based incision function and (ii)
$A\div \alpha =A\setminus \sigma (\alpha )$
.
(i) We start by showing that
$\sigma $
is a well-defined function. Let
$\alpha =\beta $
. We will prove that
$\sigma (\alpha )=\sigma (\beta )$
. From
$\alpha =\beta $
it follows that
$A\div \alpha =A\div \beta $
(since
$\div $
is a contraction operator). Thus
$\sigma (\alpha )=A\setminus A\div \alpha =A\setminus A\div \beta =\sigma (\beta )$
. It remains to prove that it is a sentence based incision function, i.e., that conditions (1) and (2) of Definition 22 hold.
(1) Let
$\beta \in \sigma (\alpha )$
. Hence
$\beta \in A\setminus A\div \alpha $
. By
$\div $
core-retainment it follows that there exists some set
$A'$
such that
$A' \subseteq A$
and
$\alpha \notin Cn(A')$
but
$\alpha \in Cn( A' \cup \{\beta \}).$
By compactness there exists a finite subset
$A"$
of
$A'$
such that
$\alpha \in Cn( A" \cup \{\beta \}).$
It follows from
$\alpha \notin Cn(A")$
and
$\alpha \in Cn( A" \cup \{\beta \})$
that there exists some
$\alpha $
-kernel
$A"'$
that contains
$\beta $
. It follows from
$\beta \in A"'\in A\!\!\perp \!\!\!\perp \!\!\alpha $
that
$\beta \in \bigcup (A\!\!\perp \!\!\!\perp \!\!\alpha )$
.
(2) Assume that
$\emptyset \not = B \in A\!\!\perp \!\!\!\perp \!\!\alpha $
. We intend to prove that
$B \cap \sigma (\alpha ) \not = \emptyset $
. It follows from
$\emptyset \not = B \in A\!\!\perp \!\!\!\perp \!\!\alpha $
that
$\not \vdash \alpha $
. By
$\div $
success it follows that
$A\div \alpha \not \vdash \alpha $
. From
$B \in A\!\!\perp \!\!\!\perp \!\!\alpha $
it follows that
$B\vdash \alpha $
. Hence
$B\not \subseteq A\div \alpha $
. Hence there exists some
$\beta \in B\subseteq A$
such that
$\beta \not \in A\div \alpha $
. Therefore
$\beta \in A\setminus A\div \alpha =\sigma (\alpha )$
. Hence
$\beta \in B \cap \sigma (\alpha )$
, from which it follows that
$B \cap \sigma (\alpha ) \not = \emptyset $
.
(ii) It follows from
$\div $
inclusion that
$A\div \alpha \subseteq A$
. Hence
$A\setminus \sigma (\alpha )=A\setminus (A\setminus A\div \alpha )=A\div \alpha $
.
Proof of Theorem 11
(Left-to-right)
Let
$\sigma $
be a sentence based incision function for A and
$\div $
be such that, for any sentence
$\alpha $
,
$A\div \alpha =A\setminus \sigma (\alpha )$
. By Theorem 10 it holds that
$\div $
satisfies success, inclusion and core-retainment. Next we prove that:
(i) If
$\sigma $
is an extensional sentence based incision function, then
$\div $
satisfies extensionality.
(ii) If
$\sigma $
is a sentence based smooth incision function, then
$\div $
satisfies relative closure.
(i) Let
$\vdash \alpha \leftrightarrow \beta $
and assume that
$\sigma $
is an extensional sentence based incision function. Hence
$\sigma (\alpha )=\sigma (\beta )$
. Therefore
$A\div \alpha =A\setminus \sigma (\alpha )=A\setminus \sigma (\beta )=A\div \beta $
.
(ii) Assume that
$\beta \not \in A\div \alpha $
. We intend to prove that
$\beta \not \in A\cap Cn(A\div \alpha )$
. It follows trivially if
$\beta \not \in A$
. Assume now that
$\beta \in A$
. From
$\beta \not \in A\div \alpha $
it follows that
$\beta \in \sigma (\alpha )$
. Assume by reductio ad absurdum that
$\beta \in Cn(A\div \alpha )$
. Hence
$\beta \in Cn(A\setminus \sigma (\alpha ))$
. Let
$B=A\setminus \sigma (\alpha )$
. Hence
$B\subseteq A$
,
$B\vdash \beta $
and
$\beta \in \sigma (\alpha )$
. It holds that
$\sigma $
is smooth, from which it follows that
$B\cap \sigma (\alpha )\not =\emptyset $
. Contradiction.
(Right-to-left)
Assume that
$\div $
satisfies success, inclusion and core-retainment. Let
$\sigma $
be such that, for any
$\alpha \in \mathcal {L}$
,
$\sigma (\alpha )=A\setminus A\div \alpha $
. It was shown in the postulates to construction part of the proof of Theorem 10 that
$\sigma $
is a sentence based incision function and for any
$\alpha $
that
$A\div \alpha =A\setminus \sigma (\alpha )$
. Next we prove that:
-
(i) If
$\div $
satisfies extensionality, then
$\sigma $
is an extensional sentence based incision function; -
(ii) If
$\div $
satisfies relative closure, then
$\sigma $
is a sentence based smooth incision function.
(i) Let
$\vdash \alpha \leftrightarrow \beta $
. By
$\div $
extensionality it follows that
$A\div \alpha =A\div \beta $
. Hence
$\sigma (\alpha )=A\setminus A\div \alpha =A\setminus A\div \beta =\sigma (\beta )$
.
(ii) Let
$B\subseteq A$
be such that
$B\vdash \beta $
and
$\beta \in \sigma (\alpha )$
. We will show that
$B \cap \sigma {(\alpha )}\not =\emptyset $
. Suppose by reductio ad absurdum that
$A\div \alpha \vdash \beta $
. From
$\beta \in \sigma (\alpha )=A\setminus A\div \alpha $
it follows that
$\beta \in A$
. By
$\div $
relative closure it follows that
$\beta \in A\div \alpha $
. Contradiction, since
$\beta \in A\setminus A\div \alpha $
. Therefore, we can conclude that
$A\div \alpha \not \vdash \beta $
. From the latter and
$B\vdash \beta $
it follows that
$B\not \subseteq A\div \alpha $
. Hence there exists
$\varepsilon \in B\setminus A\div \alpha $
. It holds that
$B\subseteq A$
, thus
$\varepsilon \in A\setminus A\div \alpha =\sigma (\alpha )$
. Therefore
$\varepsilon \in B \cap \sigma (\alpha )$
, from which it follows that
$B \cap \sigma (\alpha )\not =\emptyset $
.
Proof of Theorem 12
Let A be a set of sentences and
$\div $
be an operator on A.
(a) to (b)
Assume that
$\div $
is a uniform GKC operator. It follows, by Theorem 10, that
$\div $
satisfies success, inclusion and core-retainment. It remains to prove that
$\div $
satisfies uniformity. It holds, for any sentence
$\alpha $
that
$A\div \alpha =A\setminus \sigma (\alpha )$
, where
$\sigma $
is a uniform sentence based incision function. Assume that it holds for all subsets
$A'$
of A that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
. Hence
$\sigma (\alpha )=\sigma (\beta )$
. Therefore
$A\div \alpha =A\setminus \sigma (\alpha )=A\setminus \sigma (\beta )=A\div \beta $
.
(b) to (a)
Assume now that
$\div $
satisfies success, inclusion, core-retainment and uniformity. Let
$\sigma $
be such that, for any sentence
$\alpha $
,
$\sigma (\alpha )=A\setminus A\div \alpha $
. This is the construction used in the proof of the postulates to construction part of Theorem 10. Thus it only remains to show that
$\sigma $
is uniform. Assume that it holds for all subsets
$A'$
of A that
$\alpha \in Cn(A')$
if and only if
$\beta \in Cn(A')$
. By
$\div $
uniformity it follows that
$A\div \alpha =A\div \beta $
. Hence
$\sigma (\alpha )=A\setminus A\div \alpha =A\setminus A\div \beta =\sigma (\beta )$
.
(b) to (c) and (c) to (b)
Follows by Observation 3.
Proof of Theorem 13
Let A be a set of sentences and
$\div $
be an operator on A.
(a) to (b)
Follows by Theorems 11 and 12.
(b) to (a)
Assume now that
$\div $
satisfies success, inclusion, core-retainment, uniformity and relative closure. Let
$\sigma $
be such that, for any sentence
$\alpha $
,
$\sigma (\alpha )=A\setminus A\div \alpha $
. This is the construction used in the proof of the postulates to construction part of Theorems 10–12. Therefore, according to those proofs
$\sigma $
is a uniform sentence based smooth incision function and, for any
$\alpha \in \mathcal {L}$
,
$A\div \alpha =A\setminus \sigma (\alpha )$
.
(b) to (c) and (c) to (b)
Follows by Observation 4.
Proof of Theorem 14
Let
$\mathbf {K}$
be a belief set and
$\div $
be an operator on
$\mathbf {K}$
.
According to Observation 7 conditions (c) and (d) are equivalent. On the other hand it follows immediately from Observations 9 and 11 that conditions (a) and (b) are equivalents. Therefore, to conclude this proof it is enough to show that conditions (b) and (c) are equivalents.
(c) to (b)
Let
$\div $
be a smooth kernel contraction. Hence there exists a smooth incision function
$\sigma $
such that
$\mathbf {K}\div \alpha =\mathbf {K}\setminus \sigma ({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha )$
. Let
$\sigma '$
be such that
$\sigma '(\alpha )=\sigma ({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha )$
(for all
$\alpha $
). By Theorem 8,
$\sigma '$
is a uniform sentence based smooth incision function. Since for all
$\alpha $
it holds that
$\mathbf {K}\div \alpha =\mathbf {K}\setminus \sigma ({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha )=\mathbf {K}\setminus \sigma '(\alpha )$
, we can conclude that
$\div $
is a uniform smooth GKC.
(b) to (c)
Let
$\div $
be a uniform smooth GKC. Hence there exists a uniform sentence based smooth incision function
$\sigma $
such that
$\mathbf {K}\div \alpha =\mathbf {K}\setminus \sigma (\alpha )$
. Let
$\sigma '$
be such that
$\sigma '({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha )=\sigma (\alpha )$
(for all
$\alpha $
). By Theorem 9,
$\sigma '$
is a smooth incision function. Since for all
$\alpha $
,
$\mathbf {K}\div \alpha =\mathbf { K}\setminus \sigma (\alpha )=\mathbf {K}\setminus \sigma '({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha )$
, it holds that
$\div $
is a smooth kernel contraction.
Proof of Theorem 15
According to Observation 8 conditions (c) and (d) are equivalent. On the other hand it follows immediately from Observations 9 and 11 that conditions (a) and (b) are equivalents. Therefore, to conclude this proof it is enough to show that conditions (b) and (c) are equivalents.
(c) to (b)
Let
$\div $
be a safe contraction based on a regular and virtually connected hierarchy
$\prec $
. Hence there exists an incision function
$\sigma $
that is based on a regular and virtually connected hierarchy
$\prec $
such that
$\mathbf {K}\div \alpha =\mathbf {K}\cap Cn(\mathbf {K}\setminus \sigma ({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha ))$
. Let
$\sigma '$
be such that
$\sigma '(\alpha )=\sigma ({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha )$
(for all
$\alpha $
). By Theorem 8,
$\sigma '$
is a uniform sentence based incision function that is based on
$\prec $
and
$\mathbf {K}\div \alpha =\mathbf {K}\cap Cn(\mathbf {K}\setminus (\sigma (\alpha ))$
. Hence
$\div $
is a uniform generalized safe contraction based on a regular and virtually connected hierarchy.
(b) to (c)
Let
$\div $
be a uniform generalized safe contraction based on a regular and virtually connected hierarchy
$\prec $
. Hence there exists a uniform sentence based incision function
$\sigma $
that is based on a regular and virtually connected hierarchy
$\prec $
such that
$\mathbf {K}\div \alpha =\mathbf {K}\cap Cn(\mathbf {K}\setminus (\sigma (\alpha ))$
. Let
$\sigma '$
be such that
$\sigma '({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha )=\sigma (\alpha )$
(for all
$\alpha $
). By Theorem 9,
$\sigma '$
is an incision function that is based on
$\prec $
and
$\mathbf {K}\div \alpha =\mathbf {K}\cap Cn(\mathbf {K}\setminus (\sigma ({ \mathbf {K}}\!\!\perp \!\!\!\perp \!\!\alpha ))$
. Hence
$\div $
is a safe contraction based on a regular and virtually connected hierarchy.
Acknowledgements
We wish to thank David Makinson for his very pertinent and valuable comments on a previous version of this paper, which have contributed to a significant improvement. We also thank Hans Halvorson, the Associated Editor of RSL who handled this paper, and the anonymous reviewer for their comments which have made us considerably improve the exposition of the significance of the main contributions of this paper. This paper was partially supported by FCT-Fundação para a Ciência e a Tecnologia, Portugal through project PTDC/CCICOM/4464/2020 and by the Centro de Investigação em Matemática e Aplicações (CIMA), through the grant UIDB/04674/2020 of FCT.
