Demi-anneau

{{#ifeq:||Un article de Ziki, l'encyclopédie libre.|Une page de Ziki, l'encyclopédie libre.}}

Modèle:Confusion {{#invoke:Bandeau|ébauche}}

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

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

Ces propriétés sont proches de celles d'un anneau, la différence étant qu'il n'y a pas nécessairement d'inverses pour l’addition dans un demi-anneau.

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 <math>0\ne1</math>. 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)<ref>Modèle:Harvsp.</ref>.

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)<ref name=Sak28>Modèle:Harvsp.</ref>
  • Le demi-anneau de Boole composé de deux éléments 0 et 1. C'est l'algèbre de Boole : <math>(\{0, 1\}, \vee, \wedge, 0, 1)</math> où <math>\vee</math> et <math>\wedge</math> 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<ref name=Gut08>Modèle:Chapitre.</ref>.
  • Un treillis distributif est un demi-anneau commutatif et idempotent pour les lois <math>\vee</math> et <math>\wedge</math>.
  • Un treillis dans un anneau est un demi-anneau idempotent pour la multiplication et l'opération <math>\nabla</math> définie par <math>a\nabla b=a+b+ba-aba-bab</math>.
  • 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 des nombres réels positifs ou nuls, avec les additions et multiplications usuelles<ref name=LotIII211/>,<ref name="Pair66"/>.
  • Le Modèle:Lien sur <math>\R\cup \{\pm\infty\}</math> avec l’addition donnée par
Modèle:Retrait
et <math>+</math> pour multiplication, élément zéro <math>+\infty</math> et élément unité <math>0</math><ref name=LotIII211>Modèle:Harvsp.</ref>.

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é<ref name="droste"/>.
  • 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<ref name="droste"/>.
  • Plus généralement, l'ensemble des parties d'un monoïde, muni de la réunion et du produit des parties <math>U \cdot V = \{ u \cdot v \mid u \in U,\ v \in V \}</math> est un demi-anneau<ref name=BR4>Modèle:Harvsp.</ref>.
  • 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 à <math>\infty</math> de façon habituelle (toute somme avec <math>\infty</math> donne <math>\infty</math> ; tout produit avec <math>\infty</math> donne <math>\infty</math>, sauf pour 0 qui reste absorbant) muni de l'opérateur min et de la somme est un demi-anneau: <math>(\mathbb{N} \cup \{\infty\}, \min, +, \infty, 0)</math> 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<ref>

Modèle:Chapitre.</ref> à Dominique Perrin, alors qu'Imre Simon lui-même l'attribue à Christian Choffrut<ref> Modèle:Chapitre.</ref>,<ref> Mathoverflow, 2011, What's tropical about tropical algebra? sur Mathoverflow</ref>. 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<ref name="Pair66">Modèle:Chapitre</ref> : 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.

  • <math>(\mathbb{N} \cup \{\infty\}, \max, \min, 0, \infty)</math> 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 un 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 (<math>(f+g)(a)=f(a)+g(a)</math>) et pour multiplication la composition de fonctions. Le morphisme nul et l'identité sont les éléments neutres.
  • L'ensemble <math>S[x]</math> 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 <math>\sum_I</math> pour tout ensemble d'indices <math>I</math> et tel que les propriétés suivantes sont vérifiées<ref name="droste"/>,<ref>Modèle:Article</ref>,<ref name=Kuich90/>,<ref name=Kuich11/> :

<math>\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</math>

et

<math>\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'</math>

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 :

<math>a + \sup S = \sup(a + S) \ . </math>

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

<math> \sum_I a_i = \sup \sum_E a_i </math>

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<ref name=Kuich11/>.

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<ref name=Kuich11> Modèle:Harvsp. </ref>,<ref name="droste"/>,<ref name=Kuich90> Modèle:Chapitre</ref> :

<math>\sum_{i \in I}{(a \cdot a_i)} = a \cdot \bigl(\sum_{i \in I}{a_i}\bigl)</math> et <math>\sum_{i \in I}{(a_i \cdot a)} = \bigl(\sum_{i \in I}{a_i}\bigl) \cdot a</math>.

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<ref name=Sak471/>.

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<ref> Modèle:Chapitre. </ref>.

Tout demi-anneau continu est complet<ref name=Kuich11/> et on peut inclure cette propriété dans la définition<ref name=Sak471>Modèle:Harvsp.</ref>.

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<ref name=Esik08>Modèle:Harvsp.</ref>,<ref name="droste">Modèle:Harvsp.</ref>,<ref name="Lehmann">Modèle:Article.</ref>,<ref name=BR27>Modèle:Harvsp.</ref> :

<math>a^* = 1 + aa^* = 1 + a^*a.</math>

Exemples de demi-anneaux étoilés:

<math>R^* = \bigcup_{n \geq 0} R^n</math>.
Cette opération est la fermeture réflexive et transitive de la relation R<ref name="droste"/>.

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<ref name=Esik08/>,<ref>Modèle:Harvsp.</ref> :

<math>(a+b)^* = (a^*b)^*a^*,\,</math>
<math>(ab)^* = 1 + a(ba)^*b.\,</math>

Les trois premiers exemples ci-dessus sont aussi des demi-anneaux de Conway<ref name="droste"/>.

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<ref name=Esik08/> associés par John Conway aux groupes dans les demi-anneaux étoilés<ref>Modèle:Ouvrage</ref>

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<ref name="droste"/> :

<math>a^* = \sum_{j \geq 0}{a^j}</math>

avec <math> a^0 = 1</math> et <math> a^{j+1} = a \cdot a^j = a^j \cdot a</math> pour <math>j \geq 0</math>.

Les demi-anneaux des relations binaires, des langages formels et des nombres réels non négatifs étendus sont étoilés complets<ref name="droste"/>.

Un demi-anneau étoilé complet est aussi un demi-anneau de Conway<ref name="droste15">Modèle:Harvsp.</ref> mais la réciproque n'est pas vraie. Un exemple est fourni par les nombres rationnels non négatifs étendus <math>\{x\in\Q\mid x\ge0\}\cup\{\infty\}</math> avec l’addition et la multilication usuelles<ref name="droste"/>.

Notes et références

Modèle:Références

Bibliographie


Modèle:Palette Modèle:Portail

Récupérée de « https://wiki.trucsazeb.re:443/index.php?title=Demi-anneau&oldid=126799 »