Cette page est conforme aux normes du W3C - Auteur : Frédéric WANG - Dernière mise à jour : mardi 31 août 2004
Soit E un ensemble bien ordonné par la relation <E. Alors ℘(E) est bien ordonné par la relation <℘(E) définie ainsi :
∀(X,Y)∈℘(E)2, X<℘(E)Y ⇔ [ (X≠Y) ∧ (min((X∪Y)\(X∩Y))∈X) ]
∀(X,Y)∈℘(E)2, tel que X≤℘(E)Y et Y≤℘(E)X, supposons qu'il existe k tel que k=min((X ∪ Y)\(X ∩ Y)). Dans ce cas, k∈X et k∈Y donc k∈(X∩Y) et on aboutit à une contradiction. C'est donc que (X ∪ Y)\(X ∩ Y) n'a pas de plus petit élément. Comme c'est un sous-ensemble de l'ensemble bien ordonné E alors (X ∪ Y)\(X ∩ Y)=∅ et par conséquent X=Y.
Pour tout ensemble A, B, C, D, on démontre par double inclusion les deux égalités suivantes :
1: (A\B) = [(A ∪ C) \ (B ∪ C)] ∪ [(A ∩ C)\B]
o Si x∈ (A\B)
- Si x∈C, alors x∈(A ∩ C)\B
- Si x∉C, alors x∈(A ∪ C)\(B ∪ C)
donc (A\B) ⊂ [(A ∪ C) \ (B ∪ C)] ∪ [(A ∩ C)\B]
o Si x∈ [(A ∪ C) \ (B ∪ C)] ∪ [(A ∩ C)\B] alors x∈A et x∉B donc x∈(A\B).
donc [(A ∪ C) \ (B∪C)] ∪ [(A ∩ C)\B] ⊂ (A\B)
2: (A\B) ∪ (C\D) = (A ∪ C) \ [(A∩B)∪(C∩D)]
o Si x∈[(A\B) ∪ (C\D)]
- Si x∈(A\B) alors x∈(A ∪ C) et x∉B donc x∉(A∩B)
- Si x∈(C\D) alors x∈(A ∪ C) et x∉D donc x∉(C∩D)
Finalement si x∈A ou x∈C, x∈(A ∪ C) \ [(A∩B)∪(C∩D)]
donc [(A\B) ∪ (C\D)] ⊂ [(A ∪ C) \ [(A∩B)∪(C∩D)]]
o Si x∈(A ∪ C) \ [(A∩B)∪(C∩D)]
- Si x∈A, comme x∉(A∩B) x∉B et x∈(A\B)
- Si x∈C, comme x∉(C∩D) x∉D et x∈(C\D)
Finalement [(A ∪ C) \ [(A∩B)∪(C∩D)]] ⊂ [(A\B) ∪ (C\D)].
∀(X,Y)∈℘(E)2,
[X≤℘(E)Y] →
[∀y∈Y (y<Emin((X∪Y)\(X∩Y))) → (y∈X)]
On démontre ceci par l'absurde : y∉X → y ∈ (X∪Y)\(X∩Y) → min((X∪Y)\(X∩Y))≤Ey. Cette contradiction nous permet d'affirmer que y est élément de X.
Soient X, Y et Z des éléments de P(E) tel que X≤℘(E)Y et Y≤℘(E)Z.
Si Y=X ou Y=Z ou X=Y, la transitivité est démontrée, donc on va s'intéresser au cas où Y≠X, Y≠Z et X≠Z. On peut donc poser :
minX,Y=min((X∪Y)\(X∩Y)) avec minX,Y∈(X\Y) puisque X≤℘(E)Y
minY,Z=min((Y∪Z)\(Y∩Z)) avec minY,Z∈(Y\Z) puisque Y≤℘(E)Z
minX,Z=min((X∪Z)\(X∩Z))
Maintenant, intéressons nous à minX,Z :
(X∪Z)\(X∩Z) = [((X∪Z)∪Y) \ ((X∩Z)∪Y)] ∪ [((X∪Z)∩Y)\(X∩Z)] (d'après l'égalité 1)
= [((X∪Y)∪(Y∪Z)) \ ((X∩Y)∪(Y∩Z))] ∪ [((X∪Z)∩Y)\(X∩Z)]
= [((X∪Y)∪(Y∪Z)) \ ( [(X∪Y)∩(X∩Y)] ∪ [(Y∪Z)∩(Y∩Z)] ) ] ∪ [((X∪Z)∩Y)\(X∩Z)]
= [((X∪Y)\(X∩Y)) ∪ ((Y∪Z)\(Y∩Z))] ∪ [((X∪Z)∩Y)\(X∩Z)] (d'après l'égalité 2)
Donc finalement, minX,Z=min([((X∪Y)\(X∩Y)) ∪ ((Y∪Z)\(Y∩Z))]) ∪ [((X∪Z)∩Y)\(X∩Z)])
- Si minX,Z∈(X∪Y)\(X∩Y), alors minX,Z=min((X∪Y)\(X∩Y))=minX,Y et minX,Z∈X.
- Si minX,Z∈(Y∪Z)\(Y∩Z), alors minX,Z=min((Y∪Z)\(Y∩Z))=minY,Z et minX,Z∉Z donc minX,Z∈X.
- Enfin, supposons que minX,Z∈[((X∪Z)∩Y)\(X∩Z)], c'est à dire minX,Z∈Y. Si minX,Z∉(X∪Y)\(X∩Y) alors c'est que minX,Z<EminX,Y.
Mais alors comme X≤℘(E)Y, minX,Z∈X.
Dans tous les cas, on a minX,Z∈X et donc X≤℘(E)Z.
Remarquons pour le moment que nous venons de munir l'ensemble ℘(E) d'une relation d'ordre total. En effet, pour deux ensembles A et B distincts (si on a A = B la réflexivité permet que A et B soit comparables) de ℘(E), (A ∪ B) \ (A ∩ B) est non vide, donc on peut poser m = min((A ∪ B) \ (A ∩ B)). On a alors soit m∈A → A≤℘(E)B, soit m∈B → B≤℘(E)A.
Notons aussi que l'on a l'implication « A ⊂ B → B ≤℘(E) A », puisque si A est un sous-ensemble de B, alors (A ∪ B) \ (A ∩ B) = B \ A, et donc son plus petit élément est élément de B. En particulier, on voit que le plus petit élement et le plus grand élément de ℘(E) sont respectivement E et ∅.