IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /></figure>

DOMAINES CONCRETS

Gilles KAHN
Gordon PLOTKIN

Rapport de Recherche N° 336

Décembre 1978

143p.
## Domaines concrets

Gilles KAHN

IRIA/LABORIA

Gordon PLOTKIN

Université d'Edimbourg

### Résumé :

Dans ce rapport, on développe la théorie d'une variété particulière de domaines de calculs appelés **domaines concrets**. L'objet de cette théorie est de trouver un cadre convenable pour les notions de calcul en coroutine et d'évaluation séquentielle.

### Abstract :

This report introduces the theory of a particular kind of computation domains called **concrete domains**. The purpose of this theory is to find a satisfactory framework for the notions of coroutine computation and sequentiality of evaluation.
# Chapitre 0

## Rappels sur les concepts fondamentaux de la théorie des modèles des langages de programmation

Nous suivons l'approche générale de Scott [1]. A tout objet syntaxique peut être associé un objet sémantique, élément d'un domaine mathématique judicieusement choisi. Nous suivons pour les détails Milner [2] et Plotkin [3] plutôt que Scott.

**Définition A-D1** Un ordre partiel <D;≤> est composé d'un ensemble non-vide D et d'une relation d'ordre ≤ sur D, c'est-à-dire d'une relation binaire ≤ vérifiant

i) $\forall x \in D \quad x \leq x$ (réflexivité)

ii) $\forall x,y \in D \ x \leq y, y \leq x \Rightarrow x = y$ (antisymétrie)

iii) $\forall x,y,z \in D \ x \leq y, y \leq z \Rightarrow x \leq z$ (transitivité)

Nous écrirons $x < y$ lorsque on aura $x \leq y$ et $x \neq y$. Deux éléments x et y sont dits *comparables* lorsque l'on a ou bien $x \leq y$ ou bien $y \leq x$. Dans le cas contraire, les éléments x et y sont *incomparables* et cette relation est notée $x \parallel y$. Un ordre partiel dans lequel deux éléments quelconques sont comparables est une *chaîne*.

**Terminologie** : Soit <D;≤> un ordre partiel, H un sous-ensemble de D et x un élément de D. L'élément x est un *majorant* de H ssi

$$ \forall y \in H \quad y \leq x $$

un *minorant* de H ssi

$$ \forall y \in H \quad x \leq y $$

une *borne supérieure* de H ssi x est un majorant de H et

$$ \forall z \text{ majorant de H } x \leq z $$

une *borne inférieure* de H ssi x est un minorant de H et

$$ \forall z \text{ minorant de H } z \leq x. $$
Lorsque $x$ est une borne supérieure (resp. inférieure) de $H$ on écrit
$x = \bigcup H$ (resp. $x = \bigcap H$). Si $H = \{a,b\}$ ces notations sont abrégées en
$x = avb$ et $x = a \land b$ respectivement.

Deux éléments $x$ et $y$ de $D$ sont compatibles si $\{x,y\}$ possède un majorant. On note cette relation $x \uparrow y$ et $x \# y$ son complément, la relation d'incompatibilité.

Un élément $x$ de $H$ est dit **maximum** (resp. **minimum**) ssi

$$x = \bigcup H \quad (\text{resp. } x = \bigcap H)$$

**Définition A-D2** Dans un ordre partiel $<D; \le>$ un sous ensemble $X$ de $D$ est dirigé ssi $X$ est non vide et

$$\forall x_1, x_2 \in X \quad \exists x_3 \in X : x_1 \le x_3 \text{ et } x_2 \le x_3$$

**Remarque** : Par définition l'ensemble support de toute chaîne est $\alpha$ fortiori un ensemble dirigé.

**Définition A-D3** Un ordre partiel $<D; \le>$ est **complet** ssi

i) $D$ possède un élément minimum $\bot$

ii) Tout sous-ensemble dirigé $X$ de $D$ admet une borne supérieure.

**Définition A-D4** Un ordre partiel $<D; \le>$ est **complet sous-condition** ssi tout sous-ensemble $X$ de $D$ majoré admet une borne supérieure.

**Remarques** : i) Puisque $D$ est non vide l'ensemble vide $\emptyset$ est majoré. Donc, si $<D; \le>$ est complet sous condition, $D$ possède un élément minimum $\bot = \bigcup \emptyset$.

ii) la terminologie utilisée ici, quoique standard, n'est pas très heureuse puisqu'un ordre partiel peut être complet sans être complet sous-condition.
**Proposition A-P1** Un ordre partiel complet $<D; \le>$ est complet sous condition ssi toute paire d'éléments compatibles $<x,y>$ admet une borne supérieure xvy.

**Démonstration** : Soit $<D; \le>$ un ordre partiel complet dans lequel toute paire d'éléments compatibles admet une borne supérieure et X une partie de D. Si $X=\emptyset$ on a $\bigcup X = I$. Si X n'a qu'un élément x, celui-ci est la borne supérieure de X. Si X comporte deux éléments x et y et est majoré, alors x et y sont compatibles et $\bigcup X = xvy$.

Soit X un sous-ensemble fini majoré quelconque de D, $|X| \ge 2$, avec $X = X' \cup \{x\}$. Comme X est majoré, il en est de même de X' qui possède une borne supérieure $\bigcup X'$. Comme tout majorant de X domine $\bigcup X'$ et x, ces deux éléments sont compatibles et par suite $\bigcup X = \bigcup X' \cup x$. Si maintenant X est infini, soit Y l'ensemble des bornes supérieures des parties finies de X. Comme cet ensemble Y est dirigé, il admet une borne supérieure $\bigcup Y$. Pour tout élément x de X on a

$$x \le \bigcup Y$$

puisque $\{x\}$ est une partie finie majorée par $\bigcup Y$. Comme toute borne supérieure de X doit au moins dominer $\bigcup Y$ on en déduit

$$\bigcup X = \bigcup Y.$$

La réciproque est triviale. ☐

**Proposition A-P2** Dans un ordre partiel complet sous condition $<D; \le>$ tout sous-ensemble X non vide de D admet une borne inférieure $\bigcap X$.

**Démonstration** : Soit Y l'ensemble des minorants de tous les éléments de X :

$$y \in Y \iff \forall x \in X \ y \le x$$

Puisque X est non vide l'ensemble Y est majoré par un élément quelconque de X. Donc Y admet une borne supérieure $\bigcup Y$. Pour tout $x \in X$ on a

$$\forall y \in Y \ y \le x$$

donc aussi $\bigcup Y \le x$.

Donc $\bigcup Y$ est un minorant de X et $\bigcup Y = \bigcap X$. ☐
**Définition A-D5** Dans un ordre partiel $<D; \le>$ un sous ensemble X de D est consistant ssi deux éléments quelconques de X sont compatibles.

**Définition A-D6** Un ordre partiel $<D; \le>$ est cohérent ssi tout sous ensemble consistant X de D admet une borne supérieure.

**Remarques** : 1. Tout ensemble majoré est consistant. Donc si un ordre partiel est cohérent, il est à fortiori complet sous condition.

2. L'ensemble vide $\emptyset$ est consistant. Il admet donc une borne supérieure $\perp$. Tout ensemble dirigé est consistant. Donc un ordre partiel cohérent est a fortiori complet.

**Proposition A-P3** Un ordre partiel complet $<D; \le>$ est cohérent ssi tout triplet $<x,y,z>$ consistant admet une borne supérieure.

**Démonstration** : Si X a au plus 3 éléments, la propriété est évidente. Soit $X = \{x_1, x_2, \dots, x_n\}$ un sous ensemble fini et consistant de D avec $|X| = n > 3$. Supposons, par récurrence, que tout sous ensemble consistant Y dont la cardinalité vérifie $1 \le |Y| < n$ admet une borne supérieure. L'ensemble $\{x_1^{Vx_2}, x_2^{Vx_3}, \dots, x_{n-2}^{Vx_{n-1}}, x_n\}$ a au plus n-1 éléments. Deux éléments quelconques y sont compatibles puisque :

i) s'ils sont tous deux de la forme $x_i^{Vx_{i+1}}$ ils sont dominés par $\bigcup \{x_1, \dots, x_{n-1}\}$, qui existe par hypothèse de récurrence.

ii) $x_i^{Vx_{i+1}}$ et $x_n$ sont compatibles puisque le triplet $\{x_i, x_{i+1}, x_n\}$ admet une borne supérieure.

Par suite, en appliquant une deuxième fois l'hypothèse de récurrence, l'ensemble X possède une borne supérieure. Si maintenant X est infini, l'ensemble Y des bornes supérieures des parties finies de X est dirigé et l'on a $\bigcup X = \bigcup Y$. $\square$
**Définition A-D7.** Dans un ordre partiel $<D; \le>$ un élément $x$ de $D$ est isolé (compact) ssi de tout ensemble dirigé $X$ dont la borne supérieure existe et domine $x$, on peut extraire un élément $y$ qui domine $x$. En symboles :

$$ \forall X \subset D, X \text{ dirigé } x \le \bigcup X \Rightarrow \exists y \in X, x \le y $$

**Notation** L'ensemble des éléments isolés dominés par un élément $x$ sera noté $A(x)$. Un élément de $A(x)$ est aussi appelé un *approximant* de $x$. L'ensemble des éléments isolés de $<D; \le>$ sera noté $A(D)$.

**Remarque :** L'élément $x$ est isolé ssi $x \in A(x)$. Donc $A(D) = \bigcup_{x \in D} A(x)$.

**Proposition A-P4** Dans un ordre partiel complet sous condition $<D; \le>$

i) Si deux éléments isolés $a$ et $b$ sont compatibles, alors $avb$ est isolé.

ii) Pour tout élément $x$ l'ensemble $A(x)$ est dirigé.

**Démonstration :** i) Puisque $a$ et $b$ sont compatibles leur borne supérieure $avb$ existe. Soit $S$ un ensemble dirigé avec

$$ avb \le \bigcup S $$

Comme $a$ et $b$ sont isolés, de $a \le \bigcup S$ et $b \le \bigcup S$ on déduit l'existence de deux éléments $a'$ et $b'$ dans $S$ vérifiant

$$ a \le a' \text{ et } b \le b' $$

Comme $S$ est dirigé, il existe $c$ dans $S$ avec

$$ a' \le c \text{ et } b' \le c $$

d'où l'on déduit $a \le c$ et $b \le c$ donc $avb \le c$. Donc $avb$ est isolé.

ii) Si $a$ et $b$ sont deux approximants de $x$, l'élément $avb$ est isolé par i) et dominé par $x$, donc c'est aussi un approximant de $x$. Par suite $A(x)$ est dirigé. $\square$
**Définition A-D8** Un ordre partiel <D;≤> est algébrique ssi pour tout x dans D l'ensemble A(x) est dirigé et

$$x = \bigcup A(x)$$

Si de plus A(D) est dénombrable <D;≤> est dit séparable.

**Définition A-D9** Nous appellerons domaine de calcul un ordre partiel cohérent et séparable.

**Notation** Nous abandonnons dorénavant la notation précise <D;≤> pour un domaine de calcul. Nous utiliserons simplement la majuscule italique correspondant à l'ensemble sous-jacent, sauf si plus de précision est utile.

**Lemme A-L1** Dans un domaine de calcul

$$x \le y \iff A(x) \subset A(y)$$

**Démonstration** : De la gauche vers la droite l'implication est immédiate.

Réciproquement, puisque A(x) et A(y) sont dirigés ils admettent des bornes supérieures $\bigcup A(x)$ et $\bigcup A(y)$ avec

$$\bigcup A(x) \le \bigcup A(y)$$

et, par algébricité on en déduit

$$\bigcup A(x) = x \le y = \bigcup A(y) \quad \square$$

**Corollaire A-C1** Dans un domaine de calcul, si x est isolé et x < y on peut trouver un approximant z de y avec

$$x < z \le y$$

**Démonstration** : Soit t un élément quelconque de l'ensemble (non vide)

A(y) \ A(x). Comme x et t sont deux approximants de y il en est de même de xvt. Posant z = xvt, on a bien x < z ≤ y. □
**Corollaire A-C2** Si un élément y d'un domaine de calcul n'est pas isolé, on peut trouver une chaine infinie croissante de points isolés $\{1, x_1, x_2, \dots, x_n\dots\}$ avec $1 < x_1 < x_2 < x_3 \dots < x_n \dots < y$

**Démonstration** : Comme l'élément minimum 1 est isolé on a sûrement $1 < y$. Supposons que l'on dispose d'une chaine $\{1, x_1, x_2, \dots, x_{n-1}\}$ de n éléments isolés vérifiant $1 < x_1 < x_2 \dots < x_{n-1} < y$

Puisque $x_{n-1}$ est isolé, on peut certainement trouver, par le corollaire précédent un élément isolé $x_n$ avec

$$x_{n-1} < x_n \le y$$

Mais comme y n'est pas isolé on a aussi $x_n < y$ et l'on a étendu la chaine à n+1 éléments. □
**Proposition A-P5** Le produit cartésien d'un nombre fini ou dénombrable de domaines de calcul est un domaine de calcul.

**Démonstration** Soit $\alpha$ un ordinal avec $1 \le \alpha \le \omega$ et $\{<D_i; \le_i\}_{i<\alpha}$ une famille de domaines de calcul. Un élément $x$ de $D = \prod_{i<\alpha} D_i$ est un vecteur $<x_0, x_1, \dots, x_i, \dots>$. L'ensemble $D$ hérite de la relation d'ordre $\le$ définie composante par composante :

$$ \forall x, y \in D \ x \le y \iff \forall i < \alpha \ x_i \le y_i $$

Deux éléments $x$ et $y$ de $D$ sont compatibles ssi ils sont compatibles composante par composante : en effet si $x$ et $y$ sont compatibles, il existe $z$ avec $x \le z$ et $y \le z$ donc $\forall i, x_i \le z_i$ et $\forall i, y_i \le z_i$, donc $x$ et $y$ sont compatibles composante par composante. Réciproquement si $\forall i \exists z_i, x_i \le z_i, y_i \le z_i$, le vecteur $z = <z_0, \dots, z_i, \dots>$ domine $x$ et $y$ qui sont donc compatibles. On voit de même que, si $x \uparrow y$ on a $x \vee y = <x_0 \vee y_0, \dots, x_i \vee y_i, \dots>$. Un sous-ensemble de $X$ de $D$ est consistant ssi il est consistant composante par composante. Par suite si chaque ordre partiel $<D_i; \le_i>$ est cohérent, il en est de même de $<D; \le>$.

Montrons maintenant que $<D; \le>$ est séparable. Soit $I$ le sous-ensemble de $D$ défini par

$$ I = \bigcup_{i<\alpha} \{x_i \mid x_i \in A(D_i)\} \text{ et } \forall j<\alpha, j \neq i \ x_j = D_j \} $$

Les éléments de $I$ sont des vecteurs dont toutes les composantes ont des valeurs minimum dans leurs domaines respectifs, sauf peut-être la i-ème qui est un élément isolé de $D_i$. Un élément quelconque $x$ de $I$ est un élément isolé de $D$. Soit en effet $X$ une partie dirigée de $D$ avec $x \le \bigcup X$. Puisque la i-ème composante de $X$ est dirigée et puisque $x_i$ est isolé dans $D_i$, il existe $z_i$ dans $X_i$ avec

$$ x_i \le z_i $$
comme par ailleurs

$$ \forall j<a, j \neq i \quad x_j = \mathbb{1}_{D_j} \leq j \leq z_j $$

on a bien $x \leq z$.

Soit maintenant $x$ un élément quelconque de $D$. L'ensemble $Y_x$ défini par
$$ Y_x = \{y | y \in I, y \leq x\} $$
admet une borne supérieure $\bigcup Y_x$ puisqu'il est cohérent.
Bien entendu $\bigcup_{x \leq x} Y_x$ est fini. Mais, puisque chaque domaine $<D_i; \leq>_i>$ est algébrique, on a aussi :

$$ (\bigcup_{x_i} Y_x)_i = \bigcup_{(y_i | y \in Y_x)} A(x_i) \geq \bigcup A(x) = x $$

Donc $\bigcup_{x} Y_x = x$. Soit $Z_x$ l'ensemble dirigé obtenu en rajoutant à $Y_x$ les bornes supérieures de toutes ses parties finies. On a encore $\bigcup_{x} Z_x = x$.
Donc si $x$ est isolé, il existe un élément $z$ de $Z_x$ avec $x \leq z$. Mais comme $z$ est majoré par $x$, on en déduit $x = z$. Un élément de $D$ est donc isolé ssi il est la borne supérieure d'un nombre fini d'éléments de $I$. Donc $D$ ne contient qu'un nombre au plus dénombrable d'éléments isolés. Comme par ailleurs $Z_x$ est dirigé et $x = \bigcup_{x} Z_x$, le domaine $D$ est algébrique. Nous avons ainsi montré que $D$ est **cohérent** et **séparable**, c'est donc un domaine de calcul. $\square$

**Exemple** : Soit $T = \{\mathbb{1}, 0, 1\}; \leq \leq$ le domaine de calcul à trois éléments tel que $0 \leq 1$. Le produit cartésien d'un nombre dénombrable de copies de $T$ est le domaine de calcul $T^\omega$. Ce domaine est étudié en détail par Plotkin [3] qui montre que c'est un domaine **universel** en un sens précis.

<figure><img src="image_3.png" /></figure>

Le domaine $T$.

figure A-F1
**Définition A-D10** Soient $\langle D; \le \rangle$ et $\langle D'; \le' \rangle$ deux ordres partiels complets.

Une fonction $f$ de $D$ dans $D'$ est *continue ssi*

$$ (*) \quad \forall X \subset D, X \text{ dirigé } f(\bigcup X) = \bigcup' \{f(x) \mid x \in X\} $$

cette définition générale n'est pas très facile à utiliser. Dans un domaine
de calcul nous utiliserons la caractérisation suivante :

**Lemme A-L2** Soient $\langle D; \le \rangle$ et $\langle D'; \le' \rangle$ deux domaines de calcul. Une fonction $f$ de $D$ dans $D'$ est continue ssi

$$ (**) \quad \left\{ \begin{array}{ll} \text{i) } f \text{ est croissante, c'est-à-dire } \forall x,y \in D \ x \le y \Rightarrow f(x) \le f(y) \\ \text{ii) } \exists e \in A(f(x)) \exists d \in A(x) \text{ tel que } e \le f(d) \end{array} \right. $$

**Démonstration** : a) Montrons d'abord que (*) implique (**). Soit $f$ une fonction vérifiant (*) et $x$ et $y$ deux éléments de $D$ avec $x \le y$. L'ensemble $\{x,y\}$ est dirigé puisque $y = xVy$. On doit donc avoir

$$ f(y) = f(x) \lor f(y) $$

Par suite $f(x)$ et $f(y)$ sont comparables et $f(x) \le' f(y)$. La fonction $f$ est donc croissante. L'image d'un ensemble dirigé $X$ par une fonction croissante est un ensemble dirigé $f(X)$ et en particulier, puisque pour tout $x$ l'ensemble $A(x)$ est dirigé, l'ensemble $f(A(x))$ est dirigé. Soit alors $e$ un approximant quelconque de $f(x)$. On a

$$ e \le' f(x) = f(\bigcup A(x)) = \bigcup' f(A(x)) $$

Comme $e$ est isolé et $f(A(x))$ est dirigé, il existe donc $d$ dans $\tilde{A}(x)$, avec

$$ e \le f(d) $$

b) Montrons maintenant que (** implique (*). Soit $X$ un sous-ensemble dirigé de $D$ et $f$ une fonction de $D$ dans $D'$ vérifiant (**). Puisque $f$ est croissante, l'ensemble $f(X)$ est dirigé et on a

$$ \bigcup' f(X) \le' f(\bigcup X) $$
Pour prouver l'inégalité inverse $f(\bigcup X) \leq' \bigcup' f(X)$ considérons un approximant quelconque e de $f(\bigcup X)$. Par (**) on peut trouver d dans $A(\bigcup X)$ avec $e \leq' f(d)$. Comme d est isolé et X dirigé, de $d \leq \bigcup X$ on peut déduire l'existence d'un élément $x$ de $X$ avec $d \leq x$ et on a $f(x) \leq' \bigcup' f(X)$. Comme $f$ est croissante on a aussi $f(d) \leq' f(x)$ donc

$$ \forall e \in A(f(\bigcup X)) \quad e \leq' \bigcup' f(X) $$

et par suite $A(f(\bigcup X)) \subset A(\bigcup' f(X))$. Le lemme II.4.1 permet de conclure

$$ f(\bigcup X) \leq' \bigcup' f(X) $$

et ainsi $f(\bigcup X) = \bigcup' f(X)$ □

**Proposition A-P6** Soient les domaines de calcul $D_1, D_2$ et $D$. Une fonction $f$ de $D_1 \times D_2$ dans $D$ est continue ssi les fonctions $f_1 = \lambda y.f(x_1,y)$ et $f_2 = \lambda y.f(y,x_2)$ sont continues pour tout $x_1$ dans $D_1$ et $x_2$ dans $D_2$.

**Démonstration:** Si $f$ est continue alors les fonctions $f_1$ et $f_2$ le sont aussi, quels que soient $x_1$ et $x_2$. Montrons-le par exemple pour la famille de fonctions $f_1$. Soit $S_1$ un ensemble dirigé de $D_2$ et $S$ le sous-ensemble dirigé de $D_1 \times D_2$ défini par

$$ S = \{ \langle x_1, y \rangle \mid y \in S_1 \}. $$

$$ f_1(\bigcup S_1) = f(x_1, \bigcup S_1) = f(\bigcup S) = \bigcup f(S) = \bigcup f(x_1, S_1) = \bigcup f_1(S) $$

Supposons réciproquement les familles de fonctions $f_1$ et $f_2$ continues. La fonction $f$ est alors croissante. En effet si l'on a $\langle x_1, y_1 \rangle \leq \langle x_2, y_2 \rangle$ on peut écrire $f(x_1, y_1) \leq f(x_2, y_1) \leq f(x_2, y_2)$. Soit maintenant $\tilde{S}$ un sous-ensemble dirigé de $D_1 \times D_2$ et $S_1$ et $S_2$ ses projections sur $D_1$ et $D_2$. Posons $T = \{ \langle x, y \rangle \mid x \in S_1, y \in S_2 \}$. Par la continuité des familles $f_1$ et $f_2$ on obtient :

$$ f(\bigcup S) = f(\bigcup S_1, \bigcup S_2) = \bigcup' f(S_1, \bigcup S_2) = \bigcup f(S_1, S_2) = \bigcup f(T) $$

Comme $S$ est dirigé et $f$ croissante r, s savons que $f(S)$ est dirigé. Comme de plus $S$ est inclus dans $T$, on a forcément $\bigcup f(S) \leq \bigcup f(T)$. Soit maintenant
<x,y> un élément quelconque de T. Il existe certainement deux éléments <x,y₁> et <x₁,y> dans S puisque S₁ et S₂ sont les projections de S. Comme S est dirigé, il existe <x₂,y₂> dans S qui domine ces deux éléments et donc <x,y> ≤ <x₂,y₂>. Comme f est croissante on a donc aussi

$$ \bigcup f(T) \leq \bigcup f(S) $$

On en conclut $f(\bigcup S) = \bigcup f(T) = \bigcup f(S)$ donc f est continue. □

Le résultat ci-dessus se généralise de façon triviale aux fonctions de plus de deux arguments.

Dans un domaine de calcul D, deux éléments quelconques x et y ont toujours une borne inférieure x^y (proposition A-L2) et l'on peut définir une fonction ^ de D² dans D par ^ = λxy.x^y.

**Proposition A-P7** Si D est un domaine de calcul, la fonction ^ est une fonction continue de D² dans D.

**Démonstration.** D'après, le résultat précédent il nous suffit de démontrer que les fonctions $^1 = λy.x^y$ et $^2 = λy.y^x$ sont continues. Puisque ^ est commutative, il suffit donc de montrer que pour tout x, la fonction $^1$ est continue. Nous utilisons la caractérisation du lemme A-L2.

i) $^1$ est croissante : $y_1 \leq y_2 \Rightarrow x^y_1 \leq x^y_2$

ii) Soit e un approximant de x^y. L'élément e est un approximant de x et de y, et l'on a :

$$ e \in A(y) \text{ et } e \leq x^e = ^1(e). \quad \square $$

**Théorème A-T1** (Knaster-Tarski) Si D est un domaine de calcul, toute fonction continue f de D dans D admet un plus petit point fixe Yf qui vérifie

$$ Yf = \bigcup \{f^n(\emptyset) \mid n \geq 0\} $$
**Démonstration** : Posons $S = \{f^n(\perp) \mid n \ge 0\}$. L'ensemble S est non vide puisqu'il contient $\perp = f^0(\perp)$. Comme f est croissante, il est trivial de montrer par récurrence que

$$ \forall n \ge 0, f^n(\perp) \le f^{n+1}(\perp) $$

donc S est une chaine. Par suite S admet une borne supérieure $\cup S$.

Posons $Yf = \cup S$. Par continuité de f, puisque une chaine est un ensemble dirigé :

$$ f(Yf) = f(\cup S) = \cup f(S) = \cup \{f^n(\perp) \mid n \ge 1\} $$

Mais puisque $\perp$ est l'élément minimum de D

$$ \cup \{f^n(\perp) \mid n \ge 1\} = \cup \{f^n(\perp) \mid n \ge 1\} \cup \{\perp\} = \cup S = Yf $$

Donc $Yf = f(Yf)$ ce qui montre que Yf est un point fixe de f. Soit maintenant $x$ un point fixe quelconque de f. On a

$$ f^0(\perp) = \perp \le x $$

et si $f^n(\perp) \le x$, comme f est croissante on obtient

$$ f^{n+1}(\perp) = f(f^n(\perp)) \le f(x) = x $$

Par conséquent S est majoré par $x$ et il en est de même pour sa borne supérieure $Yf$. Donc $Yf$ est le plus petit point fixe de f. $\square$

**Notation** Si $D$ et $E$ sont des domaines de calcul, nous noterons $[D \to E]$ l'ensemble des fonctions continues de $D$ dans $E$. Cet espace hérite d'une relation d'ordre définie par extensionnalité :

$$ \forall f,g \in [D \to E] \quad f \le g \iff \forall x \in D \quad f(x) \le g(x) \quad \underset{E}{\frown} $$

La fonction constante $\lambda x. \perp_E$ est l'élément minimum de $[D \to E]$. Le résultat suivant est fondamental.

**Théorème A-T2** Si $D$ et $E$ sont des domaines de calcul, l'ensemble $[D \to E]$ muni de son ordre naturel est un domaine de calcul.

**Démonstration** : a) Soit $F$ un sous ensemble consistant de $[D \to E]$. Pour tout $x$ dans $D$ l'ensemble $\{f(x) \mid f \in F\}$ est consistant et admet donc une borne supérieure $g_x$. Montrons que la fonction $\lambda x. g_x$ est continue. Soient $X$ un
sous ensemble dirigé de D et z sa borne supérieure

$$g_z = \bigcup_E \{f(z) \mid f \in F\}$$

Puisque toutes les fonctions de $\mathcal{F}$ sont continues

$$g_z = \bigcup_E \{f(x) \mid x \in X, f \in F\} \\ = \bigcup_E \{g_x \mid x \in X\}$$

Par suite $\lambda x.g_x$ est la borne supérieure de $F$ dans $[D \to E]$. Donc $[D \to E]$ est **cohérent**.

b) Montrons maintenant que $[D \to E]$ est séparable. Considérons la famille de fonctions indexée sur $\mathcal{A}(D) \times \mathcal{A}(E)$ définie par

$$\phi(x) = \begin{cases} e & \text{si } d \le x \\ \mathbb{1}_E & \text{sinon} \end{cases} \quad (d \in \mathcal{A}(D), e \in \mathcal{A}(E))$$

1. Les fonctions de cette famille, dites *fonctions étage*, sont continues.

En effet : i) $\phi_{d,e}$ est croissante (immédiat)

ii) Soit $a$ un approximant quelconque de $\phi_{d,e}(x)$.

Si $\phi_{d,e}(x) = \mathbb{1}_E$, alors on a

$$a = \mathbb{1}_E \le \phi_{d,e}(\mathbb{1}_D) \quad \text{avec } \mathbb{1}_D \in \mathcal{A}(x)$$

Si $\phi_{d,e}(x) = e$, c'est que $d \le x$ donc $d \in \mathcal{A}(x)$ puisque $d$ est isolé. Mais alors

$$a \le \phi_{d,e}(d) = e \quad \text{avec } d \in \mathcal{A}(x)$$

2. Les fonctions étages sont des éléments isolés de $[D \to E]$

Soit $F$ une partie dirigée de $[D \to E]$ telle que

$$\phi_{d,e} \le \bigcup F$$

Le résultat de la partie a) permet d'écrire :

$$e = \phi_{d,e}(d) \le (\bigcup F)(d) = \bigcup \{f(d) \mid f \in F\}$$
Mais $e$ est isolé et $\{f(d) | f \in F\}$ est dirigé. Donc il existe une fonction $g$ dans $F$ avec

$$e = \phi_{d,e}(d) \leq g(d)$$

Mais alors, si $d \leq x$ on a $\phi_{d,e}(x) = e \leq g(d) \leq g(x)$

$$\text{sinon } \phi_{d,e}(x) = \mathbb{1}_E \leq g(x)$$

$$\text{donc } \phi_{d,e} \leq g$$

**3. Toute fonction $f$ de $[D \to E]$ est la borne supérieure des fonctions étages qu'elle domine.**

Posons $S(f) = \{\phi_{d,e} | \phi_{d,e} \leq f\}$. Remarquons que $\phi_{d,e} \in S(f) \iff e \in A(f(d))$.
En effet, l'implication de la gauche vers la droite découle immédiatement de $\phi_{d,e}(d) = e$ et celle de la droite vers la gauche de la monotonicité de $f$.
Par suite, en utilisant maintenant la continuité de $f$ :

$$\forall x : f(x) = f(\bigcup A(x)) = \bigcup_{d \in A(x)} f(d) = \bigcup_{d \in A(x), e \in A(f(d))} e = \bigcup_{d \in A(x), e \in A(f(d))} \phi_{d,e}(x) = \bigcup_{e \in A(f(d))} \phi_{d,e}(x)$$

$$\text{Soit } \forall x \quad f(x) = (\bigcup S(f))(x) \text{ donc } f = \bigcup S(f)$$

**4. Les éléments isolés de $[D \to E]$ sont exactement les unions d'un nombre fini de fonctions étages.**

Soit en effet $f$ un élément isolé de $[D \to E]$ et $S'(f)$ l'ensemble obtenu en fermant $S(f)$ par union finie. L'ensemble $S'(f)$ est dirigé et l'on a bien sûr $f = \bigcup S(f) = \bigcup S'(f)$.

Comme $f$ est isolée, il existe sûrement dans $S'(f)$ un élément $g$ avec $f \leq g$. Mais comme $g$ est l'union d'éléments de $S(f)$ on a aussi $g \leq f$. Donc $f = g$ et $f$ est bien une union finie de fonctions étages.

**5. $[D \to E]$ est séparable. Pour tout $f$ on a**

$$f = \bigcup S(f) = \bigcup S'(f)$$
Donc $[D \to E]$ est algébrique. Comme $D$ et $E$ n'ont qu'un nombre au plus dénombrable d'éléments isolés, il n'existe qu'un nombre dénombrable de fonctions étages et par suite d'éléments isolés dans $[D \to E]$. Nous avons ainsi démontré que, lorsque $D$ et $E$ sont des domaines de calcul, l'espace $[D \to E]$ est cohérent et séparable, donc aussi un domaine de calcul. []

Le théorème ci-dessus permet, à partir de domaines de calculs et de construire toute une hiérarchie de domaines de calcul, par exemple $[D \to E]$, $[D \to [D \to E]]$, $[[D \to E] \to [D \to E]]$ etc...
# CHAPITRE I

## Domaines de Calcul concrets :

### l'approche d'une notion de calcul par la théorie des modèles

Dans ce chapitre, nous essayons de traduire sous une forme mathématique un certain nombre d'idées que nous avons développées au cours de recherches antérieures. Il est difficile de se rendre compte de ce qui est essentiel au bon fonctionnement d'un mécanisme complexe. En revanche, nous sommes plus exercés à découvrir les conditions générales de validité d'un résultat mathématique.⁺

Le résultat central de ce chapitre est le Théorème de Représentation qui, en un sens, indique que nous avons réussi dans notre entreprise. Partant de la notion générale de domaine de calcul, nous justifierons progressivement la nécessité de la restreindre jusqu'à obtenir le concept de domaine de calcul concret, dont nous étudierons les propriétés.

### I.1. Motivations initiales

Dans la théorie des modèles des langages de programmation, telle qu'elle a été développée à partir des travaux initiaux de Scott [1,4], aucune distinction n'est faite entre données et fonctions. Une structure unique, le domaine de calcul, est définie et tous les objets sur lesquels on est amené à calculer sont choisis dans des domaines de calcul appropriés. Il n'y a là rien d'étonnant puisque l'objectif principal de la théorie, au moins à l'origine, était de développer un modèle fonctionnel du λ-calcul de Church, langage où ces distinctions n'existent pas. D'ailleurs certains langages de programmation comme ISWIM[5], GEDANKEN[6], ML[7] etc... présentent des caractéristiques semblables. Cependant la plupart des langages de programmation font une distinction très nette entre données et procédures. Cette distinction peut-être être retrouvée dans les modèles

<footnote>⁺ Une approche semblable est suivie par J.J. Lévy dans sa thèse [8]</footnote>
des langages de programmation, c.à.d. lorsque l'on étudie leur sémantique dénotationnelle ? Est-il possible d'analyser plus finement la structure des domaines de calcul, de manière à départager, par exemple, ceux dont la structure est suffisamment simple pour qu'il ne soit pas nécessaire de les considérer comme des espaces fonctionnels ?

**Exemples** : Nous appelerons L le domaine de calcul à un seul élément, O le domaine de calcul à deux éléments, $T = \{\underline{1},0,1\};\underline{\leq}\}$ le domaine dans lequel O et 1 sont incomparables. Ces trois espaces, ainsi que leurs produits cartésiens en nombre fini quelconque sont clairement des espaces de données plutôt que des espaces fonctionnels.

Les exemples ci-dessus pourraient amener le lecteur à proposer simplement de partitionner les domaines de calcul en deux classes, suivant qu'ils sont finis ou infinis. Une telle classification est à l'évidence trop grossière pour deux raisons :

i) Il nous sera impossible de donner une représentation en tant que structure de donnée pour certains domaines finis

ii) En revanche certains domaines infinis sont clairement à ran- ger parmi les espaces de données. Par exemple, il en sera ainsi pour $N_\downarrow$ et $\bar{N}$ définis, à partir de l'ensemble N des entiers naturels, par :
$$N_\downarrow = \left\{ \langle \underline{1} \rangle \cup N; \underline{\leq} \right\} \text{ avec } \forall x, y \in N \ x \neq y \Rightarrow x \not\leq y$$
$$\bar{N} = \left\{ \langle N \cup \{\infty\} \rangle, \underline{\leq} \right\} \text{ si } \underline{\leq} \text{ est l'ordre naturel sur N complété par } \forall x \in N, x < \infty$$

Nous allons essayer de caractériser de façon axiomatique une certaine classe de domaines de calcul. Dans cette recherche, deux principes fondamentaux nous guideront :

1. [M.Smyth]. Tous les axiomes que nous postulerons spécifieront une propriété de l'ensemble des éléments isolés d'un domaine de calcul. Les autres éléments sont en effet construits à partir de ceux-ci par un mécanisme de passage à la limite, et leurs propriétés seront donc déduites des propriétés des éléments isolés.

2. La classe de domaines de calcul que nous cherchons à définir doit être fermée par certaines constructions élémentaires, par exemple par produit cartésien fini ou infini, ou passage aux sections supérieures (cf §1.2)
Cependant, il ne sera pas nécessaire qu'elle soit fermée par exponentiation c.à.d. par passage à l'ensemble des fonctions d'un domaine de calcul dans un autre domaine de calcul.

## I.2. L'axiome des éléments isolés

Les éléments isolés d'un domaine de calcul sont supposés représenter des quantités *finies* d'information. Lorsqu'il s'agit de données, nous voulions pouvoir, comme dans les chapitres précédents, raisonner par récurrence structurelle pour prouver des propriétés de ces éléments. Ceci impose que l'ensemble des éléments isolés soit *bien fondé* par rapport à la relation : c.à.d. qu'il ne contienne pas de suite infinie {$x_1, x_2, \dots, x_n, \dots$} avec $x_1 > x_2 > \dots > x_n > \dots$.

Un élément isolé ne peut alors être décomposé de façon infinie. Mais nous voulons aussi traduire l'idée intuitive qu'un élément isolé ne peut être composé qu'à partir d'un nombre fini de ses composantes. Nous sommes alors amenés à considérer la propriété I :

### Propriété I

Entre deux éléments isolés comparables distincts, toute chaîne de points isolés est finie.

**Proposition P2.1** Soit $D = \langle D; \le \rangle$ un domaine de calcul ayant la propriété I. Soient $x$ un élément quelconque de $D$ et $y$ un élément isolé de $D$. Si $x$ est dominé par $y$, alors $x$ est isolé.

**Démonstration** : Si $x$ n'est pas isolé, d'après le corollaire A-C2, on peut trouver une chaîne infinie d'éléments isolés {$1, x_1, x_2, \dots, x_n, \dots$} avec $1 < x_1 < x_2 < \dots < x_n < \dots < x$.

Si $y$ est isolé et $x \le y$, on a nécessairement $x < y$. Par suite la chaîne {$1, x_1, \dots, x_n, \dots$} est une chaîne infinie croissante d'éléments isolés entre $1$ et $y$. L'existence de cette chaîne contredit la propriété I donc $x$ est nécessairement isolé. □
**Corollaire C-2.1** Dans un domaine de calcul, la propriété I est équivalente à la propriété $I_1$ :

**Propriété I** : Entre deux éléments isolés comparables distincts, toute chaine est finie.

**Démonstration** : La propriété $I_1$ implique trivialment la propriété I. Réciproquement si l'on a $x \le y$ avec x et y isolés, par la proposition précédente tout élément z vérifiant $x \le z \le y$ est isolé. Toute chaine entre x et y n'est composée que d'éléments isolés et est donc finie. []

**Définition D-2.1** Dans un ordre partiel complet sous-condition $<D; \le>$ on appelle *idéal* un sous ensemble J non vide de D vérifiant :

i) $\forall x \in J, \forall y \in D \quad y \le x \Rightarrow y \in J$
(c.à.d. J est "fermé vers le bas")

ii) $\forall x, y \in J \quad x \le y \Rightarrow x \vee y \in J$

**Corollaire C-2.2** Dans un domaine de calcul, la propriété I est équivalente à la propriété $I_2$ :

**Propriété I** : L'ensemble des éléments isolés est un idéal bien fondé.

**Démonstration** : Lorsqu'un domaine de calcul D vérifie la propriété I, l'ensemble de ses éléments isolés est un idéal en vertu des propositions P-2.1 et A-P4. Puisque la propriété I implique la propriété $I_1$, il n'y a pas de suite infinie décroissante dans $A(D)$. Donc la propriété I implique la propriété $I_2$.

Réciproquement, supposons que D vérifie la propriété $I_2$. Entre deux éléments isolés x et y comparables distincts avec $x<y$, il n'y a pas de suite infinie décroissante puisque $A(D)$ est bien fondé. S'il y avait dans $A(D)$ une suite infinie croissante

$$ \{x, z_1, z_2, \dots, z_n, \dots, y\} \text{ avec } x < z_1 < z_2 < \dots < z_n < \dots < y $$
on aurait $\bigcup_{i=1}^{n} z_i = z \le y.$
et comme z n'est pas isolé, z<y, ce qui contredit l'hypothèse que $A(D)$ est un idéal. Soit alors $C$ une chaine entre $x$ et $y$. Comme $C$ ne contient pas de suite infinie décroissante, la chaine $C$ est un ordinal. Si $C$ est infinie, alors $C$ contient le plus petit ordinal infini $w$. Or $w$ contient une suite infinie croissante, ce qui n'est pas le cas pour $C$. Donc $C$ est une chaine finie.

La propriété $I_2$ implique donc aussi la propriété I.

**Exemples** : Le domaine $D_1 = \langle \mathbb{N} \cup \{\infty, T\}; \le \rangle$ avec l'ordre naturel sur $N$ et $\forall x \in N$, $x < \infty$ et $\infty < T$ ne vérifie pas la propriété $I_2$ parce que $A(D_1)$ n'est pas un idéal. Le domaine $D_2 = \langle \mathbb{Z} \cup \{-\infty, +\infty\}; \le \rangle$ avec l'ordre naturel sur $\mathbb{Z}$ et $\forall x \in \mathbb{Z}$, $-\infty < x < +\infty$ ne vérifie pas $I_2$ parce que $A(D_2)$ n'est pas bien fondé. En revanche tous les domaines finis, de même que les domaines $N_1$ et $\overline{N}$ posèdent la propriété I.

**Définition 2-2.2** Soient $<D; \le>$ un ordre partiel et $x$ et $y$ deux éléments de $D$. On dit que $y$ couvre $x$ ssi

i) $x<y$

ii) $\forall z \ x \le z \le y \Rightarrow x=z \text{ ou } y=z$

De façon synonyme on dira aussi que $y$ se trouve *juste au dessus* de $x$. Cette relation est notée $x<y$. Sa *fermeture réflexive* est notée $x=y$.

**Proposition 2-2.2** Soit $<D; \le>$ un domaine de calcul ayant la propriété I.

Si $x$ et $y$ sont des éléments isolés de $D$ on a $x \le y$ ssi

$$ \begin{cases} \text{ou bien } x=y \\ \text{ou bien il existe une suite finie } \{z_n, z_{n+1}, \dots, z_r\} \text{ d'éléments de } A(D) \\ \text{avec } z_0 = x, z_n = y \text{ et } z_i < z_{i+1} \text{ pour } i \le n. \end{cases} $$
**Démonstration** : Tout d'abord, si une telle suite existe, il est trivial par transitivité que l'on a $x \le y$. Supposons donc réciproquement $x < y$. Soit $H$ l'ensemble des chaines d'éléments de $A(D)$ dont $x$ est l'élément minimum et $y$ l'élément maximum. L'ensemble $H$ est non vide puisqu'il contient en particulier la chaine $\{x,y\}$ et on peut l'ordonner par inclusion. Dans l'ordre partiel $<H;c>$ il ne peut exister de chaine infinie croissante puisque $<D;\le>$ a la propriété I. Soit $C = \{z_0, z_1, \dots, z_n\}$, un élément maximal quelconque de $<H;c>$ on dira que $C$ est une *chaine maximale* entre $x$ et $y$. Sans perdre de généralité, on peut supposer $z_0 < z_1 < \dots < z_{n-1} < z_n$. Mais alors on a $z_i < z_{i+1}$, $\forall i \le n$, car autrement on pourrait étendre $C$ avec un élément isolé $z$ tel que $z_i < z < z_{i+1}$, ce qui contredirait l'hypothèse de maximalité de $C$ dans $<H;c>$. De même, on a nécessairement $x = z_0$ et $y = z_n$. $\square$

Il nous sera utile dans la suite., de représenter des configurations d'éléments pris dans un ordre partiel ou des ordres partiels par des graphes, dits *diagrammes de Hasse*. Les noeuds du diagramme associé à $<D;\le>$ représentent les éléments de $D$ et deux noeuds $a$ et $b$ sont reliés par une arête dirigée de bas en haut ssi $a \prec b$ dans $D$. Des conventions simples seront suivies pour représenter des domaines infinis. A titre d'exemple, sur les figures F.2.1 et F.2.2 sont représentés quelques ordres partiels que nous avons déjà mentionnés.

<figure><img src="image_4.png" /><figcaption>figure F.2.2.</figcaption></figure>
Avant de poursuivre l'étude des domaines de calculs ayant la
propriété I, il est bon d'observer que seuls les espaces fonctionnels
triviaux possèdent cette propriété.

**Lemme L-2.1.** Si D et E sont des domaines de calcul, si D est infini et E possède au moins deux éléments, alors [D→E] n'a pas la propriété I.

**Démonstration :** Remarquons d'abord que si D possède une infinité d'éléments, il possède une infinité d'éléments isolés en vertu du corollaire A-C2. De même si E possède au moins deux éléments, on peut trouver un élément isolé e dans E avec $\angle_E e \neq \emptyset$. Considérons maintenant l'ordre partiel infini $<A(D); \angle_D>$. Le lemme de Koenig nous permet d'affirmer que deux cas seulement sont possibles :

a) Ou bien il existe une chaine infinie croissante d'éléments de $A(D)$

b) Ou bien il existe un élément d dans $A(D)$ et un ensemble infini
$\{d_i\}_{i \in N}$ d'éléments de $A(D)$ tels que

$$
\begin{cases}
\forall i \in N \quad d < d_i \\
\forall i,j \in N \quad d_i \le d_j \quad \text{si } i \neq j
\end{cases}
$$

Cas a. Soit {$d_1, d_2, \cdots, d_n, \cdots$} une chaine infinie croissante dans A(D),
c.à.d. vérifiant

$$
d_1 < d_2 < d_3 < \cdots < d_n < \cdots
$$

Considérons la suite de fonctions étages $\phi_{d_i,e}$.

Cette suite infinie d'éléments isolés de $[D \to E]$ est décroissante

$$
\phi_{d_1,e} > \phi_{d_2,e} > \phi_{d_3,e} > \cdots > \phi_{d_n,e} > \cdots
$$

donc $A([D \to E])$ n'est pas bien fondé, et par suite $[D \to E]$ n'a pas la propriété $I_2$

**Cas b.** Dans ce cas on a

$$
\forall i \in N \quad \phi_{d_i, e} < \phi_{d, e} \quad \text{puisque} \quad d < d_i.
$$

L'ensemble $\Phi$ de fonctions $\{\phi_{d_i,e}\}_{i \in N}$ est donc majoré. Il admet une borne supérieure $\Phi$ puisque $[D \to E]$ est un domaine de calcul.
Bien entendu on a $\phi \le \phi_{d,e}$. Mais comme

$$ \forall i \in N \quad \phi_{d_i,e}^{(d)} = \mathbb{1}_E $$

on a nécessairement

$$ \phi^{(d)} = \mathbb{1}_E $$

Or $\phi_{d,e}^{(d)} = e \neq \mathbb{1}_E$ donc $\phi < \phi_{d,e}$. Il nous suffit de montrer maintenant que $\phi$ n'est pas un élément isolé de $[D \to E]$. Si $\phi$ était isolé, il existerait un sous ensemble fini $J$ de $N$ tel que

$$ \phi = \bigcup_{j \in J} \phi_{d_j,e} $$

Soit $k$ un entier non dans $J$. Puisque $\phi_{d_k,e}^{(d_k)} = e$ et $\phi_{d_k,e} \le \phi$ on a $e \le \phi(d_k)$. Mais par hypothèse

$$ \forall j \in J \quad d_j \parallel d_k $$

donc $\phi_{d_j,e}^{(d_k)} = \mathbb{1}_E$ donc il faut aussi avoir $\phi(d_k) = \mathbb{1}_E$.

Puisque $e$ est différent de $\mathbb{1}_E$, la fonction $\phi$ ne peut être isolée dans $[D \to E]$. Donc $A([D \to E])$ n'est pas un idéal, dans ce cas.

Puisque seuls les cas a) et b) sont possibles, la conclusion du lemme s'ensuit. []

**Remarque** : Le lemme ci-dessus départage avec précision des domaines en apparence très voisins. Par exemple, le domaine $[N_\perp \to O]$ n'a pas la propriété I. En revanche $O^\omega$, le produit cartésien d'un nombre dénombrable de copies de $O$, possède bien cette propriété. Mais $O^\omega$ n'est isomorphe qu'à l'ensemble des fonctions strictes de $[N_\perp \to O]$, c.à.d. des fonctions $f$ telles que $f(\perp) = \perp_0$. Très précisément l'unique fonction non-stricte $\lambda x \cdot \tau$ est un élément isolé de $[N_\perp \to O]$ qui ne correspond à aucun élément de $O^\omega$. Or cette fonction domine la fonction stricte $\psi$ définie par :

$$ \psi(x) = \begin{cases} \tau & \text{si } x \neq \perp \\ \perp & \text{si } x = \perp \end{cases} $$

qui n'est pas isolée dans $[N_\perp \to O]$.
**Définition D-2.3.** Soit $D = \langle D; \le \rangle$ un ordre partiel possédant un élément minimum $\bot$. On appelle *atome* tout élément de $D$ qui couvre $\bot$ et l'on dira que $D$ est *atomique* ssi tout élément de $D$ distinct de $\bot$ domine un atome. En symboles :

$$ \forall x \neq \bot \exists y \ \bot \prec y \leq x $$

**Proposition P-2.3.** Un domaine de calcul $D$ vérifiant la propriété I est atomique.

**Démonstration :** Soit d'abord $x$ un élément isolé de $D$ distinct de $\bot$. D'après la proposition P-2.2. il existe une suite finie $\{z_0, z_1, \dots, z_n\}$ d'éléments de $A(D)$ avec $\bot = z_0 \prec z_1 \prec \dots \prec z_n = x$. Donc $z_1$ est un atome et l'on a bien

$$ \bot \prec z_1 \leq x $$

Si maintenant $x$ n'est pas isolé, soit e un élément quelconque de $A(x)$ distinct de $\bot$. Un tel élément doit exister sinon on aurait $A(x) = \{\bot\} = A(\bot)$ et par le lemme A-L1 $x=\bot$. Nous venons de montrer qu'il existe y avec

$$ \bot \prec y \leq e $$

Par transitivité on a donc $\bot \prec y \leq x$. $\square$

La propriété I et la propriété corollaire d'atomicité sont des propriétés intéressantes d'un domaine de calcul et elles semblent bien représenter une certaine intuition des domaines de données. Nous allons voir cependant que ces deux propriétés ne sont pas conservées par une opération fondamentale sur les domaines de calcul.

**Définition D-2.4 :** Soit $\langle D; \le \rangle$ un ordre partiel et $x$ et $y$ deux éléments quelconques de $D$ avec $x \le y$. On appelle *intervalle* $[x,y]$ l'ensemble $\{z \mid x \le z \le y\}$ et *section supérieure* de $x$, notée $[x)$ l'ensemble $\{z \mid x \le z\}$. Bien entendu, intervalles et sections supérieures héritent de l'ordre partiel $\le$. $^+$

**Proposition P-2.4** Dans un domaine de calcul, tout intervalle et toute section supérieure est un domaine de calcul.

<footnote>+ Par abus de notation, nous noterons aussi $[x,y]$ et $[x)$ les ordres partiels ainsi définis.</footnote>
**Démonstration** : Les raisonnements étant identiques dans les deux cas, contentons nous de démontrer ce résultat pour les sections supérieures. Soit donc [x) une section supérieure quelconque d'un domaine de calcul <D; ≤>. Toute partie consistante non vide de [x) est une partie consistante de D et admet donc une borne supérieure dans D.

Cette borne supérieure se trouve forcément dans [x). De plus, comme x est l'élément minimum de [x), l'ensemble vide admet aussi une borne supérieure dans [x). Donc <[x); ≤> est un ordre partiel cohérent. Montrons maintenant que <[x); ≤> est séparable. Soit {d_i}_{i∈I} une énumération de A(D). Pour tout i dans I définissons

$$c_i = \begin{cases} x \vdash d_i & \text{si } x \uparrow d_i \\ x & \text{sinon} \end{cases} \quad \forall i \in I$$

Bien entendu, chaque élément $c_i$ ainsi défini appartient à [x) et nous allons montrer d'abord que {$c_i$}$_{i \in I}$ = A([x)).

Tout d'abord x est l'élément minimum de [x) et est donc isolé dans <[x); ≤>. Considérons maintenant un élément $c_i$ distinct de x. Soit X une partie dirigée de [x) avec

$$c_i \subseteq \bigcup X$$

Comme $c_i = x \vdash d_i$ on a aussi $d_i \subseteq \bigcup X$. Comme $d_i$ est isolé dans D, dont X est une partie dirigée, on a

$$d_i \subseteq y \text{ avec } y \in X$$

Comme y se trouve dans [x), donc domine x, on a

$$c_i = x \vdash d_i \leq x \vee y = y$$

ce qui montre que $c_i$ est isolé. On a donc {$c_i$}$_{i \in I}$ ⊂ A([x)). Soit maintenant y un élément quelconque de [x).

Comme D est algébrique on a

$$y = \bigcup \{d_i \mid i \in I, d_i \subseteq y\}$$

Comme y domine x on a aussi

$$y \vee x = y = \bigcup \{d_i \vee x \mid i \in I, d_i \subseteq y\}$$

Comme $d_i \subseteq y$ ssi $d_i \vee x \subseteq y$

$$y = \bigcup \{c_i \mid i \in I, c_i \subseteq y\}$$
L'égalité ci-dessus montre que $< [x]; \le >$ est algébrique. De plus l'ensemble $\{c_i | i \in I, c_i \le y\}$ est dirigé donc si y est isolé dans $< [x]; \le >$ on a, pour certain j dans I

$$y = c_j.$$

Donc $A([x]) = \{c_i\}_{i \in I}$ et par suite l'ensemble $A([x])$ est dénombrable.

L'ordre partiel $< [x]; \le >$ est donc cohérent et séparable, c'est un domaine de calcul. ☐

Le contre-exemple de la figure F-2.3.à montre que si un domaine de calcul possède la propriété I, il n'en est pas nécessairement de même de ses sections supérieures. Dans ce domaine, on a d'une part une chaîne $\{ \bot, x_1, \dots, x_n, \dots \}$ avec

$$\bot < x_1 < x_2 < x_3 < \dots < x_n < \dots$$

dont la limite est l'élément x. D'autre part l'atome $a_i$ est supposé compatible avec x et incomparable avec chacun des $x_i$ (donc avec x).

Nous allons maintenant supposer aussi :

$$\forall j \ge 1 \quad \forall k \ge j \quad x_k \parallel a_j \quad \text{et} \quad \exists a_{j+1} \quad \text{avec } x_j < a_{j+1} < x_{j+1}$$

$$\text{et } \forall j \ge 1 \quad x_{j+1} > x_{j+2} > \dots > x_{j+\ell}$$

L'ordre partiel ainsi défini est un domaine de calcul vérifiant la propriété I. Dans $[x]$ la suite $\{x_{\ell j}\}$ est une suite infinie décroissante d'éléments isolés de $< [x]; \le >$ entre $x$ et $y$. (On peut de la même manière construire un exemple exhibant une suite infinie croissante d'éléments isolés de $< [x]; \le >$ entre $x$ et $y$, cf. figure F-2.3.b)

<figure><img src="image_5.png" /><figcaption>(a)</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>figure F-2.3</figcaption></figure>

<caption>(b)</caption>
Si nous considérons qu'il est souhaitable que la notion de domaine de données soit préservée par passage aux sections supérieures ou aux intervalles, comme nous l'avons indiqué en introduction de ce chapitre, nous sommes naturellement conduits à considérer une propriété plus forte que la propriété I.

### I.3. La relation de couverture

Nous avons vu que les éléments isolés de $<[x);<>$ étaient, sauf pour $x$, de la forme $xvd$ avec $d$ isolé, compatible et incomparable avec $x$. La propriété suivante permet de caractériser de manière semblable les *atomes* d'une section supérieure.

#### Propriété C

Si $x$ et $y$ sont deux éléments isolés compatibles

$$x \wedge y \prec x \Rightarrow y \prec x \vee y$$

**Remarques :** i) Si $x$ et $y$ sont comparables et vérifient $x \wedge y \prec x$, on ne peut avoir $x \leq y$ sinon on aurait $x \wedge y = x \prec x$ ce qui est impossible. On a donc $y \leq x$ donc $x \wedge y = y \prec x$. Dans ce cas, la propriété C se réduit donc à une tautologie.

ii) Alors que la propriété I n'excluait aucun domaine fini, il n'en est pas de même de la propriété C. Il n'y a cependant là rien de très surprenant. Il en est déjà ainsi pour certains axiomes des domaines de calcul. Par exemple l'ordre partiel de la figure (a) n'est pas complet sous-condition, celui de la figure (b) n'est pas cohérent. Les ordres partiels représentés sur la figure (c) et (d) n'ont pas la propriété C.

<figure><img src="image_7.png" /><figcaption>figure P-3.1</figcaption></figure>
La condition de cohérence amène à rajouter au diagramme de la figure (b) un élément maximum g, obtenant ainsi le diagramme de la figure (a).

Dans le domaine de la figure (c), les éléments a et c sont compatibles et $\perp = a \wedge \neg a$ ainsi que $\perp \prec c$. On devrait donc avoir $a \prec \neg a \wedge c$ et $c \prec \neg a \wedge \neg b$ si la propriété C est vérifiée. En ajoutant un élément e = $\neg a \wedge c$ qui couvre a et c et est couvert par g, on obtient à nouveau le domaine de la figure (a) qui lui vérifie C. Enfin, dans le domaine de la figure (d), on a $\perp = a \wedge \neg f$ et $avf = g$ ne couvre pas a. Si l'on rajoute un élément c de façon que $\perp \prec c \prec \neg f$ et b = $\neg a \wedge c$ avec $b \prec \neg g$ on obtient le domaine représenté sur la figure (g) qui possède la propriété C.

iii) La propriété C ne concerne que des paires d'éléments *compatibles*. Cette propriété ne peut donc qu'indiquer la structure des sous-treillis d'un domaine de calcul. En théorie des treillis, cette propriété est connue sous le nom de *condition de couverture inférieure* [9]. Bien qu'un domaine de calcul ne soit pas un treillis, le développement qui suit dans cette section est très largement inspiré de l'étude de cette condition en théorie des treillis.

Nous commençons par montrer, en plusieurs étapes, qu' si l'ensemble des points isolés d'un domaine de calcul possède les propriétés I et C, alors tout le domaine possède la propriété C.

**Proposition P-3.1.** Soit $D = \langle D ; \le \rangle$ un domaine de calcul ayant les propriétés I et C.

On a

$$ \forall x, y \in D \quad x \prec y \Rightarrow \exists z \in A(y) : x \wedge z \prec z \text{ et } y = x \vee z $$

**Démonstration :**

<figure><img src="image_8.png" /><figcaption>figure F-3.2</figcaption></figure>
Si l'on a $x<y$, a fortiori on a $x<y$. Soit alors d'un élément de $A(y)\A(x)$, lequel existe par le lemme A-L1. Puisque d'est pas un approximant de x on a :

$$x \wedge d \neq d$$

Comme D possède la propriété I on en déduit :

i) $x \wedge d \in A(D)$ puisque $d \in A(D)$

ii) $\exists z \in A(y) x \wedge d \prec z \leq d$ (proposition P-2.2.)

L'élément z ainsi défini n'est pas dominé par x, sinon il serait aussi dominé par $x \wedge d$. Par suite $x \wedge z = x \wedge d$. Puisque x et d sont compatibles x et z le sont et $x \prec x \wedge z$ par la propriété C.

Comme x et z sont dominés par y on obtient :

$$x \prec x \wedge z \leq y$$

Or $x<y$ donc $y = x \wedge z$.

**Proposition P-3.2.** Dans un domaine de calcul ayant la propriété I, la propriété C est équivalente à la propriété $\hat{C}$ :

**Propriété $\hat{C}$ :**

Si x et y sont deux éléments quelconques compatibles

$$x \wedge y \prec x \Rightarrow y \prec x \wedge y$$

**Démonstration** : La propriété $\hat{C}$ implique trivalement la propriété C. L'implication inverse est montrée en deux étapes.

1. Supposons d'abord $x$ isolé et y quelconque avec $x \prec y$ et $x \wedge y \prec x$. Comme nous l'avons déjà observé, seul le cas $x \parallel y$ est non tautologique. Par la propriété $I_3$, si $x$ est isolé alors $x \wedge y$ l'est aussi. Supposons alors qu'il existe un élément $v$ avec

$$y \prec v \prec x \wedge y$$

La propriété C exclut une telle possibilité lorsque y est isolé. Comme on a $y \prec v$, il existe un approximant $v_1$ de v qui n'est pas un approximant de y. Puisque x couvre $x \wedge y$, l'élément x ne peut dominer v, car on aurait alors $y = x \wedge y \prec x = x \wedge v$.

Il existe donc un approximant $v_2$ de v qui n'est pas un approximant de x.
Comme $x \wedge y$ est isolé par la propriété $I_3$, nous pouvons construire l'élément isolé $v' = v_1 v_2 v(x \wedge y)$ qui vérifie

$$v' \in A(v), v' \notin A(y), v' \notin A(x), x \wedge y \le v'$$

Remarquons aussi que $v'$ ne domine pas $x$ sinon il en serait de même de $v$ et on ne pourrait avoir $v < x \wedge y$.

<figure><img src="image_9.png" /><figcaption>figure F-3.3</figcaption></figure>

Comme $v'$ est dominé par $x \wedge y$ on a maintenant

$$v' \le x \wedge y = x v (\bigcup A(y)) = \bigcup_{z \in A(y)} (x v z)$$

Comme $v'$ est isolé et l'ensemble $\{x \wedge z | z \in A(y)\}$ est dirigé, il existe un approximant $t$ de $y$ avec

$$v' \le x v t$$

et par suite, en posant $t' = tv(x \wedge y)$ :

$$v'v(x \wedge y) = v' \le x v (tv(x \wedge y)) = x v t'$$

L'élément $t'$ ne peut dominer $x$ sinon on aurait $x v t' = t'$ donc $v' \le t'$, ce qui est impossible puisque $v'$ n'est pas un approximant de $y$.
Par conséquent $t' \wedge x = x \wedge y$ et par la propriété C
$$t' < x \vee t'$$

Posons alors $w = v' \vee t'$. On a
$$t' \le w \le x \vee t'$$

et donc ou bien $w = t'$ ou bien $w = x \vee t'$. Le cas $w = t'$ est impossible puisque il entraine $v' \le t'$ donc $v' \in A(y)$. Le cas $w = x \vee t'$ est lui aussi impossible parce que $v' \vee t' = w$ est un approximant de $v$ qui ne peut dominer $x$ sans contredire l'inégalité $v < x \vee v$. L'existence de $v$ menant à une contradiction dans tous les cas, on a donc nécessairement $y < x \vee y$.

2. Supposons maintenant $x$ quelconque. D'après la proposition P-3.1, si $x \wedge y < x$ on peut trouver un approximant $z$ de $x$ avec
$$(x \wedge y) \wedge z < z \text{ et } x = (x \wedge y) \vee z$$

De la première inégalité on déduit $y > z$. Mais $x \wedge y \le y$ implique aussi $(x \wedge y) \wedge z \le y \wedge z$. Par suite on a $(x \wedge y) \wedge z \le y \wedge z < z$ et donc
$$(x \wedge y) \wedge z = y \wedge z$$

Comme $y$ et $z$ sont compatibles si $y$ et $x$ le sont, on peut appliquer le résultat de la partie 1 et déduire
$$y < y \vee z$$

Comme $x = (x \wedge y) \vee z$, on a maintenant
$$x \vee y = (x \wedge y) \vee z \vee y = y \vee z$$
donc aussi
$$y < x \vee y. \square$$

**Corollaire C-3.1.** Dans un domaine de calcul $D$ vérifiant I et C, toute section supérieure (et tout intervalle) est un domaine de calcul atomique.

**Démonstration** : Ici encore, nous ne faisons la démonstration que dans le cas d'une section supérieure $[x)$. Soit y un élément vérifiant $x < y$. D'après le lemme A-4.1, nous pouvons trouver un approximant $z$ de $y$ qui n'est pas un approximant de $x$ et par suite $x \wedge z < z$.

Comme $z$ et $x \wedge z$ sont des éléments isolés de $D$, il existe un élément $t$ dans $A(D)$ avec $x \wedge z = x \wedge t < t \le z$. Comme $x \uparrow z$ entraine $x \uparrow t$ on obtient, par la propriété C, $x < x \vee t \le x \vee z \le y$. □
**Proposition P-3.3.** Dans un domaine de calcul ayant la propriété I, la propriété C est équivalente à la propriété $C_1$ :

Propriété $C_1$ : Si x et y sont deux éléments compatibles distincts :

$$ \exists z \underline{<} x, z \underline{<} y \Rightarrow x \underline{<} xVy, y \underline{<} xVy $$

Démonstration : 1. $\hat{C}$ implique $C_1$. En effet, si x et y sont distincts l'élément z est leur borne inférieure et la propriété $\hat{C}$ entraîne immédiatement $x \underline{<} xVy$ et $y \underline{<} xVy$

2. $C_1$ implique C. Soient en effet x et y deux éléments isolés compatibles avec $x \underline{<} y \underline{<} x$. Nous allons montrer par récurrence que l'on a $y \underline{<} xVy$ en nous appuyant sur la proposition P-2.2.

<figure><img src="image_10.png" /><figcaption>figure F-3.4</figcaption></figure>

Cas de base : Si $y = x \underline{<} y$ on a immédiatement $y \underline{<} xVy = x$. Si y couvre $x \underline{<} y$ et $x \underline{<} y$, on a immédiatement, par $C_1$ :

$$ y \underline{<} xVy $$

Pas de récurrence : Admettons la propriété C vraie lorsqu'il existe une chaîne maximale avec au plus n éléments entre a^b et b.

Soient alors x et y deux éléments isolés tels qu'il existe une suite à n+1 éléments $\{d_0, d_1, \dots, d_n\}$ avec $x \underline{<} y = d_0 \underline{<} d_1 \underline{<} d_2 \dots \underline{<} d_n = y$.

Par $C_1$ on a $d_1 \underline{<} dvx$. Puisque l'on a $x \underline{<} y$, l'élément $d_1 \underline{<} vx$ n'est pas dominé
par y donc $d_1 = (d_1 v_x)^\wedge y$. En appliquant l'hypothèse de récurrence on obtient

$$y \prec (d_1 v_x) v_y.$$

Or $d_1$ est dominé par y donc $y \prec x v_y$. $\square$

**Définition D-3.1.** On dit qu'un ordre partiel satisfait la condition de Jordan-Dedekind lorsqu'entre deux éléments comparables quelconques, toutes les chaines maximales sont finies et ont la même longueur.

**Théorème T-3.1.** Si $D$ est un domaine de calcul possédant les propriétés I et C, alors $A(D)$ satisfait la condition de Jordan-Dedekind.

**Démonstration** : La preuve que nous donnons ici est calquée sur la preuve du théorème 14, chapitre 2 de Birkhoff [⁹]. Montrons par récurrence que si, entre deux éléments comparables $a$ et $b$ de $A(D)$, il existe une chaine maximale de longueur $n$, alors toutes les chaines maximales ont pour longueur $n$. Supposons $a \le b$. Si $a=b$, toutes les chaines entre $a$ et $b$ ont pour longueur 0. Si $a \prec b$ il ne peut exister d'élément $c$ avec $a < c < b$ et $\{a,b\}$ est la seule chaine maximale entre $a$ et $b$.

Supposons la propriété vraie lorsqu'il existe entre deux éléments comparables, une chaine de longueur inférieure à $n+1$ ($n \ge 1$) et soient $a$ et $b$ deux éléments isolés tels qu'il existe une chaine maximale de longueur $n+1$ entre eux :

$$a = x_0 \prec x_1 \prec x_2 \prec x_3 \dots \prec x_n \prec x_{n+1} = b$$

Comme $D$ possède la propriété I, toutes les chaines maximales entre $a$ et $b$ sont finies et formées exclusivement d'éléments de $A(D)$. Soit donc $\{y_0, y_1, \dots, y_\ell\}$ une chaine maximale quelconque entre $a$ et $b$.

Deux cas sont possibles :

Cas 1 $x_1 = y_1$. Par hypothèse de récurrence, toutes les chaines maximales entre $x_1$ et $b$ ont pour longueur $n$, donc $\{y_1, \dots, y_\ell\}$ comporte $n$ éléments et $\ell = n+1$.

Cas 2 $x_1 \neq y_1$. Mais puisque $x_1$ et $y_1$ sont dominés par $b$, on a $x_1 \prec y_1$ et, par C₁ : $x_1 \prec x_1 v_y_1$ et $y_1 \prec x_1 v_y_1$.
Par hypothèse de récurrence, toutes les chaines maximales entre $x_1$ et $b$ ont pour longueur $n$, donc en particulier toutes celles dont le premier élément est $x_1 vy_1$. Par suite toutes les chaines maximales entre $x_1 vy_1$ et $b$ ont pour longueur $n-1$. Soit $\{z_0 = x_1 vy_1, z_1, \dots, z_{n-1} = b\}$ une telle chaine. La chaine $\{y_1, z_0, \dots, z_{n-1}\}$ est une chaine maximale de longueur $n$ entre $y_1$ et $b$. En appliquant une seconde fois l'hypothèse de récurrence, on obtient que toutes les chaines maximales entre $y$ et $b$ ont pour longueur $n$ et donc en particulier $\{y_1, y_2, \dots, y_\ell\}$. Par conséquent, à nouveau $\ell = n+1$. []

Le théorème ci-dessus permet la définition d'une notion absolue de *taille* pour les éléments isolés.

**Définition D-3.2.** Dans un ordre partiel $<D; \leq>$ muni d'un élément minimum $\bot$, on appelle *fonction taille* une fonction $h$ de $D$ dans $N$ vérifiant

$$i) \quad h(\bot) = 0$$

$$ii) \quad x \prec y \Leftrightarrow x \leq y \text{ et } h(y) = 1+h(x)$$

**Corollaire C-3.2.** Soit $D = \langle D; \leq \rangle$ un domaine de calcul possédant les propriétés I et C. La fonction $h$ de $A(D)$ dans $N$ qui à tout $x$ isolé associe la longueur commune $h(x)$ de toutes les chaines maximales de $\bot$ à $x$ est une fonction taille.

**Démonstration** : Par définition $h(\bot) = 0$. Supposons maintenant $x \prec y$. Toute chaine de maximale $\{\bot, x_1, \dots, x_{h(x)}\}$ de $\bot$ à $x$ peut être étendue en une chaine maximale $\{\bot, x_1, \dots, x_{h(x)}, y\}$, donc $h(y) = 1+h(x)$. Réciproquement, supposons $x \leq y$ et $h(y) = 1+h(x)$. Toutes les chaines maximales de $x$ à $y$ doivent avoir pour longueur $1$ donc $x \prec y$. []

Rappelons que nous appelons $\overline{N}$ le domaine de calcul $\langle Nu\{\infty\}; \leq \rangle$ où $\leq$ désigne l'ordre naturel sur $N$ et $\infty$ est un élément maximum. La fonction $h$ de $A(D)$ dans $N$ peut être étendue en un élément de $[D \to \overline{N}]$ puisqu'elle est croissante. On aura alors $h(x) = \infty$ si $x$ n'est pas isolé, en vertu du corollaire 1 A-C2. Cette propriété nous permettra d'appeler *finis* les éléments de $A(D)$ et *infinis* les éléments non isolés de $D$.
**Remarque** : Les propriétés C et I n'excluent pas qu'un élément fini ne puisse dominer une infinité d'éléments finis, comme l'illustre le contre exemple de la figure :

<figure><img src="image_11.png" /><figcaption>figure F-3.5</figcaption></figure>

En vue de démontrer l'inégalité fondamentale sur la fonction h qui fait l'objet du Théorème T-3.2. nous avons besoin du résultat technique suivant :

**Lemme L-3.1.** Dans un ordre partiel ayant la propriété $C_1$ on a

$$ \forall x,y,z \quad x<y, \quad z>y \quad \Rightarrow \quad x \leq y \leq z $$

**Démonstration** :

<figure><img src="image_12.png" /><figcaption>figure F-3.6</figcaption></figure>

Puisque y et z sont compatibles, a fortiori x et z le sont. Discutons les possibilités pour x vz

**Cas 1** : $xvz = x$, c.à.d. $z \leq x \leq y$. Alors $xvz = x < yvz = y$

**Cas 2** : $xvz = y$, c.à.d. $z \leq y$ donc $xvz = y = yvz$

**Cas 3** : $xv\overline{z} \leq y$. Alors par la propriété C

$$ xvz < (xvz)vy = (xvy)vz = yvz $$

**Cas 4** : $xvz \geq y$. Alors $xvz \geq y$ z mais de $x \leq y$ on déduit aussi $xvz \leq yvz$ donc finalement $xvz = yvz$.
**Théorème T-3.2.** Soient $D$ un domaine de calcul possédant les propriétés I et C, et a et b deux éléments finis compatibles de $D$. On a l'inégalité
$$h(a)+h(b) \geq h(a \wedge b)+h(a \vee b)$$

**Démonstration** : Si a et b sont comparables, considérons par exemple $a \leq b$. Comme $a \wedge b = a$ et $a \vee b = b$ on a trivalement $h(a)+h(b) = h(a \wedge b)+h(a \vee b)$. Supposons donc $a \parallel b$ et considérons une chaine maximale $\{x_0,x_1,\cdots,x_n\}$ avec
$$a \wedge b = x_0 < x_1 < x_2 < \cdots < x_n = b$$

Tous les éléments de cette chaine sont compatibles avec a et, par le lemme précédent :

$$\forall j, 0 \leq j \leq n-1 \quad x_j \vee a = < x_{j+1} \vee a $$

Donc, puisque h est une taille,

$$\forall j, 0 \leq j \leq n-1 \quad h(x_{j+1} \vee a) - h(x_j \vee a) \leq 1$$

En sommant ces inégalités

$$\sum_{0 \leq j \leq n-1} [h(x_{j+1} \vee a) - h(x_j \vee a)] \leq n = h(b) - h(a \wedge b)$$

En réduisant le membre de gauche on obtient

$$h(b \vee a) - h(a) \leq h(b) - h(a \wedge b)$$

soit $h(a)+h(b) \geq h(a \wedge b)+h(a \vee b)$ □

**Lemme L-3.2.** Soient $D$ un domaine de calcul possédant les propriétés I et C et a et b deux éléments quelconques de $D$ avec $a \leq b$. Si il existe une chaine maximale de longueur $n$ finie entre a et b, alors toutes les chaines inclus dans $[a,b]$ sont finies et de longueur inférieure à $n$.

**Démonstration** : Comme dans la démonstration du Théorème T-3.1, on raisonne par récurrence sur $n$. Si $n=0$ ou $n=1$ on a respectivement $a=b$ et $a < b$ et la proposition est immédiate. Supposons la propriété vraie lorsqu'entre deux éléments il existe une chaine maximale de longueur inférieure à $n+1$. Soient a et b deux éléments tels qu'il existe une chaine maximale de longueur $n+1$ entre eux :

$$a = x_0 < x_1 < x_2 < \cdots < x_n < x_{n+1} = b$$
Soit alors $Y = \{y_i\}_{i \in I}$ un sous ensemble totalement ordonné quelconque de $[a,b]$. Choisisons dans $Y$ un élément quelconque $y$ distinct de $a$. Deux cas sont possibles :

**Cas 1** $x_1 \le y$ : Toutes les chaines de $y$ à $b$ sont finies et de longueur inférieure à $n$ par hypothèse de récurrence, donc l'ensemble $Z = \{y_i | i \in I, y \le y_i\}$ a au plus $n+1$ éléments.

**Cas 2** $x_1 \parallel y$ : Alors $y \le x_1 \le y$ par la propriété $C_1$ et $x_1 \ne x_1 \le y$.
Par hypothèse de récurrence, toutes les chaines entre $x_1 \le y$ et $b$ sont finies et comportent au plus $n$ éléments. Donc il existe une chaine avec au plus $n+1$ éléments entre $y$ et l'hypothèse de récurrence montre qu'il en est donc de même de l'ensemble $Z$ défini ci-dessus.

Par conséquent, puisque nous avons choisi $y$ quelconque distinct de $a$, l'ensemble $\{y_i \ne a\}_{i \in I}$ a au plus $n+1$ éléments donc $Y$ a au plus $n+2$ éléments et la chaine $Y$ est au plus de longueur $n+1$. []

Nous sommes maintenant à même de prouver le résultat final de cette section.

**Théorème T-3.3.** Toute section supérieure $[x)$ et tout intervalle $[x,y]$ d'un domaine de calcul $D$ possédant les propriétés I et C est un domaine de calcul qui possède ces deux propriétés.

**Démonstration** : Nous ne faisons la démonstration que pour une section supérieure $[x)$. Nous avons vu que $[x)$ est un domaine de calcul à la proposition P-3.3., dont les éléments isolés sont de la forme $xvd$ avec $d \in A(D)$ et $x \vdash d$. Soit $d$ un élément de $A(D)$ qui n'est pas dominé par $x$. Puisque $x \wedge d$ et $d$ sont isolés, il existe une chaine maximale

$$x \wedge d = z_0 \prec z_1 \prec z_2 \cdots \prec z_n = d$$

Par le lemme L-3.1. on a : $\forall j \ 0 \le j \le n-1 \ z_j \vee x \prec z_{j+1} \vee x$

$$\text{et donc} \qquad x \prec z_1 \vee x \prec z_2 \vee x \cdots \prec z_n \vee x = d \vee x$$

Il existe par conséquent une chaine maximale finie de $x$ à $xvd$ et, par le lemme précédent, toutes les chaines de $x$ à $xvd$ sont finies.
Par suite [x) possède la propriété I. Puisque D possède la propriété $C_1$, la section supérieure [x) possède la propriété C. $\square$

**Définition D-3.3.** Nous dirons que y est fini par rapport à x si y est un élément isolé de [x), et nous écrirons alors x-y.

**Corollaire C-3.3.** Dans un domaine de calcul vérifiant les propriétés I et C, si y est fini par rapport à x toutes les chaines maximales de x à y sont finies et de même longueur.

**Démonstration :** Il suffit d'appliquer le Théorème T-3.1. à [x). $\square$

**Remarques :** Les ouvrages sur la théorie des treillis fournissent d'autres équivalents à la propriété C, qui est appelée fréquemment *condition de couverture inférieure*. Birkhoff[9] appelle treillis *semi-modulaire* un treillis qui vérifie cette condition et dans lequel toutes les chaines sont finies. Maeda[10] utilise le terme de *treillis symétrique*. Les éléments qui couvrent l'élément minimum sont aussi appelés *points* et l'intérêt porté aux treillis semi-modulaires vient de la géométrie. Un treillis est dit *géométrique* si d'une part c'est un treillis semi-modulaire et si d'autre part tout élément est la borne supérieure d'un ensemble de points. Les domaines de calcul que nous considérons n'ont pas cette seconde propriété, mais en revanche il sont algébriques.

## I.4. La relation d'incompatibilité

Les propriétés C et I portaient sur la structure des sous-treillis d'un domaine de calcul. Nous devons maintenant étudier plus en détail la relation d'incompatibilité. Cette étude nous amènera à considérer une nouvelle propriété concernant cette relation.

**Proposition P-4.1.** Si S est un sous ensemble consistant d'un domaine de calcul dont tous les éléments sont compatibles avec un élément donné x, alors $\bigcup S$ et x sont compatibles.

**Démonstration :** L'ensemble $T = S \cup \{x\}$ est consistant, il admet donc une
borne supérieure ⧸ T. Puisque S est consistant inclus dans T on a
S ⩽ S ⧸ T. Par conséquent S et x sont dominés par T, donc
compatibles. □

**Corollaire C-4.1.** Si a et x sont deux éléments incompatibles d'un domaine de calcul, il existe un élément maximum x/a dominé par x et compatible avec a. On appelle alors pseudo-borne supérieure de a et x l'élément av(x/a) qui est noté ayx.

**Démonstration :** Soit S l'ensemble des minorants de x compatibles avec a.
L'ensemble S est consistant puisque majoré par x. Par la proposition précédente S est compatible avec a, et la proposition est montrée avec x/a = S. □

**Proposition P-4.2.** Pour tout élément a d'un domaine de calcul, les fonctions $\lambda x \cdot x/a$ et $\lambda x \cdot ayx$ sont continues.

**Démonstration :** Nous utilisons comme il est d'usage la caractérisation du lemme A-L2. Tout d'abord ces deux fonctions sont croissantes :
$$ 
\begin{cases} x \le x' \Rightarrow x/a \le x'/a \\ x \le x' \Rightarrow ayx = avx/a \le avx'/a = ayx' \end{cases} 
$$

Soit maintenant un approximant de $x/a$. Puisque $e$ est compatible avec $a$, on a $e=e/a$ donc la fonction $\lambda x \cdot x/a$ est continue. Soit maintenant un approximant de $ayx$. Puisque $e$ est isolé avec $e \le avx/a = \bigcup_{z \in A(x/a)} (avz)$ il existe un approximant $d$ de $x/a$ avec $e \le avd$. Mais si $a$ et $d$ sont compatibles on a $ayd = avd$ donc on obtient bien $e \le ayd$. Par suite la fonction $\lambda x \cdot ayx$ est continue. □

**Remarque :** La fonction $\lambda x \lambda y \cdot xVy$ n'est pas croissante en son premier argument. Par exemple dans le domaine $T$ on a

$$ \underline{1V1} = 1 \text{ et } \overline{0V1} = 0 $$

Dans un domaine de calcul muni des propriétés I et C, il est possible de donner une caractérisation plus précise de la relation d'incompatibilité.
**Définition D-4.1.** Un intervalle $[a,b]$ est dit premier lorsque $a < b$.

**Proposition N-4.3.** Dans un ordre partiel quelconque D l'ensemble des intervalles est partiellement ordonné par la relation $\leq$ définie par :

$$[a,b] \leq [c,d] \Leftrightarrow a = b \land c \text{ et } d = b \lor c.$$

On note $I(D)$ l'ordre partiel ainsi obtenu.

**Démonstration : Réflexivité.** Si $[a,b]$ est un intervalle, c'est que $a \leq b$ donc $a = b \land a$ et $b = b \lor a$ donc $[a,b] \leq [a,b]$

**Antisymétrie.** Si on a $[a,b] \leq [c,d]$ on a aussi $a \leq c$ et $b \leq d$. Par suite de $[a,b] \leq [c,d] \leq [a,b]$ on déduit $a \leq c \leq a$ et $b \leq d \leq b$. Puisque $D$ est un ordre partiel, on obtient par antisymétrie $a=c$ et $b=d$.

**Transitivité.** Soient $[a,b]$, $[c,d]$, $[e,f]$ trois intervalles tels que $[a,b] \leq [c,d] \leq [e,f]$. En appliquant les définitions on écrit

$$\begin{cases} a = b \land c, & c = d \land e \text{ donc } a = b \land d \land e \\ d = b \lor c, & f = d \lor e \text{ donc } f = b \lor c \lor e \end{cases}$$

Alors $b \leq d$ et $c \leq e$ permettent de conclure

$$\begin{cases} a = b \land e \\ f = b \lor e \end{cases}$$

c'est à dire $[a,b] \leq [e,f]$. []

**Proposition P-4.4.** Soit $D$ un domaine de calcul possédant les propriétés I et C. Deux éléments $x$ et $y$ de $D$ sont incompatibles ssi on peut trouver deux intervalles premiers $[x_1, x'_1]$ et $[y_1, y'_1]$ inclus respectivement dans $[x \land y, x]$ et $[x \land y, y]$ et deux intervalles premiers $[u, a]$ et $[u, b]$ avec :

$$[x_1, x'_1] \leq [u, a] \quad [y_1, y'_1] \leq [u, b] \quad x \land y \leq u \text{ et } a \neq b$$

**Démonstration :** La situation décrite dans l'énoncé de cette proposition est représentée sur la figure F-4.1

<figure><img src="image_13.png" /><figcaption>figure F-4.1</figcaption></figure>
Soient x et y deux éléments incompatibles. Plaçons nous dans le domaine de calcul [x^y]. Puisque A(y) est un ensemble dirigé, donc consistant, il existe certainement un élément y₀ dans A(y) incompatible avec x. Posons y₁ = y₀/x. Puisque l'élément y₁ est dominé par y₀ qui est isolé dans [x^y], il est aussi isolé par la propriété I. Soit alors y'₁ un élément quelconque couvrant y₁ avec

$$y_1 < y'_1 \le y$$

(y'₁ existe puisque y₁ est compatible avec x donc distinct de y qui ne l'est pas par hypothèse). Par définition de y₁ on doit avoir y'₁≠x. Remarquant alors que x^y'₁ = x^y, nous pouvons itérer cette construction et trouver x₁ et x'₁ finis avec

$$x_1 \uparrow y'_1, x_1 < x'_1 \# y'_1$$

Posons maintenant u = x₁vy₁, a = x'₁vy₁ et b = x₁vy'₁. Puisque x₁ et y₁ sont isolés dans [x^y), il en est de même de u. Puisque x'₁ et y'₁ dominent respectivement x₁ et y₁ on peut écrire

$$a = x_1 v(x_1 vy_1) = x_1 v u$$

$$\text{et} \quad b = (x_1 vy_1) vy'_1 = u vy'_1$$

Finalement u ne peut dominer ni x'₁ ni y'₁ en raison de la relation x'₁≠y'₁. Donc u^x'₁ = x₁ et u^y'₁ = y.

En appliquant la propriété C nous concluons :

$$u < x'_1 v u = a \quad \text{et} \quad u < y'_1 v u = b$$

et, puisque x'_1 et y'₁ sont incompatibles, a^b.

La proposition est donc démontrée dans le sens direct.

Supposons réciproquement que l'on ait deux intervalles premiers [x₁,x'₁] et [y₁,y'₁] inclus respectivement dans [x^y,x] et [x^y,y] et deux intervalles premiers [u,a] et [u,b] avec

$$a \neq b, \ [x_1, x'_1] \le [u, a], \ [y_1, y'_1] \le [u, b].$$

Alors a et b sont incompatibles et b = uvy'₁. Comme a et u sont compatibles, il en résulte que a et y'₁ sont incompatibles. Mais a = x'₁vu et u↑y'₁. Donc finalement x'₁#y'₁ et par voie de conséquence x^y. □
Nous présentons maintenant une propriété nouvelle, dite propriété ( qui restreint la manière dont des incompatibilités peuvent apparaître.

### Propriété Q

Si x et y sont deux éléments isolés incompatibles

$$x \wedge y < x \Rightarrow \exists! t \ t \# x, x \wedge y < t \le y$$

Des domaines de calcul finis très simples peuvent satisfaire les propriétés I et C et ne pas posséder la propriété Q.

<figure><img src="image_14.png" /></figure>

<figure><img src="image_15.png" /><figcaption>Figure F-4.2</figcaption></figure>

Par exemple les domaines dont les diagrammes sont représentés sur la fig. F-4.2.a ne vérifient pas Q. Pour le premier, on observe que a et b sont incompatibles, avec $a \wedge b = \bot$ et $\bot < b$. Mais c est le seul élément de $\lceil \bot, a \rceil$ qui couvre $\bot$ et il est compatible avec b. Il n'existe donc aucun élément t avec $a \wedge b < t \le a$ et $t \# b$. Dans le second cas, le domaine de la fig. F-4.2.b, c'est la clause d'unicité qui n'est pas satisfaite. En effet, les éléments a et d sont incompatibles et $\bot = a \wedge d < a$. Mais b et c couvrent $\bot$, sont dominés par d et sont tous deux incompatibles avec a.

Ces exemples suggèrent que l'on peut considérer la propriété Q comme la conjonction de deux propriétés plus simples.
**Notation** : Soit $x$ un élément quelconque d'un domaine de calcul $D$. Nous noterons $P_x$ l'ensemble $\{z | x^- < z\}$ des atomes de $[x)$. Sur $P_x$ nous pouvons définir une relation $R_x$ par

$$a R_x b \iff a \neq b \text{ ou } a = b$$

La relation $R_x$ est évidemment réflexive et symétrique.

**Proposition P=4.5.** Dans un domaine de calcul $D$, la propriété $Q$ est équivalente à la conjonction des propriétés $Q_E$ et $Q_U$ suivantes :

**Propriété $Q_E$ (Existence d'un incompatible minimal)**

$$\forall x, y \in A(D) \ x \neq y, x \wedge y < x \Rightarrow \exists t \neq x, x \wedge y < t \le y$$

**Propriété $Q_U$ (unicité)**

$$\forall x \in A(D) \quad R_x \text{ est une relation d'équivalence sur } P_x.$$

**Démonstration** i) $Q$ implique $Q_E$ et $Q_U$. Il est immédiat que $Q$ entraine $Q_E$ qui en est un affaiblissement. Par ailleurs nous savons déjà que $R_x$ est réflexive et symétrique. Montrons que $Q$ entraine la transitivité de $R_x$. Soient $a, b$ et $c$ trois éléments de $P_x$ avec $a \le b$ et $b \le c$. Si $a=b$ ou $b=c$ on a immédiatement $a \le c$.

Supposons donc $a \neq b$ et $b \neq c$. Il nous faut montrer que l'on doit avoir ou bien $a=c$ ou bien $a \neq c$. Supposons alors $a \le c$. De $b \neq a$ et $b \neq c$ on déduit $b \neq a \le c$. Il ne peut y avoir qu'un seul élément $t$ vérifiant

$$b \neq t \le a \le c$$

par la propriété $Q$. Mais $a$ et $c$ satisfont cette condition. Par conséquent $a=c$.

ii) Admettons maintenant $Q_E$ et $Q_U$. Soient $x$ et $y$ deux éléments isolés vérifiant
$$x \neq y \text{ et } x \wedge y < x$$

Par $Q_E$, il existe un certain élément $t$ avec

$$x \neq t \text{ et } x \wedge y < t \le y$$
Soit alors $t'$ un élément quelconque vérifiant
$$x \# t' \quad \text{et} \quad x \wedge y \prec t' \le y$$

Dans l'ensemble $P_{x \wedge y}$ on a :

$$x \supseteq_{x \wedge y} t \quad \text{et} \quad x \supsetneq_{x \wedge y} t'$$

Par conséquent, puisque $R_{x \wedge y}$ est une relation d'équivalence :
$$t \supseteq_{x \wedge y} t'$$

Comme $t$ et $t'$ sont compatibles puisque tous deux dominés par $y$, on doit avoir $t=t'$. Par suite $Q_E$ et $Q_U$ impliquent $Q$. $\square$

**Définition D-4.1.** Nous dirons que deux intervalles premiers $[x,x']$ et $[y,y']$ sont équipollents lorsque

$$x = y \text{ et } x' \supseteq_{x} y'$$

Nous désignerons par $IP(X)$ l'ensemble des intervalles premiers d'un ordre partiel $X$. La proposition précédente montre que si $D$ possède la propriété $Q$, la relation d'équipollence est une relation d'équivalence sur $IP(A(D))$.

Comme pour la propriété C, nous allons montrer qu'il suffit de postuler la propriété $Q$ sur les éléments isolés d'un domaine de calcul $D$ pour qu'elle $y$ soit universellement valide.

**Proposition P-4.6.** Dans un domaine de calcul ayant les propriétés I et C soient $x$ et $y$ deux éléments quelconques vérifiant

$$x \# y \quad \text{et} \quad x \wedge y \prec x$$

Il existe un approximant $e$ de $x$ avec

$$e \# y, e \wedge y \prec e \quad \text{et} \quad e \vee (x \wedge y) = x$$
## Démonstration

<figure><img src="image_16.png" /><figcaption>figure F-4.3</figcaption></figure>

Si $x$ est compatible avec $y$, il existe un approximant $d$ de $x$ incompatible avec $y$ puisque $A(x)$ est un ensemble consistant, en vertu de la proposition P-4.1. Comme $d$ n'est par conséquent pas comparable avec $y$, on a nécessairement $d\^y < d$. On peut alors trouver un élément $e$ avec $d\^y - e \le d$ (corollaire C-3.1). Comme $e$ couvre $d\^y$ et n'est pas dominé par $y$, on a aussi $e\^y = d\^y$. Par la propriété $\hat{C}$ on obtient $x\^y - (x\^y)^{ve}$. Comme $e$ est aussi un approximant de $x$, l'élément $(x\^y)^{ve}$ est dominé par $x$. Comme $x$ couvre $x\^y$, on obtient $(x\^y)^{ve} = x$. Finalement, les éléments $e$ et $y$ sont incompatibles, car s'ils étaient compatibles on aurait aussi $x=e\^v(x\^y) \le e\^v y$ et $x$ et $y$ seraient compatible ce qui est contraire à l'hypothèse. $\square$

**Lemme L4.1.** Dans un domaine de calcul possédant les propriétés I et C, la propriété $\hat{Q}_E$ est équivalente à la propriété $\hat{Q}_E$ :

Propriété $\hat{Q}_E$

$$ \forall x,y \quad x\#y, x\^y - < x \Rightarrow \exists t \#x, x\^y - < t \le y $$

**Démonstration** : La propriété $\hat{Q}_E$ implique trivialment la propriété $\hat{Q}_E$. L'implication inverse est montrée en deux étapes.

1. Supposons d'abord $x$ isolé et $y$ quelconque avec $x\#y$ et $x\^y - < x$. Comme nous l'avons déjà vu, il existe un approximant $d$ de $y$ incompatible avec $x$. Comme $x\^y$ et $d$ sont dominés par $y$, on peut poser $e = d\^v(x\^y)$. L'élément $e$ est isolé puisque $d$ et $x\^y$ le sont, et incompatible avec $x$ puisqu'il hérite cette propriété de $D$. Par suite on a $x\^y = x^\wedge e$ et l'on peut utiliser la propriété $\hat{Q}_E$.
<figure><img src="image_17.png" /><figcaption>figure F-4.4</figcaption></figure>

Il existe un élément $t$ avec

$x \# t \quad x \wedge e -< t \le e$

d'où l'on déduit immédiatement

$x \# t \quad x \wedge y -< t \le y.

2. Supposons maintenant $x$ quelconque. Par la proposition précédente, il existe un élément isolé $e$ avec

$e \# y$, $e \wedge y -< e$ et $x = e \vee (x \wedge y)$

<figure><img src="image_18.png" /></figure>

On peut alors appliquer le résultat de la première partie, exhibant ainsi un élément $t$ avec

$e \# t \quad \text{et} \quad e \wedge y -< t \le y$

Maintenant remarquons que d'une part $t$ et $x \wedge y$ sont compatibles puisque tous deux dominés par $y$ et que, d'autre part $t$ n'est pas dominé par $x \wedge y$ puisque $t$ est incompatible avec $e$, ce qui permet de déduire que $t \wedge (x \wedge y) = e \wedge y$. On applique alors la propriété $\tilde{C}$ :

$$x \wedge y -< (x \wedge y) \vee t = u$$
L'élément u est incompatible avec e donc avec x et l'on a bien

$$x \wedge y \leq u \leq y. \quad \square$$

**Proposition P-4.7** Soient a, x et y trois éléments d'un domaine de calcul possédant les propriétés I et C tels que la condition

$$(G_1) \quad a < x, a < y, x \# y$$

soit satisfaite. Il existe alors trois éléments $\alpha, \xi$ et $\eta$ approximant respectivement a, x et y, satisfaisant la même condition $(G_1)$ et de plus $x = \xi \vee a$ et $y = \eta \vee a$.

**Démonstration**

<figure><img src="image_19.png" /><figcaption>figure F-4.6</figcaption></figure>

En appliquant deux fois la proposition P-4.6, on peut trouver $x_1$ et $y_1$ approximant respectivement x et y avec :

$$\begin{cases} x_1 \# y, & x_1 \wedge y < x_1, & x_1 \vee a = x \\ y_1 \not\# x, & y_1 \wedge x < y_1, & y_1 \vee a = y \end{cases}$$

Posons alors $\alpha = (x_1 \wedge y) \vee (y_1 \wedge x)$. L'élément $\alpha$ est un approximant de a et il ne peut dominer ni $x_1$ ni $y_1$. On a donc :

$$\begin{cases} \alpha \wedge x_1 = x_1 \wedge y < x_1 \\ \alpha \wedge y_1 = x \wedge y_1 < y_1 \end{cases}$$
Par la propriété C on obtient donc

$$ \begin{cases} \alpha - < \alpha \vee x_1 = \xi \\ \alpha - < \alpha \vee y_1 = \eta \end{cases} $$

et comme $\xi$ et $\eta$ sont nécessairement incompatibles avec a

$$ \begin{cases} x = \xi \vee a \\ y = \eta \vee a \end{cases} $$

Si $\xi$ et $\eta$ étaient compatibles, l'ensemble $\{\xi, \eta, a\}$ serait consistant, et il admettrait donc une borne supérieure qui dominerait $\xi \vee a$ et $\eta \vee a$. Mais ceci est impossible puisque $x$ et $y$ sont incompatibles par hypothèse. Par conséquent on a bien

$$ \alpha - < \xi, \alpha - < \eta, \xi \# \eta \quad \square $$

**Proposition P-4.8** Soient $a, x, y, z$ quatre éléments d'un domaine de calcul, possédant les propriétés I et C, tels que la condition

$$ (G_2) \quad a - < x, a - < y, a - < z, x \# y, y \# z, x \neq z $$

soit satisfaite. Il existe alors quatre éléments $\alpha, \xi, \eta, \zeta$ approximant respectivement $a, x, y, z$, satisfaisant la même condition $(G_2)$ et de plus $x = \xi \vee a, y = \eta \vee a, z = \zeta \vee a$

**Démonstration** Appliquons en premier lieu la proposition précédente aux trois éléments $a, x$ et $y$. On peut trouver $\alpha_1, \xi_1$ et $\eta_1$ approximant $a, x$ et $y$ avec :

$$ \begin{cases} \alpha_1 - < \xi_1, \quad \alpha_1 - < \eta_1, \quad \xi_1 \# \eta_1 \\ x = \xi_1 \vee a, \quad \eta = \eta_1 \vee a \end{cases} $$

Plaçons nous maintenant dans $[\alpha_1)$. Par la proposition P-3.1, on peut trouver un élément $\zeta$ tel que $\alpha_1 \leq \zeta$ avec

$$ \begin{cases} \zeta \wedge a = \alpha - < \zeta \\ z = \zeta \vee a \end{cases} $$
Comme $\alpha_1$ est fini, il en est de même de $\zeta$ et des éléments $\xi$ et $\eta$ définis par

$$ \begin{cases} \xi = \xi_1 v\alpha \\ \eta = \eta_1 v\alpha \end{cases} $$

(Comme $\xi_1$ et $\eta_1$ sont compatibles avec $\alpha$, ils sont a fortiori compatibles avec $\alpha$).

Comme $\xi_1$ et $\eta_1$ ne peuvent être dominés par $\alpha$, donc par $\alpha$

$$ \begin{cases} \xi_1 \wedge \alpha = \alpha_1 - < \xi_1 \\ \eta_1 \wedge \alpha = \alpha_1 - < \eta_1 \end{cases} $$

et par suite, par la propriété C :

$$ \begin{cases} \alpha - < \xi \\ \alpha - < \eta \end{cases} $$

Nous avons aussi $\alpha - < \zeta$. Montrons les propriétés restantes. Tout d'abord $\xi \# \eta$ puisque $\xi_1 \# \eta_1$. Ensuite on a

$$ \begin{cases} x = a \vee \zeta_1 = a \vee \xi_1 \vee \alpha = a \vee \xi \\ y = a \vee \eta_1 = a \vee \eta_1 \vee \alpha = a \vee \eta \\ z = a \vee \zeta. \end{cases} $$

Si $\eta$ et $\zeta$ étaient compatibles l'ensemble $\{a, \eta, \zeta\}$ serait consistant, ce qui contredit l'incompatibilité de $x$ et $y$. Donc on a aussi $\eta \# \zeta$. Enfin, puisque $x \neq z$ on a trivialement $\xi \neq \zeta$. $\square$

**Remarque** : Dans les deux propositions précédentes, ainsi que dans d'autres portions de démonstration de ce chapitre, nous faisons un usage libre de la propriété de cohérence, qui permet parfois des preuves plus brèves. Cependant, cette propriété n'est pas indispensable à la validité des résultats.
**Lemme L-4.2.** Dans un domaine de calcul *D* ayant les propriétés I et C, la propriété $Q_U$ est équivalente à la propriété $\hat{Q}_U$ :

**Propriété** $\hat{Q}_U$

Dans $IP(D)$, l'équipollence est une relation d'équivalence.

**Démonstration** : La propriété $\hat{Q}_U$ implique trivialment la propriété $Q_U$ qui en est un affaiblissement. L'implication inverse est un corollaire de la proposition précédente. Soient

$[a,x],[a,y]$ et $[a,z]$ trois intervalles avec

$[a,x]R[a,y]$ et $[a,y]R[a,z]$

Comme pour la proposition P-4.5, le seul cas non trivial qui reste à envisager pour montrer que $R$ est transitive est celui où $x \vdash z$, avec $x \# y$, $y \# z$, $x \not\vdash z$. D'après la proposition P-4.6, on peut alors trouver des approximants $\alpha, \xi, \eta$ et $\zeta$ de $a,x,y,z$ avec

$$ \alpha - < \xi, \alpha - < \eta, \alpha - < \zeta, \xi \# \eta, \eta \# \zeta, \xi \neq \zeta $$

et de plus $x=av\xi$ et $z=av\zeta$. Par suite, si $x$ et $z$ sont compatibles, il en est de même de $\xi$ et $\zeta$. Mais la propriété $Q_U$ exclut cette possibilité. Par suite $x$ et $z$ sont nécessairement incompatibles et la relation d'équipollence entre intervalles premiers est transitive. $\square$

**Corollaire C-4.2** La propriété $Q$, dans un domaine vérifiant les conditions I et C, est équivalente à la propriété $\hat{Q}$ :

**Propriété** $\hat{Q}$

Si $x$ et $y$ sont incompatibles

$$ x \wedge y - < x \Rightarrow \exists! t \ t \# x, x \wedge y - < t \leq y $$

**Démonstration** Il est trivial de montrer, comme à la proposition P-4.5, que $\hat{Q}$ est équivalente à la conjonction de $\hat{Q}_E$ et $\hat{Q}_U$. $\square$
**Corollaire C-4.3** Dans un domaine D vérifiant les propriétés I, C et Q, toute section supérieure possède ces propriétés.

**Démonstration** Soit [a) une section supérieure quelconque. Le domaine de calcul [a) possède les propriétés I et C. Si x et y sont deux éléments de [a), il en est de même de x^y. Donc si D possède la propriété Q, il en est de même de [a). □

**Notation** Si [a,b] et [c,d] sont deux intervalles premiers équipollents, nous écrirons désormais [a,b]=[c,d].

**Définition D-4.2** Etant donné un ordre partiel D, deux intervalles sont dits *transposés* ssi ils sont *comparables* en tant qu'éléments de I(D). Nous appellerons T la relation de transposition. Cette relation est évidemment réflexive et symétrique.

**Lemme L-4.3** Dans un domaine de calcul D satisfaisant I, C et Q, les relations d'équipollence et de transposition *commutent* sur IP(D), c'est-à-dire :

$$ \approx \circ T = T \circ \approx $$

**Démonstration** Soient [a,a'], [a,a''] et [b,b'] des intervalles premiers tels que

$$ [a,a']=[a,a''] \text{ et } [a,a'']T[b,b'] $$

Nous devons montrer qu'il existe toujours un intervalle premier [b,b''] tel que

Si $a'=a''$, on $[a,a']T[b,b']$ et l'on peut donc toujours prendre $[b,b']=[b,b']$. Supposons donc $a'#a''$. Si $[a,a']=[b,b']$, on peut prendre $[b,b']=[a,a']$. Deux cas restent possibles :
Cas 1 : $[a,a']>[b,b']$

<figure><img src="image_20.png" /><figcaption>figure F-4.7.</figcaption></figure>

Dans ce cas $a'$ est nécessairement compatible avec $b$. Supposons en effet $a'^{#b}$. Par la propriété Q il existe un élément $t$ avec

$$a'^{#t} \text{ et } a - < t \le b$$

Donc $[a,a']=[a,a']=[a,t]$. Par la propriété Q à nouveau :

$$[a,a']=[a,t]$$

Mais alors :
1. ou bien $a'^{#t}$, mais ce cas est impossible puisque $a''$ et $t$ sont dominés par $b'$
2. ou bien $a''=t$, mais ce cas est lui aussi impossible puisque $a'^{\wedge}b \ne a''$ donc $a''$ n'est pas dominé par $b$ alors que $t$ l'est.

Posons donc $b''=a'^{\vee}b$. Comme $a'^{\wedge}b=a<a'$ on peut l'appliquer la propriété C et par conséquent $b - < b''$. Finalement $b''$ et $b'$ ne peuvent être compatibles, sinon il en serait de même de $a'$ et $a''$ ce qui contredit l'hypothèse. Nous avons donc bien

$$[a,a']T[b,b''] \text{ et } [b,b'']=[b,b']$$

ce qui conclut l'étude de ce cas.

Cas 2 : $[a,a']>[b,b']$

<figure><img src="image_21.png" /><figcaption>figure F-4.8</figcaption></figure>
Dans ce cas $a'$ et $b'$ sont nécessairement incompatibles. En effet si $a'$ et $b'$ étaient compatibles l'élément $a'vb'=a'vavb'=a'va''$ existerait ce qui contredit $a'#a'$. De $a'#b'$ on déduit, puisque $a'^{\wedge}b'=b^{<}b'$, qu'il existe un certain élément $b''$ avec :

$$b''#b' \text{ et } b < b'' \le a'$$

par application de la propriété Q. Comme cet élément $b''$ n'est pas dominé par $a$, car $a''$ dominerait alors et $b'$ et $b''$, on a bien $b''va=a'$ et $b''\wedge a=b$. Donc

$$[a,a']T[b,b''] \text{ et } [b,b''] \cong [b,b']$$

ce qui conclut l'étude de ce cas et la démonstration de la proposition. ☐

**Définition D-4.3.** On appelle *relation de projectivité* la fermeture transitive de la relation de transposition. Cette relation est une relation d'équivalerce notée ~. Si les intervalles $[a,b]$ et $[c,d]$ vérifient $[a,b] \sim [c,d]$ ils sont dit *projectifs*.

Nous ne nous interesserons qu'à la restriction de cette relation aux intervalles premiers.

**Théorème T-4.1** Dans l'ensemble des intervalles premiers d'un ordre partiel satis faisant les propriétés I, C et Q, les relations d'équipollence et de projectivité sont des relations d'équivalence qui commutent, c'est-à-dire :

$$\cong \circ \cong \sim \circ \cong \cong \circ \cong$$

**Démonstration** D'après de lemme précédent nous savons que

$$\cong \circ T \cong T \circ \cong$$

Montrons par récurrence que pour tout $n$ positif on a alors

$$\cong \circ T^n \cong T^n \circ \cong$$

Le cas $n=1$ est immédiat et
$$
\begin{align*}
\approx \circ T^{n+1} &= (\approx \circ T^n) \circ T \\
&= (T^n \stackrel{\approx}{\circ} \circ T) && \text{par hypothèse de récurrence} \\
&= T^n \circ (\approx \circ T) && \text{par associativité} \\
&= T^n \circ (T \circ \approx) \\
&= T^{n+1} \circ \approx && \text{par associativité à nouveau}
\end{align*}
$$

Comme [a,b]≈[c,d] ssi il existe un entier n tel que

[a,b]≈Tⁿ[c,d], on a alors aussi [a,b]Tⁿ=[c,d] donc [a,b]≈[c,d] []

Le produit des deux relations d'équivalence ≈ et ~ est lui aussi une
relation d'équivalence que nous noterons ≈. Comme la relation ≈ étend ≈,
nous dirons **désormais** que les intervalles premiers [a,b] et [c,d] sont
équipollents ssi [a,b]≈[c,d].

Avant de procéder à une étude plus approfondie des relations d'équipollence et de projectivité, nous allons sur quelques exemples essayer de donner une interprétation intuitive de leur signification.

**Exemple 1** Considérons le domaine $O^3$ dont le diagramme est représenté sur la figure F-4.9.

<figure><img src="image_22.png" /><figcaption>figure F-4.9. Le domaine $O^3$</figcaption></figure>

Comme ce domaine est un treillis, il ne peut nous servir à illustrer la
relation d'équipollence. En revanche, il comporte trois classes d'équivalence
pour la relation de projectivité ~
Classe 1 [(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]
Classe 2 [(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]
Classe 3 [(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]~[(⊥,⊥,⊥), (⊥,⊥,⊥)]

et l'on peut remarquer que dans une classe d'index i, un intervalle premier est de la forme [v,v'] avec vᵢ=⊥ et vᵢ'=τ, toutes les autres composantes restant in-changées.

**Example 2** · Considérons le domaine O×T dont le diagramme est représenté sur la figure F-4.10.

<figure><img src="image_23.png" /><figcaption>figure F-4.10 Le domaine O×T</figcaption></figure>

Il y a ici trois classes d'intervalle s projectifs :

Classe 1 [(⊥,⊥), (0,⊥)]~[(⊥,⊥), (0,⊥)]

Classe 2 [(⊥,⊥), (1,⊥)]~[(⊥,⊥), (1,⊥)]

Classe 3 [(0,⊥), (0,⊥)]~[(⊥,⊥), (⊥,⊥)]~[(1,⊥), (1,⊥)]

La réunion des classes 1 et 2 est une classe d'intervalle s équipollents et la classe 3 en est une deuxième. Le fait que O comporte deux atomes incompa-tibles est reflété dans le fait que la première classe d'équipollence est com-posée de deux classes de projectivité. Le fait qu'il s'agisse d'un produit car-tésien de deux domaines est reflété par la présence de deux classes d'équipol-lence. Nous voyons donc mieux apparaître, par l'intermédiaire de ces deux rela-tions d'équivalence, la structure du domaine étudié. Tout naturellement, le théorème de représentation du § I.7. s'appuiera de façon cruciale sur ces relations, que nous étudions maintenant d'une manière plus approfondie.
### I.5. La relation de projectivité

Si deux intervalles premiers sont projectifs, nous souhaiterions qu'ils représentent un même accroissement élémentaire d'information, réalisé peut-être dans deux états d'information distincts. Nous appellerons désormais *décision élémentaire*, ou plus brièvement *décision* une classe d'équivalence d'intervalles premiers projectifs. Une telle interprétation se heurte cependant à une incohérence qui ne peut être éliminée que par la considération d'une propriété supplémentaire.

Considérons en effet l'ordre partiel de la figure F-5.1.

<figure><img src="image_24.png" /><figcaption>figure F-5.1</figcaption></figure>

Il est trivial de vérifier que cet ordre partiel est un domaine de calcul qui vérifie les propriétés I, C et Q. Comme on a aussi :

$$[1,a] \le [b,T] \ge [1,c] \le [a,T] \ge [1,b] \le [c,T]$$

tous les intervalles premiers de ce treillis sont dans une seule et même classe d'équivalence par projectivité. Il est difficile d'accepter qu'une même décision élémentaire puisse permettre de construire quatre éléments distincts. Plus particulièrement, deux faits précis vont à l'encontre de notre interprétation :

i) Tous les intervalles premiers de la forme $[1,x]$ sont projectifs et devraient constituer la même décision élémentaire.

ii) Pour aller de 1 à b, par exemple, la "décision" est la même que pour aller de b à T.

Considérant l'importance du treillis de la figure F-5.1, il serait concevable qu'il soit suffisant d'exclure une telle configuration de 5 éléments dans un domaine de calcul pour rendre notre interprétation cohérente. Nous verrons que lorsqu'un domaine de calcul est un treillis, il en est bien
ainsi. La présence d'éléments incompatibles rend la situation plus délicate. Considérons par exemple le domaine de la figure F-5.2, qui est représenté par son diagramme de Hasse, mais en "vue de dessus"

<figure><img src="image_25.png" /><figcaption>figure F-5.2</figcaption></figure>

(Les flèches indiquent le sens croissant). Un sous treillis de ce domaine est un sous treillis de l'un des intervalles [⊥,a'], [⊥,b'], [⊥,c'] ou [⊥,d'] puisque les éléments a',b',c' et d' sont maximaux et incompatibles. Mais il est clair qu'aucun de ces intervalles ne contient de sous-treillis isomorphe au treillis de la figure F-5.1. Cependant, les phénomènes que nous avons considérés plus haut comme incohérents se produisent ici encore puisque, dans l'intervalle [a,a'] tous les intervalles premiers sont projectifs.

De la même manière, le domaine de la fig. F-5.3, qui comporte 25 éléments met en évidence le fait que deux intervalles premiers distincts peuvent être à la fois projectifs et équipollents : [a,a₁] ~ [a,a₂] et a₁≠a₂.

Or deux intervalles équipollents distincts devraient correspondre à deux accroissements élémentaires contradictoires.
<figure><img src="image_26.png" /><figcaption>Figure F-5.3</figcaption></figure>

Les deux exemples ci-dessus, dus à Gordon Plotkin, conduisent à introduire une nouvelle propriété, appelée propriété R.

### Propriété R

Si $[a,x]$ et $[a,y]$ sont deux intervalles premiers à extrémités isolées projectifs, alors $x=y$

On peut paraphraser cette propriété de la façon suivante : si a est un élément isolé, deux accroissements élémentaires distincts à partir de a constituent deux décisions distinctes.

Avant d'étudier les multiples conséquences de la propriété R, montrons comme à l'habitude qu'elle est valide pour deux intervalles premiers quelconques.

**Proposition P-5.1** Soient $[a,a']$ et $[b,b']$ deux intervalles premiers à extrémités isolées dans un domaine de calcul vérifiant I et C. Si il existe un intervalle premier $[c,c']$ avec

$$[a,a'] \le [c,c'] \ge [b,b']$$

alors il existe un intervalle premier à extrémités isolées $[d,d']$ avec

$$[a,a'] \le [d,d'] \ge [b,b']$$

**Démonstration** : Par hypothèse $c'=a'vc$ donc $c'=a'v(\bigcup A(c))$ ou encore $c' = \bigcup_{z \in A(c)} (a'vz)$. L'ensemble $\{a'vz | z \in A(c)\}$ est dirigé et domine l'élément b'
qui est isolé. Il existe par suite un élément isolé e avec $b' \le a'$ ve, $e \in A(c)$. Posons $d=evavb$. L'élément $d$ est un approximant de $c$ qui domine $a$ et $b$. Par suite $d$ ne domine ni $a'$ ni $b'$ et, par la propriété C :

$$ \begin{cases} d < dva' \\ d < dvb' \end{cases} $$

$$ \text{Donc puisque } b' \le a' \text{ ve} \le a' \text{ veavb} = a' \text{vd} \\ d < dvb' \le dva' $$

Les éléments $dvb'$ et $dva'$ sont donc égaux à un même élément $d'$ et $[a, \text{à'}] \le [d, d'] \ge [b, b']$ .

**Proposition P-5.2** Dans un domaine de calcul vérifiant les propriétés I et C, la propriété $\hat{R}$ est équivalente à la propriété $\hat{R}$ :

**Propriété $\hat{R}$ :**

Si $[a,x]$ et $[a,y]$ sont deux intervalles premiers projectifs, alors $x=y$.

**Démonstration :** La propriété $\hat{R}$ implique trivialment la propriété P. Réciproquement soient $[a,x]$ et $[a,y]$ deux intervalles premiers projectifs. Il existe une suite $\{[x_i, x_i']\}_{0 \le i \le n}$ avec $[x_0, x_0'] = [a, x]$ et $[x_n, x_n'] = [a, y]$ vérifiant $[x_0, x_0'] \cup [x_1, x_1'] \cdots \cup [x_n, x_n']$.

D'après le lemme VI.3.1, on peut trouver des intervalles $[z_i, z_i']$ avec extrémités isolées avec $[z_i, z_i'] \le [x_i, x_i']$ ($0 \le i \le n$).

Si l'on pose $[t_i, t_i'] = [x_i, vx_{i+1}, x_i'vx_{i+1}']$ ($0 \le i \le n-1$) on a alors $[z_i, z_i'] \le [t_i, t_i'] \ge [z_{i+1}, z_{i+1}]$ ($0 \le i \le n-1$).

D'après la proposition précédente, il existe donc des intervalles premiers à extrémités isolées $[u_i, u_i']$ ($0 \le i \le n-1$) tels que $[z_i, z_i'] \le [u_i, u_i'] \ge [z_{i+1}, z_{i+1}]$ ($0 \le i \le n-1$).

Par conséquent $[z_0, z_0']$ et $[z_n, z_n']$ sont projectifs dans $A(D)$. De $[z_0, z_0'] \le [a, x]$ et $[z_n, z_n'] \le [a, y]$ on déduit que $z_0$ et $z_n$ sont tous deux dominés par $a$ et l'on peut poser

$$ z \equiv \frac{z_0}{v} z_n $$
Cet élément $z$, ne peut dominer ni $z'_0$ ni $z'_n$ Puisque c'est un approximant de $a$, qui ne les domine pas. Donc

$$ egin{cases} z \wedge z'_0 = z_0 \\ z \wedge z'_n = z'_n \end{cases} $$

Par conséquent

$$ egin{cases} z \prec z \vee z'_0 = z' \\ z \prec z \vee z'_n = z'' \end{cases} $$

ce qui montre que

$$ egin{cases} [z_0, z'_0] \preceq [z, z'] \\ [z_n, z'_n] \preceq [z, z''] \end{cases} $$

Comme $z$ est isolé et $[z,z'] \sim [z,z'']$, on peut appliquer la propriété R et déduire

$$ z' = z'' $$

Comme on a aussi

$$ egin{cases} [z, z'] \preceq [a, x] \\ [z, z''] \preceq [a, y] \end{cases} $$

on en conclut

$$ x = y $$

□

**Corollaire C-5.1** Toute section supérieure (et tout intervalle) d'un domaine de calcul possédant les propriétés I,C,Q et R vérifie ces mêmes propriétés.

**Démonstration** : Soit [b) une section supérieure. Si les intervalles premiers [a,x] et [a,y] sont projectifs dans [b), ils le sont aussi dans le domaine entier.

Par suite $x=y$, donc la section supérieure [b) possède la propriété R.

Nous savons déjà par ailleurs que toute section supérieure possède les propriétés I,C et Q. □

**Proposition P-5.2** Soient D un domaine de calcul vérifiant I, C et R et deux éléments compatibles x et y dans D. Si $[a,a']$ est un intervalle premier vérifiant

$$ a \le x \wedge y \text{ et } a' \le x \vee y $$

alors ou bien $a' \le x$ ou bien $a' \le y$.
**Démonstration** : Remarquons d'abord que dans le cas où x et y sont comparables (par exemple $x \leq y$) on a immédiatement

$$a' \leq y = x \land y$$

donc la proposition est trivialement vérifiée. Supposons donc $x \leq y$. On peut aussi supposer $a' \leq x \land y$ sinon la propriété est, là encore immédiate. Considérons d'abord le cas où x et y sont finis par rapport à $x \land y$.

**Cas 1** $x \land y \leq x, x \land y \leq y$ : Nous allons alors raisonner par récurrence sur la somme des longueurs des chaines maximales de $x \land y$ à x de $x \land y$ à y que nous appellerons $\delta(x,y)$.

i) **Cas de base** : Puisque $x \leq y$, le premier cas à envisager est celui où $\delta(x,y)=2$, c.à.d. $x \land y \leq x$ et $x \land y \leq y$. De $a' \leq x \land y$ on déduit $a=a' \land x \land y$ et, par la propriété C applicable puisque $a' \uparrow x \land y : x \land y \leq a'' \leq x \land y$ avec $a''=a' \lor (x \land y)$

* ou bien $a'' = x$ ce qui entraine $a' \leq x$

* ou bien $a'' \neq x$ et alors, par la propriété C $x \leq a'' \lor x \leq x \land y$. Mais on a aussi $x \leq x \land y$, et par conséquent $a'' \lor x = x \land y$. Des inégalités

$$[x \land y, a''] \leq [x, x \land y] \geq [x \land y, y]$$

on déduit par la propriété R que l'on a $a''=y$. Par conséquent on a bien, lorsque $\delta(x,y)=2$ ou bien $a'' \leq x$ ou bien $a'' \leq y$.

ii) **Pas de récurrence** : Supposons $\delta(x,y)=n, n>2$

<figure><img src="image_27.png" /></figure>

Comme x et y sont incomparables on doit avoir $x \land y \leq x$ et $x \land y \leq y$. Par atomicité, il existe donc deux éléments $x_1$ et $y_1$ avec

$$x \land y \leq x_1 \leq x \quad \text{et} \quad x \land y \leq y_1 \leq y.$$
Posons alors $z=x_1 vy_1$, $x'_1=x vy_1 =x v z$, $y'_1=x vy=z vy$.

Les éléments $x'_1, y'_1$ et $z$ existent nécessairement puisque $x$ et $y$ sont compatibles. Deux cas sont alors possibles :

**Cas 1.1** $a' \le z$ : On peut alors appliquer le résultat du cas de base et en déduire

$$ 
\begin{array}{lclcl}
\text{donc} & a' \le x_1 & \text{ou bien} & a' \le y_1 & \\
& a' \le x & \text{ou bien} & a' \le y &
\end{array}
$$

**Cas 1.2** $a' \neq z$ : Mais alors $a=a' \wedge z$. Comme $a'$ et $z$ sont compatibles puisque tous deux dominés par $xvy$, on peut appliquer la propriété C. Posant $a''=zva'$ on a alors

$$ z < a'' \le xvy $$

Mais $x'_1 vy'_1 = x v z vy v z = xvy$ et comme $z$ est dominé par $x'_1$ et $y'_1$ on a aussi $z \le x'_1 \wedge y'_1$. Pour pouvoir appliquer l'hypothèse de récurrence à l'intervalle premier $[z,a'']$ et aux éléments $x'_1$ et $y'_1$, il nous suffit donc de vérifier que $\delta(x'_1,y'_1) < \delta(x,y)$. Or $\delta(x'_1,y'_1)$ est majoré par la somme des longueurs de chaines maximales de $z$ à $x'_1$ et de $z$ à $y'_1$. Par suite $\delta(x'_1,y'_1) \le n-2$.

L'hypothèse de récurrence donne alors le résultat :

$$ a'' \le x'_1 \text{ ou bien } a'' \le y'_1 $$

Supposons, sans qu'il y ait perte de généralité que l'on ait $a'' \le x'_1$. Puisque $a''$ domine $a'$, on a aussi $a' \le x'_1$. Or $\delta(x,z)$ est inférieur à $n-1$. On peut alors appliquer une seconde fois l'hypothèse de récurrence à l'intervalle $[a,a']$ et aux éléments $x$ et $z$ pour conclure : ou bien $a' \le z$ ou bien $a' \le x$. Mais nous avons supposé dans le cas que nous étudions $a' \neq z$. Il ne reste donc que l'éventualité $a' \le x$.

**Cas 2** Supposons maintenant $x$ et $y$ quelconques et posons à nouveau $a'' = a' \vee (x \wedge y)$. Comme la section supérieure $[x \wedge y)$ est un domaine de calcul, il existe des approximants $x'$ et $y'$ de $x$ et $y$ dans ce domaine tels que l'atome $a''$ soit dominé par $x'vy'$. On a alors $a \le x \wedge y \le x' \wedge y'$ et $a' \le x'vy'$ avec $x' \wedge y' \le x'$ et $x' \wedge y' \le y'$.

En appliquant le résultat du cas 1 on en déduit ou bien $a' \le x'$ ou bien $a' \le y'$ ce qui permet de conclure à nouveau $a' \le x$ ou bien $a' \le y$. $\square$
**Corollaire C-5.2.** Dans un domaine de calcul possédant les propriétés I,C et R, aucun sous-treillis n'est isomorphe au treillis de la figure VI.5.1.

**Démonstration :** Soient en effet x et y deux éléments quelconques compatibles et incomparables. Choisisson un élément z quelconque avec

$$x \wedge y \leq z \leq x \vee y$$

Par atomicité, il existe un élément t avec

$$x \wedge y < t \leq z$$

D'après la proposition précédente ou bien $t \leq x$ ou bien $t \leq y$. Dans le premier cas $x \wedge y < x \wedge z$ et dans le second $x \wedge y < y \wedge z$. []

Pour prouver la réciproque de ce résultat, nous avons besoin d'un résultat très utile qui limite le nombre de cas à considérer lorsque deux intervalles sont projectifs. Ce résultat s'obtient en deux étapes.

**Proposition P-5.3** Dans un domaine de calcul vérifiant I,C et R, soient $[a,a']$, $[b,b']$, $[c,c']$ trois intervalles premiers vérifiant $[a,a'] \geq [b,b'] \leq [c,c']$. Si a et c sont compatibles, on a aussi $[a,a'] \leq [avc, a'vc'] \geq [c,c']$.

**Démonstration :**

<figure><img src="image_28.png" /><figcaption>figure F-5.4.</figcaption></figure>

Par définition de la relation $\leq$ entre intervalles on a

$$a' = avb' \text{ et } c' = b'vc$$

Comme a et c sont compatibles, le triplet $\{a,b',c\}$ est consistant. Il admet donc une borne supérieure $d' = avb'vc$. Mais

$$ \begin{cases} d' = avcvb' = (avc) \vee (cvb') = (avc) \vee c' \\ d' = avcvb' = (avc) \vee (avb') = (avc) \vee a' \end{cases} $$
Posons $avc = d$. Comme $b'$ n'est dominé ni par $a$ ni par $d$ ni par $c$, d'après la proposition précédente $b'$ n'est pas dominé par $avc$. Donc $d'$ est distinct de $d$ et par conséquent $d \prec d'$ par la propriété C. On a donc le résultat $[a,a'] \leq [d,d'] \geq [c,c']$ []

**Définition D-5.1** Nous appellerons désormais domaine de calcul concret un domaine de calcul possédant les propriétés I, C, Q et R.

**Lemme L-5.1** Dans un domaine de calcul concret, deux intervalles premiers distincts $[a,a']$ et $[b,b']$ sont projectifsssi il existe une suite "en zig-zag" $\{[x_0,x'_0],[x_1,x'_1],\cdots[x_n,x'_n]\}$ d'intervalle premiers c.à.d.

$$ [a,a']=[x_0,x'_0] \text{ et } [b,b']=[x_n,x'_n] \quad \begin{cases} [a,a']>[x_1,x'_1]>[x_2,x'_2]>[x_3,x'_3]\cdots[x_n,x'_n] \\ [a,a']>[x_1,x'_1]<[x_2,x'_2]>[x_3,x'_3]\cdots[x_n,x'_n] \end{cases} \quad (Z_1) $$

vérifiant en outre la propriété

$$ \forall i \in [0,n-2] \quad [x_i,x_i']>[x_{i+1},x_{i+1}']>[x_{i+2},x_{i+2}'] \Rightarrow x_i \neq x_{i+2} \quad (Z_2) $$

**Démonstration** : La démonstration se fait par récurrence sur la longueur de la suite de transpositions utilisée pour aller de $[a,a']$ à $[b,b']$. Si $[a,a'] \nleq [b,b']$ la propriété est immédiate. Supposons la propriété vraie pour deux intervalles premiers projectifs entre lesquels il existe une suite d'intervalle transposés de longueur $n-1$ au plus et supposons

$$ [a,a'] \nleq [x_1,x_1'] \cdots [x_{n-1},x_{n-1}'] \nleq [b,b'] $$

Par hypothèse de récurrence, il existe une suite $[[y_1,y'_1],\cdots[y_e,y'_e]]$ "en zig-zag" entre $[x_1,x'_1]$ et $[b,b']$. Deux cas sont alors possibles :

**Cas 1 :** $[x_1,x'_1]<[y_1,y'_1]>[y_2,y'_2]<\cdots[b,b']$

**Sous cas 1 :** $[a,a'] \leq [x_1,x'_1]$. Alors on a aussi $[a,a'] \leq [y_1,y'_1]$ puisque $\leq$ est une relation transitive et $[a,a']<[y_1,y'_1]<\cdots[b,b']$

**Sous cas 2 :** $[a,a']>[x_1,x'_1]$. Alors si $a \neq y_1$ la suite $\{[a,a'],[x_1,x'_1],[y,y'_1]\cdots[b,b']\}$ satisfait la condition $Z_2$.
Sinon, par la proposition précédente on a

$[a,a']<[avy_1, a_1vy_1]>[y_1y_1]$
et la suite $[[a,a'],[avy_1,a'vy_1],[y_2,y_2]^{\cdot\cdot\cdot}]$ est une suite
"en zig-zag".

Si $y_3$ existe on a $y_1\#y_3$ donc <u>a fortiori</u> $avy_1\#y_3$ et cette suite
vérifie $Z_2$.

Cas 2 : $[x_1,x_1']>[y_1,y_1']< [y_2,y_2']^{\cdot\cdot\cdot} [b,b']$

Sous cas 1 : [a,a']<[$x_1,x_1$']$. Alors la suite
$[[a,a'],[x_1,x_1'],[y_1,y_1']^{\cdot\cdot\cdot}[b,b']]$ est une suite en zig-zag
acceptable.

Sous cas 2 : [a,a']≥[$x_1,x_1$']$. Alors, par transitivité de ≤, on
a [a,a']>[y₁,y₁'] et la suite [[a,a'],[y₁,y₁'],[y₂,y₂']^{\cdot\cdot\cdot}[b,b']]
est une suite en zig-zag. Comme on avait x₁\#y₂ on a sûrement a\#y₂
la suite vérifie la condition Z₂. □

Corollaire C-5.3 Si un domaine de calcul concret est un *treillis*, deux intervalles premiers [a,a'] et [b,b'] sont projectifs ssi il existe un intervalle premier [c,c'] avec

$[a, a'] \leq [c, c'] \geq [b, b']$

Démonstration : Puisque deux éléments ne peuvent être incompatibles, les seules suites d'intervalles premiers vérifiant $Z_1$ et $Z_2$ entre deux intervalles distincts $[a,a']$ et $[b,b']$ sont de l'une des formes suivantes :

1. $[a,a']<[b,b']$

2. $[a,a']>[b,b']$

3. $[a,a']<[c,c']>[b,b']$

En rassemblant ces trois cas avec celui où [a,a'] et[b,b'] sont
identiques, on a bien toujours [a,a']≤[c,c']≥[b,b)]. La réciproque est
triviale. □

Théorème T-5.1 Lorsqu'un domaine de calcul est un treillis et vérifie les propriétés I et C, la propriété R est équivalente à la propriété R_T :
**Propriété R<sub>T</sub> :**

Aucun sous-treillis n'est isomorphe au treillis de la figure F-5.1.

**Démonstration** : Nous savons déjà par le corollaire C-5.2 que R entraîne R<sub>T</sub>.
Supposons donc maintenant la propriété R<sub>T</sub> vraie. Soient [a,x] et [a,y] deux
intervalles premiers projectifs. Par le corollaire C-5.3, il existe un intervalle premier [c,c'] avec

$$[a, x] \leq [c, c'] \geq [a, y]$$

Nous allons raisonner par récurrence sur la longueur $\delta(a,c)$ des
chaines maximales de a à c pour démontrer qu'une telle configuration implique
$x=y$ lorsque $a \leq c$, puis par continuité pour obtenir le résultat général.

**Cas $\delta(a,c)=0$ :** On a alors $a=c$ et $c'=x\vee c=x\wedge a=x$ ainsi que $c'=y\vee c=y\wedge a=y$.
Par suite $x=y$.

**Cas $\delta(a,c)=1$ :** Alors $\delta(a,c')=2$. Comme $c\vee x \neq c$ et $c\wedge y \neq c$, nécessairement $c \neq x$ et $c \neq y$. On ne peut avoir l'égalité $c'=x\vee y$ sinon le sous-treillis constitué par les éléments $a,x,c,y,c\vee y$ serait isomorphe au treillis de la figure F-5.1. Par suite $x\vee y < c'$, ce qui entraine $\delta(a,x\vee y) \leq 1$. Donc x et y sont comparables. Comme ils couvrent tous deux a, ils sont alors égaux.

**Cas $\delta(a,c)=n>1$ :** Il existe alors un certain $d$ avec

$$a < d \leq c \text{ donc } \delta(d,c) = n - 1$$

Comme $a = x \wedge c = x \wedge d$ et $a = y \wedge c = y \wedge d$, on peut appliquer la propriété C :

$$d < d \vee x \text{ et } d < d \vee y$$

On obtient immédiatement

$$[d, d \vee x] \leq [c, c'] \geq [d, d \vee y]$$

Par hypothèse de récurrence $d \vee x = d \vee y$. Mais alors si $x$ et $y$ sont
distincts le treillis constitué par les éléments $a,x,y,d,d \vee x$ est isomorphe
au treillis de la figure F-5.1. Par conséquent on doit encore avoir $x=y$.

Finalement, d'après la proposition P-5.1, si $[a,x] \leq [c,c'] \geq [a,y]$ il existe un intervalle premier $[\gamma, \gamma']$ avec $a \leq \gamma$ et $[a,x] \leq [\gamma, \gamma'] \geq [a,y]$. Par conséquent on a là encore $x=y$. $\square$

Une conséquence intéressante de la propriété R<sub>T</sub> est d'exclure
un domaine comme celui de la figure F-3.5. Plus précisément :
**Proposition P-5.4** : Dans un domaine de calcul concret, si $[x,y]$ est un intervalle de hauteur n, il contient au maximum n éléments couvrant x.

**Démonstration** : Nous montrons à nouveau ce résultat par récurrence sur la hauteur de l'intervalle $[x,y]$. Le résultat est immédiat si $x=y$ ou $x<y$. Si toutes les chaines maximales de x à y ont pour longueur 2, choisissons deux éléments a et b couvrant x. S'ils sont distincts on a, par la propriété (1) l'égalité $avb=y$. La propriété $R_T$ exclut alors qu'un troisième élément c distinct des deux premiers puisse couvrir x.

Dans le cas général, supposons que toutes les chaines maximales de x à y aient pour longueur n avec $n>2$. Choisissons un élément t quelconque vérifiant

$$x<t\le y$$

L'intervalle $[t,y]$ est de hauteur $n-1$ et par hypothèse de récurrence, il y a au plus $n-1$ éléments couvrant $t$ dans cet intervalle.

<figure><img src="image_29.png" /><figcaption>figure F-5.5.</figcaption></figure>

La fonction qui a tout élément z de $[x,y]$ couvrant x et distinct de t associe l'élément zvt est une injection par la propriété $R_T$. Par suite il y a au plus $n-1$ éléments distincts de t qui couvrent x dans $[x,y]$. En rajoutant l'élément t, le résultat est établi. []

**Corollaire C-5.4** : Dans un domaine concret, si $x<y$ l'intervalle $[x,y]$ ne comporte qu'un nombre fini d'éléments.

**Démonstration** : Ici encore on procède par récurrence sur la longueur $\delta(x,y)$ de toutes les chaines maximales de x à y. Si $\delta(x,y)=0$ ou $\delta(x,y)=1$, le résultat est immédiat. Supposons $\delta(x,y)=n>1$. Alors, pour tout a couvrant x dans $[x,y]$.
il y a, par hypothèse de récurrence un nombre fini d'éléments dans [a,y].
Comme le nombre d'éléments couvrant x dans [x,y] est fini, il y a bien un
nombre fini d'éléments dans [x,y].

**Corollaire C-5.5** : Dans un domaine concret, un élément fini domine un nombre fini d'éléments. □

**Remarque** : Nous nous préoccupons peu d'indépendance entre les axiomes des domaines de calcul et les diverses propriétés que nous avons étudié jusqu'ici. On peut toutefois remarquer ici que les propriétés C et $R_T$ entrainent respectivement la complétude sous condition et la cohérence, ce qui en un certain sens constitue un argument supplémentaire pour ces deux axiomes. Comme la propriété de cohérence a été relativement peu étudiée dans la littérature, nous prouvons qu'elle n'est pas indépendante des propriétés I,C, Q et $R_T$.

**Proposition P-5.5.** Si un ordre partiel inductif, complet sous condition possède les propriétés I,C,Q et $R_T$, il est aussi cohérent.

**Démonstration** : En vertu de la proposition A-P.2, il suffit de montrer que tout triplet a,b,c consistant par paires admet une borne supérieure. Nous raisonnerons par récurrence sur $\delta(a^b^c, a)$.

a) **Cas de base** : Si $\delta(a^b^c, a)=0$, alors bvc domine a,b et c.
Si $\delta(a^b^c, a)=1$, supposons que a soit incompatible avec bvc.

<figure><img src="image_30.png" /><figcaption>figure F-5.6.</figcaption></figure>

Par la propriété Q, puisque $a^b^c=a^c(b^c)$ il existe t vérifiant
$a^b^c \le t \le b^c$ et $a \# t$.
Mais d'après la proposition P-5.2 (dont la preuve ne repose pas sur l'hypothèse de cohérence !), que l'on applique puisque $a^\wedge b^\wedge c \leq b^\wedge c$ :
ou bien $t \leq b$ ou bien $t \leq c$.

Dans les deux cas, l'ensemble $\{a,b,c\}$ ne peut être consistant par paires : si t est par exemple majoré par b, cet élément ne peut être compatible avec a. Par suite on a bien $a^\wedge (b^\wedge c)$ et, comme le domaine est complet sous condition, la borne supérieure $a^\wedge (b^\wedge c)$ existe.

b) **Pas de récurrence** : Supposons la propriété vraie lorsque $\delta(a^\wedge b^\wedge c, a) < n \ge 1$ et supposons $\delta(a^\wedge b^\wedge c, a) = n$. Soit

$$a^\wedge b^\wedge c = x_0 < x_1 < x_2 \cdots < x_{n-1} < x_n = a$$

une chaîne maximale de $a^\wedge b^\wedge c$ jusqu'à a. Comme le triplet $\{a,b,c\}$ est consistant par paires, il en est de même du triplet $\{x_{n-1}, b, c\}$. Par hypothèse de récurrence, il admet une borne supérieure $x_{n-1}^{\vee b^\wedge c}$. On applique alors l'argument du cas de base au triplet $\{a, x_{n-1}^{\vee b}, x_{n-1}^{\vee c}\}$. Mais $a^\wedge x_{n-1}^{\vee b^\wedge c} = a^\wedge b^\wedge c$.

c) **Argument de continuité** : Si a n'est pas fini par rapport à $a^\wedge b^\wedge c$, soit $\alpha$ un approximant quelconque de a. Le triplet $\{a,b,c\}$ est consistant par paires donc $a^\wedge (b^\wedge c)$ existe. Dans la section supérieure $[a^\wedge b^\wedge c)$ on a alors :

$$\bigcup_{\alpha \in A(a)} (\alpha^\vee (b^\wedge c)) = \left( \bigcup_{\alpha \in A(a)} \alpha \right)^\vee (b^\wedge c)$$

Or par algébricité on a aussi :

$$\bigcup_{\alpha \in A(a)} \alpha = a$$

Donc $a^\wedge b^\wedge c$ existe. $\square$

Nous revenons maintenant à notre objectif principal, l'étude des conséquences de la propriété R.

**Lemma L-5.1** Soient x et y deux éléments compatibles d'un domaine concret. Alors $[x,x']$ est un intervalle premier inclus dans $[x,xvy]$, il existe un intervalle premier $[u,u']$ inclus dans $[x^\wedge y, y]$ qui lui est projectif.

**Démonstration** : Remarquons d'abord qu'on ne peut avoir $y \le x$ puisqu'alors on aurait $xvy = x$ et l'intervalle premier $[x,x']$ ne pourrait être inclus dans l'intervalle $[x,xvy]$. Raisonnons maintenant par récurrence sur la longueur $\delta(x^\wedge y, y)$ des chaînes maximales de $x^\wedge y$ à y.
a) **Cas de base** : $\delta(x^\Lambda, y)=1$, c'est à dire $x^\Lambda y<x$. Par la propriété C on a immédiatement $x<x^\Lambda y$. Comme on a aussi $x<x^\Lambda \le x^\Lambda y$ on en déduit $x' = x^\Lambda y$. Les intervalles $[x^\Lambda y, y]$ et $[x, x']$ sont donc transposés.

b) **Pas de récurrence** : Supposons $\delta(x^\Lambda, y)=n$ avec $n>1$. Choisissons un élément quelconque $v$ couvert par $y$. D'après le lemme L-3.1, on a $v^\Lambda x \subset v^\Lambda x'$.

Distinguons ces deux cas.

**Cas 1** : $v^\Lambda x = v^\Lambda x'$. On applique alors l'hypothèse de récurrence puisqu'alors $x^\Lambda v = x^\Lambda y$ donc $\delta(x^\Lambda v, v) = \delta(x^\Lambda y, v)=n-1$. Il existe donc un intervalle $[u, u']$ inclus dans $[x^\Lambda y, v]$, donc a fortiori dans $[x^\Lambda y, y]$ et projectif avec $[x, x']$.

**Cas 2** : $v^\Lambda x \subset v^\Lambda x'$. Remarquons alors que y n'est pas dominé par $v^\Lambda x$ car sinon on aurait $v^\Lambda x^\Lambda y = x^\Lambda y = v^\Lambda x$ et $v^\Lambda x \subset v^\Lambda x' \le x^\Lambda y = v^\Lambda x$

ce qui est impossible. Par conséquent $(v^\Lambda x)^\Lambda y = v$ et l'on peut appliquer la propriété C :

$v^\Lambda x \subset v^\Lambda x^\Lambda y = x^\Lambda y$

Or
$$v^\Lambda x \subset v^\Lambda x' \le x^\Lambda y$$
donc
$$v^\Lambda x' = x^\Lambda y = (v^\Lambda x) y$$
c'est à dire
$$[x, x'] \le [v^\Lambda x, v^\Lambda x'] \ge [v, y]$$

ce qui conclut la démonstration dans le cas où $\delta(x^\Lambda, y)$ est fini.

<figure><img src="image_31.png" /><figcaption>figure F-5.7.</figcaption></figure>

c) Si maintenant y n'est pas fini par rapport à $x^\Lambda y$, il existe néanmoins un élément $d \in A(y)$ avec $x^\Lambda y \supset d$ et $x<x^\Lambda \le x^\Lambda d$ et l'on peut appliquer les résultats qui précèdent aux éléments $x, x'$ et $d$.
**Remarques** : 1. Cette démonstration n'utilise pas la propriété R. Nous présentons ce résultat dans cette section parce que c'est ici que nous y en avons besoin.

2. En fait, nous pouvons montrer, au prix d'une très légère adaptation du raisonnement par récurrence choisi qu'il existe un intervalle premier $[t,t']$ avec $[x,x'] \le [t,t'] \ge [u,u']$.

**Corollaire C-5.6.** Dans un domaine concret, si $[x,x']$ est un intervalle premier inclus dans $[1,a]$, il existe un intervalle premier qui lui est projectif inclus soit dans $[1,a]$ soit dans $[1,b]$.

**Démonstration** : En appliquant le lemme L-3.1 on obtient

$$avx \prec avx' \text{ et } bvx \prec bvx'$$

**Cas 1 :** $avx \prec avx'$ et $bvx \prec bvx'$ Alors on a

$$[avx, avx] \supseteq [x, x'] \le [bvx, bvx']$$

Par la proposition P-5.3, puisque $(avx) \uparrow (bvx)$
$[avx, avx'] \le [avbvx, avbvx'] \ge [bvx, bvx']$

Mais il y a là contradiction puisque $avb = avbvx = avbvx'$, donc l'intervalle $[avbvx, avbvx']$ n'est pas premier. Ce cas ne peut donc se produire.

**Cas 2 :** $avx = avx'$ (le cas $bvx = bvx'$ est symétrique).

Alors $[x,x']$ est un intervalle premier inclus dans $[x,x']$. D'après le lemme précédent, il existe donc un intervalle premier $[u,u']$ inclus dans $[x^a,a]$ donc $a$ fortiori dans $[1,a]$ avec $[x,x'] \sim [u,u']$. $\square$

**Lemme L-5.2** Soient $[x,x']$ et $[z,z']$ deux intervalles premiers projectifs dans un domaine de calcul concret. Si il existe un intervalle premier $[y,y']$ projectif avec $[x,x']$ dans $[1,x]$, il existe un intervalle premier projectif avec $[z,z']$ dans $[1,z]$.

**Démonstration** : On procède par récurrence sur la longueur Z de la suite en zig-zag d'intervalle premiers transposés entre $[x,x']$ et $[z,z']$. Si Z=0, les intervalles $[x,x']$ et $[z,z']$ sont confondus et la propriété est évidente. Supposons maintenant Z = n(n>0). Deux cas sont possibles suivant la forme de la suite en zig-zag
**Cas 2.2.** $x_1vy = x_1vy'$. On est alors en droit d'appliquer le lemme L-5.1. Il existe un intervalle premier $[u,u']$ projectif avec $[y,y']$ dans $[x_1vy,x_1]$. Par suite $[u,u']~[x_1,x_1']$. On applique alors l'hypothèse de récurrence : il existe un intervalle premier $[t,t']$ dans $[\perp,z]$ avec $[u,u']~[t,t']$ et par conséquent $[y,y']~[t,t']$ □

**Théorème T-5.1** Si $[x,x']$ est un intervalle premier dans un domaine concret, l'intervalle $[\perp,x]$ ne contient aucun intervalle équipollent $[x,x']$.

**Démonstration** : A. Nous démontrons d'abord qu'il ne peut exister d'intervalle premier $[y,y']$ dans $[\perp,x]$ avec $[x,x']~[y,y']$.

La démonstration se fait par récurrence sur $h(x)$. Si $h(x)=0$ la propriété est immédiate. Si $h(x)=n(n>0)$, supposons qu'il existe $[y,y']~[x,x']$ avec $[y,y']$ inclus dans $[\perp,x]$.

D'après le lemme précédent, il existe $[t,t']$ projectif avec $[y,y']$ dans $[\perp,y]$. Or $h(y)<h(x)$. Donc par hypothèse de récurrence, ceci ne peut se produire. Par conséquent la propriété est démontrée pour tout $x$ fini.

Si maintenant $h(x)$ est infini, il existe certainement, par la proposition P-3.1 un intervalle premier à extrémité finies $[n,n']$ avec $[n,n']\le[y,y']$

Dans la section supérieure $[n')$, il existe aussi un intervalle $[\xi,\xi']$ fini avec $[\xi,\xi']\le[x,x']$.

Les intervalles premiers $[n,n']$ et $[\xi,\xi']$ sont maintenant des intervalles projectifs à extrémités finies et le raisonnement ci-dessus s'applique

B. Montrons maintenant qu'il ne peut y avoir d'intervalle premier équipollent à $[x,x']$ dans $[\perp,x]$. Supposons qu'un tel intervalle $[y,y']$ existe :

$[y,y']\approx[x,x']$

Par suite il existe un intervalle $[x,x'']$ avec $[y,y']~[x,x'']$.

Mais le résultat de la partie A exclut cette possibilité. □
Cas 1 : [x,x']<[x₁,x₁']>...[z,z']

Dans ce cas l'intervalle [y,y'] est inclus dans [1,x₁].

Par hypothèse de récurrence, il existe un intervalle premier [t,t'] dans
[1,z] avec [t,t']~[y,y'] puisque la suite en zig-zag de [x₁,x₁'] à [z,z'] est
de longueur n-1.

Cas 2 : [x, x']>[x₁, x₁']<...[z, z'].

D'après le lemme VI.3.1, puisque x₁ et y sont compatibles deux cas
sont possibles puisque x₁vy=<x₁vy'.

Cas 2.1. x₁vy<x₁vy'

<figure><img src="image_32.png" /><figcaption>figure F-5.8.</figcaption></figure>

Puisque x₁ et y sont tous deux dominés par x, il en est de même
de x₁vy. Par conséquent x₁vy ne domine pas x₁' sinon x₁' serait dominé par x
et on ne pourrait avoir x<x₁'vx.

Donc $x_1 = (x_1 vy) \wedge x_1'$. Alors par la propriété C :

$$
x_1 vy \prec x_1 vyvx_1' = x_1' vy
$$

Or [x₁ vy, x₁ vy']~[y, y']~[x, x']~[x₁ vy, x₁ vy'].

Par la propriété $\hat{R}$ on doit avoir :

$$
x_1 vy' = x_1 vy
$$

Mais alors $x_1' \le x_1 vy' \le x$ et on ne peut avoir $x < x_1' vy$.

Il y a donc une contradiction qui indique que ce cas ne peut se produire.
Nous avons dégagé, dans les cinq premiers paragraphes de ce chapitre les propriétés essentielles que doit satisfaire un domaine de calcul pour qu'il puisse être, de façon plausible, considéré comme un domaine d'objets de base plutôt que d'objets fonctionnels. Le développement mathématique de ces propriétés est cohérent avec notre intuition. Cependant; il faut maintenant justifier que celles-ci sont suffisantes pour caractériser véritalement une notion de domaine de calcul concret. C'est là le rôle des sections suivantes qui exposent une théorie de la représentation pour les domaines de calcul concrets.

## I.6. La notion de matrice d'information

Nous faisons d'abord apparaître les faits essentiels sur lesquels va s'appuyer notre théorie de la représentation.

**Définition D-6.1.** On appelle *cellule* une classe d'équivalence d'intervalle premiers équipollents.

**Notation** : Soit $[x,x']$ un intervalle premier. On note $d[x,x']$ la classe d'équivalence de $[x,x']$ selon la relation de projectivité (décision associée à $[x,x']$) et $c[x,x']$ la classe d'équivalence de $[x,x']$ selon la relation d'équipollence.

**Définition D-6.2** Si $[x,x']$ est un intervalle premier et si a domine $x'$, on dit que a occupe la cellule $c[x,x']$ et contient la décision $d[x,x']$. On note alors

$$ \Gamma(a) = \{c[x, x'] | x < x' \text{ et } x' \le a\} $$

$$ \Delta(a) = \{d[x, x'] | x < x' \text{ et } x' \le a\} $$

**Proposition P-6.1** Pour tout a,

$$ \Gamma(a) = \{c[x, x'] | x < x' \text{ et } x' \in A(a)\} $$

$$ \Delta(a) = \{d[x, x'] | x < x' \text{ et } x' \in A(a)\} $$

**Démonstration** : 'Ce résultat est une simple application de la proposition P-3.1. Pour tout intervalle premier $[y,y']$ il existe un intervalle premier $[x,x']$ à extrémités finies vérifiant
$$ [x,x'] \le [y,y'] $$
$$
\begin{align*}
\text{et donc} \qquad & c[x,x'] = c[y,y'] \\
& d[x,x'] = d[y,y']
\end{align*}
$$

Puisque y' est dominé par a il en est de même de x'. Comme x' est
fini, cet élément est bien un approximant de a.

**Proposition P-6.2** Soit X un sous ensemble consistant d'un domaine concret.
On a les égalités suivantes :

$$
\begin{cases}
\Gamma(\bigcup X) = \bigcup_{x \in X} \Gamma(x) \\
\Delta(\bigcup X) = \bigcup_{x \in X} \Delta(x)
\end{cases}
$$

Démonstration : Tous d'abord, par cohérence, si X est consistant, il admet
une borne supérieure ⋃X.

Mais, par définition de Γ et Δ

$$
\begin{cases}
x \le y \Rightarrow \Gamma(x) \in \Gamma(y) \\
x \le y \Rightarrow \Delta(x) \in \Delta(y)
\end{cases}
$$

On a donc immédiatement

$$
\left\{
\begin{array}{l}
\bigcup_{x \in X} \Gamma(x) \subset \Gamma(\bigcup X) \\
\\
\bigcup_{x \in X} \Delta(x) \subset \Delta(\bigcup X)
\end{array}
\right.
$$

Montrons maintenant les inégalités inverses par récurrence sur le
cardinal de X si X est fini puis continuité.

a) **Cas de base** : Si $|X|=0$ alors, $\bigcup_{x=1}^{|X|} \Gamma(\underline{\Gamma}(x)) = \emptyset$
Si $|X|=1$ alors, $X=\{x\}$ et $\bigcup_{x=x}^{|X|} \Delta(\underline{\Delta}(x)) = \emptyset$
On a donc évidemment $\Gamma(x) \supset \Gamma(\bigcup_{x=x}^{|X|} \underline{\Gamma}(x))$ et $\Delta(x) \supset \Delta(\bigcup_{x=x}^{|X|} \underline{\Delta}(x))$

b) **Pas de récurrence** : Soit $X = \{x_1, \dots, x_{n-1}, x_n\}$ ($n>1$)
Si X est consistant il en est de même de $X' = \{x_1, \dots, x_{n-1}\}$
Par hypothèse de récurrence

$$
\left\{
\begin{array}{l}
\bigcup_{x \in X'} \Gamma(x) \supset \Gamma(\bigcup_{x \in X'} \underline{\Gamma}(x')) \\
\\
\bigcup_{x \in X'} \Delta(x) \supset \Delta(\bigcup_{x \in X'} \underline{\Delta}(x'))
\end{array}
\right.
$$
Comme $\bigcup X = (\bigcup K')v_{X_n}$, d'après le corollaire VI.5.6 tout intervalle $[x,x']$ inclus dans $[1, \bigcup X]$ est projectif avec un intervalle premier inclus soit dans $[1, \bigcup X]$ soit dans $[1, x_n]$. Par suite

$$ 
\begin{cases} 
\Gamma(\bigcup X) \subset \Gamma(\bigcup X') \cup \Gamma(x_n) \\ 
\Delta(\bigcup X) \subset \Delta(\bigcup X') \cup \Delta(x_n) 
\end{cases} 
$$

En utilisant l'hypothèse de récurrence on obtient bien

$$ \Gamma(\bigcup X) \subset \bigcup_{x \in X} \Gamma(x) $$

$$ \Delta(\bigcup X) \subset \bigcup_{x \in X} \Delta(x) $$

c) Argument de continuité : Soit $[x,x']$ un intervalle premier à extrémités finies inclus dans $[1, \bigcup X]$. Puisque $x'$ est fini dominé par $\bigcup X$, il existe un sous ensemble fini $Y$ de $X$ dont la borne supérieure domine $x'$ puisque l'ensemble obtenu en adjoignant à $X$ toutes les bornes supérieures de ses parties finies est dirigé. Par suite on a

$$ 
\begin{cases} 
c[x,x'] \in \bigcup_{y \in Y} \Gamma(y) \\ 
d[x,x'] \in \bigcup_{y \in Y} \Delta(y) 
\end{cases} 
$$

d'où l'on déduit finalement

$$ 
\begin{cases} 
\Gamma(\bigcup X) \subset \bigcup_{x \in X} \Gamma(x) \\ 
\Delta(\bigcup X) \subset \bigcup_{x \in X} \Delta(x) 
\end{cases} 
\square $$

Dans un domaine concret, on a maintenant une propriété beaucoup plus forte que la condition de Jordan-Dedekind.

**Lemme L-6.1** Soit $x$ un élément quelconque d'un domaine concret et $\{1 = x_0, x_1, \dots, x_n, \dots\}$ une chaine maximale entre $1$ et $x$. On a les égalités :

$$ \Gamma(x) = \{c[x_i, x_{i+1}] \mid i \ge 0\} $$

$$ \Delta(x) = \{d[x_i, x_{i+1}] \mid i \ge 0\} $$

**Démonstration** : Ces égalités se démontrent par récurrence sur $h(x)$.
a) **Cas de base** : Si $h(x)=0$ c'est que $x=1$ et par conséquent
$\Gamma(1) = \Delta(1) = \emptyset$. Si $h(x)=1$, l'élément $x$ est un atome et la
propriété est la aussi immédiate.

b) **Pas de récurrence** : Supposons maintenant $h(x)=n(n>1)$. Soit $[y,y']$ un intervalle premier quelconque dans $[1,x]$ comme $y'$ et $x_{n-1}$ sont compatibles, d'après le lemme L-3.1 on a
$$x_{n-1}^{\vee y} \le x_{n-1}^{\vee y'}$$
et l'on envisage donc deux cas.

**Cas 1 :** $x_{n-1}^{\vee y} = x_{n-1}^{\vee y'}$. Dans ce cas par le lemme L-5.1 il existe un intervalle premier $[z,z']$ dans $[1,x_{n-1}]$ projectif avec $[y,y']$. Comme $x_{n-1}$ est de hauteur $n-1$, on peut appliquer l'hypothèse de récurrence. Il existe par conséquent un intervalle $[x_k, x_{k+1}]$ avec $k \le n-2$ et
$$d[z,z'] = d[x_k, x_{k+1}]$$
c'est à dire
$$[z,z'] \subset [x_k, x_{k+1}]$$

$$\text{Par conséquent } \begin{cases} d[y,y'] \in \{d[x_i, x_{i+1}] | i \ge 0\} \\ c[y,y'] \in \{c[x_i, x_{i+1}] | i \ge 0\} \end{cases}$$

**Cas 2 :** $x_{n-1}^{\vee y} < x_{n-1}^{\vee y'}$. Dans ce cas l'intervalle premier $[x_{n-1}^{\vee y}, x_{n-1}^{\vee y'}]$ est inclus dans l'intervalle premier $[x_{n-1}, x]$ ce qui implique

$$\begin{cases} x_{n-1} = x_{n-1}^{\vee y} \\ x = x_{n-1}^{\vee y'} \end{cases}$$
c'est à dire
$$[y,y'] \le [x_{n-1}, x]$$

et là encore

$$\begin{cases} d[y,y'] \in \{d[x_i, x_{i+1}] | i \ge 0\} \\ c[y,y'] \in \{c[x_i, x_{i+1}] | i \ge 0\} \end{cases}$$

c) **Argument de continuité** : Si $x$ n'est pas fini, nous savons cependant par la proposition P-6.1 que
$$\Gamma(x) = \{c[y,y']|[y,y'] \text{ premier et } y,y' \in A(x)\}$$
$$\Delta(x) = \{d[y,y']|[y,y'] \text{ premier et } y,y' \in A(x)\}$$
Soit alors [y,y'] un intervalle premier à extrémités finies inclus dans [1,x]. Il existe un élément fini $x_n$ de la chaine de 1 à x avec $y' \le x_n$ puisque toute chaine est un ensemble dirigé. Par suite on peut appliquer le résultat du cas fini et trouver un intervalle $[x_i, x_{i+1}]$ ($i \le n-1$) projectif avec [y,y'].

**Corollaire C-6.1** Pour tout x on a

$$h(x) := |\Gamma(x)| = |\Delta(x)|$$

**Démonstration** : Supposons d'abord x fini. D'après le lemme ci-dessus

$$|\Gamma(x)| \le h(x)$$

$$|\Delta(x)| \le h(x)$$

mais d'après le théorème T-5.1, une chaine maximale ne contient pas deux intervalles premiers équipollents. On a donc aussi

$$h(x) \le |\Gamma(x)|$$

$$h(x) \le |\Delta(x)|$$

Si x est infini, on obtient trivialment, en appliquant le théorème T-5.1

$$|\Gamma(x)| = \infty \text{ et } |\Delta(x)| = \infty \quad \square$$

Nous montrons maintenant un résultat technique beaucoup plus fort que la proposition P-5.3.

**Proposition P-6.3** Soient [a,a'] et [b,b'] deux intervalles premiers projectifs dans un domaine concret. Si a et b sont compatibles on a aussi

$$[a, a'] \le [c, c'] \ge [b, b']$$

$$\text{avec } c = avb \text{ et } c' = a'vc = avc'$$

**Démonstration** : Montrons d'abord que a' et avb sont compatibles. Si en effet on avait a' \# avb, il existerait un élément t vérifiant

$$a < t \le avb$$

$$\text{et } t \ne a'$$
Par le lemme L-5.1, il existerait alors un intervalle $[u,u']$ dans $[1,b]$ avec

$$[u,u'] \sim [a,t]$$

par conséquent $[u,u'] \sim [a,a']$

donc puisque $[a,a'] \sim [b,b']$

$$[u,u'] \sim [b,b']$$

ce qui est exclu par le théorème L-5.1. De manière symétrique on montre que l'on a aussi $b'^{\uparrow}c$. Le même raisonnement prouve aussi que $a'$ n'est pas dominé par $c$ et que $b'$ n'est pas dominé par $avb$. Par la propriété C on en déduit

$$ \begin{cases} c \leq avbva' = a'vb \\ c \leq avb' \end{cases} $$

Or les intervalles premiers $[avb,a'vb]$ et $[avb,avb']$ sont projectifs. Par la propriété R on en déduit donc

$$a'vb = avb' \quad \square$$

**Corollaire C-6.2** Si $[x,x']$ et $[y,y']$ sont deux intervalles premiers équipollents contenus dans un même intervalle $[1,z]$, ils sont projectifs.

**Démonstration** : De $[x,x'] \sim [y,y']$ on déduit qu'il existe un intervalle premier $[y,y']$ avec

$$[x,x'] \sim [y,y'] \sim [y,y']$$

Mais $x$ et $y$ sont compatibles donc, par la proposition précédente

$$[x,x'] \leq [xvy,x'vy] \geq [y,y']$$

Or $x'vy$ est dominé par $z$, donc $y''$ est dominé par $z$. Comme $y'$ est lui aussi dominé par $z$, on a nécessairement $y' = y''$ donc

$$[x,x'] \sim [y,y'] \quad \square$$

**Théorème T-6.1** Dans un domaine concret

$$x \leq y \Leftrightarrow \Delta(x) \subset \Delta(y)$$

**Démonstration** : Par définition de $\Delta$, on a

$$x \leq y \Rightarrow \Delta(x) \subset \Delta(y)$$
Nous n'avons donc que l'implication inverse à démontrer. Procédons par récurrence sur la hauteur de x.

a) **Cas de base** : Si $h(x)=0$ alors $x=1$ donc pour tout y on a $x \le y$.

b) **Pas de récurrence** : Supposons que l'on ait :

$$ \Delta(x) < \Delta(y) \Rightarrow x \le y $$

si la hauteur de x est inférieure à n et supposons $h(x)=n$.

Considérons une chaîne maximale quelconque de $1 \hat{=} x$

$$ 1 = x_0 < x_1 < x_2 \cdots < x_{n-1} < x_n = x $$

et supposons $\Delta(x) < \Delta(y)$. Puisque $x_{n-1}$ est dominé par $x$ et on a

$$ \Delta(x_{n-1}) < \Delta(x) < \Delta(y). $$

Comme $x_{n-1}$ est de hauteur $n-1$ on peut appliquer l'hypothèse de récurrence pour en déduire

$$ x_{n-1} \le y $$

Comme $d[x_{n-1}, x_n]$ appartient à $\Delta(x)$ donc à $\Delta(y)$ il existe un intervalle premier $[z, z']$ dans $[1, y]$ avec

$$ [x_{n-1}, x_n] \supseteq [z, z'] $$

Les éléments $x_{n-1}$ et $z$ sont tous deux dominés par $y$ donc compatibles et l'on peut appliquer la proposition P-6.3 :

$$ [x_{n-1}, x_n] \subseteq [x_{n-1}^V, t] \supseteq [z, z'] $$

$$ t = x_{n-1}^V z' = x_n^V z $$

Or $x_{n-1}$ et $z'$ sont tous deux dominés par $y$, il en est de même de $t$ et par conséquent de $x_n$. Comme $x_n = x$ on obtient bien

$$ x \le y $$

c) **Argument de continuité** : De $\Delta(x) < \Delta(y)$ on déduit

$$ \forall a \in A(x) \quad \Delta(a) < \Delta(y) $$

donc

$$ \forall a \in A(x) \quad a \le y $$

Par algébricité $x = \bigcup_{a \in A(x)} a$ donc $x \le y$. □
**Définition D-6.3.** Un intervalle premier $[x,x']$ est dit *minimal* ssi il est minimal au sens de la relation $\le$ entre intervalles.

**Définition D-6.4.** Un élément $x$ est dit *sup-irréductible* ssi

$$i) \quad x \neq 1$$

$$ii) \quad x = avb \implies x=a \text{ ou } x=b$$

**Proposition P-6.4.** Dans un domaine concret, pour tout intervalle premier $[x,x']$ il existe un intervalle premier $[y,y']$ avec $y$ sup-irréductible et $[y,y'] \le [x,x']$

**Démonstration** : En raison de la proposition P-3.1, il nous suffit d'étudier le cas où l'intervalle $[x,x']$ est à extrémités finies. Raisonnons alors par récurrence sur la hauteur de $x'$.

a) **Cas de base** : $h(x')=1$. L'élément $x'$ est alors un atome donc forcément sup-irréductible et la proposition est immédiate.

b) **Pas de récurrence** : Supposons $h(x')=n, n>1$. Si $x'$ est sup-irréductible la proposition est immédiate. Sinon $x' = avb$ avec

$$\begin{cases} a < x' \\ b < x' \end{cases}$$

D'après le corollaire C-5.6, il existe donc un intervalle premier $[u,u']$ inclus, soit dans $[1,a]$, soit dans $[1,b]$ avec

$$[u, u'] \supseteq [x, x']$$

Et puisque $u$ et $x$ sont tous deux dominés par $x'$, par la proposition P-6.3 :

$$[u, u'] \le [x_v u, x_v u'] \ge [x, x']$$

Comme $x_v u' \le x' \quad \text{on a } x_v u' = x' \text{ donc } x_v u = x \text{ et}$

$$[u, u'] \le [x, x']$$

Puisque $u'$ est dominé soit par $a$ soit par $b$ :

$$[u, u'] \subset [x, x']$$

donc

$$h(u') < h(x')$$
En appliquant à l'intervalle premier [u,u'] l'hypothèse de récurrence il existe un intervalle premier [y,y'] avec y' sup-irréductible et

$$[y,y'] \le [u,u']$$

donc a fortiori

$$[y,y'] \le [x,x']$$

□

**Corollaire C-6.3.** Dans un domaine concret, un intervalle premier [x,x'] est minimal ssi x' est sup-irréductible.

**Démonstration** : Si x' est sup-irréductible, soit [y,y'] un intervalle premier avec

$$[y,y'] \le [x,x']$$

$$x' = xVy'$$

Comme x est différent de x' on doit avoir y'=x'. Et par suite y = y'^xA = x'^xA = x. Donc [y,y'] = [x,x'] . Par conséquent [x,x'] est minimal. Réciproquement soit [x,x'] un intervalle minimal.

D'après la proposition précédente, il existe [y,y'] avec y' sup-irréductible et

$$[y,y'] \le [x,x']$$

Comme [x,x'] est minimal, on doit avoir [y,y'] = [x,x'] donc en particulier y' = x', ce qui montre que x' est sup-irréductible. □

**Proposition P-6.5.** Dans un domaine concret, si [x,x'] est un intervalle premier minimal, tout intervalle [x,x''] avec

$$[x,x''] = [x,x']$$

est aussi minimal.

**Démonstration** : Soit [y,y''] un intervalle premier avec

$$[y,y''] \le [x,x''] \le [x,x']$$

Puisque $\le \circ \approx = \approx \circ \le$ il existe y' tel que

$$[y,y''] = [y,y'] \le [x,x']$$

Comme [x,x'] est minimal [y,y'] = [x,x'] donc en particulier y=x. Par suite x^y'' = x donc x\le y''. Or x'' = xVy'' donc x'' = y'' et

$$[y,y''] = [x,x'']$$

Donc [x,x''], est bien minimal. □
**Définition D-6.5.** Dans un domaine concret, soient $\delta$ une décision et $\Delta$ un ensemble de décisions. On dit que $\Delta$ rend accessible $\delta$ ssi il existe un intervalle minimal $[x,x']$ avec

$$ \begin{cases} d[x,x'] = \delta \\ \Delta(x) = \Delta \end{cases} $$

D'après la proposition précédente, l'ensemble $\Delta$ rend aussi accessible toutes les décisions équipollentes avec $\delta$ et l'on est donc en droit de poser que $\Delta$ rend accessible la cellule $\gamma$ ssi il existe un intervalle minimal $[x,x']$ avec

$$ \begin{cases} c[x,x'] = \gamma \\ \Delta(x) = \Delta \end{cases} $$

**Remarques :**
1. Si l'intervalle $[x,x']$ est minimal les éléments $x$ et $x'$ sont nécessairement finis. Par conséquent, puisque $|\Delta(x)| = h(x)$, une cellule est toujours rendue accessible par un nombre fini de décisions.

2. En général, dans une même classe d'équivalence d'intervalle premiers projectifs, il existe plusieurs intervalles minimaux distincts. Par conséquent, plusieurs ensembles de décisions distincts peuvent rendre accessible une même cellule. Le cas où un seul ensemble de décisions $\Delta$ rend accessible toute cellule $\delta$ est un cas particulier très important que nous considérerons au § I.10.

Nous allons maintenant, en nous appuyant sur les notions introduites dans ce paragraphe, construire toute une classe de domaines concrets.

**Définition D-6.6.** Une matrice d'information est un quadruplet
$M = \langle \Gamma, V, \nu, E \rangle$ dans lequel

1. $\Gamma$ est un ensemble dénombrable de cellules

2. $V$ est un ensemble dénombrable quelconque

3. $\nu$ est une fonction de $\Gamma$ dans $P(V)$ qui à toute cellule $c$ dans $\Gamma$ associe le sous-ensemble $\nu(c)$ dit des valeurs possibles en $c$. Nous dirons simplement que $\nu(c)$ est le type de $c$. On appelle alors décision une paire $\langle c, v \rangle$ dans laquelle $c$ est une cellule et $v$ une valeur possible de $c$, c'est à dire :

$c \in \Gamma \text{ et } v \in \nu(c).$
Notons $\Delta_M$ l'ensemble des décisions définies par $\Gamma, V$ et $\nu$ et $F(\Delta_M)$ l'ensemble des parties finies de $\Delta_M$.

4. La fonction $E$ est définie comme une fonction de $\Gamma$ dans $P(F(\Delta_M)) - \emptyset$ dite fonction d'accessibilité de M. Si un ensemble fini de décisions $\{d_1, d_2, \dots, d_n\}$ appartient à $E(c)$, on dira que $\{d_1, d_2, \dots, d_n\}$ rend accessible la cellule c.

**Notations** : Soit $M = \langle \Gamma, V, \nu, E \rangle$ une matrice d'information, et $\Delta_M$ son ensemble de décisions. Si $d = \langle c, v \rangle$ ($e \in \Gamma, v \in V(c)$) est une décision, on dira que cette décision concerne la cellule c, et si $\{d_1, \dots, d_n\}$ est un ensemble de décisions appartenant à $E(c)$, on dira qu'il rend accessible la cellule c et la décision d. Cette dernière relation est notée

$$d_1, d_2, \dots, d_n \models d$$

Si l'ensemble vide rend accessible une cellule (ou une décision) on dit que cette cellule (ou cette décision) est initiale.

**Définition D-6.7.** Soit $M$ une matrice d'information et d'une décision de $M$. Une suite finie de décisions

$$d_0, d_1, d_2, d_3, \dots, d_{n-1}, d_n = d$$

est une preuve de d ssi pour tout $j$ avec $0 \le j \le n$, il existe un sous-ensemble $\{d_{j_1}, d_{j_2}, \dots, d_{j_k}\}$ de $\{d_0, \dots, d_{j-1}\}$ qui rend accessible $d_j$, autrement dit

$$d_{j_1}, d_{j_2}, \dots, d_{j_k} \models d_j$$

**Définition D-6.8.** Dans une matrice d'information, un sous-ensemble $X$ de décisions est connecté par un autre sous-ensemble $Y$ ssi toute décision de $X$ admet une preuve inclue dans $Y$. Si le sous-ensemble $X$ est connecté par lui-même, il est dit connecté.

**Remarques** : Si $X$ est connecté par $Y$, on doit avoir $X \subset Y$. Si $X$ est connecté par $Y$, a fortiori $X$ est connecté par tout sur-ensemble de $Y$. Si deux ensembles de décisions sont connectés, il en est de même de leur union. Une preuve est bien entendu connectée. De ces deux dernières remarques on déduit que tout sous-ensemble fini $X$ d'un ensemble connecté peut être recouvert par un sous-ensemble fini connecté : il suffit de prendre une preuve pour chaque élément de $X$.
**Définition D-6.9.** Dans une matrice d'information M, on appelle *configuration* un sous-ensemble connecté de décisions dans lequel deux décisions distinctes ne concernent pas la même cellule.

Notons $\Sigma_M$ l'ensemble des configurations de la matrice d'information M. Toute configuration $\sigma$ est une partie de $\Delta_M$ par définition et $\Sigma_M$ est naturellement ordonné par la relation d'inclusion entre configurations.

**Exemple** : Considérons la matrice $M_1 = \langle \Gamma_1, V_1, \nu_1, E_1 \rangle$ définie par

$$- \Gamma_1 = \{c_1, c_2, c_3\}$$

$$- V_1 = \{\tau\}$$

$$- \nu_1 = \lambda c \cdot \{\tau\}$$

$$- E_1(c_1) = E_1(c_2) = \{\emptyset\} \quad E_1(c_3) = \{\{c_1\}, \{c_2\}\}$$

Puisque $V_1$ n'a qu'un seul élément, l'ensemble des décisions est isomorphe à $\Gamma_1$ et l'ensemble des configurations $\Sigma_M$ comporte les sept configurations suivantes :

$$\sigma_1=\emptyset \quad \sigma_2=\{c_1\} \quad \sigma_3=\{c_2\} \quad \sigma_4=\{c_1; c_2\} \quad \sigma_5=\{c_1, c_3\} \quad \sigma_6=\{c_2, c_3\} \quad \sigma_7=\{c_1, c_2, c_3\}$$

Le diagramme de l'ordre partiel $\langle \Sigma_M; c \rangle$ est représenté sur la figure F-6.1.

<figure><img src="image_33.png" /><figcaption>figure F-6.1.</figcaption></figure>

Nous avons fait grand usage des diagrammes de Hasse pour représenter des ordres partiels, de la même manière, il est utile de pouvoir représenter de façon synthétique une matrice d'information. Une telle représentation graphique n'est en fait parlante que dans le cas où toutes les cellules peuvent prendre une seule et même valeur $\tau$ (c'est à dire $V = \lambda c \cdot \{\tau\}$). Dans ce cas $\Gamma$ et $\Delta_M$ sont isomorphes et $E$ est une fonction de $\Gamma$ dans $P(F(\Gamma))$ si bien
que nous pouvons utiliser une représentation par graphe "et-ou" familière, par exemple, en intelligence artificielle. Chaque cellule de M est représentée par un noeud du graphe et si l'on a

$$c_1, c_2, \dots, c_{n-1} \uparrow c_n$$

le graphe de M comporte n-1 arêtes $c_i \cdot c_n$ et celles-ci sont reliées entre elles par un arc de cercle.

Par exemple, la matrice $M_1$ que nous venons de considérer est représentée sur la figure

<figure><img src="image_34.png" /><figcaption>figure F-6.2.</figcaption></figure>

La matrice $M_2 = \langle T_1, V_1, V_2, E_2 \rangle$ avec $E_2(c_1) = E_2(c_2) = \emptyset$ et $E_2(c_3) = \{\{c_1, c_2\}\}$ est elle représentée par

<figure><img src="image_35.png" /><figcaption>figure F-6.3.</figcaption></figure>

Des conventions simples permettent de représenter des matrices infinies de cette manière (cf. figure F-6.4).
<figure><img src="image_36.png" /></figure>

<figure><img src="image_37.png" /><figcaption>figure F-6.2</figcaption></figure>

<figure><img src="image_38.png" /></figure>

<figure><img src="image_39.png" /><figcaption>Figure F-6.4</figcaption></figure>
**Lemme L-6.2.** Dans l'ordre partiel $<\Sigma_M; c>$ des configurations d'une matrice d'information, ordonnées par l'inclusion ensembliste, deux configurations sont compatibles ssi l'ensemble $\sigma_1 u \sigma_2$ est une configuration. De plus
$$ \sigma_1 v \sigma_2 = \sigma_1 u \sigma_2. $$

**Démonstration** : Tout d'abord si $\sigma_1 u \sigma_2$ est une configuration, puisque l'on a $\sigma_1 c \sigma_1 u \sigma_2$ et $\sigma_2 c \sigma_1 u \sigma_2$ on a $\sigma_1 \dagger \sigma_2$. Supposons réciproquement $\sigma_1 \dagger \sigma_2$, c'est à dire qu'il existe une configuration $\sigma$ avec $\sigma_1 c \sigma$ et $\sigma_2 c \sigma$. Considérons alors l'ensemble de décisions $\sigma_1 u \sigma_2$. D'après une remarque faite plus haut, puisque $\sigma_1$ et $\sigma_2$ sont connectés, il en est de même de leur union. Dans l'ensemble $\sigma_1 u \sigma_2$, s'il existait deux décisions distinctes portant sur la même cellule, elles existeraient aussi dans $\sigma$ qui contient $\sigma_1 u \sigma_2$. Mais $\sigma$ est une configuration, ceci est donc impossible. Par conséquent $\sigma_1 u \sigma_2$ est une configuration. Puisque toute configuration dominant $\sigma_1$ et $\sigma_2$ doit contenir (donc dominer) $\sigma_1 u \sigma_2$ on a

$$ \sigma_1 v \sigma_2 = \sigma_1 u \sigma_2 \quad \square $$

**Remarque** : En revanche, l'intersection ensembliste de deux configurations n'est pas, en général une configuration, car ce peut être un ensemble de décisions non connecté. Par exemple, dans la matrice $M_1$ considérée ci-dessus, on a $\sigma_5 \cap \sigma_6 = \{c_3\}$ et $\{c_3\} \cap n$ est pas connecté. Donc $\sigma_5 \wedge \sigma_6 = \emptyset \neq \sigma_5 \cap \sigma_6$.

**Lemme L-6.3.** Dans l'ordre partiel $<\Sigma_M; c>$ une configuration $\sigma_2$ couvre une configuration $\sigma_1$ ssi il existe une décision d telle que $\sigma_2 = \sigma_1 w \{d\}$

**Démonstration** : Supposons d'abord que $\sigma_1$ et $\sigma_2$ soient deux configurations avec $\sigma_2 = \sigma_1 w \{d\}$. Alors $\sigma_1 c \sigma_2$ et $\sigma_1 \neq \sigma_2$. Soit $\sigma$ une configuration quelconque dans l'intervalle $[\sigma_1, \sigma_2]$, c'est à dire

$$ \sigma_1 c \sigma c \sigma_2 $$

Comme $\sigma_1$ et $\sigma_2$ ne diffèrent que par le seul élément $d$, ou bien $\sigma$ ne contient pas $d$ et $\sigma_1 = \sigma$, ou bien $\sigma$ contient $d$ et $\sigma = \sigma_2$. Par conséquent on a bien

$$ \sigma_1 < \sigma_2 $$
Réciproquement, supposons $\sigma_1<\sigma_2$. Soit d une décision quelconque dans $\sigma_2$ qui n'appartient pas à $\sigma_1$. Une telle décision existe puisque les ensembles $\sigma_1$ et $\sigma_2$ sont distincts. Comme $\sigma_2$ est connecté, la décision d admet une preuve dans $\sigma_2$ :

$$d_0, d_1, d_2, \dots, d_{n-1}, d_n = d.$$

Soit $d_j$ la première décision de cette suite qui n'appartient pas à $\sigma_1$. L'ensemble $\sigma_1 \cup \{d_j\}$ est connecté, puisque $d_j$ admet une preuve toute entière contenue dans $\sigma_1 \cup \{d_j\}$. Comme $\sigma_1 \subset \sigma_1 \cup \{d_j\} \subset \sigma_2$ et $\sigma_1 \neq \sigma_1 \cup \{d_j\}$, puisque $\sigma_2$ couvre $\sigma_1$, on doit avoir $\sigma_2 = \sigma_1 \cup \{d_j\}$.

**Théorème T-6.2.** Pour toute matrice d'information M, l'ordre partiel $\langle\Sigma_M; c\rangle$ est un domaine de calcul concret.

**Première partie** : $\langle\Sigma_M; c\rangle$ est un domaine de calcul.

1. $\langle\Sigma_M; c\rangle$ est cohérent. Soit X un ensemble de configurations consistant. Considérons l'ensemble $\sigma$ de décisions formé par la réunion de toutes les décisions de tous les éléments de X. Cet ensemble $\sigma$ est connecté puisque c'est une réunion d'ensembles connectés. Supposons qu'il contienne deux décisions distinctes concernant la même cellule. Ces deux décisions ne peuvent provenir d'un même élément de X, puisque X ne contient que des configurations. Elles ne peuvent provenir de deux éléments distincts $x_1$ et $x_2$ de X, car alors $x_1 \cup x_2$ ne serait pas une configuration, ce qui contredirait $x_1 \uparrow x_2$ par le lemme L-6.2 et, puisque X est consistant, on doit avoir $x_1 \uparrow x_2$. Par conséquent $\sigma$ est une configuration. C'est bien sur la plus petite configuration dominant tous les éléments de X. Par suite $\sigma = \bigcup X$.

2. $\langle\Sigma_M; c\rangle$ est séparable. Montrons que les configurations finies sont exactement les points isolés de $\langle\Sigma_M; c\rangle$

i) Soit X un ensemble dirigé de configurations et $\tau$ un ensemble fini de décisions avec $\tau \subset \bigcup X$. Raisonnons par récurrence sur la taille (le cardinal) de $\tau$ pour montrer $\tau \subset X \in X$.

**Cas de base** : $|\tau|=0$ c'est à dire $\tau=\emptyset$. Alors, pour tout $x$ dans X on a $\tau \subset x$.
**Pas de récurrence** : Si $|τ|=n(n>0)$ choisissons une décision d quelconque dans $τ'$ et posons $τ = τ'|_U\{d\}$. Comme $τ'$ est de taille strictement inférieure à $n$, par hypothèse de récurrence il existe un certain $x_1$ dans X avec

$$τ'|_U x_1$$

Comme d appartient à X, il existe certainement un ensemble $x_2$ dans X avec $d \in x_2$ donc $\{d\} \subset x_2$. Comme X est dirigé, il existe une configuration x dans X avec $x_1 \subset x$ et $x_2 \subset x$ et l'on a

$$τ \subset x$$

Par conséquent, puisque une configuration finie est un ensemble fini de décisions, les configurations finies sont isolées dans $<Σ_M; c>$.

ii) Soit maintenant $x$ une configuration quelconque. Si $a$ est un sous ensemble fini quelconque de $x$, nous avons remarqué que $a$ peut être recouvert par un sous-ensemble fini de $x$ connecté $\bar{a}$ qui est donc une configuration. Comme $x$ est la réunion de toutes ses parties finies on a aussi

$$x = \bigcup \{\bar{a} | a \in F(x)\}$$

Comme le membre de droite est un ensemble dirigé de configurations on a aussi

$$x = \bigcup \{\bar{a} | a \in F(x)\}$$

Par suite si $x$ est isolé, il existe une partie finie $a$ de $x$ avec $x \subset \bar{a}$

Mais comme $\bar{a} \subset x$ on a immédiatement $x = \bar{a}$ et puisque $\bar{a}$ est une configuration finie il en est de même de $x$. Tout élément isolé de $<Σ_M; c>$ est donc une configuration finie. Rassemblant les résultats de i et ii nous en concluons que les éléments isolés de $<Σ_M; c>$ sont exactement les configurations finies. Pour toute configuration $x$, l'ensemble de $\bar{A}(x)$ est bien dirigé et l'on a $x = \bigcup \bar{A}(x)$.

iii) Comme il n'existe qu'un nombre dénombrable de parties finies d'un ensemble dénombrable, nous en concluons que l'ordre partiel $<Σ_M; c>$ est séparable.

L'ordre partiel $<Σ_M; c>$ est cohérent et séparable. C'est un domaine de calcul et nous avons terminé la première partie de la démonstration du théorème.
**Deuxième partie : <Σ<sub>M</sub>; c> est un domaine de calcul concret.**
Nous vérifions, l'une après l'autre, que <Σ<sub>M</sub>; c> possède les propriétés I, C, Q et R.

**1. Propriété I :** L'ensemble des configurations finies est trivalement un idéal de <Σ<sub>M</sub>; c>. Il n'y a qu'un nombre fini de sous-ensembles d'une configuration finie, donc *a fortiori* qu'un nombre fini de configurations dominé par une configuration finie. Donc cet idéal est bien fondé.

**2. Propriété C :** Soient $\sigma_1$ et $\sigma_2$ deux configurations finies compatibles vérifiant $\sigma_1 \wedge \sigma_2 \prec \sigma_1$. D'après le lemme L-6.3, on doit avoir

$$ \sigma_1 = \sigma_1 \wedge \sigma_2 \in \{d\} $$

Par le lemme VI.6.2 si $\sigma_1 \uparrow \sigma_2$ on a $\sigma_1 \vee \sigma_2 = \sigma_1 \cup \sigma_2$. Donc

$$ \sigma_1 \vee \sigma_2 = \sigma_1 \wedge \sigma_2 \cup \{d\} \cup \sigma_2 = \sigma_2 \cup \{d\} $$

Si l'élément d appartenait à $\sigma_2$ on aurait $\sigma_1 \subset \sigma_2$ donc $\sigma_1 = \sigma_1 \wedge \sigma_2$ ce qui est exclu par hypothèse. Par suite

$$ \sigma_1 \vee \sigma_2 = \sigma_2 \in \{d\} $$

soit, par le lemme L-3.2 à nouveau

$$ \sigma_2 \prec \sigma_1 \vee \sigma_2. $$

**3. Propriété Q :** Rappelons d'abord que si deux configurations sont incompatibles, c'est que $\sigma_1 \cup \sigma_2$ n'est pas une configuration. Comme $\sigma_1 \cup \sigma_2$ est connecté, il existe deux décisions distinctes $d_1$ et $d_2$ concernant la même cellule avec $d_1 \in \sigma_1$ et $d_2 \in \sigma_2$. Soient alors deux configurations finies incompatibles $\sigma_1$ et $\sigma$ avec

$$ \sigma_1 \wedge \sigma_2 \prec \sigma_1 $$

Posons $d_1 = \langle c, x \rangle$ et $d_2 = \langle c, y \rangle$ ($x \neq y$). Puisque $\sigma_1 \wedge \sigma_2$ est dominé par $\sigma_1$ et $\sigma_2$, la configuration $\sigma_1 \wedge \sigma_2$ ne contient pas de décision concernant la cellule c. Donc $\sigma_1 = \sigma_1 \wedge \sigma_2 \in \{d_1\}$. Comme $\sigma_1$ est connecté, la décision $d_1$ admet une preuve $\{d'_0, d'_1, \dots, d'_n = d_1\}$, donc une preuve sans répétition. Par suite, puisque $d_1$ et $d_2$ concernent la même cellule, la suite est une preuve de $d_2$.
$$ d'_0, d'_1, \dots, d'_{n-1} \vdash d_2 $$
Comme les éléments $d_i^!$ ($0 \le i \le n-1$) sont dans $\sigma_1 \wedge \sigma_2$, l'ensemble
$\tau = \sigma_1 \wedge \sigma_2 \mathfrak{w}\{d_2\}$ est connecté. Puisqu'il ne contient aucune autre décision
concernant la cellule c que la décision $d_2$, l'ensemble $\tau$ est une confi-
guration. On a bien

$$
\sigma_1 \wedge \sigma_2 < \tau, \sigma_1 \# \tau \text{ et } \tau \subset \sigma_2.
$$

La propriété $Q_E$ est donc vérifiée. Soient maintenant $\sigma_1, \sigma_2$ et $\sigma_3$
trois configurations couvrant $\sigma$, c'est à dire

$$
\sigma_1 = \sigma u\{d_1\} \sigma_2 = \sigma u\{d_2\} \sigma_3 = \sigma u\{d_3\}
$$

Si $\sigma_1 R \sigma_2$ et $\sigma_2 R \sigma_3$ c'est que $d_1 = <c, v_1>, d_2 = <c, v_2>, d_3 = <c, v_3>$.

Si $v_3 = v_1$ alors $\sigma_1 = \sigma_3$ et si $v_3 \neq v_1$ alors $\sigma_1 \# \sigma_3$. La propriété $Q_U$ est
donc vérifiée.

4. Propriété R : Nous allons montrer que si deux intervalles premiers
$[\sigma_1, \sigma'_1]$ et $[\sigma_2, \sigma'_2]$ sont projectifs alors il existe d avec

$$
\sigma'_1 = \sigma_1 u\{d\} \text{ et } \sigma'_2 = \sigma_2 u\{d\}
$$

Pour ce faire, puisque la relation de projectivité est la fermeture
transitive de la relation de transposition, il nous suffit de montrer cette
propriété lorsque $[\sigma_1, \sigma'_1] \tau [\sigma_2, \sigma'_2]$.

Cas 1 : $[\sigma_1, \sigma'_1] \leq [\sigma_2, \sigma'_2]$. Nous avons montré, dans la partie 2 de cette démonstration que l'on a alors $\sigma'_2 = \sigma'_1 v \sigma_2 = \sigma_2 w d$.

Cas 2 : $[\sigma_1, \sigma'_1] \geq [\sigma_2, \sigma'_2]$. Posons $\sigma'_2 = \sigma_2 w \{d'\}$ et $\sigma'_1 = \sigma_1 w d$
Par définition $\sigma'_1 = \sigma'_2 v \sigma_1 = (\sigma_2 w \{d'\}) u \sigma_1$. Or on sait que $\sigma_2 c \sigma'_1$ donc
$\sigma'_1 = \sigma_1 u \{d'\} = \sigma_1 w \{d\}$. Par conséquent $d=d'$, donc $\sigma'_2 = \sigma_2 w \{d\}$.

Considérons maintenant deux intervalles premiers projectifs
$[\sigma, \sigma']$ et $[\sigma, \sigma'']$. On doit avoir

$$
\sigma' = \sigma u\{d\} \text{ et } \sigma'' = \sigma w\{d\}
$$

donc $\sigma' = \sigma''$ ce qui prouve la propriété R. Ceci conclut la deuxième partie
de la démonstration et le théorème est établi. $\square$

Remarque : Dans <Σ<sub>M</sub>; c>, la hauteur h(σ) d'une configuration σ n'est autre
que |σ| si σ est finie et infinie sinon. De l'égalité ensembliste

$$
|A| + |B| = |A \cap B| + |A \cup B|
$$

on déduit puisque $\sigma_1 \wedge \sigma_2 \le \sigma_1 \wedge \sigma_2$ : $h(\sigma_1) + h(\sigma_2) \ge h(\sigma_1 \wedge \sigma_2) + h(\sigma_1 \vee \sigma_2)$
inégalité que nous avons déjà démontrée. On voit bien ici que l'inégalité sera stricte chaque fois que $σ_1∧σ_2≠σ_1∩σ_2$.

## I.7 Théorème de représentation

Le théorème que nous allons démontrer maintenant est un théorème de représentation qui joue un rôle semblable aux deux théorèmes de représentation classiques en théorie des treillis [ 9 ] :

1. Tout treillis booléen est isomorphe à un corps d'ensembles

2. Tout treillis distributif est isomorphe à un anneau d'ensembles.

Ici, étant donné un domaine concret quelconque, nous exhiberons une *matrice d'information* dont l'ensemble des configurations, qui est un domaine concret d'après les résultats de la section précédente, est isomorphe au domaine concret dont nous sommes partis.

**Théorème T-7.1.** Tout domaine concret est isomorphe à l'ensemble des configurations d'une matrice d'information.

**Démonstration** : Soit $D$ un domaine de calcul concret quelconque.

**Partie 1 :** *Construction de la matrice d'information.* Nous construisons une matrice d'information $M = \langle \Gamma, V, \nu, E \rangle$ de la manière laissée prévoir par notre terminologie.

i) $\Gamma$ est l'ensemble de cellules (classes d'équipollence) de $D$ (définition VI.6.1) Comme la cardinalité de cet ensemble est dominée par la cardinalité de l'ensemble des points isolés de $D$, l'ensemble $\Gamma$ est dénombrable.

ii) $V$ est l'ensemble des décisions (classes de projectivité) de $D$ lequel est dénombrable par le même argument.

iii) Si $c$ est une cellule de $D$, c'est une union de classes de projectivité et nous choisirons pour $V(c)$ l'ensemble des classes de projectivité dont elle se compose. Par suite si $c_1$ et $c_2$ sont deux cellules distinctes de $D$, les ensembles $V(c_1)$ et $V(c_2)$ sont disjoints. Donc l'ensemble $\Delta_M$ des décisions de $M$ est isomorphe à $V$, autrement dit, toutes les cellules de $M$ ont un type distinct.
iv) La fonction $\mathcal{E}$ associe à toute cellule c l'ensemble des parties finies de $V(c.\mathcal{A}.d. \text{ de } \mathcal{D})$ qui rendent accessible $c$ (définition D-6.5.).

L'ensemble des configurations de la matrice d'information $M$ ainsi construite est un domaine concret par le théorème T-6.2.

## Partie 2 : L'injection $\phi$ de dans $\langle\Sigma_M; c\rangle$

A tout élément $x$ de $D$, on peut associer l'ensemble $\mathcal{A}(x)$ des décisions qu'il contient (définition D-6.2). L'ensemble $\mathcal{A}(x)$ est un sous-ensemble de $V$ en bijection avec un sous-ensemble $\phi(x)$ de $\Delta_M$. Montrons, par récurrence sur la hauteur de $x$ que $\phi(x)$ est une configuration de la matrice

a) **Cas de base** : $h(x)=0$ donc $x=1$. Alors $\mathcal{A}(x)=\emptyset$, donc $\phi(x)=\emptyset$. Or l'ensemble vide est une configuration.

b) **Pas de récurrence** : Supposons $h(x)=n(n>0)$.
Deux cas sont alors possibles :

**Cas 1 :** $x$ n'est pas sup-irréductible. Alors $x=avb$ avec $a<x$ et $b<x$ donc $h(a)<n$ et $h(b)<n$. Par hypothèse de récurrence $\phi(a)$ est une configuration ainsi que $\phi(b)$. Comme $\mathcal{A}(x)=\mathcal{A}(a)\cup\mathcal{A}(b)$ par la proposition P-6.2 on a $\phi(x)=\phi(a)\cup\phi(b)$. Donc $c(x)$ est un ensemble connecté de décisions. Par le corollaire C-6.2, si deux intervalles premiers dominés respectivement par $a$ et par $b$ sont équipollents il sont projectifs, donc $\phi(a)\cup\phi(b)$ ne contient pas deux décisions distinctes de $\Delta_M$ concernant la même cellule. Donc $\phi(x)$ est une configuration de $M$.

**Cas 2 :** $x$ est sup-irréductible. Si $x$ est sup-irréductible, cet élément possède un prédécesseur (unique) $\bar{x}$ et $h(\bar{x})=n-1$. Par hypothèse de récurrence $\phi(\bar{x})$ est une configuration. Par définition dans $D$ l'ensemble $\mathcal{A}(\bar{x})$ rend accessible la cellule $c[\bar{x},x]$, donc l'ensemble $\phi(\bar{x})\cup d[\bar{x},x]$ est connecté et c'est une configuration puisque l'union est disjointe par le théorème T-5.1. Comme $\bar{x}$ est un prédécesseur de $x$ on a alors $\phi(x)=\phi(\bar{x})\cup d[\bar{x},x]$ donc $\phi(x)$ est une configuration.
c) **Argument de continuité** : Si $x$ est infini, d'après la proposition P-6.2 :

$$ \Delta(x) = \bigcup_{\xi \in A(x)} \Delta(\xi) $$

Donc $\phi(x) = \bigcup_{\xi \in A(x)} \phi(\xi)$. Comme pour tout $\xi$ fini $\phi(\xi)$ est une configuration l'ensemble $\phi(x)$ est connecté. En invoquant à nouveau le corollaire C-6.2 on obtient que $\phi(x)$ est une configuration.

Puisque $x \le y$ entraine $\Delta(x) \subset \Delta(y)$, c'est à dire $\phi(x) \subset \phi(y)$, la fonction $\phi$ est croissante. Par ailleurs, en vertu du théorème T-6.1, si $\phi(x) = \phi(y)$ on a $x=y$. Donc $\phi$ est une *injection* croissante.

## Partie 3. La fonction $\phi$ est une surjection.

Puisque $\Sigma_M$ est un domaine de calcul concret, on raisonne naturellement par récurrence sur la taille d'un élément $\sigma$ de $\Sigma_M$, c'est à dire sur $|\sigma|$.

a) **Cas de base** : Si $|\sigma|=0$, c'est que $\sigma$ est la configuration vide. Or $\phi(\mathbb{1}_D)$ est la configuration vide.

b) **Pas de récurrence** : Supposons que toute configuration de $\Sigma_M$, de cardinalité inférieure à n, soit l'image d'un élément de D et considérons une configuration $\sigma$ avec $|\sigma|=n$.

Deux cas sont alors possibles :

**Cas 1** : $\sigma$ n'est pas sup-irréductible dans $\Sigma_M$. Alors $\sigma=\sigma_1 v \sigma_2$ avec $|\sigma_1|<n$ et $|\sigma_2|<n$. Par hypothèse de récurrence, il existe deux éléments $x_1$ et $x_2$ dans D avec $\sigma_1=\phi(x_1)$ et $\sigma_2=\phi(x_2)$. Les deux éléments $x_1$ et $x_2$ sont compatibles sinon, d'après la proposition P-4.4, on pourrait trouver deux intervalles équipollents $[\xi_1, \xi_1']$ et $[\xi_2, \xi_2']$ dans $[\mathbb{1}, x_1]$ et $[\mathbb{1}, x_2]$ non projectifs. Donc $\sigma$ contiendrait deux décisions distinctes $d[\xi_1, \xi_1']$ et $d[\xi_2, \xi_2']$ concernant la même cellule ce qui est exclu. Ral·Conséquent l'élément $x_1 v x_2$ existe dans D et $\phi(x_1 v x_2) = \phi(x_1) \cup \phi(x_2) = \phi(x_1) v \phi(x_2) = \sigma$.

**Cas 2** : $\sigma$ est sup-irréductible dans $\Sigma_M$. Soit alors $\bar{\sigma}$ son unique prédécesseur. Comme $|\bar{\sigma}|=|\sigma|-1$ il existe un élément $\bar{x}$ dans D tel que $\phi(\bar{x})=\bar{\sigma}$ par hypothèse de récurrence. Puisque $\sigma$ couvre $\bar{\sigma}$, il existe une décision d'avec $\sigma = \bar{\sigma} \vdash d$ et d admet une preuve $\pi \vdash d$, avec $\pi \subset \bar{\sigma}$. Par construction de $E$, il
existe donc dans $D$ un intervalle premier minimal $[\xi, \xi']$ avec

$$d[\xi, \xi'] = d$$
$$\Delta(\xi) \subset \pi$$

Puisque $\Delta(\xi)$ est inclus dans $\bar{\sigma}$ et donc dans $\Delta(\bar{x})$, on a par le théorème T-6.1.

$$\xi \le \bar{x}$$

Puisque $\bar{\sigma} \cup d$ est une configuration il n'existe aucun intervalle premier dans $\Delta(\bar{x})$ dans la même classe d'équipollence que $[\xi, \xi']$. Donc $\xi'$ est compatible avec $\bar{x}$ et n'est pas dominé par $\bar{x}$. Posons alors $x = \bar{x} \cup \xi'$. Alors $\Delta(x) = \Delta(\bar{x}) \cup \Delta(\xi')$ donc

$$\Delta(x) = \Delta(\bar{x}) \cup \pi \cup d = \Delta(\bar{x}) \cup d = \bar{\sigma} \cup d$$

et par suite $\phi(x) = \sigma$.

c) **Argument de continuité** : Supposons maintenant que $\sigma$ soit une configuration infinie. Comme $Z_M$ est algébrique on a
$$ \sigma = \bigcup \{\tau | \tau \in A(\sigma)\}. $$
Toute configuration $\tau$ dans $A(\sigma)$ est finie. C'est donc l'image d'un point $\xi$ dans $D$ par $\phi$. L'image inverse de $A(\sigma)$ par $\phi$ est un ensemble dirigé. Posons alors
$$ x = \bigcup \{\xi | \phi(\xi) \in A(\sigma)\}. $$
Par la proposition P-6.2, on obtient
$$ \Delta(x) = \bigcup \{\tau | \tau \in A(\sigma)\} \text{ et par conséquent } \phi(x) = \sigma. $$

Le théorème T-6.1 peut se réécrire alors

$$x \le y \Leftrightarrow \phi(x) \subset \phi(y)$$

ce qui conclut la preuve de l'isomorphisme entre $D$ et $\langle \Sigma_M ; c \rangle$. $\square$

**Exemples** : Nous montrons sur quelques exemples simples comment on obtient une matrice d'information qui représente un domaine de calcul.

**Exemple 1** :

<figure><img src="image_40.png" /><figcaption>(a)</figcaption></figure>

<figure><img src="image_41.png" /><figcaption>(b)</figcaption></figure>
Le diagramme de la figure F-7.1.a. comporte 3 classes d'intervalle premiers équipollents, nous construirons donc 3 cellules. Les éléments sup-irréductibles sont ceux qui sont encerclés : a,a',c,c'. Puisque $\Delta(\perp) = \{\emptyset\}$ les cellules A et B correspondant respectivement aux classes $[[\perp,a],[c,b],[c',b']]]$ et $[[\perp,c],[a,b],[a,b']]]$ sont initiales. Comme le domaine est un treillis, les cellules de la figure F-7.1.a ne peuvent prendre qu'une seule valeur (aucune incompatibilité ne peut intervenir). Enfin la cellule C qui représente la classe $[[a,a'],[b,b'],[c,c']]]$ est rendue accessible soit par $\Delta(a)$ soit par $\Delta(c)$, autrement dit C rendue accessible par toute décision sur A ou sur B.

On vérifie rapidement que l'ensemble des configurations de la matrice d'information de la figure F-7.1.b est isomorphe à la figure F-7.1.a avec par exemple la correspondance rassemblée dans le tableau suivant :

<table><thead><tr><td>élément du domaine</td><td>Configuration</td></tr></thead><tbody><tr><td>1</td><td>Ø</td></tr><tr><td>a</td><td>{&lt;A,T&gt;}</td></tr><tr><td>c</td><td>{&lt;B,T&gt;}</td></tr><tr><td>b</td><td>{&lt;A,T&gt;, &lt;B,T&gt;}</td></tr><tr><td>a'</td><td>{&lt;A,T&gt;, &lt;C,T&gt;}</td></tr><tr><td>c'</td><td>{&lt;B,T&gt;, &lt;C,T&gt;}</td></tr><tr><td>b'</td><td>{&lt;A,T&gt;, &lt;B,T&gt;, &lt;C,T&gt;}</td></tr></tbody></table>
Exemple 2 :

<figure><img src="image_42.png" /><figcaption>(a)</figcaption></figure>

A

<figure><img src="image_43.png" /></figure>

B

<figure><img src="image_44.png" /><figcaption>(b)</figcaption></figure>

figure F-7.2

Le diagramme de la figure VI.7.2.a comporte deux classes d'équipollence : A = {[⊥,a],[b',a'],[⊥,c],[b',c']} B = {[a,a'],[⊥,b'],[c,c]} et nous construisons donc deux cellules A et B. Comme les 3 éléments sup-irréductibles sont des atomes, les deux cellules sont initiales. Enfin, la cellule A comporte deux classes d'équivalence d'intervalle premiers projectifs et peut donc prendre deux valeurs distinctes.

A titre de vérification, nous remplissons à nouveau un tableau de correspondance :

<table><thead><tr><td>Elément du domaine</td><td>Configuration</td></tr></thead><tbody><tr><td>⊥</td><td>Ø</td></tr><tr><td>a</td><td>{&lt;A,0&gt;}</td></tr><tr><td>c</td><td>{&lt;A,1&gt;}</td></tr><tr><td>b'</td><td>{&lt;B,0&gt;}</td></tr><tr><td>a'</td><td>{&lt;A,0&gt;, &lt;B,0&gt;}</td></tr><tr><td>c'</td><td>{&lt;A,1&gt;, &lt;B,0&gt;}</td></tr></tbody></table>
**Remarque** : Le domaine de la figure F-7.2.a est le produit cartésien $T \times O$.
Or O est représenté par une seule cellule pouvant prendre une seule valeur
et T est représenté par une seule cellule pouvant prendre deux valeurs. Nous
verrons au paragraphe suivant que le produit cartésien de deux domaines
concrets est représenté par la juxtaposition de leurs représentations.

**Exemple 3** :

<figure><img src="image_45.png" /><figcaption>figure F-7.3</figcaption></figure>

Ici encore, le diagramme de la figure F-7.3.a est un treillis donc
toutes les cellules dans sa représentation sous forme de matrice d'informa-
tion ne prendront qu'une seule valeur.

Il y a quatre cellules :

$$
A = \{[\perp, a], [b, e], [d, g], [i, j]\}
$$

$$
B = [[1,b],[a,e],[c,f],[h,j]]
$$

$$
C = [[a,c],[e,f],[g,j],[d,i]]
$$

$$
D = [[b,d],[e,g],[f,j],[c,h]]
$$

et six éléments sup-irréductibles : a,b,c,d,h,i.

Par suite A et B sont initiales et les ensembles {A,C} et {B} rendent
accessible la cellule¹ D. De même les ensembles {B,D} et {A} rendent acces-
sibles la cellule C. On remarque alors que le théorème de représentation ne
conduit pas à une représentation "minimale" puisque le diagramme de la
figure F-7.3.b est équivalent c.à.d. donne lieu aux mêmes configurations,
mais comporte moins de contraintes que celui que nous venons de construire.
Nous ne présentons, en raison de la symétrie, qu'une moitié de la correspondance entre le domaine et les configurations de la matrice d'information.

<table><thead><tr><th>Elément</th><th>Configuration</th></tr></thead><tbody><tr><td>1</td><td>Ø</td></tr><tr><td>a</td><td>{&lt;A, T&gt;}</td></tr><tr><td>e</td><td>{&lt;A, T&gt;, &lt;B, T&gt;}</td></tr><tr><td>c</td><td>{&lt;A, T&gt;, &lt;C, T&gt;}</td></tr><tr><td>f</td><td>{&lt;A, T&gt;, &lt;B, T&gt;, &lt;C, T&gt;}</td></tr><tr><td>h</td><td>{&lt;A, T&gt;, &lt;B, T&gt;, &lt;C, T&gt;}</td></tr><tr><td>j</td><td>{&lt;A, T&gt;, &lt;B, T&gt;, &lt;C, T&gt;, &lt;D, T&gt;}</td></tr></tbody></table>

**Remarque** : La cellule C rend accessible la cellule D et réciproquement. Cette "boucle" ne peut pas être éliminée.

**Exemple 4** :

<figure><img src="image_46.png" /><figcaption>figure F-7.4</figcaption></figure>
Le treillis de la figure F-7.4 est le treillis distributif libre à trois générateurs. Tout treillis distributif fini possède la propriété $R_T$ donc est automatiquement un domaine de calcul concret. Il comporte six classes d'équivalence d'intervalles premiers projectifs et chaque classe contient un seul intervalle premier minimal. Nous verrons plus loin que ce fait est général en présence de distributivité. Le diagramme de la représentation obtenue est celui de la figure F-6.4.b.

Nous ne donnons pour l'instant pas d'exemples de domaines infinis, en dehors du domaine des suites bien connu. Il nous faut au préalable étudier certaines opérations fondamentales qui permettent de construire des domaines de calcul concrets.

## I.8 Opérations fondamentales

Dans cette section et la suivante nous présentons certaines opérations qui permettent de construire des domaines de calculs concrets complexes à partir d'autres plus simples. Par exemple, nous avons vu que le produit cartésien de deux domaines de calcul est un domaine de calcul. De même :

**Proposition P-8.1** : Le produit cartésien de deux domaines de calcul concrets est concret.

**Démonstration** : Si $D$ et $E$ sont deux domaines de calcul concrets, leur produit cartésien est ordonné composante par composante :

$$ \langle x, y \rangle_{D \times E} \le \langle x', y' \rangle \iff_{D \times E} x \le x' \text{ et } y \le y' $$

Les points isolés de $D \times E$ sont les paires $\langle d, e \rangle$ avec $d \in A(D)$ et $e \in A(E)$. On vérifie immédiatement que les relations de couverture et d'incompatibilité dans $D \times E$ sont données par

$$ \begin{cases} \langle d, e \rangle \prec \langle d', e' \rangle \iff_{D \times E} (d \prec d' \text{ et } e=e') \text{ ou } (d=d' \text{ et } e \prec e') \\ \langle d, e \rangle \succ \langle d', e' \rangle \iff_{D \times E} (d \succ d') \text{ ou } (e \# e') \end{cases} $$

Nous pouvons maintenant vérifier que $D \times E$ possède toutes les propriétés d'un domaine de calcul concret.
**1. Propriété I** : Soient $<d,e>$ et $<d',e'>$ deux éléments isolés de $D×E$. Un élément $x,y$ dans l'intervalle $[<d,e>,<d,e'>]$ vérifie

$$ \begin{cases} d \le x \le d' \\ e \le y \le e' \end{cases} $$

Il n'existe donc qu'un nombre fini de telles paires par et à fortiori toutes les chaînes de cet intervalle sont finies.

**2. Propriété C** : Les bornes supérieures et inférieures dans $D×E$ sont prises composante par composante. Supposons alors que l'on ait $<x,x'>↑<y,y'>$ et $<x^\Lambda y,x'^\Lambda y'>←<x,x'$. Deux cas sont possibles :

**Cas 1 :** $x = x^\Lambda y$ et $x'^\Lambda y' = <x'$.

Alors, par la propriété C dans $E$ $y' = <x'Vy'$ et bien entendu $xVy=y$.

$$ \text{Donc } <y,y'>←<x^\Lambda y,x'^\Lambda y'> = <x,x'>\downarrow<y,y'> $$

**Cas 2 :** $x' = x'^\Lambda y$ et $x^\Lambda y = <x'$.

Alors la propriété C dans $D$ permet de conclure de même

$$ <y,y'>←<x,x'>\downarrow<y,y'> $$

Par conséquent $D×E$ possède la propriété C.

**3. Propriété Q** : Soient $<x,x'>$ et $<y,y'>$ deux éléments incompatibles de $D×E$ tels que

$$ <x^\Lambda y,x'^\Lambda y'>←<x,x'> $$

On a ou bien $x=y$, ou bien $x' \neq y'$, ces deux conditions ne s'excluant pas mutuellement. Deux cas (symétriques) se présentent donc :

**Cas 1 :** $x^\Lambda y = x$. Alors x et y sont comparables donc c'est que $x' \neq y'$ et puisque $x'^\Lambda y' = <x'$, par la propriété Q dans E il existe un élément $t'$ avec $x'^\Lambda y' = <t' \leq y'$ et $x' \neq t'$.

Par suite

$$ \begin{cases} <x^\Lambda y,x'^\Lambda y'>←<x,t'>\le<y,y'> \\ <x,x'>\#<x,t> \end{cases} $$

donc la propriété $Q_E$ est établie dans ce cas. Comme la propriété $Q_U$ est valide dans $E$, il ne peut exister un élément $t''$ distinct de $t'$

$$ \text{avec } \begin{cases} <x^\Lambda y,x'^\Lambda y'>←<x,t''>\le<y,y'> \\ <x,x'>\#<x,t''> \end{cases} $$
De plus, tout élément de la forme $\langle u, x' \wedge y' \rangle$ avec $x \wedge y = x \wedge \neg u$ est compatible avec $\langle x, x' \rangle$. Par conséquent la propriété $Q_U$ est elle aussi valide dans $D \times E$ dans ce cas

Cas 2 : $x' = x' \wedge y'$. Ce cas est traité par un raisonnement rigoureusement symétrique.

La propriété Q est donc valide dans $D \times E$.

4. Propriété R. Nous devons, pour établir R regarder plus en détail les intervalles premiers de $D \times E$ et la relation de transposition. Tout d'abord, l'intervalle $[\langle d, e \rangle, \langle d', e' \rangle]$ est premier ssi

$$ \begin{cases} \text{ou bien } [d, d'] \text{ est premier et } e=e' \\ \text{ou bien } [e, e'] \text{ est premier et } d=d' \end{cases} $$

Soient maintenant $[\langle d_1, e_1 \rangle, \langle d'_1, e'_1 \rangle]$ et $[\langle d_2, e_2 \rangle, \langle d'_2, e'_2 \rangle]$ deux intervalles premiers. Si l'on a

$$ [\langle d_1, e_1 \rangle, \langle d'_1, e'_1 \rangle] \leq [\langle d_2, e_2 \rangle, \langle d'_2, e'_2 \rangle] $$

c'est que

$$ \begin{cases} d_1 = d'_1 \wedge d_2 \text{ et } e_1 = e'_1 \wedge e_2 \\ d'_2 = d'_1 \vee d_2 \text{ et } e'_2 = e'_1 \vee e_2 \end{cases} $$

Si $[d_1, d'_1]$ est premier et $e_1 = e'_1$, alors

$$ \begin{cases} [d_1, d'_1] \leq [d_2, d'_2] \\ e_1 = e'_1 = e_2 = e'_2 \end{cases} $$

Si $[e_1, e'_1]$ est premier et $d_1 = d'_1$ alors

$$ \begin{cases} [e_1, e'_1] \leq [e_2, e'_2] \\ d_1 = d'_1 = d_2 = d'_2 \end{cases} $$

Par symétrie, puis transitivité on obtient :

$$ [\langle d_1, e_1 \rangle, \langle d'_1, e'_1 \rangle] \sim [\langle d_2, e_2 \rangle, \langle d'_2, e'_2 \rangle] $$

• ou bien $[d_1, d'_1]$ et $[d_2, d'_2]$ sont des intervalles premiers projectifs et $e_1 = e'_1 = e_2 = e'_2$

• ou bien $[e_1, e'_1]$ et $[e_2, e'_2]$ sont des intervalles premiers projectifs et $d_1 = d'_1 = d_2 = d'_2$

ces deux cas s'excluant mutuellement.
Alors supposons que l'on ait

$[<d,e>,<d,e'>]~[<d,e>,<d'',e''>]$

• ou bien $[d,d']$ et $[d,d'']$ sont des intervalles premiers projectifs de $D$ et alors, par $R$ $d'=d''$. Comme $e=e'=e''$, on a bien
$$<d',e'>=<d'',e''>$$

• ou bien $[e,e']$ et $[e,e'']$ sont des intervalles premiers projectifs de $E$ et par la propriété $R$ dans $E$, on obtient $e'=e''$.
Or dans ce cas on a aussi $d=d'=d''$ donc finalement
$$<d',e'>=<d'',e''>$$

La propriété $R$ est donc valide dans $D \times E$.

**Remarque** : Pour prouver qu'un domaine de calcul est concret, deux stratégies sont possibles. Ou bien on passe en revue, comme nous venons de le faire, les propriétés qui doivent être vérifiées. Ou bien on cherche à utiliser le théorème de représentation, c'est à dire à exhiber une matrice d'information dont l'ensemble des configurations est isomorphe au domaine considéré. Ces deux stratégies ont leurs avantages respectifs et nous en présenterons plusieurs illustrations.

**Définition D-8.1.** Si $M' = <\Gamma', V', V'', E'>$ et $M'' = <\Gamma'', V'', V'', E''>$ sont deux matrices d'information dont les ensembles de cellules sont *disjoints*, la *juxtaposition* de $M'$ et $M''$ est la matrice d'information $<\Gamma, V, V, E>$ définie comme suit :

$$ 
\left\{
\begin{array}{l}
\Gamma = \Gamma' \cup \Gamma'' \\
V = V' \cup V'' \\
V(c) = \begin{cases} V'(c) & \text{si } c \in \Gamma' \\ V''(c) & \text{si } c \in \Gamma'' \end{cases} \\
E(c) = \begin{cases} E'(c) & \text{si } c \in \Gamma' \\ E''(c) & \text{si } c \in \Gamma'' \end{cases}
\end{array}
\right.
$$
**Proposition P-8.2.** Si $M'$ et $M''$ sont deux matrices d'information et $M$ est leur juxtaposition, alors

$$ \langle \Sigma_M; c \rangle = \langle \Sigma_{M'}; c \rangle \times \langle \Sigma_{M''}; c \rangle $$

**Démonstration :**

Soit $\sigma$ une configuration quelconque de $M$. Puisque l'ensemble des cellules de $M$ est la réunion disjointe de l'ensemble des cellules de $M'$ et de $M''$, la configuration $\sigma$ est la réunion disjointe de deux ensembles de décisions $\sigma'$ et $\sigma''$ concernant respectivement les cellules de $M'$ et $M''$. Ces deux sous-ensembles $\sigma'$ et $\sigma''$ sont connectés par définition de la fonction d'accessibilité de $M$. En tant que sous-ensembles connectés d'une configuration $\sigma'$ et $\sigma''$ sont des configurations de $M$ en correspondance triviale avec des configurations de $M'$ et $M''$. A tout élément de $\Sigma_M$ nous pouvons donc associer un élément de $\Sigma_{M'} \times \Sigma_{M''}$. Réciproquement, par définition de la juxtaposition, à tout élément de $\Sigma_{M'} \times \Sigma_{M''}$ on peut associer une configuration de $\Sigma_M$. Enfin

$$ \sigma_{1}^{c} \sigma_{2} \Leftrightarrow (\sigma_{1}^{c} \sigma_{2}^{c}) \text{ et } (\sigma_{1}^{c} \sigma_{2}^{c}) $$

donc la bijection entre $\Sigma_M$ et $\Sigma_{M'} \times \Sigma_{M''}$ préserve la relation d'ordre. Les domaines $\Sigma_M$ et $\Sigma_{M'} \times \Sigma_{M''}$ sont donc isomorphes $\square$

De la proposition ci-dessus, nous tirons une preuve rapide que le produit cartésien de deux domaines concrets est concret. En effet si $D'$ et $D''$ sont deux domaines concrets, représentés respectivement par les matrices $M'$ et $M''$, l'ensemble des configurations de la juxtaposition de $M'$ et $M''$ est isomorphe à $D' \times_D D''$. Donc $D' \times_D D''$ est un domaine de calcul concret. Le raisonnement s'étendant à un nombre dénombrable de matrices d'information on obtient aussi :

**Corollaire C-8.1.** Le produit cartésien d'un nombre dénombrable de domaines concrets est concret.

**Exemple :**

<figure><img src="image_47.png" /><figcaption>(a)</figcaption></figure>

figure F-8.1

<figure><img src="image_48.png" /><figcaption>(b)</figcaption></figure>

<figure><img src="image_49.png" /></figure>

0/1

<figure><img src="image_50.png" /></figure>

0/1

<figure><img src="image_51.png" /></figure>

0/1

<figure><img src="image_52.png" /></figure>

0/1

<figure><img src="image_53.png" /></figure>

0/1

...

(c)
Le domaine $\mathcal{T}$ de la figure F-8.1.a est associé à la matrice représentée sur la figure F-8.1.b et $T^\omega$, le domaine universel de calcul de Plotkin [3] est associé à la matrice de la figure F-8.1.c. Par suite $T^\omega$ est un domaine concret. De même $N_⊥^\omega$, le domaine sous-jacent dans LUCID[11], est un domaine concret.

**Définition D-8.2.** Soit $\{<D_i; \le_i>\}_{i \in I}$ une famille au plus dénombrable d'ordres partiels dont les domaines sont disjoints. La somme séparée de cette famille est l'ordre partiel $<D; \le>$ définie par

$$i) \ D = \{\perp\} \cup (\bigcup_{i \in I} D_i)$$

$$ii) \ x \leq y \Leftrightarrow \begin{cases} x = \perp \\ \exists i \in I \ x \leq y_i \end{cases}$$

(L'élément $\perp$ est choisi comme n'appartenant à aucun des ensembles $D_i$).

**Proposition P-8.3.** La somme séparée d'un nombre au plus dénombrable de domaines de calcul concret est un domaine concret.

**Démonstration :**

<figure><img src="image_54.png" /><figcaption>figure F-8.2.</figcaption></figure>

Il est immédiat que la somme séparée d'un nombre dénombrable de domaines de calcul est un domaine de calcul, dont les éléments isolés sont ceux des domaines opérandes plus le nouvel élément $\perp$. La propriété I est donc vérifiée dès que les domaines opérandes la vérifient.
La propriété C est elle aussi valide puisqu'aucune paire d'éléments compatibles et incomparables n'est apparue. Les seules paires <x,y> avec x#y et x^y < x qui sont apparues dans la somme séparée sont de la forme <⊥ᵢ, dⱼ> avec i≠j et dⱼ ∈ Dᵢ puisqu'alors ⊥ᵢ^dⱼ = ⊥. Mais alors ⊥ⱼ est l'unique élément de D vérifiant ⊥ᵢ # ⊥ⱼ, ⊥ < ⊥ⱼ < dⱼ. Donc la somme séparée D possède la propriété Q. La propriété R reste vérifiée puisque les seuls intervalles premiers apparus dans D sont de la forme [⊥,⊥ⱼ] et sont uniques dans leur classe d'équivalence par projectivité. []

Rearquons que la somme séparée d'une famille de domaines de calculs concrets {$<D_i; \le_i>$} comporte une seule cellule nouvelle qui est la classe d'équipollence des intervalles premiers de la forme [⊥,⊥ᵢ] (i∈I). Cette cellule est rendue accessible par l'ensemble vide. Cette remarque suggère la définition suivante.

**Définition D-8.3.** Soit {$M_i$}$_{i \in I}$ un ensemble fini ou dénombrable de matrices d'informations dont les ensembles de cellules sont disjoints. La somme de cet ensemble de matrices est la matrice M définie par

$$
i) \Gamma = (\bigcup_{i \in I} \Gamma_i) \cup \{\gamma\}
$$

$$
ii) V = (\bigcup_{i \in I} V_i) \cup I
$$

$$
\begin{align*}
\text{iii) } V(c) &= \begin{cases} v_i(c) & \text{si } c \in \Gamma_i \\ v & \text{si } c=\gamma \end{cases} \\
\text{iv) } E(c) &= \begin{cases} \{e \mid \langle \gamma, i \rangle \mid e \in E_i(c)\} & \text{si } c \in \Gamma_i \\ \{\emptyset\} & \text{si } c=\gamma \end{cases}
\end{align*}
$$

**Proposition P-8.5.** L'ensemble des configurations de la somme d'une famille
au plus dénombrable de matrices d'informations est isomorphe à la somme sé-
parée des ensembles de configurations des éléments de cette famille.

**Démonstration :** Soit {$M_i$}$_{i \in I}$ une famille de matrices d'information dont les ensembles de cellules sont disjoints et M la somme de cette famille. Une configuration σ non vide de M contient nécessairement une et une seule décision de la forme <γ,i>. Par conséquent toutes les autres décisions de σ sont des décisions de M_i et forment une configuration de $\Sigma_{M_i}$. Il y a donc
injection de $M$ dans la somme séparée de $\{\Sigma_{M_i}\}_{i \in I}$. Réciproquement, il est trivial d'associer une configuration de $M$ à tout élément de cette somme séparée. Il y a donc bijection. Cette bijection préservant la relation d'ordre, c'est un isomorphisme. $\Box$

**Remarque :** Le choix d'une somme séparée de domaines concrets n'est pas arbitraire. En effet la somme "avec minima confondus" de deux domaines concrets n'est pas nécessairement un domaine concret, non plus que la somme oblique qui privilégie le minimum de l'un des deux domaines. La figure illustre le fait que la propriété Q risque de ne pas être valide dans ces deux cas. Le domaine Q est soit la somme confondue de $O^2$ et 0, soit la somme oblique de $O^2$ et L. Or Q n'a pas la propriété Q.

<figure><img src="image_55.png" /><figcaption>figure F-8.3.</figcaption></figure>

**Remarque :** Le domaine $L$ admet pour représentation, par exemple, la matrice qui ne contient aucune cellule. Le domaine $N_\perp$ est la somme séparée d'un nombre dénombrable de copies de $L$. Par conséquent $N_\perp$ admet pour représentation une cellule unique qui peut prendre un entier quelconque comme valeur.

**Définition D-8.4.** Dans un ordre partiel cohérent $<D; \leq>$ on appelle *idéal cohérent* un sous-ensemble $J$ non vide de $D$ vérifiant

$$i) \forall x \in J, \forall y \in D \ y \le x \Rightarrow y \in J$$

$$ii) \forall X \subset J \ X \text{ consistant} \Rightarrow \bigcup_{x \in J} X$$
**Remarque** : Puisque deux éléments compatibles forment un ensemble consistant, cette définition étend bien la définition D-2.1.

**Proposition P-8.6.** Dans un domaine de calcul concret $<D; \le>$, tout idéal cohérent J est un sous-domaine de calcul concret.

**Démonstration** : Par définition $<J; \le>$ est cohérent. Si d est un point isolé de D appartenant à J, alors d est certainement un point isolé dans J. Réciproquement, par algébricité de D, pour tout élément d de J on a

$$d = \bigcup A(d)$$

Or tous les éléments de $A(d)$ appartiennent à J puisqu'ils sont dominés par d. Par suite si d est un élément isolé de J, il est égal à un certain élément e isolé dans D. Donc les éléments isolés de J sont exactement les éléments isolés de D inclus dans J. Par conséquent $<J; \le>$ est un sous-domaine de calcul de $<D; \le>$. Montrons maintenant que J est concret.

**Propriété I** : Puisque $A(J) = A(D) \cap J$ il est immédiat que $A(J)$ est un idéal bien fondé de J.

**Propriété C** : Si x et y sont deux éléments compatibles de J, alors $x \wedge y \in J$ et $x \vee y \in J$. Comme la propriété C est valide dans D elle est donc valide dans J.

**Propriété Q** : Si x et y sont deux éléments incompatibles de J, l'intervalle $[x \wedge y, y]$ est tout entier contenu dans J et par conséquent la validité de Q dans D entraîne la validité de Q dans J.

**Propriété R** : Si R n'était pas valide dans J, cette propriété ne le serait pas non plus dans D. Donc R est vérifiée. □

Avant d'exhiber la représentation d'un idéal cohérent, signalons un résultat intéressant par lui-même et qui n'est vrai que grâce à l'intégralité de la propriété R.

**Lemme L-8.1.** Dans un domaine concret, l'idéal cohérent engendré par un nombre fini de points finis est fini.
**Démonstration** : Soit X un ensemble fini de points finis dans un domaine concret D. Posons $\Delta = \bigcup_{x \in X} \Lambda(x)$. L'ensemble $\Delta$ est un ensemble fini. Soit J l'idéal cohérent engendré par X, c'est à dire l'intersection de tous les idéaux cohérents contenant X. Soit x un élément de J.

1. Si $x \in X$ alors $\Lambda(x) \subset \Delta$

2. Si $x \le y$ avec $\Delta(y) \subset \Delta$ alors

$$ \Delta(x) \subset \Delta(y) \subset \Delta $$

3. Si $x = \bigcup Y$ avec Y une partie consistante de D dont tous les éléments y vérifient

$$ \Delta(y) \subset \Delta $$

alors par la proposition P-6.2

$$ \Delta(x) = \bigcup_{y \in Y} \Delta(y) \subset \Delta $$

Par suite, l'ensemble $\{z | \Delta(z) \subset \Delta\}$ contient X et c'est un idéal cohérent. Il contient donc l'idéal cohérent J engendré par X, c'est à dire

$$ \forall z \in J, \Delta(z) \subset \Delta \quad (*) $$

Comme $\Delta$ est fini $P(\Delta)$ est fini. Puisque, par le théorème VI.

$$ z_1 \neq z_2 \Rightarrow \Delta(z_1) \neq \Delta(z_2) $$

on a

donc J est fini.

□

**Remarque** : En généralisant l'exemple de la figure VI.5.2, il est facile de montrer que cette propriété ne découle pas de la propriété $R_T$ seule.

**Définition D-8.5.** Soit $M = \langle I, J, V, E \rangle$ une matrice d'information et X un sous-ensemble quelconque de $\Sigma_M$. Posons $\Delta_X = \bigcup_X U_X$. La restriction de M à X est la matrice d'information $\langle \Gamma, V, V', E' \rangle$ définie comme suit :

$$ \text{i) } \Gamma' = \{c | \langle c, v \rangle \in \Delta_X\} $$

$$ \text{ii) } V' = \{v | \langle c, v \rangle \in \Delta_X\} $$

$$ \text{iii) } v \in V' \text{ (c) ssi } \langle c, v \rangle \in \Delta_X $$

iv) Un ensemble de décisions $\Delta$ de $M_X$ rend accessible c ssi $\Delta \in E(c)$.

<footnote>* L'argument utilisé ici est une forme de récurrence ordinale Cf[ 12] p.27.</footnote>
Remarquons que deux restrictions $M_X$ et $M_Y$ de $M$ sont distinctes
ssi $\Delta_X$ et $\Delta_Y$ sont distincts. Les restrictions d'une même matrice d'infor-
mation sont naturellement ordonnées par inclusion et l'on a :

**Lemme L-8.1.** Soit M une matrice d'information. L'ensemble des restrictions de M ordonnées par inclusion est isomorphe à l'ensemble des idéaux cohérents de $\Sigma_M$.

**Démonstration :** 1. Soit X un sous-ensemble de $\Sigma_M$ et $M_X$ la restriction de M à X. Soit $\phi$ la fonction qui à $M_X$ associe $\Sigma_{M_X}$. Montrons d'abord que $\phi$ associe à $M_X$ un idéal cohérent de $\Sigma_M$.

i) Soit $\sigma$ une configuration de $M_X$. C'est aussi une configuration de $M$. Si $\sigma'$ est une configuration de $M$ quelconque avec
$$ \sigma' \subset \sigma $$
alors $\sigma'$ est certainement une configuration de $M_X$.

ii) Soit S un ensemble consistant de configurations de $M_X$.

L'ensemble $\bigcup_{\sigma \in S} \sigma$ est aussi une configuration de $M_X$. Or, dans $\Sigma_M$
$$ \bigcup_S = \bigcup_{\sigma \in S} \sigma $$
d'après le lemme VI.6.2. Par conséquent $\bigcup_{S \in \Sigma_M} S$. Donc $\Sigma_M$ est un idéal cohérent de $\Sigma_M$.

La fonction $\phi$ est trivialment croissante. Montrons aussi que $\phi$
est une injection. Soient $M_X$ et $M_Y$ deux restrictions de M distinctes.
D'après la remarque faite plus haut $\Delta_X \neq \Delta_Y$. Il existe alors une configuration $\sigma$ dans Y dont toutes les décisions ne sont pas dans $\Delta_X$. La configuration $\sigma$ est un élément de $\Sigma_{M_Y}$ qui n'est pas dans $\Sigma_{M_X}$.

2. Réciproquement soit J un idéal cohérent de $\Sigma_M$.

Considérons la restriction $M_J$. D'après la partie 1, l'ensemble $\Sigma_{M_J}$ est un idéal cohérent de $M$ qui contient J. Si on avait $J \neq \Sigma_{M_J}$, il existerait dans $\Sigma_{M_J}$ une décision qui n'est pas dans J.

Par la définition D-8.5, ceci est impossible. Donc $J = \Sigma_{M_J}$ et $\phi$ est une surjection.
□
Le concept dual du concept d'idéal, dans un domaine de calcul,
est celui de section supérieure, que nous avons abondamment discuté dans
les paragraphes précédents. Rappelons que toute section supérieure d'un
domaine concret est un domaine concret. Les sections supérieures ont na-
turellement l'interprétation duale des idéaux.

**Définition D-3.6.** Soit $\mathcal{M} = \langle \Gamma, V, \nu, E \rangle$ une matrice d'information et $\sigma$ une configuration quelconque de $\mathcal{M}$. Posons $O_{\sigma} = \{c \mid <c, v> \in \sigma\}$. Le prolongement $M^{\sigma}$ de $\sigma$ dans $\mathcal{M}$ est la matrice d'information $\langle \Gamma', V', \nu', E' \rangle$ définie comme suit :

i) $\Gamma' = \Gamma \setminus O_{\sigma}$

ii) $V' = V$

iii) $V'$ est la restriction de $V$ à $\Gamma'$

iv) Si $\Delta$ est un ensemble de décisions de $\mathcal{M}$ qui rend accessible une cellule $c$ dans $\Gamma'$, alors $\Delta \setminus \sigma$ rend accessible $c$ dans $M^{\sigma}$.
Réciproquement si $\Delta'$ rend accessible $c$ dans $M^{\sigma}$, c'est que $\Delta \cup \sigma$ rend accessible $c$ dans $\mathcal{M}$.

**Lemme L-3.2.** Soit $\mathcal{M}$ une matrice d'information. L'ensemble des prolongements $M^{\sigma}$ de configurations $\sigma$ de $\mathcal{M}$ est isomorphe à l'ensemble des sections supérieures de $\Sigma_{\mathcal{M}}$.

**Démonstration :** Un ensemble de décisions $\tau$ de $M^{\sigma}$ est une configuration de $M^{\sigma}$ ssi $\sigma \in \tau$ est une configuration de $\mathcal{M}$. $\square$

**Définition D-8.7.** Dans un ordre partiel $<D; \leq>$ un sous-ensemble $X$ de $D$ est convexe ssi lorsqu'il contient $x$ et $y$ avec $x \leq y$, il contient tous les éléments de l'intervalle $[x, y]$.

Dans un domaine de calcul $D$, un sous-domaine de calcul $H$ possède un élément minimum $\bot_H$. Si $H$ est convexe, alors $H$ est un idéal cohérent de $[\bot_H)$. Donc tout sous-domaine de calcul convexe d'un domaine de calcul concret est concret. L'interprétation d'un sous-domaine de calcul convexe est naturellement la restriction du prolongement d'une certaine configuration.
**Définition D-8.7.** Dans un domaine de calcul *D*, on appelle *ouvert* toute réunion de sections supérieures d'éléments isolés.

**Remarques :** 1. La famille *F* de parties de *D* ainsi définie possède les propriétés suivantes :

(01) $D \in F$ puisque $D = [\perp]$

(02) L'union d'un nombre quelconque d'éléments de *F* est dans *F*

(03) L'intersection d'un nombre fini d'éléments de *F* est dans *F* (Proposition A-P1).

Par conséquent *F* constitue une famille d'ouverts au sens usuel, ce qui justifie notre terminologie. Notons que les sections supérieures des éléments finis forment une base de cette topologie et que les sections supérieures des éléments sup-irréductibles en sont une sous-base, c'est à dire que tout élément de la base est obtenue par intersection finie d'éléments de la sous-base (par application du corollaire C-5.5).

2. Une partie de $D$ est un ouvert ssi c'est l'image inverse de $\tau$ par une fonction continue de $D$ de $0$. En effet, d'une part si $f$ est continue $f$ est la borne supérieure d'une collection de fonctions étages $\phi_{d,\tau}$ avec d isolé dans $D$. Or $\phi_{d,\tau}^{-1}(\tau)=[d)$, donc $f^{-1}(\tau)$ est un ouvert. D'autre part, si $0$ est un ouvert la fonction $f$ définie par

$$ \begin{cases} f(x) = \tau & \text{si } x \in 0 \\ f(x) = \perp & \text{sinon} \end{cases} $$

est croissante et continue.

**Définition D-8.8.** Soient $\langle D; \leq \rangle$ et $\langle E; \leq \rangle$ deux domaines de calcul et $0$ un ouvert de $D$. La greffe de $E$ sur $D$ en $0$, notée $D \xrightarrow{0} E$ est l'ordre partiel $\langle F; \leq \rangle$ défini par :

$$ \text{i) } F := \{ \langle d,e \rangle \mid d \in D, e \in E, d \in 0 \text{ ou } e = \perp \} $$

ii) $\leq$ est l'ordre partiel induit par $D \times E$ sur $F$.

**Exemple :** Soit $D=0^2$ et $E=0$. Les ouverts de $0^2$ sont les ensembles $O_i$ ($0 \leq i \leq 5$) définis par :

$$ O_1 = [\perp) \quad O_2 = [0) \quad O_3 = [1) \quad O_4 = [0) \cup [1) \quad O_5 = [\tau) $$
et les greffes de $\tilde{E}$ sur $D$ en $O_i$ sont les $F_i$ dont les diagrammes sont représentés sur la figure F-8.4.

<figure><img src="image_56.png" /><figcaption>figure F-8.4</figcaption></figure>

**Proposition P-8.10.** Si $D$ et $E$ sont des domaines de calcul concrets, toute greffe $F$ de $E$ sur $D$ est un domaine concret et $D$ est isomorphe à un idéal cohérent de $F$.

**Démonstration :** Soit $O$ un ouvert quelconque de $D$. Posons $F = D \times_{\tilde{E}} O$.

L'ensemble $F$ est une partie de $D \times E$. Si deux éléments de $F$ sont compatibles, il sont compatibles dans $D \times E$. Réciproquement, si deux éléments $\langle d_1, e_1 \rangle$ et $\langle d_2, e_2 \rangle$ de $F$ sont compatibles dans $D \times E$ il y admettent une borne supérieure $\langle d_1 \vee d_2, e_1 \vee e_2 \rangle$. Or deux cas sont possibles :

i) $d_1$ ou $d_2$ est dans $O$. Alors $c_1 \vee d_2 \in O$ et $\langle d_1 \vee d_2, e_1 \vee e_2 \rangle \in F$

ii) $d_1 \notin O, d_2 \notin O$. Alors $e_1=e_2=\perp_E$ donc $e_1 \vee e_2=\perp_E$ et $\langle d_1 \vee d_2, e_1 \vee e_2 \rangle \in F$

Par suite deux éléments de $F$ sont compatibles ssi ils sont compatibles dans $D \times E$, et les bornes supérieures dans $F$ sont celles dans $D \times E$. Il en découle immédiatement que $F$ est cohérent. Montrons maintenant que $F$ est séparable. Si $x$ est un élément isolé de $D \times E$ appartenant à $F$, il est évidemment isolé dans $F$. De plus tout élément $\langle x,y \rangle$ de $F$ est la borne supérieure de ses approximants dans $D \times E$ par algébricité de $D \times E$. Mais si $\langle d,e \rangle$ est un approximant de $\langle x,y \rangle$ dans $A(D \times E) \setminus A(F) \langle x,y \rangle \in F$, c'est que $d$ n'est pas dans $O$ et $e \neq \perp_E$. Donc $y \neq \perp_E$ et par conséquent $x$ appartient à $O$. Comme la fonction caractéristique de $O$ est continue, il existe $c$ dans $A(x) \cap O$ avec

$$d \le c \le x$$

et $\langle d,e \rangle$ est dominé par $\langle c,e \rangle$ qui lui est un élément isolé de $F$. Par conséquent $\langle x,y \rangle = \bigcup \{ \langle d,e \rangle \mid \langle d,e \rangle \in A(D \times E) \cap F \}$. Donc $F$ est algébrique et séparable.
**Proposition P-8.11.** Soient $M_1 = \langle \Gamma_1, \nu_1, \nu_1, E_1 \rangle$ et $M_2 = \langle \Gamma_2, \nu_2, \nu_2, E_2 \rangle$ deux matrices d'informations et $X$ un ensemble de configurations finies de $M_1$. Définissons $M = \langle \Gamma, \nu, \nu, E \rangle$ de la manière suivante :

i) $\Gamma = \Gamma_1 \cup \Gamma_2$ (On peut supposer $\Gamma_1$ et $\Gamma_2$ disjoints sans perdre de généralité).

$$ii) \nu = \nu_1 \cup \nu_2$$

$$iii) \nu(c) = \begin{cases} \nu_1(c) & \text{si } c \in \Gamma_1 \\ \nu_2(c) & \text{si } c \in \Gamma_2 \end{cases}$$

iv) La fonction $E$ est définie par cas :

1. Si $\gamma \in \Gamma_D$ alors $E(\gamma) = E_D(\gamma)$

2. Si $\gamma \in \Gamma_E$ et $\Delta \in E_E(\gamma)$ alors $\forall \sigma \in X \{\sigma \} \cup \Delta \in E(\gamma)$

Alors si l'on pose $O = \{\sigma' | \sigma' \supseteq \sigma \in X\}$ on a :

$$\Sigma_M = \Sigma_{M_1} \stackrel{O}{\rightleftharpoons} \Sigma_{M_2}$$

**Démonstration** : Il est immédiat par définition que toute configuration de $\Sigma_M$ est configuration de la juxtaposition de $M_1$ et $M_2$ donc que $\Sigma_M$ est inclus dans $\Sigma_M \times \Sigma_{M_2}$. De plus la relation d'ordre sur $\Sigma_M$ est héritée de l'ordre sur $\Sigma_{M_1} \times \Sigma_{M_2}$. Si $\sigma$ est une configuration de $\Sigma_M$, soient $\sigma_1$ et $\sigma_2$ les ensembles de décisions restrictions de $\sigma$ à $\Gamma_1$ et à $\Gamma_2$ respectivement. Par définition de $E$, ou bien $\sigma_2=\emptyset$ et $\sigma_1$ est une configuration de $M_1$, ou bien $\sigma_1 \neq \emptyset$ et alors $\sigma_1$ contient au moins un élément de $X$. Donc $\tilde{\Gamma}_M$ est en injection avec $\Sigma_{M_1} \stackrel{O}{\rightleftharpoons} \Sigma_{M_2}$. Réciproquement, tout élément de $\Sigma_{M_1} \stackrel{O}{\rightleftharpoons} \Sigma_{M_2}$ est un ensemble de décisions compatibles de $\Sigma_{M_1} \times \Sigma_{M_2}$ et par définition de $E$ il est connecté dans $M$, ce qui conclut la preuve d'isomorphisme. $\square$

**Exemple** : Les matrices $M_1$ et $M_2$ représentent respectivement $O^2$ et $O$. Les matrices $M_i$ de la figure représentent chacune des greffes $F_i$ de $O$ sur $O^2$.
<table><tr><td>M<sub>0</sub></td><td></td></tr><tr><td>M<sub>02</sub></td><td></td></tr><tr><td>M<sub>1</sub></td><td></td></tr><tr><td>M<sub>2</sub></td><td></td></tr><tr><td>M<sub>3</sub></td><td></td></tr><tr><td>M<sub>4</sub></td><td></td></tr><tr><td>M<sub>5</sub></td><td></td></tr></table>

## I.9. Constructions par limite inverse

Nous nous intéressons maintenant à la possibilité de construire des domaines concrets par un processus de passage à la limite. Bien entendu, puisque la propriété d'être concret n'est pas en général préservée par exponentiation, il est exclu que cette propriété soit conservée lors de la construction d'une limite inverse arbitraire. Cependant il est clair que certaines constructions limites plus restreintes permettront de conserver cette propriété.

**Définition D-9.1.** Si $D$ et $E$ sont deux domaines de calcul on appelle projection une paire de fonctions continues $<\phi, \Psi>$ avec

$$ \phi \in [D \to E] \text{ et } \Psi \in [E \to D] $$
vérifiant

$$i) \forall x \in D \quad \Psi(\phi(x)) = x$$

$$ii) \forall x \in E \quad \phi(\Psi(x)) \leq x$$

**Définition D-9.2.** Une projection $<\phi, \Psi>$ entre D et E est rigide ssi

$$\forall d \in A(D), e \in A(E) \quad e \leq \phi(d) \Rightarrow e = \phi(\Psi(e))$$

**Proposition P-9.1.** Une projection $<\phi, \Psi>$ entre D et E est rigide ssi

$$\forall x \in D, y \in E \quad y \leq \phi(x) \Rightarrow y = \phi(\Psi(y))$$

**Démonstration** : Choisisons un approximant quelconque e de y dans E. Si e est dominé par $\phi(x)$, puisque $\phi$ est continue, il existe un approximant d de x avec

$$e \leq \phi(d)$$

Or $<\phi, \Psi>$ est une projection rigide donc

$$e = \phi(\Psi(e))$$

Comme $\phi$ et $\Psi$ sont continues, il en est de même de $\phi \circ \Psi$ et par suite

$$y = \bigcup_{e \in A(y)} e = \bigcup_{e \in A(y)} \phi(\Psi(e)) = \phi(\Psi(\bigcup_{e \in A(y)} e))$$

donc

$$y = \phi'(\Psi(y))$$

□

**Proposition P-9.2.** Il existe une projection rigide entre deux domaines de calcul D et E ssi D est isomorphe à un idéal cohérent de E.

**Démonstration** :

**Partie 1** : Soit J un idéal de E et $\phi$ la restriction à J de la fonction identité sur E. A tout x dans E associons $\Psi(x)$ par $\Psi(x) = \bigcup \{z | z \in A(x) \cap J\}$. Comme E est cohérent, l'élément $\Psi(x)$ existe bien et comme J est cohérent, cet élément se trouve dans J. Montrons que la fonction $\Psi$ est continue, en utilisant comme à l'habitude la caractérisation de la proposition II.4.6. Tout d'abord $\Psi$ est trivalement croissante. Soit maintenant e un approximant quelconque de $\Psi(x)$. Comme e est isolé et l'ensemble $\{z | z \in A(x) \cap J\}$ est dirigé, il existe un certain z avec

$$e \leq z \text{ et } z \in A(x) \cap J$$