
## Proof (Sketch)

Case by case  the contradictions from a  to n   as in the table above  generate one of the two situations of the claim For example the contradiction a CG ⊕ CGPP generates
{CG, CGPP} ® {CG, CGPP} ~  ® {CG, CGPP} ® {CGPP, CGPP-1, CNO}
which is a < cycle in which two vertices are connected by an edge labelled by < as stated in the claim  All the other cases behave in the same way as can be easily checked by the reader Conversely if a contradiction derives from one of the possible implicit ways of repre senting relations in M99 the implementation also produces one of the cases of the claim In particular we have that  in  M 99   CG n    CG    CGPPn     CGPP     CGPP-1 n     CGPP-1
{CG, CGPP}"    {CG, CGPP} and {CG, CGPP-1}"    {CG, CGPP-1} are the only idem potent relations  The other cases of implicitness can be obtained by considering all the pairs of relations in M 99 composing and intersecting them  The implicit cases arising thus are listed in below

| CG                      | {CG, CGPP}" ⊕ {CG, CGPP-1}"   |                                 |    |
|-------------------------|-------------------------------|---------------------------------|----|
| CG                      | {CG, CGPP}" ⊕ {CG, CNO}       |                                 |    |
| i                       |                               |                                 |    |
| i                       | CGPP                          | {CG, CGPP}" ⊕ {CGPP, CNO}       |    |
| CNO                     | {CG, CNO} ⊕ {CGPP, CNO}       |                                 |    |
| i                       |                               |                                 |    |
| i                       | CNO                           | {CGPP, CNO} ⊕ {CGPP-1' CNO}     |    |
| i                       | CNO                           | {CGPP, CNO} ⊕ {CG, CGPP-1, CNO} |    |
| i                       | {CG, CNO}                     | {CG, CGPP, CNO}                 | e  |
| {CG, CGPP-1, CNO}       |                               |                                 |    |
| i                       | {CGPP, CNO}                   | C GPPr                          |    |
| i                       | {CGPP, CNO}                   | CPP" ® {CG, CNO}                |    |
| i                       | {CGPP, CNO}                   | CGPP" ® {CG, CGPP, CNO}         |    |
| i                       | {CGPP, CNO}                   | {CG, CGPP}" & CNO               |    |
| {CGPP, CNO}             | {CG, CGPP, CNO}               |                                 |    |
| i                       | e                             |                                 |    |
| {CGPP, CGPP-1, CNO}     |                               |                                 |    |
| {CG, CGPP}" & {CG, CNO} |                               |                                 |    |
| {CG, CGPP, CNO}         |                               |                                 |    |
