Exercices de khôlle pour la MPSI

Année scolaire 1997-1998

Deuxième semaine (relations, réels)

David A. Madore ( )

Exercice original et difficile. On dit qu’un ensemble partiellement ordonné W est \underline{bien ordonné} si et seulement si tout sous-ensemble non vide de W admet un plus petit élément. Pour tout a ∈ W, on note alors s(a) = {x ∈ W: x < a} le “segment initial” de a.

1) Montrer que tout ensemble bien ordonné est totalement ordonné. 1bis ) Montrer que si (W, ≤) et (W, ≥) sont tous deux bien ordonnés alors W est fini. 2) (Principe d’induction transfinie.) On suppose que W est bien ordonné, et que A ⊆ W vérifie la propriété suivante : si s(a) ⊆ A alors a ∈ A. Montrer que A = W. (Morale : A correspond a une certaine propriété ; on suppose que si tous les prédécesseurs de a ont cette propriété alors a lui-même l’a ; alors tous les éléments de W ont cette propriété.) 3) Montrer par un exemple que les ensembles totalement ordonnés ne vérifient pas tous le principe d’induction transfinie. 4) Montrer qu’un ensemble totalement ordonné vérifiant le principe d’induction transfinie est bien ordonné. 5) Application : Soit W un ensemble bien ordonné ; montrer que si f: W → W est une bijection croissante, alors f est l’identité. On dit dans ces circonstances que W est \underline{rigide}. 6) Donner un exemple d’ensemble totalement ordonné qui ne soit pas rigide. Donner un exemple d’ensemble totalement ordonné rigide qui ne soit pas bien ordonné.

Densité des dyadiques. Montrer que les réels de la forme \frac{a}{2^{k}} avec a ∈ ℤ et k ∈ ℕ sont denses dans ℝ.

“La catégorie des ensembles totalement ordonnés n’admet pas de produit”. Soient E et F deux ensembles totalement ordonnés, ayant au moins deux éléments chacun. On note p et q les projections canoniques respectives de E × F sur E et F. Montrer qu’il n’existe pas de structure d’ensemble totalement ordonné sur E × F telle que p et q soient croissantes.

Exercice d’introduction. Soit A un ensemble quelconque. On considère la relation ⊆ sur P(A). Montrer qu’il s’agit d’une relation d’ordre. Dans quels cas est-elle totale ? Quels sont les plus grand et plus petit élément ? Quels sont les éléments minimaux de P(A)\{∅}?

Exercice faisant appel à un peu de dénombrement. On considère dans un ensemble de n personnes la relation d’amitié, qu’on suppose irréflexive et symétrique. Montrer qu’il y a deux personnes ayant le même nombre d’amis.

Exercice trop facile. Soient E et F deux ensembles, et f: E → F une application. Montrer que la relation sur E définie par xRy ssi f(x) = f(y) est une relation d’équivalence.

Compacité des intervalles fermés bornés. Soit I = [a; b] avec a < b dans ℝ. On suppose que I ⊆ ⋃_{k∈K} I_{k} avec I_{k} =]a_{k}; b_{k}[, a_{k} < b_{k}. Montrer qu’il existe K_{0} ⊆ K \underline{fini} tel que I ⊆ ⋃_{k∈K_{0}} I_{k}. Pour cela, on pourra introduire l’ensemble Z des t ∈ ℝ tels que pour tout u < t l’intervalle [a; u] ∩ [a; b] soit recouvert par un nombre fini des I_{k} : on montrera que Z est un intervalle, et on cherchera à déterminer la borne supérieure de celui-ci.