Paper deep dive
Representation Theorems for Cumulative Propositional Dependence Logics
Juha Kontinen, Arne Meier, Kai Sauerwald
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 7/20/2026, 1:06:12 PM
Summary
This paper establishes representation theorems for cumulative propositional dependence logic (PDL) and cumulative propositional logic with team semantics (TPL). It demonstrates that entailments in System C for these logics are exactly captured by cumulative models (from Kraus, Lehmann, and Magidor) and, for TPL, by cumulative and asymmetric models. The work bridges non-monotonic reasoning with team-based semantics, showing equivalence between axiomatic System C approaches and model-theoretic cumulative approaches for logics lacking negation and material implication.
Entities (8)
Relation Signals (5)
System C → capturesentailmentof → Propositional Dependence Logic
confidence 95% · For propositional dependence logic, we show that System C entailments are exactly captured by cumulative models
Cumulative Model → represents → System C
confidence 95% · System C entailments are exactly captured by cumulative models from Kraus, Lehmann and Magidor
Asymmetric Model → capturesentailmentof → Propositional Logic with Team Semantics
confidence 92% · entailment in cumulative propositional logics with team semantics is exactly captured by cumulative and asymmetric models
Kraus, Lehmann and Magidor → developed → Cumulative Model
confidence 90% · cumulative models from Kraus, Lehmann and Magidor
Team Semantics → combinedwith → Non-monotonic Reasoning
confidence 85% · study the fusion of non-monotonic reasoning with team-based reasoning
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This paper establishes and proves representation theorems for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. Cumulative logics are famously given by System C. For propositional dependence logic, we show that System C entailments are exactly captured by cumulative models from Kraus, Lehmann and Magidor. On the other hand, we show that entailment in cumulative propositional logics with team semantics is exactly captured by cumulative and asymmetric models. For the latter, we also obtain equivalence with cumulative logics based on propositional logic with classical semantics. The proofs will be useful for proving representation theorems for other cumulative logics without negation and material implication.
Tags
Links
- Source: https://arxiv.org/abs/2602.21360v1
- Canonical: https://arxiv.org/abs/2602.21360v1
Trouble viewing inline? Open PDF directly →
Full Text
56,278 characters extracted from source content.
Expand or collapse full text
Representation Theorems for Cumulative Propositional Dependence Logics Juha Kontinen1111The authors are ordered alphabetically. Arne Meier2∗ Kai Sauerwald3∗ 1Department of Mathematics and Statistics, University of Helsinki, Helsinki, Finland 2Theoretical Computer Science, Leibniz University Hannover, Hannover, Germany 3Faculty of Mathematics and Computer Science, FernUniversität in Hagen, Hagen, Germany Abstract This paper establishes and proves representation theorems for cumulative propositional dependence logic and for cumulative propositional logic with team semantics. Cumulative logics are famously given by System C. For propositional dependence logic, we show that System C entailments are exactly captured by cumulative models from Kraus, Lehmann and Magidor. On the other hand, we show that entailment in cumulative propositional logics with team semantics is exactly captured by cumulative and asymmetric models. For the latter, we also obtain equivalence with cumulative logics based on propositional logic with classical semantics. The proofs will be useful for proving representation theorems for other cumulative logics without negation and material implication. 1 Introduction The ability to reason is one of the central features of intelligent agents and thus a major concern of artificial intelligence. In this paper, we study the fusion of non-monotonic reasoning with team-based reasoning. Such a combination is interesting, as it allows reasoning in which one can express settings involving a plurality of objects (the team-based component) while also taking into account extra-logical information, such as plausibility, exceptionality, reliability, preference, or typicality (the non-monotonic component). Notably, the combination of these approaches provides a setting that cannot be formalized by neither of the approaches alone. Less is known about how to construct non-monotonic entailment relations for team-based logics. Known approaches for non-monotonic propositional logics or non-monotonic first-order logics rely heavily on the properties of the underlying logics, such as, e.g., the availability of all Boolean connectives, the law of excluded middle, and presence of material implication. However, these properties are not (always) available in team-based logics. There are many approaches to non-monotonic logics that take inspiration from (?), from which some are also generic, e.g., MAK models (?), KLM-style reasoning (?), characterization logics (?), or approximation fixpoint theory (?). So far, there are only two pioneering works that consider a combination of team semantics and non-monotonic reasoning. First, the work by ? (?), which considers a non-monotonic team-based modal logic in the context of formal analysis of natural language. The second is by ? (?) (SMK), which also contains a broader introduction and motivation, and focuses on non-monotonic reasoning in the style of ? (?) (KLM). KLM (?) showed for classical propositional logic that cumulative entailment relations provide a stable theory of reasoning with multiple representations. Cumulative entailment relations are obtained by reasoning via the axiomatic system known as System C. Furthermore, a cumulative entailment relation |∼ | can be represented by a cumulative model ℂC, by which φ|∼ψ | ψ amounts (intuitively) to checking whether all minimal models of φ in ℂC are models of ψ. SMK (?) show that entailment via preferential models (which are specific cumulative models) satisfies System C in the context of propositional dependence logic. However, SMK provides no representation theorems for any kind of general cumulative reasoning in the context of team-based logics. Contributions. This work establishes cumulative reasoning as a stable approach in the context of team-based logics. Specifically, we will encounter the cumulative counterparts of the following team-based logics: • Propositional logic with team-based semantics ( TPL) • Propositional dependence logic ( PDL) For each of these logics, we consider, both, reasoning via System C and via cumulative models as in the approach by KLM. This leads to System C-based entailment relations for PDL, denoted by PDL -2.15277pt 4.09024pt $ c$. Also, we will consider PDL entailment relations via cumulative models, denoted by PDL -2.15277pt 4.09024pt $ cuml$. With TPL -2.15277pt 4.09024pt $ cuml$ and TPL -2.15277pt 4.09024pt $ c$, we denote the respective approaches for TPL. We will show the following representation results: Representation Theorem for Cumulative PDL: PDL -2.15277pt 4.09024pt $ c$ and PDL -2.15277pt 4.09024pt $ cuml$ define the same entailment relations. Representation Theorem for Cumulative TPL: TPL -2.15277pt 4.09024pt $ c$ and TPL -2.15277pt 4.09024pt $ cuml$ define the same entailment relations. Furthermore, we show that the novel class of asymmetric models are a sufficient subclass of cumulative models for representation. The proofs for showing these results demonstrate, in a principled way, how similar relationships between these classes of entailment relations can be obtained for other logics without negation and material implication. 2 Preliminaries In this paper, we consider propositional logics from a model-theoretic perspective. We denote by =pi∣i∈ℕ Prop=\\;p_i i \;\ the countably infinite set of propositional variables. We consider propositional formulas in negation normal form, i.e., PLPL-formulas are formed by the grammar, where p∈p∈ Prop: φ⩴p∣¬p∣⊥∣⊤∣φ∧φ∣φ∨φ. p p . We write (φ) Prop( ) for the set of variables occurring in φ . Classical Propositional Logic ( CPL). For a non-empty finite subset N⊆N Prop of propositional variables, one defines for valuations v:N→0,1v N→\0,1\ over N and PLPL-formulas φ : ⟦φ⟧c=v:N→0,1∣v⊧φ. ^c=\\,v N→\0,1\ v \. The valuation function v is extended to the set of all PLPL-formulas satisfying (φ)⊆N Prop( ) N, PL(N)PL(N), in the usual way. We denote by NA_N the set of all assignments over N. We write φ⊧cψ ^cψ for ⟦φ⟧c⊆⟦ψ⟧c ^c ψ ^c and φ≡cψ ≡^cψ if both φ⊧cψ ^cψ and ψ⊧cφψ ^c are true. Prop. Logic with Team Semantics ( TPL). Next, we define team semantics for PLPL-formulas (cf. (?; ?)). A team X is a set of valuations for some finite N⊆N Prop. The domain N of X is denoted by (X) dom(X), and NT_N denotes the set of all such teams. Definition 1 (Team semantics of PLPL). Let X be a team. For any PLPL-formula φ with (X)⊇(φ) dom(X) Prop( ), the satisfaction relation, X⊧φX , is defined inductively as: X⊧p X p if for all v∈X:v⊧p, for all v∈ X:v p, X⊧¬p X p if for all v∈X:v⊧̸p, for all v∈ X:v p, X⊧⊤ X is always the case, always the case, X⊧⊥ X if X=∅, X= , X⊧φ∧ψ X ψ if X⊧φ and X⊧ψ, X and X ψ, X⊧φ∨ψ X ψ if there exist Y,Z⊆X there exist Y,Z X s.t. X=Y∪Z,Y⊧φ, and Z⊧ψ. .t. X=Y∪ Z,Y , and Z ψ. The set of all teams X with X⊧φX is denoted by ⟦φ⟧t ^t. For any two PLPL-formulas φ,ψ ,ψ, we write φ⊧tψ ^tψ if ⟦φ⟧t⊆⟦ψ⟧t ^t ψ ^t. Write φ≡tψ ≡^tψ if both φ⊧tψ ^tψ and ψ⊧tφψ ^t are true. We define the following properties for a formula φ : • X⊧φ⇔for all v∈X,v⊧φX all v∈ X, 10000\ \v\ . (Flatness) • ∅⊧φ . (Empty team) • If X⊧φX\, \, and Y⊆XY\, \,X, then Y⊧φY . (Downward closure) Proposition 2. TPL has the properties flatness, empty team, and downward closure. Due to the flatness property, logical entailment of propositional logic with team-based semantics ⊧t ^t and classical semantics ⊧c ^c coincide. Propositional Dependence Logic ( PDL). A (propositional) dependence atom is a string =(a→,b) =\! ( a,b ), in which a→=a1,…,ak a=a_1,…,a_k and b are propositional variables from Prop. A team X satisfies a dependence atom, X⊧=(a→,b)X =\! ( a,b ), if for all v,v′∈Xv,v ∈ X, v(a→)=v′(a→)v( a)=v ( a) implies v(b)=v′(b)v(b)=v (b). A dependence atom where the first component is empty will be abbreviated as =(p) =\! (p ) and called a constancy atom. The language of propositional dependence logic (PL()PL( dep)) is defined as PLPL-formulas extended by dependence atoms. Example 3. Consider the team X over p,q,r\p,q,r\ defined by: p q r v1v_1 11 0 0 v2v_2 0 11 0 v3v_3 0 11 0 Here, we have that X⊧=(p,q)X =\! (p,q ) and X⊧=(r)X =\! (r ). Moreover, we have that X⊧=(p)∨=(p)X =\! (p ) =\! (p ), however it is true that X⊧̸=(p)X =\! (p ) as the value of p is not overall constant. Proposition 4. PDL has the empty team and the downward closure property, but not the flatness property. Generic View on Logics. Some parts of this paper require a generic perspective on logics, which we discuss next. A satisfaction system is a triple =⟨ℒ,Ω,⊧⟩S= L, , , where ℒL is the set of formulas, Ω is the set of interpretations, and ⊧⊆Ω×ℒ ×L is the satisfaction relation. We write ⟦φ⟧=ω∈Ω∣ω⊧φ ^S=\ω∈ ω \ for the set of all models of the formula α∈ℒα . An entailment relation for a satisfaction system is a relation ⊩⊆ℒ×ℒ ×L such that α⊩γα γ if and only if β⊩γβ γ, whenever ⟦φ⟧=⟦ψ⟧ ^S= ψ ^S. A satisfaction system S together with an entailment relation ⊩ is called a logic and denoted by ℒ=⟨ℒ,Ω,⊧,⊩⟩ L= L, , , . The propositional logics discussed in this section fit into this general model-theoretic view for each N⊆N Prop as follows: N CPL_N =⟨PL(N),N,⊧,⊧c⟩=\, PL(N),A_N, , ^c N TPL_N =⟨PL(N),N,⊧,⊧t⟩=\, PL(N),T_N, , ^t N PDL_N =⟨PL(=(,),N),N,⊧,⊧t⟩=\, PL( =\! (, ),N),T_\!N, , ^t When there is no ambiguity, we will write ⊧ instead of ⊧t ^t. Moreover, we will use CPL to denote the class consisting of all logics N CPL_N for any non-empty finite subset N⊆N Prop. The classes TPL and PDL are defined analogous. 3 System C and Cumulative Models We consider the construction of entailment relations. System C. We make use of the following rules for calculi: φ≡ψφ|∼γψ|∼γ ≡ψ 14.22636pt | γψ | γ (LLE) φ∧ψ|∼γφ|∼ψφ|∼γ ψ | γ 14.22636pt | ψ | γ (Cut) φ⊧ψγ|∼φγ|∼ψ ψ 14.22636ptγ | γ | ψ (RW) φ|∼ψφ|∼γφ∧ψ|∼γ | ψ 14.22636pt | γ ψ | γ (CM) Note that ⊧ is a placeholder for the entailment relation ⊩ of an underlying logic ℒ=⟨ℒ,Ω,⊧,⊩⟩ L= L, , , , and ≡ is the respective semantic equivalence from ℒ L. System C consists of the rules (RW), (LLE), (CM), (Cut) and reflexivity (Ref) φ|∼φ | for all formulas (?; ?). We say that an entailment relation |∼ | satisfies System C if |∼ | is closed under all rules of System C. Relational Models. For a relation ⊆× R ×S on a set S and a subset S⊆S , an element s∈Ss∈ S is called minimal in S with respect to R if for each s′∈Ss ∈ S holds ¬(s′s) (s Rs). Then, min(S,) (S, R) is the set of all s∈Ss∈ S that are minimal in S with respect to R. Moreover, for a set of interpretations M and a formula φ of ℒ=⟨ℒ,Ω,⊧,⊩⟩ L= L, , , , we write M⊧φM if for all ω∈Mω∈ M we have that ω⊧φω . Definition 5 (Shoman ?, Dix and Makinson ?; ?). Let ℒ=⟨ℒ,Ω,⊧,⊩⟩ L= L, , , be a logic. A relational model for ℒ L is a triple =⟨,ℓ,⟩M= S, , R where S is a set, ℓ:→(Ω) ( ), and R is a binary relation on S. We say S⊆S is smooth if for each s∈Ss∈ S, we either have that s∈min(S,)s∈ (S, R), or there exists a state s′∈min(S,)s ∈ (S, R) with s′s Rs. For φ∈ℒ and s∈s , we denote by (φ)=s∈∣ℓ(s)⊧φS( )=\\,s (s) \,\ the set of states that satisfy φ . With min(⟦φ⟧,)=⋃ℓ(s)∣s∈min((φ),) ( , R)= \\, (s) s∈ (S( ), R)\,\, we denote the set of all interpretations that appear in ℓ(s) (s) for any minimal state s that satisfy φ . We will deal, in this paper, with specific types of relational models, which we define in the following. Definition 6. A relational model ℂ=⟨,ℓ,⟩C= S, , R for a logic ℒ=⟨ℒ,Ω,⊧,⊩⟩ L= L, , , is called cumulative if for all φ∈ℒ the set (φ)S( ) is smooth. A cumulative model ℂC is strong if R is asymmetric (xRyxRy implies ¬(yRx) (yRx)) and min((φ),) (S( ), R) has exactly one element for each formula φ∈ℒ . Because cumulative models satisfy smoothness, they avoid the problem of reasoning via arbitrary relational models, in which the set min(⟦φ⟧,) ( , R) might be empty, even when (φ)S( ) is non-empty. Entailment relations, which are induced by a relational model, are defined as follows. Definition 7. Let ℒ=⟨ℒ,Ω,⊧,⊩⟩ L= L, , , be a logic. The entailment relation |∼⊆ℒ×ℒ | _M ×L for a relational model =⟨,ℓ,⟩M= S, , R for ℒ L is given by φ|∼ψ if min(⟦φ⟧,)⊆⟦ψ⟧. | _Mψ if ( , R) ψ \ . An entailment relation |∼⊆ℒ×ℒ | ×L is called (strongly) cumulative if there is a (strong) cumulative model ℂC for ℒ L such that |∼=|∼ℂ | = | _ -2.0muC. Classes of Entailment Relations. If L is a class of logics (such as PDL, TPL, or CPL), we denote with L -2.15277pt 4.09024pt $ c$ the class of all entailment relations |∼ | for ⟨ℒ,Ω,⊧,⊩⟩∈ L, , , ∈ L that satisfy System C. Similarly, we use L -2.15277pt 4.09024pt $ cuml$ ([] L -2.15277pt 4.09024pt $ cuml$[$ str$]) for the class of all (strong) cumulative entailment relations. 4 Representation Theorems In this section, we will establish representation theorems for cumulative logics, i.e., logics that satisfy System C. A classic result is that cumulative classical propositional logics coincide with classical propositional logics that satisfy System C. Proposition 8 (KLM, ?). =[]= CPL -2.15277pt 4.09024pt $ cuml$= CPL -2.15277pt 4.09024pt $ cuml$[$ str$]= CPL -2.15277pt 4.09024pt $ c$. Here we will prove that when basing System C on propositional dependence logic, there is also the same connection between cumulative logics and cumulative models. We will also show that logics based on preferential and cumulative models for TPL correspond to System C logics for CPL. 4.1 Propositional Dependence Logic We will show the following representation result that establishes an equivalence between the class of cumulative propositional dependence logics and propositional dependence logics that satisfy System C. Theorem 9. =[]= PDL -2.15277pt 4.09024pt $ cuml$= PDL -2.15277pt 4.09024pt $ cuml$[$ str$]= PDL -2.15277pt 4.09024pt $ c$. First, we like to remark that the original proof of Proposition 8 makes heavy use of classical negation and material implication of the underlying propositional logic. As neither classical negation nor material implication are available (and also not definable) in PDL, the proof of Theorem 9 requires a new approach that circumvents the usage of implication and negation. We present the proof in the following, and mark those steps that are borrowed from KLM (?). Our first observation is that entailment relations in PDL -2.15277pt 4.09024pt $ cuml$ satisfy System C. This is a novel result as the proof of System C satisfaction for CPL -2.15277pt 4.09024pt $ pref$ given by KLM does not carry over to preferential propositional dependence logic. Proposition 10. ⊆ PDL -2.15277pt 4.09024pt $ cuml$ PDL -2.15277pt 4.09024pt $ c$. Proof (idea). One checks case by case that every postulate of System C is satisfied. A full proof is provided in the accompanied supplementary material. ∎ In the remainder of this section, we will show that every entailment relation |∼∈ | ∈ PDL -2.15277pt 4.09024pt $ c$ is strongly cumulative. For that, we will first show that one can characterize all the consequences of a formula φ via |∼ | semantically. For a given formula φ , we denote the set of all teams that satisfy all consequences of φ with respect to |∼ | , by Norm(φ,|∼)=X∣X⊧ψ for all ψ with φ|∼ψ. ( , | )=\\,X X ψ for all ψ with | ψ\,\\ . In the following, we will show that for every φ the set Norm(φ,|∼)Norm( , | ) characterize semantically the consequences of |∼ | drawn from φ . For all formulas φ , all sets of formulas F⊆ℒF , and all sets of teams M we define: C|∼(φ) _ | ( ) =ψ∣φ|∼ψ,Cn(φ)=ψ∣φ⊧ψ, =\\,ψ | ψ\,\, ( )=\\,ψ ψ\,\, Th(M) (M) =φ∈ℒ∣X⊧φ for all X∈M, =\\, X for all X∈ M\,\, Cn(F) (F) =ψ∣φ⊧ψ for all φ∈F. =\\,ψ ψ for all ∈ F\,\. The following lemma provides basic insights into the closures C|∼C_ | and CnCn, and the theory operator ThTh. Due to space constraints, the proof is given in the supplementary material. Lemma 11. The following statements are true: (a) For |∼∈ | ∈ PDL -2.15277pt 4.09024pt $ c$ we have that C|∼(φ)=Cn(C|∼(φ))C_ | ( )=Cn(C_ | ( )). (b) For each formula φ there exists an M⊆(N)M (T_N) such that Cn(φ)=Th(M)Cn( )=Th(M) and M=⟦φ⟧M= . (c) For each set of formulas F with F=Cn(F)F=Cn(F) there exists a formula φF _F such that F=Cn(φF)F=Cn( _F) is true. Note that the proof of Lemma 11 relies on the fact that PL()PL( dep) is expressively complete for team properties that are downward closed and contain the empty team (?). Now, we show the central insight that Norm(φ,|∼)Norm( , | ) characterizes all consequences of φ by |∼ | . Theorem 12 (Definability of Consequences). For all entailment relations |∼∈ | ∈ PDL -2.15277pt 4.09024pt $ c$ and all formulas φ we have that: (a) For all formulas ψ we have that: φ|∼ψ | ψ if and only if Norm(φ,|∼)⊧ψNorm( , | ) ψ. (b) There is a θφ _ such that for all formulas ψ we have that: φ|∼ψ | ψ if and only if θφ⊧ψ _ ψ. Proof. Let |∼ | and φ be as above. We let θφ _ be a formula such that ⟦θφ⟧=Norm(φ,|∼) _ =Norm( , | ) which exists due to Lemma 11. [Case “φ|∼ψ⇒Norm(φ,|∼)⊧ψ | ψ ( , | ) ψ”] If φ|∼ψ | ψ, then we obtain θφ⊧ψ _ ψ by definition of Norm(φ,|∼)Norm( , | ). [Case “θφ⊧ψ⇒φ|∼ψ _ ψ | ψ”] By Lemma 11, there exist M⊆(N)M (T_N) such that |∼(φ)=Th(M) C_ | ( )=Th(M) is true. We show that M⊆Norm(φ,|∼)M ( , | ) is true. Suppose not, i.e., there is an X∈MX∈ M such that X∉Norm(φ,|∼)X ( , | ). From the latter, we obtain that there is a formula γ with X⊧̸γX γ and φ|∼γ | γ. Now, from |∼(φ)=Th(M) C_ | ( )=Th(M), we can deduce X⊧δX δ for all δ∈|∼(φ)δ∈ C_ | ( ). Consequently, X⊧γX γ, as we have that γ∈|∼(φ)γ∈ C_ | ( ). This shows M⊆Norm(φ,|∼)M ( , | ). We then obtain that Th(Norm(φ,|∼))⊆Th(M)Th(Norm( , | )) (M) by employing M⊆Norm(φ,|∼)M ( , | ). Consequently, from Norm(φ,|∼)⊧ψNorm( , | ) ψ, we deduce that M⊧ψM ψ. Thus, by employing ⟦θφ⟧=Norm(φ,|∼) _ =Norm( , | ) and |∼(φ)=Th(M) C_ | ( )=Th(M), from which we have that θφ⊧ψ _ ψ implies φ|∼ψ | ψ. ∎ Next, we construct a cumulative model that captures |∼ | . The construction is inspired by the construction of ? (?). Let ∼ be the equivalence relation, respectively ⪯|∼ _ | be the relation, defined by φ∼ψ ψ if φ|∼ψ and ψ|∼φ, if | ψ and ψ | , [φ]∼⪯|∼[ψ]∼ [ ]_ _ | [ψ]_ if there exists γ∈[φ]∼ with ψ|∼γ. if there exists γ∈[ ]_ with ψ | γ\ . Define ℂ|∼=⟨,ℓ,⟩C_ | = S, , R , with ≔PL()/∼S ( dep)/ as follows: ℓ ≔([φ]∼,Norm(φ,|∼))∣φ∈PL(), \\,([ ]_ ,Norm( , | )) ( dep)\,\\ , R ≔([φ]∼,[ψ]∼)∣[φ]∼≠[ψ]∼ and [φ]∼⪯|∼[ψ]∼. \\,([ ]_ ,[ψ]_ ) [ ]_ ≠[ψ]_ and [ ]_ _ | [ψ]_ \,\\ . The states of ℂ|∼C_ | are the equivalence classes of ∼ . The function ℓ assign to every state [φ]∼[ ]_ the normal worlds of φ , and we have that [φ]∼[ψ]∼[ ]_ R[ψ]_ if [φ]∼[ ]_ and [φ]∼[ ]_ are different and [φ]∼⪯|∼[ψ]∼[ ]_ _ | [ψ]_ is true. Proposition 13. ⊆[]. PDL -2.15277pt 4.09024pt $ c$ PDL -2.15277pt 4.09024pt $ cuml$[$ str$]. Proof. First, we show that ℂ|∼C_ | is a strong cumulative model. One sees easily that ℂ|∼C_ | is a relational model and R is asymmetric. It suffices to show that for every formula φ the state [φ]∼[ ]_ is the unique element of min((φ),) (S( ), R). Suppose not, i.e., there is a state [ψ]∼∈min((φ),)[ψ]_ ∈ (S( ), R) different from [φ]∼[ ]_ . By definition, we have ℓ([ψ]∼)=Norm(ψ,|∼) ([ψ]_ )=Norm(ψ, | ) and hence, that Norm(ψ,|∼)⊆⟦φ⟧tNorm(ψ, | ) ^t is true. We obtain from the latter that ψ|∼φψ | is true by employing Theorem 12. From φ∈[φ]∼ ∈[ ]_ and ψ|∼φψ | , we obtain [φ]∼⪯|∼[ψ]∼[ ]_ _ | [ψ]_ . Consequently, we have that [φ]∼[ψ]∼[ ]_ R[ψ]_ , because of [φ]∼⪯|∼[ψ]∼[ ]_ _ | [ψ]_ and [φ]∼≠[ψ]∼[ ]_ ≠[ψ]_ . However, [φ]∼[ψ]∼[ ]_ R[ψ]_ is a contradiction to [ψ]∼∈min((φ),)[ψ]_ ∈ (S( ), R). To complete the proof, we show that |∼ | and |∼ℂ|∼ | _C_ | coincide. Due to Theorem 12, we have that φ|∼ψ | ψ if and only if Norm(φ,|∼)⊧ψNorm( , | ) ψ. By construction of ℂ|∼C_ | , it is true that min(⟦φ⟧t,R)=Norm(φ,|∼) ( ^t,R)=Norm( , | ). By definition, we get φ|∼ℂ|∼ψ | _C_ | ψ exactly when Norm(φ,|∼)⊧ψNorm( , | ) ψ. Consequently, we have that φ|∼ψ | ψ if and only if φ|∼ℂ|∼ψ | _C_ | ψ. ∎ Because []⊆ PDL -2.15277pt 4.09024pt $ cuml$[$ str$] PDL -2.15277pt 4.09024pt $ cuml$ holds, we obtain Theorem 9 from Proposition 13 and Proposition 10. 4.2 Propositional Logic with Team-based Semantics We show that classes of System C-based entailment relations and cumulative entailment relations coincide with cumulative entailment relations for propositional logic with classical semantics and the following kind of cumulative models. Definition 14. A relational model ℂ=⟨,ℓ,⟩C= S, , R for a logic ℒ L is called asymmetric if ℂC is cumulative, ≺ is asymmetric and for each state s∈Ss∈ S, the set ℓ(s) (s) is a singleton. With [] TPL -2.15277pt 4.09024pt $ cuml$[$ as$] we denote the class of entailment relations based on asymmetric models over TPL. Theorem 15. []==== TPL -2.15277pt 4.09024pt $ cuml$[$ as$]= CPL x= CPL y= TPL x= TPL y is true for all ,∈,[], x, y∈\\, cuml,\ cuml[str],\ c\,\. Proof. Note first that Proposition 8 implies that ==[] CPL -2.15277pt 4.09024pt $ c$= CPL -2.15277pt 4.09024pt $ cuml$= CPL -2.15277pt 4.09024pt $ cuml$[$ str$]. Furthermore, we have that []⊆ TPL -2.15277pt 4.09024pt $ cuml$[$ str$] TPL -2.15277pt 4.09024pt $ cuml$ and =\, TPL -2.15277pt 4.09024pt $ c$= CPL -2.15277pt 4.09024pt $ c$\, are immediate consequences of the definitions. Finally, the analogue of Prop. 10 can be used to show that ⊆ TPL -2.15277pt 4.09024pt $ cuml$\, \, TPL -2.15277pt 4.09024pt $ c$ is true. Let us then show that []⊆[]\, CPL -2.15277pt 4.09024pt $ cuml$[$ str$]\, \, TPL -2.15277pt 4.09024pt $ cuml$[$ str$]\,. Let |∼ℂ∈[] | _ -2.0muC∈ CPL -2.15277pt 4.09024pt $ cuml$[$ str$] and ℂ=⟨,ℓ,⟩C= S, , R be the respective strong cumulative model for CPL. We reinterpret ℂC as a strong cumulative model ℂ′=⟨′,ℓ′,′⟩C = S , , R for TPL with ′=,S =S,, ℓ′=(s,ℓ(s))∣s∈ =\\,(s,\ (s)\) s \,\, ′=. R = R. Because in TPL is holds that (⋆ ) ν⊧φ\ν\ if and only if ν⊧cφν ^c for all singleton teams ν\ν\, we obtain then |∼ℂ=|∼ℂ′ | _ -2.0muC= | _C . Next, we show that []⊆[] CPL -2.15277pt 4.09024pt $ cuml$[$ str$] TPL -2.15277pt 4.09024pt $ cuml$[$ as$] is true. Note that any strong cumulative model ℂ=⟨,ℓ,⟩C= S, , R for CPL can be reinterpreted (ℓ(s)=ν1,…,νm (s)=\\, _1,…, _m\,\ becomes ℓ(s)=ν1,…,νm (s)=\\,\ _1,…, _m\\,\) as an asymmetric model for TPL, hence by the flatness property of TPL-formulas and (⋆ ) above the claim follows. Finally, we show that []⊆ TPL -2.15277pt 4.09024pt $ cuml$[$ as$] CPL -2.15277pt 4.09024pt $ cuml$ holds. Note that any asymmetric model ℂ=⟨,ℓ,⟩C= S, , R for TPL can be interpreted (ℓ(s)=ν1,…,νm (s)=\\,\ _1,…, _m\\,\ becomes ℓ(s)=ν1,…,νm (s)=\\, _1,…, _m\,\) as a cumulative model ℂC for CPL. By the flatness property of TPL-formulas and (⋆ ) above it follows that |∼ℂ=|∼ℂ′ | _ -2.0muC= | _C . ∎ 5 Conclusion In this paper, we proved representation theorems between entailment relations based on System C and based on cumulative reasoning for propositional dependence logic and propositional logic with team semantics. Hence, they are forming, in the context of these logics, a stable class which is justified to be denoted as cumulative logics. The results from SMK (?) and KLM (?), and the novel results from this paper, yield a diverse landscape as shown in Figure 1. [⋆] TPL -2.15277pt 4.09024pt $ pref$$[ ]$∩ TPL -2.15277pt 4.09024pt $ pref$∩ TPL -2.15277pt 4.09024pt $ p$ TPL -2.15277pt 4.09024pt $ p$ = CPL -2.15277pt 4.09024pt $ p$ = CPL -2.15277pt 4.09024pt $ pref$ TPL -2.15277pt 4.09024pt $ pref$[] TPL -2.15277pt 4.09024pt $ cuml$[$ as$] = TPL -2.15277pt 4.09024pt $ c$ = CPL -2.15277pt 4.09024pt $ c$ = TPL -2.15277pt 4.09024pt $ cuml$ = CPL -2.15277pt 4.09024pt $ cuml$[⋆] PDL -2.15277pt 4.09024pt $ pref$$[ ]$ = [△] PDL -2.15277pt 4.09024pt $ pref$$[ ]$ = ∩ PDL -2.15277pt 4.09024pt $ pref$∩ PDL -2.15277pt 4.09024pt $ p$ PDL -2.15277pt 4.09024pt $ p$ PDL -2.15277pt 4.09024pt $ pref$ PDL -2.15277pt 4.09024pt $ c$ = PDL -2.15277pt 4.09024pt $ cuml$ Figure 1: Landscape of classes of entailment relations. For not defined classes, consult SMK (?) or the supplemental material. On our future agenda, we will extend our work to other team-based logics. Furthermore, we will study subclasses of the rich landscape of cumulative reasoning, such as preferential reasoning (KLM ?), c-inference (?), lexicographic inference (?) or System W (?). References Baumann and Strass 2025 Baumann, R., and Strass, H. 2025. Consequence operators of characterization logics – the case of abstract argumentation. In Dodaro, C.; Gupta, G.; and Martinez, M. V., eds., Logic Programming and Nonmonotonic Reasoning, 154–166. Cham: Springer Nature Switzerland. Brewka, Dix, and Konolige 1997 Brewka, G.; Dix, J.; and Konolige, K. 1997. Nonmonotonic Reasoning: An Overview, volume 73 of CSLI Lecture Notes. CSLI Publications, Stanford, CA. Denecker, Marek, and Truszczyński 2000 Denecker, M.; Marek, V.; and Truszczyński, M. 2000. Approximations, Stable Operators, Well-Founded Fixpoints and Applications in Nonmonotonic Reasoning. Boston, MA: Springer US. 127–144. Dix and Makinson 1992 Dix, J., and Makinson, D. 1992. The relationship between klm and mak models for nonmonotonic inference operations. Journal of Logic, Language, and Information 1(2):131–140. Gabbay 1984 Gabbay, D. M. 1984. Theoretical foundations for non-monotonic reasoning in expert systems. In Apt, K. R., ed., Logics and Models of Concurrent Systems, volume 13 of NATO ASI Series, 439–457. Springer. Hannula et al. 2018 Hannula, M.; Kontinen, J.; Virtema, J.; and Vollmer, H. 2018. Complexity of propositional logics in team semantic. ACM Trans. Comput. Log. 19(1):2:1–2:14. Kern-Isberner 2001 Kern-Isberner, G. 2001. Conditionals in Nonmonotonic Reasoning and Belief Revision - Considering Conditionals as Agents, volume 2087 of Lecture Notes in Computer Science. Springer. Komo and Beierle 2022 Komo, C., and Beierle, C. 2022. Nonmonotonic reasoning from conditional knowledge bases with system W. Ann. Math. Artif. Intell. 90(1):107–144. Kraus, Lehmann, and Magidor 1990 Kraus, S.; Lehmann, D.; and Magidor, M. 1990. Nonmonotonic reasoning, preferential models and cumulative logics. Artif. Intell. 44(1-2):167–207. Lehmann 1995 Lehmann, D. 1995. Another perspective on default reasoning. Ann. Math. Artif. Intell. 15(1):61–82. Makinson 1989 Makinson, D. 1989. General theory of cumulative inference. In Proceedings of the 2nd International Workshop on Non-Monotonic Reasoning, 1–18. Berlin, Heidelberg: Springer-Verlag. Sauerwald, Meier, and Kontinen 2025 Sauerwald, K.; Meier, A.; and Kontinen, J. 2025. On the Complexity and Properties of Preferential Propositional Dependence Logic. In Proceedings of the 22nd International Conference on Principles of Knowledge Representation and Reasoning, 523–533. Shoham 1988 Shoham, Y. 1988. Reasoning About Change: Time and Causation from the Standpoint of Artificial Intelligence. MIT Press. Yan 2023 Yan, J. 2023. Monotonicity in Intensional Contexts: Weakening and Pragmatic Effects under Modals and Attitudes. Ph.D. Dissertation, University of Amsterdam. Yang and Vänänen 2016 Yang, F., and Vänänen, J. 2016. Propositional logics of dependence. Ann. Pure Appl. Logic 167(7):557–589. Yang 2014 Yang, F. 2014. On Extensions and Variants of Dependence Logic. Ph.D. Dissertation, University of Helsinki. Supplemental Material This part contains supplemental information on the relationship among classes of entailment relations and proofs. Appendix A Landscape: Classes of Entailment Relations We summarise hierarchies of classes of entailment relations provided by SMK (?), KLM (?) and this paper. Boxes contain known equivalent classes, lines stand for inclusions, whereby solid lines are strict inclusions. We start with the hierarchy of classes of entailment relations over the language PLPL: [⋆] TPL -2.15277pt 4.09024pt $ pref$$[ ]$∩ TPL -2.15277pt 4.09024pt $ pref$∩ TPL -2.15277pt 4.09024pt $ p$ TPL -2.15277pt 4.09024pt $ p$ = CPL -2.15277pt 4.09024pt $ p$ = CPL -2.15277pt 4.09024pt $ pref$ TPL -2.15277pt 4.09024pt $ pref$[] TPL -2.15277pt 4.09024pt $ cuml$[$ as$] = TPL -2.15277pt 4.09024pt $ c$ = CPL -2.15277pt 4.09024pt $ c$ = TPL -2.15277pt 4.09024pt $ cuml$ = [] TPL -2.15277pt 4.09024pt $ cuml$[$ str$] = CPL -2.15277pt 4.09024pt $ cuml$ = [] CPL -2.15277pt 4.09024pt $ cuml$[$ str$] Next, we consider the hierarchy of classes of entailment relations over the language PL()PL( dep): [⋆] PDL -2.15277pt 4.09024pt $ pref$$[ ]$ = [△] PDL -2.15277pt 4.09024pt $ pref$$[ ]$ = ∩ PDL -2.15277pt 4.09024pt $ pref$∩ PDL -2.15277pt 4.09024pt $ p$ PDL -2.15277pt 4.09024pt $ p$ PDL -2.15277pt 4.09024pt $ pref$ PDL -2.15277pt 4.09024pt $ c$ = PDL -2.15277pt 4.09024pt $ cuml$ = [] PDL -2.15277pt 4.09024pt $ cuml$[$ str$] Classes not defined in the main part of this paper are defined in SMK (?) and KLM (?). We briefly describe them below; for the exact definitions, please consult the respective literature. • CPL -2.15277pt 4.09024pt $ pref$ contains all entailment relations for CPL that are defined by a preferential model (?), i.e., cumulative models in which for every state S, the set ℓ(s) (s) contains exactly one element, and R is a strict partial order. • PDL -2.15277pt 4.09024pt $ pref$, respectively TPL -2.15277pt 4.09024pt $ pref$, from SMK (?) contain all entailment relations for PDL, respectively TPL, that are defined for preferential models (see at CPL -2.15277pt 4.09024pt $ pref$). • PDL -2.15277pt 4.09024pt $ p$ and TPL -2.15277pt 4.09024pt $ p$ from SMK (?), and CPL -2.15277pt 4.09024pt $ p$ from KLM (?), are analogously defined to PDL -2.15277pt 4.09024pt $ c$, TPL -2.15277pt 4.09024pt $ c$ and CPL -2.15277pt 4.09024pt $ c$ via using System P instead of System C. One obtains System P by extending System C by the following rule: φ|∼γψ|∼γφ∨ψ|∼γ | γ 14.22636ptψ | γ ψ | γ (Or) • [⋆] PDL -2.15277pt 4.09024pt $ pref$$[ ]$, respectively [⋆] TPL -2.15277pt 4.09024pt $ pref$$[ ]$, from SMK (?) is the restrictions to preferential models which satisfy the so-called (⋆ ‣ • ‣ A)-property, min(⟦φ∨ψ⟧,≺)⊆min(⟦φ⟧,≺)∪min(⟦ψ⟧,≺) ( ψ , ) ( , )∪ ( ψ , ) (⋆ ) forcing that minimal models of a disjunction split to minimal models of the disjuncts. • [△] PDL -2.15277pt 4.09024pt $ pref$$[ ]$ from SMK (?) is PDL -2.15277pt 4.09024pt $ pref$ over preferential models restricted such that minimal states contain only singleton teams. Appendix B Complete Proofs In this supplement, we provide more detailed and missing proofs from the main paper. Proposition 10. ⊆ PDL -2.15277pt 4.09024pt $ cuml$ PDL -2.15277pt 4.09024pt $ c$. Proof. Let |∼ℂ∈ | _ -2.0muC∈ PDL -2.15277pt 4.09024pt $ cuml$ be a cumulative entailment relation that is based on a cumulative model ℂ=⟨,ℓ,⟩C= S, , R . We show that |∼ℂ | _ -2.0muC satisfies all rules of System C: [3.] Considering the definition of |∼ℂ | _ -2.0muC yields that φ|∼ℂφ | _ -2.0muC if for all minimal s∈(φ)s ( ) it holds that ℓ(s)⊧φ (s) . By the definition of (φ)S( ), we have s∈(φ)s ( ) if ℓ(s)⊧φ (s) . Consequently, we have that φ|∼ℂφ | _ -2.0muC . [LLE.] From φ≡ψ ≡ψ, we obtain that (φ)=(ψ)S( )=S(ψ) holds. By using this last observation and the definition of |∼ℂ | _ -2.0muC, we obtain ψ|∼ℂγψ | _ -2.0muCγ from φ|∼ℂγ | _ -2.0muCγ. [RW.] Clearly, by definition of φ⊧ψ ψ we have that ⟦φ⟧ℂ⊆⟦ψ⟧ℂ ^C ψ ^C. From the definition of γ|∼ℂφγ | _ -2.0muC , we obtain that ℓ(s)⊧φ (s) holds for each minimal s∈(γ)s (γ). The condition ℓ(s)⊧φ (s) in the last statement is equivalent to stating ℓ(s)∈⟦φ⟧ℂ (s)∈ ^C. Because of ⟦φ⟧ℂ⊆⟦ψ⟧ℂ ^C ψ ^C, we also have that ℓ(s)∈⟦ψ⟧ℂ (s)∈ ψ ^C; and hence, ℓ(s)⊧ψ (s) ψ for each minimal s∈(γ)s (γ). This shows that γ|∼ℂψγ | _ -2.0muCψ holds. [Cut.] By unfolding the definition of |∼ℂ | _ -2.0muC, we obtain min((φ∧ψ),)⊆(γ) (S( ψ), R) (γ) from φ∧ψ|∼ℂγ ψ | _ -2.0muCγ. Analogously, φ|∼ℂψ | _ -2.0muCψ unfolds to min((φ),)⊆(ψ) (S( ), R) (ψ). Moreover, employing basic set theory yields that (φ∧ψ)=(φ)∩(ψ)⊆(φ)S( ψ)=S( ) (ψ) ( ) holds. From (φ∧ψ)⊆(φ)S( ψ) ( ) and min((φ),)⊆(ψ) (S( ), R) (ψ), we obtain min((φ),)⊆(φ∧ψ) (S( ), R) ( ψ). Consequently, we also have that min((φ),)=min((φ∧ψ),) (S( ), R)= (S( ψ), R) holds. Using the last observation and min((φ∧ψ),)⊆(γ) (S( ψ), R) (γ), we obtain min((φ),)⊆(γ) (S( ), R) (γ). Hence also φ|∼ℂγ | _ -2.0muCγ holds. [CM.] By unfolding the definition of |∼ℂ | _ -2.0muC, we obtain min((φ),)⊆(ψ) (S( ), R) (ψ) and min((φ),)⊆(γ) (S( ), R) (γ). We have to show that min((φ∧ψ),)⊆(γ) (S( ψ), R) (γ) holds. If (φ∧ψ)=∅S( ψ)= holds, we immediately obtain min((φ∧ψ),)=∅⊆(γ) (S( ψ), R)= (γ) holds. We continue with the case of (φ∧ψ)≠∅S( ψ)≠ . Because R is smooth, we have min((φ∧ψ),)≠∅ (S( ψ), R)≠ . Let s be element of min((φ∧ψ),) (S( ψ), R). Clearly, we have that s∈(φ)s ( ) holds. We show by contradiction that s is minimal in (φ)S( ). Assume that s is not minimal in (φ)S( ). From the smoothness condition, we obtain that there is a state s′∈(φ)s ( ) such that s′s Rs and s′s is minimal in (φ)S( ) with respect to R. Because s′s is minimal in (φ)S( ) and because we have min((φ),)⊆(ψ) (S( ), R) (ψ), we also have that s′∈(ψ)s (ψ) holds and hence that s′∈(φ∧ψ)s ( ψ) holds. The latter contradicts the minimality of s in (φ∧ψ)S( ψ). Consequently, we have that s∈min((φ),)s∈ (S( ), R) holds. Because we have that min((φ),)⊆(γ) (S( ), R) (γ), we obtain φ∧ψ|∼ℂγ ψ | _ -2.0muCγ.∎ Next, we will consider Lemma 11, Lemma 11. The following statements are true: (a) For |∼∈ | ∈ PDL -2.15277pt 4.09024pt $ c$ we have that C|∼(φ)=Cn(C|∼(φ))C_ | ( )=Cn(C_ | ( )). (b) For each formula φ there exists an M⊆(N)M (T_N) such that Cn(φ)=Th(M)Cn( )=Th(M) and M=⟦φ⟧M= . (c) For each set of formulas F with F=Cn(F)F=Cn(F) there exists a formula φF _F such that F=Cn(φF)F=Cn( _F) is true. The following Lemma B.1 to Lemma B.3 prove Lemma 11. We start with observing that consequences under System C are closed under classical consequence. Lemma B.1. For |∼∈ | ∈ PDL -2.15277pt 4.09024pt $ c$ we have that C|∼(φ)=Cn(C|∼(φ))C_ | ( )=Cn(C_ | ( )). Proof. We obtain C|∼(φ)⊆Cn(C|∼(φ))C_ | ( ) (C_ | ( )) by definition and reflexivity of ⊧ . Now assume that C|∼(φ)⊊Cn(C|∼(φ))C_ | ( ) (C_ | ( )) is true, i.e., there is ψ∈C|∼(φ)ψ _ | ( ) and γ∈Cn(C|∼(φ))γ (C_ | ( )) such that ψ⊧γψ γ and γ∉C|∼(φ)γ _ | ( ). Now recall that |∼ | satisfies (RW), and hence, we also have φ|∼γ | γ, because ψ⊧γψ γ and φ|∼ψ | ψ is true. From φ|∼γ | γ, we obtain the contradiction γ∈C|∼(φ)γ _ | ( ). ∎ The theory Th(M)Th(M) of a set of teams M is given by Th(M)=φ∈ℒ∣X⊧φ for all X∈M.Th(M)=\\, X for all X∈ M\,\\ . For every set of classical consequences of a formula φ , there is a set of teams whose theory yields the same consequences. Because this is a direct consequence of the semantics, we omit a proof here. Lemma B.2. For each formula φ there exists an M⊆(N)M (T_N) such that Cn(φ)=Th(M)Cn( )=Th(M) and M=⟦φ⟧tM= ^t. Because we consider online finite signatures here, we obtain the following result. Lemma B.3. For each set of formulas F with F=Cn(F)F=Cn(F) there exists a formula φF _F such that F=Cn(φF)F=Cn( _F). Proof. We will employ the underlying logic N PDL_N, where we have a finite signature N⊆N Prop. It has been shown that classical disjunction is expressible in N PDL_N, i.e., for two formulas φ,ψ ,ψ there is a formula φ∨⃝ψ ψ with ⟦φ∨⃝ψ⟧t=⟦φ⟧t∪⟦ψ⟧t ψ ^t= ^t∪ ψ ^t (? ?). Moreover, every downward-closed set of teams is M definable, i.e., there is a φM _M with ⟦φM⟧t=M _M ^t=M. Because N is finite, for every set of formulas F the set ⟦F⟧t F ^t is a finite disjunction of downward-closed sets of teams, i.e., ⟦F⟧t=M1∪…∪Mn F ^t=M_1∪…∪ M_n. Hence, for φF=∨⃝i=1nφMi _F= _i=1^n _M_i we have ⟦F⟧t=⟦φF⟧t F ^t= _F ^t. ∎