Relations symétriques et antisymétriques.

[invitea5ab8741]

Bonjour,

Je veux dénombrer le nombre de relations symétriques et antisymétriques dans un ensemble E à n éléments.

Je fais un diagramme cartésien ( tableau à n lignes et n colonnes )

Je pose : 0 = éléments non reliés par la relation.
1 = éléments reliés par la relation.

Dans une case (x;y) tels que : x différent de y, si je mets 1; alors dans la case (y;x) je mets 1 car la relation est symétrique.
Mais la relation est aussi antisymétrique donc je dois mettre 0.
Par l'absurde, je ne peux donc pas mettre de 1 dans une case (x;y) n'étant pas dans la diagonale.

Si je mets 0 dans une case (x;y) étant en dehors de la diagonale, alors je mets 0 ou1 dans la case (y;x) car la relation est antisymétrique.
Or la relation est aussi symétrique, donc je dois mettre 0 dans la case (y;x).

En résumé, toutes les cases n'étant pas dans la diagonale du tableau sont remplies par des 0.

Mais comment remplir les cases de la diagonale ?
-----

[Médiat]

Vous auriez pu faire une démonstration plus formelle, mais effectivement une relation à la fois symétrique et antisymétrique vérifie que xRy => x = y.

Mais comment remplir les cases de la diagonale ?

Comme vous l'avez remarqué, dans la formule précédente, il s'agit d'une implication et non d'une equivalence, ce qui veut dire que vous pouvez "remplir" la diagonale comme vous voulez.