Antichaîne

Les antichaînes d'un ensemble totalement ordonné sont les singletons et l'ensemble vide. Par conséquent, la largeur d'un ordre total est 1.

Soit ${\displaystyle {\mathcal {P}}(E)}$ l'ensemble des parties d'un ensemble donné ${\displaystyle E}$, muni de la relation d'inclusion, on appelle famille de Sperner une antichaîne de ${\displaystyle {\mathcal {P}}(E)}$.

Si ${\displaystyle E}$ est fini de cardinal n, le nombre d'antichaînes est un nombre de Dedekind M(n), et La largeur de l'inclusion est d'après le théorème de Sperner : ${\displaystyle {n \choose \lfloor {n/2}\rfloor }}$.

Prenons le cas particulier des parties d'un ensemble à 3 éléments ${\displaystyle \{x,y,z\}}$, dont la figure ci-dessous représente le diagramme de Hasse.

Diagramme de Hasse d'un ensemble à 3 éléments.

On compte en tout M(3) = 20 antichaines possibles. Ses antichaînes maximales sont :

• ${\displaystyle {\big \{}\varnothing {\big \}}}$, ${\displaystyle {\big \{}\{x,y,z\}{\big \}}}$
• ${\displaystyle {\big \{}\{x\},\{y,z\}{\big \}}}$, ${\displaystyle {\big \{}\{y\},\{x,z\}{\big \}}}$, ${\displaystyle {\big \{}\{z\},\{x,y\}{\big \}}}$
• ${\displaystyle {\big \{}\{x\},\{y\},\{z\}{\big \}}}$, ${\displaystyle {\big \{}\{x,y\},\{x,z\},\{y,z\}{\big \}}}$.

Sa largeur est égale à 3, le cardinal des deux plus grandes antichaînes.

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 2^kc avec c impair appartient à une antichaîne maximale (i.e. de cardinal n) si et seulement si 2n < 3^{k + 1} c.

Un bel ordre est un ordre partiel bien fondé sans antichaîne infinie.

• Antichaîne forte (en)
• Chaîne
• Théorème de Dilworth
• Famille de Sperner

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