Demi-anneau

Modèle:Confusion Modèle:Ébauche

En mathématiques, un demi-anneau, ou semi-anneau, est une structure algébrique $(E,+,\times ,0,1)$ qui a les propriétés suivantes :

$(E,+,0)$ constitue un monoïde commutatif ;
$(E,\times ,1)$ forme un monoïde ;
$\times$ est distributif par rapport à + ;
0 est absorbant pour le produit, autrement dit: pour tout $x\in E:x\times 0=0\times x=0$ .

Un demi-anneau est donc un anneau, à la différence près qu'il n'y a pas nécessairement d'inverses pour l’addition.

Un demi-anneau est commutatif quand son produit est commutatif ; il est idempotent quand son addition est idempotente. Parfois on distingue les demi-anneaux et les demi-anneaux unifères : dans ce cas, la structure multiplicative n'est qu'un demi-groupe, donc ne possède pas nécessairement un élément neutre. En général, on demande aussi que $0\neq 1$ . Un demi-anneau qui ne possède pas nécessairement un élément neutre pour sa multiplication est parfois appelé hémi-anneau (hemiring en anglais)^[1].

Contrairement à ce qui se passe pour les anneaux, on ne peut démontrer que 0 est un élément absorbant à partir des autres axiomes.

Domaines d'application

Les demi-anneaux se retrouvent souvent en :

recherche opérationnelle : les graphes pondérés ont des poids dans un demi-anneau ; le produit est associé à l'accumulation de valeur le long d'un chemin et la somme correspond à la façon de composer plusieurs chemins ; le calcul des plus courts chemins en est un exemple particulier.
théorie des langages et des automates : la concaténation des (ensembles de) chaînes pour en fabriquer d'autres est le produit. L'union des (ensembles de) chaînes est la somme ;
Modèle:Refnec

Exemples

Premiers exemples

Les entiers naturels forment un demi-anneau pour l'addition et la multiplication naturelles.
Les entiers naturels étendus Modèle:Nowrap} avec l'addition et la multiplication étendues et Modèle:Nowrap)^[2]
Le demi-anneau de Boole composé de deux éléments 0 et 1. C'est l'algèbre de Boole : $(\{0,1\},\vee ,\wedge ,0,1)$ où $\vee$ et $\wedge$ sont OU et ET respectivement.
En particulier, une algèbre de Boole est un tel demi-anneau. Un anneau de Boole est aussi un demi-anneau — puisque c'est un anneau — mais l'addition n’est pas idempotente. Un demi-anneau de Boole est un demi-anneau qui est isomorphe à un sous-demi-anneau d'une algèbre de Boole^[3].
Un treillis distributif est un demi-anneau commutatif et idempotent pour les lois $\vee$ et $\wedge$ .
Un treillis dans un anneau est un demi-anneau idempotent pour la multiplication et l'opération $\nabla$ définie par $a\nabla b=a+b+ba-aba-bab$ .
L'ensemble des idéaux d'un anneau forment un demi-anneau pour l'addition et la multiplication d'idéaux.
Les dioïdes sont des demi-anneaux particuliers.
Le demi-anneau des probabilités est nombres réels non négatifs avec les additions et multiplications unsuelles^[4]Modèle:,^[5].
Le log demi-anneau sur R ∪ ±∞ avec l’addition donnée par

Modèle:Retrait

et + pour multiplication, élément zéro +∞ et élément unité 0^[4].

Le demi-anneau de Łukasiewicz est l'intervalle fermé Modèle:Nowrap, avec l’addition donnée (Modèle:Nowrap) et la multiplication définie par Modèle:Nowrap. Un tel demi-anneau apparaît en logique polyvalente^[6].
Le demi-anneau de Viterbi est défini sur l'ensemble Modèle:Nowrap, avec l’addition donnée par le maximum et la multiplication usuelle ; il apparait dans l’analyse des grammaires probabilistes^[6].

Exemples généraux

L'ensemble des parties d'un ensemble E muni de l'union et de l'intersection est un demi-anneau. Les deux lois sont distributives l'une par rapport à l'autre, l'élément neutre de l'union est l'ensemble vide, celui de l'intersection est l'ensemble E. Les deux lois sont commutatives et forment avec E les deux monoïdes requis. C'est une algèbre de Boole et donc un treillis.
L'ensemble des relations binaires sur un ensemble, avec l'addition donnée par l'union et la multiplication par la composition des relations. Le zéro de ce demi-anneau est la relation vide, et son élément unité la relation identité^[6].
L'ensemble des langages formels sur un alphabet donné est un demi-anneau avec l'addition donnée par la réunion et le produit par le produit de concaténation des éléments. Le zéro est l'ensemble vide, et l'unité l'ensemble réduit au mot vide^[6].
Plus généralement, l'ensemble des parties d'un monoïde, muni de la réunion et du produit des parties $U\cdot V=\{u\cdot v\mid u\in U,\ v\in V\}$ est un demi-anneau^[7].
De même, la famille des parties d'un monoïde M avec multiplicités, c'est-à-dire des sommes formelles d'éléments de M à coefficients entiers naturels forment un demi-anneau. L'addition est la somme formelle avec addition de coefficients, et la multiplication est le produit de Cauchy. La somme nulle est l'élément neutre pour l'addition et le monöme formé de l'élément neutre de M est l'unité pour la multiplication.

Demi-anneau tropical

Modèle:Loupe

L'ensemble des entiers naturels étendu à $\infty$ de façon habituelle (toute somme avec $\infty$ donne $\infty$ ; tout produit avec $\infty$ donne $\infty$ , sauf pour 0 qui reste absorbant) muni de l'opérateur min et de la somme est un demi-anneau: $(\mathbb {N} \cup \{\infty \},\min ,+,\infty ,0)$ est connu sous les noms de (min,+)-demi-anneau et demi-anneau tropical, nommé ainsi en l'honneur de son promoteur Imre Simon. La création de l'adjectif tropical est attribuée par Jean-Éric Pin^[8] à Dominique Perrin, alors qu'Imre Simon lui-même l'attribue à Christian Choffrut^[9]Modèle:,^[10]. Le terme tropical fait juste référence aux origines brésiliennes, donc des Tropiques, d'Imre Simon. Cette structure sous-tend les algorithmes de calcul de plus court chemin dans un graphe^[5] : les poids sont additionnés le long des chemins et devant plusieurs chemins, on prend le coût minimal. Une variante est le (max,+)-demi-anneau, où le max prend la place de min. Tous deux sont des demi-anneaux tropicaux.
$(\mathbb {N} \cup \{\infty \},\max ,\min ,0,\infty )$ est le demi-anneau sous-jacent au calcul du flux maximum d'un graphe: dans une séquence d'arcs, celui de poids minimal impose son flux et devant plusieurs séquences, on prend le flux maximal.

Transfert de structure

Par transfert de structure :

Les matrices carrées d'ordre n à entrées dans une demi-anneau et avec l’addition et la multiplication induites ; ce demi-anneau n'est en général pas commutatif, même si le demi-anneau de ses entrées l’est.
L'ensemble End(A) des endomorphismes d'un monoïde commutatif A est un demi-anneau avec, pour addition, celle induite par A ( $f+g(a)=f(a)+g(a)$ ) et pour multiplication la composition de fonctions. Le morphisme nul et l'identité sont les éléments neutres.
L'ensemble $S[x]$ des polynômes à coefficients dans un demi-anneau S forment un demi-anneau, commutatif si S l'est, idempotent si S l'est. Si S est l'ensemble des entiers naturels, c'est le demi-anneau libre avec générateur {x}.

Demi-anneau complet et continu

Un monoïde complet est un monoïde commutatif qui possède une opération de sommation infinie $\sum _{I}$ pour tout ensemble d'indices $I$ tel que les propriétés suivantes sont vérifiées^[6]Modèle:,^[11]Modèle:,^[12]Modèle:,^[13] :

\sum _{i\in \emptyset }{m_{i}}=0;\quad \sum _{i\in \{j\}}{m_{i}}=m_{j};\quad \sum _{i\in \{j,k\}}{m_{i}}=m_{j}+m_{k}\quad {\textrm {pour}}\;j\neq k

et

\sum _{j\in J}{\sum _{i\in I_{j}}{m_{i}}}=\sum _{i\in I}(m_{i})\;{\textrm {si}}\bigcup _{j\in J}I_{j}=I\;{\textrm {et}}\;I_{j}\cap I_{j'}=\emptyset \;{\textrm {pour}}\;j\neq j'

Un monoïde continu est un monoïde ordonné pour lequel tout ensemble ordonné filtrant a une borne supérieure qui de plus est compatible avec l'opération de monoïde :

$a+\sup S=\sup(a+S)\ .$

Les deux concepts sont étroitement liés : un monoïde continu est complet, la somme infinie peut en effet être définie par :

\sum _{I}a_{i}=\sup \sum _{E}a_{i}

où le "sup" est pris sur tous les sous-ensembles finis E de I et chaque sommation, dans le membre droit, porte donc sur un ensemble fini^[13].

Un demi-anneau complet est un demi-anneau pour lequel le monoïde additif est un monoïde complet, et qui vérifie les lois de distributivité infinie suivantes^[13]Modèle:,^[6]Modèle:,^[12] :

\sum _{i\in I}{(a\cdot a_{i})}=a\cdot {\bigl (}\sum _{i\in I}{a_{i}}{\bigl )}

et

\sum _{i\in I}{(a_{i}\cdot a)}={\bigl (}\sum _{i\in I}{a_{i}}{\bigl )}\cdot a

.

Un exemple de demi-anneaux complet est l'ensemble des parties d'un monoïde pour l'union ; le demi-anneau des matrices à entrées dans un demi-anneau complet est lui-même un demi-anneau complet^[14].

Un demi-anneau continu est un monoïde continu dont la multiplication respecte l'ordre et le bornes supérieures. Le demi-anneau Modèle:Nowrap} avec l'addition, la multiplication, et l'ordre naturel est une demi-anneau continu^[15].

Tout demi-anneau continu est complet^[13] et on peut inclure cette propriété dans la définition^[14].

Demi-anneau étoilé

Un demi-anneau étoilé (en anglais star semiring ou starsemiring est un demi-anneau muni d'un opérateur unaire supplémentaire noté « * » satisfaisant^[16]Modèle:,^[6]Modèle:,^[17]Modèle:,^[18] :

a^{*}=1+aa^{*}=1+a^{*}a.

Exemples de demi-anneaux étoilés:

Le demi-anneau de Boole avec Modèle:Nowrap;
Le demi-anneau des relations binaires sur un ensemble U, où l'étoile d'une relation R est définie par

R^{*}=\bigcup _{n\geq 0}R^{n}

.

Cette opération est la fermeture réflexive et transitive de la relation R^[6].

Le demi-anneau des langages formels est un demi-anneau étoilé complet, l'opération étoile étant l'étoile de Kleene^[6].
L'ensemble des nombres réels positifs augmentés de ∞, avec l'addition et la multiplication usuelles est un demi-anneau complet étoilé avec l'opération étoile donnée par Modèle:Nowrap pour Modèle:Nowrap (la série géométrique usuelle) et Modèle:Nowrap pour Modèle:Nowrap^[6].
Le demi-anneau Modèle:Nowrap avec addition et multiplication étendues, et Modèle:Nowrap, Modèle:Nowrap pour Modèle:Nowrap.

Algèbre de Kleene

Une algèbre de Kleene est un demi-anneau étoilé avec une addition idempotente; elles interviennent en théorie des langages et dans les expressions régulières.

Demi-anneau de Conway

Un demi-anneau de Conway est un demi-anneau étoilé qui vérifie les équations suivantes entre l'opération étoile et l’addition et la multiplication^[16]Modèle:,^[19] :

(a+b)^{*}=(a^{*}b)^{*}a^{*},\,

(ab)^{*}=1+a(ba)^{*}b.\,

Les trois premiers exemples ci-dessus sont aussi des demi-anneaux de Conway^[6].

Demi-anneau itératif

Un demi-anneau itératif (en anglais iteration semiring) est un demi-anneau de Conway qui vérifie les axiomes de Conway des groupes^[16] associés par John Conway aux groupes dans les demi-anneaux étoilés^[20]

Demi-anneau étoilé complet

Un demi-anneau étoilé complet est un demi-anneau où l'étoile a les propriétés habituelles de l'étoile de Kleene ; on la définit à l'aide de l'opérateur de sommation infinie par^[6] :

a^{*}=\sum _{j\geq 0}{a^{j}}

avec $a^{0}=1$ et $a^{j+1}=a\cdot a^{j}=a^{j}\cdot a$ pour $j\geq 0$ .

Les demi-anneaux des relations binaires, des langages formels et des nombres réels non négatifs étendus sont étoilés complets^[6].

Un demi-anneau étoilé complet est aussi un demi-anneau de Conway^[21] mais la réciproque n'est pas vraie. Un exemple est fourni par les nombres rationnels non négatifs étendus $\{x\in \mathbb {Q} \mid x\geq 0\}\cup \{\infty \}$ avec l’addition et la multilication usuelles^[6].

Notes et références

Modèle:Références

Bibliographie

Modèle:Chapitre
Modèle:Ouvrage
Modèle:Ouvrage
Modèle:Ouvrage — Édition revue et augmentée de Modèle:Ouvrage
Modèle:Ouvrage
Modèle:Ouvrage — Édition en anglais : Modèle:Ouvrage
Modèle:Ouvrage
Modèle:Ouvrage
Modèle:Chapitre
Modèle:Chapitre
Modèle:Chapitre
Modèle:Chapitre.

Modèle:Palette Modèle:Portail

↑ Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Modèle:Chapitre.
↑ ^4,0 et ^4,1 Modèle:Harvsp.
↑ ^5,0 et ^5,1 Modèle:Chapitre
↑ ^6,00 ^6,01 ^6,02 ^6,03 ^6,04 ^6,05 ^6,06 ^6,07 ^6,08 ^6,09 ^6,10 ^6,11 ^6,12 et ^6,13 Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Modèle:Chapitre.
↑ Modèle:Chapitre.
↑ Mathoverflow, 2011, What's tropical about tropical algebra? sur Mathoverflow
↑ Modèle:Article
↑ ^12,0 et ^12,1 Modèle:Chapitre
↑ ^13,0 ^13,1 ^13,2 et ^13,3 Modèle:Harvsp.
↑ ^14,0 et ^14,1 Modèle:Harvsp.
↑ Modèle:Chapitre.
↑ ^16,0 ^16,1 et ^16,2 Modèle:Harvsp.
↑ Modèle:Article.
↑ Modèle:Harvsp.
↑ Modèle:Harvsp.
↑ Modèle:Ouvrage
↑ Modèle:Harvsp.

[1] Modèle:Harvsp.

[Sak28-2] Modèle:Harvsp.

[Gut08-3] Modèle:Chapitre.

[LotIII211-4] 4,0 et ^4,1 Modèle:Harvsp.

[Pair66-5] 5,0 et ^5,1 Modèle:Chapitre

[droste-6] 6,00 ^6,01 ^6,02 ^6,03 ^6,04 ^6,05 ^6,06 ^6,07 ^6,08 ^6,09 ^6,10 ^6,11 ^6,12 et ^6,13 Modèle:Harvsp.

[BR4-7] Modèle:Harvsp.

[8] Modèle:Chapitre.

[9] Modèle:Chapitre.

[10] Mathoverflow, 2011, What's tropical about tropical algebra? sur Mathoverflow

[11] Modèle:Article

[Kuich90-12] 12,0 et ^12,1 Modèle:Chapitre

[Kuich11-13] 13,0 ^13,1 ^13,2 et ^13,3 Modèle:Harvsp.

[Sak471-14] 14,0 et ^14,1 Modèle:Harvsp.

[15] Modèle:Chapitre.

[Esik08-16] 16,0 ^16,1 et ^16,2 Modèle:Harvsp.

[Lehmann-17] Modèle:Article.

[BR27-18] Modèle:Harvsp.

[19] Modèle:Harvsp.

[20] Modèle:Ouvrage

[droste15-21] Modèle:Harvsp.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

Demi-anneau

Sommaire

Domaines d'application