TD4 : Relations d’ordre

EX 1

1) Bel ordre total ⟺ Bon ordre :

⟹ : ABS : Si il existe une partie non vide $A$ de $E$, tq : $∀x ∈ A, ∃y ∈ E, \lnot(x≼y)$ : donc, comme l’ordre est total : $∀x ∈ A, ∃y ∈ E, y≼x$.

En notant $x_0$ un élément de $A$ non vide : \(∀n, ∃x_{n+1} ∈ E, x_{n+1}≼x_n\)

Montrons qu’il existe une suite d’éléments de $E$ dont toute sous-suite n’est pas croissante.

⟸ : On pose $i_0 = 0$ : et on note $x_{i_n}$ le $\min {x_i}{i > i{n-1}}$ : on a construit une sous-suite croissante.

Ordres totaux qui ne sont pas des bels ordres : ordres naturels dans des groupes (on passe à l’opposé d’une suite strictement croissante).

Bel ordre : dans $ℕ$.

2)

(1) ⟹ (2) : trivial (2) ⟹ (3) : trivial (3) ⟹ (1) :

Th de Ramsey (infini) : Soit $X$ un ensemble infini dénombrable. Pour toute coloration finie de $X^{(n)}$, il existe un sous-ensemble infini $M$ de $X$ tel que $M^{(n)}$ soit monochrome.

avec 3 couleurs

Soit $(x_i)_{i∈ℕ}$ une suite d’éléments de $E$.

Arêtes : ${(x_i, x_j), i<j}$

Dans le graphe complet dont les sommets sont les éléments de le suite, on colorie les arêtes avec 3 couleurs : il existe une clique infinie monochromatique.

Les couleurs :

• rouge si $x_i ≼ x_j$
• vert si $x_j ≼ x_i ∧ x_i ≠ x_j$
• bleu si incomparables

Ramsey ⟹ si la couleur de la clique infinie est :

• bleue : il y a une antichaîne infinie : impossible, par hypothèse
• vert : on obtient un suite str. décroissante : impossible, idem
• rouge : on obtient une suite croissante

3) Il faut et il suffit, par (3) ⟹ (1), de montrer que l’ensemble des antichaînes est dénombrable ssi il n’y a pas d’antichaîne infinie.

⟹ : s’il y avait une antichaîne infinie, l’ensemble de ses parties serait indénombrable.

⟸ : union (sur leur cardinal) dénombrable d’ensembles dénombrables OU : inclus dans l’ensemble des parties finies de $E$.

4) Considérer la composée des extractrices.

5)

a)

• réflexive, avec $i_{k} = k$

• antisymétrique : si $a_1 ⋯ a_m ≤{sm} b_1 ⋯ b_n$ et $b_1 ⋯ b_m ≤{sm} a_1 ⋯ a_n$ alors :

• $m ≤ n$ et $n ≤ m$ ⟹ $n=m$

• Donc $i_k = k$, et il y a égalité des lettres, par antisymétrie de $≼$

• transitive : avec l’intersection des ensembles d’indices

b) Soit $(a^{(i)}{j_i})_i$ une suite de mots $a^{(0)}_1 ⋯ a^{(0)}{j_0}, ⋯, a^{(n)}1 ⋯ a^{(n)}{j_n}$.

EX 2

1) Dickson

2) a) Le chemin qui permet d’accéder de $U_1$ à $V_1$ permet d’accéder de $U_2$ à un vecteur $V_2$ de $ℕ^k$, car les coordonnées de $U_1$ sont inférieures à celles de $U_2$.

b) Si $U \overset{t}{⟶} V$, on continue à ajouter $t$

d) L’algo termine ssi l’arbre est fini.

• Chaque noeud de l’arbre possède au plus $\vert T\vert $ fils.
• Il n’y a pas de branche infinie, car sinon : on a utilisé $R_2$ strictement plus de $k$ fois : impossible, car à chaque fois, on donne la valeur $𝜔$ à un composante (d’indice distinct à chaque) d’un vecteur.

Lemme de Koenig : Si $A$ est un arbre infini à branchements (=arités) finis, alors $A$ possède une branche infinie.

L’arbre est donc fini.

e) En appliquant $a$ et $b$ successivement un nombre arbitraire de fois, on augmente la deuxième composante de $V_0$ autant qu’on veut.

f)

• Par l’absurde : sinon, $V ≥ W$ ou $V$ et $W$ incomparables : impossible, puisqu’on aurait alors dû ajouter un sommet étiqueté par un vecteur plus ($R_2$) ou égal ($R_3$) à $V$.

⟸ : on a dû appliquer $R_2$, donc d’après b) : on peut faire une boucle.

⟹ : contraposée : si on n’a pas d’$𝜔$, il y a un nombre fini de vecteurs plus petits que les sommets. Or : tout vecteur accessible est est plus petit que ces sommets : il y en a donc un nombre fini.

NB : Machine de Minsky = idem, sauf qu’en plus, on peut “tester si une composante vaut 0” ⟶ aussi expressif que les MT.