Fermeture transitive B+ d'une relation B — Les-mathematiques.net The most powerful custom community solution in the world

Fermeture transitive B+ d'une relation B

Bonjour
[je ne poste peut-être pas au bon endroit, je n'ai rien trouvé sur le forum concernant ce sujet]
On m'explique que la fermeture transitive $B^+$ définie comme l'union des $B{_i}$, d'une relation $B$, c'est ajouter des éléments dans $B$ pour que $B$ devienne une relation transitive.
Si je prends $B$ incluse dans $\N\times \N$ (produit cartésien des entiers naturels) définie par $ (x,y)\in B$ ssi $y = 2x$ que contient $B^+$ ?

Je vois bien que si je prends $x, y, z$ dans $B$ et que si $(x,y)\in B$ et $(y,z)\in B$, je n'ai pas la transitivité parce que $z = 4x$. Comment je dois me débrouiller pour que ça le devienne ?
Au delà de l'explication du concept, je manque de méthode.
Merci.

Réponses

  • Il faut mettre $(x,z)$ dans $B^+$.
  • Math Coss
    Merci mais je ne comprends pas comment on y parvient.

    [Inutile de reproduire le message précédent. AD]
  • $B$ est un sous-ensemble de $\mathbb{N}\times\mathbb{N}$. Il s'écrit
    $$B=\{(x,2x)\mid x\in\mathbb{N}\}.
    $$ Cette relation n'est effectivement pas transitive, on rajoute donc tous les couples $(x,y)$ dont on a besoin pour que la relation devienne transitive. Par exemple, $B$ contient tous les éléments de la formes $(2x,4x)$, dans $B^+$, on trouvera donc $(x,4x)$. De la même manière, dans $B^+$ il y a les éléments de la forme $(x,4x)$ et $(4x,8x)$, on trouvera donc aussi $(x,8x)$...
    Il semblerait que $B^+$ doive contenir tous les $(x,2^n x)$ pour $x,\ n\in\mathbb{N}$.
    Maintenant concernant la méthode, est-ce que la nouvelle relation est transitive ? Par construction, ce serait la plus petite contenant $B$, et ce serait donc bien la "fermeture transitive"...

    Bon courage !
  • Merci beaucoup,

    Je comprends mieux, c'est très clair.
    Bonne soirée.
  • On a dans $B$ les couples suivants (je représente le couple $(u,v)$ par une flèche de $u$ vers $v$) : \[\xymatrix{x\ar[r]&2x\ar[r]&4x\ar[r]&8x\ar[r]&16x\ar[r]&\cdots}\]Il faut donc mettre dans $B^+$ les flèches suivantes : \[\xymatrix{x\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@/^3pc/[rrrr]\ar@/^4pc/[rrrrr]&2x\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]\ar@/^3pc/[rrrr]&4x\ar[r]\ar@/^1pc/[rr]\ar@/^2pc/[rrr]&8x\ar[r]&16x\ar[r]&\cdots}\]
Connectez-vous ou Inscrivez-vous pour répondre.
Success message!