Dioïde

En mathématiques et en informatique, un dioïde est un demi-anneau dans lequel le préordre défini par l'addition est une relation d'ordre.

Définition

Soit D un ensemble muni d'un opérateur binaire ${\displaystyle \oplus }$, nommé addition, d'un opérateur binaire ${\displaystyle \otimes }$, nommé produit, et dans lequel sont spécifiés deux éléments distincts, notés 0 et 1.

On note ≤ le préordre associé à l'opérateur ${\displaystyle \oplus }$ et défini par ${\displaystyle a\leq b\Leftrightarrow \exists c,~a\oplus c=b}$.

On dit que ${\displaystyle (D,\oplus ,\otimes ,0,1)}$ est un dioïde si :

• ${\displaystyle (D,\oplus ,0)}$ est un monoïde commutatif ;
• ${\displaystyle (D,\otimes ,1)}$ est un monoïde ;
• ${\displaystyle \otimes }$ est distributif par rapport à ${\displaystyle \oplus }$ ;
• 0 est un élément absorbant pour ${\displaystyle \otimes }$, c'est-à-dire que ${\displaystyle a\otimes 0=0\otimes a=0}$ ;
• la relation ≤ est une relation d'ordre, c'est-à-dire que ${\displaystyle a\leq b\wedge b\leq a\Rightarrow a=b}$.

Si l'on omet le dernier point, la structure définie est un demi-anneau.

Terminologie

Le nom de dioïde provient du fait qu'il combine deux monoïdes, comme tout demi-anneau (en particulier tout anneau). Ce nom a été employé par Jean Kuntzmann en 1972 pour la structure appelée maintenant demi-anneau^[1]. L'utilisation pour désigner un sous-groupe idempotent a été introduite par Baccelli et al. en 1992^[2].

Les dioïdes et les anneaux sont tous deux des demi-anneaux, mais ils sont exclusifs les uns des autres.

Dioïde idempotent

Le dioïde idempotent est la classe de dioïdes la plus utilisée. Il se caractérise le fait que tout élément ${\displaystyle a}$ est idempotent pour ${\displaystyle \oplus }$, c'est-à-dire que ${\displaystyle a\oplus a=a}$.

Par exemple, ${\displaystyle ([-\infty ,+\infty [,\max ,+,-\infty ,0)}$ est un dioïde idempotent.

Tout demi-anneau idempotent est un dioïde.

Démonstration

Il s'agit de prouver que la relation de préordre est un ordre. Si ${\displaystyle a\leq b}$ alors il existe c tel que ${\displaystyle a\oplus c=b}$, d'où

${\displaystyle b=a\oplus c=a\oplus a\oplus c=a\oplus b}$.

De même, si ${\displaystyle b\leq a}$ alors ${\displaystyle a=b\oplus a}$. Par conséquent, si ${\displaystyle a\leq b}$ et ${\displaystyle b\leq a}$, alors en utilisant la commutativité de ${\displaystyle \oplus }$ on obtient

${\displaystyle b=a\oplus b=b\oplus a=a}$.

Les demi-anneaux idempotents sont donc exactement les dioïdes idempotents.

Voir aussi

• Mathématiques tropicales