Relevance in Structured Argumentation

1 Introduction

In this paper we investigate conditions under which the nonmonotonic consequence relation of a given structured argumentation system is robust when irrelevant information is added or removed. Relevance can hereby be understood in two ways. First, syntactically as information that shares propositional variables with the information at hand. Second, semantically, as information that for some reason should not be considered to have defeating power over previously accepted arguments.

Structured argumentation has been studied in various settings such as ASPIC [Prakken, 2010], ABA [Bondarenko et al., 1997], and logic-based argumentation [Arieli and Straßer, 2015; Besnard and Hunter, 2014]. These frameworks share the underlying idea that arguments are to have a logical structure and attacks between them are at least partially determined by logical considerations. Although investigations into translations between these frameworks have been intensified recently [Heyninck and Straßer, 2016], the frameworks are in various aspects difficult to compare and results obtained in one do not easily transfer to others. For this reason, we decided in this paper to study relevance-related properties for structured argumentation on the basis of a simple framework for structured argumentation that allows us, on the one hand, to abstract away from particularities of the systems from the literature and, on the other hand, to translate these frameworks easily. The framework is simple in that arguments are premise-conclusion pairs (Γ, γ) obtained from a given consequence relation and it only allows for one type of attack (attacks in premises). The obtained simplicity makes studying meta-theory technically straight-forward and the availability of the translations makes results easily transferable.

The paper is structured as follows. In Section 2 we introduce our general setting for structured argumentation. In Section 3 we define the basic relevance-related properties that we will investigate in this paper. In Section 4 we show how many of the most common systems of structured argumentation can be represented in our setting. In Section 5 we prove our main results. We conclude in Section 6.

2 General Setting

In the following we work with a simple setting for structured argumentation. It is abstract in the sense that it allows for instantiations that are adequate representations of many of the available systems of structured argumentation such as logicbased argumentation, ASPIC, ABA, etc. (see Sec. 4). In this contribution we restrict ourselves to non-prioritized settings.

We suppose to have available a formal language L (we denote the set of well-formed formulas over L also by L) and a relation ⊢ ⊆ ℘fin(L) × L (where ℘fin denotes the set of finite subsets) which we will refer to as the deducability relation. We do not suppose any of the usual Tarskian properties in what follows (reflexivity, transitivity, and monotonicity).

Definition 1 (Arg⊢(·)). Given a set of formulas S ⊆ L we denote by Arg⊢(S) the set of S-based arguments: (Γ, γ) ∈ Arg⊢(S) iff Γ ⊢ γ for Γ ⊆ S. Given a = (Γ, γ) ∈ Arg⊢(S), Conc(a) = γ and Supp(a) = Γ.

To accommodate argumentative attacks we suppose to have two functions: a contrariness function · : L → ℘(L) that associates each formula with a set of conflicting formulas and a function̂· : ℘fin(L) \ ∅ → ℘fin(L) that associates support sets with sets of formulas in which they can be attacked.

Remark 1. Often ̂· will simply be the identity function, although another option is, e.g., ̂Γ = {∧ Γ′ | ∅ ̸= Γ′ ⊆ Γ}.

Definition 2 (AF⊢). An (argumentation) setting is a triple AF⊢ = (⊢, ·,̂·). A setting based on S ⊆ L is given by the quadruple AF⊢(S) = (S, ⊢, ·,̂·).

Example 1. A simple example of a setting is AF pdef ⊢CL = (⊢CL, ·, id) where ⊢CL is the deducability relation of classical propositional logic and φ = {¬φ}.

Example 2. Another example is the setting AF def ⊢CL = (⊢CL , ·,̂·) where φ = {¬φ} and ̂Γ = {∧ ∆ | ∅ ̸= ∆ ⊆ Γ}.

Definition 3 (Attacks). Given an setting AF⊢(S), where a = (Γ, γ) ∈ Arg⊢(S) and b = (Γ′ , γ ′ ) ∈ Arg⊢(S), a attacks b (in φ) iff there is a φ ∈ ̂ Γ′ for which γ ∈ φ.

Our attack form is sometimes called premiseattack [Prakken, 2010] or directed undercut [Besnard and Hunter, 2014]. In Section 4 we will show that by adjusting · and ̂· adequately we are able to accommodate many other attack forms defined in the literature.

Definition 4 (Attack Diagram). Given a setting AF⊢(S), its attack diagram is the directed graph with the set of nodes Arg⊢(S) and edges between a and b iff a attacks b.

Definition 5 (Dung Semantics, [Dung, 1995]). Where AF⊢(S) is a setting and A ⊆ Arg⊢(S) we define: A is conflict-free iff there are no a, b ∈ A such that a attacks b. A defends a ∈ Arg⊢(S) iff for each attacker b ∈ Arg⊢(S) of a there is a c ∈ A that attacks b. A is admissible iff it is conflict-free and it defends every a ∈ A. A is complete iff it is admissible and it contains every a ∈ Arg⊢(S) it defends. A is preferred iff it is ⊆-maximal complete. A is grounded iff it is ⊆-minimal complete. A is stable iff it is admissible and for all a ∈ Arg⊢(S) \ A there is a b ∈ A that attacks a.

We denote the set of all admissible [complete, preferred, stable] sets A (also called "extensions") by Adm(AF⊢(S)) [Cmp(AF⊢(S)), Prf(AF⊢(S)), Stb(AF⊢(S))] and the grounded set by Grd(AF⊢(S)).

Definition 6 (Consequence Relations). Where Sem ∈ {Grd, Prf, Stb}, and given a setting AF⊢ we define: S |∼AF⊢ Sem φ iff for all A ∈ Sem(AF⊢(S)) there is an a ∈ A with Conc(a) = φ.

Where the setting AF⊢ is clear from the context we will simply write |∼Sem to avoid clutter.

Remark 2. For reasons of space we restrict our focus in this paper on skeptical consequence as defined in Definition 6. Note that |∼AF⊢ Cmp coincides with |∼AF⊢ Grd .

3 The Relevance Properties

3.1 Syntactic Relevance

A syntactical relevance property that has been proposed in the context of structured argumentation is noninterference [Caminada et al., 2011]. Let us call two sets of formulas syntactically disjoint if no atom that occurs in a formula in S1 also occurs in a formula in S2 and vice versa: so Atoms(S1) ∩ Atoms(S2) = ∅ where Atoms(S) is the set of atoms occurring in formulas in S. In such cases we write: S1 | S2.

Definition 7 (Non-Interference, [Caminada et al., 2011]). |∼ ⊆ ℘(L) × L satisfies Non-Interference iff for all S1 ∪ {φ} ∪ S2 ⊆ L for which (S1 ∪ {φ}) | S2 we have: 1 S1 |∼φ iff S1 ∪ S2 |∼φ.

Definition 8 (Contamination, [Caminada et al., 2011]). Let |∼ ⊆ ℘(L)×L be a consequence relation. A set S ⊆ L, such that Atoms(S) ⊂ Atoms(L), is called contaminating (with respect to |∼), if for any set of formulas S ′ ⊆ L such that S | S ′ and for every φ ∈ L, it holds that S |∼ φ if and only if S ∪S ′ |∼ φ.

Consequence relations that are non-trivial and satisfy NonInterference also satisfy Crash-Resistance: 2

Definition 9 (Crash-Resistance, [Caminada et al., 2011]). A consequence relation |∼ ⊆ ℘(L) × L satisfies CrashResistance iff there is no set S ⊆ L that is contaminating with respect to |∼.

Given a setting AF⊢, a natural question is whether NonInterference is a property that gets inherited on the level of non-monotonic inference |∼Sem from ⊢: we will show below that in case ⊢ satisfies Non-Interference so does |∼Sem . In fact, the following less requiring criterion is sufficient:

Definition 10 (Pre-Relevance). ⊢ ⊆ ℘(L) × L satisfies PreRelevance iff for all S1 ∪ {φ} ∪ S2 ⊆ L for which S1 ∪ {φ} | S2: if S1 ∪ S2 ⊢ φ then there is a S ′1 ⊆ S1 such that S ′1 ⊢ φ.

When considering attacks we need to extend the notion of Pre-Relevance by taking into account̂· and ·. We first define:

Definition 11 (Prime settings). A setting (⊢, ·,̂·) is prime iff for all sets of atoms A1 and A2 in L for which A1 | A2, for all S1, T1, S2, T2 ∈ ℘fin(L) for which Atoms(S1), Atoms(T1) ⊆ A1 and Atoms(S2), Atoms(T2) ⊆ A2, and for all φ and ψ for which ψ ∈ φ and φ ∈ ̂ T1 ∪ T2, we have:

if S1 ∪ S2 ⊢ ψ then there are i ∈ {1, 2}, S ′ i ⊆ Si, φi ∈ ̂ Ti and ψi ∈ φi for which S ′ i ⊢ ψi.

Definition 12 (Pre-Relevant Settings). A setting AF = (⊢,·,̂·) is Pre-Relevant iff (i) ⊢ is Pre-Relevant, (ii) AF is prime, and (iii) ̂· is ⊆-monotonic (i.e., for all ∆,∆′ ∈ ℘fin(L), ̂∆ ⊆ ̂ ∆ ∪ ∆′ ).

Example 3. Note that ̂· : ∆ ↦→ ∆ (see Ex. 1) and̂· : ∆ ↦→ {∧ ∆′ | ∅ ⊂ ∆′ ⊆ ∆} (see Ex. 2) are both ⊆-monotonic.

Fact 1. Wherê· = id(·) (see Ex. 1) and γ = {¬γ}, the PreRelevance of (⊢, ·,̂·) follows from the Pre-Relevance of ⊢.

Proof. Items (i) and (iii) are trivial. For Item (ii) suppose that S1 ∪ S2 ⊢ ψ, where ψ = ¬φ and φ ∈ ̂ T1 ∪ T2 = T1 ∪ T2 and where S1, S2, T1, T2 are as in Def. 11. Thus, there is an i ∈ {1, 2} s.t. φ ∈ Ti. Thus, Atoms(ψ) ⊆ Ai. By the PreRelevance of ⊢, there is an S ′ i ⊆ Si for which S ′ i ⊢ ψ.

1 A similar property is Basic Relevance [Avron, 2014, Definition 3.1].

2 |∼ is non-trivial if there are always two sets of formulas with the same atoms but different conclusions (see [Caminada et al., 2011]).

Fact 2. Where ̂∆ = {∧ ∆′ | ∅ ⊂ ∆′ ⊆ ∆} (see Ex. 2), γ = {¬γ} and ⊢ is contrapositable (i.e., S ⊢ ¬ ∧(∆∪∆′ ) implies S ∪∆′ ⊢ ¬ ∧ ∆), the Pre-Relevance of (⊢, ·,̂·) follows from the Pre-Relevance of ⊢.

In Section 5.1 we will show that:

Theorem1. If AF⊢ satisfies Pre-Relevance then |∼AF⊢ Sem satisfies Non-Interference for each Sem ∈ {Grd, Prf}.

Example 4. We take the setting AF⊢RM = (⊢RM, ·, id), where ⊢RM is the consequence relation of the semi-relevance logic RM and · : φ ↦→ {¬φ}. ⊢RM satisfies Pre-Relevance (see [Avron, 2016, Prop. 6.5]) and thus AF⊢RM satisfies NonInference and Crash-Resistance. Similar for other relevance logics.

Example 5. Although ⊢CL does not satisfy Pre-Relevance, ⊢⊤CL does, where ⊢⊤CL is the restriction of ⊢CL to pairs (Γ, γ) for which ⊬CL ¬ ∧ Γ. Hence, AF⊢⊤CL = (⊢⊤CL , ·, id) where · : φ ↦→ {¬φ} satisfies Non-Interference. In [Wu and Podlaszewski, 2014] such a restriction is applied in the context of ASPIC.

Example 6. Recently paraconsistent logics based on maximal consistent subsets [Grooters and Prakken, 2016] have been used in the context of structured argumentation. Let Γ ⊢∩mcs φ [Γ ⊢∪mcs φ] iff for all [some] maximal consistent subsets Γ′ of Γ, Γ′ ⊢CL φ. (Γ′ ⊆ Γ is a maximal consistent subset of Γ if it is consistent and there are no consistent Γ′′ ⊆ Γ such that Γ′ ⊂ Γ′′ .) Such consequence relations satisfy Pre-Relevance and thus, argumentative settings based on them satisfy NonInterference.

A refinement of Theorem 1 is given in Corollary 1 below.

Definition 13. Given a setting (⊢, ·,̂·) let ⊢∅ be the restriction of ⊢ to pairs (Γ, γ) for which there is no (∅, δ) ∈ ⊢ such that δ ∈ ψ for some ψ ∈ ̂Γ.

Since arguments with empty supports have no attackers we have:

Lemma 1. Where Sem ∈ {Grd, Prf} and S ⊆ L,

Corollary 1. If AF⊢∅ satisfies Pre-Relevance then |∼AF⊢ Sem satisfies Non-Interference for each Sem ∈ {Grd, Prf}.

We illustrate the latter point with an example.

Example 7. Also the setting AF def ⊢CL in Ex. 2 satisfies NonInterference. Note for this that ⊢∅CL = ⊢⊤CL (where the latter is defined as in Ex. 5) in the context of AF def ⊢CL .

In the following sections we will relate these results to systems of structured argumentation from the literature.

3.2 Semantic Relevance

As for semantic relevance we study in this paper a criterion known from non-monotonic logic, namely Cumulativity.

Definition 14. Given ⊢ ⊆ ℘(L) × L and φ ∈ L, let ⊢+φ be the transitive closure of ⊢ ∪ {(∅, φ)}. Given a setting AF⊢ and a semantics Sem ∈ {Grd, Prf} let |∼+φ Sem be an abbreviation of |∼AF ⊢+φ Sem and AF +φ ⊢ for AF⊢+φ.

On the level of consequence relations Cumulativity is the following property, intuitively expressing that the consequence set is invariant under the addition of derivable formulas to the premises:

Definition 15 (Cumulativity). A setting AF⊢ satisfies Cumulativity for Sem ∈ {Grd, Prf}, iff, for all S ∪ {φ, ψ} ⊆ L such that S |∼Sem φ we have: S |∼+φ Sem ψ iff S |∼Sem ψ.

On the level of Dung-extensions, Cumulativity is:

Definition 16 (Extensional Cumulativity). A setting AF⊢ satisfies Extensional Cumulativity for Sem ∈ {Grd, Prf} iff for all S ∪ {φ} ⊆ L such that S |∼Sem φ we have: Sem(AF⊢(S)) = {E ∩ Arg⊢(S) | E ∈ Sem(AF⊢+φ(S))} .

We will show, in Section 5.2, that a setting AF⊢ satisfies Cumulativity for grounded semantics if AF⊢ is pointed:

Definition 17 (Pointed Settings). (⊢, ·,̂·) is pointed iff

1. for all Γ,∆ ∈ ℘fin(L),̂ Γ ∪ ∆ = ̂Γ ∪ ̂∆ (in this case we say that̂· is pointed), and
2. ⊢ satisfies Cut w.r.t. ⊢+φ for any φ ∈ L, i.e., for every Γ ∪ {γ} ⊆ L, Γ ∪ ∆ ⊢ γ if Γ ⊢ φ and ∆ ⊢+φ γ.

Theorem 2. Where AF⊢ is pointed, AF⊢ satisfies Cumulativity and Extensional Cumulativity for grounded semantics.

Example 8. Any setting (⊢, ·, id) is pointed iff ⊢ satisfies Cut. For instance, each of the consequence relations in Examples 1 and 4 satisfies Cut and thus the corresponding settings are pointed and therefore satisfy Cumulativity.

If we restrict ⊢ to consistent sets on the left side, denoted by ⊢con (see Def. 19 below) and if ⊢ satisfies Cut and Contraposition (see Def. 18 below), then the setting AFcon = (⊢con, ·, id) is cumulative. In more detail:

Definition 18. (⊢, ·) is contrapositable iff for all Θ ∈ ℘fin(L), if Θ ⊢ γ ′ where γ ′ ∈ γ then for all σ ∈ Θ, (Θ∪ {γ}) \ {σ} ⊢ σ′ for some σ′ ∈ σ. By extension we call AF⊢ = 〈⊢, ·,̂·〉 contrapositable if (⊢, ·) is contrapositable.

Definition 19. Where AF⊢ = 〈⊢, ·, id〉, a set Θ ⊆ S is AF⊢(S)-inconsistent iff there is a Θ′ ⊆ Θ and a γ ∈ Θ′ for which Θ \ {γ} ⊢ γ ′ where γ ′ ∈ γ. Θ is AF⊢(S)-consistent iff it is not AF⊢(S)-inconsistent.

Given ⊢, let ⊢con= {(Γ, γ) | Γ ⊢ γ and Γ is AF⊢-consistent}.

Theorem 3. Where AF⊢ = (⊢, ·, id) is contrapositable and ⊢ satisfies Cut, AFcon = (⊢con, ·, id) is cumulative and extensionally cumulative for Sem ∈ {Grd, Prf, Stb}.

Example 9. In view of Theorem 3, AF⊢⊤CL from Ex. 5 is cumulative for Sem ∈ {Grd, Stb, Prf}.

4 Systems of Structured Argumentation

In this section we take a look at several of the structured argumentation frameworks from the literature and show how they can be represented in our setting.

Example 10 (Logic-Based Argumentation). Logic-based argumentation is closest to our setting from Section 2. Systems can be found in, for instance, [Arieli and Straßer, 2015;

Besnard and Hunter, 2014]. 3 The core logic L is a finitary Tarskian logic with an adequate consequence relation ⊢ ⊆ ℘fin(L) × L. Given a set S ⊆ L, the set of arguments defined by Arg⊢(S) consists of all (Γ, γ) where Γ ⊢ γ and Γ ⊆ S just like in Def. 1. Different attack rules have been proposed, such as: (Γ, γ) attacks (∆, ψ) iff . . .

Dung semantics are defined as usual on top of an attack diagram analogous to Definitions 4 and 5. Consequence relations are defined analogous to Definition 6 S ‖∼Sem φ iff in all Sem-extensions there is an argument (Γ, φ).

Systems of logic-based argumentation translate rather directly to our setting. We only need to adjust the definitions of · and̂· so that we can use our attack definition to simulate the attack definitions above. The following table shows how:

The easy proof concerning the adequacy of our representations is omitted for reasons of space.

Remark 3. The definitions for direct attack forms (DiDef, DiUcut, DiCoDef) all give rise to a pointed̂· (namely id) in our representation. Thus, combining these attack forms with core logics L for which ⊢L satisfies Cut, we obtain Cumulativity.

Remark 4. Instantiating logic-based argumentation with a core logic that satisfies Pre-Relevance (such as the ones in Examples 4, 5, 6) we obtain Non-Interference.

Example 11 (Assumption-Based Argumentation (ABA), [Bondarenko et al., 1997]). Let L be a formal language, · : L → ℘(L) a contrariness function, Ab ⊆ L a subset of so-called assumptions, and R be a set of rules of the form φ1, . . . , φn → φ where φ1, . . . , φn, φ ∈ L and φ /∈ Ab. 4 There is an R-deduction from some ∆ ⊆ Ab to φ iff there is a sequence φ1, . . . , φn for which ∆ = {φ1, . . . , φn} ∩ Ab, φn = φ and for each 1 ≤ i ≤ n, φi is either in ∆ or there is a rule φi1 , . . . , φim → φi where i1, . . . , im < i. Given two sets of assumptions ∆,∆′ ⊆ Ab, ∆ attacks ∆′ iff there is a δ ∈ ∆′ for which there is an R-deduction of some ψ ∈ δ from some ∆′′ ⊆ ∆. Subsets of assumptions in Ab and attacks between them give rise to an attack diagram where nodes are sets of assumptions and arcs are attacks. Dung-style semantics are applied to these graphs: ∆ is conflict-free if it does not attack itself, ∆ is admissible if it defends itself, it is complete if it contains all assumptions it defends, it is preferred if it is maximally admissible and stable if it is admissible and attacks every assumption it does not contain. Given a semantics Sem, a consequence relation is given by (Ab, R) ‖∼aba Sem φ iff φ is R-derivable from all sets of assumptions ∆ ⊆ Ab that satisfy the requirements of Sem.

3 There are differences between these presentations: while [Besnard and Hunter, 2014] uses classical logic as a core logic, [Arieli and Straßer, 2015] allows for any Tarskian logic with an adequate sequent calculus to serve as core logic. [Besnard and Hunter, 2014] requires the support sets of arguments to be consistent and minimal while [Arieli and Straßer, 2015] omit this requirement. In what follows we follow the generalized setting of [Arieli and Straßer, 2015]. Consistency and minimality can easily be captured by changing the underlying relation ⊢ (see e.g., Ex. 5).

4 In this paper we restrict ourselves to so-called flat frameworks that satisfy the latter requirement.

In most presentations of ABA, the rules R are considered domain-specific strict inference rules that are part of a given knowledge base. They may also be obtained from an underlying core logic L with consequence relation ⊢L by setting φ1, . . . , φn → φ iff {φ1, . . . , φn} ⊢L φ.

We can translate ABA into our setting as follows. Where R represents domain-specific rules that are part of the knowledge base, we define for ∆ ⊆ Ab and R′ ⊆ R:

(†aba) ∆∪R′ ⊢ φ, iff, there is an R-deduction of φ from∆ making use of the rules in R′ (and only of these). 5

Where R is generated from a given core logic L, we define for ∆ ⊆ Ab:

In both cases, we use the definition of · from ABA, let ̂· = id(·). Clearly, in our setting (∆, δ) attacks (Γ, γ) iff δ ∈ φ for some φ ∈ Γ. For reasons of space we omit the proof that the setting AF⊢(Ab ∪ R) [resp. AF⊢(Ab)] adequately represents the ABA framework based on Ab and R for ⊢ in (†aba) [resp. (‡aba)] so that (Ab,R) ‖∼aba Sem φ iff Ab ∪ R |∼AF⊢ Sem φ [resp. Ab |∼AF⊢ Sem φ].

Remark 5. It is easy to see that for representation (†aba) the underlying consequence relation ⊢ satisfies Pre-Relevance and if (†) Atoms(φ) ⊆ Atoms(φ) for all φ ∈ L, we obtain Non-Interference. For the representation (‡aba) it depends on the logic L. In case ⊢L satisfies Pre-Relevance and if (†) we obtain Non-Interference.

Remark 6. Our representation of ABA makes use of the pointed̂· (namely id) and R-derivability satisfies Cut. Note that AF⊢+φ(Ab ∪ R) [resp. AF⊢+φ(Ab)] adequately represents the ABA framework based on (Ab, R ∪ {→ φ}) for ⊢ in (†aba) [resp. for ⊢ in (‡aba)]. Thus we obtain Cumulativity. Example 12 (ASPIC, [Prakken, 2010]). In ASPIC we work with a formal language L, a contrariness function · : L → ℘(L), a set of defeasible rules D and a set of strict rules R of the form A1, . . . , An ⇒ A resp. A1, . . . , An → A. Similarly as was the case for ABA, the strict rules may reflect domainspecific knowledge or be generated in view of an underlying core logic L. We assume that L contains for each defeasible rule R ∈ D a logical atom n(R) that serves as name of R. An (D, R)-deduction of φ ∈ L from ∆ ⊆ L is given by a tree

· whose leaves are labeled by elements in ∆ (so that each δ ∈ ∆ occurs as label of a leaf),

5 For this the language L underlying the original ABA framework is enriched by R so that ⊢ ⊆ ℘fin(L ∪R) ×L. This is important to track syntactic relevance.

• for every non-root node labeled by ψ there is a rule R = φ1, . . . , φn → ψ ∈ R or R = φ1, . . . , φn ⇒ ψ ∈ D and its child-nodes are labeled by φ1, . . . , φn (if R has an empty body, the single child-node is unlabeled). The edges connecting the child-nodes with the parent are labeled R. 6
• the root of the tree is labeled by φ.

Given a (D,R)-derivation a, DefC(a) [StrC(a)] is the set of all node labels to which an edge labeled with a defeasible [strict] rule leads and DefR(a) [StrR(a)] is the set of all edge labels that are defeasible [strict] rules.

An argumentation theory is a triple (P,R,D) where P ⊆ L is a set of premises, R is a set of strict rules and D is a set of defeasible rules. The set Argaspic(P,R,D) is the set of all (D, R)-derivations of some φ ∈ L from some finite ∆ ⊆ P. Given two arguments a, b ∈ Argaspic(P, R, D), a rebuts b iff there is a φ ∈ DefC(b) such that Conc(a) ∈ φ; a undercuts b iff a ∈ n(R) for some R ∈ DefR(b). Attack diagrams, underlying Dung-semantics and consequence relations ‖∼aspic Sem are then defined in the usual way.

To represent ASPIC in our setting we first need to define our derivability relation and then translate the ASPIC attacks. In case the set of strict rules R presents domainspecific knowledge we define:

(†aspic) Γ ⊢ φ iff there is a (D,R)-derivation a of φ from P where Γ = {R, n(R) | R ∈ DefR(a)} ∪ DefC(a) ∪ StrR(a) ∪ {→ ψ | ψ ∈ P}. 7

If R is generated via an underlying core logic we define:

For reasons of space we omit the proof that, where S = {R, n(R), Conc(R) | R ∈ D} ∪ {→ ψ | ψ ∈ P} and̂· = id(·), 8 the setting AF⊢(S∪R) [resp. AF⊢(S)] represents the ASPIC theory (P,R,D) for ⊢ in (†aspic) [resp. in (‡aspic)] so that (P, R, D) ‖∼aspic Sem φ iff S∪R|∼AF⊢ Sem φ [resp. S |∼AF⊢ Sem φ]. Remark 7. Analogous to Remark 5, if (†) holds, we obtain Non-Interference for the presentation (†aspic) and for (‡aspic) if additionally the underlying logic L satisfies Pre-Relevance. Remark 8. Our representation of ASPIC makes use of the pointed ̂· (namely id) and (D,R)-derivability satisfies Cut. Note that AF⊢+φ(S ∪R) [resp. AF⊢+φ(S)] adequately represents the ASPIC argumentation theory (P ∪ {φ}, R, D) for ⊢ in (†aspic) [resp. for ⊢ in (‡aspic)] and S as specified in Example 12. Thus we obtain Cumulativity for grounded semantics.

6 Usually edges are not labeled with rules in ASPIC (and so in cases of rules with empty bodies, there are usually no child-nodes either). We introduce these labels since they enable us to define our representation in a simpler way. We also simplify the presentation in that we do not assume there to be defeasible premises.

7 Similar as in the case of ABA we enrich the language L for ⊢ to track syntactic relevance. See Fn. 5.

8 For the variants ASPIC- [Caminada et al., 2014] and ASPIC⊖ [Heyninck and Straßer, 2017] where rebut is unrestricted we need to add StrC(a) to Γ in (†aspic) and (‡aspic). For generalized rebut in ASPIC⊖ we can proceed analogous to Ex. 2.

5 Meta-Theory

We will now present the proofs of Theorems 1 and 2. 9

5.1 Syntactic Relevance

In this section we prove Theorem 1. In the following we suppose that AF⊢ is a setting that satisfies Pre-Relevance (see Def. 12). We start with some notations:

Definition 20. Where S ⊆ L and a, b ∈ Arg⊢(S), we write a ⪯ b iff ̂ Supp(a) ⊆ ̂ Supp(b).

Definition 21. Where S ⊆ L and E ⊆ Arg⊢(S), let Defended(E,AF⊢(S)) be the set of all arguments a ∈ Arg⊢(S) that are defended by arguments in E.

In view of the monotonicity of ̂· we have:

Fact 3. Where b′ ⪯ b, if a attacks b′ then a attacks b.

Complete extensions are closed under ⪯:

Fact 4. Where S ⊆ L, E ∈ Cmp(AF⊢(S)), a ∈ E, and b ∈ Arg⊢(S), then b ∈ E if b ⪯ a.

Lemma 2. Where S | S ′ , if a ∈ Arg⊢(S ∪ S ′ ) attacks b ∈ Arg⊢(S), there is an a′ ∈ Arg⊢(S ∩Supp(a)) that attacks b.

Proof. Suppose a = (Γ, ψ) ∈ Arg⊢(S ∪ S ′ ) attacks b = (Λ, σ) ∈ Arg⊢(S). Then, ψ ∈ φ for some φ ∈ ̂Λ. Where A1 = Atoms(S), A2 = Atoms(S ′ ), T1 = Λ, T2 = ∅, S1 = Γ∩S and S2 = Γ∩S ′ , with Def. 11, S ′1 ⊢ ψ′ where S ′1 ⊆ S1, ψ′ ∈ φ′ and φ′ ∈ ̂Λ. Thus, (S ′1 , ψ′ ) ⪯ a attacks b.

Lemma 3. Where S | S ′ , E ∈ Cmp(AF⊢(S)), E ′ ∈ Cmp(AF⊢(S ′ )), E ∪ E ′ ∈ Adm(AF⊢(S ∪ S ′ )).

Proof. Suppose S | S ′ , E ∈ Cmp(AF⊢(S)) and E ′ ∈ Cmp(AF⊢(S ′ )). We now show that E ∪ E ′ is admissible.

Conflict-free: Assume for a contradiction that there are a, a′ ∈ E ∪ E ′ such that a attacks a′ . By the conflict-freeness of E and E ′ it is not the case that a, a′ ∈ E or a, a′ ∈ E ′ . Wlog. suppose a ∈ E and a′ ∈ E ′ . By Lemma 2, there is a b ∈ Arg⊢(S ′ ∩ Supp(a)) = Arg⊢(∅) that attacks a′ . Thus, b is trivially defended by E ′ and by the completeness of E ′ , b ∈ E ′ . This is a contradiction to the conflict-freeness of E ′ . Admissibility: Suppose some b ∈ Arg⊢(S ∪S ′ ) attacks some a ∈ E ∪ E ′ . Wlog. assume a ∈ E. By Lemma 2, there is a b′ ∈ Arg⊢(S ∩Supp(b)) that attacks a. Thus, there is a c ∈ E that attacks b′ . By Fact 3, c attacks b.

Lemma 4. Where S1 | S2, a, b ∈ Arg⊢(S1 ∪S2), Supp(b) = Θ and b attacks a,

1. some b′ ∈ Arg⊢(S1 ∩Θ) ∪Arg⊢(S2 ∩Θ) attacks a;
2. if a ∈ Arg⊢(S1), some b′ ∈ Arg⊢(S1 ∩Θ) attacks a.

Proof. Let a = (Γ, α) ∈ Arg⊢(S1∪S2). Suppose b = (Θ, β) attacks a. Thus, there is a γ ∈ ̂Γ s.t. β ∈ γ. By Def. 12 (ii), we have i ∈ {1, 2}, Θ′ ⊆ Θ ∩ Si, φ ∈ ̂ Γ ∩ Si and ψ ∈ φ s.t. b′ = (Θ′ , ψ) ∈ Arg⊢(Si). By Def. 12 (iii), ̂ Γ∩Si ⊆ ̂Γ and hence b′ attacks a. For Item 2 note that i = 1 when setting T1 = Γ and T2 = ∅ in Def. 11.

9 The proof of Theorem 3 is omitted for reasons of space.

Lemma 5. Where S | S ′ , E ∈ Cmp(AF⊢(S ∪ S ′ )), E1 = E ∩ Arg⊢(S) and E2 = E ∩ Arg⊢(S ′ ),

1. E = Defended(E1 ∪ E2,AF⊢(S ∪S ′ ));
2. E1 ∈ Cmp(AF⊢(S)).

Proof. Ad 1. Suppose E defends some a ∈ Arg⊢(S ∪ S ′ ). By Lemma 4 and Fact 4, E1 ∪ E2 defends a.

Ad 2. Note that E1 is conflict-free since E is conflict-free. Suppose b ∈ Arg⊢(S) attacks some a ∈ E1. Thus, there is a c ∈ E that attacks b. By Lemma 4 and Fact 4, E1 attacks b. Thus, E1 is admissible. Suppose E1 defends some d ∈ Arg⊢(S). Then E defends d and hence d ∈ E ∩ Arg⊢(S) = E1. Hence, E1 is complete.

Lemma 6. Where S | S ′ , E1 ∈ Cmp(AF⊢(S)), E2 ∈ Cmp(AF⊢(S ′ )), E = Defended(E1 ∪ E2, AF⊢(S ∪ S ′ )),

1. E ∩Arg⊢(S) = E1 and E ∩Arg⊢(S ′ ) = E2.
2. E ∈ Cmp(AF⊢(S ∪S ′ )).

Proof. Ad 1. Suppose a ∈ Arg⊢(S) ∩ E. Thus, a it is defended by E1 ∪ E2 in AF⊢(S ∪ S ′ ). Suppose some b ∈ Arg⊢(S) attacks a. Thus, there is a c = (Λ, σ) ∈ E1 ∪ E2 that attacks b. If c ∈ E2, by Lemma 2, there is a c′ ∈ Arg⊢(S ∩ Λ) = Arg⊢(∅) that attacks b. Since c′ has no attackers, by the completeness of E1, c′ ∈ E1. Altogether this shows that a ∈ Defended(E1,AF⊢(S ∪ S ′ )). Again, by the completeness of E1, a ∈ E1. Thus, E ∩ Arg⊢(S) = E1. Analogously, E ∩ Arg⊢(S ′ ) = E2. This is Item 1.

Ad 2. Suppose there are a, b ∈ E such that a attacks b. We know that there is a c ∈ E1 ∪E2 that attacks a. Wlog. suppose c ∈ E1. Thus, there is a d ∈ E1 ∪ E2 that attacks c. Since by Lemma 3, E1 ∪ E2 ∈ Adm(AF⊢(S ∪ S ′ )) we have reached a contradiction. Thus, E is conflict-free.

Suppose now some a ∈ Arg⊢(S ∪ S ′ ) attacks some b ∈ E. By the definition of E there is a c ∈ E1 ∪ E2 that attacks b. Thus, E is admissible.

For completeness assume that E defends some a ∈ Arg⊢(S ∪ S ′ ). Suppose b = (Λ, β) ∈ Arg⊢(S ∪ S ′ ) attacks a. Hence, there is a c ∈ E that attacks b. In view of Lemma 4 and Fact 3 there is a c′ ∈ (E ∩ Arg⊢(S)) ∪ (E ∩ Arg⊢(S ′ )) that attacks b. By Item 1, c′ ∈ E1 ∪ E2 and therefore a ∈ Defended(E1 ∪ E2, AF⊢(S ∪ S ′ )) = E.

Lemma 7. Where S | S ′ , E1 ∈ Sem(AF⊢(S)), Sem ∈ {Cmp, Prf, Grd}, there is a E ∈ Sem(AF⊢(S ∪ S ′ )) for which E1 = E ∩ Arg⊢(S).

Proof. (Sem = Cmp) Let E2 be arbitrary in Cmp(AF⊢(S ′ )). By Lemma 6, E = Defended(E1 ∪ E2,AF⊢(S ∪ S ′ )) ∈ Cmp(AF⊢(S ∪ S ′ )) and E1 = E ∩ Arg⊢(S).

(Sem = Grd) Let E1 = Grd(AF⊢(S)), E2 = Grd(AF⊢(S ′ )). Again, by Lemma 6, E = Defended(E1 ∪ E2,AF⊢(S ∪ S ′ )) ∈ Cmp(AF⊢(S ∪ S ′ )), E1 = E ∩ Arg⊢(S), and E2 = E ∩ Arg⊢(S ′ ). Suppose there is a E ⋆ ⊂ E such that E ⋆ ∈ Cmp(AF⊢(S ∪ S ′ )). By Lemma 5, E ⋆ ∩ Arg⊢(S) ∈ Cmp(AF⊢(S)) and E ⋆ ∩ Arg⊢(S ′ ) ∈ Cmp(AF⊢(S ′ )). Thus, E ⋆ ∩Arg⊢(S) = Grd(AF⊢(S)) and E ⋆ ∩ Arg⊢(S ′ ) = Grd(AF⊢(S ′ )). However, by Lemma 5, E ⋆ = Defended(E1 ∪ E2,AF⊢(S ∪ S ′ )) = E, a contradiction with the assumption that E ⋆ ⊂ E. The case for preferred extension is similar and left to the reader.

Lemma 8. Where S | S ′ , E ∈ Prf(AF⊢(S ∪ S ′ )) and E1 = E ∩ Arg⊢(S), also E1 ∈ Prf(AF⊢(S)).

Proof. Let S | S ′ , E ∈ Prf(AF⊢(S ∪ S ′ )), E1 = E ∩ Arg⊢(S), and E2 = E ∩ Arg⊢(S ′ ). By Lemma 5, E1 ∈ Cmp(AF⊢(S)) and E2 ∈ Cmp(AF⊢(S ′ )). Let E ′1 ∈ Cmp(AF⊢(S)) for which E1 ⊆ E ′1 . By Lemma 6, where E ′ = Defended(E ′1 ∪E2,AF⊢(S∪S ′ )), E ′ ∈ Cmp(AF⊢(S∪ S ′ )). By Lemma 5, E = Defended(E1 ∪ E2,AF⊢(S ∪ S ′ )) and thus E ⊆ E ′ . Since E is preferred, E = E ′ and hence E1 = E ′1 . Thus, E1 is ⊆-maximal and E1 ∈ Prf(AF⊢(S)).

Proof of Theorem 1. Suppose S ∪ {φ} | S ′ . We show that S |∼sem φ iff S ∪ S ′ |∼sem φ. (⇒) Suppose S ∪ S ′ ̸|∼sem φ. Thus, there is a E ∈ Sem(AF⊢(S ∪ S ′ )) for which there is no a ∈ E with conclusion φ. By Lemmas 5 and 8, E1 = E ∩ Arg⊢(S) ∈ Sem(AF⊢(S)). Since there is no a ∈ E1 with conclusion φ, S ̸|∼sem φ. (⇐) Suppose S ̸|∼sem φ. Thus, there is a E ∈ Sem(AF⊢(S)) for which there is no a ∈ E with conclusion φ. By Lemma 7, there is a E ′ ∈ Sem(AF⊢(S ∪ S ′ )) for which E ′ ∩ Arg⊢(S) = E. Assume for a contradiction that there is an argument a ∈ E ′ with Conc(a) = φ. By the Pre-Relevance of ⊢, there is an a′ = (Γ′ , φ) ∈ Arg⊢(S ∩ Supp(a)). By Fact 4, a′ ∈ E which contradicts our main supposition. Thus, S ∪ S ′ ̸|∼sem φ.

5.2 Semantic Relevance

Theorem 2 is a direct consequence of Theorem 4 below. Remark 9. The grounded extension can be characterized inductively: Grd(AF⊢(S)) = ⋃α≥0 Grdα(AF⊢(S)) where Grd0(AF⊢(S)) = Defended(∅,AF⊢(S)), Grdα+1(AF⊢(S)) = Defended(Grdα(AF⊢(S)),AF⊢(S)) for successor ordinals α + 1, and Grdβ(AF⊢(S)) = Defended(⋃α<β Grdα(AF⊢(S)), AF⊢(S)) for limit ordinals β.

Theorem 4. Where ⊢ satisfies Cut and ̂· is pointed, if AF⊢(S) |∼grd φ then

1. there is a (Φ, φ) ∈ Grd(AF⊢(S)),
2. Grd(AF⊢(S)) ⊆ Grd(AF⊢+φ (S)),
3. Grd(AF⊢+φ(S)) ∩Arg⊢(S) = Grd(AF⊢(S)),
4. for every a = (Γ, γ) ∈ Grd(AF⊢+φ(S)) \ Arg⊢(S), (Γ ∪ Φ, γ) ∈ Grd(AF⊢(S)) .

Proof. Ad 1. This is due to the fact that AF⊢(S) |∼grd φ.

Ad 2. We give an inductive proof and show the inductive step for a successor ordinal α+1. Let a ∈ Grdα+1(AF⊢(S)). Suppose b = (Γ, γ) ∈ Arg⊢+φ(S) attacks a. If b ∈ Arg⊢(S) there is a c ∈ Grdα(AF⊢(S)) that attacks b. By the inductive hypothesis (IH), c ∈ Grd(AF⊢+φ(S)). Otherwise, by Cut b′ = (Γ ∪ Φ, γ) ∈ Arg⊢(S) and b′ attacks a. Thus, there is a d ∈ Grdα(AF⊢(S)) that attacks b′ in some β ∈̂ Γ∪Φ. Since ̂· is pointed, β ∈ ̂Γ ∪ ̂Φ. Since (Φ, φ) ∈ Grd(AF⊢(S)), β ∈ ̂Γ and hence d attacks b in AF⊢+φ(S). By IH, d ∈

Grd(AF⊢+φ(S)). Altogether this shows that a is defended by Grd(AF⊢+φ(S)) and thus a ∈ Grd(AF⊢+φ(S)).

Ad 3 and 4. We show both simultaneously via induction. We show the inductive base. Let a = (Γ, γ) ∈ Grd0(AF⊢+φ(S)). Suppose first that a ∈ Arg⊢(S). Since Arg⊢(S) ⊆ Arg⊢+φ(S), there are no attackers of a in Arg⊢(S) and hence a ∈ Grd0(AF⊢(S)). Suppose now that a /∈ Arg⊢(S). By Cut, a′ = (Γ∪Φ, γ) ∈ Arg⊢(S). Suppose some b ∈ Arg⊢(S) attacks a′ in some β ∈̂ Γ∪Φ. By the pointedness of ̂·, β ∈ ̂Γ∪ ̂Φ. Note that β /∈ ̂Γ since otherwise b attacks a but a has no attackers. Thus, β ∈ ̂Φ. Hence, b attacks (Φ, φ) and is thus attacked by Grd(AF⊢(S)).

Our previous result does not generalize to preferred semantics or to ⊢ that do not satisfy Cut. We give two examples.

Example 13 ([Makinson, 2003]). Consider an ASPIC framework with defeasible rules D = {n0 : ⊤⇒ p; n1 : p ∨ q ⇒ ¬p}, facts P = ∅, the strict rules induced by classical logic (see Ex. 12), and φ = ψ if φ = ¬ψ and φ = ¬φ else. Consider the ASPIC-arguments a0 = ⊤ ⇒ p; a = a0 → (p ∨ q) and b = a ⇒ ¬p. With (‡aspic) we have the arguments a0 = ({n0, ⊤ ⇒ p, p}, p), a = ({n0, ⊤ ⇒ p, p}, p ∨ q) and b = ({n0, n1, ⊤ ⇒ p, p, p ∨ q ⇒ ¬p, ¬p}, ¬p) in AF⊢(S) where S = {n0, ⊤ ⇒ p, n1, p ∨ q ⇒ ¬p, p, ¬p}. Note that b attacks a0, a and b while a0 attacks b. Thus, the only preferred extension contains both a0 and a which means that S |∼Prf p and S |∼Prf p ∨ q. Once we move to ⊢+(p∨q) we also have the argument c = ({n1, p ∨ q ⇒ ¬p, ¬p}, ¬p) attacking a0. It is easy to see that now S ̸|∼+(p∨q) Prf p.

Example 14. We now consider the same example but with ⊢⋆ = {(Γ, φ) ∈ ⊢ | Γ is CL-consistent} and grounded extension. Unlike Ex. 13, b is not anymore in AF⊢⋆ (S). Thus, S |∼AF⊢⋆ Grd p and S |∼AF⊢⋆ Grd p ∨ q. Once we move to ⊢+(p∨q) ⋆ , c = ({n1, p ∨ q ⇒ ¬p, ¬p}, ¬p) again attacks a0 and a and thus, S ̸|∼AF +(p∨q) ⊢⋆ Grd p. Note that ⊢⋆ does not satisfy Cut.

6 Conclusion

In this paper we investigated the robustness of systems of structured argumentation under the addition of irrelevant information. To this end we introduced a simple and easily accessible account of structured argumentation in which meta-theoretic properties can be studied conveniently while systems from the literature can be represented. We studied the properties Non-Interference, Crash Resistance, and Cumulativity. In future work we plan to incorporate priorities (e.g., [Arieli et al., 2018; Cyras and Toni, 2016]) and to extend our study to other meta-theoretic properties, such as other properties of non-monotonic inference and rationality postulates.

Acknowledgments

The authors are supported by the Alexander von Humboldt Foundation and the German Ministry for Education and Research. The first author is also supported by the Israel Science Foundation (grant 817/15).