Adloun

informatique (MP2I/MPI) · Chapitre 9 · Application directe du cours

Minimal n'est pas minimum, et l'on peut les compter

Ordres bien fondés et induction structurelle · niveau 2

É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.

Exercices semblables

Le cours du chapitre · Tous les exercices du chapitre