Mathématiques pour l’Informatique 2 2016–17 http://www.lri.fr/~blsk/MI2

6 Équivalences et Ordres

Dans cette partie on considère une relation binaire R sur un ensemble A à la fois comme domaine et comme image, soit un sous ensemble de A × A.

6.1 Définitions

On définit ici les principales propriétés des relations binaires.

Définition 1 (Propriétés d’une relation) On introduit les propriétés suivantes pour une relation.
Réflexivité
R est réflexive ssi ∀ x ∈ A, R(x,x)
Transitivité
R est transitive ssi ∀ x y z ∈ A, R(x,y) ⇒ R(y,z) ⇒ R(x,z)
Symétrie
R est symétrique ssi ∀ x y ∈ A, R(x,y) ⇒ R(y,x)
Irreflexivité
R est irréflexive ∀ x ∈ A, ¬ R(x,x)
Anti-symétrie
R est anti-symétrique ∀ x y ∈ A, R(x,y) ⇒ R(y,x) ⇒ x = y
Exemple 1

6.2 Équivalence

Définition 2 (Relation d’équivalence) Un relation est une relation d’équivalence si elle est réflexive, symétrique et transitive.

L’égalité est une relation d’équivalence et nous allons montrer qu’une relation d’équivalence peut servir d’égalité.

Exemple 2 On peut définir une relation sur les couples d’entiers ℕ×ℕ par :
(n1,m1) ≡ (n2,m2)
def
=
 
 n1+m2=n2+m1
D’un point de vue géométrique, les couples (n1,m1) et (n2,m2) sont équivalents si les différences n1−m1 et n2−m2 sont égales.

On montre aisément que c’est une relation d’équivalence, la seule difficulté est la transitivité : si (n1,m1) ≡ (n2,m2) et (n2,m2) ≡ (n3,m3) alors par définition n1+m2=n2+m1 et n2+m3=n3+m2. On a alors n1+m2+n3=n2+m1+n3 donc n1+n2+m3=n2+m1+n3 et donc n1+m3=m1+n3 donc (n1,m1)≡ (n3,m3).

On peut regrouper tous les éléments de A qui sont équivalents entre eux.

Définition 3 (Classe d’équivalence) Soit R une relation d’équivalence sur A. Une classe d’équivalence pour R est un ensemble C non vide tel que ∀ x ∈ C, ∀ y ∈ A, y ∈ C ⇔ R(x,y).
Soit x ∈ A, l’ensemble {y ∈ A | R(x,y)} est une classe d’équivalence (appelée la classe d’équivalence pour R de x).
Exercice 1 Donner les classes d’équivalence de (0,1) et (1,0) pour l’équivalence de l’exemple 2.

6.2.1 Partition

Deux classes d’équivalence sont soit égales, soit disjointes et chaque élément de A appartient à une classe d’équivalence (la sienne). On dit que l’ensemble des classes d’équivalences forme une partition de l’ensemble A.

Définition 4 (Partition) Soit P un ensemble de parties de A (c’est-à-dire P⊆ ℘(A)). On dit que P est une partition de A si tous les éléments de P sont non vides, disjoints 2 à 2 et couvrent tout l’ensemble A.
Exemple 3 Dans une classe mixte d’étudiants, Soit X le sous-ensemble des filles et Y le sous-ensemble des garçons alors {X;Y } forme une partition de l’ensemble des étudiants. Si on prend le sous-ensemble N de ceux qui font de la natation et le sous-ensemble B de ceux qui font du basket, en général {B;N } ne sera pas une partition (certains étudiants peuvent ne pratiquer aucune de ces activités ou au contraire en pratiquer 2).
Proposition 1 Soit une relation d’équivalence R sur A. Soit X l’ensemble des classes d’équivalence de R défini par :
X
def
=
 
 {C ∈ ℘(A) | C classe d’équivalence de R}
alors X forme une partition de A.

Preuve: Les classes d’équivalence sont non vides par définition. Chaque élément x∈ A appartient à la classe d’équivalence de x et donc à ∪X. Soient deux classes C1 et C2, montrons que si elles ont un élément commun alors elles sont égales. Supposons qu’il existe x∈ C1 ∩ C2. Soit y∈ C1 alors on a R(x,y) car x ∈ C1 donc on a aussi y∈ C2 car x∈ C2 et R(x,y) donc C1 ⊆ C2. De manière symétrique on a aussi C2⊆ C1, donc C1 = C2. □

De manière réciproque, si on se donne une partition P d’un ensemble A alors on peut définir une relation d’équivalence R de A telle que la partition P corresponde au découpage en classes d’équivalence de R. Il suffit de poser :

R(x,y)
def
=
 
 ∃ C∈ P, x∈ C ∧ y ∈ C

On vérifie que c’est bien une relation d’équivalence.

6.2.2 Espace quotient

Lorsqu’une équivalence R sur un ensemble A est définie, on souhaite identifier les éléments qui sont équivalents. On s’intéresse à l’ensemble des classes d’équivalence que l’on appelle l’espace quotient de l’espace A par la relation R et on le note A/R. Un élément de cet ensemble correspond à un sous-ensemble de A d’objets équivalents entre eux. Pour chaque élément C de A/R, il existe x∈ A tel que C est la classe d’équivalence de x, mais ce x n’est pas unique: C est aussi la classe d’équivalence de y pour tout y tel que R(x,y).

Exemple 4

Application compatible avec une équivalence.

Soit A un ensemble et R une relation d’équivalence sur A. On veut construire une application f de A/R dans X. Comme pour les autres applications, si a=b alors f(a)=f(b). Comme a,b∈ A/R, a et b sont des classes d’equivalence. Si on prend un représentant dans A de a (noté x) et un représentant dans A de b (noté y), on n’a pas forcément x=y, mais on sait que R(x,y). Si on calcule la valeur de f(a) à partir d’un représentant x de a en utilisant une application g∈ A → X alors on doit s’assurer que ∀ x y ∈ A, R(x,y) ⇒ g(x)=g(y).

Ceci nous donne un principe de construction d’application dont le domaine est un ensemble quotient.

Proposition 2 Soit g une application de A → X telle que ∀ x y ∈ A, R(x,y) ⇒ g(x)=g(y), alors il existe une unique application f ∈ A/R → X telle que ∀ a ∈ A/R,∀ x ∈ a, f(a)=g(x)
Exemple 5 Si on considère les entiers relatifs représentés comme des couples d’entiers, on peut définir l’opération opposée par opp(n,m)=(m,n) qui est une application de ℕ×ℕ → ℕ×ℕ.

On vérifie que si (n1,m1)≡(n2,m2) alors par définition de l’équivalence, on a n1+m2=m1+n2 et donc opp(n1,m1)≡ opp(n2,m2)

Si ℤ =def ℕ×ℕ/≡ alors on introduit opp1 une application de ℕ× ℕ → ℤ en associant à (n,m) la classe d’équivalence de opp(n,m). On a alors si (n1,m1)≡(n2,m2) alors opp1(n1,m1)≡ opp1(n2,m2). On peut alors passer au quotient pour construire une application de ℤ→ℤ.

Ce principe est important en informatique, en effet lorsque l’on représente une notion avancée dans un ordinateur, on doit souvent utiliser une représentation concrète (sous forme de terme par exemple). Il est courant que l’égalité sur la représentation concrète soit différente de l’égalité mathématique que l’on souhaite modéliser.

Par exemple, si on représente des rationnels en machine, on utilisera deux entiers pour le numérateur et le dénominateur. Mais on peut alors avoir plusieurs représentations pour le même objet : (1,2), (8,16)…

De même un ensemble fini peut se représenter par une séquence, mais plusieurs séquences peuvent représenter le même ensemble : [1;2], [2;1;1] …

On peut parfois trouver des représentations canoniques par exemple dans le cas des rationnels, demander que numérateur et dénominateur n’aient pas de facteur commun (on dit que la fraction est irréductible), ou bien dans le cas des ensembles, demander que la séquence soit ordonnée avec un ordre total strict. Néanmoins ce n’est pas toujours le meilleur choix d’un point de vue informatique, car maintenir la contrainte d’être irréductible ou d’être trié nécessite des opérations supplémentaires (après une addition, ou une union par exemple) qui peuvent être trop coûteuses. On peut donc se contenter que les opérations programmées respectent bien la relation d’équivalence sur la représentation qui correspond à l’égalité de la notion mathématique que l’on souhaite modéliser.

Exercice 2 (Construction de ℚ)
Soit E=ℤ×(ℕ∖{0 }) on définit la relation (a,b)≡(c,d) =def ad=bc.
  1. Montrer que ≡ est une relation d’equivalence sur E.
  2. Quelle est la classe d’équivalence de (0,1) ? de (1,1) ?
  3. Soit les applications plus et mult dans E × E → E définies par :
    plus((a,b),(c,d))
    def
    =
     
    		 (ad+bc,bd) mult((a,b),(c,d))
    def
    =
     
    		 (ac,bd)
    Montrer que ces applications sont compatibles avec la relation ≡.
  4. Montrer que pour tout a, b et c dans E, on a
    mult(plus(a,b),c)≡ plus(mult(a,c),mult(b,c))
  5. (Optionnel) Soit la fonction inv de E dans E définie par :
    inv((a,b))
    def
    =
     
    		 (b,a)
    • Quel est l’ensemble de définition de inv ?
    • Montrer que ∀ x∈ E, x≢(0,1) ⇒ mult(x,inv(x))≡ (1,1)

6.2.3 Représentation informatique de classes d’équivalence

Il est parfois utile en informatique de pouvoir organiser des données en classes d’équivalence. C’est-à-dire représenter des partitions d’un ensemble fini A.

Les structures dites union-find permettent de réaliser cela. On en donne ici une représentation abstraite qui peut se voir comme l’interface d’une bibliothèque pour la manipulation de ces structures.

On notera U l’ensemble des structures union-find qui représentent les partitions de l’ensemble A. On ne dit pas comment ces partitions sont représentées mais on se donne les objets suivants pour travailler sur cette structure.

On indique ci-dessous quelques propriétés des objets ci-dessus.

Il y a plusieurs manières de représenter les structures union-find qui peuvent être plus ou moins efficaces. L’idée est que chaque paquet soit organisé comme un arbre dont la racine est le représentant du paquet avec des liens inversés qui vont des fils vers le père. Pour que la fonction de recherche du représentant soit efficace il faut que le chemin soit le plus court possible. Dans l’opération d’union on a deux paquets qui ont chacun leur représentant. Il faut raccrocher la racine de l’un comme fils de la racine de l’autre. On peut le faire en s’arrangeant pour que la hauteur de l’arbre reste la plus tetite possible. Dans l’opération de recherche du représentant, on parcours l’arbre jusqu’à la racine, on peut en profiter pour rattacher tous les nœuds rencontrés directement à la racine et ainsi les recherches suivantes sur ces mêmes nœuds se feront en temps constant.

6.3 Construction d’ordres

6.3.1 Définitions générales sur les ordres

Définition 5 (Ordre) Une relation binaire est un pre-ordre si elle est transitive et anti-symétrique. C’est un ordre si elle est de plus réflexive. Un ordre strict est un pre-ordre qui est de plus irréflexif.
Définition 6 (Ensemble ordonné) Un ensemble ordonné est un couple (E,≤) avec ≤ une relation d’ordre sur E.
Exemple 6
Définition 7 (Ordre strict associé à un ordre) Si on se donne une relation d’ordre ≤ sur un ensemble A alors on peut définir l’ordre strict associé par x<y =def x ≤ y ∧ x≠y qui est une relation irreflexive et transitive.

Un ordre peut être total s’il permet de comparer deux éléments différents quelconques de A, il est dit partiel dans le cas contraire.

Définition 8 (Ordre total, partiel) Un ordre est total ssi ∀ x y, (x ≤ y ∨ y ≤ x). Un ordre qui n’est pas total est dit partiel.
Exemple 7 L’ordre usuel sur les entiers est total, celui d’inclusion sur les ensembles est partiel car par exemple {1,2 } et {2,3 } sont incomparables.
Exercice 3 (Ordre préfixe sur les mots) On définit une relation m1 ≺ m2 sur les mots si m1 est un préfixe de m2, c’est-à-dire que le mot m2 commence par le mot m1.
  1. Proposer une formule logique correspondant à la relation m1 ≺ m2.
  2. Montrer que m1 ≺ m2 est un ordre.
  3. Cet ordre est-il total ou partiel?
Définition 9 (Application monotone) Soient deux ensembles ordonnés (A1,≤1) et (A2,≤2) et une application f∈ A1→ A2. On dit que f est monotone si et seulement si
∀ x y, x ≤1 y ⇒ f(x)≤2 f(y)
f est strictement monotone si et seulement si
∀ x y, x <1 y ⇒ f(x) <2 f(y)
ou de manière équivalente si elle est monotone et de plus
∀ x y, x ≠ y ⇒ f(x) ≠ f(y)
(ce qui est équivalent à f est injective) Une suite monotone d’éléments d’un ensemble ordonné (A,≤) est une application monotone de (ℕ,≤) dans (A,≤).

6.3.2 Diagramme de Hasse

Une relation binaire R sur un ensemble fini A peut se représenter graphiquement en représentant les éléments de A par des points et en mettant une flèche de x à y lorsque R(x,y).

Dans le cas d’un ordre, certaines flèches sont obligatoires (reflexivité, transitivité). Pour simplifier le diagramme, on peut donc les ignorer. Formellement, cela revient à définir une relation successeur S(x,y) associée à une relation d’ordre.

S(x,y)
def
=
 
 R(x,y) ∧ x≠y ∧ ∀ z, R(x,z)∧ R(z,y) ⇒ (z=x∨ z=y)

Le diagramme de Hasse d’un ordre R est la représentation graphique de la relation successeur S. Cette relation détermine de manière unique la relation R comme la plus petite relation reflexive et transitive qui contient S.

6.3.3 Majorants et minorants

Lorsqu’on a une relation d’ordre sur un ensemble, il est intéressant de considérer les éléments les plus grands ou bien les plus petits.

Définition 10 (Majorants) Soit X ⊆ A, on appelle ensemble des majorants de X dans A, l’ensemble des éléments de A qui sont plus grands que tous les élements de X, c’est-à-dire :
maj(X)={x ∈ A | ∀ y ∈ X, y ≤ x}
On définit de même l’ensemble des minorants :
min(X)={x ∈ A | ∀ y ∈ X, x ≤ y}
Exemple 8 L’ensemble des entiers impairs n’a pas de majorant dans ℕ mais admet {0;1 } comme ensemble de minorants. L’ensemble des majorants et des minorants de l’ensemble vide est égal à l’espace A tout entier.

Il faut noter que l’ensemble des majorants de X peut contenir des éléments qui ne sont pas dans X.

Définition 11 (élément maximal, maximum) Soit X⊆ A.
Proposition 3 Si X⊆ A admet un élément maximum alors cet élément est aussi maximal, c’est l’unique élément de maj(X)∩ X.

Preuve: Soit a un élément maximum de X dans A alors par définition a∈ X et ∀ x∈ X, x ≤ a c’est-à-dire a ∈ maj(X). Les éléments maximum sont par définition les éléments de maj(X)∪ X. Montrons maintenant que maj(X)∩ X est réduit à un élément. Supposons x et y dans maj(X)∩ X. Comme x∈ X et y ∈ maj(X), on a x ≤ y. De même en inversant les rôles de x et de y on trouve y ≤ x et donc x=y. □

Il faut faire attention que certaines propriétés ne sont vraies que dans le cas d’un ordre total. Un élément maximal n’est pas toujours maximum. Si on regarde X={{1 };{2 } }, les éléments de A sont incomparables et tous les deux sont des éléments maximaux de X qui n’admet pas d’élément maximum. Même si un ensemble a un seul élément maximal, cela ne veut pas dire qu’il est maximum. Par exemple, on peut prendre un ensemble X de sous ensembles de ℕ qui contient tous les ensembles Xn =def {k ∈ ℕ | k est pair ∧ k≤ 2n} ainsi que l’ensemble Y =def {1 }. On a Xn ⊆ Xn+1 et Xn ≠ Xn+1 donc aucun ensemble Xn n’est maximal. Les ensembles Xn et Y sont incomparables pour tout n et donc Y est maximal. C’est l’unique élément maximal mais il n’est pas maximum.

Exercice 4 Montrer que si ≤ est un ordre total alors un élément maximal est aussi maximum.
Preuve: Soit a un élément maximal, on a a ∈ X et ∀ x∈ X, a ≤ x ⇒ a=x. Il faut montrer que ∀ x∈ X, x ≤ a. Comme l’ordre est total on peut raisonner par cas suivant que x ≤ a ou a ≤ x. Dans le premier cas, x ≤ a on a la propriété attendue. Dans le second cas a ≤ x, comme a est maximal, on en déduit a=x et donc x ≤ a également. □
Définition 12 (Borne supérieure) On dit que a∈ A est la borne supérieure d’un ensemble X, si et seulement si a est un majorant de X et a est le minimum des majorants (s’il existe). C’est-à-dire :

De même la borne inférieure se définit comme le plus grand des minorants.

Remarques.

Proposition 4 Soit E un ensemble et A=℘(E) ordonné par la relation d’inclusion. Tout sous ensemble X de A admet une borne supérieure qui est ∪X.

Preuve: Par définition de ∪X. On a ∀ Y∈ X, Y ⊆ ∪X et ∪X est le plus petit ensemble qui contient tous les Y∈ X au sens où s’il existe Z tel que on a ∀ Y∈ X, Y ⊆ Z alors ∪X ⊆ Z. □

De même en considérant l’ordre inverse, on montre que toute partie X de ℘(E) admet une borne inférieure qui est ∩X.

Pour l’ordre de la divisibilité, la borne supérieure de {x;y } est exactement le plus petit multiple commun des deux nombres.

Exercice 5 On se donne un ensemble A, un ordre ≤ sur cet ordre et un ensemble X. Dans chacun des cas suivants, dire si l’ordre est total et donner pour X l’ensemble des majorants, des minorants, des éléments maximaux, des éléments minimaux, et lorsqu’ils existent : le minimum, le maximum, la borne supérieure et la borne inférieure.
  1. A=ℕ*, x≤ y ⇔ x div y, X={3,4,6}
  2. A=℘({a,b,c}) , x≤ y ⇔ x⊆ y, X={x∈ A|1≤ card(x)≤ 2}
  3. A=℘(ℕ) , x≤ y ⇔ x⊆ y, X={[n,+∞[ | n∈ ℕ}

6.3.4 Ordre sur un ensemble produit

Soient deux ensembles ordonnés (A1,≤1) et A2,≤2). Il y a plusieurs manières de définir un ordre sur l’ensemble produit A1× A2.

Définition 13 (Ordre produit) On définit l’ordre produit par (x1,x2)≤ (y1,y2) si et seulement si x1≤1 y1 ∧ x2 ≤2 y2.

Sur le plan ℤ×ℤ, les points plus petits que x,y seront tous ceux placés dans le quart de plan en bas à gauche de x,y.

Définition 14 (Ordre lexicographique) On définit l’ordre lexicographique par (x1,x2)≤ (y1,y2) si et seulement si x1<1 y1 ∨ (x1=y1 ∧ x2 ≤2 y2)

Sur le plan ℤ×ℤ, les points plus petits que x,y seront tous les points placés dans le demi-plan ouvert à gauche de x,y plus les points de la demi-droite verticale dessous x,y.

Exercice 6

6.4 Ordres bien fondés

Les ordres bien fondés sont des ordres pour lesquels il n’existe pas de suite infinie strictement décroissante. Ils jouent un rôle essentiel dans les preuves par induction mais aussi dans la terminaison des programmes. Si un programme contient une boucle et que l’on peut montrer qu’à chaque itération une certaine expression décroit pour un ordre bien fondé alors on garantit que la boucle devra forcément s’arréter.

Définition 15 (Ordre bien fondé) Un ordre ≤ sur un ensemble A est bien fondé s’il n’existe pas de suite infinie (xn)n∈ℕ strictement décroissante c’est-à-dire telle que ∀ n∈ℕ, xn+1 < xn.

L’ordre usuel sur les entiers naturels est un ordre bien fondé, par contre ce n’est pas le cas sur ℤ. L’ordre d’inclusion sur les parties de ℕ n’est pas bien fondé, en effet il suffit de regarder la suite des [n,∞[ qui est une suite infinie strictement décroissante.

Un ordre sur un ensemble fini est bien fondé, en effet dans une suite infinie strictement décroissante, si i<j alors xj<xi et par irreflexivité de l’ordre strict on a xj≠xi. Les éléments sont donc deux à deux distincts ce qui est impossible si l’ensemble est fini.

La caractérisation suivante des ordres bien fondés est parfois plus simple à manipuler.

Proposition 5 Un ordre ≤ sur un ensemble A est bien fondé si et seulement si toute partie non vide admet au moins un élément minimal.

Preuve: On rappelle que a ∈ X est un élément minimal de X si et seulement si ∀ x ∈ X, x ≤ a ⇒ x = a. Soit X une partie non vide de A et supposons qu’elle n’admette pas d’élément minimal. Alors pour tout a∈ A, il existe x ∈ X tel que x ≤ a ∧ x≠a c’est-à-dire x < a. Comme X≠∅ on peut construire une suite (xn)n∈ℕ d’objets de X en choisissant x0 arbitraire dans X et en choisissant pour xn+1 un élément de X strictement plus petit que xn. On construit ainsi une suite infinie strictement décroissante qui contredit le fait que ≤ est bien-fondée. Réciproquement, si tout ensemble non-vide admet un élément minimal, soit (xn)n∈ℕ une suite infinie décroissante. C’est un ensemble non vide donc qui admet un élément minimal xi. On a xi+1<xi ce qui contredit que xi est minimal. □

Proposition 6 L’ordre produit de deux ordres bien fondés est bien fondé. De même pour l’ordre lexicographique.

Preuve: On peut montrer que tout sous-ensemble X de A1× A2 admet un élément minimal. Pour cela on regarde X1={x ∈ A1 | ∃ y∈ A2,(x,y)∈ X} c’est un ensemble non-vide qui admet donc un élément minimal x1. On regarde ensuite Y1={y ∈ A2 | (x1,y)∈ X} c’est un ensemble non vide qui admet donc un élément minimal y1. On peut montrer que (x1,y1) est minimal dans X. Soit (x,y) ∈ X tel que (x,y)≤ (x1,y1), on a par définition de l’ordre produit x ≤ x1 et y≤ y1. Comme x∈ X1 et x1 est minimal on a x=x1 et donc y∈ Y1 et par minimalité de y1 on en déduit que y=y1.

La même construction s’applique pour l’ordre lexicographique. Montrons que (x1,y1) est minimal. Soit (x,y) ∈ X tel que (x,y)≤ (x1,y1), on a par définition de l’ordre lexicographique x < x1 ou bien x= x1 et y≤ y1. Comme x∈ X1 et x1 est minimal on a forcément x=x1 et donc y∈ Y1 et par minimalité de y1 on en déduit que y=y1. □

Les ordres bien fondés permettent de déduire un principe d’induction généralisé. Si on doit prouver ∀ x ∈ A,P(x) et que A est muni d’un ordre bien fondé, alors il suffit de prouver P(x) pour tout x∈ A en supposant de plus que P(y) est vérifié pour tous les y strictement inférieurs à x.

Proposition 7 Soit A un ensemble muni d’un ordre bien fondé ≤ et P(x) une propriété des élements de A.
Si ∀ x ∈ A, (∀ y ∈ A, y < x ⇒ P(y)) ⇒ P(x) alors ∀ x ∈ A, P(x)

Preuve: La preuve se fait par l’absurde en montrant que X={x ∈ A | ¬ P(x)} est vide. En effet s’il n’est pas vide alors il admet un élément minimal x∈ X. Comme x est minimal alors ∀ y ∈ A, y < x ⇒ y ∉X et donc ∀ y ∈ A, y < x ⇒ P(y) et donc l’hypothèse d’induction permet de prouver que P(x) est vrai, ce qui contredit le fait que x∈ X. □

Exemple 9 On cherche à définir la fonction d’Ackermann par les équations suivantes :
ack(0,m)=m+1 ack(n+1,0)=ack(n,1) ack(n+1,m+1)=ack(n,ack(n+1,m))

On peut définir la relation correspondante par cloture :

Ack(0,m,m+1)
Ack(n,1,y)
Ack(n+1,0,y)
Ack(n+1,m,y) Ack(n,y,z)
Ack(n+1,m+1,z)

Pour montrer que cette fonction est totale, il faut établir que : ∀ n m ∈ ℕ, ∃ y ∈ℕ, Ack(n,m,y). Une tentative par récurrence sur n ou sur m ne fonctionne pas. On peut utiliser plutôt une induction bien fondée sur le couple (n,m) en utilisant l’ordre lexicographique. On peut donc supposer que ∀ n1 m1∈ ℕ, (n1,m1)<(n,m) ⇒∃ y∈ℕ, Ack(n1,m1,y). Il faut alors montrer ∃ y ∈ℕ, Ack(n,m,y) On raisonne par cas :

Il n’est pas toujours aisé de construire des ordres bien fondés. Prenons l’ensemble A* des mots finis sur un alphabet A qui est un ensemble ordonné. On peut définir l’ordre lexicographique sur A* par m1 ≤ m2 si et seulement si m1 est un préfixe de m2 ou bien il existe un indice i inférieur à la longueur de m1 et à la longueur de m2 telle que m1[i]<m2[i] ∧ ∀ k < i, m1[k]=m2[k].

Si on se donne un alphabet à deux lettres {a;b } avec a < b alors on a

є < a a < aa ab < b aab<ab

Si on se restreint aux mots de longueur inférieure à une taille donnée n et si l’ordre sur l’alphabet est bien fondé alors il en est de même de l’ordre lexicographique sur les mots de longueur inférieure à n. Il suffit de généraliser la construction sur le produit pour construire un mot minimal dans chaque ensemble non vide. Par contre l’ordre lexicographique sur les mots n’est pas bien fondé si on considère des ensembles de mots dont la taille n’est pas bornée. En effet il suffit de considérer la suite (anb)n∈ℕ qui est strictement décroissante car pour tout n on a an+1b < an b.

L’ordre préfixe par contre est bien fondé (il ne nécessite pas d’ordre sur l’alphabet sous-jacent); l’ordre préfixe n’est pas total alors que l’ordre lexicographique l’est.

Remarques.

Les ordres sont une notion importante en informatique. En effet, la terminaison d’un programme est un problème indécidable, il faut donc pour chaque programme apporter une preuve spécifique du fait que le calcul s’arrêtera quelle que soit l’entrée. Exhiber un ordre bien fondé tel que le calcul construit une chaine décroissante de valeurs est une manière de résoudre ce problème.

Les ordres bien fondés servent également pour effectuer des preuves par induction.

Les ordres interviennent également dans le problème de l’ordonnancement en machine: l’ordinateur a plusieurs tâches à compléter, chacune se découpe en instructions élémentaires, et certaines instructions doivent être effectuées avant d’autres ce qui correspond à un ordre partiel. Le processeur doit exécuter les instructions de manière séquentielle, c’est-à-dire en construisant un ordre total qui doit respecter les contraintes.

6.5 Treillis et théorèmes de point fixe

Définition 16 Un ensemble ordonné (A,≤) est un treillis si deux éléments x et y ont une borne supérieure (notée x⊔ y) et une borne inférieure (notée x ⊓ y).
Exemple 10

Les opérations ⊓ et ⊔ satisfont des propriétés particulières :

Proposition 8 Soit (A,≤) un treillis. Les propriétés suivantes sont dérivables : Une conséquence des lois d’absorption est l’idempotence des opérations :
∀ x ∈ A, x ⊓ x = x ∀ x ∈ A, x ⊔ x = x
Preuve: On a x ⊓ x = x ⊓ (x ⊔ (x ⊓ x)) = x. on déduit ensuite x = x ⊔ (x ⊓ x) = x ⊔ x. □

Réciproquement, si on se donne deux opérations ⊓ et ⊔ qui sont symétriques, associatives et qui vérifient les lois d’absorption alors il est possible de définir une relation d’ordre x ≤ y =def x ⊓ y = x ce qui est équivalent à x ⊔ y = y.

6.5.1 Cas particuliers de treillis

Un treillis (A,≤) est dit borné s’il possède un élément minimum (noté ⊥) et un élément maximum (noté ⊤) qui sont différents. Un treillis borné vérifie les propriétés suivantes :

Preuve: Les premières propriétés sont une traduction de la propriété de maximum de ⊤ et de minimum de ⊥. Les dernières se déduisent de la règle d’absorption : x=x ⊓ (x ⊔ ⊤) et comme x ⊔ ⊤ = ⊤ on en déduit le résultat. □

Un treillis (A,≤) est distributif si de plus chaque opération est distributive par rapport à l’autre, c’est-à-dire que l’on a :

Un treillis (A,≤) borné est complémenté s’il existe une application x ↦ x telle que

Définition 17 (Algèbre de Boole) Un treillis qui est complémenté et distributif s’appelle une algèbre de Boole.
Exemple 11 Dans le cas du treillis sur les parties d’un ensemble E, l’opération de complément est l’application qui à un sous-ensemble A de E, associe son complément E∖ A.

Dans un treillis complémenté on a ⊤=⊥ et ⊥=⊤.
Preuve: On a ⊤ = ⊤ ⊓ ⊤ =⊥ et ⊥ = ⊥ ⊔ ⊥ =⊤. □

Dans un treillis distributif complémenté, il n’existe qu’une seule application de complément. Cette application vérifie les lois suivantes dites lois de de Morgan :

Preuve: On montre d’abord qu’il n’y a qu’une seule application de complément. Supposons que l’on ait deux compléments y1 et y2 pour x. On a alors x⊔ y1 = ⊤, x⊔ y2 = ⊤, x⊓ y1 = ⊥ et x⊓ y2 = ⊥. On a alors (x⊔ y1) ⊓ y2 = ⊤ ⊓ y2 = y2 et par distributivité (x⊔ y1) ⊓ y2 = (x ⊓ y2) ⊔ (y1 ⊓ y2) = ⊥ ⊔ (y1 ⊓ y2) = y1 ⊓ y2. Don y2=y1 ⊓ y2 et donc y2 ≤ y1. Le même raisonnement en changeant y1 et y2 nous donne y1≤ y2 et finalement y1 = y2.

x= x ⊔ ⊥ = x ⊔ (x⊓ x) = (x⊔ x) ⊓ (x⊔ x) = ⊤ ⊓ (x⊔ x) = x⊔ x donc x ≤ x.
x= x ⊓ ⊤ = x ⊓ (x⊔ x) = (x⊓ x) ⊔ (x⊓ x) = ⊥ ⊔ (x⊓ x) = x⊓ x donc x ≤ x et finalement x = x.
Pour montrer les lois de de Morgan, on peut utiliser l’unicité du complément et on prouve (x ⊓ y) ⊓ (x ⊔ ȳ)=⊥ (x ⊓ y) ⊔ (x ⊔ ȳ)=⊤.
On a (x ⊓ y) ⊓ (x ⊔ ȳ) = (x ⊓ y ⊓ x) ⊔ (x ⊓ y ⊓ ȳ) = (⊥ ⊓ y) ⊔ (x ⊓ ⊥) = ⊥ ⊔ ⊥ = ⊥.
x ≤ y ⇔ x ⊓ y = x ⇔ x ⊓y=x ⇔ x ⊔ ȳ=x ⇔ ȳ≤ x. □

6.5.2 Théorèmes de point fixe

Définition 18 (Treillis complet) Un treillis (A,≤) est complet si tout ensemble (pas seulement les ensembles finis) admet une borne supérieure. On notera ⊔X la borne supérieure de l’ensemble X.
Exemple 12 L’ensemble des parties de E est un treillis complet. La borne supérieure est l’union.

Un intervalle fermé de ℝ forme un treillis complet pour l’ordre usuel.

Proposition 9 Dans un treillis complet, tout ensemble admet une borne inférieure. On note X, la borne inférieure de l’ensemble X.

Preuve: Soit une partie X de A. On introduit Y l’ensemble des minorants de X et a la borne supérieure de Y. On montre que a est la borne inférieure de X.

Il faut montrer que ∀ x∈ X, a ≤ x. Soit x ∈ X, on a ∀ y ∈ Y, y ≤ x donc a ≤ x.

On suppose maitenant que y vérifie ∀ x∈ X, b ≤ x, on a alors y∈ Y et donc y ≤ a. □

La borne supérieure de l’ensemble A entier est un élément maximum noté ⊤ et la borne inférieure de A est un élément minimum noté ⊥. Un treillis complet est donc borné.

Proposition 10 (Point fixe de fonction monotone) Soit A un treillis complet et f une application monotone de A dans A, alors l’ensemble des point-fixes de f (ie {x ∈ A | f(x)=x}) est non-vide et admet un plus petit et un plus grand élément.

Preuve: On regarde l’ensemble des pre-point-fixes, ie F =def {x ∈ A | f(x)≤ x}. Cet ensemble contient au moins ⊤. On note a sa borne inférieure. On a

  1. ∀ x, f(x)≤ x ⇒ a ≤ x.
  2. ∀ y (∀ x, f(x)≤ x ⇒ y ≤ x) ⇒ y ≤ a .

On montre d’abord que f(a)≤ a. Pour cela il suffit de montrer que f(a) est un minorant de F. Soit donc x∈ F, on a f(x)≤ x, comme a est un minorant de F, on a et de plus a ≤ x et donc f(a) ≤ f(x) et par transitivité f(a) ≤ x et finalement f(a) ≤ a. Donc a∈ F.

Pour montrer a≤ f(a) on utilise la première propriété de la borne inférieure avec x=f(a). il suffit de montrer f(f(a))≤ f(a) qui est une conséquence de la monotonie et de la propriété f(a)≤ a montrée précédemment.

Donc a est un point fixe, c’est le plus petit car si on a un autre point fixe x, il appartient à F et donc il est plus grand que a.

De même le plus grand point fixe, se construit comme la borne supérieure de l’ensemble des post-point fixes, c’est-à-dire de G =def {x ∈ A | x ≤ f(x)} □

Une application de ce théorème est la définition d’une relation R par clôture. Dans une telle définition on se donne des règles d’inférence qui caractérisent la relation. Ces règles d’inférence peuvent se traduire sous la forme d’une équation R = F(R). Prenons l’exemple de la définition par cloture de l’ordre sur les entiers :

le(x,x)
le(x,y)
le(x,y+1)

L’espace est l’ensemble des parties de ℕ× ℕ muni de l’ordre d’inclusion. On traduit les règles d’inférence en la propriété attendue :

∀ x z, le(x,z) ⇔ ( x=z ∨ ∃ y,z=y+1 ∧ le(x,y))

On peut donc introduire la fonction F sur les relations binaires d’entiers par:

F(le)={(x,z) ∈ ℕ× ℕ | x=z ∨ ∃ y,z=y+1 ∧ le(x,y)}

Cette fonction est monotone (c’est-à-dire que ∀ le1 le2 ⊆ A × A, le1 ⊆ le2 ⇒ F(le1) ⊆ F(le2)) et admet donc un plus point fixe qui vérifie la propriété attendue.

Définition 19 (Continuité) Une application f d’un treillis A dans un treillis B est continue si elle préserve les bornes supérieures des ensembles non-vides, c’est-à-dire que si X⊆ A est non vide et si X admet une borne supérieure a alors l’ensemble f(X) (qui est non-vide) admet aussi une borne supérieure et celle-ci est égale à f(a).

Une fonction continue sur un treillis est monotone. En effet si x≤ y alors la borne supérieure de {x;y } est y et donc la borne supérieure de {f(x);f(y) } est f(y) et donc f(x)≤ f(y).

Pour n’importe quelle fonction monotone f sur un treillis complet on a ⊔(f(X)) ≤ f(⊔X) par contre le contraire n’est pas toujours vérifié.

Exemple 13 (Fonction non continue) Soit A l’ensemble des suites infinies de 0 et de 1 et F la fonction qui à la suite s associe le réel Σn=0∞ s[n]1/2n avec s[n] la n-ème valeur de la suite s. L’ensemble des réels muni de l’ordre total usuel est un treillis. Cette fonction est monotone si on considère l’ordre point à point sur les séquences. On considère maintenant l’ensemble des suites sn telles que sn[n]=1 et sn[k]=0 si k≠n. On a ⊔n sn est la suite qui vaut 1 partout et donc pour cette suite la valeur de F est 2 alors que pour chaque suite sn on a F(sn)=1/2n ≤ 1.

La continuité permet de caractériser le plus petit point-fixe.

Proposition 11 (Point fixe de fonction continue) Soit A un treillis complet et f une application continue de A dans A, alors le plus petit point fixe de f est égal à la borne supérieure de l’ensemble {fn(⊥)|n∈ℕ}.

Preuve: On note a la borne supérieure de F =def {fn(⊥)|n∈ℕ} et on montre que c’est un point fixe. On a ⊥ ≤ f(⊥) et donc par monotonicité fn(⊥) ≤ fn+1(⊥) On en déduit que la borne supérieure de F est égale à la borne supérieure de f(F)={fn+1(⊥)|n∈ℕ}. On a donc a=f(a).
On remarque que pour cette preuve, on a juste besoin de l’existence d’une borne supérieure pour un suite croissante d’objets. □

En informatique, on utilise souvent la construction de point fixe de fonction monotone sur des ensembles finis.

Proposition 12 (Point fixe dans un ensemble fini) Soit A un ensemble ordonné fini, qui admet un élément minimum ⊥ et f une application monotone de A dans A. La fonction f admet un plus petit point fixe qui est de la forme fk(⊥) avec k inférieur au cardinal de A.

Preuve: On regarde la suite croissante {fn(⊥)|n∈ℕ}, elle contient au plus un nombre d’éléments égal au cardinal de A et donc il existe k tel que fk+1(⊥)=fk(⊥) et donc fk(⊥) est un point fixe de f. □