Bourbaki, vraiment pour comprendre (8)

PREAMBULE :

J'aurai pu laisser ce post tel quel, se perdre au fil des pages. Mais dans la mesure du possible, il est logique de terminer ce que l'on a commencé ... en outre, et sans prétention aucune, cela pourra peut-être servir à d'autres qui voudraient s'essayer à l'exercice. L'honnêteté m'oblige néanmoins à dire que je ne l'ai pas trouvé tout seul (en particulier a) : 0) et 1-1) et b) : 1-2) ) j'ai donc (malheureusement) dû m'inspirer de la démonstration publiée dans "Annals of Mathematics" qu'un de mes (très) anciens professeurs m'a gentiment envoyée. Ci-dessous donc, à priori8-), la correction de l'exercice :

$\bullet$ Définitions, notations et abréviations :
. $\underset{[1,k]}{\exists}j$ : il existe $j$ dans l'intervalle $[1,k]\hspace{1 cm}$ t.o. : totalement ordonné $\hspace{1 cm} PL(A)$ : partie libre d'un ensemble $A$
$ppe (A)$ : plus petit élément d'un ensemble $A$
. Soit $R$ une relation, on notera $R$ (V) pour "$R$ est vraie" (ou "$R$ est un théorème") et $R$ (F) pour "$R$ est fausse" (ou "$\lnot(R)$ est un théorème"...)
. Ensuite, pour éviter de surcharger les démonstrations en "donc", "si ... alors", etc... , il m'arrivera d'utiliser la notation très personnelle suivante (qui en a déjà déconcerté plus d'un sur ce forum (:D) : $A \underset {P}{\Longrightarrow} B$ qui signifie :" de $A$ je déduis $B$ en utilisant le fait que $P$ est vrai". En particulier, il m'arrivera de symboliser " de $A$ je déduis $B$" par $A\Rightarrow B$
. De même $\Leftrightarrow$ sera employé pour "est équivalent à".
. Enfin : $F=P_1+P_2+...+ P_k$ ou $F=\sum_{i=1}^k P_i$ exprimera que $(P_i)_{i\in[1,k]}$ est une partition de $ F$ et donc "$+$" représente une réunion disjointe...

$\bullet$ Une remarque annexe pour les bourbachistes purs : "le plus grand nombre d'éléments des parties libres $X$" signifie chez Bourbaki :" le plus grand cardinal des parties libres $X$" ... sous entendu : $X$ partie libre de $E$, est un ensemble ! ... et bien juste pour le fun, j'ai voulu le démontrer en utilisant la notion de relation collectivisante et les critères $C 51$, $C52$ ou $C53$ ... mais n'y suis pas arrivé.
Si quelqu'un peut me donner une indication, je lui en saurai gré.
a)
$\bullet$ Il s'agit d'appliquer le raisonnement par récurrence sur $Card(E)=n$, ($n$ entier) tel que Bourbaki le fait dans son cours, c'est le critère $C 61$ (p.III-32 ) :

je définis l'hypothèse de récurrence R(n) : $" \Bigl(Card(E)=n \land max(Card[PL(E)])=k \Bigr) \Longrightarrow$ il existe une partition de $E$ en $k$ ensembles t.o."

1) J'initialise la récurrence en montrant que R(0) est vrai, avec R(0) : $" \Bigl( Card(E)=0 \land max(Card[PL(E)])=k \Bigr) \Longrightarrow$ il existe une partition de $E$ en $k$ ensembles t.o." :

. $k$ sera supposé $\neq 0$... par conséquent, si $\Bigl(Card(E)=0\Bigr)$ (V) alors $\Bigl(max(Card[PL(E)])=k\Bigr)$ (F)

. et donc : $\Bigl( Card(E)=0 \land max(Card[PL(E)])=k \Bigr)$ (F)

. enfin comme $A$ (F) entraine $(A \Rightarrow $ (V) pour tout $B$, on en tire $R(0)$ (V) $\hspace{1 cm} $ CQFD

Remarque : A ce stade, et pour une approche moins logique et plus intuitive, on aurait pu "démarrer" la récurrence non pas à $0$ mais à $k$ pour ensuite appliquer le critère $C 61 - 2)$ du cours. En effet, d'après l'énoncé on doit avoir nécessairement $n\geqslant k$. On initialise alors la récurrence en démontrant que $R(k)$ est vrai, c'est à dire que : "$Card(E)=k \land max(Card[PL(E)])=k \Longrightarrow$ il existe une partition de $E$ en $k$ ensembles t.o." (V)
.Or le membre à gauche de l'implication signifie : $E$ est un ensemble de $k$ éléments dont la plus grande partie libre a $k$ éléments
.donc tous les éléments de $E$ sont non comparables
.donc les sous-ensembles t.o. de $E$ sont réduits à 1 seul éléments, et il y en a $k \,\, !! \hspace{1 cm} CQFD$


2) Montrons : $\Bigl(n \,\, entier \land R(n)\Bigr) \Rightarrow R(n+1)$ avec

R(n+1) : "$ \Bigl(Card(E)=n+1 \land max(Card[PL(E)])=k \Bigr) \Rightarrow$ il existe une partition de $E$ en $k$ ensembles t.o."

$\bullet \, n \text{ entier } \underset {prop.1, p.III-31} {\Longrightarrow} n+1 \text{ entier } \underset {Card(E)=n+1} {\Longrightarrow} E$ fini $\underset{\text{ E est ordonné}}{\Longrightarrow} E$ admet un élément minimal...

Bien que ce soit affirmé d'emblée dans l'énoncé, la dernière implication mérite une démonstration, et cela se fait par récurrence sur $Card(E)$ en prenant pour hypothèse de récurrence H(n): "Card(E)=n $\Rightarrow E$ admet un élément minimal" :

* c'est trivial si $Card(E)=0$.
En effet : Card(E) = 0 $\Rightarrow E=\emptyset$ et comme "$a\in \emptyset$" (F) on a toujours : "$(a\in \emptyset \land x \leqslant a) \Rightarrow x=a$" (V)

** montrons $\Bigl( n \text{ entier } \land H(n)\Bigr) \Rightarrow H(n+1)$ :

Soit $F$ tel que Card (F) = n+1, cela entraîne $F=F'\cup \{x\}$ avec $x\notin F' \land Card(F')=n$, par conséquent (par H(n)) $F'$ admet un élément minimal "$m$" $\rightarrow$ plusieurs cas:

a) $m$ et $x$ non comparables : alors $m$ minimal dans $F$

b) $m$ et $x$ comparables $\rightarrow$ 2 sous cas :

b1) $\, m\leqslant x$ : alors $m$ minimal dans $F$

b2)$ \, m\geqslant x$ : soit alors $z\in F$,

on a : $z\leqslant x \Rightarrow \begin{cases} z=x \\ \text{ou}\\ z \neq x \Rightarrow z \in F' \Rightarrow (z<x\leqslant m \land z \in F') \Rightarrow (z< m \land z \in F') \rightarrow \text{ : impossible par définition de m !} \end{cases}$

Il s'ensuit $x$ est minimal dans $F \hspace{1 cm}$ CQFD

*** On applique alors $C61$ pour conclure la démonstration...


$\bullet$ Il vient donc $E= E'\cup \{a\}$ avec $a \notin E'$, ou de manière équivalente: $E'=E-\{a\}$ et $Card(E')=n$

Par hypothèse, il existe une partition de $E'$ en $k$ ensembles $C_i$ totalement ordonnés, c'est à dire : $E'=\underset{1\leqslant i \leqslant k}{\cup} C_i $ et $ C_i \cap C_j=\emptyset, \underset {i \neq j}{\forall (i,j)} \in [1,k]^2$

. On considère alors $U_i =\{x\in C_i \,|\, x>a \} \subseteq C_i$, et en posant $S_i= PL(E'-U_i)$ on montre: $\underset{[1,k]}{\exists}j \,,\, \underset{E'-U_j}{\forall S_j} \,,\, \Bigl(Card[S_j]\leqslant k-1 \Bigr)\hspace{1 cm} (\alpha)$

La démonstration de ($\alpha$) se fait par l'absurde, suivant les indications données par l'énoncé :

. supposons : $\underset{[1,k]}{\forall}j \,,\, \underset{E'-U_j}{\exists S_j} \,,\, \Bigl(Card[S_j]> k-1 \Bigr)$ c'est-à-dire : $\underset{[1,k]}{\forall}j \,,\, \underset{E'-U_j}{\exists S_j} \,,\, \Bigl(Card[S_j]\geqslant k \Bigr)$ c'est-à-dire : $ \underset{[1,k]}{\forall}j \,,\, \underset{E'-U_j}{\exists S_j} \,,\, \Bigl(Card[S_j] = k \Bigr)$ (car par hypothèse : $k$ est le plus grand nombre d'éléments dans une partie libre de $E'$, donc : $Card(S_i)\geqslant k \Leftrightarrow Card(S_i)= k$)


On considère $S=\underset {1\leqslant i\leqslant k}{\cup} S_i$ et $s_i = ppe(S\cap C_i)$ pour $1\leqslant i\leqslant k$

. Supposons prouvées : l'existence des $s_i$ et l'assertion " $F = \{ a,s_1,...,s_k\}$ est une partie libre de $E$ "

Alors comme $Card(F)=k+1$ et $k+1\neq k$ (puisque $k$ entier), il y a contradiction avec le fait que $k$ est le plus grand nombre d'éléments d'une partie libre de $E$ !

CQFD


$\bullet$ On a donc la partition suivante : $E=E'\cup\{a\}=U_j\cup[E'-U_j]\cup\{a\}=[U_j\cup\{a\}]\cup[E'-U_j]$

- $U_j\cup\{a\}$ est t.o. (puisque $U_j \subseteq C_j$ qui est t.o. et de plus $x>a$ pour tout $x$ dans $U_j$)

- Par hypothèse de récurrence et d'après $(\alpha) : E'-U_j$ est partitionné en $k-1$ ensembles totalement ordonnés $P_i \,,\,1\leqslant i \leqslant k-1$

Par conséquent $E$ est partitionné en $k$ ensembles totalement ordonnés

CQFD .....


Il reste maintenant à démontrer :

0) Existence des $s_i$ :

. ($R_1$): Si $\alpha,\beta$ sont des éléments distincts de $S_i$ alors il existe $t,u (t\neq u)$ dans $[1,k]$ tels que $\alpha \in C_t$ et $\beta \in C_u$.
En effet : $\alpha,\beta \in E'$ et comme les $(C_i)_{1\leqslant i \leqslant k}$ forment une partition de $E', \alpha,\beta$ sont nécessairement éléments des $C_i$. De plus si $ \alpha,\beta \in C_i$ alors, $C_i$ étant t.o. , $\alpha$ et $\beta$ seraient comparables $\rightarrow$ contradiction car $\alpha,\beta \in S_i$ !

. ($R_2$): Du fait que $S_i$ possède $k$ éléments, il découle aussi que $S_i$ a exactement un élément dans chacun des $C_j, (1\leqslant j\leqslant k)$ et donc en particulier $ S_i \cap C_i \neq \emptyset$

. Il s'ensuit que pour chaque $C_i \,,\, S\cap C_i \neq \emptyset \, \, \Bigl($en effet : $S\cap C_i = (\underset {1 \leqslant i \leqslant k} {\cup} S_i) \cap C_i = \underset {1 \leqslant i \leqslant k}{\cup} (S_i\cap C_i) \neq\emptyset \Bigr)$, de plus $C_i$ étant fini, $S \cap C_i$ est fini et admet donc un ppe : $s_i \,! $

CQFD


1) $F = \{ a,s_1,...,s_k\}$ est une partie libre de $E$.

1-1) $a \nsim s_i$

$\bullet$ Bien entendu on a : $\lnot (s_i \leqslant a)$ (V)
En effet, par l'absurde supposons $s_i \leqslant a$ alors $a$ minimal entraîne $s_i = a$ ce qui est impossible car $a\notin E'$ contrairement à $s_i$ !

$\bullet \bullet$ montrons : $\lnot (a \leqslant s_i)$ (V)

. D'après ($R_2$), il découle que $s_i$ minore chacun des éléments $t_v$ de $S_v \cap C_i , (1 \leqslant v \leqslant k)$, et en particulier $s_i\leqslant t_i \longrightarrow$ on aurait donc : $a\leqslant s_i\leqslant t_i $ c'est-à-dire $a\leqslant t_i \hspace{0.5 cm} (*)$

. Or $t_i \in S_i \cap C_i \Longrightarrow t_i \in S_i \Longrightarrow t_i \in E'-U_i \Longrightarrow t_i \notin U_i \underset {t_i \in C_i}{\Longrightarrow} \lnot (t_i \geqslant a)$ ce qui contredit $(*)\,\, ! \hspace{0.5 cm}$ CQFD

De $\bullet$ et $\bullet\bullet$, on déduit le résultat $\hspace{4 cm}$ CQFD


1-2) $s_i \nsim s_j$ si $i \neq j$ (on démontrera par exemple $\lnot(s_i \leqslant s_j)$ , le cas $\lnot (s_j \leqslant s_i)$ étant symétrique...).

. Par l'absurde, supposons donc $s_i \leqslant s_j$. Comme $s_j$ minore exactement un élément de chaque $S_r$ ($1\leqslant r \leqslant k$), $s_j$ minore en particulier un élément "$\alpha$" d'un sous-ensemble $S_t$ dans lequel $s_i$ est aussi un élément, et on a alors $s_i\leqslant s_j \leqslant \alpha$.

. Mais on ne peut avoir $s_i \leqslant \alpha$ car $s_i$ et $\alpha$ sont $2$ éléments de $S_t$ qui est une partie libre $\longrightarrow$ contradiction !

CQFD


b) On suppose $E$ quelconque, il s'agit de démontrer :

$\exists k\,,\, \Bigl(k \text{ entier } \land k=max [PL(E)] \Bigr) \Longrightarrow \exists (P_i)_{i\in [1,k]} \, ,\, \Bigl( E=\displaystyle\bigcup_{i=1}^k P \,\land P_i \text{: t.o. } \,\land \, (i \neq j \Rightarrow P_i \cap P_j =\emptyset) \Bigr)$.

Cela se fera par récurrence sur $k$ ... On prendra comme hypothèse de récurrence , $F$ étant un ensemble quelconque,

$(H_{k-1}) : \Bigl(k-1=max [PL(F)] \Bigr) \Longrightarrow \exists (M_i)_{i\in [1,k]} \, ,\, \Bigl( E=\displaystyle\bigcup_{i=1}^k M_i\,\land M_i \text{: t.o. } \,\land \, (i \neq j \Rightarrow M_i \cap M_j =\emptyset) \Bigr) \hspace{1cm}(V)$.

$\bullet \,$ Démontrons $H_1$:
L'hypothèse traduit que les parties libres ont un seul élément, autrement dit : tous les élément de $F$ sont comparable entre eux et donc $F$ : t.o. $\longrightarrow$ il s'ensuit que la famille $(M_i)_{i\in [1,k]}$ est bien réduite à un seul élément $\hspace{1cm}CQFD$

$\bullet \,$ Considérons $(H_{k-1})\,\,$ (V) , et supposons démontrées les 2 assertions:
1) Il existe $C_0$ maximal fortement liée
2) toute partie libre de $E-C_0$ a, au plus, $k-1$ éléments

. Alors, par $(H_{k-1})$, on déduit que $E-C_0$ admet une partition en $k-1$ ensembles t.o. $L_i$, et donc: $E=C_0 + \displaystyle\sum_{i=1}^{k-1} L_i \,\,$ (on notera $+,\displaystyle\sum$ : des réunions disjointes)

. De plus, $C_0$ est t.o.
En effet : Soient $x,y \in C_0$. Considérons une partie finie $V$ de $E$ contenant $x$ et $y$.
$C_0$ fortement liée $\Rightarrow \{x,y\} \in C_0\cap V \subseteq W_j,\,\, W_j$ étant un ensemble t.o., élément d'une partition $(W_i)_{i\in[1,r], r\leqslant k}$ de $V \Longrightarrow x$ et $y$ : comparables
CQFD

. On a donc bien une partition de $E$ en $k$ ensembles t.o. $\{C_0,L_1,L_2,...L_{k-1} \}$, ce qui revient à dire que l'on a démontré $(H_{k})$ !

. On applique alors $C61$ pour conclure $\hspace{3 cm} CQFD$


Il reste donc à montrer:

1) Il existe une partie $C_0$ fortement liée maximale

. L'ensemble $\Lambda$ des parties fortement liées est non vide puisque tout singleton $\{a\}$ est fortement lié.

Démonstration : Par hypothèse, les parties libres de $E$ ont au maximum $k$ éléments, par conséquent toute partie finie $T$ de $E$ possède à fortiori des parties libres comprenant, au plus, $k$ éléments. Par a), il s'ensuit que $T$ possède une partition de $r (r\leqslant k)$ sous ensembles t.o. $M_i$, et on a $\{a\} \cap T = \begin{cases} \emptyset \\ \lor \\ a \text{ (si } a \in T) \end{cases} \Rightarrow \begin{cases} \emptyset \subseteq M_i , \, \underset {[1,r]}{\forall} i \hspace{0.5cm} (\emptyset \text{ est inclus dans n'importe quel ensemble ...)} \\ \lor\\ \underset {[1,r]}{\exists} i , (a \in M_i) \text{ et donc } \{a\} \subseteq M_i \end{cases} \Longrightarrow \underset {[1,r]}{\exists} i \,,\,\{a\} \cap T \subseteq M_i \hspace{1.5 cm} CQFD$

. $\Lambda$ est de caractère fini (def 2, III-34)

Démonstration : il s'agit de montrer ($A$ fini $\subseteq B$ fortement lié) $\Longleftrightarrow A$ fortement lié
- Soit $F$ partie finie quelconque de $E$, alors $B$ fortement liée $\Longrightarrow \exists (P_i)_{i\in I \text{ fini}}$ partition de $F \land \underset {I}{\exists} j$ tel que $ F\cap B \subseteq P_j$
- Or : $F\cap B \subseteq P_j \underset{A\subseteq B}{\Longleftrightarrow} F \cap (A\cup \complement_B A) \subseteq P_j \Leftrightarrow \Bigl( (F \cap A) \cup (F \cap \complement_B A)\Bigr) \subseteq P_j \Rightarrow F \cap A \subseteq P_j \Rightarrow A$ fortement lié $\hspace{1 cm}$ CQFD

. Par conséquent, par III-35 - Th. 1, $\Lambda$ admet un élément maximal $C_0 \hspace{3 cm}$ CQFD


2) toute partie libre de $E-C_0$ a, au plus, $k-1$ éléments :

Par l'absurde, supposons : $\exists A, \,\Bigl(A=PL(E-C_0)\, \land \, Card(A)>k-1 \Bigr)$

. $Card(A)>k-1$ entraine $Card(A)\geqslant k$

Or $k=max [PL(E)]$ entraîne $k=max \Bigl( Card [PL(E)-C_0]\Bigr)$ et donc : $Card(A)\leqslant k$

Il s'ensuit $Card(A)=k $ et par conséquent $A=\{a_1,...,a_k\}$

. $C_0$ fortement liée maximale $\land \,\underset{ [1,k]}{\forall} i,\, (a_i \notin C_0) \Rightarrow \underset{ [1,k]}{\forall} i,\,\Bigl( \Theta_i = C_0 \cup \{a_i\}\text{ non fortement liée}\Bigr)$

$ \Leftrightarrow \underset{[1,k]}{\forall} i,\, \exists F_i, \, \Bigl[F_i \subseteq E \, \land \, F_i$ fini $\,\land \, \forall (T_j)_{j \in [1,r],r\leqslant k}$ partition de $F_i$ avec $T_j$ t.o. $\,\land\, \underset{[1,r]}{\forall} j,\, (F_i\cap\Theta_i \nsubseteq T_j)\Bigr]$

Note : la dernière équivalence ci-dessus signifie que les éléments de $F_i \cap \Theta_i$ ne peuvent pas être, tous à la fois, contenus dans un seul élément $T_j$ de la partition}

. ($R_3$) Une remarque importante: $\underset{[1,k]}{\forall} i\, ,\, (a_i\in F_i)$
En effet : si $a_i \notin F_i$ alors $F_i\cap \Theta_i = F_i \cap [C_0 \cup \{a_i\}] = F_i \cap C_0$, et alors par définition de $C_0 : \exists (U_j)_{1 \leqslant j \leqslant r \leqslant k}$ partition de $F_i \land \underset{[1,r]}{\exists} q \, ,\, (F_i \cap C_0 \subseteq U_q) \longrightarrow$ contradiction ! $\hspace{1 cm}$ CQFD

. On considère alors $F=\displaystyle\bigcup_{i=1}^k F_i \,. \,F$ contient donc $a_1 , a_2, \dotsc, a_k$ et $F$ est fini en tant que réunion finie d'ensembles finis (cela se démontre par récurrence à l'aide de l'exercice 1) du même chapitre

. Or : $F \text{ fini } \underset{\text{def. de } C_0} {\Longrightarrow} \exists (P_i)_{1\leqslant i \leqslant r \leqslant k} \text{ partition de } F$ en sous ensembles t.o. $\land \underset{[1,r]}{\exists} n \,,\, (C_0\cap F \subseteq P_n)$

. Comme $a_1 , a_2, \dotsc, a_k$ libres et que $(P_i)_{1\leqslant i \leqslant r \leqslant k}$ est une partition de $F$ en sous-ensembles t.o. : $\underset{[1,k]}{\exists} m \, ,\, (a_m \in P_n)$ (en raisonnant comme dans la remarque $R_3$ , on a même $r=k \,\,$ ! )

. En notant $P'_i = F_m \cap P_i$, on a $F_m = P'_1 + P'_2 + \dotsb + P'_k$ (partition de $F_m$)

. Alors $F_m\cap C_0 = (F_m\cap F) \cap C_0 = F_m \cap (F \cap C_0) \subseteq F_m \cap P_n = P'_n$

Mais comme : ($a_m \in F_m \land \ a_m \in P_n) \Rightarrow a_m \in P'_n$, il s'ensuit que $\Bigl( (F_m \cap C_0)\cup a_m \Bigr) \subseteq P'_n \Longleftrightarrow \Bigl( F_m \cap (C_0 \cup a_m) \Bigr) \subseteq P'_n \Longleftrightarrow F_m\cap \Theta_m\subseteq P'_n$ (élément d'une partition de $F_m) \longrightarrow$ contradiction !

CQFD