Minimal n'est pas minimum, et l'on peut les compter
Exercice · niveau 2 · informatique (MP2I/MPI), chapitre 9 — Ordres bien fondés et induction structurelle
Énoncé
Dans l'ensemble ordonné par la divisibilité :
- quels sont les éléments minimaux ? Combien y en a-t-il ?
- a-t-il un minimum ?
- a-t-il un maximum ? des éléments maximaux ?
Corrigé
1. Les minimaux sont exactement les nombres premiers de , et il y en a dix, énumérés par le calcul :
Preuve. est minimal s'il n'a aucun diviseur strict dans . Ses diviseurs autres que lui-même sont — hors de — et ses diviseurs propres . Il est donc minimal si et seulement si il n'a pas de diviseur propre , c'est-à-dire s'il est premier.
2. Aucun minimum. Un minimum devrait diviser tous les éléments de , donc diviser à la fois et : ce serait , qui n'est pas dans . On a donc dix éléments minimaux et aucun minimum — l'illustration exacte de la mise en garde du cours, et cette fois avec un compte.
3. Les maximaux sont les éléments de dont aucun multiple propre n'est dans . Le plus petit multiple propre de est : est donc maximal si et seulement si , c'est-à-dire . Il y en a quinze — calcul vérifié : . Noter que , et ne le sont pas, malgré leur taille : , et sont dans .
Il n'y a pas de maximum : il devrait être multiple de et de , donc valoir au moins .
Le dessin qui aide. L'ordre de divisibilité sur se lit comme le graphe orienté acyclique du cours : un arc de vers quand divise immédiatement. Les minimaux sont les sommets sans arc sortant — les dix premiers —, les maximaux ceux sans arc entrant. Un minimum serait un sommet atteint depuis tous les autres : il n'y en a pas, et le graphe le montre d'un coup d'œil.
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.