# 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)
P1 is satisfied because: , if has no direct attacker ( is empty), then and .

P2 is satisfied because if , evaluates the direct attack'' of .

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

P4 is 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:
1. If then such that
2. 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 :

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 .
In all cases, .

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:
• if and , the case 2 of Algorithm 1 is applied and ,
• else and , the case 6 of Algorithm 1 is applied and .

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

The principle P2 is satisfied because of Definition 10.

The principles P3 and P4 are satisfied: all the possible cases of improvement/degradation of the defence/attack for a given argument (see Definition 16) are applied case by case31. 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 principle P3 (or P4, 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 a reductio 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)
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.

2. 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.

3. 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