SPO-Representable Inductive Inference Operators Extending Rational Closure

Abstract

Rational closure, as introduced by Lehmann or via Pearl’s system Z, exhibits desirable characteristics of nonmonotonic inference relations. The property (RC Extension), formalizing that an inductive inference operator extends rational closure, has recently been investigated for basic defeasible entailment relations. In this article, we explore (RC Extension) for more general classes of inference relations. We semantically characterize (RC Extension) for preferential inference relations in general by a specific type of preferential models. Then we focus on operators that can be represented with strict partial orders (SPOs) on possible worlds and characterize SPO-representable inductive inference operators. We show that for SPO-representable inference operators, (RC Extension) is semantically characterized by refinements of the Z-rank relation on possible worlds. Finally, we explore several examples of inference operators satisfying (RC Extension) and their interrelationships.

1. Introduction

Research in the field of non-monotonic reasoning often deals with inferences that can be drawn from a set of given defeasible rules. The resulting inference relations are then assessed in terms of broadly accepted axiomatic properties, like system P (Kraus et al., 1990). Beyond the inference relations, the seminal papers (Lehmann, 1989; Pearl, 1990) put the role of the belief base into the focus of reasoning methods, proposing closure operations for reasoning from defeasible rule bases that have inspired many other works on non-monotonic reasoning since then. In particular, rational closure (RC) (Lehmann, 1989) (or equivalently system Z (Pearl, 1990)) is an inductive inference operator that can be characterized by a certain closure of a belief base under system P and rational monotony (RM) (Kraus et al., 1990; Makinson & Gärdenfors, 1989) and exhibit desirable properties.

Every inference relation satisfying system P and (RM) is induced by a ranked model (or equivalently by a total preorder (TPO) on worlds) (Lehmann & Magidor, 1992). An inference relation satisfying system P is called preferential and is induced by a preferential model (Kraus et al., 1990). Obviously, preferential models are more general than ranked models as they can also represent inference relations not complying with (RM).

Both system P and (RM) have their benefits and drawbacks:

System P is generally seen as a kind of gold standard which a non-monotonic inference relation should fulfill. However, inference only with the axioms of system P (p-entailment) is very skeptical because it takes all preferential models of a belief base $\mathrm{\Delta }$ into account. Therefore, system P on its own is often perceived to be too weak for drawing informative inferences.

If $A|\sim C$ , the postulate (RM) licences the entailment $A\wedge B|\sim C$ for every $B$ as long as from $A$ we cannot defeasibly entail the negation of $B$ . Therefore, because no other condition on $B$ is required, (RM) is often perceived to be too strong.

Thus, one would expect inference operators to comply with system P while possibly licensing additional conditional entailments. However, the additional entailments should be restricted to defeasible inferences and should avoid adding inferences of the form $A|{\sim }_{\mathrm{\Delta }}\mathrm{\perp }$ . Note that $A|{\sim }_{\mathrm{\Delta }}\mathrm{\perp }$ causes all models of $A$ to be completely infeasible, thus expressing that $\mathrm{\neg }A$ is not a defeasible but a strict belief. The postulate (Classic Preservation) (Casini et al., 2019) requires that the inductive inference operator licenses an entailment of the form $A|{\sim }_{\mathrm{\Delta }}\mathrm{\perp }$ only if $A|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ , that is, if it is a p-entailment.

The postulate (RC Extension) (Casini et al., 2019) restricts the closure under (RM) to the belief base $\mathrm{\Delta }$ and thus makes a difference between beliefs explicitly given in $\mathrm{\Delta }$ and implicit beliefs derived from $\mathrm{\Delta }$ by nonmonotonic entailment. This distinction between explicit and implicit beliefs perfectly fits the basic idea of inductive inference operators (Kern-Isberner et al., 2020), which map a belief base $\mathrm{\Delta }$ to a complete inference relation induced by $\mathrm{\Delta }$ . Inference relations satisfying (RM), classic preservation (CP), and (RC Extension) can be semantically characterized by ranked models that are rank preserving with respect to the Z-ranking (Casini et al., 2019).

In this article, we explore the field of inference relations involving system P respectively (RM) as limiting characterizations, and extend the work started in Casini et al. (2019) by dropping the rather strong requirement of (RM). Instead, we consider more general classes of so-called RCP inductive inference operators, that is, inductive inference operators satisfying (RC Extension) and (Classic Preservation). For RCP inductive inference operators that satisfy system P (RCP preferential inductive inference operators) we show that these are characterized by Z-rank refining preferential models, where Z-rank refining is a newly introduced adaption of rank preserving to preferential models. The intuition of Z-rank refining is that the preferential model respects and possibly refines the structure on worlds that is induced by Z-ranking functions ${\kappa }_{\mathrm{\Delta }}^z$ .

While preferential models are more general than TPOs, they are also more complex. Between the class of preferential inference relations and the class of inference relations induced by TPOs there is the class of inductive inference operators induced by strict partial orders (SPOs) on worlds. SPOs on worlds are more expressive than TPOs but less complex than preferential models: for example, for signatures of size $|\mathrm{\Sigma }|=2$ there are 75 TPOs, 219 SPOs, and 485 (non-equivalent) preferential models on the four $\mathrm{\Sigma }$ -worlds (Beierle & Haldimann, 2022; Beierle et al., 2021b, 2023). Thus, to fill the gap between TPOs and preferential models we also consider the class of RCP inductive inference operators induced by SPOs on worlds, called RCP SPO-representable inductive inference operators. We show that RCP SPO-representable inductive inference operators are characterized by Z-rank refining SPOs on worlds. Furthermore, we investigate inference relations induced by SPOs on formulas and show that such inductive inference operators satisfy RCP if they are based on Z-rank refining SPOs on formulas. Thus, our work extends (Casini et al., 2019) in different directions, in particular by providing characterization theorems for different classes of RCP inductive inference operators.

Finally, we illustrate the characterization results of this article by applying them to multiple inference operators from the literature that extend (RC); this includes system W (Komo & Beierle, 2020, 2022), some of its approximations (Haldimann & Beierle, 2023), and the closure of relevant closure (Casini et al., 2014) under system P. By applying the results of this article to these inference operators, we obtain some interesting insights into their semantic properties. To summarize, the main contributions of this article are:

A characterization theorem showing that RCP preferential inductive inference operators can be characterized by Z-rank refining preferential models.

Introduction of the class of SPO-representable inductive inference operators, which prove to be central within a map of inductive inference operators.

A characterization theorem showing that RCP SPO-representable inductive inference operators can be characterized by Z-rank refining SPOs on formulas.

Illustration of the characterization results by applying them to RCP preferential and RCP SPO-representable inductive inference operators from literature.

This article is a revised and largely extended version of our conference paper presented at the 18th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2023) (Haldimann et al., 2023b). In particular, we added full proofs for all propositions and theorems that were not part of the conference paper. Furthermore, we added Section 7 that explores different RCP inductive inference operators from literature.

After recalling preliminaries of conditional logic (Section 2) and non-monotonic reasoning (Section 3), we introduce RCP preferential and SPO representable inductive inference operators (Section 4 and 5) and prove corresponding characterizations in Section 6. In Section 7 we apply our results to examples of RCP inductive inference operators from the literature before we conclude and point out future work in Section 8.

2. Conditional Logic

A (propositional) signature is a finite set $\mathrm{\Sigma }$ of propositional variables. Assuming an underlying signature $\mathrm{\Sigma }$ , we denote the resulting propositional language by $\mathcal{L}$ . Usually, we denote elements of signatures with lowercase letters $a,b,c,\dots$ and formulas with uppercase letters $A,B,C,\dots$ . We may denote a conjunction $A\wedge B$ by $AB$ and a negation $\mathrm{\neg }A$ by $\overline{A}$ for brevity of notation. The set of interpretations over the underlying signature is denoted as $\mathrm{\Omega }$ . Interpretations are also called worlds and $\mathrm{\Omega }$ is called the universe. An interpretation $\omega \in \mathrm{\Omega }$ is a model of a formula $A\in \mathcal{L}$ if $A$ holds in $\omega$ , denoted as $\omega \models A$ . The set of models of a formula (over a signature $\mathrm{\Sigma }$ ) is denoted as $\text{ Mod}(A)=\{\omega \in \mathrm{\Omega }\mid \omega \models A\}$ or short as ${\mathrm{\Omega }}_A$ . A formula $A$ entails a formula $B$ if ${\mathrm{\Omega }}_A\subseteq {\mathrm{\Omega }}_B$ . By slight abuse of notation we sometimes interpret worlds as the corresponding complete conjunction of all elements in the signature in either positive or negated form.

A conditional $(B|A)$ connects two formulas $A,B$ and represents the rule “If $A$ then usually $B$ ”, where $A$ is called the antecedent and $B$ the consequent of the conditional. The conditional language is denoted as $(\mathcal{L}|\mathcal{L})=\{(B|A)\mid A,B\in \mathcal{L}\}$ . A finite set $\mathrm{\Delta }$ of conditionals is called a belief base.

We use a three-valued semantics of conditionals in this article (de Finetti, 1937): for a world $\omega$ a conditional $(B|A)$ is either verified by $\omega$ if $\omega \models AB$ , falsified by $\omega$ if $\omega \models A\overline{B}$ , or not applicable to $\omega$ if $\omega \models \overline{A}$ . Popular models for belief bases are ranking functions (also called ordinal conditional functions, OCFs) (Spohn, 1988) and total preorders (TPOs) on $\mathrm{\Omega }$ (Darwiche & Pearl, 1997).

An OCF $\kappa :\mathrm{\Omega }\to {\mathbb{N}}_0\cup \{\mathrm{\infty }\}$ maps worlds to a rank such that at least one world has rank 0, that is, ${\kappa }^{-1}(0)\ne \mathrm{\varnothing }$ . The intuition is that worlds with lower ranks are more plausible than worlds with higher ranks; worlds with rank $\mathrm{\infty }$ are considered infeasible. OCFs are lifted to formulas by mapping a formula $A$ to the smallest rank of a model of $A$ , or to $\mathrm{\infty }$ if $A$ has no models. An OCF $\kappa$ is a model of a conditional $(B|A)$ , denoted as $\kappa \models (B|A)$ , if $\kappa (AB)<\kappa (A\overline{B})$ ; $\kappa$ is a model of a belief base $\mathrm{\Delta }$ , denoted as $\kappa \models \mathrm{\Delta }$ , if it is a model of every conditional in $\mathrm{\Delta }$ . A belief base $\mathrm{\Delta }$ is called (strongly) consistent if there exists at least one ranking function $\kappa$ with $\kappa \models \mathrm{\Delta }$ and ${\kappa }^{-1}(\mathrm{\infty })=\mathrm{\varnothing }$ , that is, if there is at least one ranking function modeling $\mathrm{\Delta }$ that considers all worlds feasible. This notion of consistency is used in many approaches, for example, in Goldszmidt and Pearl (1996) while in, for example, Casini et al., 2019; Giordano et al., 2015 a more relaxed notion of consistency is used. The latter is characterized precisely by the notion of weak consistency introduced in Haldimann et al. (2023a) which is obtained by dropping the condition ${\kappa }^{-1}(\mathrm{\infty })=\mathrm{\varnothing }$ , that is, a belief base $\mathrm{\Delta }$ is weakly consistent if there exists at least one ranking function $\kappa$ with $\kappa \models \mathrm{\Delta }$ .

3. Defeasible Entailment

Having the ability to answer conditional questions of the form does $A$ entail $B$ ? enables an agent to draw appropriate conclusions in different situations. The set of conditional beliefs the agent can draw is formally captured by a binary relation $|\sim$ on propositional formulas with $A|\sim B$ representing that $A$ (defeasibly) entails $B$ ; this relation is called an inference or entailment relation. As we consider defeasible or non-monotonic entailment, it is possible that there are formulas $A,B,C$ with both $A|\sim B$ and $AC\text{⧸}|\sim B$ : given more specific information the agent might revoke a conclusion that she drew based on more general information.

There are different sets of properties for inference relations suggested in the literature. A preferential inference relation is an inference relation satisfying the following set of postulates called system P (Adams, 1975; Kraus et al., 1990), which is often considered as the minimal requirement for inference relations:

(REF)   Reflexivity for all $A\in \mathcal{L}$ it holds that $A|\sim A$

(LLE)   Left Logical Equivalence  $A\equiv B$ and $B|\sim C$ imply $A|\sim C$

(RW)    Right Weakening  $B\models C$ and $A|\sim B$ imply $A|\sim C$

(CM)    Cautious Monotony  $A|\sim B$ and $A|\sim C$ imply $AB|\sim C$

(CUT) $A|\sim B$ and $AB|\sim C$ imply $A|\sim C$

(OR) $A|\sim C$ and $B|\sim C$ imply $(A\vee B)|\sim C$

Beyond system P, another axiom has been proposed that seems to be desirable in general, and is also satisfied by Rational Closure (or system Z Pearl, 1990):

(RM)   Rational Monotony  $A|\sim C$ and $A\text{⧸}|\sim \overline{B}$ imply $(A\wedge B)|\sim C$

Besides ranking functions, preferential models are another kind of models for conditionals that are useful to represent preferential inference relations.

Definition 1 preferential model Kraus et al. (1990)

Let $\mathcal{M}=(S,l,\prec )$ be a triple consisting of a set $S$ of states, a function $l:S\to \mathrm{\Omega }$ mapping states to interpretations, and a SPO $\prec$ on $S$ .

For $A\in \mathcal{L}$ and $s\in S$ we denote $l(s)\models A$ by s A; and we define $\text{⟦}A{\text{⟧}}_{\mathcal{M}}=\{s\in S\mid s$ $A\}$ . We say $\mathcal{M}$ is a preferential model if for any $A\in \mathcal{L}$ and $s\in \text{⟦}A{\text{⟧}}_{\mathcal{M}}$ either $s$ is minimal in $\text{⟦}A{\text{⟧}}_{\mathcal{M}}$ or there is a $t\in \text{⟦}A{\text{⟧}}_{\mathcal{M}}$ such that $t$ is minimal in $\text{⟦}A{\text{⟧}}_{\mathcal{M}}$ and $t\prec s$ (smoothness condition).

Note that the smoothness condition is automatically satisfied for finite sets of states. A preferential model $\mathcal{M}=(S,l,\prec )$ induces an inference relation $|{\sim }_{\mathcal{M}}$ by $A|{\sim }_{\mathcal{M}}B$ iff $min(\text{⟦}A{\text{⟧}}_{\mathcal{M}},\prec )\subseteq \text{⟦}B{\text{⟧}}_{\mathcal{M}}$ .

One result from Kraus et al. (1990) states that preferential models characterize preferential entailment relations: every inference relation $|{\sim }_{\mathcal{M}}$ induced by a preferential model $\mathcal{M}$ is preferential, and for every preferential inference relation $|\sim$ there is a preferential model $\mathcal{M}$ with $|{\sim }_{\mathcal{M}}=|\sim$ . Two preferential models $\mathcal{M}$ , $\mathcal{N}$ are called equivalent if they induce the same inference relation, that is, if $|{\sim }_{\mathcal{M}}=|{\sim }_{\mathcal{N}}$ .

Inductive inference is the process of completing a given belief base to an inference relation, formally defined by the concept of inductive inference operators.

Definition 2 inductive inference operator Kern-Isberner et al., 2020

An inductive inference operator is a mapping $C:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^{}$ that maps each belief base to an inference relation such that direct inference (DI) and trivial vacuity (TV) are fulfilled, that is,

(DI) if $(B|A)\in \mathrm{\Delta }$ then $A|{\sim }_{\mathrm{\Delta }}^{}B$ , and

(TV) if $\mathrm{\Delta }=\mathrm{\varnothing }$ and $A|{\sim }_{\mathrm{\Delta }}^{}B$ then $A\models B$ .

We can define p-entailment (Kraus et al., 1990) as an inductive inference operator.

Definition 3 p-entailment

Let $\mathrm{\Delta }$ be a belief base and $A,B$ be formulas. $A$ p-entails $B$ with respect to $\mathrm{\Delta }$ , denoted as $A|{\sim }_{\mathrm{\Delta }}^{p}B$ , if $A|{\sim }_{\mathcal{M}}B$ for every preferential model $\mathcal{M}$ of $\mathrm{\Delta }$ . P-entailment is the inductive inference operator mapping each $\mathrm{\Delta }$ to $|{\sim }_{\mathrm{\Delta }}^p$ .

In the context of conditional beliefs, a conditional of the form $(\mathrm{\perp }|A)$ or an entailment $A|\sim \mathrm{\perp }$ expresses a strict belief in the sense that every $A$ -world is considered to be impossible. The following postulate (Classic Preservation) formalizes that an inference relation treats strict beliefs in the same way as p-entailment.

Postulate 1 (Classic Preservation) An inference relation $|\sim$ satisfies (Classic Preservation) (Casini et al., 2019) w.r.t. a belief base $\mathrm{\Delta }$ if for all $A\in \mathcal{L}$ , $A|\sim \mathrm{\perp }$ iff $A|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ .

An inductive inference operator satisfies (Classic Preservation) if every $\mathrm{\Delta }$ is mapped to an inference relation satisfying (Classic Preservation) w.r.t. $\mathrm{\Delta }$ .

We are now ready to formally define the first two subclasses of inductive inference operators that we will use in this article (for an overview over all classes of inductive inference operators considered here, see Figure 1 on page 16).

Figure 1.

Relationships Among the Classes of Inductive Inference Operators Considered in Sections 5 and 6. $C_1\hookrightarrow C_2$ Indicates That $C_1$ is a Proper Subclass of $C_2$ .

Definition 4 preferential inductive inference operator, basic defeasible inductive inference operator

An inductive inference operator $C$ is called a

preferential inductive inference operator if every inference relation $|{\sim }_{\mathrm{\Delta }}^{}$ in the image of $C$ satisfies system P;

basic defeasible inductive inference operator, for short BD-inductive inference operator, if every inference relation $|{\sim }_{\mathrm{\Delta }}^{}$ in the image of $C$ satisfies system P, rational monotony (RM), and (Classic Preservation).

The original definition of BD-inductive inference operator is based on the notion of basic defeasible entailment relations (Casini et al., 2019) (short BD-entailment relations) which satisfy system P and rational monotony (RM) and, additionally, direct inference (DI) and (Classic Preservation) with respect to a belief base $\mathrm{\Delta }$ .

BD-entailment relations can be characterized in many different ways. For instance, an inference relation $|{\sim }_{\mathrm{\Delta }}^{}$ is a BD-entailment relation with respect to a belief base $\mathrm{\Delta }$ iff there is a ranked model of $\mathrm{\Delta }$ inducing $|{\sim }_{\mathrm{\Delta }}^{}$ , or equivalently iff there is a rank function that is a model of $\mathrm{\Delta }$ and induces $|{\sim }_{\mathrm{\Delta }}^{}$ (Casini et al., 2019, Theorem 1). BD-entailment relations can also be characterized by ranking functions. The inference relation $|{\sim }_{\kappa }$ induced by a ranking function $\kappa$ is defined by

$$A|{\sim }_{\kappa }B\text{iff}\kappa (A)=\mathrm{\infty }\text{or}\kappa (AB)<\kappa (A\overline{B}).$$

(1)

Note that the condition $\kappa (A)=\mathrm{\infty }$ in (1) ensures that system P’s axiom (REF) is satisfied for $A\equiv \mathrm{\perp }$ . Exploiting the relationship between ranked models and ranking functions, it is easy to show that $|{\sim }_{\mathrm{\Delta }}^{}$ is a BD-entailment relation with respect to $\mathrm{\Delta }$ iff there is a ranking function $\kappa$ with $\kappa \models \mathrm{\Delta }$ that induces $|{\sim }_{\mathrm{\Delta }}^{}$ .

System Z is a BD-inductive inference operator that is defined based on the Z-partition of a belief base (Pearl, 1990). Here we use an extended version of system Z that also covers belief bases that are only weakly consistent and that was shown to be equivalent to rational closure (Lehmann, 1989) in Goldszmidt and Pearl (1990).

Definition 5 (extended) Z-partition

A conditional $(B|A)$ is tolerated by $\mathrm{\Delta }=\{(B_i|A_i)\mid i=1,\dots ,n\}$ if there exists a world $\omega \in \mathrm{\Omega }$ such that $\omega$ verifies $(B|A)$ and $\omega$ does not falsify any conditional in $\mathrm{\Delta }$ , that is, $\omega \models AB$ and $\omega \models \underset{i=1}{\overset{n}{\bigwedge }}(\overline{A_i}\vee B_i)$ .

The (extended) Z-partition $\mathit{E}\mathit{Z}\mathit{P}(\mathrm{\Delta })=({\mathrm{\Delta }}^0,\dots ,{\mathrm{\Delta }}^k,{\mathrm{\Delta }}^{\mathrm{\infty }})$ of a belief base $\mathrm{\Delta }$ is the ordered partition of $\mathrm{\Delta }$ that is constructed by letting ${\mathrm{\Delta }}^i$ be the inclusion maximal subset of $\bigcup _{j=i}^n{\mathrm{\Delta }}^j$ that is tolerated by $\bigcup _{j=i}^n{\mathrm{\Delta }}^j$ until ${\mathrm{\Delta }}^{k+1}=\mathrm{\varnothing }$ . The set ${\mathrm{\Delta }}^{\mathrm{\infty }}$ is the remaining set of conditionals that contains no conditional which is tolerated by ${\mathrm{\Delta }}^{\mathrm{\infty }}$ .

It is well-known that the construction of $\mathit{E}\mathit{Z}\mathit{P}(\mathrm{\Delta })$ is successful with ${\mathrm{\Delta }}^{\mathrm{\infty }}=\mathrm{\varnothing }$ iff $\mathrm{\Delta }$ is strongly consistent, and because the ${\mathrm{\Delta }}^i$ are chosen inclusion-maximal, the Z-partition is unique (Pearl, 1990).

Also, it holds that $\mathit{E}\mathit{Z}\mathit{P}(\mathrm{\Delta })$ has ${\mathrm{\Delta }}^0\ne \mathrm{\varnothing }$ iff $\mathrm{\top }{\text{⧸}|\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ .

Definition 6 (extended) system Z

Let $\mathrm{\Delta }$ be a belief base with $\mathit{E}\mathit{Z}\mathit{P}(\mathrm{\Delta })=({\mathrm{\Delta }}^0,\dots ,{\mathrm{\Delta }}^k,{\mathrm{\Delta }}^{\mathrm{\infty }})$ . If $\mathrm{\Delta }$ satisfies $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ , then let $A|{\sim }_{\mathrm{\Delta }}^{z}B$ for any $A,B\in \mathcal{L}$ . Otherwise, the (extended) Z-ranking function ${\kappa }_{\mathrm{\Delta }}^z$ is defined as follows. For a world $\omega \in \mathrm{\Omega }$ , if one of the conditionals in ${\mathrm{\Delta }}^{\mathrm{\infty }}$ is applicable to $\omega$ define ${\kappa }_{\mathrm{\Delta }}^z(\omega )=\mathrm{\infty }$ . Otherwise, let ${\mathrm{\Delta }}^j$ be the last partition in $\mathit{E}\mathit{Z}\mathit{P}(\mathrm{\Delta })$ that contains a conditional falsified by $\omega$ . Then let ${\kappa }_{\mathrm{\Delta }}^z(\omega )=j+1$ . If $\omega$ does not falsify any conditional in $\mathrm{\Delta }$ , then let ${\kappa }_{\mathrm{\Delta }}^z(\omega )=0$ .

(Extended) system Z maps $\mathrm{\Delta }$ to the inference relation $|{\sim }_{\mathrm{\Delta }}^z$ induced by ${\kappa }_{\mathrm{\Delta }}^z$ .

For strongly consistent belief bases the extended system Z coincides with system Z as defined in Goldszmidt and Pearl (1996); Pearl (1990).

Lemma 1

For a belief base $\mathrm{\Delta }$ with $\mathrm{\top }{\text{⧸}|\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ and a formula $A$ we have ${\kappa }_{\mathrm{\Delta }}^z(A)=\mathrm{\infty }$ iff $A|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ .

Proof.

If $A|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ then $A|{\sim }_{\mathrm{\Delta }}^z\mathrm{\perp }$ because system Z captures p-entailment. Following Lehmann and Magidor (1992, Lemma 30), it is $A|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ only if $A|{\sim }_{\mathrm{\Delta }}^z\mathrm{\perp }$ . By looking at (1) we see that $A|{\sim }_{\mathrm{\Delta }}^z\mathrm{\perp }$ iff ${\kappa }_{\mathrm{\Delta }}^z(A)=\mathrm{\infty }$ .

4. Extending Rational Closure

In Casini et al. (2019), the authors explored BD-inductive inference relations that extend the rational closure (i.e. the system Z inference relation) of a belief base. This property of a belief base is formally defined by (RC Extension).

Postulate 2 (RC Extension) An inference relation $|\sim$ satisfies (RC Extension) (Casini et al., 2019) with respect to a belief base $\mathrm{\Delta }$ if for all $A,B\in \mathcal{L}$ , $A|{\sim }_{\mathrm{\Delta }}^{z}B$ implies $A|\sim B$ .

An inductive inference operator satisfies (RC Extension) if every $\mathrm{\Delta }$ is mapped to an inference relation satisfying (RC Extension) with respect to $\mathrm{\Delta }$ .

This formulation of (RC Extension) uses the fact that rational closure and system Z coincide. In Casini et al. (2019) the BD-inductive inference relations satisfying (RC Extension) are called rational defeasible entailment relations and are characterized in different ways, among them the following: an inference relation is a rational defeasible entailment relation (with respect to a belief base $\mathrm{\Delta }$ ) iff it is induced by some base rank preserving ranked model of $\mathrm{\Delta }$ , or equivalently iff it is induced by some base rank preserving rank function that is a model of $\mathrm{\Delta }$ .

In this article we apply (RC Extension) to inductive inference operators in general.

Definition 7 RCP inductive inference operator

An RCP inductive inference operator is an inductive inference operator satisfying (RC Extension) and (Classic Preservation).

As BD-inductive inference operators satisfy (Classic Preservation) by definition, BD-inductive inference operators satisfying (RC Extension) are RCP.

Similar to the results in Casini et al. (2019) we can provide model-based characterizations of RCP inductive inference operators. For preferential inference operators we identify the following property which we will show to characterize RCP preferential inductive inference operators.

Definition 8 Z-rank refining

A preferential model $\mathcal{M}=(S,l,\prec )$ is called Z-rank refining (with respect to a belief base $\mathrm{\Delta }$ ) if $l(S)=\{\omega \in \mathrm{\Omega }\mid {\kappa }_{\mathrm{\Delta }}^z(\omega )<\mathrm{\infty }\}$ and additionally ${\kappa }_{\mathrm{\Delta }}^z(\omega )<{\kappa }_{\mathrm{\Delta }}^z({\omega }^{\prime })$ implies that for every $s^{\prime }\in l^{-1}({\omega }^{\prime })$ there is an $s\in l^{-1}(\omega )$ s.t. $s\prec s^{\prime }$ for any $\omega ,{\omega }^{\prime }\in \mathrm{\Omega }$ . A preferential model for $\mathrm{\Delta }$ with $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ is said to be Z-rank refining if and only if $S=\mathrm{\varnothing }$ .

Building on the result from Kraus et al. (1990) that preferential inference relations are characterized by preferential models, we can show that RCP preferential inductive inference operators are characterized by Z-rank refining preferential models. For every inference relation satisfying (Classic Preservation) and (RC Extension) there is a Z-rank refining preferential model inducing this inference relation. In the other direction, every Z-rank refining preferential model induces an inference relation satisfying (Classic Preservation) and (RC Extension).

Theorem 1

(1.) If $|\sim$ is a preferential inference relation satisfying (Classic Preservation) and (RC Extension) w.r.t. a belief base $\mathrm{\Delta }$ , then every preferential model inducing $|\sim$ is Z-rank refining with respect to $\mathrm{\Delta }$ .

(2.) If a preferential model $\mathcal{M}=(S,l,\prec )$ is Z-rank refining with respect to a belief base $\mathrm{\Delta }$ , then the inference relation $|{\sim }_{\mathcal{M}}$ induced by it satisfies (Classic Preservation) and (RC Extension) with respect to $\mathrm{\Delta }$ .

Proof.

Ad (1.): Let $|\sim$ be a preferential inference relation satisfying (Classic Preservation) and (RC Extension) w.r.t. a belief base $\mathrm{\Delta }$ , and let $\mathcal{M}=(S,l,\prec )$ be a preferential model inducing $|\sim$ . For $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ the proposition can be easily verified. For the remainder of the proof assume that $\mathrm{\top }{\text{⧸}|\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ . It holds that ${\kappa }_{\mathrm{\Delta }}^z(\omega )=\mathrm{\infty }$ iff $\omega |{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ . Because $|\sim$ satisfies (Classic Preservation), this is the case iff $\omega |\sim \mathrm{\perp }$ . This happens iff $\omega \notin l(S)$ . Therefore, $l(S)=\{\omega \in \mathrm{\Omega }\mid {\kappa }_{\mathrm{\Delta }}^z(\omega )<\mathrm{\infty }\}$ .

Let $\omega ,{\omega }^{\prime }\in \mathrm{\Omega }$ with ${\kappa }_{\mathrm{\Delta }}^z(\omega )<{\kappa }_{\mathrm{\Delta }}^z({\omega }^{\prime })$ . Then $\omega \vee {\omega }^{\prime }|{\sim }_{\mathrm{\Delta }}^z\omega$ . Because $|\sim$ satisfies (RC Extension), we have $\omega \vee {\omega }^{\prime }|\sim \omega$ . It must hold that $min(\text{⟦}\omega \vee {\omega }^{\prime }{\text{⟧}}_{\mathcal{M}},\prec )\subseteq \text{⟦}\omega {\text{⟧}}_{\mathcal{M}}$ , that is, $min(l^{-1}(\omega )\cup l^{-1}({\omega }^{\prime }),\prec )\subseteq l^{-1}(\omega )$ . The states in $l^{-1}({\omega }^{\prime })$ cannot be minimal in $l^{-1}(\omega )\cup l^{-1}({\omega }^{\prime })$ . Therefore, for every $s^{\prime }\in l^{-1}({\omega }^{\prime })$ there is an $s\in l^{-1}(\omega )$ with $s\prec s^{\prime }$ .

Ad (2.): Let $\mathcal{M}=(S,l,\prec )$ be Z-rank refining with respect to $\mathrm{\Delta }$ . For $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ we have $S=\mathrm{\varnothing }$ , and the proposition can be easily verified. Assume for the remainder of the proof that $\mathrm{\top }{\text{⧸}|\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ .

For $F\in \mathcal{L}$ we have that $F|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ iff ${\kappa }_{\mathrm{\Delta }}^z(F)=\mathrm{\infty }$ , that is, iff ${\kappa }_{\mathrm{\Delta }}^z(\omega )=\mathrm{\infty }$ for all $\omega \in {\mathrm{\Omega }}_F$ . As $\mathcal{M}$ is Z-rank refining, this happens iff $\text{⟦}F{\text{⟧}}_{\mathcal{M}}=\mathrm{\varnothing }$ which is equivalent to $F|{\sim }_{\mathcal{M}}\mathrm{\perp }$ . Therefore, $|{\sim }_{\mathcal{M}}$ satisfies (Classic Preservation) with respect to $\mathrm{\Delta }$ .

Let $A,B\in \mathcal{L}$ with $A|{\sim }_{\mathrm{\Delta }}^{z}B$ . For $\text{⟦}A{\text{⟧}}_{\mathcal{M}}=\mathrm{\varnothing }$ we have $A|{\sim }_{\mathcal{M}}X$ for any formula $X$ , in this case the proposition holds. Now assume that $\text{⟦}A{\text{⟧}}_{\mathcal{M}}\ne \mathrm{\varnothing }$ . Choose $s_A\in min(\text{⟦}A{\text{⟧}}_{\mathcal{M}},\prec )$ arbitrarily. We have to show that ${\omega }_A=l(s_A)$ satisfies ${\omega }_A\models B$ . Towards a contradiction assume that ${\omega }_A\models \overline{B}$ . Then we have that ${\omega }_A\models A\overline{B}$ . Because $A|{\sim }_{\mathrm{\Delta }}^{z}B$ there must be an ${\omega }^{\prime }\in {\mathrm{\Omega }}_{AB}$ with ${\kappa }_{\mathrm{\Delta }}^z({\omega }^{\prime })<{\kappa }_{\mathrm{\Delta }}^z(\omega )$ . As $\mathcal{M}$ is Z-rank refining, there has to be an $s^{\prime }\in l^{-1}({\omega }^{\prime })$ with $s^{\prime }\prec s_A$ . Because ${\omega }^{\prime }\models AB$ we have $s^{\prime }\in \text{⟦}A{\text{⟧}}_{\mathcal{M}}$ . This contradicts the minimality of $s_A$ . Hence, ${\omega }_A=l(s_A)$ satisfies ${\omega }_A\models B$ . Because $s_A$ was chosen arbitrarily we have $A|{\sim }_{\mathcal{M}}B$ , and thus $|{\sim }_{\mathcal{M}}$ satisfies (RC Extension) with respect to $\mathrm{\Delta }$ .

From Theorem 1 we get the following characterization of RCP preferential inductive inference operators.

Theorem 2 RCP preferential

An inductive inference operator is RCP iff it maps each belief base $\mathrm{\Delta }$ to an inference relation that is induced by a preferential model that is Z-rank refining with respect to $\mathrm{\Delta }$ .

The proof of Theorem 2 is a direct consequence of Theorem 1.

5. Entailment Based on SPOs

Preferential models are not the only structures that can model belief bases and entail an inference relation. Sometimes it is sufficient to consider a SPO, that is, a transitive and irreflexive binary relation, on the possible worlds to induce an inference relation. For example system W (Komo & Beierle, 2022) is an inductive inference operator defined based on SPOs on worlds.

Note that we allow an SPO $\prec$ to order only a subset ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ of all worlds in $\mathrm{\Omega }$ . This supports expressing beliefs of the form $\overline{A}|\sim \mathrm{\perp }$ , that is, $A$ strictly holds, by choosing ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\subseteq \text{Mod}(A)$ . The worlds in ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ are called feasible.

Definition 9 SPO on worlds

An SPO on worlds (over $\mathrm{\Sigma }$ ) is an SPO $\prec$ on a set ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\subseteq \mathrm{\Omega }$ of feasible worlds, denoted as $\mathit{f}\mathit{e}\mathit{a}\mathit{s}(\prec )={\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . A full SPO on worlds $\prec$ is an SPO on worlds s.t. $\mathit{f}\mathit{e}\mathit{a}\mathit{s}(\prec )=\mathrm{\Omega }$ , that is, if all possible worlds are feasible.

An SPO on worlds $\prec$ on $\mathrm{\Omega }$ models a conditional $(B|A)$ , denoted as $\prec \models (B|A)$ , if for any feasible ${\omega }^{\prime }\in {\mathrm{\Omega }}_{A\overline{B}}$ there is a feasible $\omega \in {\mathrm{\Omega }}_{AB}$ with $\omega \prec {\omega }^{\prime }$ . We say $\prec$ models a belief base $\mathrm{\Delta }$ if $\prec$ models every conditional in $\mathrm{\Delta }$ , in this case $\prec$ is also called an SPO model of $\mathrm{\Delta }$ .

The inference relation $|{\sim }_{\prec }$ induced by an SPO on worlds $\prec$ is defined by

$$A|{\sim }_{\prec }B\text{iff}\prec \models (B|A).$$

(2)

The SPOs on worlds are defined on a subset of $\mathrm{\Omega }$ to allow modeling belief bases that force some worlds to be completely implausible. If we consider only strongly consistent belief bases we only need full SPOs on worlds. Lemma 2

$\mathrm{\Delta }$ has a full SPO model iff it is strongly consistent.

Proof.

If a belief base $\mathrm{\Delta }$ is strongly consistent then there is a ranking function $\kappa$ with ${\kappa }^{-1}(\mathrm{\infty })=\mathrm{\varnothing }$ and $\kappa \models \mathrm{\Delta }$ . The SPO on worlds $\prec$ induced by $\omega \prec {\omega }^{\prime }$ iff $\kappa (\omega )<\kappa ({\omega }^{\prime })$ over ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathrm{\Omega }$ is a full SPO model of $\mathrm{\Delta }$ .

If a belief base $\mathrm{\Delta }$ has a full SPO model $\prec$ of $\mathrm{\Delta }$ we can define a ranking function $\kappa$ as follows. Let ${\mathrm{\Omega }}^0=min(\mathrm{\Omega },\prec )$ . Then let ${\mathrm{\Omega }}^i=min(\mathrm{\Omega }\setminus {\mathrm{\Omega }}^0\setminus \cdots \setminus {\mathrm{\Omega }}^{i-1})$ until ${\mathrm{\Omega }}^{k+1}=\mathrm{\varnothing }$ . Define $\kappa (\omega )=i$ for $\omega \in {\mathrm{\Omega }}^i$ for $i=0,\dots ,k$ . It holds that $\omega \prec {\omega }^{\prime }$ entails $\kappa (\omega )<\kappa ({\omega }^{\prime })$ . As $\prec$ is a full SPO on worlds without infeasible worlds we have that $\prec \models (B|A)$ implies $\kappa \models (B|A)$ for $(B|A)\in \mathrm{\Delta }$ . Therefore, $\kappa \models \mathrm{\Delta }$ and $\mathrm{\Delta }$ is strongly consistent.

Example 1

Let $\mathrm{\Sigma }=\{a,b\}$ and let $\prec$ be the full SPO on worlds defined by $\prec =\{(\overline{a}\overline{b},a\overline{b}),(a\overline{b},ab),(\overline{a}\overline{b},\overline{a}b),(\overline{a}b,ab),(\overline{a}\overline{b},ab)\}$ . Then we have, for example, $\mathrm{\top }|{\sim }_{\prec }\overline{a}$ and $a\vee b|{\sim }_{\prec }\overline{a}\vee \overline{b}$ .

Equation (2) enables us to introduce a new class of inductive inference operators. Definition 10 SPO-representable inductive inference operator

An inference relation $|\sim$ is SPO-representable if there is an SPO on worlds inducing $|\sim$ .

An SPO-representable inductive inference operator is an inductive inference operator $C:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^{}$ s.t. every $|{\sim }_{\mathrm{\Delta }}^{}$ in the image of $C$ is an SPO-representable inference relation.

An SPO-representable inductive inference operator can alternatively be written as a mapping $C^{\mathit{s}\mathit{p}\mathit{o}}:\mathrm{\Delta }\mapsto {\prec }_{\mathrm{\Delta }}$ that maps each belief base to an SPO on worlds ${\prec }_{\mathrm{\Delta }}$ . The induced inference relation $|{\sim }_{\mathrm{\Delta }}^{}$ is obtained from ${\prec }_{\mathrm{\Delta }}$ as in (2). Then (DI) and (TV) amount to ${\prec }_{\mathrm{\Delta }}\models \mathrm{\Delta }$ and ${\prec }_{\mathrm{\varnothing }}=\mathrm{\varnothing }$ .

For every SPO on worlds, there is an equivalent preferential model on the respective subset of worlds.

Proposition 1

Let $\prec$ be an SPO on worlds with ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathit{f}\mathit{e}\mathit{a}\mathit{s}(\prec )$ . The preferential model $\mathcal{M}=({\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}},\mathrm{id},\prec )$ induces the inference relation $|{\sim }_{\prec }$ .

Proof.

Let $A,B\in \mathcal{L}$ . We have $A|{\sim }_{\mathcal{M}}B$ iff $min(\text{⟦}A{\text{⟧}}_{\mathcal{M}},\prec )\subseteq \text{⟦}B{\text{⟧}}_{\mathcal{M}}$ , the latter being equivalent to $min({\mathrm{\Omega }}_A\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}},\prec )\subseteq {\mathrm{\Omega }}_B\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . For ${\mathrm{\Omega }}_A\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathrm{\varnothing }$ , we have both $A|{\sim }_{\prec }B$ and $A|{\sim }_{\mathcal{M}}B$ ; the lemma holds. For the remainder of the proof assume ${\mathrm{\Omega }}_A\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\ne \mathrm{\varnothing }$ .

If $A|{\sim }_{\prec }B$ , then for every ${\omega }^{\prime }\in {\mathrm{\Omega }}_{A\overline{B}}\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ there is an $\omega \in {\mathrm{\Omega }}_{AB}\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ such that $\omega \prec {\omega }^{\prime }$ . Therefore, a minimal feasible model of $A$ cannot be a feasible model of $\overline{B}$ and is hence a model of $B$ . Thus, $A|{\sim }_{\mathcal{M}}B$ .

If $A|{\sim }_{\mathcal{M}}B$ , then any ${\omega }^{\prime }\in {\mathrm{\Omega }}_{A\overline{B}}\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ is not minimal in ${\mathrm{\Omega }}_A\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . Using the smoothness condition, there must be a minimal $\omega \in {\mathrm{\Omega }}_A\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ with $\omega \prec {\omega }^{\prime }$ . The world $\omega$ is a feasible model of $A$ and $B$ . Therefore $A|{\sim }_{\prec }B$ .

Therefore, every SPO-representable inference relation is a preferential inference relation and every SPO-representable inductive inference operator is a preferential inductive inference operator. This implies that every SPO-representable inductive inference operator $C$ extends p-entailment, that is, for a belief base $\mathrm{\Delta }$ , and formulas $A,B$ we have that $A|{\sim }_{\mathrm{\Delta }}^{p}B$ implies $A|{\sim }_{\mathrm{\Delta }}^{C}B$ .

Because not every preferential inference relation is induced by an SPO on worlds, the inference relations induced by SPOs on worlds form a proper subclass of all preferential inference relations.

Lemma 3

There are preferential inference relations that are not SPO-representable.

Proof.

Consider the inference relation $|{\sim }_{\mathcal{M}}$ induced by the preferential model $\mathcal{M}=(S,l,<)$ with $S=\{1,2,3,4\}$ , $<=\{(3,1),(4,2)\}$ , and $l:1\mapsto ab,2\mapsto ab,3\mapsto a\overline{b},4\mapsto \overline{a}b$ . Towards a contradiction, assume that $|{\sim }_{\mathcal{M}}$ is induced by an SPO on worlds $\prec$ . We observe that $\omega |{\sim }_{\mathcal{M}}\mathrm{\perp }$ holds exactly for the world  $\omega =\overline{a}\overline{b}$ , therefore ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{ab,a\overline{b},\overline{a}b\}$ must be the set of feasible worlds for $\prec$ . By checking that $a\overline{b}\vee \overline{a}b{\text{⧸}|\sim }_{\mathcal{M}}a\overline{b}$ and $a\overline{b}\vee \overline{a}b{\text{⧸}|\sim }_{\mathcal{M}}\overline{a}b$ we can see that $a\overline{b}$ and $\overline{a}b$ must be incomparable in $\prec$ . Similarly, we can conclude that $a\overline{b}$ and $ab$ as well as $\overline{a}b$ and $ab$ must be incomparable in $\prec$ . Therefore, $\prec$ must be the empty SPO over ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . But $|{\sim }_{\mathcal{M}}$ allows for the non-trivial inference $\mathrm{\top }|{\sim }_{\mathcal{M}}a\overline{b}\vee \overline{a}b$ which contradicts that $|{\sim }_{\mathcal{M}}$ is induced by an empty SPO on worlds.

BD-inference relations are a subclass of SPO-representable inference relations. The reverse is not true in general because there are SPO-representable inference relations that are not BD-inference relations.

Proposition 2

Every basic defeasible inference relation is an SPO-representable inference relation.

Proof.

A ranked interpretation $\mathcal{R}$ is a ranking function satisfying the following convexity property: For every $i\in \mathcal{N}$ with ${\mathcal{R}}^{-1}(i)\ne \mathrm{\varnothing }$ , and $0\le j<i$ , it holds that ${\mathcal{R}}^{-1}(j)\ne \mathrm{\varnothing }$ .

For every basic defeasible inference relation $|\sim$ there is a ranked model $\mathcal{R}$ inducing this inference relation according to Casini et al. (2019, Theorem 1). $\mathcal{R}$ induces an ordering ${\prec }_{\mathcal{R}}$ over ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{\omega \in \mathrm{\Omega }\mid \mathcal{R}(\omega )<\mathrm{\infty }\}$ by $\omega {\prec }_{\mathcal{R}}{\omega }^{\prime }$ iff $\mathcal{R}(\omega )<\mathcal{R}({\omega }^{\prime })$ . This ordering ${\prec }_{\mathcal{R}}$ is an SPO on worlds inducing $|\sim$ .

Lemma 4

There are inference relations that are SPO-representable but not basic defeasible.

Proof.

Let $\prec$ be the full SPO on worlds over $\mathrm{\Sigma }=\{a,b\}$ defined by $\prec =\{(ab,a\overline{b}),(ab,\overline{a}\overline{b}),(\overline{a}b,\overline{a}\overline{b}),(a\overline{b},\overline{a}\overline{b})\}$ .

The inference relation $|{\sim }_{\prec }$ induced by $\prec$ is (obviously) SPO-representable but it violates (RM): for $A=\mathrm{\top },B=\overline{a}\vee \overline{b},C=b$ we have $A|{\sim }_{\prec }C$ and $A{\text{⧸}|\sim }_{\prec }\overline{B}$ but not $AB|{\sim }_{\prec }C$ . Therefore, $|{\sim }_{\prec }$ is not a basic defeasible inference relation.

Now we present a property that characterizes SPO-representable inference relations. The following Proposition 3 is based on the representation result for injective preferential models in Freund (1993, Theorem 4.13) and the observation that injective preferential models are equivalent to SPOs on worlds for our setting of a finite logical language. An injective preferential model is a preferential model $\mathcal{M}=(S,l,\prec )$ such that $l$ is injective.

Proposition 3

An inference relation $|\sim$ is SPO-representable iff it is preferential and satisfies that, for any $A,B,D\in \mathcal{L}$ and $C_{|\sim }(X):=\{Y\in \mathcal{L}\mid X|\sim Y\}$ ,

$$A\vee B|\sim D\text{implies}(C_{|\sim }(A)\cup C_{|\sim }(B))\models D.$$

(3)

Proof.

We first show that $|\sim$ is SPO-representable iff it is representable by an injective model.

For direction $\Leftarrow$ , assume that $|\sim$ is SPO-representable, that is, there is an SPO on worlds $\prec$ such that $|\sim =|{\sim }_{\prec }$ . According to Proposition 1, $\mathcal{M}=({\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}},\mathrm{id},\prec )$ is an injective model inducing the same inference relation. For direction $\Rightarrow$ , assume that there is an injective model $\mathcal{M}=(S,l,\prec )$ inducing $|\sim$ . As $l$ is injective, we can obtain an equivalent model ${\mathcal{M}}^{\prime }=(S^{\prime },\mathrm{id},{\prec }^{\prime })$ by replacing every state $s\in S$ by $l(s)$ and defining ${\prec }^{\prime }$ by $\omega {\prec }^{\prime }{\omega }^{\prime }$ iff $l^{-1}(\omega )\prec l^{-1}({\omega }^{\prime })$ . We have that $S^{\prime }\subseteq \mathrm{\Omega }$ , meaning that ${\prec }^{\prime }$ is an SPO on worlds over ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=S^{\prime }$ inducing $|\sim$ .

Applying Freund (1993, Theorem 4.13) yields that $|\sim$ is SPO-representable iff it is a preferential inference relation satisfying (3).

Requiring the function $l$ in a preferential model $(S,l,\prec )$ to be injective means that for any world there is at most one state mapping to it. This allows to identify each state $s\in S$ with the world $l(s)\in l(S)$ . By considering the set of feasible worlds ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=l(S)$ we can see that an injective preferential model is equivalent to an SPO on the set ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\subseteq \mathrm{\Omega }$ .

Example 2

Consider the inference relation $|{\sim }_{\mathcal{M}}$ from the proof of Lemma 3. We can verify that this inference relation violates the condition (3) for $A=a$ , $B=b$ , and $D=a\overline{b}\vee \overline{a}b$ . It is $A\vee B|{\sim }_{\mathcal{M}}D$ and $C_{|{\sim }_{\mathcal{M}}}(A)=\mathrm{Cn}(A)$ and $C_{|{\sim }_{\mathcal{M}}}(B)=\mathrm{Cn}(B)$ and therefore $C_{|{\sim }_{\mathcal{M}}}(A)\cup C_{|{\sim }_{\mathcal{M}}}(B)⊭D$ .

To obtain a model of a belief base, instead of considering an SPO on worlds we could also consider an SPO on formulas. To support expression of strict beliefs, the SPO may order only a subset ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ of all formulas in $\mathcal{L}$ ; the formulas in ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ are called feasible. If $\mathrm{\neg }A\notin {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ then it is strictly believed that $A$ holds.

Definition 11 SPO on formulas

An SPO on formulas is an SPO $⋖$ on a set ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ of feasible formulas that satisfies

syntax independence, that is, for $A,B,C,D\in \mathcal{L}$ with $A\equiv C$ and $B\equiv D$ it holds that

$A⋖B$ iff $C⋖D$ and $A\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ iff $C\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$

plausibility preservation, that is, for $E,F\in \mathcal{L}$ with $E\models F$ it holds that

$E\text{⧸}⋖F$ and $E\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ implies $F\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ .

The set of feasible formulas of an SPO on formulas is denoted as $\mathit{f}\mathit{e}\mathit{a}\mathit{s}(⋖)={\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . An SPO on formulas $⋖$ is a full SPO on formulas if $\mathit{f}\mathit{e}\mathit{a}\mathit{s}(⋖)=\mathcal{L}\setminus \{\mathrm{\perp }\}$ , that is, if all consistent formulas are feasible. An SPO on formulas $⋖$ models a conditional $(B|A)$ , denoted as $⋖\models (B|A)$ , if $A\overline{B}$ is not feasible or if $AB⋖A\overline{B}$ . We say $⋖$ models a belief base $\mathrm{\Delta }$ if $⋖$ models every conditional in $\mathrm{\Delta }$ .

Thus, to rule out models that are too obscure, an SPO on formulas requires that equivalent formulas have the same position in the SPO and that the logical entailments of a formula $F$ may not be considered less plausible than $F$ itself.

Analogously to $|{\sim }_{\prec }$ in Equation (2), the inference relation $|{\sim }_{⋖}$ induced by a SPO on formulas $⋖$ is defined by

$$A|{\sim }_{⋖}B\text{iff}⋖\models (B|A).$$

(4)

Example 3

Let $⋖$ be the full SPO on formulas defined by $A⋖B$ if $A\equiv a\overline{b}\vee \overline{a}b$ and $B\equiv ab$ . We have $a\vee b|{\sim }_{⋖}\overline{a}\vee \overline{b}$ .

An SPO on worlds induces an equivalent SPO on formulas.

Definition 12 SPO on formulas induced by an SPO on worlds

Let $\prec$ be an SPO on worlds. The SPO on formulas ${\prec }_{\mathcal{L}}$ over ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{A\in \mathcal{L}\mid {\mathrm{\Omega }}_A\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\ne \mathrm{\varnothing }\}$ induced by $\prec$ is defined by, for any formulas $A,B\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ ,

$$\begin{array}{rl}A{\prec }_{\mathcal{L}}B\text{iff}& \text{for every feasible }{\omega }^{\prime }\in {\mathrm{\Omega }}_B\\ & \text{there is a feasible }\omega \in {\mathrm{\Omega }}_A\text{ such that }\omega \prec {\omega }^{\prime }.\end{array}$$

(5)

Proposition 4

Let $\prec$ be an SPO on worlds and ${\prec }_{\mathcal{L}}$ the SPO on formulas induced by $\prec$ . For $A,B\in \mathcal{L}$ we have that $\prec \models (B|A)$ iff ${\prec }_{\mathcal{L}}\models (B|A)$ .

Proof.

Let ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathit{f}\mathit{e}\mathit{a}\mathit{s}(\prec )$ . For ${\mathrm{\Omega }}_{AB}\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\ne \mathrm{\varnothing }$ and ${\mathrm{\Omega }}_{A\overline{B}}\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\ne \mathrm{\varnothing }$ the definitions of $\prec \models (B|A)$ (Definition 9) and ${\prec }_{\mathcal{L}}\models (B|A)$ (Definitions 11 and 12) coincide.

For ${\mathrm{\Omega }}_{A\overline{B}}\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathrm{\varnothing }$ we have both $\prec \models (B|A)$ and ${\prec }_{\mathcal{L}}\models (B|A)$ . For ${\mathrm{\Omega }}_{AB}\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathrm{\varnothing }$ and ${\mathrm{\Omega }}_{A\overline{B}}\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\ne \mathrm{\varnothing }$ we have $\prec ⊭(B|A)$ and ${\prec }_{\mathcal{L}}⊭(B|A)$ .

In all cases we have $\prec \models (B|A)$ iff ${\prec }_{\mathcal{L}}\models (B|A)$ .

With Proposition 4 and (2) and (4) we can see that $A|{\sim }_{\prec }B$ iff $A|{\sim }_{{\prec }_{\mathcal{L}}}B$ . This entails that for every SPO on worlds $\prec$ there is an SPO on formulas $⋖$ that induces the same inference relation. Lemma 5 states that the reverse is not true.

Lemma 5

There are SPOs on formulas $⋖$ that induce an inference relation that is not SPO-representable.

Proof.

Consider the SPO on formulas $⋖$ with ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{F\in \mathcal{L}\mid F⊭\overline{a}\overline{b}\}$ and

$A⋖B$ iff $(a\overline{b}\vee \overline{a}b\models A$ and $(B\equiv ab$ or $B\equiv ab\vee \overline{a}\overline{b}))$ .

Towards a contradiction, let us assume that there is an SPO on worlds $\prec$ for $|{\sim }_{⋖}$ . We observe that $\omega |{\sim }_{\mathcal{M}}\mathrm{\perp }$ holds exactly for the world $\omega =\overline{a}\overline{b}$ , therefore ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{ab,a\overline{b},\overline{a}b\}$ must be the set of feasible worlds for $\prec$ . By checking that $a\overline{b}\vee \overline{a}b{\text{⧸}|\sim }_{⋖}a\overline{b}$ and $a\overline{b}\vee \overline{a}b{\text{⧸}|\sim }_{⋖}\overline{a}b$ we can see that $a\overline{b}$ and $\overline{a}b$ must be incomparable in $\prec$ . Similarly, we can conclude that $a\overline{b}$ and $ab$ as well as $\overline{a}b$ and $ab$ must be incomparable in $\prec$ . Therefore, $\prec$ must be the empty SPO over ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . But $|{\sim }_{⋖}$ allows for the non-trivial inference $\mathrm{\top }|{\sim }_{⋖}a\overline{b}\vee \overline{a}b$ which contradicts that $|{\sim }_{⋖}$ is induced by an empty SPO on worlds.

Let us summarize the relations between the class of SPO-representable inductive inference operators and other classes of inference operators. Every BD-inductive inference operator is SPO-representable, and every SPO-representable inductive inference operator is preferential and can be induced by an SPO on formulas. The reverse of none of these statements is true. An overview over these classes of inference operators is given in Figure 1.

6. RCP SPO-Representable Inference

After introducing SPO-representable inductive inference operators in the previous section, in this section we consider RCP SPO-representable inductive inference operators, that is, SPO-representable inductive inference operators that satisfy (RC Extension) and (Classic Preservation).

Just as Z-rank refining preferential models characterize RCP preferential inductive inference operators, we can characterize RCP SPO-representable inductive inference operators with Z-rank refining SPOs on worlds.

Definition 13 Z-rank refining

An SPO on worlds $\prec$ with ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathit{f}\mathit{e}\mathit{a}\mathit{s}(\prec )$ is called Z-rank refining (with respect to a belief base $\mathrm{\Delta }$ ) if ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{\omega \in \mathrm{\Omega }\mid {\kappa }_{\mathrm{\Delta }}^z(\omega )<\mathrm{\infty }\}$ and additionally ${\kappa }_{\mathrm{\Delta }}^z(\omega )<{\kappa }_{\mathrm{\Delta }}^z({\omega }^{\prime })$ implies $\omega \prec {\omega }^{\prime }$ for any $\omega ,{\omega }^{\prime }\in {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . For $\mathrm{\Delta }$ with $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ the only Z-rank refining SPO on worlds is defined to be $\prec$ with $\mathit{f}\mathit{e}\mathit{a}\mathit{s}(\prec )=\mathrm{\varnothing }$ .

While Definition 13 for Z-rank refining SPOs on worlds deviates from Definition 8 for Z-rank refining preferential models, they both formulate the same idea that the structure on worlds induced by the Z-ranking function ${\kappa }_{\mathrm{\Delta }}^z$ is preserved and possibly refined.

Theorem 3

(1.) Let $|\sim$ be an inference relation. If $|\sim$ satisfies (Classic Preservation) and (RC Extension) w.r.t. $\mathrm{\Delta }$ then every SPO on worlds inducing $|\sim$ is Z-rank refining w.r.t. $\mathrm{\Delta }$ .  (2.) Let $\prec$ be an SPO on worlds and $|{\sim }_{\prec }$ be the inference relation induced by it. If $\prec$ is Z-rank refining then $|{\sim }_{\prec }$ satisfies (Classic Preservation) and (RC Extension).

Proof.

Ad (1.): Let $|\sim$ be an inference relation satisfying (Classic Preservation) and (RC Extension) w.r.t. $\mathrm{\Delta }$ and $\prec$ be an SPO on worlds inducing $|\sim$ . For $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ the proposition can be easily verified. Assume for the remainder of the proof that $\mathrm{\top }{\text{⧸}|\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ . Let ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathit{f}\mathit{e}\mathit{a}\mathit{s}(\prec )$ . It holds that ${\kappa }_{\mathrm{\Delta }}^z(\omega )=\mathrm{\infty }$ iff $\omega |{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ . Because $|\sim$ satisfies (Classic Preservation), this is the case iff $\omega |\sim \mathrm{\perp }$ . This happens iff $\omega \notin {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ , that is, ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{\omega \in \mathrm{\Omega }\mid {\kappa }_{\mathrm{\Delta }}^z(\omega )<\mathrm{\infty }\}$ .

Let $\omega ,{\omega }^{\prime }\in {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ such that ${\kappa }^z(\omega )<{\kappa }^z({\omega }^{\prime })$ . In this case $\omega \vee {\omega }^{\prime }|{\sim }_{\mathrm{\Delta }}^z\omega$ . As $|\sim$ satisfies (RC Extension), we have $\omega \vee {\omega }^{\prime }|\sim \omega$ . As $\omega$ and ${\omega }^{\prime }$ are feasible, this entails $\omega \prec {\omega }^{\prime }$ .

Ad (2.): Let $\prec$ be a Z-rank refining SPO on worlds and $|{\sim }_{\prec }$ be the inference relation induced by it. For $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ the proposition can be easily verified. Assume for the remainder of the proof that $\mathrm{\top }{\text{⧸}|\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ .

For $F\in \mathcal{L}$ we have that $F|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ iff ${\kappa }_{\mathrm{\Delta }}^z(F)=\mathrm{\infty }$ , that is, iff ${\kappa }_{\mathrm{\Delta }}^z(\omega )=\mathrm{\infty }$ for all $\omega \in {\mathrm{\Omega }}_F$ . As $\prec$ is Z-rank refining, this happens iff ${\mathrm{\Omega }}_F\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathrm{\varnothing }$ which is equivalent to $F|{\sim }_{\prec }\mathrm{\perp }$ . Therefore, $|{\sim }_{\prec }$ satisfies (Classic Preservation) w.r.t. $\mathrm{\Delta }$ .

Let $A,B\in \mathcal{L}$ such that $A|{\sim }_{\mathrm{\Delta }}^{z}B$ . If ${\kappa }_{\mathrm{\Delta }}^z(A)=\mathrm{\infty }$ there are no feasible models of $A$ as $\prec$ is Z-rank refining. Therefore, $A|{\sim }_{\prec }B$ . Otherwise, this implies that ${\kappa }_{\mathrm{\Delta }}^z(AB)<{\kappa }_{\mathrm{\Delta }}^z(A\overline{B})$ .

Let $\omega \in \arg \underset{\omega \in {\mathrm{\Omega }}_{AB}}{min}{\kappa }_{\mathrm{\Delta }}^z(\omega )$ . For any feasible ${\omega }^{\prime }\in {\mathrm{\Omega }}_{A\overline{B}}$ it holds that ${\kappa }_{\mathrm{\Delta }}^z(\omega )<{\kappa }_{\mathrm{\Delta }}^z({\omega }^{\prime })$ . Because $\prec$ is Z-rank refining, we have that $\omega \prec {\omega }^{\prime }$ for any feasible ${\omega }^{\prime }\in {\mathrm{\Omega }}_{A\overline{B}}$ . Therefore, $A|{\sim }_{\prec }B$ .

From Theorem 3 we obtain the following characterization of RCP SPO-representable inductive inference operators.

Theorem 4 RCP SPO-representable

Let $C:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^C$ be an SPO-representable inductive inference operator. $C$ is RCP iff for each belief base $\mathrm{\Delta }$ the inference relation $C(\mathrm{\Delta })$ is induced by a SPO on worlds that is Z-rank refining with respect to $\mathrm{\Delta }$ .

As every SPO-representable inductive inference operator is preferential we have that every RCP SPO-representable inductive inference operator is an RCP preferential inductive inference operator. Similarly, every RCP BD-inductive inference operator is an RCP SPO-representable inductive inference operator. The reverse of these statements is not true, as observed by the Lemmas 6 and 7.

Lemma 6

There are RCP preferential inductive inference operators that are not RCP SPO-representable inductive inference operators.

Proof.

Consider an RCP preferential inductive inference operator $C$ that maps $\mathrm{\Delta }=\{(\overline{a}|b)\}$ to the inference relation $|{\sim }_{\mathcal{M}}$ induced by the preferential model $\mathcal{M}$ presented in the proof of Lemma 3; this mapping violates neither (RC Extension) nor (Classic Preservation) as $\mathcal{M}$ is Z-rank refining with respect to $\mathrm{\Delta }$ . As shown in the proof of Lemma 3, $|{\sim }_{\mathcal{M}}$ is not SPO-representable.

Lemma 7

There are RCP SPO-representable inductive inference operators that are not RCP basic defeasible inductive inference operators.

Proof.

Consider a rational SPO-representable inductive inference operator $C$ that maps $\mathrm{\Delta }=\{(\overline{a}|b)\}$ to the inference relation $|{\sim }_{\prec }$ induced by the SPO presented in the proof of Lemma 4; this mapping violates neither (RC Extension) nor (Classic Preservation). As shown in the proof of Lemma 4, $|{\sim }_{\prec }$ violates (RM). Therefore, $C$ is not a basic defeasible inference operator.

Finally, we can extend the notion of Z-rank refining to SPOs on formulas, and we can show its connection to RCP inductive inference operators that map each belief base to an inference relation induced by some SPO on formulas.

Definition 14 Z-rank refining

An SPO on formulas $⋖$ with ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathit{f}\mathit{e}\mathit{a}\mathit{s}(⋖)$ is called Z-rank refining (with respect to a belief base $\mathrm{\Delta }$ ) if ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{A\in \mathcal{L}\mid {\kappa }_{\mathrm{\Delta }}^z(A)<\mathrm{\infty }\}$ and additionally ${\kappa }_{\mathrm{\Delta }}^z(A)<{\kappa }_{\mathrm{\Delta }}^z(B)$ implies $A⋖B$ for any $A,B\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . For $\mathrm{\Delta }$ with $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ the only Z-rank refining SPO on formulas is defined to be $⋖$ with $\mathit{f}\mathit{e}\mathit{a}\mathit{s}(⋖)=\mathrm{\varnothing }$ .

While Definition 13 describes preserving the structure on worlds induced by Z-ranking functions, Definition 14 describes preserving the structure on formulas that is induced by Z-ranking functions. Note that Z-rank refining SPOs on worlds always induce Z-rank refining SPOs on formulas.

Theorem 5

Let $\prec$ be an SPO on worlds, ${\prec }_{\mathcal{L}}$ be the SPO on formulas induced by $\prec$ , and $\mathrm{\Delta }$ a belief base. Then $\prec$ is Z-rank refining iff ${\prec }_{\mathcal{L}}$ is Z-rank refining (each with respect to $\mathrm{\Delta }$ ).

Proof.

Let ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathit{f}\mathit{e}\mathit{a}\mathit{s}(\prec )$ and ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathit{f}\mathit{e}\mathit{a}\mathit{s}({\prec }_{\mathcal{L}})$ . For $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ the lemma can be easily verified. Assume for the remainder of the proof that $\mathrm{\top }{\text{⧸}|\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ .

Direction $\Rightarrow$ : Let $\prec$ be Z-rank refining with respect to $\mathrm{\Delta }$ . By Definition 12 a formula $F$ is in ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ iff ${\mathrm{\Omega }}_F\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\ne \mathrm{\varnothing }$ . Because $\prec$ is Z-rank refining we have that ${\mathrm{\Omega }}_F\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{\omega \in {\mathrm{\Omega }}_F\mid {\kappa }_{\mathrm{\Delta }}^z(\omega )<\mathrm{\infty }\}$ , and hence ${\mathrm{\Omega }}_F\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\ne \mathrm{\varnothing }$ iff there is a model of $F$ with finite rank, which is the case iff $\kappa (F)<\mathrm{\infty }$ . Therefore, ${\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{F\in \mathcal{L}\mid {\kappa }_{\mathrm{\Delta }}^z(F)<\mathrm{\infty }\}$ .

Let $A,B\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ with ${\kappa }_{\mathrm{\Delta }}^z(A)<{\kappa }_{\mathrm{\Delta }}^z(B)$ . This implies that there is at least one world in ${\mathrm{\Omega }}_A\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ as $\prec$ is Z-rank refining. Let $\omega \in \arg \underset{\omega \in {\mathrm{\Omega }}_A\cap {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}}{min}{\kappa }_{\mathrm{\Delta }}^z(\omega )$ . For any ${\omega }^{\prime }\in {\mathrm{\Omega }}_B$ it holds that $\kappa (\omega )<\kappa ({\omega }^{\prime })$ . Because $\prec$ is Z-rank refining, we have that $\omega \prec {\omega }^{\prime }$ for any ${\omega }^{\prime }\in {\mathrm{\Omega }}_B$ . Therefore, $A{\prec }_{\mathcal{L}}B$ .

Direction $\Leftarrow$ : Let ${\prec }_{\mathcal{L}}$ be Z-rank refining with respect to $\mathrm{\Delta }$ . For any world ${\omega }^{*}\in \mathrm{\Omega }$ , we have that ${\omega }^{*}\in {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ iff ${\omega }^{*}\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ where we consider $\omega$ as a formula on the right side of the “iff”. Because $⋖$ is Z-rank refining, ${\omega }^{*}\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ iff ${\kappa }_{\mathrm{\Delta }}^z({\omega }^{*})<\mathrm{\infty }$ which is the case iff ${\omega }^{*}$ considered as world has finite rank. Hence, ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\{{\omega }^{*}\in \mathrm{\Omega }\mid {\kappa }_{\mathrm{\Delta }}^z({\omega }^{*})<\mathrm{\infty }\}$ .

Let $\omega ,{\omega }^{\prime }\in {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ be worlds such that ${\kappa }_{\mathrm{\Delta }}^z(\omega )<{\kappa }_{\mathrm{\Delta }}^z({\omega }^{\prime })$ . In this case it is ${\kappa }_{\mathrm{\Delta }}^z(\omega )<{\kappa }_{\mathrm{\Delta }}^z({\omega }^{\prime })$ interpreting $\omega ,{\omega }^{\prime }$ as formulas. As ${\prec }_{\mathcal{L}}$ is Z-rank refining, it holds that $\omega {\prec }_{\mathcal{L}}{\omega }^{\prime }$ . This entails $\omega \prec {\omega }^{\prime }$ (with worlds considered as interpretations again).

Theorem 5 implies that every RCP SPO-representable inference operator maps belief bases to inference relations that can be obtained from Z-rank refining SPOs on formulas. The reverse is not true in general: not every Z-rank refining SPO on formulas induces an SPO-representable inference relation.

Lemma 8

Let $C:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^C$ be an RCP SPO-representable inductive inference operator. For every $\mathrm{\Delta }$ there is a Z-rank refining SPO on formulas inducing $|{\sim }_{\mathrm{\Delta }}^C$ .

Proof.

Let $C:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^C$ be an RCP SPO-representable inductive inference operator and $\mathrm{\Delta }$ be a belief base. With Theorem 4 we have that there is a Z-rank refining SPO on worlds ${\prec }_{\mathrm{\Delta }}$ inducing $|{\sim }_{\mathrm{\Delta }}^C$ . With Theorem 5 it follows that the SPO on formulas ${\prec }_{\mathrm{\Delta },\mathcal{L}}$ induced by ${\prec }_{\mathrm{\Delta }}$ is Z-rank refining.

Lemma 9

Not every Z-rank refining SPO on formulas induces an SPO-representable inference relation.

Proof.

Consider the SPO on formulas $\mathcal{M}$ in the proof of Lemma 5. $\mathcal{M}$ is Z-rank refining with respect to $\mathrm{\Delta }=\{(\mathrm{\perp }|\overline{a}\overline{b})\}$ , but does not induce an SPO-representable inference relation.

We can show that Z-rank refining SPOs on formulas induce inference relations satisfying (Classic Preservation) and (RC Extension). In the other direction we have that if an SPOs on formulas induces an inference relation that satisfies (Classic Preservation) and (RC Extension) then it must be Z-rank refining, provided that $E\not\equiv F$ , $E\models F$ implies $F⋖E$ . This additional assumption is necessary as information about entailments, as provided by (RC Extension), can only be translated to information about formulas with disjoint sets of models. The additional assumption allows connecting formulas that share models.

Theorem 6

Let $⋖$ be an SPO on formulas, $|{\sim }_{⋖}$ be the inference relation induced by $⋖$ , and let $\mathrm{\Delta }$ be a belief base.

If $⋖$ is Z-rank refining with respect to $\mathrm{\Delta }$ then $|{\sim }_{⋖}$ satisfies (Classic Preservation) and (RC Extension) with respect to $\mathrm{\Delta }$ .

If additionally $⋖$ satisfies that for $E,F\in \mathcal{L}$ , $E\not\equiv F$ it holds that $E\models F$ implies $F⋖E$ , then $|{\sim }_{⋖}$ satisfying (Classic Preservation) and (RC Extension) with respect to $\mathrm{\Delta }$ implies that $⋖$ is Z-rank refining with respect to $\mathrm{\Delta }$ .

Proof.

Let $⋖$ be an SPO on formulas and let $\mathrm{\Delta }$ be a belief base. For $\mathrm{\top }|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ the proposition can be easily verified. Assume for the remainder of the proof that $\mathrm{\top }{\text{⧸}|\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ .

Part (1.): Let $⋖$ be Z-rank refining with respect to $\mathrm{\Delta }$ . Let $F\in \mathcal{L}$ . We have $F|{\sim }_{⋖}\mathrm{\perp }$ iff $F\notin {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ . As $⋖$ is Z-rank refining, this is the case iff ${\kappa }_{\mathrm{\Delta }}^z(F)=\mathrm{\infty }$ , which happens iff $F|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ . Hence, (Classic Preservation) holds.

Let $A,B\in \mathcal{L}$ with $A|{\sim }_{\mathrm{\Delta }}^{z}B$ . If ${\kappa }_{\mathrm{\Delta }}^z(A)=\mathrm{\infty }$ then $A$ is not feasible as $⋖$ is Z-rank refining. Therefore, $A|{\sim }_{\mathrm{\Delta }}^{z}B$ . Otherwise, it follows that ${\kappa }_{\mathrm{\Delta }}^z(AB)<{\kappa }_{\mathrm{\Delta }}^z(A\overline{B})$ . As $⋖$ is Z-rank refining, this implies that $A\overline{B}$ is not feasible or that $AB⋖A\overline{B}$ . In both cases $A|{\sim }_{⋖}B$ . Therefore, (RC Extension) holds.

Part (2.): Let $|{\sim }_{⋖}$ satisfy (Classic Preservation) and (RC Extension). Let $F\in \mathcal{L}$ . We have ${\kappa }_{\mathrm{\Delta }}^z(F)=\mathrm{\infty }$ iff $F|{\sim }_{\mathrm{\Delta }}^p\mathrm{\perp }$ . As $|{\sim }_{⋖}$ satisfies (Classic Preservation), this happens iff $F|{\sim }_{⋖}\mathrm{\perp }$ , which is the case iff $F\notin {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ .

Let $A,B\in {\mathcal{L}}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ with ${\kappa }_{\mathrm{\Delta }}^z(A)<{\kappa }_{\mathrm{\Delta }}^z(B)$ . This implies ${\kappa }_{\mathrm{\Delta }}^z(A)<\mathrm{\infty }$ ; and we have $A\vee B|{\sim }_{\mathrm{\Delta }}^z\overline{B}$ . As $|{\sim }_{⋖}$ satisfies (RC Extension) we have that $A\vee B|{\sim }_{⋖}\overline{B}$ . Because $A$ and $B$ are feasible, we have that $A\vee B$ is feasible. This in combination with $A\vee B|{\sim }_{⋖}\overline{B}$ yields that $(A\vee B)\overline{B}⋖(A\vee B)B$ which is equivalent to $A\overline{B}⋖B$ . We have either $A\equiv A\overline{B}$ and therefore $A⋖B$ or $A\not\equiv B$ and therefore $A⋖A\overline{B}⋖B$ because $A\overline{B}\models A$ .

Theorem 6 shows that an inductive inference operator mapping a belief base to an inference relation induced by a Z-rank refining SPO on formulas is RCP.

7. Instances of RC Extending Inference Operators

Naturally, rational BD-inductive inference operators like lexicographic inference (Lehmann, 1995) are examples of RCP SPO-representable inductive inference operators because they are based on TPOs and every TPO is also an SPO. In this section we will show some examples of RC extending inference operators that do not satisfy (RM) and thus make use of the more general characterizations introduced in this article.

System W (Komo & Beierle, 2020, 2022) is an example of an RCP SPO-representable inductive inference operator that is not a BD-inductive inference operator. In addition to the Z-partition of a belief base $\mathrm{\Delta }$ , system W also takes into account the structural information which conditionals are falsified. The definition of system W is based on a binary relation called a preferred structure on worlds ${<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}$ over $\mathrm{\Omega }$ that is assigned to every belief base $\mathrm{\Delta }$ . Here, we use an extended version of system W introduced in Haldimann et al. (2023a) that also covers weakly consistent belief bases.

Definition 15 ${\xi }^j,\xi$ , preferred structure ${<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}$ on worlds (Haldimann et al., 2023a; Komo & Beierle, 2022)

Let $\mathrm{\Delta }$ be a belief base with the Z-partition $\mathit{E}\mathit{Z}\mathit{P}(\mathrm{\Delta })=({\mathrm{\Delta }}^0,\dots ,{\mathrm{\Delta }}^k,{\mathrm{\Delta }}^{\mathrm{\infty }})$ . For $j\in \{0,\dots ,k,\mathrm{\infty }\}$ the function ${\xi }^j$ is the function mapping worlds to the set of falsified conditionals in ${\mathrm{\Delta }}^j$ given by ${\xi }^j(\omega )=\{(B_i|A_i)\in {\mathrm{\Delta }}^j\mid \omega \models A_i\overline{B_i}\}$ .

Let ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathrm{\Omega }\setminus \{\omega \mid {\xi }^{\mathrm{\infty }}(\omega )\ne \mathrm{\varnothing }\}$ . The preferred structure on worlds is the relation ${<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}\subseteq {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\times {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ defined by

$$\begin{array}{rl}\omega {<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}{\omega }^{\prime }& \text{iff}\text{there exists an }m\in \{0,\dots ,k\}\text{ such that }\\ & {\xi }^i(\omega )={\xi }^i({\omega }^{\prime })\mathrm{\forall }i\in \{m+1,\dots ,k\}\text{ and }\\ & {\xi }^m(\omega )⫋{\xi }^m({\omega }^{\prime }).\end{array}$$

Thus, $\omega {<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}{\omega }^{\prime }$ iff $\omega$ falsifies strictly fewer conditionals than ${\omega }^{\prime }$ in the partition with the biggest index $m$ where the conditionals falsified by $\omega$ and ${\omega }^{\prime }$ differ.

Definition 16 system W, $|{\sim }_{\mathrm{\Delta }}^{\mathsf{\text{w}}}$ Haldimann et al., 2023a; Komo & Beierle, 2022

Let $\mathrm{\Delta }$ be a belief base and $A,B$ be formulas. Then $B$ is a system W inference from $A$ , denoted $A|{\sim }_{\mathrm{\Delta }}^{\mathsf{\text{w}}}B$ , if for every ${\omega }^{\prime }\in {\mathrm{\Omega }}_{A\overline{B}}$ there is a feasible $\omega \in {\mathrm{\Omega }}_{AB}$ such that $\omega {<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}{\omega }^{\prime }$ .

Multipreference-closure (short MP-closure) is an inference method developed for the description logic with typicality $\mathcal{A}\mathcal{L}\mathcal{C}+{\mathbf{\text{T}}}_{\mathsf{\text{R}}}$ introduced in Giordano and Gliozzi (2018). MP-closure was adapted for reasoning with conditionals based on propositional logic in (Giordano & Gliozzi, 2021).

While system W and MP-closure were developed independently in different contexts and defined using distinct approaches, it is interesting that it has been shown that MP-closure for propositional conditionals coincides with system W both for strongly consistent belief bases (Haldimann & Beierle, 2022a) and weakly consistent belief bases (Haldimann et al., 2023a).

Since ${<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}$ is a SPO (Komo and Beierle, 2022, Lemma 3), system W, and thus also MP-closure, is an SPO representable inductive inference operator $C^{\mathsf{w}}:\mathrm{\Delta }\mapsto |{\sim }_{{<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}}$ . System W fulfills the postulates of system P, strictly extends both system Z (Pearl, 1990) and also c-inference (Beierle et al., 2016, 2021a), and enjoys further desirable properties like avoiding the drowning problem, (Benferhat et al., 1993; Komo & Beierle, 2022) fully complying with syntax splitting (Haldimann & Beierle, 2022b, 2022c; Haldimann et al., 2023a; Kern-Isberner et al., 2020), and also with conditional syntax splitting (Heyninck et al., 2023). Using Theorem 2 we can immediately see that for every weakly consistent $\mathrm{\Delta }$ the preferred structure ${<}_{\mathrm{\Delta }}^{\mathsf{\text{w}}}$ inducing system W is Z-rank refining.

Another example of an SPO representable inference operator, inspired by system W, uses the following modified SPO to obtain an inference relation from a belief base (Haldimann & Beierle, 2023; Tönnies, 2022).

Definition 17 $C^{wl}$ , $|{\sim }^{wl}$

Let $\mathrm{\Delta }$ be a belief base with the Z-partition $\mathit{E}\mathit{Z}\mathit{P}(\mathrm{\Delta })=({\mathrm{\Delta }}^0,\dots ,{\mathrm{\Delta }}^k,{\mathrm{\Delta }}^{\mathrm{\infty }})$ . Let ${\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}=\mathrm{\Omega }\setminus \{\omega \mid {\xi }^{\mathrm{\infty }}(\omega )\ne \mathrm{\varnothing }\}$ . We define the relation ${<}_{\mathrm{\Delta }}^{wl}\subseteq {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}\times {\mathrm{\Omega }}^{\mathit{f}\mathit{e}\mathit{a}\mathit{s}}$ by

$$\begin{array}{rl}\omega {<}_{\mathrm{\Delta }}^{wl}{\omega }^{\prime }& \text{iff}\text{there exists an }m\in \{0,\dots ,k\}\text{ such that }\\ & {\xi }_{\mathrm{\Delta }}^i(\omega )={\xi }_{\mathrm{\Delta }}^i({\omega }^{\prime })\mathrm{\forall }i\in \{m+1,\dots ,k\}\text{ and }\\ & |{\xi }_{\mathrm{\Delta }}^m(\omega )|<|{\xi }_{\mathrm{\Delta }}^m({\omega }^{\prime })|.\end{array}$$

The inductive inference operator $C^{wl}:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^{wl}$ is defined by $A|{\sim }_{\mathrm{\Delta }}^{wl}B$ iff for every ${\omega }^{\prime }\in {\mathrm{\Omega }}_{A\overline{B}}$ there is an $\omega \in {\mathrm{\Omega }}_{AB}$ such that $\omega {<}_{\mathrm{\Delta }}^{wl}{\omega }^{\prime }$ .

The inductive inference operator $C^{wl}$ is defined via a SPO on worlds and thus satisfies system P (Haldimann & Beierle, 2023); furthermore it satisfies (Classic Preservation). $C^{wl}$ captures and strictly extends system W and thus also c-inference and system Z while being captured and strictly extended by lexicographic inference (Haldimann & Beierle, 2023).

Again, we can use Theorem 2 to conclude that for every $\mathrm{\Delta }$ the SPO ${<}^{wl}$ must be Z-rank refining with respect to $\mathrm{\Delta }$ . By analyzing the construction of ${<}^{wl}$ we can verify that this is indeed the case.

As system W was the first inference operator shown to extend both rational closure and c-inference, in search of approximations of system W the idea of combining inference operators by their union was introduced (Haldimann & Beierle, 2023).

Definition 18 union of inference operators, Haldimann and Beierle (2023)

Let $C^1:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^1$ and $C^2:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^2$ be inductive inference operators. The union of $C^1$ and $C^2$ , denoted by is the mapping $C:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}$ with $|{\sim }_{\mathrm{\Delta }}=|{\sim }_{\mathrm{\Delta }}^1\cup |{\sim }_{\mathrm{\Delta }}^2$ .

This means that for any $A,B\in {\mathcal{L}}_{\mathrm{\Sigma }}$ we have $A|{\sim }_{\mathrm{\Delta }}B$ iff $A|{\sim }_{\mathrm{\Delta }}^{1}B$ or $A|{\sim }_{\mathrm{\Delta }}^{2}B$ (with $C^1,C^2,C$ as in Definition 18). Note that this operator does not ensure the inheritance of the properties of the involved inference operators in any way. The only guarantee it gives is that the union of two inductive inference operators yields again an inductive inference operator (Haldimann & Beierle, 2023). This means that the union of inference operators may have unwanted properties. For example, if $A|{\sim }_{\mathrm{\Delta }}^{1}B,A\text{⧸}|{\sim }_{\mathrm{\Delta }}^1\mathrm{\perp }$ and $A|{\sim }_{\mathrm{\Delta }}^2\mathrm{\neg }B,A\text{⧸}|{\sim }_{\mathrm{\Delta }}^2\mathrm{\perp }$ , then for the resulting operator $|{\sim }_{\mathrm{\Delta }}=|{\sim }_{\mathrm{\Delta }}^1\cup |{\sim }_{\mathrm{\Delta }}^2$ it holds that $A|{\sim }_{\mathrm{\Delta }}B$ , $A|{\sim }_{\mathrm{\Delta }}\mathrm{\neg }B$ , and $A\text{⧸}|{\sim }_{\mathrm{\Delta }}\mathrm{\perp }$ . Uniting inference operators also does not preserve the compliance with system P postulates. Consider the union of c-inference and system Z. By definition, $C^{cZ}$ is the smallest inductive inference operator to capture system Z and c-inference. However, $C^{cZ}$ is not preferential, that is, it does not comply with the postulates of system P (Haldimann & Beierle, 2023).

If an inductive inference operator $C$ fails to satisfy a (set of) postulate(s), compliance with these postulates can possibly be achieved by adding additional pairs to the inference relations induced by $C$ .

Definition 19 Closure under a set of postulates, Haldimann and Beierle (2023)

Let $C:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}$ be an inductive inference operator. Let $X$ be a set of postulates for inductive inference operators. An inductive inference operator $C^X:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^X$ is a closure of $C$ under $X$ if $|{\sim }_{\mathrm{\Delta }}\subseteq |{\sim }_{\mathrm{\Delta }}^X$ and $|{\sim }_{\mathrm{\Delta }}^X$ satisfies $X$ . $C^X:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^X$ is a minimal closure of $C$ under $X$ if it is a closure of $C$ under $X$ , and if there is no closure $C^{\prime }$ of $C$ under $X$ such that $C^{\prime }(\mathrm{\Delta })\subseteq C^X(\mathrm{\Delta })$ for every $\mathrm{\Delta }$ .

For any inductive inference operator $C$ there is a unique minimal closure of $C$ under system P (Haldimann & Beierle, 2023). As the result $C^{cZ}$ of naively combining system Z and c-inference does not satisfy system P, we consider the minimal closure of $C^{cZ}$ under system P, denoted as

$$C^{P(cZ)}:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^{\mathit{P}\mathit{(}\mathit{c}\mathit{Z}\mathit{)}}.$$

To better understand $C^{P(cZ)}$ it would be useful to have a semantic characterization of it, but to the best of our knowledge no such characterization is known. However, there are at least some things we can infer. By construction, $C^{P(cZ)}$ satisfies system P, (RC Extension), and (Classic Preservation). Thus, it is an RCP preferential inference operator. By Theorem 1 we know that for every $\mathrm{\Delta }$ , the inference relation $|{\sim }_{\mathrm{\Delta }}^{P(cZ)}$ is induced by a Z-rank refining preferential model. In fact, all preferential models inducing $|{\sim }_{\mathrm{\Delta }}^{P(cZ)}$ must be Z-rank refining. While this is far from a semantic characterization, it is a starting point for further research on the semantics of this inference operator.

Relevant closure (Casini et al., 2014) is an inference operator that was introduced as strengthening of rational closure. To decide if $A|{\sim }_{\mathrm{\Delta }}^{rel}B$ is entailed, it takes into account what conditionals are relevant for making the antecedent $A$ exceptional. While the original definition of propositional conditionals is given for defeasible DL inclusions, we can translate it to the setting of propositional conditionals used in this article.

Definition 20 justification, cf. Casini et al. (2014)

Let $\mathrm{\Delta }$ be a belief base and $A\in \mathcal{L}$ . The formula $A$ is exceptional for a set $J$ of conditionals if every model of $A$ falsifies at least one conditional in $J$ . A set $J\subseteq \mathrm{\Delta }$ is a justification for $A$ with respect to $\mathrm{\Delta }$ if $A$ is exceptional for $J$ , but $A$ is not exceptional for every $J^{\prime }⊊J$ . ${\mathcal{J}}^{\mathrm{\Delta }}(A)$ denotes the set of all justifications of $A$ with respect to $\mathrm{\Delta }$ .

Using justifications, relevant closure is defined by a modified version of the syntactic characterization of rational closure.

Definition 21 relevant closure, cf. Casini et al. (2014)

Let $\mathrm{\Delta }$ be a belief base with the Z-partition $\mathit{E}\mathit{Z}\mathit{P}(\mathrm{\Delta })=({\mathrm{\Delta }}^0,\dots ,{\mathrm{\Delta }}^k,{\mathrm{\Delta }}^{\mathrm{\infty }})$ , and let $A,B\in \mathcal{L}$ . Let $R=\bigcup _{J\in {\mathcal{J}}^{\mathrm{\Delta }}(A)}J$ . For a set $C$ of conditionals let $\overline{C}=\{E\to F\mid (F|E)\in C\}$ denote the set of material implications corresponding to the conditionals in $C$ .

Let $i\in \{-1,\dots ,k\}$ be the minimal number for which $\{A\}\cup \overline{\mathrm{\Delta }\setminus (R\cap ({\mathrm{\Delta }}^0\cup \cdots \cup {\mathrm{\Delta }}^i))}$ is satisfiable. Then $B$ is in the (basic) relevant closure of $A$ , denoted $A|{\sim }_{\mathrm{\Delta }}^{rel}B$ , if $\{A\}\cup \overline{\mathrm{\Delta }\setminus (R\cap ({\mathrm{\Delta }}^0\cup \cdots \cup {\mathrm{\Delta }}^i))}\models B$ . If no such $i$ exists, that is, if $\{A\}\cup \overline{\mathrm{\Delta }\setminus (R\cap ({\mathrm{\Delta }}^0\cup \cdots \cup {\mathrm{\Delta }}^k))}$ is unsatisfiable, then we define $A|{\sim }_{\mathrm{\Delta }}^{rel}B$ to hold as well.

Example 4

Let ${\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}=\{(f|b),(b|p),(\overline{f}|p),(w|b)\}$ be a belief base over $\mathrm{\Sigma }=\{p,b,w,f\}$ . The corresponding tolerance partition is $\mathit{E}\mathit{Z}\mathit{P}({\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}})=({\mathrm{\Delta }}^0,{\mathrm{\Delta }}^1,{\mathrm{\Delta }}^{\mathrm{\infty }})$ with ${\mathrm{\Delta }}^0=\{(f|b),(w|b)\}$ , ${\mathrm{\Delta }}^1=\{(b|p),(\overline{f}|p)\}$ , and ${\mathrm{\Delta }}^{\mathrm{\infty }}=\mathrm{\varnothing }$ . Consider the query “does $p$ entail $w$ ?” The only justification for $p$ is $J=\{(f|b),(b|p),(\overline{f}|p)\}$ ; therefore $R=J$ . We can check that

$$\begin{array}{rl}& \{p\}\cup \overline{{\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}}\text{ is unsatisfiable, and that}\\ & \{p\}\cup \overline{{\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}\setminus (R\cap {\mathrm{\Delta }}^0)}=\{p,p\to b,p\to \overline{f},b\to w\}\text{ is satisfiable.}\end{array}$$

Because $\{p\}\cup \overline{{\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}\setminus (R\cap {\mathrm{\Delta }}^0)}\models w$ we have that $p|{\sim }_{{\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}}^{\mathit{r}\mathit{e}\mathit{l}}w$ .

Relevant closure strictly extends rational closure. It is known that relevant closure does not comply with system P in some cases, specifically it violates (OR) and (CM) (Casini et al., 2014) which is a major drawback. To fix this, we can consider the minimal closure of relevant closure under system P, denoted by

$$C^{P(rel)}:\mathrm{\Delta }\mapsto |{\sim }_{\mathrm{\Delta }}^{\mathit{P}\mathit{(}\mathit{r}\mathit{e}\mathit{l}\mathit{)}}.$$

This preferential version of relevant closure is only defined by a syntactic construction, and it would be interesting to understand it through a semantic characterization. The properties of $C^{P(rel)}$ are subject to investigation in future work. But we know that $C^{P(rel)}$ extends rational closure, and that it satisfies system P by construction. We can also observe that $C^{P(rel)}$ satisfies classic preservation. From this we can conclude by Theorem 1 that for every $\mathrm{\Delta }$ , the inference relation $|{\sim }_{\mathrm{\Delta }}^{P(rel)}$ is induced by a Z-rank refining preferential model.

Example 5

Consider the belief base ${\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}$ from Example 4. The Z-ranking function induced by ${\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}$ is illustrated in Figure 2(a), and a preferential model $\mathcal{M}=(S,l,\prec )$ inducing $|{\sim }_{{\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}}^{P(rel)}$ is illustrated in Figure 2(b), with states in $S$ being labelled by the worlds they are mapped to by $l$ . We can see that $\mathcal{M}$ is Z-rank refining with respect to ${\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}$ .

Figure 2.

Z-ranking Function and a Preferential Model of ${\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}$ From Example 5. (a) Z-ranking Function ${\kappa }_{{\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}}^z$ of ${\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}$ and (b) Order $\prec$ of the Z-rank Refining Preferential Model $\mathcal{M}=(S,l,\prec )$ Inducing $|{\sim }_{{\mathrm{\Delta }}^{\mathit{b}\mathit{i}\mathit{r}\mathit{d}}}^{P(rel)}$ .

Because relevant closure is strictly extended by lexicographic inference (Casini et al., 2014), which is preferential, we know that $C^{P(rel)}$ is extended by lexicographic inference. The relations among the inductive inference operators in this section are illustrated in Figure 3.

Figure 3.

Overview Over Relationships Among the Inductive Inference Operators Considered in This Article. An Arrow $I_1\hookrightarrow I_2$ Indicates That Inductive Inference Operator $I_1$ is Captured by $I_2$ and that $I_1$ is Strictly Extended by $I_2$ for Some Belief Bases.

8. Conclusions and Future Work

In this article, we investigated RCP inductive inference operators, that is, inductive inference operators satisfying (RC Extension) and (Classic Preservation). Doing this we focused on SPO-representable inference relations, that is, inference relations that can be obtained from SPOs on worlds. We showed that this class of inductive inference operators is a subclass of preferential inductive inference operators and a superclass of basic defeasible inductive inference operators. We provided characterization theorems for RCP preferential and RCP SPO-representable inductive inference operators using the newly introduced property ‘Z-rank refining’ for preferential models and SPOs on worlds. Finally, we investigated instances of RCP inductive inference operators and applied our characterization results to them. Future work includes to further investigate instances of RCP inductive inference operators. Characterizing relevant closure semantically and establishing its relationship to inference operators like system W is of special interest to us, but we are also interested in implementing and evaluating these inference operators empirically, for example, on basis of the reasoning platform InfOCF (Beierle et al., 2024; Kutsch & Beierle, 2021).