Produit ou lexicographique : compter les comparables

$E$ a $9$ éléments, donc $\left(\genfrac{}{}{0ex}{}{9}{2}\right)=36$ paires d'éléments distincts.

1. Calcul exhaustif : $27$ paires comparables pour l'ordre produit, $36$ pour l'ordre lexicographique. Le second chiffre était prévisible : $36$ sur $36$, c'est-à-dire toutes, et c'est la définition d'un ordre total. Le premier ne l'était pas : on perd exactement un quart des comparaisons.

2. Les $9$ paires incomparables pour le produit :

Elles ont toutes la même forme : l'une gagne sur la première composante, l'autre sur la seconde. C'est la raison pour laquelle l'ordre produit est partiel, et il n'y en a pas d'autre.

3. Non : il y a deux minimaux. $E\setminus \{(0,0)\}$ admet $(0,1)$ et $(1,0)$ comme éléments minimaux — calcul vérifié — et aucun minimum, puisque ces deux-là sont précisément incomparables.

Ce que le contraste enseigne, et ce qui compte pour la suite. Les deux ordres portent sur le même ensemble, avec les mêmes ordres sur les composantes. Le lexicographique est plus fin : il compare tout, en décidant arbitrairement que la première composante prime. Le produit ne compare que ce dont il est sûr.

Et pourtant — c'est le point — les deux sont bien fondés. Un ordre partiel n'est pas un ordre défectueux : pour prouver une terminaison, on n'a pas besoin de comparer tous les états, seulement de garantir qu'on descend. C'est l'ordre produit qui prouvera la terminaison d'une double boucle, et le lexicographique celle d'Ackermann à l'exercice suivant.