Plus petite relation d'équivalence
Réponses à toutes vos questions après le Bac (Fac, Prépa, etc.)
-
Anonyme
par Anonyme » 29 Déc 2005, 18:12
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,
\
On veut déterminer la plus petite relation d'équivalence S contenant R, càd
pour tout A,B dans E,
Rq : une relation d'équivalence = reflexive (
) , transitive (
et
), et symetrique (
)
J'ai pensé à plusieurs solutions :
*
B contenu dans E \ A
-> pas reflexive
*
B contenu dans P(A)
-> pas symetrique
*
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
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 21:20
-
par yos » 29 Déc 2005, 19:17
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.
-
Anonyme
par Anonyme » 29 Déc 2005, 19:44
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 ;)
-
yos
- Membre Transcendant
- Messages: 4858
- Enregistré le: 10 Nov 2005, 21:20
-
par yos » 29 Déc 2005, 20:06
zyb a écrit: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).
-
Anonyme
par Anonyme » 29 Déc 2005, 20:12
Ok, je vais m'entrainer sur d'autres cas.
A+, longue vie au forum ^^
Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 60 invités