Antichaîne

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, plus précisément en théorie des ordres, une antichaîne d'un ensemble E muni d'une relation d'ordre (notée ici ≤ ) est une partie A de E telle que, pour tout x, y de A,

x \le y \Rightarrow x=y.

Autrement dit, dans un ensemble ordonné, une antichaîne est une partie dont les éléments sont deux à deux incomparables.

La largeur d'un ordre est le maximum des cardinaux de ses antichaînes (par exemple : un ordre total est un ordre de largeur 1).

Antichaînes de N[modifier | modifier le code]

Considérons l'ensemble N des entiers naturels, ordonné par la divisibilité.

Pour tout entier naturel n, la largeur de {1, 2, … , 2n} (muni de l'ordre induit) est n. De plus, dans cet ensemble ordonné, un élément de la forme 2kc avec c impair appartient à une antichaîne maximale (i.e. de cardinal n) si et seulement si 2n  < 3k + 1 c.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Lien externe[modifier | modifier le code]

(en) Eric W. Weisstein, « Antichain », MathWorld