Plus petite relation d'équivalence

(Cliquez-ici pour accéder à la version originale de cette discussion avec couleurs et images)





Posted by: zyb

Bonjour, je suis bloqué sur un problème de combinatoire, voici l'exposé :

On a une une relation R définie comme suit sur P(E) l'ensemble des parties de E :
pour tout A,B dans E, A R B <=> B = E \ A

On veut déterminer la plus petite relation d'équivalence S contenant R, càd
pour tout A,B dans E, A R B => A S B

Rq : une relation d'équivalence = reflexive (A S A) , transitive ( A S B et B S C =&gt; A S C ), et symetrique ( A S B <=> B S A )

J'ai pensé à plusieurs solutions :
* A S B &lt;=&gt; B contenu dans E \ A
-> pas reflexive

* A S B &lt;=&gt; B contenu dans P(A)
-> pas symetrique

* A S B &lt;=&gt; P(B) = P(E\A)
-> pas reflexive

En fait j'ai cherché un peu au pif sans succès, et j'aimerais bien une méthode pour trouver la plus petite relation d'équivalence d'une relation donnée, s'il y en a une. Et eventuellement une réponse à l'exo ou une indication serait bienvenu :p.

Merci d'avance


Posted by: yos

Telle qu'elle est là, la relation est symétrique.
Pour la rendre réflexive, il faut rajouter les couples (A,A) (c'est-à-dire ARA), pour tout A de P(E).
Après on regarde si cela suffit. La relation devient : ARB ssi (A=B ou B=E-A).

Elle est toujours symétrique. Reste la transitivité : spposons ARB et BRC , alors on a 4 cas :
1)A=B et B=C; alors A=C donc ARC.
2)A=B et C=E-B alors C=E-A donc ARC.
...et je t'en laisse un peu.


Posted by: zyb

Merci, la fin est pas difficile.
En fait j'y avais un peu pensé, mais j'étais parti sur
A S B <=> A c ( (E \ B) u A ) mais ça bloquait à la symétrie je crois, et ca avait pas trop de sens :s.

En fait pour trouver la plus petite relation d'équivalence, tu pars de celle que tu as déja et tu rajoute ce qu'il te manque en gros ?

En tout cas merci pour ta réponse ;)


Posted by: yos

Citation:
Posté par zyb
En fait pour trouver la plus petite relation d'équivalence, tu pars de celle que tu as déja et tu rajoute ce qu'il te manque en gros ?


C'est bien ce que je fais et c'est une chance que ça marche aussi vite ici. Car le fait de rajouter des éléments (relations) peut faire perdre des propriétés. Ici ce n'est pas le cas.

Il est évident que l'on peut compléter toute relation en une relation d'équivalence, de plusieurs façon en général. Si E est fini, on a bien sûr un procédé minimum (et il faut encore réfléchir un peu pour l'unicité de ce minimum).


Posted by: zyb

Ok, je vais m'entrainer sur d'autres cas.
A+, longue vie au forum ^^










-