Exercice 5, § 4

Soit E un ensemble ordonné pour lequel il existe un entier k tel que k soit le plus grand nombre d’éléments des parties libres X de E (III, p. 70, exerc. 5). Montrer qu’il existe une partition de E en k ensembles totalement ordonnés par l’ordre induit « théorème de Dilworth »). On procédera en deux étapes: a) Si E est fini et a n éléments, procéder par récurrence sur n: soit a un élément minimal de E et soit E′ = E − {a}. S’il existe une partition de E′ en k ensembles C_i (1 ≤ i ≤ k) totalement ordonnés par l’ordre induit, considérer pour chaque indice i l’ensemble U_i des x ∈ C_i qui majorent a; montrer qu’il y a au moins un indice i tel que dans E′ − U_i une partie libre ait au plus k − 1 éléments. Pour cela, on raisonnera par l’absurde, en considérant dans chaque E′ − U_i une partie libre S_i de k éléments, puis en prenant la réunion S des S_i et, pour chaque indice j ≤ k, le plus petit élément s_j de S ∩ C_j; on montrera que les k + 1 éléments a, s_1, . . . , s_k formeraient une partie libre de E. b) Si E est quelconque, procéder par récurrence sur k, de la façon suivante. On dit qu’une partie C de E est fortement liée dans E si, pour toute partie finie F de E, il existe une partition de F en au plus k ensembles totalement ordonnés telle que C ∩ F soit contenue dans l’un d’eux. Montrer qu’il existe une partie fortement liée maximale C_0, et que dans E − C_0 toute partie libre a au plus k − 1 éléments. (Raisonner par l’absurde en supposant qu’il y ait dans E − C_0 une partie libre {a_1, . . . , a_k} de k éléments; considérer chacun des ensembles C_0 ∪ {a_i} (1 ≤ i ≤ k), et exprimer qu’il n’est pas fortement lié, ce qui introduit pour chaque indice i une partie finie F_i de E. Considérer enfin la réunion F des F_i et utiliser le fait que C_0 est fortement liée pour obtenir une contradiction.)