Semigruppo

In matematica, un semigruppo è un insieme munito di un'operazione binaria associativa. In altre parole per semigruppo si intende una struttura algebrica espressa da una coppia $(A,*)$ con $A$ insieme e $*$ funzione definita su $A\times A$ a valori in $A$ per la quale si ha:

$a*(b*c)=(a*b)*c\qquad {\text{per ogni }}a,b,c\in A.$

Equivalentemente si può definire come semigruppo ogni magma associativo.

Se l'operazione è commutativa si parla di semigruppo commutativo o semigruppo abeliano.

Primi esempi

Si incontrano molti esempi di semigruppi, finiti e infiniti. Consideriamone alcuni facilmente definibili.

• L'insieme vuoto.
• L'insieme dei numeri interi positivi munito dell'addizione (operazione notoriamente associativa). Questo semigruppo è commutativo.
• L'insieme dei numeri interi naturali munito della moltiplicazione (anche questa operazione è notoriamente associativa). Questo semigruppo è commutativo.
• L'insieme $\{1,2,3,4\}$ munito dell'operazione $\max(m,n)$: per l'associatività basta osservare che, evidentemente,

$\max(\max(m,n),p)=\max(m,n,p)=\max(m,\max(n,p)).$

Questo semigruppo è commutativo ed è un semigruppo finito di 4 elementi. La sua tavola di moltiplicazione consiste nella matrice

${\begin{bmatrix}1&2&3&4\\2&2&3&4\\3&3&3&4\\4&4&4&4\end{bmatrix}}.$

• L'insieme di tutte le endofunzioni definite su un insieme $S,$ ad esempio su $\{1,2,3,4\}$, munito della composizione di funzioni. La composizione di funzioni è infatti associativa. Questo semigruppo non è commutativo. In effetti non è commutativo neppure il semigruppo delle endofunzioni di un qualsiasi insieme ambiente $S$ formato da 2 o più elementi. Per questo basta considerare il controesempio di due endofunzioni che non commutano: se $a$ e $b$ sono due elementi diversi di $S,$ introduciamo le due funzioni a valore costante $f_{a}$ e $f_{b}$, definite da $f_{a}(s)=a$ e $f_{b}(s)=b$ per ogni $s\in S.$ Le due composizioni di queste funzioni danno quindi

$(f_{a}\circ f_{b})(s)=a\neq b=(f_{b}\circ f_{a})(s),\qquad {\text{per ogni }}s\in S,$

da cui risulta che $f_{a}\circ f_{b}\neq f_{b}\circ f_{a}.$

• L'insieme, numerabile, di tutte le stringhe sopra un dato alfabeto munito della giustapposizione di stringhe. La giustapposizione di stringhe è una specie di archetipo delle operazioni binarie associative. Questo semigruppo si chiama semigruppo libero sull'alfabeto prefissato. Questo semigruppo non è commutativo se viene costruito su un alfabeto di due o più caratteri.

Semigruppi e monoidi

Un semigruppo dotato di un elemento neutro, cioè un semigruppo unitale o unitario di solito viene chiamato monoide. Ogni semigruppo S può essere fatto diventare un monoide semplicemente aggiungendogli un elemento e non facente parte di S e definendo ee := e ed es := s =: se per ogni s in S. Un tale ampliamento può essere effettuato più volte (i "vecchi" elementi neutri non sono più tali, ma assorbono la composizione con i "nuovi").

Viceversa dato un monoide lo si riduce a semigruppo eliminando semplicemente l'elemento unità e riga e colonna corrispondenti della tavola di moltiplicazione; questo semigruppo potrebbe contenere o non contenere un nuovo elemento neutro. Dunque lo studio dei monoidi aggiunge ben poco allo studio dei semigruppi: le due specie di strutture sono sostanzialmente equivalenti.

Un monoide con base si definisce monoide libero: esso è un semigruppo con elemento neutro dotato di base per i suoi elementi. Il linguaggio di un automa a stati finiti rappresentato dall'insieme delle stringhe su un certo alfabeto $\Sigma$ è un esempio importante di monoide libero.

Altri esempi di semigruppi

• Ogni gruppo può considerarsi un monoide.
• Ogni ideale di un qualsiasi anello, munito dell'operazione di moltiplicazione per l'anello.
• Ogni sottoinsieme di un semigruppo che sia chiuso per l'operazione di semigruppo.
• Un semigruppo la cui operazione è commutativa e idempotente è un semireticolo. Semireticoli di questo genere sono dati dalla collezione dei sottoinsiemi di un dato ambiente munita dell'intersezione (oppure dell'unione).
• L'insieme di tutte le relazioni entro un insieme munito della composizione tra relazioni.
• L'insieme di tutti i linguaggi su un dato alfabeto munito della giustapposizione fra linguaggi.

Isomorfismi, sottosemigruppi e ideali

Introduciamo ora le relazioni e le costruzioni che costituiscono il normale armamentario per lo studio delle caratteristiche delle strutture algebriche della specie semigruppi. Per brevità, l'operazione del semigruppo generico viene presentata con la semplice giustapposizione, cioè xy denota il risultato della applicazione dell'operazione di semigruppo alla coppia ordinata (x, y). Se A e B sono sottoinsiemi di un semigruppo, allora AB denota l'insieme { ab | a in A e b in B }.

Due semigruppi S e T si dicono isomorfi se esiste una biiezione f : S → T con la proprietà che, per ogni coppia di elementi a, b in S, f(ab) = f(a)f(b). In questo caso f si dice isomorfismo di S su T. Se ci si limita a considerare le caratteristiche degli elementi dei semigruppi collegate alle operazioni di tali strutture due semigruppi isomorfi sono del tutto equivalenti: potranno invece essere distinti da altre proprietà derivanti dalle modalità secondo le quali sono stati costruiti.

Un sottoinsieme A non vuoto di un semigruppo S viene detto sottosemigruppo di S se è chiuso per la operazione di semigruppo, ossia se AA è un sottoinsieme di A. A viene detto ideale destro se AS è sottoinsieme di A, e simmetricamente viene chiamato ideale sinistro se SA è sottoinsieme di A. Se A è contemporaneamente ideale sinistro e ideale destro, allora viene chiamato ideale bilatero o semplicemente ideale di S. Si vede rapidamente che l'intersezione di due ideali è anch'essa un ideale: se ne deduce che un semigruppo può avere al più un ideale minimale. Il generico ideale del semigruppo degli interi positivi muniti dell'addizione è l'insieme dei multipli di un qualsiasi intero positivo. Si vede quindi che il semigruppo additivo dei positivi non possiede ideale minimale. L'ideale minimale di un semigruppo commutativo, quando esiste, è un gruppo.

Generazione di sottosemigruppi

Se S è un semigruppo, allora l'intersezione di ogni collezione di suoi sottosemigruppi è anch'essa un sottosemigruppo si S. Dunque i sottosemigruppi di S formano un reticolo completo. Per ogni sottoinsieme A di S tra i sottosemigruppi di S che contengono tale A ne esiste uno ed uno solo minimale per la inclusione; se lo denotiamo T, si dice che A genera T. Ogni elemento x di S genera il sottosemigruppo { xⁿ |: n intero positivo } che si denota <x>. Se tale sottoinsieme di S è finito si dice che x è di ordine finito, oppure che ha ordine finito; più precisamente si dice ordine di x in S la cardinalità del sottosemigruppo generato. Se viceversa <x> è infinito (evidentemente infinito numerabile) si dice che x è di, oppure ha, ordine infinito.

Si dice semigruppo periodico ogni semigruppo costituito solo da elementi di ordine finito. Chiaramente ogni semigruppo finito è periodico.

Si dice semigruppo monogenico ogni semigruppo che può considerarsi generato da un singolo elemento (talora viene detto anche semigruppo ciclico, ma questa espressione può indurre confusione). Ogni semigruppo monogenico infinito è isomorfo al semigruppo additivo degli interi positivi.

Anche i semigruppi monogenici finiti possono essere individuati in modo esauriente. Denotando x un suo generatore e n la sua cardinalità i suoi elementi possono essere elencati come successive potenze di x: x, x², ... ,xⁿ; la successiva potenza xⁿ⁺¹ deve coincidere con una potenza inferiore, scriviamola x^k. Gli interi n e k caratterizzano completamente il semigruppo. Consideriamo l'insieme di p:=n-k+1 elementi G := {m=k, k+1, ...,n :| x^m }. Chiaramente esso costituisce un sottosemigruppo di S; più precisamente si tratta di un gruppo, in quanto i suoi elementi vengono permutati quando vengono moltiplicati per uno di essi. Se k=1 il semigruppo è il gruppo ciclico di n elementi. L'unità del sottogruppo è un idempotente del semigruppo; ogni altro elemento del semigruppo moltiplicato per sé stesso porta ad un altro elemento. Dunque ogni semigruppo periodico finito contiene almeno un elemento idempotente e ogni semigruppo monogenico finito contiene esattamente un idempotente. Si osserva anche che il sottogruppo (gruppo ciclico) di un semigruppo monogenico finito è un ideale del semigruppo.

Semigruppi e gruppi

Un sottosemigruppo di un semigruppo S che è anche un gruppo viene detto sottogruppo di S. Vi è una stretta relazione tra i sottogruppi di un semigruppo e i suoi idempotenti. Ogni sottogruppo contiene esattamente un idempotente, cioè l'elemento neutro del semigruppo. Per ogni idempotente e del semigruppo esiste un unico sottogruppo massimale che contiene e. Ogni sottogruppo massimale viene individuato in questo modo, e di conseguenza esiste una corrispondenza biunivoca tra idempotenti e sottogruppi massimali. Si dovrebbe notare che il termine sottogruppo massimale viene qui usato in modo differente da come viene usato in teoria dei gruppi. In questa teoria un sottogruppo massimale si sottintende che sia un sottogruppo proprio. Quando è considerato come semigruppo, un gruppo possiede solo un sottogruppo massimale, cioè sé stesso.

Semigruppi di endofunzioni

Ogni semigruppo può considerarsi un semigruppo di endofunzioni: infatti si può associare ad ogni elemento y di un semigruppo S la endofunzione di S corrispondente alla moltiplicazione a destra per y dei suoi varielementi. Viceversa ad ogni insieme E di endofunzioni di un insieme ambiente A si associa il semigruppo <E> generato dagli elementi di E (e da tutti i loro prodotti). Se A è infinito il semigruppo <E> può essere finito o infinito; se A è finito <E> evidentemente deve essere finito.

Si possono considerare anche semigruppi generati da insiemi di relazioni entro un insieme ambiente. Si trova che questi semigruppi si possono ridurre a semigruppi di endofunzioni: si tratta di passare dalle relazioni entro un insieme A alle endofunzioni entro l'insieme delle parti di A. I semigruppi di endofunzioni entro insiemi finiti possono essere convenientemente trattati come semiautomi deterministici (a stati finiti), mentre i semigruppi di relazioni entro insiemi finiti possono essere trattati come semiautomi non-deterministici. In proposito si veda teoria degli automi a stati finiti.

I risultati su questi semigruppi e questi automi possono essere formulati anche come fatti riguardanti relazioni di congruenza entro monoidi liberi su alfabeti finiti che forniscono quozienti finiti. In proposito si veda teoria dei linguaggi razionali (o dei linguaggi regolari).

Sui semigruppi finiti visti nei modi precedenti si può dire molto di più. Notevoli risultati sulla classificazione delle strutture di tali semigruppi finiti sono ottenuti dalla teoria di Krohn-Rhodes.

Bibliografia

• (EN) John M. Howie (1995): Fundamentals of Semigroup Theory, Oxford University Press, ISBN 0198511949
• (EN) Aldo Belleni Morante, Applied semigroups and evolution equations, Oxford Mathematical Monographs. The Clarendon Press, Oxford University Press, New York, 1979. XV+387 pp. ISBN 0-19-853529-5
• (EN) Aldo Belleni Morante, A Concise Guide to Semigroups and Evolution Equations, Series on Advances in Mathematics for Applied Sciences, World Scientific Publishing Co. Inc., River Edge, NJ, 1994. XIV+164 pp. ISBN 981-02-1294-1

Voci correlate

• Gruppo di Grothendieck
• Linguaggio formale

Altri progetti

Altri progetti

• Wikizionario

• Wikizionario contiene il lemma di dizionario «semigruppo»

Collegamenti esterni

• Semigruppo, su Treccani.it – Enciclopedie on line, Istituto dell'Enciclopedia Italiana.
• Semigruppo, in Dizionario delle scienze fisiche, Istituto dell'Enciclopedia Italiana, 1996.
• Semigruppo, su Vocabolario Treccani, Istituto dell'Enciclopedia Italiana.
• semigrùppo, su sapere.it, De Agostini.
• Semigruppo, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) semigroup, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Semigroup, su MathWorld, Wolfram Research.
• (EN) Semi-group, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.