The Role of Syntax in Inductive Inference: A Property-Based Study Jesse Heyninck1,3 , Richard Booth2 and Thomas Meyer3 1 Open Universiteit, the Netherlands 2 Cardiff University, United Kingdom 3 University of Cape Town and CAIR, South Africa Abstract 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. Keywords inductive inference, lexicographic inference, properties 1. Introduction tween them, and test some well-known forms of inductive inference against them. In Knowledge Representation, properties (or postulates) • We introduce properties constraining model-based provide a standard, and useful, way of studying inference inductive operators to be tightly coupled to the con- operators. The use of properties allows us to eliminate ditional statements provided in a belief base, and approaches regarded as undesirable, thereby restricting the show that this is incompatible with one of the no- attention to the most relevant operators. Viewed as a form tions of equivalence and the property of Syntax Split- of a top-down approach to characterising inference, they are ting [9]. often used in tandem with more bottom-up methods that • Based on the failure of the well-studied form of in- focus on constructing inference operators. The interaction ductive inference known as lexicographic inference between these approaches frequently lead to better insights [10] to satisfy one of our notions of equivalence, we regarding the type of inference being studied. In addition, propose a variant of lexicographic inference that properties can be used to classify and categorise different satisfies it. approaches to inference, leading to a better understanding • We introduce a property of language independence of the overall picture. for inductive inference and show that a property re- Two of the best known instances of the use of properties ferred to as conditional-functional ensures language are the AGM properties for belief change [1, 2] and the KLM independence. properties for nonmonotonic inference [3, 4], the latter itself based on the work of Adams [5]. See also the pioneering The paper is organized as follows. Section 2 provides the work of Gabbay [6]. In both cases, the use of properties various preliminaries required to present our contributions. has had a big impact on the two respective fields, leading Section 3 presents versions of equivalence for inductive to further improvements and clarifications. In fact, it also inference, and tests this against the newly-added property contributed to the realisation that KLM-style inference and of being conditional-based. Section 4 presents a version of AGM belief change are closely related [7, 8]. lexicographic inference that satisfies the notion of pairwise In this paper we continue the tradition of employing prop- equivalence introduced in the previous section. Section 5 erties for the study of inference operators understanding, introduces and studies language independence. Section 6 and apply it to a specific kind of nonmonotonic inference considers related work. Finally, Section 7 concludes and operator described by Kern-Isberner et al. [9] as inductive considers future work. inference operators. In particular, we focus on properties that formalize ways in which the syntax of a conditional knowledge base can or should influence the inferences in- 2. Preliminaries duced by them. More specifically, we make the following contributions: In the following we recall preliminaries on propositional logic, and technical details on inductive inference. • We introduce different versions of equivalence for inductive inference, point out the relationships be- 2.1. Propositional Logic For a set Σ of atoms, let ℒ(Σ) be the corresponding propo- 22nd International Workshop on Nonmonotonic Reasoning, November 2-4, 2024, Hanoi, Vietnam sitional language constructed using the usual connectives $ jesse.heyninck@ou.nl (J. Heyninck); BoothR2@cardiff.ac.uk ∧ (and), ∨ (or), ¬ (negation), → (material implication) and (R. Booth); tommie.meyer@uct.ac.za (T. Meyer) ↔ (material equivalence). A (classical) interpretation (also € https://sites.google.com/view/jesseheyninck (J. Heyninck); called possible world) 𝜔 for a propositional language ℒ(Σ) https://profiles.cardiff.ac.uk/staff/boothr2 (R. Booth); is a function 𝜔 : Σ → {1, 0} where 1 is understood to https://tommiemeyer.org.za (T. Meyer)  0000-0002-3825-4052 (J. Heyninck); 0000-0002-6647-6381 (R. Booth); denote truth, and 0 to denote falsity. Let Ω(Σ) denote the 0000-0003-2204-6969 (T. Meyer) set of all interpretations for Σ. We simply write Ω if the © 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribu- tion 4.0 International (CC BY 4.0). set of atoms is implicitly given, and similarly for ℒ. An CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings interpretation 𝜔 satisfies (or is a model of) an atom 𝑎 ∈ Σ, way: If Θ ⊆ Σ then any TPO ⪯ on Ω(Σ) uniquely induces denoted by 𝜔 |= 𝑎, if and only if 𝜔(𝑎) = 1. The satisfaction a marginalized TPO ⪯|Θ on Ω(Θ) by setting relation |= is extended to formulas in the usual way. As an abbreviation we sometimes identify an interpretation 𝜔 with 𝜔1Θ ⪯|Θ 𝜔2Θ iff 𝜔1Θ ⪯ 𝜔2Θ . (2) its complete conjunction, i. e., if 𝑎1 , . . . , 𝑎𝑛 ∈ Σ are those atoms that are assigned ⊤ by 𝜔 and 𝑎𝑛+1 , . . . , 𝑎𝑚 ∈ Σ Note that on the right hand side of the iff condition are those propositions that are assigned ⊥ by 𝜔 we iden- above 𝜔1Θ , 𝜔2Θ are considered as propositions in the super- tify 𝜔 by 𝑎1 . . . 𝑎𝑛 𝑎𝑛+1 . . . 𝑎𝑚 (or any permutation of this). language ℒ(Ω). Hence 𝜔1Θ ⪯ 𝜔2Θ is well defined [13]. SPOs For 𝑋 ⊆ ℒ(Σ) we also define 𝜔 |= 𝑋 if and only if can be marginalized in a similar manner. Similarly, any infer- 𝜔 |= 𝐴 for every 𝐴 ∈ 𝑋. Define the set of models ence relation |∼ on ℒ(Σ) induces a marginalized inference Mod(𝑋) = {𝜔 ∈ Ω(Σ) | 𝜔 |= 𝑋} for every formula relation |∼|Θ on ℒ(Θ) by setting or set of formulas 𝑋. A formula or set of formulas 𝑋1 en- 𝐴 |∼|Θ 𝐵 iff 𝐴 |∼ 𝐵 (3) tails another formula or set of formulas 𝑋2 , denoted by 𝑋1 |= 𝑋2 , if Mod(𝑋1 ) ⊆ Mod(𝑋2 ). Where 𝜃 ⊆ Σ, and for any 𝐴, 𝐵 ∈ ℒ(Θ). 𝜔 ∈ Ω(Σ), we denote by 𝜔 𝜃 the restriction of 𝜔 to 𝜃, i.e. 𝜔 𝜃 An obvious generalisation of total preorders are ordinal is the interpretation over Σ𝜃 that agrees with 𝜔 on all atoms conditional functions (OCFs), (also called ranking functions) in 𝜃. Where Σ𝑖 , Σ𝑗 ⊆ Σ, Ω(Σ𝑖 ) will also be denoted by Ω𝑖 𝜅 : Ω → N ∪ {∞} with 𝜅−1 (0) ̸= ∅. [14]. They express for any 𝑖 ∈ N, and likewise Ω𝑖,𝑗 will denote Ω(Σ𝑖 ∪ Σ𝑗 ) degrees of (im)plausibility of possible worlds and proposi- (for 𝑖, 𝑗 ∈ N). Likewise, for some 𝑋 ⊆ ℒ(Σ𝑖 ), we define tional formulas 𝐴 by setting 𝜅(𝐴) := min{𝜅(𝜔) | 𝜔 |= Mod𝑖 (𝑋) = {𝜔 ∈ Ω𝑖 | 𝜔 |= 𝑋}. 𝐴}. A conditional (𝐵|𝐴) is accepted by 𝜅 iff 𝐴 |∼𝜅 𝐵 iff 𝜅(𝐴 ∧ 𝐵) < 𝜅(𝐴 ∧ ¬𝐵). Notice that any OCF induces a 2.2. Reasoning with Nonmonotonic TPO on Ω, defined by 𝜔1 ⪯ 𝜔2 iff 𝜅(𝜔1 ) ⩽ 𝜅(𝜔2 ). Conditionals 2.3. Inductive Inference Operators Given a language ℒ, conditionals are objects of the form (𝐵|𝐴) where 𝐴, 𝐵 ∈ ℒ. The set of all conditionals based on In this paper we will be interested in inference operators a language ℒ is defined as: (ℒ|ℒ) = {(𝐵|𝐴) | 𝐴, 𝐵 ∈ ℒ}. |∼ Δ parametrized by a finite conditional belief base ∆. In We follow the approach of de Finetti [11] who considers more detail, such inference operators are induced by ∆, in conditionals as generalized indicator functions for possible the sense that ∆ serves as a starting point for the inferences worlds or propositional interpretations 𝜔: in |∼ Δ . We call such operators inductive inference operators: Definition 1 ([9]). An inductive inference operator (from ⎧ ⎨ 1 : 𝜔 |= 𝐴 ∧ 𝐵 (𝐵|𝐴)(𝜔) = 0 : 𝜔 |= 𝐴 ∧ ¬𝐵 (1) conditional belief bases) is a mapping C that assigns to each ⎩ 𝑢 : 𝜔 |= ¬𝐴 conditional belief base ∆ ⊆ (ℒ|ℒ) an inference relation |∼ Δ on ℒ that satisfies the following basic requirement of direct where 𝑢 stands for unknown or indeterminate. In other inference: words, a possible world 𝜔 verifies a conditional (𝐵|𝐴) iff it (DI) If ∆ is a conditional belief base and |∼ Δ is an infer- satisfies both antecedent and conclusion ((𝐵|𝐴)(𝜔) = 1); ence relation that is induced by ∆, then (𝐵|𝐴) ∈ ∆ it falsifies, or violates it iff it satisfies the antecedent but implies 𝐴 |∼ Δ 𝐵. not the conclusion ((𝐵|𝐴)(𝜔) = 0); otherwise the con- ditional is not applicable, i. e., the interpretation does not As already indicated in the previous subsection, inference satisfy the antecedent ((𝐵|𝐴)(𝜔) = 𝑢). We say that 𝜔 sat- operators can be obtained on the basis of SPOs, TPOs, and isfies a conditional (𝐵|𝐴) iff it does not falsify it, i.e., iff 𝜔 OCFs, respectively: satisfies its material counterpart 𝐴 → 𝐵. We will look at the semantics of conditionals given both by total preorders Definition 2. A model-based-based inductive inference (TPOs) ⪯⊆ Ω(Σ) × Ω(Σ) and strict partial orders (SPOs) operator for strict partial orders is a mapping C𝑠𝑝𝑜 that ≺⊆ Ω(Σ) × Ω(Σ).1 As is usual, given a preorder ⪯, we assigns to each conditional belief base ∆ a strict partial order denote 𝜔 ⪯ 𝜔 ′ and 𝜔 ′ ⪯ 𝜔 by 𝜔 ≈ 𝜔 ′ and 𝜔 ⪯ 𝜔 ′ and ≺Δ on Ω s.t. 𝐴 |∼ ≺Δ 𝐵 for every (𝐵|𝐴) ∈ ∆ (i.e., s.t. (DI) 𝜔 ′ ̸⪯ 𝜔 by 𝜔 ≺ 𝜔 ′ . Thus, without loss of generality, the is ensured). A model-based inductive inference operator for following definition applies to both TPOs and SPOs: given a total preorders C𝑡𝑝𝑜 is defined similarly, by using a TPO ⪯Δ strict order ≺ on possible worlds, representing relative plau- instead of an SPO ≺Δ . sibility, we define 𝐴 ≺ 𝐵 iff for every 𝜔 ′ ∈ min≺ (Mod(𝐵)) A model-based inductive inference operator for OCFs (on there is an 𝜔 ∈ min⪯ (Mod(𝐴)) such that 𝜔 ≺ 𝜔 ′ . This Ω) is a mapping C𝑜𝑐𝑓 that assigns to each conditional belief allows for expressing the validity of conditional inferences base ∆ an OCF 𝜅Δ on Ω s.t. ∆ is accepted by 𝜅Δ (i.e., s.t. (DI) via stating that 𝐴 |∼ ≺ 𝐵 iff (𝐴 ∧ 𝐵) ≺ (𝐴 ∧ ¬𝐵) [12] for is ensured). a TPO or SPO. We say that a set ∆ ⊆ (ℒ(Σ)|ℒ(Σ)) of con- Examples of inductive inference operators for OCFs in- ditionals is consistent if there is an SPO ≺ over Ω(Σ) s.t. clude System Z (also called rational closure, [15, 16], see 𝐴 |∼ ≺ 𝐵 for every (𝐵|𝐴) ∈ ∆. In what follows, we will, Sec. 2.4) and c-representations ([17]), whereas lexicographic for simplicity, always assume a set of conditionals is finite inference ([10], see Sec. 2.5) is an example of an inductive and consistent, and call such a set a conditional belief base. inference operator for TPOs and System W ([18], see Sec. We can marginalize total preorders and even inference 2.6) is an example of an inductive inference operator for operators, i.e., restricting them to sublanguages, in a natural SPOs. 1 A strict partial order is a binary relation that is irreflexive and transitive. We now recall a property that has been recently intro- A total preorder is a binary relation that is transitive and complete (and duced and studied, syntax splitting [9]. To define the prop- therefore reflexive), i.e., 𝜔1 ⪯ 𝜔2 or 𝜔2 ⪯ 𝜔1 for all 𝜔1 , 𝜔2 . erty of syntax splitting we assume a conditional belief base ∆ that can be split into subbases ∆1 , ∆2 s.t. ∆𝑖 ⊂ (ℒ𝑖 |ℒ𝑖 ) 𝜔 𝜅𝑍 Δ 𝜔 𝜅𝑍 Δ 𝜔 𝜅𝑍 Δ 𝜔 𝜅𝑍 Δ with ℒ𝑖 = ℒ(Σ𝑖 ) for 𝑖 = 1, 2⋃︁ s.t. Σ1 ∩ Σ2 = ∅ and 𝑝𝑏𝑓 2 𝑝𝑏𝑓 1 𝑝𝑏𝑓 2 𝑝𝑏 𝑓 2 Σ1 ∪ Σ2 = Σ, writing ∆ = ∆1 ∆2 whenever this is 𝑝𝑏𝑓 0 𝑝𝑏𝑓 1 𝑝𝑏𝑓 0 𝑝𝑏 𝑓 0 Σ1 ,Σ2 the case. As an example of a (non-)inference, observe that e.g. Definition 3 (Independence (Ind), [9]). An inductive infer- ⊤ |∼ 𝑍 𝑍 Δ ¬𝑝 and 𝑝 ∧ 𝑓 ̸|∼ Δ 𝑏. ence operator C satisfies (Ind) if for any ∆ = ∆1 Σ1 ,Σ2 ∆2 ⋃︀ and for any 𝐴, 𝐵 ∈ ℒ𝑖 , 𝐶 ∈ ℒ𝑗 (𝑖, 𝑗 ∈ {1, 2}, 𝑗 ̸= 𝑖), 2.5. Lexicographic Inference 𝐴 |∼ Δ 𝐵 iff 𝐴 ∧ 𝐶 |∼ Δ 𝐵 We recall lexicographic inference as introduced by Lehmann [10]. For some conditional belief base ∆, the order ⪯lex Δ Definition 4 (Relevance (Rel), [9]). An inductive ⋃︀ inference is defined as follows: Given 𝜔 ∈ Ω and ∆′ ⊆ ∆, operator C satisfies (Rel) if for any ∆ = ∆1 Σ1 ,Σ2 ∆2 𝑉 (𝜔, ∆′ ) = |{(𝐵|𝐴) ∈ ∆′ | (𝐵|𝐴)(𝜔) = 0}|. Given a set and for any 𝐴, 𝐵 ∈ ℒ𝑖 (𝑖 ∈ {1, 2}), of conditionals ∆ partitionend in OP (∆) = (∆0 , . . . , ∆𝑛 ), the lexicographic vector for a world 𝜔 ∈ Ω is the vec- 𝐴 |∼ Δ 𝐵 iff 𝐴 |∼ Δ𝑖 𝐵. tor lex(𝜔) = (𝑉 (𝜔, ∆0 ), . . . , 𝑉 (𝜔, ∆𝑛 )). Given two vectors (𝑥1 , . . . , 𝑥𝑛 ) and (𝑦1 , . . . , 𝑦𝑛 ), (𝑥1 , . . . , 𝑥𝑛 ) ⪯lex Definition 5 (Syntax splitting (SynSplit), [9]). An inductive (𝑦1 , . . . , 𝑦𝑛 ) iff there is some 𝑗 ⩽ 𝑛 s.t. 𝑥𝑘 = 𝑦𝑘 for every inference operator C satisfies (SynSplit) if it satisfies (Ind) 𝑘 > 𝑗 and 𝑥𝑗 ⩽ 𝑦𝑗 . 𝜔 ⪯lex Δ 𝜔 iff lex(𝜔) ⪯ lex(𝜔 ′ ). The ′ lex and (Rel). resulting inductive inference operator 𝐶⪯lex will be denoted 𝑡𝑝𝑜 Thus, (Ind) requires that inferences from one sub- by 𝐶 lex to avoid clutter. language are independent from formulas over the other Example 2 (Example 1 ctd.). For the Tweety belief base ∆ sublanguage, if the belief base splits over the respective as in Example 1 we obtain the following lex(𝜔)-vectors: sublanguages. In other words, information on the basis of one sublanguage does not influences inferences made in 𝜔 lex(𝜔) 𝜔 lex(𝜔) 𝜔 lex(𝜔) 𝜔 lex(𝜔) the other sublanguage. (Rel), on the other hand, restricts 𝑝𝑏𝑓 (0,1) 𝑝𝑏𝑓 (1,0) 𝑝𝑏𝑓 (0,2) 𝑝𝑏 𝑓 (0,1) the scope of inferences, by requiring that inferences in a 𝑝𝑏𝑓 (0,0) 𝑝𝑏𝑓 (1,0) 𝑝𝑏𝑓 (0,0) 𝑝𝑏 𝑓 (0,0) sublanguage can be made on the basis of the conditionals in a conditional belief base formulated on the basis of that The lex-vectors are ordered as follows: sublanguage. (SynSplit) combines these two properties. It has been shown that System Z satisfies (Rel) but not (Ind) (0, 0) ≺lex (1, 0) ≺lex (0, 1) ≺lex (0, 2). [9], while lexicographic inference [19] and system W [20] Observe that e.g. ⊤ |∼ lex lex Δ ¬𝑝 and 𝑝 ∧ 𝑓 |∼ Δ 𝑏. satisfy full (SynSplit). 2.6. System W 2.4. System Z System W is a recently introduced inductive inference opera- We present system 𝑍 as defined by Goldszmidt and Pearl tor [21, 18] that takes into account the structural information [15] as follows. A conditional (𝐵|𝐴) is tolerated by a finite about which conditionals are falsified. set of conditionals ∆ if there is a possible world 𝜔 with (𝐵|𝐴)(𝜔) = 1 and (𝐵 ′ |𝐴′ )(𝜔) ̸= 0 for all (𝐵 ′ |𝐴′ ) ∈ Definition 6 (𝜉 𝑗 , 𝜉, preferred structure ≺wΔ on worlds [18]). ∆, i.e. 𝜔 verifies (𝐵|𝐴) and does not falsify any (other) For a belief base ∆ = {(𝐵𝑖 |𝐴𝑖 ) | 𝑖 ∈ {1, . . . , 𝑛}} with conditional in ∆. The Z-partitioning (or ordered partition) OP (∆) = (∆0 , . . . , ∆𝑘 ) and for 𝑗 = 0, . . . , 𝑘, the func- OP (∆) = (∆0 , . . . , ∆𝑛 ) of ∆ is defined as: tions 𝜉 𝑗 and 𝜉 are given by 𝑗 • ∆0 = {𝛿 ∈ ∆ | ∆ tolerates 𝛿}; 𝜉Δ (𝜔) := {(𝐵𝑖 |𝐴𝑖 ) ∈ ∆𝑗 | 𝜔 |= 𝐴𝑖 ∧ ¬𝐵𝑖 }, • OP (∆ ∖ ∆0 ) = ∆1 , . . . , ∆𝑛 . 𝜉Δ (𝜔) := {(𝐵𝑖 |𝐴𝑖 ) ∈ ∆ | 𝜔 |= 𝐴𝑖 ∧ ¬𝐵𝑖 }. For 𝛿 ∈ ∆ we define: 𝑍Δ (𝛿) = 𝑖 iff 𝛿 ∈ ∆𝑖 and OP (∆) = If ∆ is clear from the contex, we drop the subindex and write (∆0 , . . . , ∆𝑛 ). Finally, the ranking function 𝜅𝑍 Δ is defined 𝑗 𝜉 𝑗 instead of 𝜉Δ The preferred structure on worlds is given via: 𝜅𝑍Δ (𝜔) = max{𝑍Δ (𝛿) | 𝛿(𝜔) = 0, 𝛿 ∈ ∆} + 1, with by the binary relation ≺wΔ ⊆ Ω × Ω defined by, for any max ∅ = −1. The resulting inductive inference operator 𝜔, 𝜔 ′ ∈ Ω, 𝑍 is denoted by 𝐶 . System 𝑍 has been shown to be 𝐶𝜅𝑜𝑐𝑓 𝑍 Δ 𝜔 ≺wΔ 𝜔 ′ iff there exists an 𝑚 ∈ {0 , . . . , 𝑘} such that equivalent to rational closure [4], and the two terms are sometimes used interchangeably in the literature. 𝜉 𝑖 (𝜔) = 𝜉 𝑖 (𝜔 ′ ) ∀𝑖 ∈ {𝑚 + 1 , . . . , 𝑘} and We now illustrate OCFs in general and system𝑍 in partic- 𝜉 𝑚 (𝜔) ⊂ 𝜉 𝑚 (𝜔 ′ ) . ular with the well-known “Tweety the penguin”-example. I.e., 𝜔 ≺wΔ 𝜔 ′ if and only if 𝜔 falsifies strictly fewer (in the Example 1. Consider the conditional belief base ∆ = set-theoretic sense) conditionals than 𝜔 ′ in the ∆𝑚 with the {(𝑓 |𝑏), (𝑏|𝑝), (¬𝑓 |𝑝)}, where 𝑏 is intended to represent being biggest index 𝑚 where the conditionals falsified by 𝜔 and 𝜔 ′ a bird, 𝑓 represents being able to fly, and 𝑝 represents being a differ. Note that ≺wΔ is a strict partial order [18, Lemma 3]. penguin. ∆ has the following Z-partitioning: ∆0 = {(𝑓 |𝑏)} and ∆1 = {(𝑏|𝑝), (¬𝑓 |𝑝)}. This gives rise to the following Definition 7 (System W, |∼ wΔ [18]). Let ∆ be a belief base 𝜅𝑍 Δ -ordering over the worlds based on the signature {𝑏, 𝑓, 𝑝}: 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 The following example shows global equivalence does order, System W is an SPO-based inductive inference opera- not imply pairwise equivalence: tor 𝐶 w : ∆ ↦→ ≺wΔ . In fact, System W strictly lies between System Z and lexicographic inference: Example 4. Consider ∆1 = {(𝑞|𝑝), (𝑟|𝑝)} and ∆2 = {(𝑞∧ 𝑟|𝑝)}. Then clearly ∆1 and ∆2 are globally equivalent but Proposition 1 ([21, 22]). If 𝐴 is consistent, then 𝐴 |∼𝑧Δ 𝐵 not pairwise equivalent. implies 𝐴 |∼ wΔ 𝐵 and 𝐴 |∼ wΔ 𝐵 implies 𝐴 |∼ lex Δ 𝐵, but not vice versa. The following example shows pairwise equivalence does not imply bijective pairwise equivalence: Example 3 (Example 1 ctd.). The belief base ∆ from Ex. 1 induces the ≺wΔ below. We can entail 𝑝𝑏 |∼ wΔ 𝑓 as the verifying Example 5. Consider ∆1 = {(𝑞|𝑝)} and ∆2 = {(𝑞|𝑝), (𝑞∧ 𝑝|𝑝)}. Then clearly ∆1 and ∆2 are pairwise equivalent but world 𝑝𝑏𝑓 is ≺wΔ -preferred to the only falsifying world 𝑝𝑏𝑓 , not bijectively so. i.e., 𝑝𝑏𝑓 ≺wΔ 𝑝𝑏𝑓 . The following properties express that an inductive infer- 𝑝𝑏𝑓 𝑝𝑏𝑓 ence operator satisfies a given notion of equivalence: 𝑝𝑏 𝑓 𝑝𝑏𝑓 𝑝𝑏𝑓 𝑝𝑏𝑓 𝑝𝑏𝑓 Definition 9. Let an inductive inference operator C be given. 𝑝𝑏 𝑓 ≺wΔ Then C: • satisfies bijective pairwise equivalence if for any two bijective pairwise equivalent knowledge bases ∆1 and 3. Equivalence in Conditional ∆2 , C(∆1 ) = C(∆2 ). Reasoning • satisfies pairwise equivalence if for any two pairwise equivalent knowledge bases ∆1 and ∆2 , C(∆1 ) = We first define some preliminaries regarding equivalence. C(∆2 ). Two conditionals (𝐵1 |𝐴1 ) and (𝐵2 |𝐴2 ) are equivalent iff • satisfies global equivalence if for any two pairwise every world has the same attitude to both conditionals: globally equivalent knowledge bases ∆1 and ∆2 , i.e. (𝐵1 |𝐴1 )(𝜔) = (𝐵2 |𝐴2 )(𝜔) for every 𝜔 ∈ Ω. This C(∆1 ) = C(∆2 ). is equivalent to 𝐴1 ≡ 𝐴2 and 𝐵1 ∧ 𝐴1 ≡ 𝐵2 ∧ 𝐴2 . Notice that this implies that for any TPO or SPO ⪯, 𝐴1 |∼ ⪯ 𝐵1 iff In other words, an inductive inference operator C sat- 𝐴2 |∼ ⪯ 𝐵2 . We write (𝐵1 |𝐴1 ) ≡ (𝐵2 |𝐴2 ) in that case. isfies [bijective] pairwise [global] equivalence if for any We now define the following kinds of equivalence for [bijective] pairwise [globally] equivalent knowledge bases conditional knowledge bases: ∆1 and ∆2 , 𝐴 |∼ Δ1 𝐵 iff 𝐴 |∼ Δ2 𝐵. Notice that satisfying global equivalence is the strongest property, and satisfy- Definition 8. Two conditional knowledge bases ∆1 and ∆2 ing bijective pairwise equivalence the weakest (this is an are: immediate consequence of Proposition 2). • bijective pairwise equivalent if there is a bijection We now commence the study of the satisfaction of equiva- 𝑓 : ∆1 → ∆2 s.t. 𝛿 ≡ 𝑓 (𝛿) for every 𝛿 ∈ ∆1 ; lence for the inductive inference operators introduced above, • pairwise equivalent if for every 𝛿1 ∈ ∆1 there is moving from strongest result to weakest result. The first some 𝛿2 ∈ ∆2 s.t. 𝛿1 ≡ 𝛿2 , and vice versa; result concerns System Z: • globally equivalent if for every tpo ⪯, ∆1 is valid Proposition 3. System Z satisfies global equivalence. w.r.t. ⪯ iff ∆2 is valid w.r.t. ⪯. Proof Sketch. Pearl [16] showed that 𝜅𝑍 Δ has the following The intuition behind these notions is the following: bi- property: for any ⪯ s.t. ∆ is valid w.r.t. ⪯ and for any jective pairwise equivalence requires that two sets of condi- Δ (𝜔1 ) < 𝜅Δ (𝜔2 ) implies 𝜔1 ≺ 𝜔2 . Now, if 𝜔1 , 𝜔2 ∈ Ω, 𝜅𝑍 𝑍 tionals have the same size, and that every conditional in one some ∆1 and ∆2 are globally equivalent, they have the same set is equivalent to a conditional in the other set. Pairwise TPOs w.r.t. which they are valid, and thus 𝜅𝑍 Δ 1 = 𝜅Δ 2 . 𝑍 equivalence requires that for every conditional in the first set ∆1 , we can find an equivalent conditional in ∆2 , and We now move to System W, showing it satisfies pair- vice versa, but does not require these sets to have the same wise equivalence. We first show some preliminary results size. Finally, global equivalence merely requires that ∆1 The first result shows that tolerance is satisfied by pairwise and ∆2 have the same semantic structure, in the sense that equivalent conditional knowledge bases. they are valid w.r.t. the same TPOs. These notions are strictly hierarchical: Lemma 1. Let some conditional 𝛿 and two pairwise equiva- lent conditional knowledge bases ∆1 and ∆2 be given. Then Proposition 2. If ∆1 and ∆2 are bijectively pairwise equiv- ∆1 tolerates 𝛿 iff ∆2 tolerates 𝛿. alent, they are pairwise equivalent, and if they are pairwise equivalent, they are globally equivalent. Proof. Suppose ∆1 tolerates 𝛿. Then there is an 𝜔 ∈ Ω s.t. 𝜔(𝛿) = 1 and for every 𝛿1 ∈ ∆1 , 𝜔(𝛿1 ) ̸= 0. Consider Proof. The implication from bijectively pairwise equiva- some 𝛿2 ∈ ∆2 . Since ∆1 and ∆2 are pairwise equivalent, lent to pairwise equivalent is immediate. Suppose ∆1 there is a 𝛿1 ∈ ∆1 s.t. 𝛿1 ≡ 𝛿2 . As 𝜔(𝛿1 ) ̸= 0, also 𝜔(𝛿2 ) ̸= and ∆2 are pairwise equivalent and that ∆1 is valid w.r.t. 0. Thus, ∆2 tolerates 𝛿. ⪯. Consider some (𝐵2 |𝐴2 ) ∈ ∆2 . Then with pairwise equivalence, there is some (𝐵1 |𝐴1 ) ∈ ∆1 s.t. (𝐵1 |𝐴1 ) ≡ The next result builds on Lemma 1 to show that two (𝐵2 |𝐴2 ). Since ∆1 is valid w.r.t. ⪯, 𝐴1 |∼ ⪯ 𝐵1 and thus pairwise equivalent conditional knowledge bases generate also 𝐴2 |∼ ⪯ 𝐵2 . identical ordered partitions (up to pairwise equivalence). Lemma 2. Let two pairwise equivalent conditional knowl- Notice that the example used in this proof is also a viola- edge bases ∆1 and ∆2 with OP (∆𝑖 ) = (∆1𝑖 , . . . , ∆𝑛 𝑖 𝑖 ) (for tion of the property of Cut when applied to conditionals: if 𝑖 = 1, 2) be given. Then 𝑛1 = 𝑛2 and ∆𝑖1 is pairwise equiv- 𝐴 |∼ Δ 𝐵 then C(∆ ∪ {(𝐵|𝐴)}) ⊆ C(∆). This rule says alent with ∆𝑖2 for 1 ⩽ 𝑖 ⩽ 𝑛1 . that if we add a conditional to ∆ that is already inferred on the basis of ∆ - such as (𝑟 ∧ 𝑞|𝑞) being added to ∆1 above - Proof Sketch. This is shown by an easy induction on 𝑛𝑖 then this should not lead to the inference of any new con- (using Lemma 1). ditionals. In the above we have, e.g., 𝑞 ∧ (𝑝 ↔ ¬𝑟) ̸|∼ Δ1 𝑟 but 𝑞 ∧ (𝑝 ↔ ¬𝑟) |∼ Δ2 𝑟. Lemma 2 can then be used to prove that System W satis- Despite violating pairwise equivalence, lexicographic in- fies pairwise equivalence. ference satisfies bijective pairwise equivalence: Proposition 4. System W satisfies pairwise equivalence. Proposition 6. Lexicographic inference satisfies bijective Proof. Suppose ∆1 and ∆2 are pairwise equivalent. Let pairwise equivalence. 𝑖 ) (for 𝑖 = 1, 2). Then with OP (∆𝑖 ) = (∆1𝑖 , . . . , ∆𝑛 𝑖 Proof. This is immediate from the fact that for any two Lemma 2, 𝑛1 = 𝑛2 . We therefore denote 𝑛1 (= 𝑛2 ) by bijective pairwise equivalent ∆1 and ∆2 , 𝑉 (𝜔, ∆1 ) = 𝑛. 𝑉 (𝜔, ∆2 ) (for any 𝜔 ∈ Ω(Σ)). We first show the following (†): if ∆1 and ∆2 are pairwise equivalent, then for any 𝜔 ∈ Ω, Arguably, the failure of lexicographic inference to satisfy pairwise equivalence is undesirable, as it means that the 𝑗 𝜉Δ 1 (𝜔) = {𝛿1 ∈ ∆1 | 𝛿1 ≡ 𝛿2 for some 𝛿2 ∈ 𝜉Δ 𝑗 2 (𝜔)}. number of (equivalent) conditionals in a knowledge base has an effect on the inferences from the knowledge base. To This is shown as follows. Suppose 𝛿1 ∈ 𝜉Δ 𝑗 1 . Then there overcome this defect, we will propose a variant of lexico- is some 𝛿2 ∈ ∆2 (in view of Lemma 2) s.t. 𝛿2 ≡ 𝛿1 , which 𝑗 graphic inference that avoids this in Section 4. implies 𝛿2 ∈ 𝜉Δ 𝑗 2 . Thus, 𝜉Δ 𝑗 1 (𝜔) ⊆ {𝛿1 ∈ ∆1 | 𝛿1 ≡ 𝛿2 for some 𝛿2 ∈ 𝜉Δ2 (𝜔)}. Furthermore, for every 𝛿2 ∈ 𝑗 3.1. Satisfaction of Global Equivalence and 𝜉Δ𝑗 2 there is a 𝛿1 ∈ 𝜉Δ 𝑗 1 (𝜔) s.t. 𝛿1 ≡ 𝛿2 . Thus, 𝜉Δ 𝑗 1 (𝜔) ⊇ Syntax Splitting {𝛿1 ∈ ∆1 | 𝛿1 ≡ 𝛿2 for some 𝛿2 ∈ 𝜉Δ2 (𝜔)} 𝑗 We now show that (‡): for any pairwise equivalent ∆1 We now show a more general result that shows that the and ∆2 and any 𝜔1 , 𝜔2 ∈ Ω, 𝜉Δ1 (𝜔1 ) ⊆ 𝜉Δ1 (𝜔2 ) implies satisfaction of global equivalence is perhaps too strong of 𝜉Δ2 (𝜔1 ) ⊆ 𝜉Δ2 (𝜔2 ). Indeed, suppose that 𝛿2 ∈ 𝜉Δ2 (𝜔1 ). a requirement, in the sense that it is incompatible with an- Then there is some 𝛿1 ∈ ∆2 s.t. 𝛿1 ≡ 𝛿1 . With †, 𝛿1 ∈ other property deemed desirable for inductive inference 𝜉Δ1 (𝜔1 ) and thus 𝛿1 ∈ 𝜉Δ1 (𝜔2 ). But then with †, 𝛿2 ∈ operators, namely syntax splitting. To show this, we will as- 𝜉Δ2 (𝜔2 ). sume another property, namely conditional-basedness, which We now show that for any 𝜔1 , 𝜔2 ∈ Ω, 𝜔1 ≺𝑤 expresses that worlds that have exactly the same attitudes Δ1 𝜔2 iff w.r.t. the inducing set of condintionals should not be distin- 𝜔1 ≺𝑤 Δ1 𝜔2 . Suppose for this that 𝜔1 ≺Δ1 𝜔2 , i.e. there is 𝑤 guished. Intuitively, in inductive inference, the only infor- some 1 ⩽ 𝑘 ⩽ 𝑛 s.t. 𝜉Δ 𝑗 (𝜔1 ) = 𝜉Δ𝑗 (𝜔2 ) for every 𝑗 > 𝑘, 1 1 mation that is relevant is the set of conditionals the inductive and 𝜉Δ1 (𝜔1 ) ⊂ 𝜉Δ1 (𝜔2 ). With ‡, 𝜉Δ 𝑘 𝑘 𝑗 2 (𝜔1 ) = 𝜉Δ 𝑗 2 (𝜔2 ) for inference operator is based on. every 𝑗 > 𝑘, and 𝜉Δ2 (𝜔1 ) ⊂ 𝜉Δ2 (𝜔2 ). Thus, 𝜔1 ≺𝑤 𝑘 𝑘 Δ2 𝜔2 . Altogether, this shows that 𝐴 |∼ 𝑊 𝐵 iff 𝐴 |∼ 𝑊 𝐵. Definition 10. A model-based inductive inference operator Δ1 Δ2 C for TPOs is conditional-based if, for any 𝜔1 , 𝜔2 ∈ Ω, if We’ll see in the next section (Proposition 9) that a similar (𝛿)(𝜔1 ) = (𝛿)(𝜔2 ) for every 𝛿 ∈ ∆ then 𝜔1 ≈Δ 𝜔2 . result can not be obtained for global equivalence, though. We finally turn to lexicographic inference. Perhaps some- A similar property can be defined for model-based induc- what surprisingly, we observe that lexicographic inference tive inference operators on SPOs and OCFs. does not even satisfy pairwise equivalence: Notice that this is a rather harmless property, in the sense that any of the inductive inference relations studied in this Proposition 5. Lexicographic inference does not satisfy pair- paper satisfy it: wise equivalence. Proposition 7. System Z, lexicographic inference and System Proof. Consider the following conditional knowledge bases: W are conditional-based. ∆1 ={(𝑝|𝑞), (𝑟|𝑞)} We can now show that, in the context of conditional- based inductive inference operators, global equivalence and ∆2 =∆1 ∪ {(𝑟 ∧ 𝑞|𝑞)}. Ind are jointly incompatible. ∆1 and ∆2 are pairwise equivalent. It is easy to see Proposition 8. There exists no conditional-based inductive that OP (∆1 ) = (∆1 ) and OP (∆2 ) = (∆2 ). Thus, the inference operation that satisfies global equivalence and satis- lexicographic vectors for the worlds 𝑝𝑞𝑟 and 𝑝𝑞𝑟 are fies (Ind). determined as follows: Proof. Suppose that C satisfies global equivalence and sat- 𝑉 (𝑝𝑞𝑟, ∆1 ) = 1, 𝑉 (𝑝𝑞𝑟, ∆2 ) = 1, since 𝑝𝑞𝑟 |= 𝑞 ∧ ¬𝑝; isfies syntax splitting. 𝑉 (𝑝𝑞𝑟, ∆1 ) = 1, 𝑉 (𝑝𝑞𝑟, ∆2 ) = 2, since 𝑝𝑞𝑟 |= Consider first ∆1 = {(𝑎|⊤), (𝑏|⊤)}. With (DI), ⊤ |∼ CΔ1 𝑎 (which implies 𝑎𝑏 ≺ 𝜔 for any 𝜔 ∈ Ω ∖ 𝑞 ∧ ¬𝑟 ∧ ¬(𝑟 ∧ 𝑞). {𝑎𝑏}), and likewise, ⊤ |∼ C Δ1 𝑏. Then since ∆1 = Δ1 𝑝𝑞𝑟 whereas 𝑝𝑞𝑟 ≺Δ2 𝑝𝑞𝑟. This means that 𝑝𝑞𝑟 ≈lex lex {(𝑎|⊤)} {𝑎},{𝑏} {(𝑏|⊤)}, ⊤ ∧ ¬𝑏 |∼ C Δ1 𝑎 by (Ind). This ⋃︀ means that 𝑎𝑏 ≺CΔ1 𝑎𝑏. With symmetry, we establish that Proof. Immediate from the fact that ⪯lex,≡ Δ extends 𝜅𝑍 Δ and 𝑎𝑏 ≺CΔ1 𝑎𝑏. ⪯Δ extends ⪯Δ (as 𝑉 (𝜔, ∆) ⩽ 𝑉 (𝜔, ∆) for any 𝜔). lex lex,≡ ≡ Consider now ∆2 = {(𝑎 ∧ 𝑏|⊤)}. Notice that ∆1 and ∆2 are globally equivalent. Thus, since C satisfies global equivalence, ≺C The next proposition show that this inference relation Δ1 =≺Δ2 . However, as ((𝑎 ∧ 𝑏|⊤))(𝑎𝑏) = C ((𝑎∧𝑏|⊤))(𝑎𝑏) = ((𝑎∧𝑏|⊤))(𝑎𝑏) = 0, we see that 𝑎𝑏 ≈C is quite well-behaved in the sense that it satisfies pairwise Δ2 equivalence and syntax splitting. 𝑎𝑏 ≈CΔ2 𝑎𝑏, contradiction. Proposition 11. 𝐶 lex,≡ satisfies pairwise equivalence. Notice that global equivalence is only incompatible with part of (SynSplit), in particular, with the property of (Ind). Proof. Immediate from the fact that for any pairwise equiv- Indeed, as system Z satisfies (Rel) [13], we see it is possible alent ∆1 and ∆2 , 𝑉 ≡ (𝜔, ∆1 ) = 𝑉 ≡ (𝜔, ∆2 ). to satisfy global equivalence and (Rel). We conclude this section with a result following from Proposition 12. 𝐶 lex,≡ satisfies SynSplit. Proposition 8 (and the fact that System W satisfies (Syn- Split) ([20]) and is conditional-based (Proposition 7)). Proof sketch. The proof is essentially the same as that of Theorem 1 by Heyninck et al. [19], with the exception of Proposition 9. System W does not satisfy global equivalence. Lemma 10, which we adapt to 𝐶 lex,≡ : Lemma 3. Let a conditional belief base ∆ = ∆1 Σ1 ,Σ2 ∆2 ⋃︀ 4. A variant of lexicographic with its corresponding Z-partition (∆0 , . . . , ∆𝑛 ) be given. Then for every 0 ⩽ 𝑖 ⩽ 𝑛, 𝑉 ≡ (𝜔, ∆𝑖 ) = 𝑉 ≡ (𝜔 1 , ∆1𝑖 ) + inference that satisfies pairwise 𝑉 ≡ (𝜔 2 , ∆2𝑖 ).2 equivalence Proof. Take some 0 ⩽ 𝑖 ⩽ 𝑛. Since ∆ = ∆1 Σ1 ,Σ2 ∆2 , ⋃︀ Obtaining a variant of lexicographic inference that satisfies (𝐵|𝐴) ∈ ∆𝑖 iff (𝐵|𝐴) ∈ ∆1𝑖 or (𝐵|𝐴) ∈ ∆2𝑖 . Fur- pairwise equivalence is rather straightforward. Instead of thermore, since Σ1 ∩ Σ2 = ∅, it cannot be the case counting which conditionals are violated by a world, we that (𝐵|𝐴) ∈ ∆1𝑖 and (𝐵|𝐴) ∈ ∆2𝑖 . Observe now count which conditionals are violated up to equivalence. In that: 𝑉 ≡ (𝜔, ∆𝑖 ) = |{[(𝐵|𝐴)] ∈ ∆𝑖 | 𝜔 |= 𝐴 ∧ more detail, we observe that equivalence of conditionals ¬𝐵}| = |{[(𝐵|𝐴)] | 𝜔 1 |= 𝐴 ∧ ¬𝐵 and (𝐵|𝐴) ∈ is an equivalence relation over (ℒ|ℒ), and thus, as usual, ∆1𝑖 }| ∪ |{[(𝐵|𝐴)] | 𝜔 2 |= 𝐴 ∧ ¬𝐵 and (𝐵|𝐴) ∈ ∆2𝑖 }|. we define the equivalence class of a conditional (𝐵|𝐴) as Thus: 𝑉 ≡ (𝜔, ∆𝑖 ) = 𝑉 ≡ (𝜔 1 , ∆1𝑖 ) + 𝑉 ≡ (𝜔 2 , ∆2𝑖 ), because [(𝐵|𝐴)] = {(𝐷|𝐶) ∈ (ℒ|ℒ) | 𝐴 ≡ 𝐶 and 𝐴 ∧ 𝐵 ≡ {[(𝐵|𝐴)] | 𝜔 1 |= 𝐴 ∧ ¬𝐵 and (𝐵|𝐴) ∈ ∆1𝑖 } ∩ {[(𝐵|𝐴)] | 𝐶 ∧ 𝐷}. We can now count the violations of conditionals 𝜔 2 |= 𝐴 ∧ ¬𝐵 and (𝐵|𝐴) ∈ ∆2𝑖 } = ∅. in ∆ by 𝜔 up to equivalence as: This completes the proof of Proposition 12. 𝑉 ≡ (𝜔, ∆) := |{[(𝐵|𝐴)] | (𝐵|𝐴)(𝜔) = 0, (𝐵|𝐴) ∈ ∆} Furthermore, it should be noticed that, as Clex,≡ is a It is easy to observe that 𝑉 (𝜔, ∆) ⩽ 𝑉 (𝜔, ∆) ≡ model-based inductive inference operator for strict partial for any 𝜔 and set of conditionals ∆. We can orders, it satisfies all the so-called KLM-postulates, including now define, for ∆ with OP (∆) = (∆0 , . . . , ∆𝑛 ), rational monotony. lex≡ (𝜔) = (𝑉 ≡ (𝜔, ∆0 ), . . . , 𝑉 ≡ (𝜔, ∆𝑛 )). We further- more let 𝜔1 ⪯lex,≡ 𝜔2 iff lex≡ (𝜔1 ) ⪯lex lex≡ (𝜔2 ). We Δ denote the corresponding inductive inference relation by 5. Language Independence 𝐶 lex,≡ We illustrate this with an adapted Tweety-Example: A final property of inductive inference operators we study Example 6. Let ∆ = {(𝑓 |𝑏), (𝑏|𝑝), (¬𝑓 |𝑝), (¬𝑓 ∧ 𝑝|𝑝)}. is the property of language independence. This property Notice that (¬𝑓 ∧ 𝑝|𝑝) ≡ (¬𝑓 |𝑝) We have the following lex- intuitively states that inductive inference should be inde- and lex≡ -vectors: pendent 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 𝜔 lex(𝜔) lex≡ (𝜔) 𝜔 lex(𝜔) lex≡ (𝜔) can be equivalently represented as complex formulas and vice versa. For example, one can represent “I don’t have a 𝑝𝑏𝑓 (0,2) (0,1) 𝑝𝑏𝑓 (1,0) (1,0) dog” by 𝑎 or ¬𝑎. This idea is formalized by Marquis and 𝑝𝑏𝑓 (0,3) (0,2) 𝑝𝑏 𝑓 (0,1) (0,1) Schwind [23] by defining a symbol translation as any map- 𝑝𝑏𝑓 (0,0) (0,0) 𝑝𝑏𝑓 (1,0) (1,0) ping 𝜎 : Σ → ℒ(Σ′ ). We can extend such a translation to 𝑝𝑏𝑓 (0,0) (0,0) 𝑝𝑏 𝑓 (0,0) (0,0) formulas by simply defining 𝜎(𝐴) the formula obtained by lex,≡ substituting any 𝑝 ∈ Σ by 𝜎(𝑝) in 𝐴, and for any conditional We see that e.g. 𝑝𝑏𝑓 ≺lex Δ 𝑝𝑏𝑓 yet 𝑝𝑏𝑓 ≈Δ 𝑝𝑏𝑓 . This means knowledge base ∆ we denote by 𝜎(∆) the knowledge base that 𝑝 ∧ ¬(𝑏 ∧ ¬𝑓 ) |∼ Δ 𝑏𝑓 whereas 𝑝 ∧ ¬(𝑏 ∧ ¬𝑓 ) ̸|∼ lex,≡ lex Δ 𝑏𝑓 . obtained by replacing each (𝐵 | 𝐴) in ∆ by (𝜎(𝐵) | 𝜎(𝐴)). We restrict attention to a specific class of symbol transla- We note firstly that this inference relation lies between tions. System Z and lexicographic inference: Proposition 10. For any conditional knowledge base ∆, 𝐴 |∼ 𝑍 lex,≡ Δ 𝐵 implies 𝐴 |∼ Δ 𝐵 and 𝐴 |∼ lex,≡ Δ 𝐵 implies 2 lex 𝐴 |∼ Δ 𝐵 Notice that it follows from Fact ?? that, given the Z-partition (Δ1 , . . . , Δ𝑛 ) of Δ and Σ𝑖 ⊆ Σ, Δ𝑖𝑗 = Δ𝑗 ∩ (ℒ𝑖 |ℒ𝑖 ) for any 0 ⩽ 𝑗 ⩽ 𝑛. Definition 11. A mapping 𝜎 : Σ → ℒ(Σ′ ) is a belief- times every vector of attitudes occurs. This can be seen amount preserving symbol translation (in short, a BAP- as a placeholder for a conditional knowledge base, in the translation) if there is a bijection 𝛾 : Ω(Σ) → Ω(Σ′ ) s.t. for sense that this is the only information about a conditional every 𝐴 ∈ ℒ(Σ) Mod(𝜎(𝐴)) = {𝛾(𝜔) | 𝜔 ∈ Mod(𝐴)}. knowledge base that should be of interest for a conditional- functional inductive inference operator that looks solely The idea is that a symbol translation is a way of translat- at the attitudes of worlds w.r.t. conditionals. We can now ing every atom to a formula such that the images of atoms define conditional-funtionality: are semantically equivalent (in the new language) to their originals: every world in the original language corresponds Definition 13. An inductive inference operator C is to exactly one world in the translated language. conditional-functional iff there is a function 𝐷 that returns, for any 𝑛 and any 𝑛VMD 𝐹 , a pair (𝑉𝐹𝐷 , ⊑𝐷 𝐹 ) where: Example 7. Consider Σ = {𝑎, 𝑏} and the symbol translation 𝜎(𝑎) = 𝑎 and 𝜎(𝑏) = 𝑎 ↔ 𝑏. Then we have the following 1. 𝑉𝐹𝐷 ⊆ {1, 0, 𝑢}𝑛 , translations of Ω(Σ): 2. ⊑𝐷 𝐷 𝐹 is a TPO on 𝑉𝐹 . such that: 𝜎(𝑎𝑏) = 𝑎∧𝑎↔𝑏 (= 𝑎𝑏) 𝜎(𝑎𝑏) = 𝑎 ∧ ¬(𝑎 ↔ 𝑏) (= 𝑎𝑏) • ⃗ 𝛼 ∈ 𝑉𝐹𝐷 implies 𝐹 (𝛼 ⃗ ) > 0, and 𝜎(𝑎𝑏) = 𝑎 ∧ (𝑎 ↔ 𝑏) (= 𝑎𝑏) • for any permutation 𝜎 on {1, . . . , 𝑛}, 𝑉𝜎(𝐹 𝐷 ) = 𝜎(𝑎𝑏) = 𝑎 ∧ ¬(𝑎 ↔ 𝑏) (= 𝑎𝑏) 𝐷 𝛼⊑ 𝜎(𝑉𝐹 ) and ⃗ 𝐷 ⃗ −1 𝛽 iff 𝜎 (𝛼 𝐷 −1 ⃗ ⃗ ) ⊑𝐹 𝜎 (𝛽 ) 𝜎(𝐹 ) We thus see that the bijection 𝛾 with 𝛾(𝑎𝑏) = 𝑎𝑏, 𝛾(𝑎𝑏) = 𝑎𝑏 and such that 𝜔1 ⪯Δ 𝜔2 iff ⟨𝛿1 (𝜔1 ), . . . , 𝛿𝑛 (𝜔1 )⟩ ⊑𝐷 𝐹Δ and that maps 𝑎𝑏 and 𝑎𝑏 to their selves is a bijection that ⟨𝛿1 (𝜔2 ), . . . , 𝛿𝑛 (𝜔2 )⟩, where ∆ = {𝛿1 , . . . , 𝛿𝑛 } and ensures 𝜎 is a BAP-translation. 𝐹Δ (𝛼⃗ ) = |{𝜔 | ⃗ 𝛼 = ⟨𝛿1 (𝜔), . . . , 𝛿𝑛 (𝜔)⟩}|. We are now ready to state what it means for an induc- The intuition behind this definition is the following: C tive inference operator to satisfy language independence—it should depend only on attitudes of worlds w.r.t. conditionals. should be invariant under BAP symbol translation. That is, we should be able to formulate it on basis of the VMD alone. This is formalized by the condition that 𝜔1 ⪯Δ 𝜔2 Definition 12. An inductive inference operator C satis- iff ⟨𝛿1 (𝜔1 ), . . . , 𝛿𝑛 (𝜔1 )⟩ ⊑𝐷 𝐹Δ ⟨𝛿1 (𝜔2 ), . . . , 𝛿𝑛 (𝜔2 )⟩ for fies language independence if for every BAP-translation 𝜎, some function 𝐷 generating TPOs over the attitude-vectors 𝐴 |∼ Δ 𝐵 iff 𝜎(𝐴) |∼ 𝜎(Δ) 𝜎(𝐵). that depends only on the VMD. Furthermore, the exact or- On the level of TPOs, we obtain the following representa- dering of the conditionals in a conditional knowledge base tion of language independence (variants for OCFs and SPOs should not matter. Hence the requirement of invariance are obtained similarly): under permutations. Proposition 13. A model-based inductive inference operator Example 8. We start with the conditional belief base from for TPOs C satisfies language independence if for every BAP- Example 1 and show how it can be interpreted in terms of translation 𝜎 : Σ1 → Σ2 , and any conditional belief base ∆ a 3VMD. We first recall that the worlds have the following over ℒ(Σ1 ), 𝜔1 ⪯Δ 𝜔2 iff 𝜎(𝜔1 ) ⪯𝜎(Δ) 𝜎(𝜔2 ). attitudes w.r.t. the conditionals 𝛿1 = (𝑓 |𝑏), 𝛿2 = (𝑏|𝑝) and 𝛿3 = (¬𝑓 |𝑝): Proof. Suppose that for every BAP-translation 𝜎 : Σ1 → ℒ(Σ2 ), and any conditional belief base ∆ over Σ1 , 𝜔 𝜔(𝛿1 ) 𝜔(𝛿2 ) 𝜔(𝛿3 ) 𝜔 𝜔(𝛿1 ) 𝜔(𝛿2 ) 𝜔(𝛿3 ) 𝜔1 ⪯Δ 𝜔2 iff 𝜎(𝜔1 ) ⪯𝜎(Δ) 𝜎(𝜔2 ). Suppose now that 𝐴 |∼ Δ 𝐵, i.e. min⪯Δ (Mod(𝐴)) ⊆ Mod(𝐵). As the or- 𝑝𝑏𝑓 1 1 0 𝑝𝑏𝑓 u 0 0 𝑝𝑏𝑓 1 u u 𝑝𝑏 𝑓 u u u der of ⪯Δ is preserved over 𝜎, min⪯𝜎(Δ) (Mod(𝜎(𝐴))) = 𝑝𝑏𝑓 0 1 1 𝑝𝑏𝑓 u 0 1 {𝜎(𝜔) | 𝜔 ∈ min⪯Δ (𝐴)}. As 𝜎 is BAP-translation, 𝑝𝑏𝑓 0 u u 𝑝𝑏 𝑓 u u u {𝜎(𝜔) | 𝜔 ∈ min⪯Δ (𝐴)} ⊆ Mod(𝜎(𝐵)). Thus, min⪯𝜎(Δ) (Mod(𝜎(𝐴))) ⊆ Mod(𝜎(𝐵)) which implies This means that we can view this knowledge base as the 𝜎(𝐴) |∼ 𝜎(Δ) 𝜎(𝐵). The proof of the opposite direction 3VMD 𝐹 defined by: (𝜎(𝐴) |∼ 𝜎(Δ) 𝜎(𝐵) implies 𝐴 |∼ Δ 𝐵) is similar. ⃗ 𝛼 𝐹 (𝛼 ⃗) ⃗ 𝛼 𝐹 (𝛼 ⃗) When are inductive inference operators language inde- pendent? We delineate a condition that ensures language ⟨1, 1, 0⟩ 1 ⟨𝑢, 0, 0⟩ 1 independence (as well as generalising the property of being ⟨1, 𝑢, 𝑢⟩ 1 ⟨𝑢, 𝑢, 𝑢⟩ 2 conditional-based), which we call conditional-functional. ⟨0, 1, 1⟩ 1 ⟨𝑢, 0, 1⟩ 1 Intuitively, this property requires that an induced conse- ⟨0, 𝑢, 𝑢⟩ 1 quence relation C(∆) only depends on the attitudes worlds have w.r.t. conditionals. Formally defining this property and 𝐹 (𝛼 𝛼 ∈ {1, 0, 𝑢}𝑛 . ⃗ ) = 0 for all remaining ⃗ turned out to be rather intricate, and we do so below in full Furthermore, system Z for this instance is captured by detail. Intuitively, the idea is that we are interested in infer- 𝐷(𝐹 ) = (𝑉𝐹𝐷 , ⊑𝐷 𝐷 𝐹 ) with 𝑉𝐹 = {𝛼 ⃗ | 𝐹 (𝛼 ⃗ > 0} and ence operators that only depend on vectors ⟨𝑖1 , . . . , 𝑖𝑛 ⟩ of ⟨𝑢, 𝑢, 𝑢⟩, ⟨1, 𝑢, 𝑢⟩ ⊑𝐹 ⟨0, 𝑢, 𝑢⟩, ⟨0, 1, 1⟩ ⊑𝐷 𝐷 𝐹 attitudes of worlds to conditionals. ⟨1, 1, 0⟩, ⟨𝑢, 0, 0⟩, ⟨𝑢, 0, 1⟩. In more formal detail, we let an 𝑛-dimensional vector The next result shows that for TPO-based inductive in- mass distribution (𝑛VMD) for a signature Σ be a function ference operators, being conditional-functional implies sat- 𝐹 : {1, 0, 𝑢}𝑛 ↦→ N s.t. Σ𝛼 ⃗ ) = 2|Σ| . Intu- ⃗ ∈{1,0,𝑢}𝑛 𝐹 (𝛼 isfying bijective pairwise-equivalence and language inde- itively, a VMD 𝐹 is a function that keeps track of how many pendence. Proposition 14. If a TPO-based inductive inference operator and, for any 𝑗1 , 𝑗2 ∈ {1, . . . , 𝑝}, C is conditional-functional then it satisfies bijective pairwise equivalence and language independence. 𝛼𝑗1 ⊑𝐷 ⃗ 𝐹 ⃗ 𝛼𝑗2 iff 𝜔𝑖1 ⪯* 𝜔𝑖2 for some 𝑖1 , 𝑖2 s.t. 𝛼𝑗1 and 𝑡(𝜔𝑖2 ) = ⃗ 𝑡(𝜔𝑖1 ) = ⃗ 𝛼𝑗2 Proof. We first show language independence. For this, con- sider a set of conditionals ∆ ⊆ (ℒ(Σ)|ℒ(Σ)) and a BAP- We now show that the conditions from Definition 13 are translation 𝜎 with corresponding bijection 𝛾 : Ω(Σ) → satisfied: Ω(Σ′ ). With Proposition 13, we have to show that 𝜔1 ⪯Δ 1. [𝛼 ⃗ ∈ 𝑉𝐹𝐷 implies 𝐹 (𝛼 ⃗ ) > 0]: clear from construction. 𝜔2 iff 𝜎(𝜔1 ) ⪯𝜎(Δ) 𝜎(𝜔2 ) for any 𝜔1 , 𝜔2 ∈ Ω(Σ). 2. [for any permutation 𝜎 on {1, . . . , 𝑛}, 𝑉𝜎(𝐹 𝐷 ) = 𝜎(𝑉𝐹 ) 𝐷 First, notice that, as 𝜎 is a BAP-translation, 𝜔 |= 𝐴 iff and ⃗ 𝛼 ⊑𝐷 ⃗ 𝜎(𝐹 ) 𝛽 iff 𝜎(𝛼 ⃗ ) ⊑𝐷 𝐹 𝜎(𝛽⃗ )]: Let 𝜎 be a 𝛾(𝜔) |= 𝜎(𝐴) for any 𝐴 ∈ ℒ(Σ). This means that for any permutation on {1, . . . , 𝑛}, i.e. there is a bijection 𝑓 : 𝛿 ∈ ∆, 𝛿(𝜔) = 𝜎(𝛿)(𝛾(𝜔)). Thus, ⟨𝛿1 (𝜔), . . . , 𝛿𝑛 (𝜔)⟩ = {1, . . . , 𝑛} ↦→ {1, . . . , 𝑛} s.t. for every ⟨𝛼1 , . . . , 𝛼𝑛 ⟩ ∈ ⟨𝜎(𝛿1 )(𝛾(𝜔)), . . . , 𝜎(𝛿𝑛 )(𝛾(𝜔))⟩. As C is conditional- {1, 0, 𝑢}𝑛 , 𝜎(⟨𝛼1 , . . . , 𝛼𝑛 ⟩) = ⟨𝛼𝑓 (1) , . . . , 𝛼𝑓 (𝑛) ⟩. Define based, and 𝜎(𝜔) = 𝛾(𝜔) for any 𝜔 ∈ Ω(Σ), this imme- 𝜎(𝐹 ) by 𝜎(𝐹 )(⟨𝛼1 , . . . , 𝛼𝑛 ⟩) = 𝐹 (𝜎 −1 (⟨𝛼1 , . . . , 𝛼𝑛 ⟩)). diately implies that 𝜔1 ⪯Δ 𝜔2 iff 𝜎(𝜔1 ) ⪯𝜎(Δ) 𝜎(𝜔2 ) for We now show the construction is invariant under 𝜎. Let 𝑡′ any 𝜔1 , 𝜔2 ∈ Ω(Σ). be the assignment of vectors to worlds relative to the VMD Next we show the satisfaction of bijective pairwise equiv- 𝜎(𝐹 ). We start by defining a bijection 𝛾 : Ω(Σ) ↦→ Ω(Σ) alence. For this, consider two knowledge bases ∆1 = s.t. for every 𝜔 ∈ Ω(Σ), 𝛾(𝜔) = 𝜔 ′ implies that 𝑡(𝜔) ∈ {𝛿1 , . . . , 𝛿𝑛 } and ∆2 = {𝛿1′ , . . . , 𝛿𝑛′ } that are bijectively 𝜎 −1 (𝑡′ (𝜔 ′ )). Notice that by the definition of 𝑡′ and the con- pairwise equivalent, where 𝑓 is the bijection 𝑓 : ∆1 ↦→ ∆2 struction above, such a bijection is guaranteed to exist (but s.t. 𝑓 (𝛿) ≡ 𝛿 for every 𝛿 ∈ ∆1 . Then clearly, for ev- might not be unique). Intuitively, 𝛾 maps every world 𝜔 ery 𝜔 ∈ Ω(Σ), 𝛿(𝜔) = 𝑓 (𝛿)(𝜔) (by definition of bijec- to one of its 𝜎-counterparts 𝜔 ′ (i.e. 𝜔 corresponds to the tive pairwise equivalence). Thus, ⟨𝛿1 (𝜔), . . . , 𝛿𝑛 (𝜔)⟩ = vector ⃗ 𝛼 and 𝜔 ′ corresponds to ⋁︀ the vector 𝜎(𝛼 ⃗ )). Define ⟨𝑓 (𝛿1 )(𝜔), . . . , 𝑓 (𝛿𝑛 )(𝜔)⟩. As 𝐷 is invariant under per- now 𝜏 : Σ ↦→ ℒ(Σ) by 𝜏 (𝑎) = {𝛾(𝜔) | 𝜔 ∈ Mod(𝑎)}. mutations on {1, . . . , 𝑛}, ⟨𝑓 (𝛿1 )(𝜔), . . . , 𝑓 (𝛿𝑛 )(𝜔)⟩ and It can be easily checked that this is a BAP-translation. Fur- ⟨𝛿1′ (𝜔), . . . , 𝛿𝑛′ (𝜔)⟩ get assigned the same position accord- thermore, it can be easily seen that: (†): ∆𝜎(𝐹 ) is bijectively ing to ⊑𝐷 . This concludes the proof. pairwise equivalent to 𝜏 (∆𝐹 ) We now show that 𝑉𝜎(𝐹 𝐷 ) = 𝜎(𝑉𝐹 ). Suppose first that 𝐷 The final result in this section shows the converse—for TPO-based inductive inference operators, satisfying bijec- 𝛼 ∈ 𝑉𝜎(𝐹 ) , i.e. 𝜔 ̸|∼ Δ𝐹 ⊥ for some 𝜔 s.t. 𝑡(𝜔) = ⃗ ⃗ 𝐷 C 𝛼. As 𝜏 tive pairwise equivalence and language independence im- is a BAP-translation and C is language independent, sat- plies being conditional-functional. isfies bijective pairwise equivalence and in view of (†), 𝜏 (𝜔) ̸|∼ C 𝜎(Δ𝐹 ) ⊥ and thus 𝜏 (𝜔) ∈ 𝜎(𝑉𝐹 ). As 𝜏 (𝜔) = 𝛾(𝜔) 𝐷 Proposition 15. If a TPO-based inductive inference opera- and 𝑡′ (𝛾(𝜔)) = 𝜎(𝑡(𝜔)) = 𝜎(𝛼 ⃗ ) (by construction of 𝛾), we tor C satisfies bijective pairwise equivalence and language see that 𝜎(𝛼 ⃗ ) ∈ 𝜎(𝑉𝐹𝐷 ). The opposite direction is similar. independence then it is conditional-functional. We now show that ⃗ ⃗ ⃗ 𝛼 ⊑𝐷 𝜎(𝐹 ) 𝛽 iff 𝜎(𝛼 ⃗ ) ⊑𝐷 𝐹 𝜎(𝛽 ). Proof. Given C satisfying bijective pairwise equivalence Suppose first that ⃗ 𝛼 ⊑ 𝐷 ⃗ 𝛽 , i.e. there are some 𝜔𝛼 ⃗ , 𝜔⃗ 𝜎(𝐹 ) 𝛽 and language independence, we must construct 𝐷 from C with 𝑡(𝜔𝑥 ) = 𝑥 for 𝑥 = ⃗ 𝛼, ⃗𝛽 and 𝜔𝛼⃗ ≺Δ𝐹 𝜔⃗ C 𝛽 . As such that C = C𝐷 . Let 𝐹 be a VMD of dimension 𝑚. We 𝜏 is a BAP-translation and C is language independent, must specify 𝑉𝐹𝐷 and ⊑𝐷 𝐹 . Our strategy will be to construct satisfies bijective pairwise equivalence and in view of (†), from 𝐹 a particular conditional belief base ∆𝐹 of size 𝑚 𝛾(𝜔𝛼 C ⃗ ) ≺𝜎(Δ𝐹 ) 𝛾(𝜔⃗ 𝛽 ). As 𝑡 (𝛾(𝜔𝑥 )) = 𝜎(𝑡(𝜔𝑥 )) = 𝜎(𝑥 ′ ⃗) and then use C(∆𝐹 ) to define 𝑉𝐹𝐷 and ⊑𝐷 𝐹 . As a first step, for 𝑥 = ⃗ 𝛼, ⃗𝛽 (by construction of 𝛾), we see that let ⟨𝜔1 , . . . , 𝜔2𝑛 ⟩ be an arbitrary enumeration of the inter- ⃗ 𝜎(𝛼⃗ ) ⊑𝐷 𝐹 𝜎(𝛽 ). The opposite direction is similar. pretations and let ⟨𝛼 𝛼𝑝 ⟩ be an enumeration of the ⃗ 1, . . . , ⃗ 3.[𝜔1 ⪯Δ 𝜔2 iff ⟨𝛿1 (𝜔1 ), . . . , 𝛿𝑛 (𝜔1 )⟩ ⊑𝐷 set of all ⃗𝛼 such that 𝐹 (𝛼 ⃗ ) > 0, ordered lexicographically 𝐹Δ ⟨𝛿1 (𝜔2 ), . . . , 𝛿𝑛 (𝜔2 )⟩, where ∆ = {𝛿1 , . . . , 𝛿𝑛 } and under the assumption 0 < 𝑢 < 1. We now choose some 𝐹Δ (𝛼 ⃗ ) = |{𝜔 | ⃗ 𝛼 = 𝛿1 (𝜔), . . . , 𝛿𝑛 (𝜔)}|]: This can way to distribute the ⃗ 𝛼𝑗 among the interpretations. A con- be easily seen by observing the following: for every crete way to do this is to set up a function 𝑡 assigning to each interpretation 𝜔𝑖 a vector ⃗ 𝛼𝑗 as follows: 𝜔 ∈ Ω(Σ),⋁︀ ⋁︀ . . . , 𝛿𝑚 (𝜔)⟩ = 𝑡(𝜔). Indeed, consider ⟨𝛿1 (𝜔), 𝛿𝑖 = (⊥ ∨ Ω1 | Ω2 ) for some 𝑖 = 1, . . . , 𝑚, where Ω1 ∑︁ and Ω2 are the sets of worlds as defined for ∆𝐹 above. 𝑡(𝜔𝑖 ) = ⃗ 𝛼𝑗 where 𝑗 is min. s.t. 𝐹 (𝛼⃗ 𝑘) ⩾ 𝑖 We consider three cases: (i.) 𝛿𝑚 (𝜔) = 1. This can only 𝑘⩽𝑗 happen if 𝜔 ∈ Ω1 ∩ Ω2 , which implies that the 𝑖𝑡ℎ element In other words, assign ⃗ 𝛼1 to the first 𝐹 (𝛼 ⃗ 1 ) interpreta- of 𝑡(𝜔) is 1. (ii.) 𝛿𝑚 (𝜔) = 0. This can only happen if tions in ⟨𝜔1 , . . . , 𝜔2𝑛 ⟩, then assign ⃗ 𝛼2 to the next 𝐹 (𝛼 ⃗ 2) 𝜔 ∈ Ω1 ∖ Ω2 , which implies that the 𝑖𝑡ℎ element of 𝑡(𝜔) is interpretations in the list, and so on. Then let ∆𝐹 = 0. (iii.) This can only happen if 𝜔 ̸∈ Ω1 , which implies the {(𝐵1 |𝐴1 ), . . . , (𝐵𝑚 |𝐴𝑚 )}, where, for each 𝑘 = 1, . . . , 𝑚: 𝑖𝑡ℎ element of 𝑡(𝜔) is 𝑢. As this exhausts all the options, this is sufficient to show the claim. We must now show that C𝐷 = C. So let {𝛿1 , . . . , 𝛿𝑚 } ⋁︁ 𝐴𝑘 = {𝜔𝑖 | 𝑘th element of 𝑡(𝜔𝑖 ) is 0 or 1} be a conditional belief base. For each 𝑖 = 1, . . . , 2𝑛 , let ⋁︁ ⃗𝑏𝑖 = ⟨𝛿1 (𝜔𝑖 ), . . . , 𝛿𝑚 (𝜔𝑖 )⟩ and let 𝛾 be a permutation on 𝐵𝑘 = ⊥ ∨ {𝜔𝑖 | 𝑘th element of 𝑡(𝜔𝑖 ) is 1} {1, . . . , 2𝑛 } such that the sequence ⟨𝑏 ⃗ 𝛾(1) , . . . , ⃗𝑏𝛾(2𝑛 ) ⟩ is Now let |∼ * = C(∆𝐹 ) with ⪯* its associated TPO. Then sorted lexicographically. Let 𝜎 be the BAP-translation cor- 𝑉𝐹 and ⊑𝐷 𝐷 𝐹 are specified as follows: responding to 𝛾. Then, since C satisfies language indepen- dence, we have: 𝐴 |∼ Δ 𝐵 iff 𝜎(𝐴) |∼ 𝜎(Δ) 𝜎(𝐵) ⃗ 𝑗 | 𝜔𝑖 ̸|∼ * ⊥ for some 𝜔𝑖 s.t. 𝑡(𝜔𝑖 ) = ⃗𝑎𝑗 } 𝑉𝐹𝐷 = {𝛼 Based on their construction, we strongly expect that sys- postulates can also be helpful in characterising inductive tem Z, lexicographic inference and system W are conditional inference operators. functional, but a rigorous proof is left to the next version of this work. References 6. Related Work [1] C. Alchourrón, P. Gärdenfors, D. Makinson, On the logic of theory change: Partial meet contraction and While there are several works related to the work we have revision functions, Journal of Symbolic Logic 50 (1985) done in this paper [24, 13, 25], the work of Weydert [24] is 510–530. perhaps the closest. Weydert suggested several properties [2] H. Katsuno, A. Mendelzon, Propositional knowledge in his study of default reasoning that share strong common- base revision and minimal change, Artificial Intelli- alities with some of the properties discussed in our work. gence 3 (1991) 263–294. For example, global logical invariance is rather similar to the [3] S. Kraus, D. Lehmann, M. Magidor, Nonmonotonic satisfaction of global equivalence, even though he does not reasoning, preferential models and cumulative logics, define (as far as we could see) in a formally precise manner Artificial Intelligence 44 (1990) 167–207. when two sets of conditionals are equivalent. Furthermore, [4] D. Lehmann, M. Magidor, What does a conditional strong irrelevance is very similar to relevance and representa- knowledge base entail?, Artificial intelligence 55 (1992) tion independence is very similar to language independence 1–60. (with the main differences being induced by the differences [5] E. Adams, Probability and the logic of conditionals, in the assumptions of the framework of Weydert, such as in: J. Hintikka, P. Suppes (Eds.), Aspects of inductive allowing for languages generated on the basis of infinite logic, North-Holland, 1966, pp. 265––316. boolean algebras, and allowing for rankings over rational [6] D. M. Gabbay, Theoretical foundations for non- numbers). Furthermore, he shows, in his exceptional inheri- monotonic reasoning in expert systems, in: K. R. tance paradox, that no consistent default inference notion Apt (Ed.), Logics and Models of Concurrent Systems, (his version of an inductive operator)can satisfy logicality, Springer Berlin Heidelberg, Berlin, Heidelberg, 1985, exceptional inheritance and global logical invariance. This is pp. 439–457. a slightly different but still quite similar result to our propo- [7] P. Gärdenfors, Belief revision and nonmonotonic sition 8. Essentially, we assume syntax splitting whereas logic: Two sides of the same coin?, in: Proc. JELIA’90, he assumes logicality (which means that the basic KLM- Springer, 1991, pp. 52–54. properties are satisfied) and exceptional inheritance. Excep- [8] P. Gärdenfors, D. Makinson, Nonmonotonic inference tional inheritance states that {𝜑, ¬𝜓} |∼ {(𝜓|𝜑),(𝜓′ |𝜑)} 𝜓 ′ if based on expectations, Artificial Intelligence 65 (1994) “𝜓 and 𝜓 ′ are logically independent given 𝜑”, although the 197–245. concept of logical independence is not precisely formalised. [9] G. Kern-Isberner, C. Beierle, G. Brewka, Syntax split- We note as a further difference that he does not study System ting= relevance+ independence: New postulates for Z, System W and lexicographic inference as we. nonmonotonic reasoning from conditional belief bases, in: Proceedings of the International Conference on Principles of Knowledge Representation and Reason- 7. Conclusion ing, volume 17, 2020, pp. 560–571. [10] D. Lehmann, Another perspective on default reason- This paper continues a tradition of studying inductive in- ing, Annals of Mathematics and Artificial Intelligence ference operators using properties. Table 1 summarizes 15 (1995) 61–82. the main findings of our work. More specifically, it consid- [11] B. de Finetti, La prévision, ses lois logiques et ses ers the inductive inference operators System Z, System W, sources subjectives, 1937. English translation in Studies lexicographic inference, and the variation of lexicographic in Subjective Probability, ed. H. Kyburg and H.E. Smok- inference introduced in Section 4, and shows, for each of ler, 1974, 93–158. New York: Wiley & Sons. them, whether or not they satisfy the properties of Indepen- [12] D. Makinson, General theory of cumulative inference, dence, Relevance, Global Equivalence, Pairwise Equivalence, in: International Workshop on Non-Monotonic Rea- Conditional-Based, and Language Independence. soning (NMR), Springer, 1988, pp. 1–18. [13] G. Kern-Isberner, G. Brewka, Strong Syntax Splitting System Z System W Lex Lex≡ for Iterated Belief Revision, in: C. Sierra (Ed.), Pro- Independence × ([9]) ∨ ([20]) ∨ ([19]) ∨ ceedings International Joint Conference on Artificial Relevance ∨ ([9]) ∨ ([20]) ∨ ([19]) ∨ Global Eq. ∨ × × × Intelligence, IJCAI 2017, ijcai.org, 2017, pp. 1131–1137. Pairwise Eq. ∨ ∨ × ∨ [14] W. Spohn, Ordinal conditional functions: A dynamic Bij. Pairwise Eq. ∨ ∨ ∨ ∨ theory of epistemic states, in: Causation in decision, Cond.-based ∨ ∨ ∨ ∨ belief change, and statistics, Springer, 1988, pp. 105– Table 1 134. Summary of the properties studied in this paper, where previous [15] M. Goldszmidt, J. Pearl, Qualitative probabilities for shown results occur with the respective reference. default reasoning, belief revision, and causal modeling, Artificial Intelligence 84 (1996) 57–112. [16] J. Pearl, System Z: a natural ordering of defaults with We see several avenues for future work. An obvious di- tractable applications to nonmonotonic reasoning, in: rection is to study other inductive inference operators, such Proceedings of the 3rd conference on Theoretical as- as c-representations [17], relevant closure [26], disjunctive pects of reasoning about knowledge, 1990, pp. 121– rational closure [27] or Weydert’s many System J-variants 135. [24]. Another avenue for future work is to see whether these [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, Lexico- graphic Entailment, Syntax Splitting and the Drown- ing Problem, in: L. D. Raedt (Ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence, IJCAI 2022, Vienna, Aus- tria, 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. Lake- meyer, T. Meyer (Eds.), 19th International Conference on Principles of Knowledge Representation and Rea- soning, 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 Opera- tors, in: I. Varzinczak (Ed.), Foundations of Informa- tion and Knowledge Systems - 12th International Sym- posium, 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, Condi- tional Independence for Iterated Belief Revision, in: L. D. Raedt (Ed.), Proceedings of the Thirty-First International Joint Conference on Artificial Intelli- gence, 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 clo- sure: A new form of defeasible reasoning for descrip- tion logics, in: Logics in Artificial Intelligence: 14th Eu- ropean Conference, JELIA 2014, Funchal, Madeira, Por- tugal, 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.