Relations et relations d'équivalence

[Guitou80]

Bonjour,

Savez vous svp pourquoi il y a 2^(n^2) relations binaires sur un ensemble à n éléments ?
Je pensais qu'il y en avait n^2

A moins qu'on considère le nombre de matrices associées possibles a cette relation, il y a 2^n cases dans la matrices et chaqu'une peut avoir la valeur zero ou un, dans ce cas il ya en effet 2^(n^2) matrices possibles associées à une relation binaire sur un ensemble à n éléments. J'ai bon ?

Et pourquoi y a-t'il 2^(n^2-n) relations réflexives ? N'y en a t'il pas 2^n ?

Je rappelle ce qu'est une relation reflexive :
(merci de mindiquer comment écrire en language mathématique sur ce forum)
pour tout a appartenant a lensemble E, aRa donc la matrice associée à cette relation a sa grande diagonale (matrice identité) qui vaut un et le reste zero.

Merci

[fatal_error]

salut,

oui tu peux représenter ta relation par une matrice booléenne, et donc t'as n^2 cases.
Du coup le nombre de matrices que tu peux faire représente le nombre de relation, et tu peux faire 2^(le nombre de case de la matrice) donc 2^(n^2)

pour le deuxieme cas, l'idée est identique.
Tu fixes la diagonale à 1 (pour dire que x est en relation avec lui même), et donc il te reste n^2-n cases que tu peux faire varier.

Pour le langage mathématique, tu peux regarder les commandes latex de bases!genre \forall, \exists, \in, etc....

[Guitou80]

salut,

oui tu peux représenter ta relation par une matrice booléenne, et donc t'as n^2 cases.
Du coup le nombre de matrices que tu peux faire représente le nombre de relation, et tu peux faire 2^(le nombre de case de la matrice) donc 2^(n^2)

pour le deuxieme cas, l'idée est identique.
Tu fixes la diagonale à 1 (pour dire que x est en relation avec lui même), et donc il te reste n^2-n cases que tu peux faire varier.

Pour le langage mathématique, tu peux regarder les commandes latex de bases!genre \forall, \exists, \in, etc....

Merci à toi

l'explication est très claire.
Merci de ne pas vérrouiller ce topic il se peut que je repose des questions dans ce domaine

Bonne soirée

[Nightmare]

Salut,

pour une preuve plus visuelle :

Une relation binaire R sur A, c'est la donnée d'un sous-ensemble de A² (le sous-ensemble {(x,y) dans A² tel que xRy}.

Il y a donc autant de relation binaire entre A et B que de sous-ensembles de A²

Or A² a n² éléments et il est bien connu que le nombre de sous ensemble d'un ensemble à k élément est .

:happy3:

[Guitou80]

Salut,

pour une preuve plus visuelle :

Une relation binaire R sur A, c'est la donnée d'un sous-ensemble de A² (le sous-ensemble {(x,y) dans A² tel que xRy}.

Il y a donc autant de relation binaire entre A et B que de sous-ensembles de A²

Or A² a n² éléments et il est bien connu que le nombre de sous ensemble d'un ensemble à k élément est .

:happy3:

Bien vu, oui ca aide de se le repésenter comme le nombre de sous-ensembles possibles d'un ensemble de couples