Bonjour,
une idée un peu folle m'est venue l'autre jour, celle de compter les ordres sur un ensemble E finis.
J'aimerai savoir si quelqu'un s'y est attelé avant moi, et si quelqu'un avait une idée du résultat...
Pour un ensemble de cardinal n, je pense sans trop me tromper pouvoir dire qu'il y en a moins que 2^n², et qu'il y en a toujours au moins 2 sur un ensemble non vide.
En fait je pense que cela revient a trouver le nombre de graphes a n éléments sans compter les isomoprhies....
Re : Relations-relations d'ordre
Comment on prend en compte la transitivité dans ce genre de recherche ?
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
Bonjour
J'ai peut être mal compris
Pour moi, dans un ensemble à 2 éléments, il y a deux ordres possibles.
Pour un ensemble à 1 élément, il n'y a qu'un ordre possible (ordre non strict).
Si, plus généralement, je veux ordonner (ranger) n éléments, il y a n! possibilités.
Ai-je compris de travers?
Amicalement
JM
Salut,Envoyé par doryphore
c'est justement le probleme, on va compter beaucoup de repetitions... si on ne prend pas en compte la transitivité...
Re : Relations-relations d'ordre
Plus ou moins, ta réponse doit être valable pour la recherche des relations d'ordre totales, c'est à dire quand on peut toujours comparer deux éléments.
Mais, il existe d'autres relations d'ordre qu'il faut inclure dans cette recherche.
Un exemple est la relation d'inclusion sur l'ensemble des idéaux.
"Plus les choses changent et plus elles restent les mêmes..." Snake Plisskein
Merci, j'ai compris ce que j'avais compris de travers et je suis d'accord. Je ne considérais effectivement que les ordres totaux.
Toutefois, si on ne compte que les ordres totaux, on est bien au delà de 2n2 (le fil initial ne le précise pas)
JM
Salut, je ne disais pas qu'il y en avait 2n² mais 2^(n²)
Oupss..Connaîtrais tu, pour moi, un bon oculiste?
On peut effectivement affirmer avec certitude qu'il y en a moins que 2^(n²), qui est le nombre de relations binaires sur un ensemble de cardinal n.
En effet, une relation binaire sur un ensemble E est un sous-ensemble de ExE, soit un élément de l'ensemble des parties de ExE, et on a évidemment:
Card(P(ExE)) = 2^(Card(ExE)) = 2^(n²).
Si on ne considère que les relations qui sont au moins réflexives (pour tout élément de E), on réduit à 2^(n²-n).
Je vais continuer à réfléchir sur la transitivité...
En espérant avoir fait avancer le schmilblick
Geoffrey
