Relations-relations d'ordre

[Quinto]

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....

[doryphore]

Comment on prend en compte la transitivité dans ce genre de recherche ?

[invite76]

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

[Quinto]

Comment on prend en compte la transitivité dans ce genre de recherche ?

Salut,
c'est justement le probleme, on va compter beaucoup de repetitions... si on ne prend pas en compte la transitivité...

[doryphore]

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

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.

[invite76]

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 2n² (le fil initial ne le précise pas)

JM

[Quinto]

Salut, je ne disais pas qu'il y en avait 2n² mais 2^(n²)

[invite76]

Oupss..Connaîtrais tu, pour moi, un bon oculiste?

[Geof]

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