Lexicographic Entailment, Syntax Splitting and the Drowning Problem

1 Introduction

Lexicographic inference [Lehmann, 1995] is a well-known and popular approach to reasoning with non-monotonic conditionals, which has been applied in (probabilistic) description logics [Casini and Straccia, 2012; Giugno and Lukasiewicz, 2002] as well as richer preferential languages [Booth et al., 2015]. It is seen as a logic of very high-quality, as it extends rational closure and avoids the so-called drowning problem. It seems, however, this high quality comes at a cost, as reasoning on the basis of lexicographic inference is P NP -complete, even when restricted to belief bases consisting of Horn-literal rules, i.e. rule bases where every rule's antecedent is a conjunction of atoms and every rule's consequent is a literal [Eiter and Lukasiewicz, 2000]. In this paper, we show that lexicographic inference satisfies syntax splitting [Kern-Isberner et al., 2020], which means that we can restrict our attention to parts of the belief base that share atoms with a given query, thus seriously restricting the computational strain for many concrete queries. To the best of our knowledge, this is the first result that shows that lexicographic inference satisfies this property, and thus we show that there exists an inductive inference relation that both extends rational closure and satisfies syntax splitting. In more detail, the contributions of this paper are the following:

1. We show that lexicographic inference satisfies syntax splitting. This shows that lexicographic inference is an inference relation that is of the highest quality, and at least in many cases, its computational complexity can be circumvented.
2. We show that lexicographic inference is closely related but not identical to c-representations [Kern-Isberner, 2002], the only other inference relation that was shown to satisfy syntax splitting.
3. We show that lexicographic inference is not the only extension of rational closure that satisfies syntax splitting, and that syntax splitting is independent of the drowning problem.

Outline of this Paper We first state all the necessary preliminaries in Section 2 on propositional logic (Section 2.1), reasoning with non-monotonic conditionals (Section 2.2), inductive inference (Section 2.3), System Z (Section 2.4), lexicographic inference (Section 2.5) and c-representations (Section 2.6). In Section 3 we show that lexicographic inference satisfies syntax splitting. In Section 4 we compare lexicographic inference with the only other inductive inference relation known to satisfy syntax splitting: c-representations. In Section 5 we make some further observations on inference relations extending rational closure, syntax splitting and the drowning effect. In Section 6 we discuss related work, and we conclude in Section 7.

2 Preliminaries

In the following, we recall general preliminaries on propositional logic, and technical details on inductive inference.

2.1 Propositional Logic

For a set Σ of atoms let L(Σ) be the corresponding propositional language constructed using the usual connectives ∧ (and), ∨ (or), ¬ (negation), → (material implication) and ↔ (material equivalence). A (classical) interpretation (also called possible world) ω for a propositional language L(Σ) is a function ω : Σ → {⊤,⊥}. Let Ω(Σ) denote the set of all interpretations for Σ. We simply write Ω if the set of atoms is implicitly given. An interpretation ω satisfies (or is a model of) an atom a ∈ Σ, denoted by ω |= a, if and only if ω(a) = ⊤. The satisfaction relation |= is extended to formulas as usual. As an abbreviation we sometimes identify an interpretation ω with its complete conjunction, i. e., if a1, . . . , an ∈ Σ are those atoms that are assigned ⊤ by ω and an+1, . . . , am ∈ Σ are those propositions that are assigned ⊥ by ω we identify ω by a1 . . . anan+1 . . . am (or any permutation of this). For X ⊆ L(Σ) we also define ω |= X if and only if ω |= A for every A ∈ X. Define the set of models Mod(X) = {ω ∈ Ω(Σ) | ω |= X} for every formula or set of formulas X. A formula or set of formulas X1 entails another formula or set of formulas X2, denoted by X1 ⊢ X2, if Mod(X1) ⊆ Mod(X2). Where θ ⊆ Σ, and ω ∈ Ω(Σ), we denote by ωθ the restriction of ω to Σθ , i.e. ωθ is the interpretation over Σθ that agrees with ω on all atoms in Σθ . Ω(Σi) will also be denoted by Ωi for any i ∈ N. Likewise, for some X ⊆ L(Σi), we define Modi(X) = {ω ∈ Ωi | ω |= X}.

2.2 Reasoning with Nonmonotonic Conditionals

Given a language L, conditionals are objects of the form (B|A) where A, B ∈ L. The set of all conditionals based on a language L is defined as: (L|L) = {(B|A) | A,B ∈ L}. We follow the approach of [de Finetti, 1974] who considered conditionals as generalized indicator functions for possible worlds resp. propositional interpretations ω:

where u stands for unknown or indeterminate. In other words, a possible world ω verifies a conditional (B|A) iff it satisfies both antecedent and conclusion ((B|A)(ω) = 1); it falsifies, or violates it iff it satisfies the antecedence but not the conclusion ((B|A)(ω) = 0); otherwise the conditional is not applicable, i. e., the interpretation does not satisfy the antecedent ((B|A)(ω) = u). We say that ω satisfies a conditional (B|A) iff it does not falsify it, i.e., iff ω satisfies its material counterpart A → B. Given a total preorder ⪯ on possible worlds, representing relative plausibility, A ⪯ B iff ω ⪯ ω′ for some ω ∈ min⪯(Mod(A)) and some ω′ ∈ min⪯(Mod(B)). This allows for expressing the validity of defeasible inferences via stating that A|∼ ⪯B iff (A ∧ B) ≺ (A ∧ ¬B) [Makinson, 1988]. As is usual, we denote ω ⪯ ω′ and ω′ ⪯ ω by ω ≈ ω′ and ω ⪯ ω′ and ω′ ̸⪯ ω by ω ≺ ω′ (and similarly for formulas). We can marginalize total preorders and even inference relations, i.e., restricting them to sublanguages, in a natural way: If Θ ⊆ Σ then any TPO ⪯ on Ω(Σ) induces uniquely a marginalized TPO ⪯|Θ on Ω(Θ) by setting

Note that on the right hand side of eqn. (2) above ωΘ 1 , ωΘ 2 are considered as propositions in the superlanguage L(Ω), hence ωΘ 1 ⪯ ωΘ 2 is well defined [Kern-Isberner and Brewka, 2017].

Similarly, any inference relation |∼ on L(Σ) induces a marginalized inference relation |∼|Θ on L(Θ) by setting

for any A, B ∈ L(Θ).

An obvious implementation of total preorders are ordinal conditional functions (OCFs), (also called ranking functions)

κ : Ω → N ∪ {∞} [Spohn, 1988]. They express degrees of (im)plausibility of possible worlds and propositional formulas A by setting κ(A) := min{κ(ω) | ω |= A}. A conditional (B|A) is accepted by κ iff A |∼κB iff κ(A∧B) < κ(A∧¬B).

2.3 Inductive Inference

In this paper, we will be interested in inference relations |∼ ∆ parametrized by a conditional belief base ∆. In more detail, such inference relations are induced by ∆, in the sense that ∆ serves as a starting point for the inferences in |∼ ∆. We call such operators inductive inference operators:

Definition 1 ([Kern-Isberner et al., 2020]). An inductive inference operator (from conditional belief bases) is a mapping C that assigns to each conditional belief base ∆ ⊆ (L|L) an inference relation |∼ ∆ ⊆ L×L that satisfies the following basic requirement of direct inference:

DI If ∆ is a conditional belief base and |∼ ∆ is an inference relation that is induced on ∆, then (B|A) ∈ ∆ implies A |∼ ∆B.

Examples of inductive inference operators include system P [Kraus et al., 1990] and the inference relations below.

Inference relations can be obtained on the basis of TPOs respectively OCFs:

Definition 2. A model-based inductive inference operator for total preorders (on Ω) is a mapping Ctpo that assigns to each conditional belief base ∆ a total preorder ⪯∆ on Ω s.t. A|∼ ⪯∆ B for every (B|A) ∈ ∆ (i.e. s.t. DI is ensured). A model-based inductive inference operator for OCFs (on Ω) is a mapping Cocf that assigns to each conditional belief base ∆ an OCF κ∆ on Ω s.t. ∆ is accepted by κ∆(i.e. s.t. DI is ensured).

Examples of inductive inference operators for OCFs are System Z ([Goldszmidt and Pearl, 1996], see Sec. 2.4) and crepresentations ([Kern-Isberner, 2002], see Sec. 2.6), whereas lexicographic inference ([Lehmann, 1995], see Sec. 2.5) is an example of an inductive inference operator for TPOs.

To define the property of syntax splitting [Kern-Isberner et al., 2020], we assume a conditional belief base ∆ that can be split into subbases ∆1 ,∆2 s.t. ∆i ⊂ (Li|Li) with Li = L(Σi) for i = 1, 2 s.t. Σ1∩Σ2 = ∅ and Σ1∪Σ2 = Σ, writing:

whenever this is the case.

Definition 3 (Independence (Ind), [Kern-Isberner et al., 2020]). An inductive inference operator C satisfies (Ind) if for any ∆ = ∆1 ⋃Σ1,Σ2 ∆2 and for any A, B ∈ Li, C ∈ Lj (i, j ∈ {1, 2}, j ̸= i),

Definition 4 (Relevance (Rel), [Kern-Isberner et al., 2020]). An inductive inference operator C satisfies (Rel) if for any ∆ = ∆1 ⋃Σ1,Σ2 ∆2 and for any A, B ∈ Li (i ∈ {1, 2}),

Definition 5 (Syntax splitting (SynSplit), [Kern-Isberner et al., 2020]). An inductive inference operator C satisfies (SynSplit) if it satisfies (Ind) and (Rel).

Thus, Ind requires that inferences from one sub-language are independent from formulas over the other sublanguage, if the belief base splits over the respective sublanguages. In other words, information on the basis of one sublanguage does not influences inferences made in the other sublanguage. Rel, on the other hand, restricts the scope of inferences, by requiring that inferences in a sublanguage can be made on the basis of the conditionals in a conditional belief base formulated on the basis of that sublanguage. SynSplit combines these two properties.

2.4 SystemZ

We present system Z defined in [Goldszmidt and Pearl, 1996] as follows. A conditional (B|A) is tolerated by a finite set of conditionals ∆ if there is a possible world ω with (B|A)(ω) = 1 and (B′ |A′ )(ω) ̸= 0 for all (B′ |A′ ) ∈ ∆, i.e. ω verifies (B|A) and does not falsify any (other) conditional in ∆. The Z-partitioning (∆0, . . . , ∆n) of ∆ is defined as:

• ∆0 = {δ ∈ ∆ | ∆ tolerates δ};
• ∆1, . . . ,∆n is the Z-partitioning of ∆\∆0.

For δ ∈ ∆ we define: Z∆(δ) = i iff δ ∈ ∆i and (∆0, . . . ,∆n) is the Z-partioning of ∆. Finally, the ranking function κZ∆ is defined via: κZ∆(ω) = max{Z(δ) | δ(ω) = 0, δ ∈ ∆} + 1, with max∅ = -1. The resulting inductive inference operator C ocf κZ∆ is denoted by C Z .

In the literature, system Z has also been called rational closure [Lehmann and Magidor, 1992]. An inference relation |∼ ∆ based on ∆ s.t. A |∼ Z∆B implies A |∼ ∆B is called RC-extending [Casini et al., 2019]. An RC-extending inference relation has also been called a refinement of System Z [Ritterskamp and Kern-Isberner, 2008]. We call an inductive inference operator C RC-extending iff every C(∆) is RCextending.

We now illustrate OCFs in general and System Z in particular with the well-known "Tweety the penguin"-example.

As an example of a (non-)inference, observe that e.g. ⊤ |∼ Z∆¬p and p ∧ f ̸|∼ Z∆b.

2.5 Lexicographic Entailment

We recall lexicographic inference as introduced by [Lehmann, 1995]. For some conditional belief base ∆, the order ⪯lex ∆ is defined as follows: Given ω ∈ Ω and ∆′ ⊆ ∆, V (ω,∆′ ) = |({(B|A) ∈ ∆′ | (B|A)(ω) = 0}|. Given a set of conditionals ∆ Z-partitioned in (∆0, . . . ,∆n), the lexicographic vector for a world ω ∈ Ω is the vector lex(ω) = (V (ω,∆0), . . . , V (ω,∆n)). Given two vectors (x1, . . . , xn) and (y1, . . . , yn), (x1, . . . , xn) ⪯lex (y1, . . . , yn) iff there is some j ⩽ n s.t. xk = yk for every k > j and xj ⩽ yj. ω ⪯lex ∆ ω′ iff lex(ω) ⪯lex lex(ω′ ). The resulting inductive inference operator C tpo ⪯lex will be denoted by C lex to avoid clutter.

In [Lehmann, 1995], lexicographic inference was shown to be RC-extending (for finite conditional belief bases):

Proposition 1 ([Lehmann, 1995, Theorem 3]). For any A ∈ L s.t. κZ∆(A) is finite, then A |∼ Z∆B implies A |∼ lex ∆ B.

The lex-vectors are ordered as follows:

2.6 C-Representations

Here we present c-representations as presented by [KernIsberner, 2002]. Given a set of conditionals ∆ = {(B1|A1), . . . , (Bn|An)}, an OCF κ is indifferent with respect to ∆ iff there are η0, ηi ∈ Q for 1 ⩽ i ⩽ n s.t. for every ω ∈ Ω:

We can then ensure that κ |= ∆ holds by making sure the following inequality holds for every 1 ⩽ i ⩽ n: 1

A c-representation of a set of conditionals ∆ is an OCF κ of the form (4) whose parameters satisfy equation (5). It can be observed that for any c-representation κ of ∆, κ |= ∆.

As an example of an inference, observe that e.g. ⊤ |∼ κ¬p and p ∧ f |∼ κ b.

3 Lexicographic Entailment Satisfies Syntax Splitting

In this short but central section, we state one of the main results of the paper, namely that lexicographic entailment satisfies syntax splitting. Syntax splitting is shown by showing that Ind and Rel are satisfied. Rel is quite straightforward. In fact it also holds for e.g. system Z [Kern-Isberner et al., 2020], and is proved in a way that is similar to the proof for system Z in [Kern-Isberner et al., 2020]. For Ind, things are a bit more involved. Due to spatial restrictions, the proof could not be included (but is given, like the proofs of all results in this paper, in the appendix), but we illustrate the main ideas using an example.

We see that ⊤|∼ Z∆a (since κZ∆(a) < κZ∆(a)) yet b ̸|∼ Z∆a (since κZ∆(ab) = κZ∆(ab)), i.e. inferences in System Z over the signature {a} are not independent from the signature {b} even though {a}, {b} splits ∆. The reason is that ab and ab have the same κZ∆-value, and thus the κZ∆-value does not preserve the original order between a and a when looking at bworlds. This is not the case for lexicographic inference since lex(ab) ≺lex lex(ab).

More generally, the reason for lexicographic entailment satisfying Ind is that, since lexicographic vectors count the number of conditionals violated by a world, the relative order of marginalized world is independent of other subsignatures, i.e. (for ∆ = ∆1 ⋃Σ1,Σ2 ∆2 , ωi1 , ωi2 ∈ Ωi, ωj ∈ Ωj, i, j = 1, 2 and i ̸= j):

Altogether, the following central theorem of the paper can be shown:

Theorem 1. C lex satisfies SynSplit.

It is important to notice that the satisfaction of syntax splitting by lexicographic entailment does not improve the worstcase complexity of lexicographic inference. However, syntax splitting can be used to develop implementations that are more efficient than current implementations for many concrete queries, as it ensures that we can restrict attention to the part of the conditional belief base relevant to the query.

4 Lexicographic Entailment in C-Representations

In previous work, only c-representations were shown to be an inductive inference method that satisfies syntax splitting (see Algorithm 1 Algorithm for generating a c-representation equivalent to lexicographic entailment Input: a belief base ∆ = {ri | i ∈ I} Z-partitioned in (∆0, . . . , ∆n).

Output: A set of κ-i for i ∈ I.

• 1: ηlex2c ∆0 = 1
• 2: ηi = ηlex2c ∆0 for every ri ∈ ∆0
• 3: for 1 ⩽ k ⩽ n do
• 4: ηlex2c ∆k = (|∆k-1| +1) × ηlex2c ∆k-1
• 5: ηi = κlex2c ∆k for all ri ∈ ∆k;
• 6: end for

[Kern-Isberner et al., 2020]). Given the results shown in the previous section, we can thus say that lexicographic inference and c-representations are two inductive inference methods of very high quality. In order to obtain a precise view on these two high-quality inductive inference relations, we investigate the exact relationship between c-representations and lexicographic inference in this section. The comparison between lexicographic inference and c-representations was started in [Strotkamp, 2020], where an algorithm (Algorithm 1) originally proposed in [Bourne and Parsons, 1999] was adapted to an algorithm that generates, given a conditional belief base ∆, an OCF κ that (1) is a c-representation of ∆ and (2) preserves lexicographic inference, i.e. for any ω, ω′ : ω ≺lex ∆ ω′ iff κ(ω) < κ(ω′ ). In more detail, given a belief base ∆ (Zpartitioned into (∆0, . . . , ∆n)), we use Algorithm 1 to calculate ηi for any rule ri ∈ ∆. We can then obtain the rank of any ω ∈ Ω by setting:

[Strotkamp, 2020] shows that this algorithm results in a crepresentation that captures lexicographic inference:

Proposition 2. (1) κclex (as defined in Equation 6) forms a c-representation of ∆. (2) For any ω, ω′ ∈ Ω, κclex (ω) ⩽ κclex (ω′ ) iff ω ⪯lex ω′ .

However, this does not imply that ⪯lex can be unambiguously equated with (a subclass of) c-representations. Indeed, the algorithm from [Strotkamp, 2020] might give rise to nonconvex OCFs, i.e. OFCs with "empty" layers. One might wonder whether it is also possible to construct a convex crepresentation equivalent to lexicographic inference. This question is answered negatively:

Proposition 3. There exist conditional belief bases ∆ s.t. there is no c-representation κ : Ω → N for ∆ s.t. (1) κ-1 (i) ̸= ∅ implies κ-1 (i - 1) ̸= ∅ for any i ∈ N, (2) ηi ∈ Q+ for every ri ∈ ∆, and (3) κ(ω) ⩽ κ(ω′ ) iff ω ⪯lex ω′ for any ω, ω′ ∈ Ω.

5 Syntax Splitting and the Drowning Problem

The main result of this paper (Theorem 1) is that lexicographic inference satisfies syntax splitting, which means that it is the first RC-extending inference relation shown to satisfy syntax splitting (since c-representations are incomparable with system Z [Beierle et al., 2018] and system Z itself does not satisfy syntax splitting (see Example 4). To the best of our knowledge, lexicographic inference and crepresentations are also the only two inductive inference operators known to avoid the drowning effect.

We start by recalling the drowning problem:

Example 5 (The Drowning Problem). The drowning problem is illustrated by using the following conditional belief base ∆ = {(f|b), (b|p), (¬f|p), (e|b)}, which represents the Tweety-example together with the additional conditional "birds typically have beaks" ((e|b)). The drowning problem is constituted by the fact that some inductive inference operators, such as system Z, do not allow to infer that penguins typically have beaks (p |∼ Z∆b), i.e. the fact that penguins are abnormal when it comes to flying blocks or drowns inferences about penguins with beaks. It can be verified that lexicographic inference and c-representations do not suffer from the drowning problem.

As lexicographic inference and c-representations are at the same time (1) the only two inductive inference operators that avoid the drowning effect and (2) the only two inductive inference operators that have been shown to satisfy syntax splitting, we investigate connections between these two properties in this section. Indeed, since the drowning effect is, essentially, caused by unrelated information (e) influencing inferences, and the two only inductive inference operations known to satisfy syntax splitting also are the two only known inductive inference relations known to avoid the drowning effect, we might conjecture there is an intimate relationship between syntax splitting and the drowning effect. The answer to this question is negative. We show this by constructing an inductive inference relation, systemZ ind , that satisfies syntax splitting and is RC-extending, yet still suffers from the drowning problem.

For this, we first recall the concept of a finest syntax splitting [Parikh, 1999], adapted to our setting of conditional belief bases.

Definition 6. Given a conditional belief base ∆, and Σ1, . . . ,Σn s.t. ⋃ni=1 Σi and Σi ∩ Σj ̸= ∅ for every i, j = 1, . . . , n s.t. i ̸= j, Σ1, . . . ,Σn splits ∆ iff ∆i ⊂ (L(Σi)|L(Σi)) for every i = 1, . . . , n and ∆ = ⋃ni ∆i . We also say Σ1, . . . , Σn is a splitting of ∆.

Given two partitions Σ1, . . . , Σn and Σ′1 , . . . , Σ′m of Σ, we say that Σ1, . . . ,Σn is finer than Σ′1 , . . . ,Σ′m iff for every 1 ⩽ i ⩽ n, there is some 1 ⩽ j ⩽ m s.t. Σi ⊆ Σj .

It can be easily shown, similarly to [Parikh, 1999, Lemma 1], that every conditional belief base admits a unique finest splitting. We define the system Z ind -TPO based on a variation of the lexicographic vectors defined in section 2.5. In particular, instead of counting the number rules in a part ∆i of the partition ∆1, . . . , ∆n, we now use V ′ (ω, ∆′ ) to count for how many sub-alphabets of the finest splitting Σ1, . . . , Σm of ∆, a rule in ∆′ is violated by ω. More formally:

Definition 7. Given a conditional belief base ∆ partitioned in (∆0, . . . , ∆n) with finest splitting Σ1, . . . , Σm, Θ ⊆ ∆ and

ω ∈ Ω(Σ), we define:

We can then define ⪯Zind ∆ over Ω as: ω ⪯Zind ∆ ω′ iff Z ind (ω) ⪯lex Z ind (ω′ ). We define System Z ind as the inductive inference operator C tpo ⪯Zind ∆ . We denote C tpo ⪯Zind by C Zind

and the appertaining inference relation C Zind (∆) by |∼ Zind

∆ .

Notice that e.g. Z ind (abc) = 2 since abc(a|⊤) = 0, abc(c|⊤) = 0 and {a, b} and {c} are the finest splitting of ∆. Examples of (non-)inferences include: a |∼ Zind ∆ b ∧ c and ¬(b ∧ c) ̸|∼ Zind ∆ a.

We can see that for this belief base, Z ind is different from lexicographic entailment. Indeed, we have:

System Z ind satisfies syntax splitting:

Theorem 2. SystemZ ind satisfies SynSplit.

We can furthermore show that System Z ind extends System Z and is itself extended by lexicographic entailment:

Proposition 4. (1) System Z ind is RC-extending; and (2) A |∼ Zind ∆ B implies A|∼ lex ∆ B (for any conditional belief base ∆).

Example 6 shows that A |∼ lex ∆ B does not imply A |∼ Zind ∆ B. We now show that system Z ind coincides with system Z if the finest splitting of ∆ is the whole signature Σ. Intuitively, if the whole signature is the finest splitting, V ′ (ω,∆i) ⩽ 1, which means ⪯Zind ∆ will coincide with κZ∆.

Proposition 5. Given a conditional belief base ∆ over the signature Σ with finest splitting Σ, C Zind (∆) = C Z (∆).

Proposition 4 shows that System Z ind is weaker than lexicographic inference. How much weaker? Well, for one, Z ind does still suffer from the drowning problem, as the unique finest splitting of ∆ is the (trivial) splitting {p, b, f, e}, we see that |∼ Zind ∆ = |∼ Z∆ for ∆ as in Example 5 (with Proposition 5). Altogether, this shows that the property of SynSplit is independent of the drowning effect, as Z ind is an inductive inference relation that satisfies SynSplit but suffers from the drowning effect.

Remark 1. The fact that system Z ind satisfies syntax splitting and RC-extending also disproves a potential conjecture about how to characterise lexicographic inference axiomatically, namely by syntax splitting and being RC-extending.

Remark 2. What seems to distinguish System Z ind and lexicographic inference and ensure that the latter does not suffer from the drowning problem is the following property:

Qual says that if ω falsifies strictly fewer conditionals than ω′ , this should be reflected in the ordering ≺∆. Clearly, this is satisfied by lexicographic but not by Z ind - or Z-inference. It is not hard to see that, at least for the Tweety-example, Qual ensures the drowning effect is avoided, as any world ω s.t. ω |= b ∧ ¬e will be ranked strictly higher than any ω′ that agrees with ω on all atoms except w s.t. ω′ |= b ∧ e, as ω′ |= p ∧ b ∧ e implies (e|b)(ω′ ) = 0 and (e|b)(ω) implies ω ≺∆ ω′ . It remains a question for future work to formalize the drowning effect into a general property of inductive inference relations, and to study the conjectured connection between such a property and Qual.

We conclude by noticing that lexicographic inference is neither the least refined (witnessed by Z ind ) nor the most refined RC-extending inference relation that satisfies SynSplit. The following example illustrates the latter claim:

For c-representations of ∆, however, we get the following c-representations:

κc1 and κc2 are both strict refinements of ⪯∆, and therefore are RC-extending. In view of [Kern-Isberner et al., 2020, Proposition 9], κc1 and κc2 satisfy SynSplit.

In this section, we have shown that (1) lexicographic inference is not the only inductive inference relation that is RCextending and satisfies syntax splitting and (2) that there are (RC-extending) inductive inference relations that still suffer from the drowning effect. This points to several open questions in the field of non-monotonic reasoning. First, how to axiomatically characterize lexicographic inference? Secondly, what is the exact relation between notions of independence and relevance on the one hand, and the drowning effect on the other hand. Intuitively, these concepts seem to be on the core of why the drowning effect is undesirable: in the belief base ∆, we have no reasons to assume that having a beak (e) is related to flying (f), once we know that something is a bird (b).

2 An alternative version of Qual is Qual': If {r ∈ ∆ | ω(r) = 0} ⊂ {r ∈ ∆ | ω′ (r) = 0} then ω ≺∆ ω′ . Notice that this version is stronger than our formulation (i.e. Qual implies Qual', but not vice-versa).

6 RelatedWork

Considerations pertaining to relevance and independence in logic are numerous, but the notion of syntax splitting comes from [Kern-Isberner et al., 2020], which was in turn inspired by similar considerations in belief revision [Kern- Isberner and Brewka, 2017b]. Other notions of relevance and syntax splitting in belief revision can be found in [Parikh, 1999; Aravanis et al., 2019] and are compared in depth with syntax splitting in [Kern-Isberner et al., 2020].

To the best of our knowledge, no axiomatic notion of relevance or independence has been studied for lexicographic inference before. Furthermore, System Z Ind has, as far as we know, not been proposed in the literature. This is not surprising, as it was designed to disprove several conjectures on lexicographic inference. There are a couple of nonmonotonic logics that are somewhat related to system Z Ind and lexicographic inference which we mention here. Firstly, System W [Komo and Beierle, 2021] bases inferences on a partial order over worlds obtained by comparing, given a Zpartitionend conditional belief base (∆0, . . . ,∆n, the vector (η0(ω), . . . , ηn(ω)), where ηi(ω) contains the conditionals in ∆i violated by ω. These vectors are compared lexicographically, but using the ⊆-relation instead of the cardinality relation. This results in partial order over worlds, which means, among others, that the resulting inference relation does not satisfy rational monotony. In [Haldimann and Beierle, 2022], it is shown that system W satisfies syntax splitting as well. The exact relationship with lexicographic inference remains a question for future work. Another related logic is System ARS [Ritterskamp and Kern-Isberner, 2008], where so-called tolerance layers are combined lexicographically. However, in [Ritterskamp and Kern-Isberner, 2008], it is shown that lexicographic inference and system ARS are incomparable.

In [Casini et al., 2019], the class of RC-extending inference relations is described. In future work, we plan to give a complete characterisation of the subclass of RC-extending inference relations satisfying syntax splitting.

7 Conclusion

The main results of this paper are the following: (1) lexicographic inference satisfies syntax splitting, thus establishing it as an RC-extending inference relation of high quality; (2) c-representations and lexicographic inference are related, but not identical; (3) syntax splitting does not uniquely characterize lexicographic inference and (4) the drowning problem and syntax splitting are unrelated. The latter negative results point to two open questions, to which we have pointed first suggestions of where to look for answers. Further future work includes taking advantage of syntax splitting in the development of efficient solvers, and the generalization of syntax splitting to first-order and (probabilistic) description logics and richer preferential languages, where lexicographic inference [Casini and Straccia, 2012; Giugno and Lukasiewicz, 2002; Booth et al., 2015] has been applied extensively.

Acknowledgments

The work of Jesse Heyninck was partially supported by Fonds Wetenschappelijk Onderzoek - Vlaanderen (project G0B2221N).