The proofs

In this section, we give the proofs of all the properties presented in Sections 3 and 4.

Proof(of Property 1)By induction from and by applying function twice.

Proof(of Property 2)The valuation function associates each argument with a value belonging to a set which is a subset of a completely ordered set .

Proof(of Property 3)Let be a cycle:

- If is even: and
; so, is a
fixpoint of . It is the same for each ,
.
However, the may have different values: for example, for , with the valuation of [13], and with and . If all the have the same value, then this value will be a fixpoint of (because ).

- If is odd: and
; so, is a
fixpoint of
. It is the same for each ,
.
Since the function is non-increasing, the function is also non-increasing and we can apply the following result: ``if a non-increasing function has fixpoints, these fixpoints are identical''

^{30}. So, . But, , so is a fixpoint of .So, for all the , is a fixpoint of .

Proof(of Property 4)P1is satisfied because: , if has no direct attacker ( is empty), then and .

P2is satisfied because if , evaluates the ``direct attack'' of .

P3is satisfied because the function is supposed to be non-increasing.

P4is satisfied due to the properties of the function .

Proof(of Property 5)The valuation proposed by [13] is the following:

Let be an argumentation system. A complete labelling of is a function such that:

- If then such that
- If then or ,

Moreover, [13] also defines a complete rooted labelling with: , if then such that .

The translation of into a local gradual valuation is very easy:

is defined by , , and is the function .

Proof(of Property 6)[4] introduces the following function (in the context of ``deductive'' arguments and for an acyclic graph):

- if , then
- if with ,

The translation of into a gradual valuation is: , , and and is defined by and is defined by .

Proof(of Property 7)Let , , be tuples.

**Commutativity of :**- There are two cases:
- if or , the property is given by Definition 8.
- if and :

**Associativity of :**- There are two cases:
- if or or , we can simplify the
expression. For example, if
:

- if , and :

- if or or , we can simplify the
expression. For example, if
:
**Property of :**- We have:

**Distributivity:**- We have:

Proof(of Property 9)First, we show that the relation defined by Algorithm 1 is a partial ordering:

Let , , be three tupled values, the relation defined by Algorithm 1 is:

- reflexive: because , so AND (case 1 of Algorithm 1);
- transitive: suppose that and and
consider all the possible cases:
- if :
- if : then so ,
- if AND : then AND , so ,
- if AND : then AND , so ,
- if AND AND AND : then AND AND AND , so ;

- if
AND :
- if : then AND so ,
- if AND : then AND , so ,
- if AND : then AND , so ,
- if AND : then AND , so ;

- if AND
:
- if : then AND so ,
- if AND : then AND , so ,
- if AND : then AND , so ,
- if AND : then AND , so ;

- if AND AND
AND
:
- if : then AND AND AND so ,
- if AND : then AND , so ,
- if AND : then AND , so ,
- if AND AND AND : then AND AND AND , so .

- if :

Now, consider the maximal and minimal values:

- The tupled value
is the unique maximal element for the
preordering : let be a tupled value such that
, then
and . Compare
and with
Algorithm 1:
so the case number 1
is not used; then,
AND
so there are two cases:
- if and , the case 3 of Algorithm 1 is applied and ,
- else and , the case 5 of Algorithm 1 is applied and .

- The tupled value is the unique minimal element for the preordering : let be a tupled value such that , then and . Compare and with Algorithm 1: so the case number 1 is not used; then, AND so there are two cases:

Proof(of Property 10)The principleP1is satisfied by Definition 10 and by the fact that is the unique maximal element of (see Property 9).

The principleP2is satisfied because of Definition 10.

The principlesP3andP4are satisfied: all the possible cases of improvement/degradation of the defence/attack for a given argument (see Definition 16) are applied case by case^{31}. Each case leads to a new argument. Using Algorithm 1, the comparison between the argument before and after the application of the case shows that the principleP3(orP4, depending on the applied case) is satisfied.

Proof(of Property 11)From Definition 10.

Proof(of Property 12)First, we consider the case of the preferred extensions: Let be a preferred extension , we assume that does not contain all the unattacked arguments of . So, let be an unattacked argument such that .

Consider :

- If is conflict-free then, with an unattacked argument and a preferred extension, collectively defends itself, so is admissible and . This contradicts the fact that is a preferred extension.
- If contains at least one conflict, then:
- such that . This is impossible since is unattacked.
- or such that . But, since is unattacked, such that . So, does not collectively defend , which is in contradiction with the fact that is a preferred extension.

So, the assumption `` does not contain all the unattacked arguments of '' cannot hold.

Now, we consider stable extensions: Let be a stable extension , we assume that does not contain all the unattacked arguments of . So, let be an unattacked argument such that .

Since there exists in another argument which attacks ; This is impossible since is unattacked.

So, the assumption `` does not contain all the unattacked arguments of '' cannot hold.

Proof(of Property 13)An argument and one of its direct attackers cannot belong to the same extension in the sense of [9] because the extension must be conflict-free. So, since is uni-accepted, it means that belongs to all the extensions, and none of the direct attackers of belongs to these extensions.

For the converse, we use the following counterexample in the case of the preferred semantics:

There are two preferred extensions and . The argument is cleanly-accepted ( and do not belong to any preferred extension, and belongs to at least one of the two extensions). But, is not uni-accepted because it does not belong to all preferred extensions.

Proof(of Property 14)First, uni-accepted cleanly-accepted is the result of Property 13.

Conversely, let be a cleanly-accepted argument, there exists at least one stable extension such that and , , stable extension. Using areductio ad absurdum, we assume that there exists a stable extension such that ; but, if , it means that such that , so, the direct attacker of belongs to a stable extension; so, there is a contradiction with the assumption ( is cleanly-accepted); so, does not exist and is uni-accepted.

Proof(of Theorem 1)

- We consider the arguments
such that . Let
be a leaf, the path
is
with and denoting
the length of the path (if is even, this path is a defence
branch for , else it is an attack branch).
The constraints from to are the following:

or

So, for the path , the set of the well-defended arguments is if is odd, otherwise (this is the set of all the arguments having a value strictly better than those of their direct attackers). This set will denoted by ACCEP.

By definition, this set is conflict-free, it defends all its elements (because it contains only the leaf of the path and all the arguments which are defended by this leaf) and it attacks all the other arguments of the path. If we try to include another argument of the path ACCEP, we obtain a conflict (because

**all**the other arguments of the path are attacked by the elements of ACCEP). So, for , ACCEP is the only preferred and stable extension.Consider , with being the restriction of to

^{32}and UNIONACCEP ACCEP, then UNIONACCEP is the only preferred and stable extension of .So, , is accepted iff well-defended.

- Now, consider . If is accepted then UNIONACCEP is the only
preferred and stable extension of
. So, ,
does not belong to the extension. Then, ,
. Therefore, each branch leading to is a defence branch for
. So, ,
. So,
. Then, ,
. Therefore, is well-defended.
Using the following example, we show that the converse is false:

is well-defended (, and is incomparable with ) but not accepted.

- Now, if is well-defended and all the branches leading to are defence branches for , then UNIONACCEP is conflict-free and is defended against each of its direct attackers (because UNIONACCEP for each branch ). So, UNIONACCEP is the preferred and stable extension of and is accepted.

Proof(of Lemma 1)Let be an argumentation system with a finite relation without cycles (so, there is only one non empty preferred and stable extension denoted by ). We know that:

- if is exi-accepted and if has a direct attacker denoted by then is not-accepted,
- if is not-accepted then there exists at least one argument
such that
and is exi-accepted (because does not belong to
and is stable, so must ). So,
*a fortiori*, if is not-accepted and has only one direct attacker , then will be exi-accepted.

The proof is done by induction on the depth of a proof tree for or .

- Basic case for : is exi-accepted with only
one direct attacker (
) and
are the direct attackers of ; so, we have a proof tree whose
depth is 2 for
and one of the unattacked , for example ; so:

so:

But, Property 1 says that , so .

- Basic case for :
with
the only direct attacker of ; so, we have a proof tree whose
depth is 0 for ,
*i.e.*is unattacked; so, and (following Definition 6). - General case for : is exi-accepted with only
one direct attacker (
) and
are the direct attackers of , with one of the exi-accepted, for
example ; we consider the subgraph leading to to which we add
, and we assume:
(induction assumption issued from )
So:

and with the non-increasing of :

- General case for : is not-accepted, so
is exi-accepted; we assume that has several direct
attackers
which are all not-accepted
(because is exi-accepted); we consider each subgraph leading to
to which we add
and we assume:
, (induction assumption issued from )
so:

so:

Proof(of Theorem 2)Assume that is true and consider which is exi-accepted. Let , , be the direct attackers of . Then, for all , in the subgraph leading to and completed with , we apply the lemma and we obtain: , . Thus, we have:

So, is well-defended.

For the converse, let be well-defended. Let be the direct attackers of and assume that is not exi-accepted. Then, there exists at least one direct attacker of such that is exi-accepted (because there is only one preferred and stable extension). We can apply of the lemma on the subgraph leading to completed with and we obtain . So, there exists a direct attacker of such that:

This is in contradiction with well-defended. So, is exi-accepted.

Marie-Christine Lagasquie 2005-02-04