Inscription / Connexion Nouveau Sujet
cloture réflexive transitive d'une relation symétrique
Bonjour je sèche sur ce problème:
montrer que la clôture réflexive transitive (notée S) d'une relation symétrique R est une relation d'équivalence et donc que c'est la relation d'équivalence engendrée par R.
Pour montrer la symétrie, je prends xSy et je suppose non(ySx) et tente d'arriver à une absurdité. Mais après avoir écris non(ySx) => non(yRx) => non(xRy) je ne sais pas quoi faire.
Merci
Bonjour,
Est-ce n'est pas tout simplement un appel à la définition d'une relation d'équivalence :
Une relation d'équivalence sur un ensemble E est une relation binaire sur E qui est à la fois réflexive, symétrique et transitive.
Source Wikipédia, entre autres...
C'est la définition même de la clôture réflexive-transitive : 
C'est la plus petite relation réflexive et transitive sur X contenant R.
Toute clôture réflexive transitive n'est pas par définition symétrique...
Ici on a une clôture réflexive transitive (d'une relation symétrique) et on doit montrer qu'elle est symétrique.
Bonne remarque !
En reprenant les notations de l'article en lien :
Rtrans = 
nRn
Si R est symétrique, les Rn sont symétriques, et Rtrans est symétrique.
Sauf erreur de ma part, toujours possible 
Voici les définitions que j'ai à disposition (j'aurais du commencer par là désolé je pensais qu'elles étaient universelles) :
L'intersection de toutes les relations transitives (resp. réflexive transitive) qui contiennent une relation R donnée est appelée clôture transitive (resp. réflexive transitive). L'intersection de toutes les relations d'équivalences qui contiennent une relation R est appelée relation d'équivalence engendrée par la relation R.
Commence par montrer que l'intersection de 2 relations réflexives transitives est réflexive transitive, et passe à la clôture par récurrence.
J'ai montré que la clôture réflexive transitive (notée S) d'une relation R quelconque est réflexive et transitive (c'est une évidence). J'ai aussi montré qu'en supposant S symétrique, S est la relation d'équivalence engendrée par R.
Ce que je doit montrer c'est que si R est symétrique, alors S l'est aussi.
S est une réunion infinie de Rn, montre-le par récurrence, d'abord que c'est vrai pour tout Rn, ensuite que c'est vrai pour une réunion Rp Rq, et conclut par récurrence.
La définition avec les réunions ne me parle pas du tout.
En revanche celle avec les oui et j'ai réussi à montrer ce que je voulais, sans récurrence (sauf erreur et dis moi si ça te semble improbable).
Merci beaucoup !
Bonjour.
Je pense que vous confondez clôture transitive et fermeture transitive.
En parlant d'une relation binaire, le titre approprié au fil serait plutôt "fermeture réflexive et transitive d'une relation symétrique".
Tu pars donc de , ta relation symétrique sur un ensemble E.
Soit alors le graphe de S.
Soit le graphe de la fermeture réflexive et transitive
de
.
Comme tu veux une fermeture réflexive, tu ajoutes à la diagonale
de
.
On a donc .
Puis, si et
alors
puisque l'on veut une fermeture transitive.
Comme S est symétrique alors et
et par suite on a également que
.
Conclusion : vérifie :
1- et
(réflexivité de
)
2- (transitivité de
3- (symétrie de
)
Par suite est une relation d'équivalence sur
Annuler
connectez vous
algèbre en post-bac