The study of inference operators frequently involves the introduction of properties to which such operators should conform. Amongst other advantages, the property-based approach helps to restrict the range of operators, and to classify and categorise the type of inference being studied. This paper continues this tradition by proposing a number of properties for the class of inductive inference operators. We study the interaction of these properties, both with one another, and with other well-known properties for inductive inference. We also test a number of well-known inductive inference operators against the newly proposed, and some existing properties.
In Knowledge Representation, properties (or postulates) provide a standard, and useful, way of studying inference operators. The use of properties allows us to eliminate approaches regarded as undesirable, thereby restricting the attention to the most relevant operators. Viewed as a form of a top-down approach to characterising inference, they are often used in tandem with more bottom-up methods that focus on constructing inference operators. The interaction between these approaches frequently lead to better insights regarding the type of inference being studied. In addition, properties can be used to classify and categorise diferent approaches to inference, leading to a better understanding of the overall picture.
Two of the best known instances of the use of properties
are the AGM properties for belief change [
In this paper we continue the tradition of employing
properties for the study of inference operators understanding,
and apply it to a specific kind of nonmonotonic inference
operator described by Kern-Isberner et al. [
0000-0002-3825-4052 (J. Heyninck); 0000-0002-6647-6381 (R. Booth);
0000-0003-2204-6969 (T. Meyer)
© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License
Attribution 4.0 International (CC BY 4.0).
tween them, and test some well-known forms of
inductive inference against them.
• We introduce properties constraining model-based
inductive operators to be tightly coupled to the
conditional statements provided in a belief base, and
show that this is incompatible with one of the
notions of equivalence and the property of Syntax
Splitting [
The paper is organized as follows. Section 2 provides the various preliminaries required to present our contributions. Section 3 presents versions of equivalence for inductive inference, and tests this against the newly-added property of being conditional-based. Section 4 presents a version of lexicographic inference that satisfies the notion of pairwise equivalence introduced in the previous section. Section 5 introduces and studies language independence. Section 6 considers related work. Finally, Section 7 concludes and considers future work.
In the following we recall preliminaries on propositional logic, and technical details on inductive inference.
For a set Σ of atoms, let ℒ(Σ) 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 ℒ(Σ) is a function : Σ → {1, 0} where 1 is understood to denote truth, and 0 to denote falsity. Let Ω(Σ) denote the set of all interpretations for Σ . We simply write Ω if the set of atoms is implicitly given, and similarly for ℒ. An interpretation satisfies (or is a model of) an atom ∈ Σ , denoted by |= , if and only if () = 1. The satisfaction relation |= is extended to formulas in the usual way. As an abbreviation we sometimes identify an interpretation with its complete conjunction, i. e., if 1, . . . , ∈ Σ are those atoms that are assigned ⊤ by and +1, . . . , ∈ Σ are those propositions that are assigned ⊥ by we identify by 1 . . . +1 . . . (or any permutation of this). For ⊆ ℒ Mod() = { ∈ Ω(Σ) | = for every ∈ .
(Σ) we also define |
= if and only if
Define the set of models | |= } for every formula or set of formulas . A formula or set of formulas 1 entails another formula or set of formulas 2, denoted by ∈ Ω(Σ) 1 |= 2, if Mod(1) ⊆
Mod(2). Where ⊆ Σ , and , we denote by the restriction of to , i.e. is the interpretation over Σ that agrees with on all atoms in . Where Σ , Σ ⊆ Σ , Ω(Σ Mod() = { ∈ Ω | |= }. for any ∈ N, and likewise Ω , will denote Ω(Σ (for , ∈ N). Likewise, for some ⊆ ℒ (Σ ), we define ∪ Σ ) ) will also be denoted by Ω
Given a language ℒ, conditionals are objects of the form
(|) where , ∈ ℒ. The set of all conditionals based on
a language ℒ is defined as: (ℒ|ℒ) = {(|) | , ∈ ℒ}.
We follow the approach of de Finetti [
0 : |= ∧ ¬ ⎩ : |= ¬ (1) satisfies its (TPOs) ⪯⊆
Ω(Σ) ⊆≺ ′ ̸⪯ denote ⪯
by ≺ words, a possible world verifies a conditional (|) if it satisfies both antecedent and conclusion ( (|)() = 1); it falsifies, or violates
it if it satisfies the antecedent but not the conclusion ((|)() = 0); otherwise the conditional is not applicable, i. e., the interpretation does not satisfy the antecedent ((|)() = ). We say that satisfies a conditional (|) if it does not falsify it, i.e., if material counterpart → . We will look at the semantics of conditionals given both by total preorders Ω(Σ) × Ω(Σ) × Ω(Σ)
and strict partial orders (SPOs) .1 As is usual, given a preorder ⪯ , we ′ and ′ ⪯ by ≈ ′ and ⪯ ′ and ′. Thus, without loss of generality, the following definition applies to both TPOs and SPOs: given a strict order ≺ sibility, we define ≺ there is an ∈ on possible worlds, representing relative plaumin⪯ (Mod()) such that ≺ ′. This if for every ′ ∈ min≺ (Mod()) allows for expressing the validity of conditional inferences via stating that |∼ ≺
if ( ∧ ) ≺ ( ∧ ¬) [
We can marginalize total preorders and even inference operators, i.e., restricting them to sublanguages, in a natural 1A strict partial order is a binary relation that is irreflexive and transitive. A total preorder is a binary relation that is transitive and complete (and therefore reflexive), i.e., 1 ⪯ 2 or 2 ⪯ 1 for all 1, 2. where stands for unknown or indeterminate. In other inference: a marginalized TPO ⪯ |Θ on Ω(Θ) way: If Θ ⊆ Σ then any TPO ⪯ on Ω(Σ) by setting
uniquely induces 1Θ⪯ |Θ 2Θ if 1Θ ⪯ 2Θ.
Note that on the right hand side of the if
condition
above 1Θ, 2Θ are considered as propositions in the
superlanguage ℒ(Ω) . Hence 1Θ ⪯
2Θ is well defined [
induces a marginalized inference by setting |∼ |Θ if |∼ (2) (3) for any , ∈ ℒ(Θ) .
An obvious generalisation of total preorders are ordinal
conditional functions (OCFs), (also called ranking functions)
: Ω
degrees of (im)plausibility of possible worlds and
proposi→ N ∪ {∞} with − 1(0) ̸= ∅. [
In this paper we will be interested in inference operators |∼ Δ parametrized by a finite conditional belief base ∆ . In more detail, such inference operators are induced by ∆ , in the sense that ∆ in |∼ Δ
serves as a starting point for the inferences
. We call such operators inductive inference operators:
Definition 1 ([
Definition 2.
A model-based-based inductive inference operator for strict partial orders is a mapping C that assigns to each conditional belief base ∆ a strict partial order ≺ Δ on Ω s.t. |∼ ≺ Δ for every (|) ∈ ∆ is ensured). A model-based inductive inference operator for total preorders C is defined similarly, by using a TPO ⪯ Δ (i.e., s.t. (DI) instead of an SPO ≺ Δ.
A model-based inductive inference operator for OCFs (on Ω ) is a mapping C 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
include System Z (also called rational closure, [
We now recall a property that has been recently
introduced and studied, syntax splitting [
Definition 3 (Independence (Ind), [
|∼ Δ if |∼ Δ .
Definition 5 (Syntax splitting (SynSplit), [
Thus, (Ind) requires that inferences from one
sublanguage 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. It
has been shown that System Z satisfies (Rel) but not (Ind)
[
We present system as defined by Goldszmidt and Pearl
[
For ∈ ∆ we define: Δ( ) = if ∈ ∆ and OP (∆) =
(∆ 0, . . . , ∆ ). Finally, the ranking function Δ is defined
via: Δ () = max{Δ( ) | () = 0, ∈ ∆ } + 1, with
max ∅ = − 1. The resulting inductive inference operator
Δ is denoted by . System has been shown to be
equivalent to rational closure [
We now illustrate OCFs in general and system in
particular with the well-known “Tweety the penguin”-example.
Example 1. Consider the conditional belief base ∆ =
{( |), (|), (¬ |)}, where is intended to represent being
a bird, represents being able to fly, and represents being a
penguin. ∆ has the following Z-partitioning: ∆ 0 = {( |)}
and ∆ 1 = {(|), (¬ |)}. This gives rise to the following
Δ -ordering over the worlds based on the signature {, , }:
Δ
We recall lexicographic inference as introduced by Lehmann
lex
[
Example 2 (Example 1 ctd.). For the Tweety belief base ∆ as in Example 1 we obtain the following lex()-vectors: lex() lex()
lex() (0,1) (0,0) (1,0) (1,0) (0,2) (0,0) lex() (0,1) (0,0) The lex-vectors are ordered as follows:
(0, 0) ≺ lex (1, 0) ≺ lex (0, 1) ≺ lex (0, 2).
Observe that e.g. ⊤ |∼ lΔex¬ and ∧ |∼ lΔex.
System W is a recently introduced inductive inference operator [21, 18] that takes into account the structural information about which conditionals are falsified.
Definition 6 ( , , preferred structure ≺ wΔ on worlds [18]). For a belief base ∆ = {(|) | ∈ {1, . . . , }} with OP (∆) = (∆ 0, . . . , ∆ ) and for = 0, . . . , , the functions and are given by Δ() := {(|) ∈ ∆ | |= ∧ ¬}, Δ() := {(|) ∈ ∆ | |= ∧ ¬}.
If ∆ is clear from the contex, we drop the subindex and write instead of Δ The preferred structure on worlds is given w by the binary relation ≺ Δ ⊆ Ω × Ω defined by, for any , ′ ∈ Ω , ≺ wΔ ′ if there exists an ∈ {0 , . . . , } such that () = (′) () ⊂ (′) .
∀ ∈ { + 1 , . . . , } and I.e., ≺ wΔ ′ if and only if falsifies strictly fewer (in the set-theoretic sense) conditionals than ′ in the ∆ with the biggest index where the conditionals falsified by and ′ difer. Note that ≺ wΔ is a strict partial order [18, Lemma 3]. Definition 7 (System W, |∼ wΔ[18]). Let ∆ be a belief base and , be formulas. Then is a system W inference from (in the context of ∆ ), denoted |∼ wΔ, if for every ′ ∈ Mod() there is an ∈ Mod() such that ≺ wΔ ′.
Thus, employing Definition 2, since ≺ wΔ is a strict partial order, System W is an SPO-based inductive inference operator w : ∆ ↦→ ≺ wΔ. In fact, System W strictly lies between System Z and lexicographic inference: Proposition 1 ([21, 22]). If is consistent, then |∼ Δ implies |∼ wΔ and |∼ wΔ implies |∼ lΔex , but not vice versa.
Example 3 (Example 1 ctd.). The belief base ∆ from Ex. 1 induces the ≺ wΔ below. We can entail |∼ wΔ as the verifying world is ≺ wΔ-preferred to the only falsifying world , i.e., ≺ wΔ .
w ≺ Δ Definition 8. are:
We first define some preliminaries regarding equivalence. Two conditionals (1|1) and (2|2) are equivalent if every world has the same attitude to both conditionals: i.e. (1|1)() = (2|2)() for every ∈ Ω . This is equivalent to 1 ≡ 2 and 1 ∧ 1 ≡ 2 ∧ 2. Notice that this implies that for any TPO or SPO ⪯ , 1 |∼ ⪯ 1 if 2 |∼ ⪯ 2. We write (1|1) ≡ (2|2) in that case.
We now define the following kinds of equivalence for conditional knowledge bases:
Two conditional knowledge bases ∆ 1 and ∆ 2 • bijective pairwise equivalent if there is a bijection : ∆ 1 → ∆ 2 s.t. ≡ ( ) for every ∈ ∆ 1; • pairwise equivalent if for every 1 ∈ ∆ 1 there is some 2 ∈ ∆ 2 s.t. 1 ≡ 2, and vice versa; • globally equivalent if for every tpo ⪯ , ∆ 1 is valid w.r.t. ⪯ if ∆ 2 is valid w.r.t. ⪯ .
The intuition behind these notions is the following: bijective pairwise equivalence requires that two sets of conditionals have the same size, and that every conditional in one set is equivalent to a conditional in the other set. Pairwise equivalence requires that for every conditional in the first set ∆ 1, we can find an equivalent conditional in ∆ 2, and vice versa, but does not require these sets to have the same size. Finally, global equivalence merely requires that ∆ 1 and ∆ 2 have the same semantic structure, in the sense that they are valid w.r.t. the same TPOs.
These notions are strictly hierarchical: Proposition 2. If ∆ 1 and ∆ 2 are bijectively pairwise equivalent, they are pairwise equivalent, and if they are pairwise equivalent, they are globally equivalent.
Proof. The implication from bijectively pairwise equivalent to pairwise equivalent is immediate. Suppose ∆ 1 and ∆ 2 are pairwise equivalent and that ∆ 1 is valid w.r.t. ⪯ . Consider some (2|2) ∈ ∆ 2. Then with pairwise equivalence, there is some (1|1) ∈ ∆ 1 s.t. (1|1) ≡ (2|2). Since ∆ 1 is valid w.r.t. ⪯ , 1 |∼ ⪯ 1 and thus also 2 |∼ ⪯ 2.
The following example shows global equivalence does not imply pairwise equivalence: Example 4. Consider ∆ 1 = {(|), (|)} and ∆ 2 = {(∧ |)}. Then clearly ∆ 1 and ∆ 2 are globally equivalent but not pairwise equivalent.
The following example shows pairwise equivalence does not imply bijective pairwise equivalence: Example 5. Consider ∆ 1 = {(|)} and ∆ 2 = {(|), (∧ |)}. Then clearly ∆ 1 and ∆ 2 are pairwise equivalent but not bijectively so.
The following properties express that an inductive inference operator satisfies a given notion of equivalence:
Let an inductive inference operator C be given.
Definition 9.
Then C: • satisfies bijective pairwise equivalence if for any two bijective pairwise equivalent knowledge bases ∆ 1 and ∆ 2, C(∆ 1) = C(∆ 2). • satisfies pairwise equivalence if for any two pairwise equivalent knowledge bases ∆ 1 and ∆ 2, C(∆ 1) = C(∆ 2). • satisfies global equivalence if for any two pairwise globally equivalent knowledge bases ∆ 1 and ∆ 2, C(∆ 1) = C(∆ 2).
In other words, an inductive inference operator C satisfies [bijective] pairwise [global] equivalence if for any [bijective] pairwise [globally] equivalent knowledge bases ∆ 1 and ∆ 2, |∼ Δ1 if |∼ Δ2 . Notice that satisfying global equivalence is the strongest property, and satisfying bijective pairwise equivalence the weakest (this is an immediate consequence of Proposition 2).
We now commence the study of the satisfaction of
equivalence for the inductive inference operators introduced above,
moving from strongest result to weakest result. The first
result concerns System Z:
Proposition 3. System Z satisfies global equivalence.
Proof Sketch. Pearl [
We now move to System W, showing it satisfies pairwise equivalence. We first show some preliminary results The first result shows that tolerance is satisfied by pairwise equivalent conditional knowledge bases.
Lemma 1. Let some conditional and two pairwise equivalent conditional knowledge bases ∆ 1 and ∆ 2 be given. Then ∆ 1 tolerates if ∆ 2 tolerates .
Proof. Suppose ∆ 1 tolerates . Then there is an ∈ Ω s.t. ( ) = 1 and for every 1 ∈ ∆ 1, ( 1) ̸= 0. Consider some 2 ∈ ∆ 2. Since ∆ 1 and ∆ 2 are pairwise equivalent, there is a 1 ∈ ∆ 1 s.t. 1 ≡ 2. As ( 1) ̸= 0, also ( 2) ̸= 0. Thus, ∆ 2 tolerates .
The next result builds on Lemma 1 to show that two pairwise equivalent conditional knowledge bases generate identical ordered partitions (up to pairwise equivalence). Lemma 2. Let two pairwise equivalent conditional knowledge bases ∆ 1 and ∆ 2 with OP (∆ ) = (∆ 1 , . . . , ∆ ) (for = 1, 2) be given. Then 1 = 2 and ∆ 1 is pairwise equivalent with ∆ 2 for 1 ⩽ ⩽ 1.
Proof Sketch. This is shown by an easy induction on (using Lemma 1).
Lemma 2 can then be used to prove that System W satisifes pairwise equivalence.
Proposition 4. System W satisfies pairwise equivalence. Proof. Suppose ∆ 1 and ∆ 2 are pairwise equivalent. Let OP (∆ ) = (∆ 1 , . . . , ∆ ) (for = 1, 2). Then with Lemma 2, 1 = 2. We therefore denote 1(= 2) by .
We first show the following ( †): if ∆ 1 and ∆ 2 are pairwise equivalent, then for any ∈ Ω ,
Δ1 () = { 1 ∈ ∆ 1 | 1 ≡ 2 for some 2 ∈ Δ2 ()}. This is shown as follows. Suppose 1 ∈ Δ1 . Then there is some 2 ∈ ∆ 2 (in view of Lemma 2) s.t. 2 ≡ 1, which implies 2 ∈ Δ2 . Thus, Δ1 () ⊆ { 1 ∈ ∆ 1 | 1 ≡ 2 for some 2 ∈ Δ2 ()}. Furthermore, for every 2 ∈ Δ2 there is a 1 ∈ Δ1 () s.t. 1 ≡ 2. Thus, Δ1 () ⊇ { 1 ∈ ∆ 1 | 1 ≡ 2 for some 2 ∈ Δ2 ()}
We now show that (‡): for any pairwise equivalent ∆ 1 and ∆ 2 and any 1, 2 ∈ Ω , Δ1 (1) ⊆ Δ1 (2) implies Δ2 (1) ⊆ Δ2 (2). Indeed, suppose that 2 ∈ Δ2 (1). Then there is some 1 ∈ ∆ 2 s.t. 1 ≡ 1. With †, 1 ∈ Δ1 (1) and thus 1 ∈ Δ1 (2). But then with †, 2 ∈ Δ2 (2).
We now show that for any 1, 2 ∈ Ω , 1 ≺ Δ1 2 if 1 ≺ Δ1 2. Suppose for this that 1 ≺ Δ1 2, i.e. there is some 1 ⩽ ⩽ s.t. Δ1 (1) = Δ1 (2) for every > , and Δ 1 (1) ⊂ Δ 1 (2). With ‡, Δ2 (1) = Δ2 (2) for Altogether, this shows that |∼ Δ1 if |∼ Δ2 . every > , and Δ 2 (1) ⊂ Δ 2 (2). Thus, 1 ≺ Δ2 2.
We’ll see in the next section (Proposition 9) that a similar result can not be obtained for global equivalence, though.
We finally turn to lexicographic inference. Perhaps somewhat surprisingly, we observe that lexicographic inference does not even satisfy pairwise equivalence: Proposition 5. Lexicographic inference does not satisfy pairwise equivalence.
Proof. Consider the following conditional knowledge bases: ∆ 1 ={(|), (|)} ∆ 2 =∆ 1 ∪ {( ∧ |)}. ∆ 1 and ∆ 2 are pairwise equivalent. It is easy to see that OP (∆ 1) = (∆ 1) and OP (∆ 2) = (∆ 2). Thus, the lexicographic vectors for the worlds and are determined as follows: (, ∆ 1) = 1, (, ∆ 2) = 1, since |= ∧ ¬; (, ∆ 1) = 1, (, ∆ 2) = 2, since ∧ ¬ ∧ ¬( ∧ ). |= This means that ≈ lΔex1 whereas ≺ lΔex2 .
Notice that the example used in this proof is also a violation of the property of Cut when applied to conditionals: if |∼ Δ then C(∆ ∪ {(|)}) ⊆ C(∆) . This rule says that if we add a conditional to ∆ that is already inferred on the basis of ∆ - such as ( ∧ |) being added to ∆ 1 above then this should not lead to the inference of any new conditionals. In the above we have, e.g., ∧ ( ↔ ¬) ̸ |∼ Δ1 but ∧ ( ↔ ¬) |∼ Δ2 .
Despite violating pairwise equivalence, lexicographic inference satisfies bijective pairwise equivalence: Proposition 6. Lexicographic inference satisfies bijective pairwise equivalence.
Proof. This is immediate from the fact that for any two bijective pairwise equivalent ∆ 1 and ∆ 2, (, ∆ 1) = (, ∆ 2) (for any ∈ Ω(Σ) ).
Arguably, the failure of lexicographic inference to satisfy pairwise equivalence is undesirable, as it means that the number of (equivalent) conditionals in a knowledge base has an efect on the inferences from the knowledge base. To overcome this defect, we will propose a variant of lexicographic inference that avoids this in Section 4.
We now show a more general result that shows that the satisfaction of global equivalence is perhaps too strong of a requirement, in the sense that it is incompatible with another property deemed desirable for inductive inference operators, namely syntax splitting. To show this, we will assume another property, namely conditional-basedness, which expresses that worlds that have exactly the same attitudes w.r.t. the inducing set of condintionals should not be distinguished. Intuitively, in inductive inference, the only information that is relevant is the set of conditionals the inductive inference operator is based on.
Definition 10. A model-based inductive inference operator C for TPOs is conditional-based if, for any 1, 2 ∈ Ω , if ( )(1) = ( )(2) for every ∈ ∆ then 1 ≈ Δ 2.
A similar property can be defined for model-based inductive inference operators on SPOs and OCFs.
Notice that this is a rather harmless property, in the sense that any of the inductive inference relations studied in this paper satisfy it: Proposition 7. System Z, lexicographic inference and System W are conditional-based.
We can now show that, in the context of conditionalbased inductive inference operators, global equivalence and Ind are jointly incompatible.
Proposition 8. There exists no conditional-based inductive inference operation that satisfies global equivalence and satisifes (Ind). ⊤ |∼ {}), and likewise, ⊤ |∼ CΔ1 .
Proof. Suppose that C satisfies global equivalence and satisfies syntax splitting.
Consider first ∆ 1 = {(|⊤), (|⊤)}. With (DI), CΔ1 (which implies ≺ for any ∈ Ω ∖ Then since ∆ 1 = {(|⊤)} ⋃︀{},{}{(|⊤)}, ⊤ ∧ ¬ |∼ CΔ1 by (Ind). This means that ≺ CΔ1 . With symmetry, we establish that ≺ CΔ1 .
Consider now ∆ 2 = {( ∧ |⊤)}. Notice that ∆ 1 and ∆ 2 are globally equivalent. Thus, since C satisfies global equivalence, ≺ CΔ1 =≺ CΔ2 . However, as (( ∧ |⊤))() = C ((∧|⊤))() = ((∧|⊤))() = 0, we see that ≈ Δ2
C ≈ Δ2 , contradiction.
Notice that global equivalence is only incompatible with
part of (SynSplit), in particular, with the property of (Ind).
Indeed, as system Z satisfies (Rel) [
We conclude this section with a result following from Proposition 8 (and the fact that System W satisfies (SynSplit) ([20]) and is conditional-based (Proposition 7)). Proposition 9. System W does not satisfy global equivalence.
Obtaining a variant of lexicographic inference that satisfies pairwise equivalence is rather straightforward. Instead of counting which conditionals are violated by a world, we count which conditionals are violated up to equivalence. In more detail, we observe that equivalence of conditionals is an equivalence relation over (ℒ|ℒ), and thus, as usual, we define the equivalence class of a conditional (|) as [(|)] = {(|) ∈ (ℒ|ℒ) | ≡ and ∧ ≡ ∧ }. We can now count the violations of conditionals in ∆ by up to equivalence as: ≡ (, ∆) :=
|{[(|)] | (|)() = 0, (|) ∈ ∆ } It is easy to observe that ≡ (, ∆) ⩽ (, ∆) for any and set of conditionals ∆ . We can now define, for ∆ with OP (∆) = (∆ 0, . . . , ∆ ), lex≡ () = ( ≡ (, ∆ 0), . . . , ≡ (, ∆ )). We furthermore let 1 ⪯ lΔex,≡ 2 if lex≡ (1) ⪯ lex lex≡ (2). We denote the corresponding inductive inference relation by lex,≡ We illustrate this with an adapted Tweety-Example: Example 6. Let ∆ = {( |), (|), (¬ |), (¬ ∧ |)}. Notice that (¬ ∧ |) ≡ (¬ |) We have the following lexand lex≡ -vectors: lex() lex≡ () lex() lex≡ () We see that e.g. ≺ lΔex yet ≈ lΔex,≡ . This means that ∧ ¬( ∧ ¬ ) |∼ lΔex whereas ∧ ¬( ∧ ¬ ) ̸ |∼ lΔex,≡ .
We note firstly that this inference relation lies between System Z and lexicographic inference: Proposition 10. For any conditional knowledge base ∆ , |∼ Δ implies |∼ lΔex,≡ and |∼ lΔex,≡ implies |∼ lΔex
Proof. Immediate from the fact that ⪯ lΔex,≡ extends Δ and ⪯ lΔex extends ⪯ lΔex,≡ (as ≡ (, ∆) ⩽ (, ∆) for any ).
The next proposition show that this inference relation is quite well-behaved in the sense that it satisfies pairwise equivalence and syntax splitting.
Proposition 11. lex,≡ satisfies pairwise equivalence. Proof. Immediate from the fact that for any pairwise equivalent ∆ 1 and ∆ 2, ≡ (, ∆ 1) = ≡ (, ∆ 2).
Proposition 12. lex,≡ satisfies SynSplit.
Proof sketch. The proof is essentially the same as that of Theorem 1 by Heyninck et al. [19], with the exception of Lemma 10, which we adapt to lex,≡ : Lemma 3. Let a conditional belief base ∆ = ∆ 1 ⋃︀Σ1,Σ2 ∆ 2 with its corresponding Z-partition (∆ 0, . . . , ∆ ) be given. Then for every 0 ⩽ ⩽ , ≡ (, ∆ ) = ≡ (1, ∆ 1 ) + ≡ (2, ∆ 2 ).2 Proof. Take some 0 ⩽ ⩽ . Since ∆ = ∆ 1 ⋃︀Σ1,Σ2 ∆ 2, (|) ∈ ∆ if (|) ∈ ∆ 1 or (|) ∈ ∆ 2 . Furtthheartm(or|e,)sin∈ce ∆ Σ 11 ∩andΣ 2(|) ∈ ∆ 2 . Observe now = ∅, it cannot be the case that: ≡ (, ∆ ) = |{[(|)] ∈ ∆ | |= ∧ ¬}| = |{[(|)] | 1 |= ∧ ¬ and (|) ∈ ∆ 1 }| ∪ |{[(|)] | 2 |= ∧ ¬ and (|) ∈ ∆ 2 }|. Thus: ≡ (, ∆ ) = ≡ (1, ∆ 1 ) + ≡ (2, ∆ 2 ), because {[(|)] | 1 |= ∧ ¬ and (|) ∈ ∆ 1 } ∩ {[(|)] | 2 |= ∧ ¬ and (|) ∈ ∆ 2 } = ∅.
This completes the proof of Proposition 12.
Furthermore, it should be noticed that, as Clex,≡ is a model-based inductive inference operator for strict partial orders, it satisfies all the so-called KLM-postulates, including rational monotony.
A final property of inductive inference operators we study is the property of language independence. This property intuitively states that inductive inference should be independent of how exactly atoms are expressed. For example, it should not matter whether we represent two atoms as and or and . More generally, in many cases, atoms can be equivalently represented as complex formulas and vice versa. For example, one can represent “I don’t have a dog” by or ¬. This idea is formalized by Marquis and Schwind [23] by defining a symbol translation as any mapping : Σ → ℒ(Σ ′). We can extend such a translation to formulas by simply defining () the formula obtained by substituting any ∈ Σ by () in , and for any conditional knowledge base ∆ we denote by (∆) the knowledge base obtained by replacing each ( | ) in ∆ by ( () | ()). We restrict attention to a specific class of symbol translations. 2Notice that it follows from Fact ?? that, given the Z-partition (Δ1, . . . , Δ) of Δ and Σ ⊆ Σ, Δ = Δ ∩ (ℒ|ℒ) for any 0 ⩽ ⩽ .
Definition 11. A mapping : Σ → ℒ(Σ ′) is a beliefamount preserving symbol translation (in short, a BAPtranslation) if there is a bijection : Ω(Σ) → Ω(Σ ′) s.t. for every ∈ ℒ(Σ) Mod( ()) = { () | ∈ Mod()}.
The idea is that a symbol translation is a way of translating every atom to a formula such that the images of atoms are semantically equivalent (in the new language) to their originals: every world in the original language corresponds to exactly one world in the translated language. Example 7. Consider Σ = {, } and the symbol translation () = and () = ↔ . Then we have the following translations of Ω(Σ) : () () () () = = = =
∧ ↔ ∧ ¬( ↔ ) ∧ ( ↔ ) ∧ ¬( ↔ ) (= ) (= ) (= ) (= ) We thus see that the bijection with () = , () = and that maps and to their selves is a bijection that ensures is a BAP-translation.
We are now ready to state what it means for an inductive inference operator to satisfy language independence—it should be invariant under BAP symbol translation. Definition 12. An inductive inference operator C satisifes language independence if for every BAP-translation , |∼ Δ if () |∼ (Δ) ().
On the level of TPOs, we obtain the following representation of language independence (variants for OCFs and SPOs are obtained similarly): Proposition 13. A model-based inductive inference operator for TPOs C satisfies language independence if for every BAPtranslation : Σ 1 → Σ 2, and any conditional belief base ∆ over ℒ(Σ 1), 1 ⪯ Δ 2 if (1) ⪯ (Δ) (2). Proof. Suppose that for every BAP-translation : Σ 1 → ℒ(Σ 2), and any conditional belief base ∆ over Σ 1, 1 ⪯ Δ 2 if (1) ⪯ (Δ) (2). Suppose now that |∼ Δ, i.e. min⪯ Δ (Mod()) ⊆ Mod(). As the order of ⪯ Δ is preserved over , min⪯ (Δ) (Mod( ())) = { () | ∈ min⪯ Δ ()}. As is BAP-translation, { () | ∈ min⪯ Δ ()} ⊆ Mod( ()). Thus, min⪯ (Δ) (Mod( ())) ⊆ Mod( ()) which implies () |∼ (Δ) (). The proof of the opposite direction ( () |∼ (Δ) () implies |∼ Δ) is similar.
When are inductive inference operators language independent? We delineate a condition that ensures language independence (as well as generalising the property of being conditional-based), which we call conditional-functional. Intuitively, this property requires that an induced consequence relation C(∆) only depends on the attitudes worlds have w.r.t. conditionals. Formally defining this property turned out to be rather intricate, and we do so below in full detail. Intuitively, the idea is that we are interested in inference operators that only depend on vectors ⟨1, . . . , ⟩ of attitudes of worlds to conditionals.
In more formal detail, we let an -dimensional vector mass distribution (VMD) for a signature Σ be a function : {1, 0, } ↦→ N s.t. Σ ⃗ ∈{1,0,} ⃗( ) = 2|Σ|. Intuitively, a VMD is a function that keeps track of how many and ⃗( ) = 0 for all remaining⃗ ∈ {1, 0, }.
Furthermore, system Z for this instance is captured by ( ) = (, ⊑) with = ⃗{ | ⃗( > 0} and ⟨, , ⟩, ⟨1, , ⟩ ⊑ ⟨0, , ⟩, ⟨0, 1, 1⟩ ⊑ ⟨1, 1, 0⟩, ⟨, 0, 0⟩, ⟨, 0, 1⟩.
The next result shows that for TPO-based inductive inference operators, being conditional-functional implies satisfying bijective pairwise-equivalence and language independence. times every vector of attitudes occurs. This can be seen as a placeholder for a conditional knowledge base, in the sense that this is the only information about a conditional knowledge base that should be of interest for a conditionalfunctional inductive inference operator that looks solely at the attitudes of worlds w.r.t. conditionals. We can now define conditional-funtionality: Definition 13. An inductive inference operator C is conditional-functional if there is a function that returns, for any and any VMD , a pair (, ⊑) where: 1. ⊆ { 1, 0, }, 2. ⊑ is a TPO on . such that: •⃗ ∈ implies ⃗( ) > 0, and • for any permutation on {1, . . . , }, ( ) = () and⃗ ⊑ ( ) ⃗ if − 1⃗( ) ⊑ − 1(⃗ ) and such that 1 ⪯ Δ 2 if ⟨ 1(1), . . . , (1)⟩ ⊑Δ ⟨ 1(2), . . . , (2)⟩, where ∆ = { 1, . . . , } and Δ⃗( ) = |{ ⃗| = ⟨ 1(), . . . , ()⟩}|.
The intuition behind this definition is the following: C should depend only on attitudes of worlds w.r.t. conditionals. That is, we should be able to formulate it on basis of the VMD alone. This is formalized by the condition that 1 ⪯ Δ 2 if ⟨ 1(1), . . . , (1)⟩ ⊑Δ ⟨ 1(2), . . . , (2)⟩ for some function generating TPOs over the attitude-vectors that depends only on the VMD. Furthermore, the exact ordering of the conditionals in a conditional knowledge base should not matter. Hence the requirement of invariance under permutations.
Example 8. We start with the conditional belief base from Example 1 and show how it can be interpreted in terms of a 3VMD. We first recall that the worlds have the following attitudes w.r.t. the conditionals 1 = ( |), 2 = (|) and 3 = (¬ |): ( 1) ( 2) ( 3) ( 1) ( 2) ( 3)
This means that we can view this knowledge base as the 3VMD defined by: ⃗ ⃗( ) ⃗ ⃗( ) based, and () = () for any ∈ Ω(Σ) diately implies that 1 ⪯ Δ 2 if (1) ⪯ (Δ) (2) for As C is conditional, this immeany 1, 2 ∈ Ω(Σ)
.
Next we show the satisfaction of bijective pairwise equivalence. For this, consider two knowledge bases ∆ 1 = { 1, . . . , } and ∆ 2 = { 1′, . . . , ′} that are bijectively pairwise equivalent, where is the bijection : ∆ 1 ↦→ ∆ 2 for every ∈ ∆ 1
. Then clearly, for ev, () = ( )() (by definition of bijecs.t. ( ) ≡ ery ∈ Ω(Σ) ing to ⊑. This concludes the proof. tive pairwise equivalence). Thus, ⟨ 1(), . . . , ()⟩ = ⟨ ( 1)(), . . . , ( )()⟩. As is invariant under permutations on {1, . . . , }, ⟨ ( 1)(), . . . , ( )()⟩ and ⟨ 1′(), . . . , ′()⟩ get assigned the same position accord
The final result in this section shows the converse—for TPO-based inductive inference operators, satisfying bijective pairwise equivalence and language independence implies being conditional-functional.
Proposition 15. If a TPO-based inductive inference operator C satisfies bijective pairwise equivalence and language independence then it is conditional-functional.
Proof. Given C satisfying bijective pairwise equivalence and language independence, we must construct from C such that C = C. Let be a VMD of dimension . We must specify and ⊑. Our strategy will be to construct from a particular conditional belief base ∆ of size and then use C(∆ ) to define and ⊑. As a first step, let ⟨1, . . . , 2 ⟩ be an arbitrary enumeration of the interpretations and let⃗⟨ 1, . . .⃗, ⟩ be an enumeration of the set of al⃗l such that ⃗( ) > 0, ordered lexicographically under the assumption 0 < < 1. We now choose some way to distribute the⃗ among the interpretations. A concrete way to do this is to set up a function assigning to each interpretation a vecto⃗r as follows: () =⃗ where is min. s.t. ∑︁ ⃗( ) ⩾ ⩽ In other words, assign⃗ 1 to the first ⃗( 1) interpretations in ⟨1, . . . , 2 ⟩, then assign⃗ 2 to the next ⃗( 2) interpretations in the list, and so on. Then let ∆ = {(1|1), . . . , (|)}, where, for each = 1, . . . , : = ⋁︁{ | th element of () is 0 or 1} = ⊥ ∨
⋁︁{ | th element of () is 1} and ⊑ are specified as follows:
Now let |∼ * = C(∆ ) with ⪯ * its associated TPO. Then = ⃗{ | ̸ |∼ * ⊥ for some s.t. () = ⃗ } and, for any 1, 2 ∈ {1, . . . , },
∈ implies ⃗( ) > 0]: clear from construction. 2. [for any permutation on {1, . . . , }, ( ) = () ⊑ ( ) ⃗ if ⃗( )
⊑ (⃗ )]:
Let be a permutation on {1, . . . , }, i.e. there is a bijection : {1, . . . , } ↦→
{1, . . . , } s.t. for every ⟨ 1, . . . , ⟩ ∈ {1, 0, }, ( 1, . . . , ⟩) = ⟨ (1), . . . , ()⟩. Define ⟨ ( ) by ( )(⟨ 1, . . . , ⟩) = ( − 1( 1, . . . , ⟩)). ⟨ We now show the construction is invariant under . Let ′ be the assignment of vectors to worlds relative to the VMD ( ). We start by defining a bijection : Ω(Σ) s.t. for every ∈ Ω(Σ)
, () = ′ implies that () ∈ − 1(′(′)). Notice that by the definition of ′ and the construction above, such a bijection is guaranteed to exist (but might not be unique). Intuitively, maps every world to one of its -counterparts ′ (i.e. corresponds to the vector⃗ and ′ corresponds to the vector ⃗( )). Define ↦→ Ω(Σ) now : Σ ↦→ ℒ(Σ)
by () = ⋁︀{ () | ∈ Mod()}. pairwise equivalent to (∆ ) It can be easily checked that this is a BAP-translation. Furthermore, it can be easily seen that: (†): ∆ ( ) is bijectively
We now show that ( ) = (). Suppose first that ⃗ ∈ ( ), i.e. ̸ |∼
C Δ ⊥ for some s.t. () =⃗ . As is a BAP-translation and C is language independent, satisfies bijective pairwise equivalence and in view of
C () ̸ |∼ (Δ )⊥ and thus () ∈ (). As () = () and ′( ()) = (()) = ⃗( ) (by construction of ), we see that ⃗( ) ∈ (). The opposite direction is similar. (†),
Suppose first that ⃗ ⊑ ( ) ⃗ if ⃗( ) ⊑ (⃗ ).
⊑ ( ) ⃗ , i.e. there are some ⃗ , ⃗
for 3.[1 with () = for =⃗ , ⃗ and ⃗ ≺ Δ C is a BAP-translation and C is language independent, ⃗ . As satisfies bijective pairwise equivalence and in view of (†),
C (⃗ ) ≺ (Δ ) (⃗ ). As ′( ()) = (()) = (⃗) = ⃗ , ⃗ (by construction of ), we see that ⃗( ) ⊑ (⃗ ). The opposite direction is similar. ⪯ Δ 2 if
⟨ 1(1), . . . , (1)⟩ Δ⃗( ) = |{ |⃗ ⟨ 1(2), . . . , (2)⟩, where ∆ =
{ 1, . . . , } = 1(), . . . , ()}|]: This can ∈ Ω 1 ∖ be easily seen by observing the following: for every 0. (iii.) This can only happen if ̸∈ Ω 1, which implies the ℎ element of () is . As this exhausts all the options, this is suficient to show the claim. ⃗
We must now show that C = C. So let { 1, . . . , } be a conditional belief base. For each = 1, . . . , 2, let = ⟨ 1(), . . . , ()⟩ and let be a permutation on {1, . . . , 2} such that the sequence ⟨⃗ (1), . . . , ⃗ (2)⟩ is sorted lexicographically. Let be the BAP-translation corresponding to . Then, since C satisfies language independence, we have: |∼ Δ if () |∼ (Δ) () ⊑Δ and
Based on their construction, we strongly expect that system Z, lexicographic inference and system W are conditional functional, but a rigorous proof is left to the next version of this work.
While there are several works related to the work we have
done in this paper [
This paper continues a tradition of studying inductive inference operators using properties. Table 1 summarizes the main findings of our work. More specifically, it considers the inductive inference operators System Z, System W, lexicographic inference, and the variation of lexicographic inference introduced in Section 4, and shows, for each of them, whether or not they satisfy the properties of Independence, Relevance, Global Equivalence, Pairwise Equivalence, Conditional-Based, and Language Independence.
System Z
System W Independence Relevance Global Eq.
Pairwise Eq.
Bij. Pairwise Eq.
Cond.-based
× ([
Lex ∨ ([19]) ∨ ([19])
× × ∨ ∨ ∨
Lex≡ ∨ ∨ ∨ ∨
We see several avenues for future work. An obvious direction is to study other inductive inference operators, such as c-representations [17], relevant closure [26], disjunctive rational closure [27] or Weydert’s many System J-variants [24]. Another avenue for future work is to see whether these postulates can also be helpful in characterising inductive inference operators. [17] G. Kern-Isberner, Handling conditionals adequately in uncertain reasoning and belief revision, Journal of Applied Non-Classical Logics 12 (2002) 215–237. [18] C. Komo, C. Beierle, Nonmonotonic reasoning from conditional knowledge bases with system W, Ann.
Math. Artif. Intell. 90 (2022) 107–144. [19] J. Heyninck, G. Kern-Isberner, T. Meyer, Lexicographic Entailment, Syntax Splitting and the Drowning Problem, in: L. D. Raedt (Ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Austria, 23-29 July 2022, ijcai.org, 2022, pp. 2662–2668. URL: https://doi.org/10.24963/ijcai.2022/369. doi:10. 24963/ijcai.2022/369. [20] J. Haldimann, C. Beierle, Inference with System W Satisfies Syntax Splitting, in: G. Kern-Isberner, G. Lakemeyer, T. Meyer (Eds.), 19th International Conference on Principles of Knowledge Representation and Reasoning, KR 2022, Haifa, Israel., 2022, pp. 405–409. [21] C. Komo, C. Beierle, Nonmonotonic Inferences with Qualitative Conditionals Based on Preferred Structures on Worlds, in: U. Schmid, F. Klügl, D. Wolter (Eds.), KI 2020: Advances in Artificial Intelligence - 43rd German Conference on AI, volume 12325 of LNCS, Springer, 2020, pp. 102–115. [22] J. Haldimann, C. Beierle, Properties of System W and Its Relationships to Other Inductive Inference Operators, in: I. Varzinczak (Ed.), Foundations of Information and Knowledge Systems - 12th International Symposium, FoIKS 2022, volume 13388 of LNCS, Springer, 2022, pp. 206–225. [23] P. Marquis, N. Schwind, Lost in translation: Language independence in propositional logic–application to belief change, Artificial Intelligence 206 (2014) 1–24. [24] E. Weydert, System JLZ–rational default reasoning by minimal ranking constructions, Journal of Applied Logic 1 (2003) 273–308. [25] G. Kern-Isberner, J. Heyninck, C. Beierle, Conditional Independence for Iterated Belief Revision, in: L. D. Raedt (Ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, ijcai.org, 2022, pp. 2690–2696. URL: https://doi.org/10.24963/ijcai.2022/373. doi:10. 24963/ijcai.2022/373. [26] G. Casini, T. Meyer, K. Moodley, R. Nortjé, Relevant closure: A new form of defeasible reasoning for description logics, in: Logics in Artificial Intelligence: 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings 14, Springer, 2014, pp. 92–106. [27] R. Booth, I. Varzinczak, Conditional inference under disjunctive rationality, in: Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, 2021, pp. 6227–6234.